On the calculation of Crowding Distance

Version 1.0.0.0 (4.66 KB) by SKS Labs
This submission demonstrates the issues in the calculation of crowding distance
337 Downloads
Updated 23 Jan 2018

View License

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

Cite As

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. Retrieved .

MATLAB Release Compatibility
Created with R2017b
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

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

Start Hunting!
Version Published Release Notes
1.0.0.0

Correction in references