A Time-Efficient Method for Metaheuristics: Using Tabu Search and Tabu GA as a Case
This paper presents an efficient algorithm for reducing the computation time of metaheuristics. The proposed algorithm is motivated by the observation that some of the subsolutions of metaheuristics will eventually end up being part of the final solutions. As such, if they can be saved away as soon as they were found, then most, if not all, of the redundant computations can be eliminated to save the computation time of metaheuristics. To evaluate the performance of the proposed algorithm, we use it to cut the computation time of a single-solutionbased algorithm called Tabu Search (TS) and a population-based algorithm called Tabu Genetic Algorithm (Tabu GA) in solving the traveling salesman problem (TSP). The test benchmarks for the TSP problem are from 198 up to 1,655 cities. Our experimental results indicate that the proposed algorithm can reduce the computation time from 65.72％ up to about 94.25％ compared to those of TS and Tabu GA alone.
Metaheuristics Traveling Salesman Problem Tabu Search
Chun-Wei Tsai Shih-Pang Tseng Ming-Chao Chiang Chu-Sing Yang
Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan, Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan, Department of Electrical Engineering, National Cheng Kung University, Tainan, Taiwan, R.O.C.
国际会议
2009 Ninth International Conference on Hybrid Intelligent Systems(第九届混合智能系统国际会议 HIS 2009)
沈阳
英文
1-6
2009-08-12（万方平台首次上网日期，不代表论文的发表时间）