Methods of using the Quadratic Assignment Problem solution

• Autorzy: Kudelska I.

Warianty tytułu

PL

Metody wykorzystywania rozwiązania Quadratic Assignment Problem

• Języki publikacji: EN

Abstrakty

EN

Background: Quadratic assignment problem (QAP) is one of the most interesting of combinatorial optimization. Was presented by Koopman and Beckamanna in 1957, as a mathematical model of the location of indivisible tasks. This problem belongs to the class NP-hard issues. This forces the application to the solution already approximate methods for tasks with a small size (over 30). Even though it is much harder than other combinatorial optimization problems, it enjoys wide interest because it models the important class of decision problems. Material and methods: The discussion was an artificial intelligence tool that allowed to solve the problem QAP, among others are: genetic algorithms, Tabu Search, Branch and Bound. Results and conclusions: QAP did not arise directly as a model for certain actions, but he found its application in many areas. Examples of applications of the problem is: arrangement of buildings on the campus of the university, layout design of electronic components in systems with large scale integration (VLSI), design a hospital, arrangement of keys on the keyboard.

PL

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

EN

QAP; genetic algorithms; Branch and Bound; tabu search

PL

QAP; problem kwadratowego przydziału; algorytmy genetyczne; wyżarzanie symulowane; algorytm tabu search

• Wydawca: Wyższa Szkoła Logistyki
• Czasopismo: LogForum
• Rocznik: 2012
• Tom: Vol. 8, no. 3
• Strony: 177--189
• Opis fizyczny: Bibliogr. 33 poz., rys.

Twórcy

autor

Kudelska I.

• Institute of Engineering Management, Poznan University of Technology, Strzelecka 11 St., 60-966 Poznan, Poland

Bibliografia

