Wykorzystanie własności zagadnienia QAP w konstrukcji algorytmów ewolucyjnych

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

Warianty tytułu

EN

Exploitation of properties of QAP problem in evolutionary algorithms construction

• Języki publikacji: PL

Abstrakty

PL

Artykuł prezentuje wyniki prac związanych z implementacją i badaniem efektywności algorytmu ewolucyjnego, wykorzystującego specjalizowane operatory pseudogenetyczne dla kwadratowego zagadnienia przydziału. Operatory te bazują na własnościach przestrzeni rozwiązań, stosując warunkową wartość oczekiwaną funkcji celu rozwiązań częściowo ustalonych. Wprowadzenie do operatorów dodatkowej wiedzy o optymalizowanym problemie umożliwia ukierunkowanie procesu eksploracji przestrzeni rozwiązań w regiony zawierające rozwiązania o wyższej jakości.

EN

The paper presents an approach to an implementation and evaluation of evolutionary algorithm using operators exploiting peculiar properties of QAP problem. They are based on expected conditional value of objective function for partially fixed solutions. The numerical experiments were performed for standard test problems of quadratic assignment problem (QAP) from QAPLIB-A library. We compare the results of algorithms using pseudo-genetic operators which exploit some QAP problem properties with results obtained from algorithms using standard pseudo-genetic operators for permutation problems.

Słowa kluczowe

PL

kwadratowe zagadnienie przydziału; QAP; algorytmy przybliżone; algorytmy ewolucyjne; warunkowa wartość oczekiwana funkcji celu

EN

quadratic assignment problem; QAP; approximate algorithms; evolutionary algorithms; genetic operators; conditional expected value of objective function

• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2007
• Tom: T. 11, z. 1-2
• Strony: 151-160
• Opis fizyczny: Bibliogr. 7 poz., rys., tab.

Twórcy

autor

Kadłuczka, P.

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

autor

Chmiel, W.

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

Bibliografia

• [1] Goldberg D.E.: Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company, 1989; tłum. na jęz. polski: Algorytmy genetyczne i ich zastosowania. WNT, Warszawa 1995
• [2] Michalewicz Z.: Genetic Algorithms + Data Strructures = Evolution Programs. Springer Verlag,1995; tłum. na jęz. polski: Algorytmy genetyczne + struktury danych = programy ewolucyjne, WNT, Warszawa 1996
• [3] Chmiel W.: Algorytmy ewolucyjne w optymalizacji przydziału zadań z kwadratowąfunkcją celu. Kraków, AGH 2005 (Praca doktorska)
• [4] Nissen V.: Evolutionare Algorithmen Darstellung, Beispiele, betriebswirtschaftliche Anwendungs-moglichkeiten. Wiesbaden, Deutscher Universitats Verlag 1994
• [5] Kadłuczka P., Chmiel W.: Efektywność algorytmu ewolucyjnego wykorzystującego warunkową wartość oczekiwaną funkcji celu. Automatyka, AGH, Kraków, 2005, 105-114
• [6] Chmiel W., Kadłuczka P., Jędrusik S.: Efektywność algorytmu ewolucyjnego wykorzystującego mechanizm różnicowania. Zeszyty Naukowe Politechniki Śląskiej, seria: AUTOMATYKA, Gliwice 2006, z. 143, 33-44
• [7] Burkard R.E., Karisch S.E., Rendl F.: QAPLIB-A Quadratic Assignment Problem Library. European Journal of Operational Resarch, 55, 1991, 115