Article

Preference-driven co-evolutionary algorithms show promise for many-objective optimisation

Authors:

Robin C. Purshouse,

Peter J. FlemingAuthors Info & Claims

EMO'11: Proceedings of the 6th international conference on Evolutionary multi-criterion optimization

Pages 136 - 150

Published: 05 April 2011 Publication History

Abstract

The simultaneous optimisation of four or more conflicting objectives is now recognised as a challenge for evolutionary algorithms seeking to obtain full representations of trade-off surfaces for the purposes of a posteriori decision-making. Whilst there is evidence that some approaches can outperform both random search and standard Paretobased methods, best-in-class algorithms have yet to be identified. We consider the concept of co-evolving a population of decision-maker preferences as a basis for determining the fitness of competing candidate solutions. The concept is realised using an existing co-evolutionary approach based on goal vectors. We compare this approach and a variant to three realistic alternatives, within a common optimiser framework. The empirical analysis follows current best practice in the field. As the number of objectives is increased, the preference-driven co-evolutionary approaches tend to outperform the alternatives, according to the hypervolume indicator, and so make a strong claim for further attention in many-objective studies.

References

[1]

Bentley, P.J., Wakefield, J.P.: Finding acceptable solutions in the Pareto-optimal range using multiobjective genetic algorithms. In: Chawdhry, P.K., Roy, R., Pant, R.K. (eds.) Soft Computing in Engineering Design and Manufacturing, pp. 231-240. Springer, Heidelberg (1997).

[2]

Bosman, P.A.N., Thierens, D.: The balance between proximity and diversity in multiobjective evolutionary algorithms. IEEE Transactions on Evolutionary Computation 7(2), 174-188 (2003).

Digital Library

[3]

Brockhoff, D., Saxena, D.K., Deb, K., Zitzler, E.: On handling a large number of objectives a posteriori and during optimization. In: Knowles, J., Corne, D., Deb, K. (eds.) Multiobjective Problem Solving from Nature. Natural Computing Series, pp. 377-403. Springer, Heidelberg (2008).

[4]

Corne, D., Knowles, J.: Techniques for highly multiobjective optimisation: Some nondominated points are better than others. In: Proceedings of GECCO 2007, pp. 773-780 (2007).

Digital Library

[5]

Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6(2), 182-197 (2002).

Digital Library

[6]

Deb, K.: Multi-Objective Optimization Using Evolutionary Algorithms. John Wiley & Sons, Chichester (2001).

Digital Library

[7]

Deb, K., Thiele, L., Laumanns, M., Zitzler, E.: Scalable multi-objective optimization test problems. In: Proceedings of the 2002 Congress on Evolutionary Computation, vol. 1, pp. 825-830 (2002).

[8]

Fonseca, C.M., Fleming, P.J.: Multiobjective genetic algorithms made easy: Selection, sharing and mating restriction. In: Proceedings of the First International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications, pp. 42-52 (1995).

[9]

Fonseca, C.M., Fleming, P.J.: On the performance assessment and comparison of stochastic multiobjective optimizers. In: Ebeling, W., Rechenberg, I., Voigt, H.- M., Schwefel, H.-P. (eds.) PPSN 1996. LNCS, vol. 1141, pp. 584-593. Springer, Heidelberg (1996).

Digital Library

[10]

Fonseca, C.M., Fleming, P.J.: Multiobjective optimization and multiple constraint handling with evolutionary algorithms -- part I: A unified formulation. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans 28(1), 26-37 (1998).

Digital Library

[11]

Fonseca, C.M., Paquete, L., López-Ibáñez, M.: An improved dimension-sweep algorithm for the hypervolume indicator. In: Proceedings of the 2006 Congress on Evolutionary Computation, pp. 1157-1163 (2006).

[12]

Goldberg, D.: The race, the hurdle and the sweet spot. In: Bentley, P. (ed.) Evolutionary Design by Computers, pp. 105-118. Morgan Kaufmann, San Francisco (1999).

[13]

