Art. 04 – Vol. 25 – Nr. 2 – 2015

Multi-objective Optimization Problems Solving based on Evolutionary Algorithm

Iulia Cristina Rădulescu
iulia.radulescu1702@yahoo.com

POLITEHNICA University of Bucharest

Abstract: Most optimization problems that arise in practice have multiple objectives because they suppose to optimize simultaneously several objective functions. In this article we analyze several approaches for solving multi-objective optimization problems, focusing on the approaches based on evolutionary algorithms. We present a classification of optimization techniques in enumerative, deterministic and stochastic. From the stochastic optimization techniques are detailed Evolutionary Algorithms – EA. These algorithms are successfully used for solving multi-objective optimization. We present the basic concepts used in evolutionary algorithms and an overview of several evolutionary algorithms for solving multi-objective optimization problems. Finally, we solve four multi-objective optimization problems using a well-known evolutionary algorithm called the Non-Dominated Sorting Genetic Algorithms – NSGA-II. The Matlab program, that implements the algorithm NSGA-II, computes the Pareto frontier of the four multi-objective optimization problems considered.

Keywords: Multi-objective optimization, Evolutionary Algorithms, Non-Dominated Sorting Genetic Algorithms, Pareto frontier.

REFERENCES

  1. BÄCK, T.: Evolutionary Algorithms in Theory and Practice. Oxford University Press, New York, 1996.
  2. COELLO, C.; LAMONT, G.; VELDHUIZEN, D.: Evolutionary Algorithms for solving Multi-Objective Problems. Springer, 2007.
  3. DAY, O.; KLEEMAN, M. P.; LAMONT, G.B.: Multi-Objective fast messy Genetic Algorithm Solving Deception Problems. In 2004 Congress on Evolutionary Computation (CEC’2004), volume 2, Portland, Oregon, USA, IEEE Service Center, June 2004, pp. 1502-1509.
  4. DAY, R. O.; LAMONT, G. B.: Multiobjective Quadratic Assignment Problem Solved by an Explicit Building Block Search Algorithm – MOMGA-IIa. In G.R. Raidl and J. Gottlieb, editors, Evolutionary Computation in Combinatorial Optimization. 5th European Conference, EvoCOP 2005, , Lausanne, Switzerland,. Springer, Lecture Notes in Computer Science Vol. 3448, March/April 2005, pp 91-100.
  5. DEB, K.; AGRAVAL, S.; PRATAB, A.; MEYARIVAN, T.: A Fast Elitist Non-Dominated Sorting Genetics Algorithm for Multi-Objective Optimization: NSGA-II. In M. Schoenauer, K.Deb, G. Rudolph, X. Yao, E. Lutton, J. J. Merelo, and H.-P. Schwefel, editors, Proceedings of the Parallel Problem Solving from Nature VI Conference, Lecture Notes in Computer Science No. 1917, Springer, Paris, France, 2000, pp. 849-858.
  6. DEB, K.; PRATAP, A.; AGARWAL, S.; MEYARIVAN, T.: A fast and Elitist multi-objective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182-197, April 2002.
  7. ERICKSON, M.; MAYER, A.; HORN, J.: The Niched Pareto Genetic Algorithm 2 Applied to the Design of Groundwater Remediation Systems. In E. Zitzler, K. Deb, L. Thiele, C. A. Coello Coello, and D. Corne, editors, First International Conference on Evolutionary Multi-Criterion Optimization, Springer-Verlag. Lecture Notes in Computer Science No. 1993, 2001, pp. 681-695.
  8. FONSECA, C. M.; FLEMING, P. J.: Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization. In S. Forrest, editor, Proceedings of the Fifth International Conference on Genetic Algorithms, San Mateo, California. University of Illinois at Urbana-Champaign, Morgan Kaufman Publishers, 1993, pp. 416-423.
  9. FOURMAN, M. P.: Compaction of Symbolic Layout using Genetic Algorithms. In J. J. Grefenstette, editor, Genetic Algorithms and their applications: Proceedings of the First International Conference on Genetic Algorithms,. Lawrence Erlbaum, Hillsdale, New Jersey, 1985, pp. 141-153.
  10. HAJELA, P.; LIN, C. Y.: Genetic search strategies in multicriterion optimal design. Structural Optimization, 4:99-107, 1992.
  11. HORN, J.; NAFPLIOTIS, N.: Multiobjective Optimization using the Niched Pareto Genetic Algorithm. Technical Report IlliGAI Report 93005, University of Illinois at Urbana-Champaign, Urbana, Illinois, USA, 1993.
  12. KITA, H.; YABUMOTO, Y.; MORI, N.; NISHIKAWA, Y.: Multi-Objective Optimization by Means of the Thermodynamical Genetic Algorithm. In H.-M. Voight, W. Ebeling, I. Rechenberg, and H.-P. Schwefel, editors, Parallel problem Solving from Nature – PPSN IV. Springer-Verlag. Lecture Notes in Computer Science No. 1141, berlin, Germany, September, 1996, pp. 504-512.

