Recognizing Sets in Evolutionary Multiobjective Optimization

• Autorzy: Gajda-Zagórska E.
• Języki publikacji: EN

Abstrakty

EN

Among Evolutionary Multiobjective Optimization Algorithms (EMOA) there are many which find only Paretooptimal solutions. These may not be enough in case of multimodal problems and non-connected Pareto fronts, where more information about the shape of the landscape is required. We propose a Multiobjective Clustered Evolutionary Strategy (MCES) which combines a hierarchic genetic algorithm consisting of multiple populations with EMOA rank selection. In the next stage, the genetic sample is clustered to recognize regions with high density of individuals. These regions are occupied by solutions from the neighborhood of the Pareto set. We discuss genetic algorithms with heuristic and the concept of well-tuning which allows for theoretical verification of the presented strategy. Numerical results begin with one example of clustering in a single-objective benchmark problem. Afterwards, we give an illustration of the EMOA rank selection in a simple two-criteria minimization problem and provide results of the simulation of MCES for multimodal, multi-connected example. The strategy copes with multimodal problems without losing local solutions and gives better insight into the shape of the evolutionary landscape. What is more, the stability of solutions in MCES may be analyzed analytically.

Słowa kluczowe

EN

basin of attraction; clustering; genetic algorithm; multiobjective optimization

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2012
• Tom: nr 1
• Strony: 74--82
• Opis fizyczny: Bibliogr. 26 poz., rys.

Twórcy

autor

Gajda-Zagórska E.

• AGH University of Science and Technology, Faculty of Electrical Engineering, Automatics, IT and Electronics, A. Mickiewicza Av. 30, B-1 building, 30-059 Krakow, Poland,

Bibliografia

