A new genetic representation for quadratic assignment problem

Authors

  • Jozef Kratica Mathematical Institute, Serbian Academy of Sciences and Arts, Belgrade
  • Dušan Tošić Faculty of Mathematics, Belgrade
  • Vladimir Filipović Faculty of Mathematics, Belgrade
  • Đorđe Dugošija Faculty of Mathematics, Belgrade

DOI:

https://doi.org/10.2298/YJOR1102225K

Keywords:

Genetic algorithm, evolutionary computation, combinatorial optimization, quadratic assignment problem

Abstract

In this paper, we propose a new genetic encoding for well known Quadratic Assignment Problem (QAP). The new encoding schemes are implemented with appropriate objective function and modified genetic operators. The numerical experiments were carried out on the standard QAPLIB data sets known from the literature. The presented results show that in all cases proposed genetic algorithm reached known optimal solutions in reasonable time.

References

Abraham, A., Nedjah, N., and Mourelle, L., “Evolutionary computation: From genetic algorithms to genetic programming”, in: Nedjah et al. (eds.) Studies in Computational Intelligence, Springer, (2006) 1-20.

Aleret, R.M., Valls, J., and Fernandez, O., “Evolving generalized Euclidean distances for training RBNN”, Computing and Informatics, 26 (1) (2007) 33-43.

Ben-David, G., and Malah, D., “Bounds on the performance of vector-quantizers under channel errors”, IEEE Transactions on Information Theory, 51 (6) (2005), 2227-2235.

Davendra, D., and Zelinka, I., “Optimization of quadratic assignment problem using self-organising migrating algorithm”, Computing and Informatics, 28 (2) (2009), 169-180.

Djurić, B., Kratica, J., Tošić, D., and Filipović, V., “Solving the maximally balanced connected partition problem in graphs by using genetic algorithm”, Computing and Informatics, 27 (3) (2008), 341-354.

Drezner, Z., “Compounded genetic algorithms for the quadratic assignment problem”, Operations Research Letters, 33 (5) (2005) 475-480.

Drezner, Z., “The extended concentric tabu for the quadratic assignment problem”, European Journal of Operational Research, 160 (2) (2005), 416-422.

Drezner, Z., “Extensive experiments with hybrid genetic algorithms for the solution of the quadratic assignment problem”, Computers and Operations Research, 35 (3) (2008) 717-736.

Duman, E., and Or, I., “The quadratic assignment problem in the context of the printed circuit board assembly process”, Computers and Operations Research, 34 (1) (2007) 163-179.

El-Baz, M.A., “A genetic algorithm for facility layout problems of different manufacturing environments”, Computers and Industrial Engineering, 47 (23) (2004) 233-246.

Filipović, V., “Fine-grained tournament selection operator in genetic algorithms”, Computing and Informatics, 22 (2) (2003) 143-161.

Hani, Y., Amodeo, L., Yalaoui, F., and Chen, H., “Ant colony optimization for solving an industrial layout problem”, European Journal of Operational Research, 183 (2007) 633-642.

Holland, J., Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor, 1975.

James, T., Rego, C., and Glover, F., “A cooperative parallel tabu search algorithm for the quadratic assignment problem”, European Journal of Operational Research, 195 (3) (2009) 810-826.

Khamis, A.M., Girgis, M.R., and Ghiduk, A.S., “Automatic software test data generation for spanning sets coverage using genetic algorithms”, Computing and Informatics, 26 (4) (2007) 383-401.

Koopmans, T. C., and Beckman, M. J., “Assignment problems and the location of economic activities”, Econometrica, 25 (1957) 53-76.

Kratica, J.: “Improving performances of the genetic algorithm by caching”, Computers and Artificial Intelligence, 18, 3 (1999) 271-283.

Kratica, J., Stanimirović, Z., Tošić, D., and Filipović, V., “Two genetic algorithms for solving the uncapacitated single allocation p-hub median problem”, European Journal of Operational Research, 182 (1) (2007) 15-28.

Kratica, J., Kovačević-Vujičić, V., and Čangalović, M., “Computing strong metric dimension of some special classes of graphs by genetic algorithms”, Yugoslav Journal of Operations Research, 18 (2) (2008) 143-151.

Liu, H., Abraham A., and Zhang, J., “A particle swarm approach to quadratic assignment problems”, in: A. Saad et al. (ed.), Advances in Soft Computing, 39, Springer - Verlag, (2007) 213 - 222.

Liu, H., and Abraham, A., “An hybrid fuzzy variable neighborhood particle swarm optimization algorithm for solving quadratic assignment problems”, Journal of Universal Computer Science, 13 (9) (2007) 1309-1331.

Loiola, E.M., de Abreu, N.M.M., Boaventura-Netto, P.O., Hahn, P., and Querido, T., “A survey for the quadratic assignment problem”, European Journal of Operational Research, 176 (2) (2007) 657-690.

Misevicius, A., “A modified simulated annealing algorithm for the quadratic assignment problem”, Informatica, 14 (4) (2003) 497-514.

Misevicius, A., “A tabu search algorithm for the quadratic assignment problem”, Computational Optimization and Applications, 30 (1) (2005), 95-111.

Mitchell, M., Introduction to Genetic Algorithms, MIT Press, Cambridge, Massachusetts, 1999.

Oliveira, C.A.S., Pardalos, P.M., and Resende, M.G.G., “GRASP with path-relinking for the quadratic assignment problem”, Lecture Notes in Computer Science, 3059 (2004) 356-368.

Qahri Saremi, H., Abedin, B., and Meimand Kermani, A., “Website structure improvement: Quadratic assignment problem approach and ant colony meta-heuristic technique”, Applied Mathematics and Computation, 195 (1) (2008) 285-298.

Sahni, S., and Gonzales, T., “P-complete approximation problems”, Journal of the Association for Computing Machinery, 23 (1976) 555-565.

Singh, S.P., and Sharma, R.R.K., “Two-level modified simulated annealing based approach for solving facility layout problem”, International Journal of Production Research, 46 (13) (2008) 3563-3582.

Stutzle, T., “Iterated local search for the quadratic assignment problem”, European Journal of Operational Research, 174 (3) (2006) 1519-1539.

Tao J., Wang N., and Wang X., “Genetic algorithm based recurrent fuzzy neural network modeling of chemical processes”, Journal of Universal Computer Science, 13 (9) (2007) 1332-1343.

Tseng, L.-Yu., and Liang, S.-C., “A hybrid metaheuristic for the quadratic assignment problem”, Computational Optimization and Applications, 34 (1) (2006) 85-113.

Wang, R.L., and Okazaki, K., “Solving facility layout problem using an improved genetic algorithm”, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, E88a (2) (2005) 606-610.

Wess, B., and Zeitlhofer, T., “On the phase coupling problem between data memory layout generation and address pointer assignment”, Lecture Notes in Computer Science, 3199 (2004) 152-166.

Downloads

Published

2011-09-01

Issue

Vol. 21 No. 2 (2011)

Section

Research Articles

License

Copyright (c) 2011 YUJOR

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.