Abstract A twostage tabu search algorithm based on rough set theory is proposed for combinatorial optimization problems which are represented by TSP. For most of the adaptive tabu search algorithms, the balance between intensification and diversification is achieved by tuning tabu search parameters dynamically. Unlike them, a twostage search strategy is used in the proposed approach. The aim of the first stage is diversification. In this stage, the search area is stimulated to move away from the initial solution, and the whole solution space is explored to a certain degree. Then, based on the solutions obtained in diversification, a promising area decision table is constructed and the corresponding promising area is found. The goal of the second stage is intensification. In this stage, the search procedure begins with the best solution which contains the promising area. In the search procedure, the selection of the new current solution is limited so as to utilize the useful information obtained in the first stage. The proposed algorithm is tested by TSP benchmark problems. The results show that it is feasible and effective.
[1] Glover F. Tabu Search-Part I. ORSA Journal on Computing, 1989, 1(3): 190206 [2] Glover F. Tabu Search-Part II. ORSA Journal on Computing, 1990, 2(1): 432 [3] Montemanni R, Moon J N J, Smith D H. An Improved Tabu Search Algorithm for the FixedSpectrum FrequencyAssignment Problem. IEEE Trans on Vehicular Technology, 2003, 52(4): 891901 [4] Kalinli A, Karaboga D. Training Recurrent Neural Networks by Using Parallel Tabu Search Algorithm Based on Crossover Operation. Engineering Applications of Artificial Intelligence, 2004, 17(5): 529542 [5] Chelouah R, Siarry P. Tabu Search Applied to Global Optimization. European Journal of Operational Research, 2000,123(2): 256270 [6] Ferland J A, Ichoua S, Lavoie A, et al. Scheduling Using Tabu Search with Intensification and Diversification. Computers and Operations Research, 2001, 28 (11): 10751092 [7] Michel G, Gilbert L, Frederic S. A Tabu Search Heuristic for the Undirected Selective Traveling Salesman Problem. European Journal of Operation Research, 1998, 106(1): 539545 [8] He Yi, Liu Guangyuan, Qiu Yuhui. A New Adaptive Search Strategy of Intensification and Diversification in Tabu Search. Journal of Computer Research and Development, 2004, 41(1): 162166 (in Chinese) (贺 一,刘光远,邱玉辉. Tabu Search中集中性和多样性的自适应搜索策略.计算机研究与发展, 2004, 41(1): 162166) [9] Pawlak Z, GrzymalaBusse J, Slowinski R, et al. Rough Sets. Communication of the ACM, 1995, 38(11): 8995 [10] Pawlak Z. Rough Sets: Theoretical Aspect of Reasoning about Data. Dordrecht, Netherlands: Kluwer Academic Publishers, 1991 [11] Wang Guoyin. Rough Set Theory and Knowledge Acquisition. Xi’an, China: Xi’an Jiaotong University Press, 2001 (in Chinese) (王国胤. Rough集理论与知识获取.西安:西安交通大学出版社, 2001) [12] Higgins A J. A Dynamic Tabu Search for LargeScale Generalised Assignment Problems. Computers and Operations Research, 2001, 28(10): 10391048 [13] Grabowskia J, Wodeckib M. A Very Fast Tabu Search Algorithm for the Permutation Flow Shop Problem with Makespan Criterion. Computers and Operations Research, 2004, 31(11): 18911909 [14] Wong S K M, Ziarko W. On Optimal Decision Rules in Decision Table. Bulletin of Polish Academy of Science, 1985, 33(11/12): 693696 [15] Jelonek J, Krowiec K, Slowinski R. Rough Set Reduction of Attributes and Their Domains for Neural Networks. Computational Intelligence, 1995, 11(2): 339347 [16] Liu Shaohui, Sheng Qiujian, Wu Bin, et al. Research on Efficient Algorithms for Rough Set Methods. Chinese Journal of Computers, 2003, 26(5): 524529 (in Chinese) (刘少辉,盛秋戬,吴 斌,等.Rough集高效算法研究.计算机学报, 2003, 26(5): 524529) [17] Wang Jue, Wang Ju. Reduction Algorithms Based on Discernibility Matrix: The Ordered Attributes Method. Journal of Computer Science and Technology, 2001,16(6): 489504 [18] Wang Guoyin, Yu Hong, Yang Dachun. Decision Table Reduction Based on Conditional Information Entropy. Chinese Journal of Computers, 2002, 25(7): 759766 (in Chinese) (王国胤,于 洪,杨大春.基于条件信息熵的决策表约简.计算机学报, 2002, 25(7): 759766) [19] Han Jianchao, Hu Xiaohua, Lin T Y, et al. A New Computation Model for Rough Set Theory Based on Database Systems // Proc of the 5th International Conference on Data Warehousing and Knowledge Discovery. Prague, Czechoslovakia, 2003: 381390 [20] Wang Ling. Intelligent Optimization Algorithms with Applications. Beijing, China: Tsinghua University Press, 2001 (in Chinese) (王 凌.智能优化算法及其应用.北京:清华大学出版社, 2001) [21] Demirhan M, Ozdamar L. A Note on the Use of a Fuzzy Approach in Adaptive Partitioning Algorithms for Global Optimization. IEEE Trans on Fuzzy Systems, 1999, 7(4): 468475 [22] Bazan J G, Skowron A, Synak P. Dynamic Reducts as a Tool for Extracting Laws from Decision Tables // Ras Z W, Zemankiva M, eds. Methodologies for Intelligent Systems. Berlin, Germany: SpringerVerlag, 1994: 346355 [23] Li Fan, Liu Qihe, Ye Mao, et al. Approaches to Knowledge Reductions in Inconsistent Decision Tables. Control and Decision, 2006, 21(8): 857 862 (in Chinese) (李 凡,刘启和,叶 茂,等.不一致决策表的知识约简方法研究.控制与决策, 2006, 21(8): 857 862) [24] Li Fan, Liu Qihe, Yang Guowei. A New Crossover Operator Based on the Rough Set Theory for Genetic Algorithms // Proc of the 4th International Conference on Machine Learning and Cybernetics. Guangzhou, China, 2005, Ⅴ: 29072912
2007, Vol. 20 