• [1] B. Barabasz, S. Migorski, R. Schaefer, and M. Paszyński, “Multideme, twin adaptive strategy hp-hgs”, Inverse Problems in Sci. Engin., vol. 19, no. 1, pp. 3–16, 2011.
• [2] M. C. Cowgill, R. J. Harvey, and L. T. Watson, “A genetic algorithm approach to cluster analysis”, Comput. Mathem. Appl., vol. 37, no. 7, pp. 99–108, 1999.
• [3] E. Hruschka and N. Ebecken, “A genetic algorithm for cluster analysis”, Intell. Data Analysis, vol. 7, no. 15, pp. 15–25, 2003.
• [4] U. Maulik and S. Bandyopadhyay, “Genetic algorithm-based clustering technique”, Pattern Recognition, vol. 33, no. 9, pp. 1455–1465, 2000.
• [5] R. Schaefer, K. Adamska, and H. Telega, “Clustered genetic search in continuous landscape exploration”, Engin. Appl. Artificial Intell., vol. 17, no. 4, pp. 407–416, 2004.
• [6] K. Adamska, “Genetic clustering as a parallel algorithm for approximating basins of attraction”, in Parallel Processing and Applied Mathematics, R. Wyrzykowski, J. Dongarra, M. Paprzycki, and J. Wasniewski, Eds., vol. 3019, LNCS. Berlin/Heidelberg: Springer, 2004, pp. 536–543.
• [7] R. Schaefer and K. Adamska, “Well-tuned genetic algorithm and its advantage in detecting basins of attraction”, in Proc. 7th Conf. Evol. Algorithms Global Optimiz., Kazimierz Dolny, Poland, 2004, pp. 149–154.
• [8] Handbook of Global Optimization vol. 2. P. M. Pardalos and H. E. Romeijn, Eds. Kluwer, 1995. Kluwer, 1995.
• [9] R. Schaefer and H. Telega, Foundation of Global Genetic Optimization. Springer, 2007.
• [10] C. Stoean, M. Preuss, R. Stoean, and D. Dumitrescu, “Ea-powered basin number estimation by means of preservation and exploration”, in Parallel Problem Solving from Nature – PPSN X, G. Rudolph, T. Jansen, S. M. Lucas, C. Poloni, and N. Beume, Eds., vol. 5199, LNCS, Berlin: Springer, 2008, pp. 569–578.
• [11] C. Stoean R. Stoean, M. Preuss, “Approximating the number of attraction basins of a function by means of clustering and evolutionary algorithms”, in 8th Int. Conf. Artif. Intelli. Digit. Commun. AIDC 2008, Research Notes in Artificial Intelligence and Digital Communications, N. Tandareanu, Ed., Reprograph Press, 2008, pp. 171–180.
• [12] V. A. Emelichev and E. E. Gurevsky, “On stability of a paretooptimal solution under perturbations of the parameters for a multicriteria combinatorial partition problem” [Online]. Available: http://www.math.md/publications/csjm/issues/v16-n2/8827/
• [13] E. Zitzler, “Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications”, Ph.D. thesis, ETH Zurich, Switzerland, 1999.
• [14] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learnings. Reading, Massachusetts: Addison-Wesley, 1989.
• [15] N. Srinivas and K. Deb, “Multiobjective optimization using nondominated sorting in genetic algorithms”, Evolutionary Comput., 1994.
• [16] C. M. Fonseca and P. J. Fleming, Genetic algorithms for multiobjective optimization: Formulation, discussion and generalization. Genetic Algorithms: Proceedings of the Fifth International Conference, pp. 416-423, 1993.
• [17] E. Zitzler and L. Thiele, “Multiobjective evolutionary algorithms: A comparative case study and the strength pareto evolutionary algorithm”, IEEE Trans. Evolutionary Comput., vol. 3, no. 4, pp. 257–271, 1999.
• [18] E. Zitzler, M. Laumanns, and L. Thiele, “SPEA2: Improving the strength pareto evolutionary algorithm for multiobjective optimization”, in Evolutionary Methods for Design, Optimisation and Control with Application to Industrial Problems (EUROGEN 2001), International Center for Numerical Methods in Engineering (CIMNE), 2002, pp. 95–100.
• [19] M. Emmerich, N. Beume, and B. Naujoks, “An EMO algorithm using the hypervolume measure as selection criterion”, in Evolutionary Multi-Criterion Optimization: Third International Conference EMO 2005, Springer, 2005, pp. 62–76.
• [20] M. Preuss, B. Naujoks, and G. Rudolph, “Pareto set and EMOA behavior for simple multimodal multiobjective functions”, in Parallel Problem Solving from Nature – PPSN IX, T. P. Runarsson, H.-G. Beyer, E. Burke, J. J. Merelo-Guervos, L. D. Whitley, and X. Yao, Eds., vol. 4193, LNCS, Berlin: Springer, 2006, pp. 513–522.
• [21] J. Kolodziej, “Modelling hierarchical genetic strategy as a family of markov chains”, in Proc. Int. Conf. Parallel Proces. Applied Mathem.-Revised Papers, Springer, 2002, pp. 595–598.
• [22] R. Schaefer and J. Kolodziej, “Genetic search reinforced by the population hierarchy”, in Foundations of Genetic Algorithms 7, R. Poli, K. A. De Jong, and J. E. Rowe, Eds., Morgan Kaufman, 2003, pp. 383–388.
• [23] C. A. Coello Coello and G. B. Lamont, Applications of Multi-objective Evolutionary Algorithms. World Scientific, 2004.
• [24] M. D. Vose, The Simple Genetic Algorithm. MIT Press, 1999.
• [25] E. Gajda, R. Schaefer, and M. Smolka, “Evolutionary multiobjective optimization algorithm as a markov system”, in Parallel Problem Solving from Nature – PPSN XI, Springer, 2010, pp. 617–626.
• [26] H. Park and C. Jun, “A simple and fast algorithm for k-medoids clustering”, Expert Systems with Applications, vol. 36, no. 2, part 2, pp. 3336–3341, 2009.