Multi-objective optimization is a search for solutions to problems that have several, often conflicting, objectives: reducing costs while increasing performance or reducing weight while increasing strength… For these kinds of problems, usually there is no solution that could be singled out as the best one, but there is a set of non-dominated solutions. One solution dominates the other when the first one has no objective value that is worse than corresponding value of the second solution and has at least one objective value that is better than the corresponding value of the second. Solution is non-dominated when there is no other solutions that dominates it. That means it is not possible to improve one objective without degrading other objectives for the non-dominated solution. Set of all non-dominated solutions is called Pareto set. Number of non-dominated solutions can be infinite, so an algorithm cannot provide whole Pareto set but its approximation. Diversity of the selected solution in the approximated set is important so that whole Pareto set is represented equally.
Simple genetic algorithms are designed for optimizing problems with a single objective and are incapable to handle situations when several objectives should be considered. The solution to this problem would be to transform multiple objective values to a single fitness value.
Naïve approach would be to assign weight to each objective and then use sum of weighted values of all objective functions as fitness value. Some of the problems that arise are selecting appropriate weights for the objectives, keeping diversity of the solutions and there is no guarantee that solutions with highest fitness values are non-dominated solutions.
There are number of proposed solutions for overcoming these problems, that allow genetic algorithms to handle multi-objective optimization effectively. They often vary greatly in their design, but there are several criteria by which they can be grouped:
- fitness assignment – how the algorithm assigns fitness value based on values of objective functions of the solutions
- diversity mechanism – how the algorithm preserves diversity of the selected non-dominated solutions
- elitism – whether the algorithms keeps non-dominated solutions between the generations
- external populations – whether the algorithm requires additional external populations/archives
In-depth discussion about multi-objective optimization and overview of popular algorithms can be found here:
- Multi-objective optimization using genetic algorithms: A tutorial [CiteSeerX, PDF]
- Multi-objective optimization using genetic algorithms: A tutorial [ScienceDirect, PDF] – this version contains comparative review of popular algorithms
The following table lists all multi-objective optimization algorithms implemented by the library:
Vector Evaluated Genetic Algorithm (VEGA) | ||||
Multiple Objective Optimization with Vector Evaluated Genetic Algorithms [ACM, PDF] | ||||
fitness | diversity | elitism | ext. population | |
each objective value is separately used as fitness | no | no | no | |
Algorithm Stub | implemented by: Algorithm::Stubs::GaSimpleGAStub class |
|||
located in: SimpleStub.h and SimpleStub.cpp files |
||||
note: use Multiobjective::VEGA::GaVEGA scaling operation |
||||
Implementation | namespace: Multiobjective::VEGA |
|||
located in: VEGA.h and VEGA.cpp |
||||
Non-dominated Sorting Genetic Algorithm (NSGA) | ||||
Multiobjective Optimization Using Non-dominated Sorting in Genetic Algorithms [CiteSeerX, PDF] | ||||
fitness | diversity | elitism | ext. population | |
rank based on non-dominated sorting | fitness sharing by niching | no | no | |
Algorithm Stub | implemented by: Algorithm::Stubs::GaNSGAStub class |
|||
located in: NSGAStub.h and NSGAStub.cpp files |
||||
Implementation | namespace: Multiobjective::NSGA |
|||
located in: NSGA.h and NSGA.cpp |
||||
Fast Elitist Non-Dominated Sorting Genetic Algorithm (NSGA2) | ||||
A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II [CiteSeerX, PDF] | ||||
fitness | diversity | elitism | ext. population | |
rank based on non-dominated sorting | crowding distance | yes | no | |
Algorithm Stub | implemented by: Algorithm::Stubs::GaNSGA2Stub class |
|||
located in: NSGAStub.h and NSGAStub.cpp files |
||||
Implementation | namespace: Multiobjective::NSGA |
|||
located in: NSGA.h and NSGA.cpp |
||||
Strength Pareto Evolutionary Algorithm (SPEA) | ||||
Multi-objective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach [CiteSeerX, PDF] | ||||
fitness | diversity | elitism | ext. population | |
rank based on external set of non-dominated solutions | clustering | yes | yes | |
Algorithm Stub | implemented by: Algorithm::Stubs::GaSPEAStub class |
|||
located in: SPEAStub.h and SPEAStub.cpp files |
||||
Implementation | namespace: Multiobjective::SPEA |
|||
located in: SPEA.h and SPEA.cpp |
||||
Improved Strength Pareto Evolutionary Algorithm (SPEA2) | ||||
SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multi-objective Optimization [CiteSeerX, PDF] | ||||
fitness | diversity | elitism | ext. population | |
strength of dominators | density of k-th nearest neighbor | yes | yes | |
Algorithm Stub | implemented by: Algorithm::Stubs::GaSPEA2Stub class |
|||
located in: SPEAStub.h and SPEAStub.cpp files |
||||
Implementation | namespace: Multiobjective::SPEA |
|||
located in: SPEA.h and SPEA.cpp |
||||
Pareto Envelope-based Selection Algorithm (PESA) | ||||
The Pareto Envelope-based Selection Algorithm for Multi-objective Optimization [CiteSeerX, PDF] | ||||
fitness | diversity | elitism | ext. population | |
fitness is based on density | cell-based density | pure | yes | |
Algorithm Stub | implemented by: Algorithm::Stubs::GaPESAStub class |
|||
located in: PESAStub.h and PESAStub.cpp files |
||||
Implementation | namespace: Multiobjective::PESA |
|||
located in: PESA.h and PESA.cpp |
||||
Pareto Region-based Selection Algorithm (PESA2) | ||||
PESA-II:Region-based Selection in Evolutionary Multi-objective Optimization [CiteSeerX, PDF] | ||||
fitness | diversity | elitism | ext. population | |
fitness is based on density, assigned to a group of solutions | cell-based density | pure | yes | |
Algorithm Stub | implemented by: Algorithm::Stubs::GaPESAStub class |
|||
located in: PESAStub.h and PESAStub.cpp files |
||||
note: whether the PESA or PESA-II will be used is controlled by algorithm parameters (GaPESAParams class, SetRegionSharing method) |
||||
Implementation | namespace: Multiobjective::PESA |
|||
located in: PESA.h and PESA.cpp |
||||
Pareto Archived Evolution Strategy (PAES) | ||||
The Pareto Archived Evolution Strategy: A New Baseline Algorithm for Pareto Multi-objective Optimization [CiteSeerX, PDF] | ||||
fitness | diversity | elitism | ext. population | |
dominant offspring replaces parent | cell-based density | yes | yes | |
Algorithm Stub | implemented by: Algorithm::Stubs::GaPAESStub class |
|||
located in: PAESStub.h and PAESStub.cpp files |
||||
Implementation | namespace: Multiobjective::PAES |
|||
located in: PAES.h and PAES.cpp |
||||
Rank-Density-Based Multi-objective Genetic Algorithm (RDGA) | ||||
Rank-Density-Based Multi-objective Genetic Algorithm and Benchmark Test Function Study [IEEE Xplore, PDF] | ||||
fitness | diversity | elitism | ext. population | |
automatic accumulated ranking strategy | adaptive cell-based density | implicit | no | |
Algorithm Stub | implemented by: Algorithm::Stubs::GaRDGAStub class |
|||
located in: RDGAStub.h and RDGAStub.cpp files |
||||
Implementation | namespace: Multiobjective::RDGA |
|||
located in: RDGA.h and RDGA.cpp |
You must be logged in to leave a reply.