Parametry charakteryzujące własności przestrzeni rozwiązań dla problemu QAP

• Autorzy: Chmiel W.

Warianty tytułu

EN

Parameters describing properties of solution space for quadratic assignment problem

• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

problem QAP; kwadratowy problem przypisania; QAP

EN

QAP; quadratic assignment problem

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2003
• Tom: T. 7, z. 3
• Strony: 637--648
• Opis fizyczny: Bibliogr. 28 poz., tab.

Twórcy

autor

Chmiel W.

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

Bibliografia

• [1] Angel E., Zissimopoulos V.: Autocorrelation coefficient for the graph bipartitioning problem. Theoretical Computer Science, vol. 191, 1998, 229-243
• [2] Angel E., Zissimopoulos V.: Towards to classification of combinatorial optimization problems relatively to their difficulty for generalized local search algorithm. Technical Report 1112, LRI, Universite de Paris-Sud, 1997
• [3] Angel E., Zissimopoulos V.: On the landscape ruggedness of the Quadratic Assignment Problem. Theoretical Computer Science, vol. 263, nr 1, 2, 2001, 159-172
• [4] Alon, N., Spencer J.: The probabilistic method. New York, Willey 1992
• [5] Bachelet V., Preux P., Talbi E-G.: Parallel hybrid meta-heuristics: Application to the QAP. Technical Report LIL-96-2, LIFL, Universite des Sciences et Technologies de Lille, 1996, Proc. Parallel Optimization Colloquium, Versailles
• [6] Block T.E.: On the complexity of facilities layout problems. Management Science, 25, 280, 1979
• [7] Burkard R.E., Stratmann, K.H.: Numerical investigations on quadratic assignment problem. Naval Research Logistics Quarterly, 25, 1978, 129-148
• [8] Burkard R.E., Karisch S.E., Rendl F.: QAPLIB-A Quadratic Assignment Problem Library. European Journal of Operational Resarch, 55, 1991,115-119
• [9] Chmiel W.: Algorytm ewolucyjny z ograniczonym wyborem operatorów genetycznych. Zeszyty Naukowe Politechniki Śląskiej, z. 125, 1998, 125-134
• [10] Chmiel W.: Algorytm Tabu Search ze zmiennym czasem pamięci krótkoterminowej. Zeszyty Naukowe Politechniki Śląskiej, Automatyka, z. 136, Gliwice 2002
• [11] Deisenroth M.P., Apple J. M.: A computerized Plant layouts analysis and evaluation techniques. Technical Paper, Annual AIIE Conference, Norcross, GA, 1972
• [12] Filipowicz B., Wala K.: Algorytmy optymalizacji kwadratowego zagadnienia przydziału. Kwartalnik AGH Elektrotechnka, z. 1, 1992
• [13] Finkę G., Burkard R.E, Rendl F.: Quadratic assignments problems. Annals of Discrete Mathematics. vol. 31, North-Holland, 1987, 61-82
• [14] Francis L.R., White J.A.: Facility layout and location: An analytical approach. Englewood Hall, NJ, Pretence-Hall 1974
• [15] Glover F.: Tabu Search. Part I. ORSA Journal of Computing 1, 1989, 190-206
• [16] Glover F.: Tabu Search. Part II. ORSA Journal of Computing, 2, 1990, 4-32
• [17] Gutin G., Yeo A.: Polynomial approximation algorithms for TSP and the QAP with factorial domination number
• [18] Holland J.: Adaptation in natural and artificial systems. Univ. of Michigan Press, Ann Arbor, MI, 1975
• [19] Herroelen W, Van Gils A.: On the use flow dominance in complexity measures for facility layout problems. International Journal of Production Research, 23(1), 1985, 97-108
• [20] Mautor T., Roucairol C.: Difficulties of exact methods for solving the quadratic assignment problem. DIMACS Workshop (Series in Discrete Mathematics and Theoretical Computer Science), vol. 16, 1993, 263-274
• [21] Merz R, Freisleben B.: A genetic local search approach to the quadratic assignment problem. Proceedings of the 17’th International Conference on Genetic Algorithms (ICGA’97), East Lansing, USA, 1997
• [22] Michalewicz Z.: Genetic algorithms + data structures = evolution programs. Berlin, Springer- -Verlag 1992
• [23] Passman D.S.: Permutation Group. NY, Benjamin Inc. 1968, 36
• [24] Stadler P.F.: Landscapes and their correlations functions. Technical Report 95-07-067, Santa Fe Institute, Santa Fe, NM, 1995
• [25] Raghavan P: Probabilistic construction of deterministic algorithms: approximating packing integer programs. J. Computer and System 37, 1988, 130-143
• [26] Tailard E.D.: Comparison of iterative searches for the quadratic assignment problem. Location Science, 3, 1995
• [27] Wala K., Chmiel W.: Evolution Algorithm for Quadratic Assignment Problem. University of Mining and Metallurgy Press, Elektrotechnika, 1,1, 1997, 409-414
• [28] Weinberger E.D.: Correlated and uncorrelated fitness landscapes and how to tell the difference. Biological Cybernetics, 63, 1990, 325-336