Szczegóły publikacji
Opis bibliograficzny
Parametry charakteryzujące własności przestrzeni rozwiązań dla problemu QAP — Parameters describing properties of solution space for Quadratic Assignment Problem / Wojciech CHMIEL // Automatyka : półrocznik Akademii Górniczo-Hutniczej im. Stanisława Staszica w Krakowie ; ISSN 1429-3447. — 2003 — t. 7 z. 3, s. 637–648. — Bibliogr. s. 647–648, Streszcz., Summ.
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 15307 |
|---|---|
| Data dodania do BaDAP | 2004-02-04 |
| Rok publikacji | 2003 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Automatyka/Automatics |
Abstract
Quadratic Assignment Problem (QAP) generalizes several essential combinatorial problems: TSP, Generalized Graph Partitioning (GGP), Maximal Clique Problem (MCP), and many others. Because QAP belongs to NP-hard combinatorial problems, exact solution is possible only for small size (n < 25) QAP problems. To solve QAP problem of large size different kinds of approximate algorithms are used - among them the evolutionary algorithms based on evolution laws. Because of a great variety of properties of solution space, the quality of solution obtained with an evolutionary algorithm is different for various instances of QAP. In this paper we present methods of estimating properties of solution space of QAP. The analysis of those properties allows us to establish a set of optimal parameters of the implemented evolutionary algorithm. This task was realized on the basis of experimental analysis of our approximate algorithm. Examples from Quadratic Assignment Problem Library (called QAPLIB-A) were used in test cases.
Streszczenie
Kwadratowy problem przypisania (Quadratic Assignment Problem) generalizuje wiele istotnych zagadnień kombinatorycznych. Wśród nich można wymienić takie problemy jak problem komiwojażera (TSP), uogólniony problem podziału grafu (GGP), problem maksymalnej kliki (MCP) w grafie oraz wiele innych. Ze względu na fakt, że problem ten należy do klasy problemów NP-trudnych, otrzymanie dokładnego rozwiązania jest możliwe jedynie dla instancji o niewielkich rozmiarach (n < 25). Do rozwiązywania problemu QAP o większych rozmiarach stosuje się różnego rodzaju algorytmy przybliżone - wśród nich także algorytmy ewolucyjne. Ze względu ma duże zróżnicowanie własności przestrzeni rozwiązań, dla różnych instancji problemu QAP, różna jest jakość uzyskiwanych rozwiązań w oparciu o zastosowany algorytm ewolucyjny. W pracy przedstawiono metody oceny własności przestrzeni rozwiązań problemu QAP oraz próbę określenia na ich podstawie optymalnych wartości parametrów sterujących algorytmem ewolucyjnym. Zadanie to zrealizowano w oparciu o eksperymentalne wyniki uzyskane dla zaimplementowanego algorytmu ewolucyjnego. Dla testów wykorzystano zagadnienia testowe z biblioteki QAPLIB-A.