Hollander, M., Wolfe, D.A.: Nonparametric Statistical Methods, 2nd edn. Wiley, New York (1999).

[14]

Huband, S., Hingston, P., Barone, L., While, L.: A review of multiobjective test problems and a scalable test problem toolkit. IEEE Transactions on Evolutionary Computation 10(5), 477-506 (2006).

Digital Library

[15]

Hughes, E.J.: MSOPS-II: A general-purpose many-objective optimiser. In: Proceedings of the 2007 Congress on Evolutionary Computation, pp. 3944-3951 (2007).

[16]

Hughes, E.J.: Fitness assignment methods for many-objective problems. In: Knowles, J., Corne, D., Deb, K. (eds.) Multiobjective Problem Solving from Nature. Natural Computing Series, pp. 307-329. Springer, Heidelberg (2008).

[17]

Ishibuchi, H., Tsukamoto, N., Nojima, Y.: Evolutionary many-objective optimization: A short review. In: Proceedings of the 2008 Congress on Evolutionary Computation, pp. 2419-2426 (2008).

[18]

Kleeman, M.P., Lamont, G.B.: Coevolutionary multi-objective EAs: The next frontier? In: Proceedings of the 2006 Congress on Evolutionary Computation, pp. 1726- 1735 (2006).

[19]

Lohn, J.D., Kraus, W.F., Haith, G.L.: Comparing a coevolutionary genetic algorithm for multiobjective optimization. In: Proceedings of the 2002 Congress on Evolutionary Computation, pp. 1157-1162 (2002).

Digital Library

[20]

Manly, B.F.J.: Randomization and Monte Carlo Methods in Biology. Chapman and Hall, Boca Raton (1991).

[21]

Purshouse, R.C., Fleming, P.J.: An adaptive divide-and-conquer methodology for evolutionary multi-criterion optimisation. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Deb, K., Thiele, L. (eds.) EMO 2003. LNCS, vol. 2632, pp. 133-147. Springer, Heidelberg (2003).

Digital Library

[22]

Purshouse, R.C., Fleming, P.J.: Conflict, harmony, and independence: Relationships in evolutionary multi-criterion optimisation. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Deb, K., Thiele, L. (eds.) EMO 2003. LNCS, vol. 2632, pp. 16-30. Springer, Heidelberg (2003).

Digital Library

[23]

Purshouse, R.C., Fleming, P.J.: On the evolutionary optimization of many conflicting objectives. IEEE Transactions on Evolutionary Computation 11(6), 770-784 (2007).

Digital Library

[24]

Rachmawati, L., Srinivasan, D.: Preference incorporation in multi-objective evolutionary algorithms: A survey. In: Proceedings of the 2006 Congress on Evolutionary Computation, pp. 962-968 (2006).

[25]

Wagner, T., Beume, N., Naujoks, B.: Pareto-, aggregation-, and indicator-based methods in many-objective optimization. In: Obayashi, S., Deb, K., Poloni, C., Hiroyasu, T., Murata, T. (eds.) EMO 2007. LNCS, vol. 4403, pp. 742-756. Springer, Heidelberg (2007).

Digital Library

[26]

Zitzler, E., Deb, K., Thiele, L.: Comparison of multiobjective evolutionary algorithms: Empirical results. Evolutionary Computation 8(2), 173-195 (2000).

Digital Library

[27]

Zitzler, E., Knowles, J., Thiele, L.: Quality assessment of pareto set approximations. In: Branke, J., Deb, K., Miettinen, K., Słowinski, R. (eds.) Multiobjective Optimization. LNCS, vol. 5252, pp. 373-404. Springer, Heidelberg (2008).

Digital Library

[28]

Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., Grunert da Fonseca, V.: Performance assessment of multiobjective optimizers: An analysis and review. IEEE Transactions on Evolutionary Computation 7(2), 117-132 (2003).

Digital Library

Cited By

