On the calculation of Crowding Distance

版本 1.0.0.0 (4.7 KB) 作者: SKS Labs
This submission demonstrates the issues in the calculation of crowding distance
339.0 次下载
更新时间 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 (2024). 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
类别
Help CenterMATLAB Answers 中查找有关 Genetic Algorithm 的更多信息

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