Clustering based population size reduction method for evolutionary algorithms

• Autorzy: Dziedzic M.

Warianty tytułu

PL

Metoda redukcji liczności populacji algorytmów ewolucyjnych oparta na klasteryzacji

• Języki publikacji: EN

Abstrakty

EN

Nowadays, due to the growing dimensionality of optimisation problems, numerous studies are dedicated to reduction of metaheuristics computational requirements. Reducing size of the population during optimisation process is one of the promising research trends in the field of Evolutionary Algorithms. The purpose of this paper is to clarify the subject in form of a survey of population size reduction methods already proposed and to present preliminary results of a new method based on the clustering technique. Introduced method was implemented in the framework of Differential Evolution algorithm and verified on a set of real-parameter benchmark functions.

PL

Obecnie, ze względu na ciągły wzrost wymiarowości problemów optymalizacyjnych, liczne prace poświęcone są zmniejszeniu zapotrzebowania metaheurystyk na zasoby obliczeniowe. Jednym z obiecujących kierunków badań w przypadku algorytmów ewolucyjnych jest redukcja liczności populacji w trakcie procesu optymalizacji. Niniejszy artykuł ma na celu przybliżenie tej tematyki w formie przeglądu dotychczas zaproponowanych metod oraz prezentację wstępnych wyników autorskiej metody opartej na technice klasteryzacji. Przedstawiona metoda została zaimplementowana w strukturę algorytmu ewolucji różnicowej i zweryfikowana za pomocą standardowego zestawu funkcji rzeczywistych wielu zmiennych.

Słowa kluczowe

EN

metaheuristics; evolutionary algorithms; differential evolution; population size reduction; clustering

PL

metaheurystyki; algorytmy ewolucyjne; ewolucja różnicowa; redukcja liczności populacji; klasteryzacja

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Czasopismo Techniczne. Automatyka
• Rocznik: 2012
• Tom: R. 109, z. 1-AC
• Strony: 81--92
• Opis fizyczny: Bibliogr. 34 poz., il., wykr.

Twórcy

autor

Dziedzic M.

• Katedra Automatyki i Technik Informacyjnych, Wydział Inżynierii Elektrycznej i Komputerowej, Politechnika Krakowska

Bibliografia

