一种基于Rough集理论的两阶段禁忌搜索算法  

A Two-Stage Tabu Search Algorithm Based on Rough Set Theory

作　　者：李凡[1] 刘启和[1] 杨国纬[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,成都610054

出　　处：《模式识别与人工智能》2007年第4期478-484,共7页Pattern Recognition and Artificial Intelligence

基　　金：国家863计划资助项目(No.2005AA114030)

摘　　要：针对以旅行商问题(TSP)为代表的组合优化问题提出一种基于 Rough 集理论的两阶段禁忌搜索算法.该算法没有采用多数自适应禁忌搜索算法所用的动态调整禁忌搜索参数的方式平衡集中性搜索和多样性搜索,而是采用两阶段搜索策略.第一阶段着眼于多样性搜索.通过激励搜索过程远离起点,对解空间进行相当程度的探索,在此基础上构造希望区域决策表,继而获得希望区域.第二阶段着眼于集中性搜索.以包含希望区域的最佳解作为起点进行集中性搜索.在选择当前解时,利用多样性搜索得到的路径信息进行有条件的限制.TSP 基准问题的计算结果表明该算法是可行有效的.A two-stage 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 two-stage 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.

关 键 词：禁忌搜索(TS) ROUGH集 集中性 多样性 旅行商问题(TSP) 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]