Improving Population-Based Algorithms with Fitness Deterioration

• Autorzy: Wolny A. , Schaefer R.
• Języki publikacji: EN

Abstrakty

EN

This work presents a new hybrid approach for supporting sequential niching strategies called Cluster Supported Fitness Deterioration (CSFD). Sequential niching is one of the most promising evolutionary strategies for analyzing multimodal global optimization problems in the continuous domains embedded in the vector metric spaces. In each iteration CSFD performs the clustering of the random sample by OPTICS algorithm and then deteriorates the fitness on the area occupied by clusters. The selection pressure pushes away the next-step sample (population) from the basins of attraction of minimizers already recognized, speeding up finding the new ones. The main advantages of CSFD are low memory an computational complexity even in case of large dimensional problems and high accuracy of deterioration obtained by the flexible cluster definition delivered by OPTICS. The paper contains the broad discussion of niching strategies, detailed definition of CSFD and the series of the simple comparative tests.

Słowa kluczowe

EN

basin of attraction; clustering; fitness deterioration; genetic algorithm; optics; sequential niching

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2011
• Tom: nr 4
• Strony: 31--44
• Opis fizyczny: Bibliogr. 22 poz., rys., tab.

Twórcy

autor

Wolny A.

autor

Schaefer R.

• Department of Computer Science, AGH University of Science and Technology, Mickiewicza Av. 30, 30-059 Krakow, Poland,

Bibliografia

• [1] E. Zeidler, Nonlinear Functional Analysis and its Application. Springer, 1985.
• [2] M. P. Pardalos and H. E. Romeijn, Handbook Global Optimization, vol. 2, Kluwer, 2002.
• [3] R. Schaefer, Foundation of Glabal Genetic Optimization. Springer, 2007.
• [4] A. H. G. Rinnoy Kan and G. T. Timmer 1987, “Stochastic global optimization methods”, Mathematical Programming, vol. 39, pp. 27–56.
• [5] Toward Global Optimization, L. C. W. Dixon and G. P. Szeg¨o, Eds. North Holland, 1975.
• [6] D. Goldberg, Genetic Algorithms and their Applications. Addison- Wesley, 1989.
• [7] J. Arabas, Wykłady z algorytmów ewolucyjnych. WNT, Warsaw, Poland (in Polish).
• [8] S. W. Mahfoud, “Niching Methods”, in Handbook of Evolutionary Computations, T. B¨ack, D. B. Fogel, and Z. Michalewicz, Eds. Oxford University Press., 1997
• [9] A. Obuchowicz, “The evolutionary search with soft selection and deterioration of the objective function”, in Proc. 6th Int. Conf. Intel. Inform. Sys. IIS’97, Zakopane, Poland, 1997, pp. 288–295.
• [10] R. Schaefer, K. Adamska, and H. Telega, “Genetic clustering in continuous landscape exploration”, Engin. Applicat. Artif. Intell. EAAI, vol. 17, pp. 407–416, 2004.
• [11] D. Beasley, D. R. Bull, and R. R. Martin, “A sequential niche for multimodal function optimization”, Evol. Comput., vol. 1, no. 2, pp. 101–125, 1993.
• [12] A. Obuchowicz, “Adoption of the time-varying landscape using an evolutionary search with soft selection algorithm”, in Proc. 3rd Krajowa Konferencja Algorytmy Ewolucyjne i Optymalizacja Globalna KAGiOG Conf. Potok Złoty, Poland, 1997, pp. 245–251.
• [13] A. Obuchowicz and K. Patan, “About some evolutionary algorithm cases”, in Proc. 2nd Krajowa Konferencja Algorytmy Ewolucyjne i Optymalizacja Globalna KAEiOG Conf., Rytro, Poland, 1997, pp. 193–200.
• [14] A. Obuchowicz and J. Korbicz, “Evolutionary search with soft selection algorithms in parameter optimization, in Proc. Parallel Proces. Appl. Mathemat. Conf. PPAM’99, Kazimierz Dolny, Poland, 1999, pp. 578–586
• [15] H. Telega, “Rownoległe algorytmy rozwia，zywania wybranych zagadnień odwrotnych ”, Ph.D. thesis, AGH University of Science and Technology, Krakow, Poland, 1999 (in Polish).
• [16] R. Schaefer and J. Kołodziej, “Genetic search reinforced by the population hierarchy”, in Foundations of Genetic Algorithms 7, K. A. De Jong, R. Poli, and J. E. Rowe, Eds.Morgan Kaufman, 2003, pp. 383–399.
• [17] R. Schaefer and K. Adamska, “Well-tuned genetic algorithm and its advantage in detecting basins of attraction”, in Proc. 7th Krajowa Konferencja Algorytmy Ewolucyjne i Optymalizacja Globalna KAEiOG Conf., Kazimierz, Poland, 2004, pp. 149–154.
• [18] R. Schaefer and Z. J. Jabłoński, “On the convergence of sampling measures in global genetic search”, LNCS, vol. 2328, pp. 593–600, 2001.
• [19] M. Ankerst, M. M. Breunig, H. P. Kriegel, and J. Sander, “OPTICS: Ordering points to identify the clustering structure”, in Proc. ACM SIGMOD Int. Conf. Manag. Data, Philadephia, Pennsylvania, USA, 1999, vol. 28/2, pp. 49–60.
• [20] M. Ester, H. P. Kriegel, J. Sander, and Xiaowei Xu, “A densitybased algorithm for discovering clusters in large spatial databases with noise”, Computer, no. 6, pp. 226–231, 1996.
• [21] J. P. Hoffbeck and D. A. Landgrebe, “Covariance matrix estimation and classification with limited training data”, IEEE Trans. Pattern Anal. Machine Intell., vol. 18, no. 7, 1996.
• [22] B. Wierzba, A. Semczuk, J. Kołodziej, and R. Schaefer, “Hierarchical genetic strategy with real number encoding”, in Proc. 6th Krajowa Konferencja Algorytmy Ewolucyjne i Optymalizacja Globalna KAEiOG Conf., Łagow Lubuski, Poland, 2003, pp. 231–237.