Wyniki wyszukiwania - BazTech

1

Zastosowanie algorytmów rojowych w rozwiązywaniu zagadnień permutacyjnych

Chmiel W., Kadłuczka P., Packanik G.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2011

|

T. 15, z. 2

117-126

PL

W artykule przedstawiono wyniki badań nad zastosowaniem algorytmów rojowych w optymalizacji zagadnienia szeregowania zadań, jako przykładu AP-trudnego zagadnienia optymalizacyjnego. W oparciu o instancje testowe dla zagadnienia szeregowania zadań zaproponowane przez E. Taillarda, przeprowadzono eksperymenty obliczeniowe, porównując wyniki otrzymywane przez algorytm ptasi oraz algorytm pszczeli. Przebadano także wpływ implementacji poszczególnych elementów algorytmów, takich jak liczba, dokładność i sposób przeszukiwania otoczenia rozwiązań obiecujących, na uzyskiwane wyniki optymalizacji. Pozwoliło to na sformowanie ogólnych wniosków dotyczących własności obu algorytmów.

EN

The objective of this paper is to examine the most important properties of a multi-population genetic algorithm. These elements include: connection topology, migration size, migration interval and a method for migrant selection. A short review of the existing papers on multi-population algorithms is presented. A new diversity measure that applies to permutation encoding is introduced. The proposed measure has proved effective in helping to retain balance between population diversity and convergence. A multi-population genetic algorithm, with different parameters like type of topology, migration interval, migration size and selection method was tested against several different test instances of traveling salesman problem, that belongs to the NP-hard permutational problem class.

2

Efektywność wielopopulacyjnego algorytmu ewolucyjnego dla zagadnień permutacyjnych

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

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2011

|

T. 15, z. 2

147-158

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.

3

Strategia przetwarzania wiedzy w wielopopulacyjnym algorytmie ewolucyjnym

Kadłuczka P., Chmiel W., Piwowarczyk J.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2009

|

T. 13, z. 2

325-331

PL

Artykuł prezentuje koncepcję wielopopulacyjnego, samoadaptacyjnego algorytmu ewolucyjnego, wykorzystującego technologię inteligentnych agentów. Algorytm ten zastosowano dla zagadnienia komiwojażera, należącego do klasy problemów permutacyjnych NP-trudnych. Współbieżna realizacja wielu algorytmów ewolucyjnych pozwala na ich komunikację, mającą na celu udostępnienie informacji dotyczącej dotychczasowego przebiegu obliczeń, uzyskanych rozwiązań oraz oceny aktualnie wykorzystywanych elementów konstrukcyjnych algorytmu. Zróżnicowana strategia przetwarzania i stosowania wiedzy prowadzi do zróżnicowanej efektywności algorytmów i całego systemu.

EN

The paper presents intelligent agent approach to multi-population evolutionary algorithm with self-adaptation. The algorithm was used to solve traveling salesman problem that belongs to the NP-hard permutational problem class, one of the most popular optimization discrete problem. Concurrent system realization allows to exchange data, like solutions, results and parameter estimations between algorithms. The possibility to improve the algorithm and system efficiency is based on the strategy and knowledge processing diversification.