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

REZOLVAREA UNOR PROBLEME DE OPTIMIZARE MULTI-OBIECTIV BAZATĂ PE ALGORITMI EVOLUTIVI

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

Universitatea POLITEHNICA din Bucureşti – Facultatea de Automatică şi Calculatoare

Rezumat: Cele mai multe probleme de optimizare care apar în practică au un caracter multi-obiectiv deoarece în cadrul lor este necesar să fie optimizate simultan mai multe funcţii obiectiv. În acest articol se realizează o analiză a modului de rezolvare a problemelor de optimizare multi-obiectiv, cu accent pe rezolvarea bazată pe algoritmi evolutivi. Se prezintă o clasificare a tehnicilor de optimizare în enumerative, deterministe şi stocastice. Din cadrul tehnicilor de optimizare stocastice sunt detaliaţi algoritmii de calcul evolutiv (Evolutionary Algorithms – EA). Aceşti algoritmi sunt folosiţi cu succes pentru rezolvarea problemelor de optimizare multi-obiectiv. Se prezintă concepte de bază utilizate în cadrul algoritmilor evolutivi şi se trec în revistă mai mulţi algoritmi evolutivi pentru rezolvarea problemelor de optimizare multi-obiectiv. În final, se rezolvă patru probleme de optimizare multi-obiectiv, cu ajutorul unui cunoscut algoritm evolutiv: algoritmul genetic cu sortare ne-dominată (Non-Dominated Sorting in Genetic Algorithms – NSGA-II). Programul Matlab ce implementează algoritmul NSGA-II calculează frontiera Pareto a celor patru probleme considerate.

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

Introducere

Cele mai multe probleme de optimizare care apar în practică au un caracter multi-obiectiv deoarece în cadrul lor este necesar să fie optimizate simultan mai multe funcţii obiectiv. Problemele de optimizare multi-obiectiv joaca un rol important în inginerie, management şi în multe alte domenii. Funcţiile obiectiv în cadrul unei probleme de optimizare multi-obiectiv pot să fie, în cele mai multe cazuri, în conflict. De exemplu în acelaşi timp unele dintre funcţiile obiectiv trebuie maximizate iar altele minimizate. De asemenea optimul realizat pentru anumite funcţii obiectiv nu coincide cu optimul realizat de alte funcţii obiectiv. Găsirea unor soluţii care să realizeze un compromis, cu o bază raţională, a reprezentat o provocare pentru cercetători de-a lungul timpului.

O problemă de optimizare multi-obiectiv poate fi definită ca problema găsirii unui vector (componentele acestuia având semnificaţia de variabile de decizie) care satisface anumite restricţii şi optimizează o funcţie vectorială ale cărei componente reprezintă funcţiile obiectiv [18]. Aceste funcţii descriu din punct de vedere matematic criterii de performanţă care de cele mai multe ori sunt în conflict una cu alta. Termenul de “optimizare” înseamnă găsirea unei soluţii care furnizează valori pentru funcţiile obiectiv acceptabile de către decident.

Concluzii

În lucrare s-a realizat o analiză a modurilor de rezolvarea a problemelor de optimizare multi-obiectiv prin algoritmi clasici şi prin algoritmi bazaţi pe Inteligentă Artificială avansată. Domeniul Optimizărilor Multi-obiectiv este extrem de complex şi dificil din punct matematic. El posedă multe sub-domenii puţin cercetate şi probleme remarcabile. Algoritmii bazaţi pe inteligenţă artificială folosiţi pentru rezolvarea problemelor de optimizare multi-obiectiv sunt algoritmii evolutivi.

Algoritmii de inteligenţă artificială au un caracter euristic. Ei sunt aplicaţi de cele mai multe ori la probleme în care abordările cu algoritmi clasici de optimizare au performanţe slabe sau foarte slabe. Aceşti algoritmi sunt eficienţi în sensul că produc soluţii suboptimale într-un interval rezonabil de timp. De multe ori au fost elaborate metode euristice de optimizare care se aplica unor clase largi de probleme de optimizare. Astfel de metode au fost numite meta-euristici. De exemplu algoritmii evoluţionişti sau cei de tip Simulated Annealing, metodele Monte Carlo, căutarea “tabu search” sunt exemple de meta-euristici.

În concluzie pentru a se obţine soluţii bune la problemele de optimizare (multi-obiectiv) este bine să se utilizeze atât algoritmi determinişti clasici cât şi algoritmi bazaţi pe inteligenţă artificială. Există probleme la care cea mai bună alegere pentru rezolvarea lor o reprezintă algoritmii clasici cunoscuţi, la fel cum, există probleme care pot fi rezolvate numai prin aplicarea algoritmilor bazaţi pe inteligenţă artificială.

BIBLIOGRAFIE

  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.

Vizualizează articolul complet

  1. 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.
  2. 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.

  1. 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.
  2.  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.
  3. 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.
  4. KNOWLES, J. D.; CORNE. D. W.: Approximating the Nondominated Front Using the Pareto Archieved Evolution Strategy. Evolutionary Computation, 8(2):149-172, 2000.
  5. 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.
  6. 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.
  7. 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.
  8. OSYCZKA, A.: Multicriteria optimization for engineering design, Optimization (J. S. Gero, ed.), Academic Press, 1985, pp. 193-227.
  9. OSYCZKA, A.; KUNDU, S.: A new method to solve generalized multicriteria optimization problems uing the simple genetic algorithm. Structural Optimization, 10:94-99, 1995.
  10. 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.
  11. 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.
  12. ROSENBERG, R. S.: Simulation of genetic populations with biochemical properties. PhD thesis, University of Michigan, Ann Arbor, Michigan, USA, 1967.
  13. SCHAFFER, J. D.: Multiple Objective Optimization with Vector Evaluated Genetic Algorithms. PhD thesis, Vanderbilt University, Nashville, Tennessee, 1984.
  14. 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.
  15. SRINIVAS, N.; DEB, K.: Multiobjective Optimization using NonDominated Sorting in Genetic Algorithms. Evolutionary Computation, 2(3):221-248, fall 1994.
  16. 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.
  17. 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.
  18. 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.
  19. 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.
  20. 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