• Anderson P., 2002, Introduction to Genetic Algorithms, Rochester Institute of Technology, Lecture, December 15
• Arabas J., 2001, Wykłady z algorytmów ewolucyjnych [Lectures on evolutionary algorithms], WNT, Warszawa
• Bartolomei-Suárez S., Egbelu Pius J., 2000, Quadratic assignment problem QAP with adaptable material handling, International Journal of Production Research, Vol. 38, No. 4, Taylor & Francis, pp 855-873
• Burkard R., Çela E., Karisch S. E., Rendl F., 2006, QAPLIB - A Quadratic Assignment Problem Library, http://www.seas.upenn.edu/qaplib/ access: 19.07.2011r.
• Burkard R., Dell'Amico M., Martello S., 2009, Assignment Problems, Society for Industrial and Applied Mathematics, Philadelphia
• Çela E., 1998, The Quadratic Assignment Problem Theory and Algorithms, Kluwer Academic Publishers, Boston/London
• Christofides Nicos, Benavent Enrique, 1989, An Exact Algorithm for the Quadratic Assignment Problem on a tree, Operations Research, Vol. 37, No. 5, September-October
• Commander C. W., 2005, A Survey of the Quadratic Assignment Problem, with Applications, Morehead Electronic Journal of Applicable Mathematics, Issue 4
• Cytowski J., 1996, Algorytmy genetyczne. Podstawy i zastosowania. Problemy współczesnej nauki. Teoria i zastosowania[Genetic algorithms. Fundamentals and applications. The problem of modern science. Theory and applications], Akademicka Oficyna Wydawnicza PLJ, Warszawa
• Geoffrion A. M., Graves G. W., 1976, Scheduling Parallel Production Lines with Changeover Costs : Practical Application of a Quadratic Assignment / LP Approach, Operations Research, Vol. 24, No. 4, July-August
• Gilmore P.C., 1962, Optimal and suboptimal algorithms for the quadratic assignment problem, SIAM Journal on Applied Mathematics 10, pp. 305-313
• Glover F., Laguna E., Taillard E., de Werra D., (eds.), 1993, Tabu search, Annals of Operations Research 41
• Goldberg D. E., 2003, Algorytmy genetyczne i ich zastosowania [Genetic algorithms and their applications], Wydawnictwa Naukowo Techniczne, Warszawa
• Haupt R. L., Haupt S. E., 2004, Practical Genetic Algorithms, John Wiley&Sons, New Jersey
• James T., Rego C., Glover F., 2009, Multistart Tabu Search and Diversification Strategies for the Quadratic Assignment Problem, IEEE Transactions on Systems, MAN, and Cybernetics, part A, Systems and Humans, Vol. 39, No 3
• Ji P., Yongzhong Wu, Haozhao Liu, 2006, A Solution Method for the Quadratic Assignment Problem (QAP), The Sixth International Symposium on Operations Research and Its Applications (ISORA '06), pp. 106-117
• Juszkiewicz M., 2010, Zastosowanie algorytmu pszczelego w rozwiązaniu zagadnienia kwadratowego przydziału[The use of bees algorithm to solve quadratic assignment problems], Kraków
• Kirkpatrick S., Gelatt C., Vecchi M., 1983, Optimization by simulated annealing, [in:] Science, 220, p. 671-680
• Knosala R., 2002, Zastosowania metod sztucznej inteligencji w inżynierii produkcji [Applications of artificial intelligence in manufacturing engineering], Wydawnictwa Naukowo Techniczne, Warszawa.
• Komosiński M., 2010, Optymalizacja: przeszukiwanie tabu [Optimization: Tabu Search], http://www.cs.put.poznan.pl/mkomosinski, access: 19.06.2011 r.
• Łęski J., 2008, Systemy neuronowo rozmyte [Neuro fuzzy systems], Wydawnictwa Naukowo Techniczne, Warszawa
• Metropolis N., Rosenbluth A. W., Rosenbluth N. M., Teller A. H., Teller E., 1953, Equation of state calculations by fast computing machines, [in:] Journal of Chemical Physics, 21 (6), p. 1087-1092
• Michalewicz Zb., 1996, Algorytmy genetyczne + struktury danych = programy ewolucyjne [Genetic Algorithms + Data Structures = Programs Evolutionary], Wydawnictwa Naukowo Techniczne, Warszawa
• Misevicius A., 2005, A Tabu Search Algorithm for the Quadratic Assignment Problem, Computational Optimization and Applications 30, pp. 96-111
• Morin T. L., Marsten R. E., 1976, Branch and Bound Strategies for Dynamic Programming, Operations Research, Vol. 24, No. 4, July-August
• Povh J., 2008, Assignment Problems in Logistics, Logistics & Sustainable Transport, Vol. 1, Issue 3
• Rutkowska D., Piliński M., Rutkowski L., 1997, Sieci neuronowe, algorytmy genetyczne i systemy rozmyte [Neural Networks, Genetic Algorithms and fuzzy systems], PWN, Warszawa
• Rutkowski L., 2006, Metody i techniki sztucznej inteligencji [Methods and techniques of artificial intelligence], Wydawnictwo Naukowe PWN, Warszawa
• Sarker R., Newton C., 2002, A genetic algorithm for solving economic lot size scheduling problem, Computers and Industrial Engineering 42, p. 189-198
• Stützle T., 2006, Iterative local search for the quadratic assignment problem, Eur. J. Operations Research 174, pp. 1519-1539
• Tseng L., Liang S., 2006, A hybrid metaheuristic for the quadratic assignment problem, Comp. Opt. Appl. 34, pp. 85-113
• Witczak E., 2010, Zastosowanie algorytmów poszukiwania z tabu do optymalizacji układania planu zajęć [Application of tabu search algorithms for optimization scheduling], [in:] Studia i Materiały Informatyki Stosowanej [Studies and applied informatics materials], tom 2, nr 2, Bydgoszcz, p. 59-66
• Zhu W., Curry J., Marquez A., 2010, SIMD Tabu Search for the Qauadratic Assignment Problem with graphics hardware acceleration, International Journal of Production Research, Vol. 48, No. 4, pp. 1035-1047.