BazEkon - Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie

BazEkon home page

Meny główne

Autor
Kudelska Izabela (Poznan University of Technology, Poland)
Tytuł
Methods of Using the Quadratic Assignment Problem Solution
Metody wykorzystywania rozwiązania Quadratic Assignment Problem
Źródło
LogForum, 2012, vol. 8, nr 3, s. 177-189, rys., bibliogr. 33 poz.
Słowa kluczowe
Algorytmy genetyczne, Algorytmy, Modele matematyczne
Genetic algorithms, Algorithms, Mathematical models
Uwagi
summ., streszcz., Zfsg.
Abstrakt
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. (abstrakt oryginalny)

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. (original abstract)
Dostępne w
Biblioteka Główna Uniwersytetu Ekonomicznego w Poznaniu
Pełny tekst
Pokaż
Bibliografia
Pokaż
  1. Anderson P., 2002, Introduction to Genetic Algorithms, Rochester Institute of Technology, Lecture, December 15
  2. Arabas J., 2001, Wykłady z algorytmów ewolucyjnych [Lectures on evolutionary algorithms], WNT, Warszawa
  3. 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
  4. 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.
  5. Burkard R., Dell'Amico M., Martello S., 2009, Assignment Problems, Society for Industrial and Applied Mathematics, Philadelphia
  6. Çela E., 1998, The Quadratic Assignment Problem Theory and Algorithms, Kluwer Academic Publishers, Boston/London
  7. Christofides Nicos, Benavent Enrique, 1989, An Exact Algorithm for the Quadratic Assignment Problem on a tree, Operations Research, Vol. 37, No. 5, September - October
  8. Commander C. W., 2005, A Survey of the Quadratic Assignment Problem, with Applications, Morehead Electronic Journal of Applicable Mathematics, Issue 4
  9. 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
  10. 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
  11. Gilmore P.C., 1962, Optimal and suboptimal algorithms for the quadratic assignment problem, SIAM Journal on Applied Mathematics 10, pp. 305 - 313
  12. Glover F., Laguna E., Taillard E., de Werra D., (eds.), 1993, Tabu search, Annals of Operations Research 41
  13. Goldberg D. E., 2003, Algorytmy genetyczne i ich zastosowania [Genetic algorithms and their applications], Wydawnictwa Naukowo Techniczne, Warszawa
  14. Haupt R. L., Haupt S. E., 2004, Practical Genetic Algorithms, John Wiley&Sons, New Jersey
  15. 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
  16. 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
  17. 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
  18. Kirkpatrick S., Gelatt C., Vecchi M., 1983, Optimization by simulated annealing, [in:] Science, 220, p. 671 - 680
  19. Knosala R., 2002, Zastosowania metod sztucznej inteligencji w inżynierii produkcji [Applications of artificial intelligence in manufacturing engineering], Wydawnictwa Naukowo Techniczne, Warszawa.
  20. Komosiński M., 2010, Optymalizacja: przeszukiwanie tabu [Optimization: Tabu Search], http://www.cs.put.poznan.pl/mkomosinski, access: 19.06.2011 r.
  21. Łęski J., 2008, Systemy neuronowo rozmyte [Neuro fuzzy systems], Wydawnictwa Naukowo Techniczne, Warszawa
  22. 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
  23. Michalewicz Zb., 1996, Algorytmy genetyczne + struktury danych = programy ewolucyjne [Genetic Algorithms + Data Structures = Programs Evolutionary], Wydawnictwa Naukowo Techniczne, Warszawa
  24. Misevicius A., 2005, A Tabu Search Algorithm for the Quadratic Assignment Problem, Computational Optimization and Applications 30, pp. 96 - 111
  25. Morin T. L., Marsten R. E., 1976, Branch and Bound Strategies for Dynamic Programming, Operations Research, Vol. 24, No. 4, July - August
  26. Povh J., 2008, Assignment Problems in Logistics, Logistics & Sustainable Transport, Vol. 1, Issue 3
  27. Rutkowska D., Piliński M., Rutkowski L., 1997, Sieci neuronowe, algorytmy genetyczne i systemy rozmyte [Neural Networks, Genetic Algorithms and fuzzy systems], PWN, Warszawa
  28. Rutkowski L., 2006, Metody i techniki sztucznej inteligencji [Methods and techniques of artificial intelligence], Wydawnictwo Naukowe PWN, Warszawa
  29. Sarker R., Newton C., 2002, A genetic algorithm for solving economic lot size scheduling problem, Computers and Industrial Engineering 42, p. 189 - 198
  30. Stützle T., 2006, Iterative local search for the quadratic assignment problem, Eur. J. Operations Research 174, pp. 1519 - 1539
  31. Tseng L., Liang S., 2006, A hybrid metaheuristic for the quadratic assignment problem, Comp. Opt. Appl. 34, pp. 85 - 113
  32. 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
  33. 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.
Cytowane przez
Pokaż
ISSN
1895-2038
Język
eng
Udostępnij na Facebooku Udostępnij na Twitterze Udostępnij na Google+ Udostępnij na Pinterest Udostępnij na LinkedIn Wyślij znajomemu