Ukierunkowane przeszukiwanie przestrzeni rozwiązań w algorytmach rojowych

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

Warianty tytułu

EN

Guided search of the solution space in swarm algorithm

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono sposób ukierunkowania przeszukiwania przestrzeni rozwiązań, wykorzystujący warunkową wartość oczekiwaną funkcji celu rozwiązań częściowo ustalonych. Teoretyczne podstawy dotyczące wartości oczekiwanej opracowano dla szerokiej klasy zagadnień permutacyjnych, których przykładem są TSP (zagadnienie komiwojażera), czy rozważane zagadnienie testowe QAP (kwadratowe zagadnienie przydziału) - należące do NP-trudnych problemów optymalizacji dyskretnej. Zastosowanym algorytmem rojowym jest algorytm pszczeli, ale powyższe podejście może być również wykorzystane w algorytmach mrówkowych. Przedstawione wyniki badań eksperymentalnych dla standardowych zagadnień testowych zaczerpniętych z biblioteki QAPLIB wskazują na wysoką efektywność zaproponowanej metody.

EN

This paper investigates a new advanced swarm algorithm for optimization of permutation problems. The introduction in algorithms the expected value of objective function allows effective evaluation of quality of partially fixed solutions. The parameter can be used as auxiliary criterion for selection and construction of new solutions, increasing the effectiveness of designed algorithms. The experiments were performed for standard test problems of quadratic assignment problems (QAP).

Słowa kluczowe

PL

kwadratowe zagadnienie przydziału; QAP; metody przybliżone; algorytmy rojowe; algorytm pszczół; warunkowa wartość oczekiwana funkcji celu

EN

swarm algorithm; approximate algorithms; conditional expected value of objective function; quadratic assignment problem

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2009
• Tom: T. 13, z. 2
• Strony: 247--255
• Opis fizyczny: Bibliogr. 8 poz., wykr., tab.

Twórcy

autor

Filipowicz B.

• Katedra Automatyki, Akademia Górniczo-Hutnicza w Krakowie

autor

Chmiel W.

• Katedra Automatyki, Akademia Górniczo-Hutnicza w Krakowie

autor

Kadłuczka P.

• Katedra Automatyki, Akademia Górniczo-Hutnicza w Krakowie

Bibliografia

• [1] Burkard R.E., Karisch S.E., Rendl F., QAPLIB-A Quadratic Assignment Problem Library. European Journal of Operational Research, 55, 1991, 115-119.
• [2] Chmiel W., Kadłuczka P., Jedrusik S., Efektywność algorytmu ewolucyjnego wykorzystującego mechanizm różnicowania. Zeszyty Naukowe Politechniki Śląskiej, seria: AUTOMATYKA, zeszyt 143, 33-44, Wydawnictwo Naukowo-Dydaktyczne Politechniki Śląskiej, Gliwice 2006.
• [3] Chmiel W., Algorytmy ewolucyjne w optymalizacji przydziału zadań z kwadratową funkcją celu. AGH, Kraków 2004.
• [4] Eberhart R., Shi Y., Kenedy J., Swarm Intelligence. Morgan Kaufman, San Francisco 2001.
• [5] Filipowicz В., „Algorytm pszczeli", praca zespołowa pod kierunkiem prof В. Filipowicza. LBOiS, Katedra Automatyki AGH, Kraków 2008 (niepublikowana).
• [6] Filipowicz В., Wala K., Algorytmy optymalizacji kwadratowego zagadnienia przydziału. Kwartalnik Elektrotechnika, z. 1, Wydawnictwo AGH, Kraków 1992.
• [7] Kadłuczka P., Chmiel W., Zastosowanie własności zagadnienia QAP w konstrukcji algorytmów ewolucyjnych. AGH, Kraków 2004, 112-120.
• [8] Pham D.T., Ghanbarzadeh A., Koc E., Otri S., Rahim S., Zaidi M., The Bees Algorithm - A Novel Tool for Complex Optimisation Problems. Technical Note, Manufacturing Engineering Centre, Cardiff University, UK, 2005.