信息与控制2011，Vol.40Issue(4)：445-451,7.DOI:10.3724/SP.J.1219.2011.00445
一种求解最大团问题的自适应过滤局部搜索算法
An Adaptive Filtered Local Search Algorithm for the Maximum Clique Problem
张雁 1黄永宣 2魏明海1
作者信息
- 1. 西安交通大学系统工程研究所,陕西西安710049
- 2. 陕西电力信通有限公司,陕西西安710048
- 折叠
摘要
Abstract
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.关键词
局部搜索算法/最大团问题/漂移分析/参数设置Key words
local search algorithm/ maximum clique problem/ drift analysis/ parameter setting分类
数学引用本文复制引用
张雁,黄永宣,魏明海..一种求解最大团问题的自适应过滤局部搜索算法[J].信息与控制,2011,40(4):445-451,7.
