Efektywność wielopopulacyjnego algorytmu ewolucyjnego dla zagadnień permutacyjnych

• Autorzy: Filipowicz B. , Chmiel W. , Dudek M. , Kadłuczka P.

Warianty tytułu

EN

Performance of multi-population evolutionary algorithms for permutation problems

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono wyniki badań najistotniejszych elementów wielopopulacyjnego algorytmu ewolucyjnego. W zastosowanym modelu wyspowym należą do nich: topologia połączeń, rozmiar i częstotliwość migracji oraz metoda selekcji migrantów. Zaproponowana miara różnorodności populacji może być wykorzystywana dla szerokiej klasy zagadnień permutacyjnych, których przykładem jest rozważane zagadnienie komiwojażera (TSP). Badania eksperymentalne przeprowadzono dla standardowych zagadnień testowych zaczerpniętych z biblioteki TSPLib95.

EN

The objective of this study is to examine the most important traits of a multi-population genetic algorithm. These elements include: connection topology, migration size, migration interval and migrant seleetion method. A review of the existing papers on multi-population algorithms is presented. A new diversity measure that applies to permutation encoding is introduced. It has proved effective in helping to retain balance between population diversity and convergence. For each trait, several algorithm configurations have been tested. Every configuration was tested against 25 different test instances, which were derived from the TSPLib95 library. Test results showed that, among the tested parameters, the most important was topology. Of the eleven topologies, a circular (ring) topology consisting of 16 islands obtained the best results. Varying of migration interval showed little correlation with the solution quality, but it did affect the convergence time. In comparison to other parameters, migration size exerts a relatively strong influence on performance. Moreover, a medium migration size proved to be reasonable. Among migrant selection methods, random selection outperformed these methods that exert selective pressure.

Słowa kluczowe

PL

zagadnienie permutacyjne; zagadnienie komiwojażera; wielopopulacyjny algorytm ewolucyjny; model wyspowy

EN

permutation problem; travelling salesman problem; multi-population evolutionary algorithm; island model

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2011
• Tom: T. 15, z. 2
• Strony: 147--158
• Opis fizyczny: Bibliogr. 13 poz., rys., tab.

Twórcy

autor

Filipowicz B.

• AGH Akademia Górniczo-Hutnicza, Wydział Elektrotechniki, Automatyki, Informatyki i Elektroniki, Katedra Automatyki

autor

Chmiel W.

• AGH Akademia Górniczo-Hutnicza, Wydział Elektrotechniki, Automatyki, Informatyki i Elektroniki, Katedra Automatyki

autor

Dudek M.

• AGH Akademia Górniczo-Hutnicza, Wydział Elektrotechniki, Automatyki, Informatyki i Elektroniki, Katedra Automatyki

autor

Kadłuczka P.

• AGH Akademia Górniczo-Hutnicza, Wydział Elektrotechniki, Automatyki, Informatyki i Elektroniki, Katedra Automatyki

Bibliografia

• [1] Cohoon J.P., Hegde S.U., Martin W.N., Richards D., Punctuated eguilibria: a parallel genetic algorithm. Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, Hillsdale, L. Erlbaum Associates Inc., 1987, 148.
• [2] Wang L., Maciejewski A., Siegel H., Roychowdhury V., A comparative study of five parallel genetic algorithms using the traveling salesman problem. Salesman Problem, IPPS: llth International Parallel Processing Symposium, IEEE Computer, Society Press, 1998.
• [3] Borovska P., Lazarova M., Migration policies for island genetic models on multicomputer platform, [w:] Intelligent Data Acąuisition and Advanced Computing Systems: Technology and Applications, IEEE, 2007, 143.
• [4] Cantu-Paz E., Topologies, migration rates, and multi-population parallel genetic algorithms.
• [5] Sekaj I., Robust parallel genetic algorithms with reinitialisation. Yao X. and a. editors, Lecture Notes in Computer Science, PPSN, Springer, 2004,3242,411.
• [6] Whitley D., Rana S., Heckendorn R., Island model genetic algorithms and linearly separable problems. Proceedings of AISB Workshop on Evolutionary Computation, LNCS, Springer--Verlag, 1997, 1305, 109.
• [7] Skolicki Z., DeJong K., The influence of migration sizes and intervals on island models. GECCO '05: Proceedings of the conference on Genetic and evolutionary computation, New York 2005, 1295.
• [8] Hong T.P., Lin W.Y., Liu S.M., Lin J.H., Dynamically adjusting migration rates for multi-population genetic algorithms. Journal of Advanced Computational Intelligence and Intelligent Informa-tics, 2006.
• [9] Denzinger J., Kidney J., Improving migration by diversity. Evolutionary Computation, CEC, 2003.
• [10] Morrison R., DeJong K., Measurement of population diversity. 5th International Conference EA 2001, Springer-Verlag, 2002, 2310, 31.
• [11] Tsujimura Y, Gen M., Entropy-based genetic algorithm for sohing TSP. Knowledge-Based Intelligent Electronic Systems, Proceedings KES '98, IEEE, 1998, 285.
• [12] Dudek M., Badanie efektywności wielopopulacyjnego algorytmu ewolucyjnego. Praca magisterska, AGH, Kraków 2009.
• [13] Uni-Heidelberg, TSPLib95. http://www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95.