• [1] Abbas A., The self-adaptive pareto differential evolution algorithm, Proceedings of the IEEE Congress on Evolutionary Computation, 2002, 831-836.
• [2] Arabas J., Michalewicz Z., Mulawka J., GAVaPS – a genetic algorithm with varying population size, Proceedings of the 1st IEEE Conference on Evolutionary Computation, 1994, 73-78.
• [3] Auger A., Hansen N., A restart CMA evolution strategy with increasing population size, Proceedings of the 2005 IEEE Congress on Evolutionary Computation, 2005, 1769-1776.
• [4] Bäck T., Fogel D.B., Michalewicz Z., Evolutionary Computation 1: Basic Algorithms and Operators, Taylor & Francis, 2000.
• [5] Blum C., Chiong R., Clerc M., De Jong K., Michalewicz Z., Neri F., Weise T., Evolutionary optimization, [in:] Variants of Evolutionary Algorithms for Real-World Applications, Chiong R., Weise T., Michalewicz Z. (Eds.), Springer, 2012, 1-19.
• [6] Brest J., Maučec M.S., Population size reduction for the differential evolution algorithm, Applied Intelligence, vol. 29, 2008, 228-247.
• [7] Brest J., Maučec M.S., Self-adaptive differential evolution algorithm using population size reduction and three strategies, [in:] Soft Computing – A Fusion of Doundations, Methodologies and Applications, vol. 15, 2011, 2157-2174.
• [8] Brest J., Zamuda A., Bošković B., Greiner S., Žumer V., An analysis of the control parameters’ adaptation in DE, [in:] Advances in Differential Evolution, Chakraborty U.K. (Eds.), 2008, 89-110.
• [9] Diaz-Gomez P.A., Hougen D.F., Initial population for genetic algorithms: A metric approach, Proceedings of the 2007 International Conference on Genetic and Evolutionary Methods, 2007, 43-49.
• [10] Dziedzic M., Differential Evolution with Population Size Reduction, Proceedings of The First International Conference on Automatic Control and Information Technology, vol. "Streszczenia”, CD (9 pages), 2011, 28.
• [11] Eiben A.E., Marchiori E., Valko V.A., Evolutionary algorithms with on-the-fly population size adjustment, [in:] Parallel Problem Solving from Nature, Yao X., Burke E.K., Lozano J.A., Smith J., Merelo-Guervos J.J., Bullinaria J.A., Rowe J.E., Tino P., Kabán A., Schwefel H.-P. (Eds.), 2004, 41-50.
• [12] Fernandes C., Rosa A., A study on non-random mating and varying population size in genetic algorithms using a royal road function, Proceedings of the 2001 Congress on Evolutionary Computation, 2001, 60-66.
• [13] Fernandes C., Rosa A., Self-regulated population size in evolutionary algorithms, [in:] Parallel Problem Solving from Nature, Runarsson T.P., Beyer H.-G., Burke E., Merelo-Guervos J.J., Whitley L.D., Yao X. (Eds.), 2006, 920-929.
• [14] Finck S., Hansen N., Ros R., Auger A., Real-Parameter Black-Box Optimization Benchmarking 2010: Presentation of the Noiseless Functions, Working Paper 2009/20, 3rd GECCO Workshop for Real-Parameter Optimization, 2012.
• [15] Harik G.R., Lobo F.G., A parameter-less genetic algorithm, Proceedings of the 1999 Genetic and Evolutionary Computation Conference, 1999, 258-265.
• [16] Hill R.R., A Monte Carlo study of genetic algorithm initial population generation methods, Proceedings of 1999 Winter Simulation Conference, 1999, 543-547.
• [17] Hinterding R., Michalewicz Z., Peachey T.C., Self-adaptive genetic algorithm for numeric functions, [in:] Parallel Problem Solving from Nature, Voigt H.-M., Ebeling W., Rechenberg I., Schwefel H.-P. (Eds.), 1996, 420-429.
• [18] Iacca G., Mallipeddi R., Mininno E., Nerif., Suganthan P.N., Superfit and population size reduction in compact differential evolution, Proceedings of 2011 IEEE Workshop on Memetic Computing, 2011, 1-8.
• [19] Kaelo P., Ali M.M., A numerical study of some modified differential evolution algorithms, European Journal of Operational Research, 169(3), 2006, 1176-1184.
• [20] Lima C.F., Lobo F.G., Parameter-less optimization with the extended compact genetic algorithm and iterated local search, „Genetic and Evolutionary Computation, Part I”, Deb K. (Eds.), 2004, 1328-1339.
• [21] Mac Queen J.B., Some methods for classification and analysis of multivariate observations, Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, 1967, 281-297.
• [22] Omran M.G.H., Salman A., Engelbrecht A.P., Self-adaptive differential evolution, [in:] Computational Intelligence and Security, Hao Y., Liu J., Wang Y.-P., Cheung Y.-M., Yin H., Jiao L., Ma J., Jiao Y.-C. (Eds.), vol. 3801, 2005, 192-199.
• [23] Paterlini S., Krink T., Differential evolution and particle swarm optimization in partitional clustering, Computational Statictics & Data Analysis, vol. 50, 2006, 1220-1247.
• [24] Schlierkamp-Voosen D., Muhlenbein H., Strategy adaptation by competing subpopulations, [in:] Parallel Problems Solving from Nature, Davidor Y., Schwefel H.-P., Männer R. (Eds.), 1994, 199-208.
• [25] Shi X.H., Wan L.M., Lee H.P., Yang X.W., Wang L.M., Liang Y.C., An improved genetic algorithm with variable population size and a pso-ga based hybrid evolutionary algorithm, Proceedings of the 2nd International Conference on Machine Learning and Cybernetics, 2003, 1735-1740.
• [26] Storn R., Differential evolution homepage (Online: 2011-11-20), http://www.icsi.berkeley.edu/~storn/code.html
• [27] Storn R., On the usage of differential evolution for function optimization, Biennial Conference of the North American Fuzzy Information Processing Society, 1996, 519-523.
• [28] Storn R., Price K., Differential evolution – A simple and efficient heuristic for global optimization over continuous spaces, Journal of Global Optimization, vol. 11, 1997, 341-359.
• [29] Teo J., Exploring dynamic self-adaptive populations in differential evolution, Soft Computing – A Fusion of Foundations, Methodologies and Applications, vol. 10, 2006, 673-686.
• [30] Tirronen V., Neri F., Differential evolution with fitness diversity self-adaptation, [in:] Nature-inspired Algorithm for Optimisation, Chiong R. (Eds.), 2009, 199-234.
• [31] Toğan V., Daloğlu A.T., An improved genetic algorithm with initial population strategy and self-adaptive member grouping, Computers & Structures, vol. 86, 2008, 1204-1218.
• [32] Xu R., Wunsch D., Clustering, Wiley-IEEE Press, 2008.
• [33] Zamuda A., Brest J., Boskovic B., Zumer V., Large scale global optimization using differential evolution with self-adaptation and cooperative co-evolution, Proceedings of the IEEE Congress on Evolutionary Computation, 2008, 3718-3725.
• [34] Zhuang N., Benten M.S., Cheung P.Y., Improved variable ordering of BDDS with novel genetic algorithm, Proceedings of the IEEE International Symposium on Circuits and Systems, vol. 3, 1996, 414-417.

Uwagi

EN

This contribution is partially supported by the Foundation for Polish Science under International PhD Projects in Intelligent Computing. Project financed from The European Union within the Innovative Economy Operational Programme 2007–2013 and European Regional Development Fund.