On the calculation of Crowding Distance

버전 1.0.0.0 (4.66 KB) 작성자: SKS Labs
This submission demonstrates the issues in the calculation of crowding distance

다운로드 수: 312

업데이트 날짜: 2018/1/23

라이선스 보기

Crowding distance is widely used in multi-objective optimization and is a measure of "density of solutions surrounding a particular solution in the population" [1]
The procedure to determine the crowding-distance is given as following in the literature

"The crowding-distance computation requires sorting the population according to each objective function value in ascending order of magnitude. Thereafter, for each objective function, the boundary solutions (solutions with smallest and largest function values) are assigned an infinite distance value. All other intermediate solutions are assigned a distance value equal to the absolute normalized difference in the function values of two adjacent solutions. This calculation is continued with other objective functions. The overall crowding-distance value is calculated as the sum of individual distance values corresponding to each objective." [1]

Thus the crowding distance has to be unique for a given dataset. However some of the most common implementations [2,3,4] do not seem to be appropriately calculating the crowding distance.

In this submission, we determine the crowding distance of two datasets involving 4 points and 3 objectives. All the four points are non-dominated solutions. The only difference between dataset1 and dataset2 is that two of the rows are swapped.

As per the definition of crowding distance, both dataset1 and dataset2 should have the same crowding distance. However the use of the function "distancecrowding" of MATLAB yields two different results.

The same issue is prevalent in the code of Aravind Sheshadri [3] and also in the PLATEMO software [4]

References:
[1] A fast and elitist multiobjective genetic algorithm: NSGA-II,
IEEE Transactions on Evolutionary Computation, 6(2): 182-197
http://ieeexplore.ieee.org/document/996017/

[2] https://in.mathworks.com/help/gads/genetic-algorithm-options.html

[3] https://in.mathworks.com/matlabcentral/fileexchange/10429-nsga-ii--a-multi-objective-optimization-algorithm
function non_domination_sort_mod

[4] PlatEMO: A MATLAB Platform for Evolutionary Multi-Objective Optimization [Educational Forum], IEEE Computational Intelligence Magazine, 2017, 12(4): 73-87
http://bimk.ahu.edu.cn/index.php?s=/Index/Software/index.html - PlatEMO v1.5 (2017/11/24)
function CrowdingDistance.m

인용 양식

SKS Labs (2023). On the calculation of Crowding Distance (https://www.mathworks.com/matlabcentral/fileexchange/65809-on-the-calculation-of-crowding-distance), MATLAB Central File Exchange. 검색됨 .

MATLAB 릴리스 호환 정보
개발 환경: R2017b
모든 릴리스와 호환
플랫폼 호환성
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
버전 게시됨 릴리스 정보
1.0.0.0

Correction in references