Pareto Front

Two efficient algorithms to find Pareto Front

Description

Identifying the Pareto Front from a set of points in a multi-objective space is the most important and also the most time-consuming task in multi-objective optimization. Usually, this is done through so called nondominated sorting. In this package, two efficient algorithms are provided to find the Pareto Front from a large set of multi-objective points.

The basic algorithm is implemented as an mex function. The algorithm considers the logical relationship between dominated and nondominated points to avoid unnecessary comparisons as much as possible so that the overall operations reduced from n x n x m for an n x m problem to r x n x m, where r is the size of the final Pareto Front.

The second algorithm takes the advantage of vectorization of MATLAB to splits the given objective set into several smaller groups to be examined by the first algorithm. Then, the Pareto Fronts of each group are combined as one set to be
re-checked by the first algorithm again to determine the overall Pareto
Front. Numerical tests show that, the overal computation time can be reduced about half of using the first algorithm alone.

Acknowledgements

The author wishes to acknowledge the following in the creation of this submission:
Performing Pareto set membership tester for sets of points in K-dimensions, Pareto Set
This submission has inspired the following:
Hypervolume Indicator

• MATLAB release: MATLAB 7.5 (R2007b)
• Other requirements: The mex file enclosed is compiled under MATLAB R2007b Windows XP. For other version of MATLAB and platforms, please use command "mex paretofront.c" to re-compile the file before use.
• Other Files: paretofront.mexw32, ; paretofront.c, ; paretofront.m, ; paretoGroup.m

[Timo A]

This is excellent package and very fast implementation to determine nondominated points in a given set. Works very well also with big sets. As I am working with multiobjective optimization algorithms, this package has been very useful to me. Thank you very much for sharing!

[liudaohai liudaohai]

file paretoGroup.m error:
gRoup=max(1,floor(m/groupcut));
modified:
gRoup=max(1,ceil(m/groupcut));or
for k=1:gRoup-->for k=1:gRoup + 1

[Yi Cao]

Thanks for pointing this out. It has been fixed now. The updated version should be available for download in a few days.

[liudaohai liudaohai]

gRoup=ceil(m/groupcut);

[liudaohai liudaohai]

inconsistent:
if X=[3 1;3 1;3 1];and membership=paretofront(X),then membership=[1 0 0]';
membership=isparetosetMember(X);membership=[1 1 1]'.
(Performing Pareto set membership tester for sets of points in K-dimensions)

[matt dash]

Of all the pareto front algorithms for MATLAB i've come across or written, this one is my favorite.

[V. Poor]

 

[BASKAR Subramanian]

Hi,

Can we use this code for more than two objectives?
We are getting the scattered front when using more than two objectives.

[Yi Cao]

Yes, you can. For a higher dimension, you have to provide much more data points.

HTH
Yi

[Pompilia Buzatu]

Can anyone explain to me how to use these files? :-/ Thank you!