Extensive Testing of a Hybrid Genetic Algorithm for Solving Quadratic Assignment Problems |
| |
Authors: | Meng-Hiot Lim Yu Yuan Sigeru Omatu |
| |
Institution: | (1) School of Electrical & Electronic Engineering, Nanyang Technological University, Block S1, Singapore, 639798;(2) Department of Computer & Systems Science, College of Engineering, Osaka Prefecture University, Sakai, Osaka, 593, Japan |
| |
Abstract: | A robust search algorithm should ideally exhibit reasonable performance on a diverse and varied set of problems. In an earlier paper Lim et al. (Computational Optimization and Applications, vol. 15, no. 3, 2000), we outlined a class of hybrid genetic algorithms based on the k-gene exchange local search for solving the quadratic assignment problem (QAP). We follow up on our development of the algorithms by reporting in this paper the results of comprehensive testing of the hybrid genetic algorithms (GA) in solving QAP. Over a hundred instances of QAP benchmarks were tested using a standard set of parameters setting and the results are presented along with the results obtained using simple GA for comparisons. Results of our testing on all the benchmarks show that the hybrid GA can obtain good quality solutions of within 2.5% above the best-known solution for 98% of the instances of QAP benchmarks tested. The computation time is also reasonable. For all the instances tested, all except for one require computation time not exceeding one hour. The results will serve as a useful baseline for performance comparison against other algorithms using the QAP benchmarks as a basis for testing. |
| |
Keywords: | genetic algorithms quadratic assignment combinatorial optimization hybrid genetic search k-gene exchange |
本文献已被 SpringerLink 等数据库收录! |
|