Szczegóły publikacji
Opis bibliograficzny
Efektywność wielopopulacyjnego algorytmu ewolucyjnego dla zagadnień permutacyjnych — Performance of multi-population evolutionary algorithms for permutation problems / Bogusław FILIPOWICZ, Wojciech CHMIEL, Maciej Dudek, Piotr KADŁUCZKA // Automatyka : półrocznik Akademii Górniczo-Hutniczej im. Stanisława Staszica w Krakowie ; ISSN 1429-3447. — 2011 — t. 15 z. 2, s. 147–158. — Bibliogr. s. 158, Streszcz., Summ.
Autorzy (4)
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 61072 |
|---|---|
| Data dodania do BaDAP | 2011-10-03 |
| Tekst źródłowy | URL |
| Rok publikacji | 2011 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Creative Commons | |
| Czasopismo/seria | Automatyka/Automatics |
Streszczenie
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.
Abstract
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.
