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

An Adaptive Filtered Local Search Algorithm for the Maximum Clique Problem

提出了一种求解最大团问题的自适应过滤局部搜索算法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.