Li BLi JTang KYao X(2015)Many-Objective Evolutionary AlgorithmsACM Computing Surveys10.1145/279298448:1(1-35)Online publication date: 29-Sep-2015
https://dl.acm.org/doi/10.1145/2792984
Li MYang SLiu X(2015)Bi-goal evolution for many-objective optimization problemsArtificial Intelligence10.1016/j.artint.2015.06.007228:C(45-65)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1016/j.artint.2015.06.007
Reynoso-Meza GSanchis JBlasco XGarcía-Nieto S(2014)Physical programming for preference driven evolutionary multi-objective optimizationApplied Soft Computing10.1016/j.asoc.2014.07.00924:C(341-362)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.1016/j.asoc.2014.07.009
Show More Cited By

Recommendations

A coevolutionary algorithm using multi-operator ensemble for many-objective optimisation problems

MaOPs are typically solved by using evolutionary algorithms (EAs) to search solutions with the help of operators. The strategy of multiple-operator ensemble (MOE) can combine the search capabilities of different operators to ensure better adaptability in ...
Partial Dominance for Many-Objective Optimization
ISMSI '20: Proceedings of the 2020 4th International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence

Many optimisation problems have more than three objectives, referred to as many-objective optimisation problems (MaOPs). As the number of objectives increases, the number of solutions that are non-dominated with regards to one another also increases. ...
Solving many-objective optimisation problems using partial dominance
Abstract
Most optimisation problems have multiple, often conflicting, objectives. Due to the conflicting objectives, a single solution does not exist, and therefore, the goal of a multi-objective optimisation algorithm (MOA) is to find a set of optimal ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

EMO'11: Proceedings of the 6th international conference on Evolutionary multi-criterion optimization

April 2011

618 pages

ISBN:9783642198922

Editors:
Ricardo H. C. Takahashi
Federal University of Minas Gerais, Department of Mathematics, Belo Horizonte, MG, Brazil
,
Kalyanmoy Deb
Indian Institute of Technology Kanpur, Department of Mechanical Engineering, Kanpur, India
,
Elizabeth F. Wanner
Centro Federal de Educação Tecnológica de Minas Gerais, Belo Horizonte, MG, Brazil
,
Salvatore Greco
University of Catania, Faculty of Economics, Catania, Italy

Sponsors

CEMIG: Companhia Energética de Minas Gerais (CEMIG)
FAPEMIG: Fundação de Amparo à Pesquisa do Estado de Minas Gerais (FAPEMIG)
SBC: Sociedade Brasileira de Computação
CONACyT: Consejo Nacional de Ciencia y Tecnología
EMBRAER: Empresa Brasileira de Aeronáutica (EMBRAER)

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 05 April 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li BLi JTang KYao X(2015)Many-Objective Evolutionary AlgorithmsACM Computing Surveys10.1145/279298448:1(1-35)Online publication date: 29-Sep-2015
https://dl.acm.org/doi/10.1145/2792984
Li MYang SLiu X(2015)Bi-goal evolution for many-objective optimization problemsArtificial Intelligence10.1016/j.artint.2015.06.007228:C(45-65)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1016/j.artint.2015.06.007
Reynoso-Meza GSanchis JBlasco XGarcía-Nieto S(2014)Physical programming for preference driven evolutionary multi-objective optimizationApplied Soft Computing10.1016/j.asoc.2014.07.00924:C(341-362)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.1016/j.asoc.2014.07.009
Britto AMostaghim SPozo AAlba E(2013)Iterated multi-swarmProceedings of the 15th annual conference on Genetic and evolutionary computation10.1145/2463372.2463447(583-590)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2463372.2463447
Wang RPurshouse RFleming PAlba E(2013)On finding well-spread pareto optimal solutions by preference-inspired co-evolutionary algorithmProceedings of the 15th annual conference on Genetic and evolutionary computation10.1145/2463372.2463444(695-702)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2463372.2463444
Wang RPurshouse RFleming PMoore J(2012)Local preference-inspired co-evolutionary algorithmsProceedings of the 14th annual conference on Genetic and evolutionary computation10.1145/2330163.2330236(513-520)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330163.2330236

View Options

View options

Figures

Tables

Media

View Table of Conten