Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Knowledge Incorporation in Multi-objective Evolutionary Algorithms

  • Chapter
Multi-Objective Evolutionary Algorithms for Knowledge Discovery from Databases

Part of the book series: Studies in Computational Intelligence ((SCI,volume 98))

This chapter presents a survey of techniques used to incorporate knowledge into evolutionary algorithms, with a particular emphasis on multi-objective optimization. We focus on two main groups of techniques: those that incorporate knowledge into the fitness evaluation, and those that incorporate knowledge in the initialization process and the operators of an evolutionary algorithm. Several techniques representative of each of these groups are briefly discussed, together with some examples found in the specialized literature. In the last part of the chapter, we provide some research ideas that are worth exploring in the future by researchers interested in this topic.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Coello Coello C A, Van Veldhuizen D A, Lamont G B (2002) Evolutionary algorithms for solving multi-objective problems. Kluwer Academic Publishers, New York

    MATH  Google Scholar 

  2. Deb K (2001) Multi-objective optimization using evolutionary algorithms. John Wiley & Sons, Chichester, UK

    MATH  Google Scholar 

  3. Vapnik V (1998) Statistical learning theory. Wiley Information Technology Encyclopedia and Acronyms. Springer, Berlin Heidelberg, New York

    Google Scholar 

  4. Riesbeck C K, Schank R C (1989) Inside case-based reasoning. Lawrence Erlbaum Associates, New Jersey

    Google Scholar 

  5. Chen J H, Goldberg D E, Ho S-Y, Sastry K (2002) Fitness inheritance in multi-objective optimization. In: Langdon W B and Cantú-Paz E, Mathias K, Roy R, Davis D, Poli R, Balakrishnan K, Honavar V, Rudolph G, Wegener J, Bull L, Potter M A, Schultz A C, Miller J F, Burke E, Jonoska N (eds) Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’2002). Morgan Kaufmann Publishers, San Francisco, California, 319–326

    Google Scholar 

  6. Deb K, Thiele L, Laumanns M, Zitzler E (2005) Scalable test problems for evolutionary multiobjective optimization. In: Abraham A, Jain L, Goldberg R (eds) Evolutionary Multiobjective Optimization. Theoretical Advances and Applications. Springer, USA, 105–145

    Chapter  Google Scholar 

  7. Reynolds R G (1994) An introduction to cultural algorithms. In: Sebald A V, Fogel L J (eds) Proceedings of the Third Annual Conference on Evolutionary Programming. World Scientific, 131–139

    Google Scholar 

  8. Reynolds R G, Michalewicz Z, Cavaretta M (1995) Proceedings of the Fourth Annual Conference on Evolutionary Programming. In: McDonnell J R, Reynolds R G, Fogel, D B (eds) Using Cultural Algorithms for Constraint Handling in GENOCOP. MIT Press, 298–305

    Google Scholar 

  9. Ong Y S, Nair P B, Keane A J, Wong K W (2004) Surrogate-assisted evolutionary optimization frameworks for high-fidelity engineering design problems. In: Jin Y (eds) Knowledge Incorporation in Evolutionary Computation, Springer, Studies in Fuzziness and Soft Computing, 307–332

    Google Scholar 

  10. Williams C K I, Rasmussen C E (1996) Gaussian processes for regression. In: Touretzky D S, Mozer M C, Hasselmo M E (eds) Advances in Neural Information Processing Systems 8, MIT Press

    Google Scholar 

  11. Chafekar D, Shi L, Rasheed K, Xuan J (2005) Multi-objective GA optimization using reduced models. IEEE Transactions on Systems, Man, and Cybernetics: Part-C 35 (2):261–265

    Article  Google Scholar 

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

    Article  Google Scholar 

  13. Jensen M T (2003) Reducing the run-time complexity of multiobjective EAs: the NSGA-II and other algorithms. IEEE Transactions on Evolutionary Computation 7(5):503–515

    Article  Google Scholar 

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

    Article  Google Scholar 

  15. Jin Y (2005) A comprehensive survey of fitness approximation in evolutionary computation. Soft Computing 9(1):3-12

    Article  Google Scholar 

  16. Knowles J (2006) ParEGO: A hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems. IEEE Transactions on Evolutionary Computation 10(1): 50–66

    Article  Google Scholar 

  17. Salami M, Hendtlass T (2003) A fast evaluation strategy for evolutionary algorithms. Applied Soft Computing 2:156–173

    Article  Google Scholar 

  18. Islas Pérez E and Coello Coello C A, Hernández Aguirre A (2005) Extraction and reuse of design patterns from genetic algorithms using case-based reasoning. Soft Computing–A Fusion of Foundations, Methodologies and Applications 9(1):44–53

    Google Scholar 

  19. Louis S J, McGraw G, Wyckoff R (1993) Case-based reasoning assisted explanation of genetic algorithm results. Journal of Experimental and Theoretical Artificial Intelligence 5: 21–37

    Article  Google Scholar 

  20. Chung C-J, Reynolds R G (1998) CAEP: An evolution-based tool for real-valued function optimization using cultural algorithms. Journal on Artificial Intelligence Tools 7(3): 239–292

    Article  Google Scholar 

  21. Kung H T, Luccio F, Preparata F P (1975) On finding the maxima of a set of vectors. Journal of the Association for Computing Machinery 22(4): 469–476

    MATH  MathSciNet  Google Scholar 

  22. Deb K, Mohan M, Mishra S (2005) Evaluating the ε-domination based multi-objective evolutionary algorithm for a quick computation of pareto-optimal solutions. Evolutionary Computation 13(4):501–525

    Article  Google Scholar 

  23. Emmerich M T M, Giannakoglou K C, Naujoks B (2006) Single and multiobjective evolutionary optimization assisted by Gaussian random field metamodels. IEEE Transactions on Evolutionary Computation 10(4):421-439

    Article  Google Scholar 

  24. Gibbs M N, MacKay D J C (1996) Efficient implementation of Gaussian processes for interpolation. http://www.inference.phy.cam.ac.uk/mackay/ abstracts/gpros.html

  25. Rasheed K, Ni X, Vattam S (2003) Comparison of methods for developing dynamic reduced models for design optimization. Soft Computing Journal (in press)

    Google Scholar 

  26. Hong Y-S, Lee H, Tahk M-J (2003) Acceleration of the convergence speed of evolutionary algorithms using multi-layer neural networks. Engineering Optimization 35(1): 91–102

    Article  MathSciNet  Google Scholar 

  27. Hüscken M, Jin Y, Sendhoff B (2005) Structure optimization of neural networks for aerodynamic optimization. Soft Computing Journal 9(1):21–28

    Article  Google Scholar 

  28. Pierret S (1999) Turbomachinery blade design using a navier-stokes solver and artificial neural network. ASME Journal of Turbomachinery 121(3): 326–332

    Article  Google Scholar 

  29. Bueche D, Schraudolph N N, Koumoutsakos P (2004) Accelerating evolutionary algorithms with Gaussian process fitness function models. IEEE Trans. on Systems, Man, and Cybernetics: Part C

    Google Scholar 

  30. Hardy R L (1971) Multiquadric equations of topography and other irregular surfaces. Journal of Geophysics Research 76:1905–1915

    Article  Google Scholar 

  31. Bramanti A, Barba P Di, Farina M, Savini A (2001) Combining response surfaces and evolutionary strategies for multiobjective Pareto-optimization in electromagnetics. International Journal of Applied Electromagnetics and Mechanics 15(1):231–236

    Google Scholar 

  32. Ong Y S, Nair P B, Keane A J (2003) Evolutionary optimization of computationally expensive problems via surrogate modeling. AIAA Journal 41(4):687–696

    Article  Google Scholar 

  33. Becerra R L, Coello Coello C A (2006) Cultured differential evolution for constrained optimization. Computer Methods in Applied Mechanics and Engineering 195 (33–36):4303–4322

    MATH  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  35. Farina M (2002) A neural network based generalized response surface multiobjective evolutionary algorithms. Congress on Evolutionary Computation, IEEE Press, 956–961

    Google Scholar 

  36. Nain P K S, Deb K (2003) Computationally effective search and optimization procedure using coarse to fine approximation. Congress on Evolutionary Computation, IEEE Press, 2081–2088

    Google Scholar 

  37. Sastry K, Goldberg D E, Pelikan M (2001) Don’t evaluate, inherit. Proceedings of Genetic and Evolutionary Computation Conference, Morgan Kaufmann Publishers, 551–558

    Google Scholar 

  38. Smith R E, Dike B A, Stegmann S A (1995) Fitness inheritance in genetic algorithms. SAC ’95: Proceedings of the 1995 ACM symposium on Applied Computing, Nashville, Tennessee, United States, ACM Press, New York, NY, USA, 345–350

    Chapter  Google Scholar 

  39. Bui L T, Abbass H, Essam D (2005) Fitness inheritance for noisy evolutionary multi-objective optimization. Proceedings of Genetic and Evolutionary Computation Conference (GECCO-2005), ACM, 779–785

    Google Scholar 

  40. Reyes-Sierra M, Coello Coello C A (2006) Dynamic fitness inheritance proportion for multi-objective particle swarm optimization. Genetic and Evolutionary Computation Conference (GECCO’2006), ACM Press. ISBN 1-59593-186-4, Seattle, Washington, USA, 89–90

    Google Scholar 

  41. Louis S J, Johnson J (1997) Solving similar problems using genetic algorithms and case-based memory. Proceedings of the Seventh International Conference on Genetic Algorithms (ICGA97), Morgan Kaufmann, San Francisco, CA.

    Google Scholar 

  42. Louis S J, Zhang Y (1999) A sequential similarity metric for case injected genetic algorithms applied to TSPs. Proceedings of the Genetic and Evolutionary Computation Conference, Morgan Kaufman, Orlando, Florida, USA, 377–384

    Google Scholar 

  43. Louis S J (2002) Genetic learning for combinational logic design. Proceedings of the GECCO-2002 Workshop on Approximation and Learning in Evolutionary Computation, New York, NY, 21–26

    Google Scholar 

  44. Miles C, Louis S J (2005) Case-injection improves response time for a real-time strategy game. Proceedings of the IEEE Symposium on Computational Intelligence in Games, IEEE Press, New York, NY

    Google Scholar 

  45. Drewes R, Louis S J, Miles C, McDonnell J, Gizzi N (2003) Use of case injection to bias genetic algorithm solution of similar problems. Proceedings of the International Congress on Evolutionary Computation, IEEE Press, Canberra, Australia

    Google Scholar 

  46. Jin X, Reynolds R G (1999) Using knowledge-based evolutionary computation to solve nonlinear constraint optimization problems: a cultural algorithm approach. Congress on Evolutionary Computation, IEEE Service Center, 1672–1678

    Google Scholar 

  47. Coello Coello C A, Landa Becerra R (2002) Adding knowledge and efficient data structures to evolutionary programming: A cultural algorithm for constrained optimization. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’2002), Morgan Kaufmann Publishers, 201–209

    Google Scholar 

  48. Peng B, Reynolds R G, Brewster J (2003) Cultural swarms. Proceedings of the Congress on Evolutionary Computation 2003 (CEC’2003), IEEE Service Center

    Google Scholar 

  49. Landa Becerra R, Coello Coello C A (2005) Optimization with constraints using a cultured differential evolution approach. Genetic and Evolutionary Computation Conference (GECCO’2005), ACM Press,Washington, DC, USA, : 27–34

    Google Scholar 

  50. Landa Becerra R, Coello Coello C A (2006) Solving hard multiobjective optimization problems using e-Constraint with cultured differential evolution. Parallel Problem Solving from Nature - PPSN VIII, LNCS, Springer-Verlag

    Google Scholar 

  51. Coello Coello C A, Landa Becerra R (2003) Evolutionary multiobjective optimization using a cultural algorithm. IEEE Swarm Intelligence Symposium Proceedings, IEEE Service Center, 6–13

    Google Scholar 

  52. Huband S, Barone L, While L, Hingston P (2005) A scalable multi-objective test problem toolkit. Evolutionary Multi-Criterion Optimization. Third International Conference, EMO 2005, Springer. Lecture Notes in Computer Science, 3410:280–295

    Google Scholar 

  53. Sacks J, Welch W, Mitchell T, Wynn H (1989) Design and analysis of computer experiments (with discussion). Statistical Science 4:409–435

    Article  MATH  MathSciNet  Google Scholar 

  54. Emmerich M, Giotis A, Özdenir M, Bäck T, Giannakoglou K (2002) Metamodel-assisted evolution strategies. Parallel Problem Solving from Nature, Lecture Notes in Computer Science, Springer, 371–380

    Google Scholar 

  55. Ratle A (1998) Accelerating the convergence of evolutionary algorithms by fitness landscape approximation. Parallel Problem Solving from Nature V, 87–96

    Google Scholar 

  56. Ulmer H, Streichert F, Zell A (2003) Evolution startegies assisted by Gaussian processes with improved pre-selection criterion. Proceedings of IEEE Congress on Evolutionary Computation, 692–699

    Google Scholar 

  57. Wilson B, Cappelleri D J, Simpson T W, Frecker M I (2000) Efficient pareto frontier exploration using surrogate approximations. Symposium on Multidisciplinary Analysis and Optimization, AIAA, Long Beach, CA

    Google Scholar 

  58. Karakasis M K, Giannakoglou K C (2005) Metamodel-assisted multi-objective evolutionary optimization. EUROGEN 2005. Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems, Munich, Germany

    Google Scholar 

  59. Voutchkov I, Keane A J (2006) Multiobjective optimization using surrogates. Adaptive Computing in Design and Manufacture Proceedings of the Seventh International Conference, the Institute for People-centered Computation (IP-CC), Bristol, UK, 167–175

    Google Scholar 

  60. Deb K, Mohan M, Mishra S (2003) Towards a quick computation of well-spread pareto-optimal solutions. Evolutionary Multi-Criterion Optimization. Second International Conference, EMO 2003, Springer. Lecture Notes in Computer Science. 2632:222–236

    Article  Google Scholar 

  61. X. Zheng and B. A. Julstrom and W. Cheng (1997) Design of vector quantization codebooks using an genetic algorithm. Proceedings of IEEE International Conference on Evolutionary Computation (ICEC 97), 525–530

    Google Scholar 

  62. Reyes Sierra M, Coello Coello C A (2005) A study of fitness inheritance and approximation techniques for multi-objective particle swarm optimization. IEEE Congress on Evolutionary Computation (CEC’2005), IEEE Service Center, Edinburgh, Scotland

    Google Scholar 

  63. Ulmer H, Streicher F, Zell A (2003) Model-assisted steady-state evolution strategies. Proceedings of Genetic and Evolutionary Computation Conference, LNCS 2723:610–621

    Google Scholar 

  64. Won K S, Ray T (2004) Performance of kriging and cokriging based surrogate models within the unified framework for surrogate assisted optimization. IEEE Congress on Evolutionary Computation, 1577–1585

    Google Scholar 

  65. Abboud K, Schoenauer M (2002) Surrogate deterministic mutation. Proceedings of Artificial Evolution, 103–115

    Google Scholar 

  66. Bhattacharya M, Lu G (2003) A dynamic approximate fitness based hybrid EA for optimization problems. Proceedings of IEEE Congress on Evolutionary Computation, 1879–1886

    Google Scholar 

  67. Ducheyne Els I, De Baets B, De Wulf R (2003) Is fitness inheritance useful for real-world applications? Evolutionary Multi-Criterion Optimization. Second International Conference, EMO 2003, Springer. Lecture Notes in Computer Science. 2632:31–42

    Article  Google Scholar 

  68. Reynolds R G, Chung C-J (1997) A cultural algorithm framework to evolve multi-agent cooperation with evolutionary programming. Proceedings of the 6th International Conference on Evolutionary Programming VI, Springer-Verlag, 323–334

    Google Scholar 

  69. Saleem S, Reynolds R (2000) Cultural algorithms in dynamic environments. Proceedings of the Congress on Evolutionary Computation, 1513–1520

    Google Scholar 

  70. Reynolds R G, Chung C-J (1997) Knowledge-based self-adaptation in evolutionary programming using cultural algorithms. Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC 97), 71–76

    Google Scholar 

  71. Reyes Sierra María M (2006) Use of coevolution and fitness inheritance for multiobjective particle swarm optimization. Computer Science Section, Department of Electrical Engineering, CINVESTAV-IPN, Mexico

    Google Scholar 

  72. Giunta A A, Watson L (1998) A comparison of approximation modeling techniques: Polynomial versus interpolating models. AIAA, 47–58

    Google Scholar 

  73. Jin R, Chen W, Simpsonand T W (2000) Comparative studies of metamodeling techniques under miltiple modeling criteria. AIAA, 2000–4801

    Google Scholar 

  74. Goel T, Vaidyanathan R, Haftka R, Shyy W, Queipo N, Tucker K (2004) Response surface approximation of Pareto optimal front in multiobjective optimization. AIAA, 2004–4501

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Computación, CINVESTAV-IPN, 07360, Mexico

    Ricardo Landa-Becerra, Luis V. Santana-Quintero & Carlos A. Coello Coello

Authors
  1. Ricardo Landa-Becerra
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Luis V. Santana-Quintero
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Carlos A. Coello Coello
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Indian Statistical Institute, 203 B. T. Road, 700 108, Kolkata, India

    Ashish Ghosh

  2. F. M. University, 756 019, Balasore, India

    Satchidananda Dehuri

  3. Jadavpur University, 700 032, Kolkata, India

    Susmita Ghosh

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Landa-Becerra, R., Santana-Quintero, L.V., Coello, C.A.C. (2008). Knowledge Incorporation in Multi-objective Evolutionary Algorithms. In: Ghosh, A., Dehuri, S., Ghosh, S. (eds) Multi-Objective Evolutionary Algorithms for Knowledge Discovery from Databases. Studies in Computational Intelligence, vol 98. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77467-9_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-77467-9_2

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-77466-2

  • Online ISBN: 978-3-540-77467-9

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation