5 Multi-Objective Evolutionary Algorithms


NSGA-II

NSGA-II features a fast non-dominated sorting approach, implicit elitist selection method based on Pareto-dominance rank and a secondary selection method based on crowding distance, which significantly improve its performance on difficult multi-objective problems. Moreover, it provides a constraint-handling technique to deal with constrained problems efficiently and supports both binary and real coding representations. More details about NSGA-II readers are referred to the following paper:

  • Deb, K., Pratap, A., Agarwal, S., Meyarivan, T., 2002. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE T. Evolut. Comput. 6(2), 182-197.

The source code of NSGA-II was written in C and can be downloaded from the following website: http://www.iitk.ac.in/kangal/codes.shtml.


AMALGAM

AMALGAM is a hybrid optimisation framework which employs four sub-algorithms simultaneously within its structure, including NSGA-II, adaptive metropolis search, particle swarm optimisation and differential evolution. It is designed to overcome the drawbacks of using an individual algorithm. The strategies of global information sharing and genetically adaptive offspring creation are implemented in the process of population evolution. Each sub-algorithm is allowed to produce a specific number of offspring based on the survival history of its solutions in the previous generation. The pool of current best solutions is shared among sub-algorithms for reproduction.

More details about AMALGAM readers are referred to the following paper:

  • Vrugt, J. A., Robinson, B. A., 2007. Improved Evolutionary Optimization from Genetically Adaptive Multimethod Search. Proc. Natl. Acad. Sci. U.S.A. 104(3), 708-711.

The source code of AMALGAM was written in Matlab and can be obtained by request to the following website: http://faculty.sites.uci.edu/jasper/sample/.


ε-MOEA

Unlike the NSGA-II, ε-MOEA is a steady-state MOEA in which only one solution is generated per iteration. It incorporates the concept of ε-dominance, being able to preserve a good representation of Pareto front in terms of convergence and diversity. At the beginning, a population is initialised randomly and the non-dominated solutions are retained in an archive. Next, a solution is created via crossover and mutation using two parents each of which selected from the population and the archive. Then, this solution is checked for acceptance or rejection by the population and the archive, using Pareto dominance and ε-dominance, respectively. The abovementioned procedure is repeated until a stopping criterion is met.

More details about ε-MOEA readers are referred to the following paper:

  • Deb, K., Mohan, M., Mishra, S., 2005. Evaluating the epsilon-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions. Evolut. Comput. 13(4), 501-525.

The source code of ε-MOEA was written in C and can be downloaded from the following website: http://www.iitk.ac.in/kangal/codes.shtml.


Borg

Based on the steady-state structure of ε-MOEA, Borg incorporates more advanced features into a unified framework, including ε-dominance, ε-progress (a measure of convergence speed), randomised restart, and auto-adaptive multi-operator recombination (similar to AMALGAM). The advantages of Borg are threefold: (1) usage of ε-box dominance archive contributes to maintaining the convergence and diversity concurrently throughout the search; (2) the combination of time continuation, adaptive population sizing, and two types of randomised restart (i.e. ε-progress triggered restart and population-to-archive ratio triggered restart) boosts the algorithm towards global optima; (3) simultaneous employment of multiple recombination operators enhances performance on a wide assortment of problem domains. In addition, the adoption of the steady-state, elitist model of ε-MOEA make it easily extendable for use on parallel architectures.

More details about Borg readers are referred to the following paper:

  • Hadka, D., Reed, P., 2013. Borg: An Auto-Adaptive Many-Objective Evolutionary Computing Framework. Evolut. Comput. 21(2), 231-259.

The source code of Borg was written in C and can be obtained by request to the following website: http://borgmoea.org/.


ε-NSGAII

The ε-NSGA-II method goes beyond the common implementation of MOEA by building on NSGA-II and three key components, namely ε-dominance archiving, adaptive population sizing with archive injection, and automatic termination. The ε-NSGA-II differs from the NSGA-II primarily in two aspects: (1) while the population evolves in the same manner as NSGA-II, an offline archive is frequently updated by selecting the ε-non-dominated solutions from the elitist population at current generation; (2) the optimisation is implemented in consecutive epochs, each of which is terminated automatically according to the user-specified improvement criteria. The next epoch is populated by injecting the members in the archive and generating new random solutions. The ε-dominance archiving maintains the convergence and diversity of the archive concurrently. It also allows users to specify the precision of each objective and thus is more flexible in practice. Adaptive population sizing contributes to balancing the exploration and exploitation throughout the search, which is achieved by increasing or decreasing the capacity of the population based on the number of members in the archive. Additionally, several connected runs, known as time continuation, enhance the possibility to explore other regions of search space.

More details about ε-NSGA-II readers are referred to the following paper.

  • Kollat, J. B., Reed, P. M., 2006. Comparing state-of-the-art evolutionary multi-objective algorithms for long-term groundwater monitoring design. Adv. Water Resour. 29(6), 792-807.

The source code of ε-NSGA-II was written in C and can be obtained by sending the request to the authors.

Google+