Logforum. 2012. 8(3), artykuł 1, 177-189;
METODY WYKORZYSTYWANIA ROZWIąZANIA QUADRATIC ASSIGNMENT PROBLEM
Izabela Kudelska
Poznan University of Technology, Poznań, Poland
Wstęp: Kwadratowy Problem Przydziału (QAP) jest jednym z najciekawszych zagadnień optymalizacji kombinatorycznej. Został przedstawiony przez Koopmana i Beckamanna w roku 1957, jako matematyczny model lokalizacji niepodzielnych zadań. Problem ten należy do klasy zagadnień NP.-trudnych. Wymusza to stosowanie do jego rozwiązania metod przybliżonych już dla zadań o niewielkim rozmiarze (powyżej 30).
Mimo że jest ono znacznie trudniejsze niż inne zagadnienia optymalizacji kombinatorycznej, to cieszy się powszechnym zainteresowaniem, ponieważ modeluje ważną klasę problemów decyzyjnych.
Metody: Dyskusji poddano narzędzia sztucznej inteligencji, które pozwoliły rozwiązać problem QAP, między innymi są to: algorytmy genetyczne, Tabu Search, Branch and Bound
Wyniki i wnioski: Sam problem bezpośrednio nie powstał jako model pewnych działań, jednak znalazł on swoje zastosowanie w wielu dziedzinach. Przykładowymi zastosowaniami problemu jest: rozmieszczenie budynków na kampusie uczelnianym, projektowanie rozmieszczenia elementów elektronicznych w układach o wielkiej skali integracji (VLSI), projekt szpitala, rozmieszczenie klawiszy na klawiaturze.
Słowa kluczowe: QAP, problem kwadratowego przydziału, algorytm podziału i ograniczeń, algorytmy genetyczne, symulowane wyżarzanie, algorytm Tabu Search
Adobe Acrobat
Abstract in English.
Zusammenfassung in Deutsch.
MLA | Kudelska, Izabela. "Methods of using the quadratic assignment problem solution." Logforum 8.3 (2012): 1. |
APA | Izabela Kudelska (2012). Methods of using the quadratic assignment problem solution. Logforum 8 (3), 1. |
ISO 690 | KUDELSKA, Izabela. Methods of using the quadratic assignment problem solution. Logforum, 2012, 8.3: 1. |