ShareEmail this to someoneShare on RedditTweet about this on TwitterShare on FacebookShare on Google+Share on LinkedIn

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:

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.