一种求解最大团问题的自适应过滤局部搜索算法  

An Adaptive Filtered Local Search Algorithm for the Maximum Clique Problem

作　　者：张雁[1,2] 黄永宣[1] 魏明海 

机构地区：[1]西安交通大学系统工程研究所,陕西西安710049 [2]陕西电力信通有限公司,陕西西安710048

出　　处：《信息与控制》2011年第4期445-451,共7页Information and Control

摘　　要：提出了一种求解最大团问题的自适应过滤局部搜索算法AF-RLS(adaptive filtered-reactive local search).该算法通过构建独立集约束,优选出有希望的邻域移动方向来提高局部搜索趋向最优解的概率;并在比较分析两种不同逃逸策略的逃逸能力和逃逸代价的基础上,提出了基于问题解空间结构自适应设置局部搜索深度参数的方法.基于漂移分析理论和在37个典型测试算例上的实验结果表明,所提出的AF-RLS算法相比原RLS算法性能有明显改善.An adaptive filtered reactive local search（AF-RLS） algorithm for solving the maximum clique problem（MCP） is proposed.The promising moving direction in the neighborhood is selected out through constructing the independent set constraint,thereby the probability of the local search towards the optimal solution is increased.Furthermore,the adaptive setting method of the local search depth parameter according to the structure of the problem solution space is proposed based on the analysis of the escape ability and costs of two escape strategies.Both the drifting analysis theory and simulation results on 37 classical tests show that the performance of the proposed AF-RLS algorithm is obviously better than that of the RLS（reactive least square） algorithm.

关 键 词：局部搜索算法 最大团问题 漂移分析 参数设置 

分 类 号：O157[理学—数学]