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-solution based 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.