Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/36580
標題: A hybrid metaheuristic for the quadratic assignment problem
作者: Tseng, L.Y.
曾怜玉
Liang, S.C.
關鍵字: ant colony optimization;genetic algorithm;local search;quadratic;assignment problem;genetic algorithm;ant colonies;optimization;search;system;qap
Project: Computational Optimization and Applications
期刊/報告no:: Computational Optimization and Applications, Volume 34, Issue 1, Page(s) 85-113.
摘要: 
The quadratic assignment problem (QAP) is known to be NP-hard. We propose a hybrid metaheuristic called ANGEL to solve QAP. ANGEL combines the ant colony optimization (ACO), the genetic algorithm (GA) and a local search method (LS). There are two major phases in ANGEL, namely ACO phase and GA phase. Instead of starting from a population that consists of randomly generated chromosomes, GA has an initial population constructed by ACO in order to provide a good start. Pheromone acts as a feedback mechanism from GA phase to ACO phase. When GA phase reaches the termination criterion, control is transferred back to ACO phase. Then ACO utilizes pheromone updated by GA phase to explore solution space and produces a promising population for the next run of GA phase. The local search method is applied to improve the solutions obtained by ACO and GA. We also propose a new concept called the eugenic strategy intended to guide the genetic algorithm to evolve toward a better direction. We report the results of a comprehensive testing of ANGEL in solving QAP. Over a hundred instances of QAP benchmarks were tested and the results show that ANGEL is able to obtain the optimal solution with a high success rate of 90%.
URI: http://hdl.handle.net/11455/36580
ISSN: 0926-6003
DOI: 10.1007/s10589-005-3069-9
Appears in Collections:資訊網路與多媒體研究所

Show full item record
 

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.