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

• Autorzy: Chmiel W. , Kadłuczka P. , Packanik G.

Warianty tytułu

EN

Performance of multi-population evolutionary algorithms for permutation problems

• Języki publikacji: PL

Abstrakty

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.

Słowa kluczowe

PL

zagadnienie permutacyjne; zagadnienie szeregowania zadań; algorytm ptasi; algorytm pszczół; dyskretna optymalizacja

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: 117--126
• Opis fizyczny: Bibliogr. 9 poz., tab.

Twórcy

autor

Chmiel W.

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

autor

Kadłuczka P.

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

autor

Packanik G.

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

Bibliografia

• [1] Filipowicz B., Badania operacyjne. Wybrane metody obliczeniowe i algorytmy. Część I. Kraków, F.U.H Poldex, 1997.
• [2] Coffman jra E.G., Teoria szeregowania zadań. Warszawa, Wydawnictwa Naukowo-Techniczne, 1980.
• [3] Pham D.T., Koc E., Lee J.Y., Phrueksanant J., Using the Bees Algorithm to schedule jobs for a machinę. Manufacturing Engineering Centre, Cardiff University, 2007.
• [4] Filipowicz B., Chmiel W., Kadłuczka P., Ukierunkowane przeszukiwanie przestrzeni rozwiązań w algorytmach rojowych. Automatyka (półrocznik AGH), 13, 2, 2009.
• [5] Kennedy j., Eberhart R.C., Particle Swaem Optimization. In Proceedings of the IEEE International Conference on Neural Networks, Perth, 1995, 12.
• [6] Ismael A., Vaz F., Vicente L.N., A particle swarm pattern search method for bound constrained nonlinear optimization. Portugalia, 2006.
• [7] Ching-Jong L., Chao-Tang T., Pin L., A discrete version of particle swarm optimization for flowshop scheduling problems. Computers & Operations Research, 2007.
• [8] Packanik G., Zastosowania algorytmów rojowych w zagadnieniach szeregowania zadań. Praca magisterska, AGH, Kraków, 2010.
• [9] Tillard E., Benchmarks for Basic Scheduling Problems. http://mistic.heig-vd.ch/taillard/proble- mes.dir/ ordonnancement.dir/ordonnancement, 1989.