View full article

  1. KNOWLES, J. D.; CORNE, D. W.: The Pareto Archived Evolution Strategy: A New Baseline Algorithm for Multiobjective Optimisation. In 1999 Congress on Evolutionary Computation, Washington, D.C., IEEE Service Center, July 1999, pp. 98-105
  2. KNOWLES, J. D.; CORNE. D. W.: Approximating the Nondominated Front Using the Pareto Archieved Evolution Strategy. Evolutionary Computation, 8(2):149-172, 2000.
  3. KURSAWE, F. A.: Variant of Evolution Strategies for Vector Optimization. In H.-P.Schewefel and R. Manner, editors, Parallel Problem Solving from Nature. 1st Workshop, PPSN I, ,.. Lecture Notes in Computer Science No.496, Springer-Verlag, Dortmund, Germany, October 1991, pp. 193-197.
  4. LAUMANNS, M.; OCENASEK, J.: Bayesian Optimization Algorithms for Multi-objective Optimization. In J.J. Merelo Guervos, P. Adamidis, H.-G. Beyer, J.-L. F.V. nas, and H.-P. Schwefel, editors, Parallel Problem Solving from Nature – PPSN VII,. Lecture Notes in Computer Science No. 2439, Springer-Verlag, Granada, Spain, September 2002, pp. 298-307.
  5. MERKLE, L. D.; LAMONT, G. B.: A Random Function Based Framework for Evolutionary Algorithms. In T. Bäck, editor, Proceedings of the Seventh International Conference on Genetic Algorithms. Morgan Kaufmann Publishers, San Mateo, California, July 1997, pp. 105–112.
  6. OSYCZKA, A.: Multicriteria optimization for engineering design, Optimization (J. S. Gero, ed.), Academic Press, 1985, pp. 193-227.
  7. OSYCZKA, A.; KUNDU, S.: A new method to solve generalized multicriteria optimization problems uing the simple genetic algorithm. Structural Optimization, 10:94-99, 1995.
  8. OSYCZKA, A.; KUNDU, S.: A Genetic Algorithm-Based Multicriteria Optimization Method. In Proceedings of First World Congress of Structural and Multidisciplinary Optimization, Goslar, Elsevier Science, Germany, May 1995, pp. 909-914.
  9. PELIKAN, M.; SASTRY, K.; GOLDBERG, D. E.: Multiobjective BOA, Clustering, and Scalability. In H.-G. B.et al., editor, 2005 Genetic and Evolutionary Computation Conference (GECCO’2005), volume 1, New York, USA, ACM Press, June 2005, pp. 663-670.
  10. ROSENBERG, R. S.: Simulation of genetic populations with biochemical properties. PhD thesis, University of Michigan, Ann Arbor, Michigan, USA, 1967.
  11. SCHAFFER, J. D.: Multiple Objective Optimization with Vector Evaluated Genetic Algorithms. PhD thesis, Vanderbilt University, Nashville, Tennessee, 1984.
  12. SCHAFFER, J. D.: Multiple Objective Optimization with Vector Evaluated Genetic Algorithms. In Genetic Algorithms and their Applications: Proceedings of the First International Conference on Genetic Algorithms, , Hillsdale, New Jersey, 1985, pp. 93–100.
  13. SRINIVAS, N.; DEB, K.: Multiobjective Optimization using NonDominated Sorting in Genetic Algorithms. Evolutionary Computation, 2(3):221-248, fall 1994.
  14. VAN VELDHUIZEN, D. A.; LAMONT, G. B.: Genetic Algorithms, Building Bloks, and Multiobjective Optimization. In A. S. Wu, editor, Proceedings of the 1999 Genetic and Evolutionary Computation Conference. Workshop Program, Orlando, Florida, July 1999, pp. 125-126.
  15. ZITZLER, E.; THIELE, L.: Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. IEEE Transactions on Evolutionary Computation, 3(4):257-271, November 1999.
  16. ZITZLER, E.; LAUMANNS, M.; THIELE, L.: SPEA2: Improving the Strength Pareto Evolutionary Algorithm. In K. Giannakoglou, D. Tsahalis, J. Periaux, P. Papailou, and T. Fogarty, editors, EURIGEN 2001. Evolutionary Methods for Design, Optimization and Control with Applications to Industrial problems, Athens, Greece, 2001, pp. 95-100.
  17. ZYDALLIS, J. B.; VAN VELDHUIZEN, D. A.; LAMONT, G. B.: A Statistical Comparison of Multiobjective Evolutionary Algorithms Including the MOMGA-II. În E. Zitzler, K. Deb, L. Thiele, C.A.C. Coello, and D. Corne, editors, First International Conference on Evolutionary Multi-Criterion Optimization. Springer-Verlag. Lecture Notes in Computer Science No. 1993, 2001, pp. 226-240.
  18. ZYDALLIS, J. B.: Explicit Building-Block Multiobjective Genetic Algorithms: Theory, Analysis, and Development. PhD thesis, Air Force Institute of Technology, Department of the Air Force, Air University, Wtight-Patterson, Air-forceBase, Ohio, USA, 2003.

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

| Designed by ICI București
© Copyright 2008-2023, All Rights Reserved