Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Solution of multiobjective optimization problems: coevolutionary algorithm based on evolutionary game theory

  • Original Article
  • Published:
Artificial Life and Robotics Aims and scope Submit manuscript

Abstract

When attempting to solve multiobjective optimization problems (MOPs) using evolutionary algorithms, the Pareto genetic algorithm (GA) has now become a standard of sorts. After its introduction, this approach was further developed and led to many applications. All of these approaches are based on Pareto ranking and use the fitness sharing function to keep diversity. On the other hand, the scheme for solving MOPs presented by Nash introduced the notion of Nash equilibrium and aimed at solving MOPs that originated from evolutionary game theory and economics. Since the concept of Nash Equilibrium was introduced, game theorists have attempted to formalize aspects of the evolutionary equilibrium. Nash genetic algorithm (Nash GA) is the idea to bring together genetic algorithms and Nash strategy. The aim of this algorithm is to find the Nash equilibrium through the genetic process. Another central achievement of evolutionary game theory is the introduction of a method by which agents can play optimal strategies in the absence of rationality. Through the process of Darwinian selection, a population of agents can evolve to an evolutionary stable strategy (ESS). In this article, we find the ESS as a solution of MOPs using a coevolutionary algorithm based on evolutionary game theory. By applying newly designed coevolutionary algorithms to several MOPs, we can confirm that evolutionary game theory can be embodied by the coevolutionary algorithm and this coevolutionary algorithm can find optimal equilibrium points as solutions for an MOP. We also show the optimization performance of the co-evolutionary algorithm based on evolutionary game theory by applying this model to several MOPs and comparing the solutions with those of previous evolutionary optimization models.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Zitzler E, Deb K, Thiele L (1999) Comparison of multiobjective evolutionary algorithms: empirical results. Technical Report 70, Computer Engineering Networks Laboratory (TIK), Swiss Federal Inst Technol (ETH) Zurich, Switzerland, Proceedings of the 1999 Genetic and Evolutionary Computation Conference, Workshop Program, Orlando, Florida, pp 121–122

    Google Scholar 

  2. Fonseca CM, Fleming PJ (1998) Multiobjective optimization and multiple constraint handling with evolutionary algorithms-part I: a unified formulation. IEEE Trans Syst Man Cy 28:26–37

    Article  Google Scholar 

  3. Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms - a comparative case study. In: Eiben AE, Beack T, Schoenauer M, et al. (eds) Fifth International Conference on Parallel Problem Solving from Nature (PPSN-V), Springer, Berlin Heidelberg New York, pp 292–301

    Google Scholar 

  4. Cohon JL (1978) Multiobjective programming and planning. Academic, New York

    MATH  Google Scholar 

  5. Schaffer JD (1984) Some experiments in machine learning using vector evalutated genetic algorithms. Ph.D. dissertation, Vanderbilt University

  6. Schaffer JD (1985) Multiple objective optimization with vector evaluated genetic algorithms. Proceedings of the International Conference on Genetic Algorithms and their Applications, pp 93–100

  7. Horn J, Nafpliotis N, Goldberg DE (1994) A niched pareto genetic algorithm for multiobjective optimization. IEEE World Congress on Computational Intelligence (ICEC ’94) 1:82–87

    Article  Google Scholar 

  8. Fourman MP (1985) Compaction of symbolic layout using genetic algorithms. In: Grefenstette JJ (ed) Genetic Algorithms and Their Applications: Proceedings of the 1st International Conference on Genetic Algorithms. Lawrence Erlbaum, Princeton, pp 141–153

    Google Scholar 

  9. Fonseca CM, Fleming PJ (1998) Multiobjective optimization and multiple constraint handling with evolutionry algorithms-part II: application example. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans 28:38–47

    Article  Google Scholar 

  10. Kursawe F (1991) A variant of evolution strategies for vector optimization. In: Schwefel H-P, Maenner R (eds) Parallel Problem Solving from Nature, 1st Workshop Proceedings, vol 496 of Lecture Notes in Computer Science. Springer, Berlin Heidelberg New York, pp 193–197

    Chapter  Google Scholar 

  11. Hajela P, Lin C-Y (1992) Genetic search strategies in multicriterion optimal design. Struct Optim 4:99–107

    Article  Google Scholar 

  12. Fonseca CM, Fleming PJ (1993) Genetic algorithms for multi-objective optimization: formulation, discussion and generalization. Proceedings of the Fifth International Conference, Kaufmann, San Mateo, CA, pp 416–423

    Google Scholar 

  13. Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading, MA

    MATH  Google Scholar 

  14. Fonseca CM, Fleming PJ (1995) An overview of evolutionary algorithms in multiobjective optimization. Evolution Comput 3:1–16

    Article  Google Scholar 

  15. Horn J, Nafpliotis N (1993) Multiobjective optimization using the niched Pareto genetic algorithm. IlliCAL Report 93005, University of Illinois at Urbana-Champaign, Urbana, IL

    Google Scholar 

  16. Goldberg DE, Richardson JJ (1987) Genetic algorithms with sharing for multi-modal function optimization. Genetic Algorithms and Their Application: Proceedings of the Second ICGA, Lawrence Erlbaum, Hillsdal, pp 41–49

    Google Scholar 

  17. Srinivas N, Deb K (1995) Multiobjective optimization using non-dominated sorting in genetic algorithms. Evolution Comput 2:221–248

    Article  Google Scholar 

  18. Poloni C (1995) Hybrid GA for multi objective aerodynamic shape optimization. In: Galan M, Winter G, Periaux J, et al. (eds) Genetic algorithms in engineering and computer science. Wiley, Las Palmas, Spain, pp 397–415

    Google Scholar 

  19. Makinen R, Neittaanmaki P, Periaux J, et al. (1996) Parallel genetic solution for multiobjective MDO. Parallel CFD 96, Elsevier, Capri

    Google Scholar 

  20. Bristeau M-O, Glowinski R, Mantel B, et al. (1999) Genetic algorithms for electromagnetic backscattering: multiobjective optimization. In: Rahmat-Samii Y, Michielssen E (eds) System design using evolutionary optimization: genetic algorithms. Wiley, New York

    Google Scholar 

  21. Sefrioui M, Periaux J (2000) Nash genetic algorithms: examples and applications. Proceedings of the 2000 Congress on Evolutionary Computation CEC00, IEEE, pp 509–516

  22. Zitzler E (1999) Evolutionary algorithms for multiobjective optimization: methods and applications. Dissertation for the degree of Doctor of Technical Sciences, Swiss Federal Institute of Technology, Zurich

    Google Scholar 

  23. Zitzler E (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach

  24. Deb K (1998) Multiobjective genetic algorithms: problem difficulties and construction of test functions. Technical Report No. CI-49/ 98, Department of Computer Science/XI, University of Dortmund, Germany

    Google Scholar 

  25. Nash JF (1951) Noncooperative games. Ann Math 54:89

    Article  MathSciNet  Google Scholar 

  26. Sefrioui M, Periaux J, Ganascia J-G (1996) Fast convergence thanks to diversity. In: Fogel LJ, Angeline PJ, Baeck T (eds) Proceedings of the Fifth Annual Conference on Evolutionary Programming, San Diego, CA. IEEE Computer Society

    Google Scholar 

  27. Maynard-Smith J (1982) Evolution and the theory of games. Cambridge University Press, Cambridge

    Google Scholar 

  28. Ficici SG, Pollack JB (2001) Game theory and the simple coevolutionary algorithm: some preliminary results on fitness sharing. GECCO 2001 Workshop on Coevolution: Turning Adaptative Algorithms upon Themselves, pp 2–7

  29. Lessard S (1990) Evolutionary stability: one concept, several meanings. Theor Popul Biol 37:159–170

    Article  MATH  MathSciNet  Google Scholar 

  30. Rowe GW, Harvey IF, Hubbard SF (1985) The essential properties of evolutionary stability. J Theor Biol 115:269–285

    Article  MathSciNet  Google Scholar 

  31. Strogatz SH (1994) Nonlinear dynamics and chaos. Addison-Wesley, Reading, MAs

    Google Scholar 

  32. Zitzler E, Deb K, Thiele L (1999) Comparison of multiobjective evolutionary algorithms: empirical results. Proceedings of the 1999 Genetic and Evolutionary Computation Conference, Workshop Program, Orlando, Florida, pp 121–122

    Google Scholar 

  33. Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Trans Evolution Comput 3:257–271

    Article  Google Scholar 

  34. Deb K (1999) Multiobjective genetic algorithms: problem difficulties and construction of test problems. Evolution Comput 7:205–230

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Electrical and Electronic Engineering, Chung-Ang University, 221 Huksuk-Dong, 156-756, Dongjak-Ku, Seoul, Korea

    Kwee-Bo Sim & Ji-Yoon Kim

Authors
  1. Kwee-Bo Sim
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ji-Yoon Kim
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kwee-Bo Sim.

Additional information

This work was presented, in part, at the 8th International Symposium on Artificial Life and Robotics, Oita, Japan, January 24#x2013;26, 2003.

About this article

Cite this article

Sim, KB., Kim, JY. Solution of multiobjective optimization problems: coevolutionary algorithm based on evolutionary game theory. Artif Life Robotics 8, 174–185 (2004). https://doi.org/10.1007/s10015-004-0308-6

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10015-004-0308-6

Key words

Search

Navigation