一种基于匹配交叉求解最大团问题的Memetic算法  

A Memetic algorithm based on match-crossover for the maximum clique problem

作　　者：张雁[1,2] 党群[1] 黄永宣[1] 

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

出　　处：《控制与决策》2010年第9期1408-1412,1419,共6页Control and Decision

摘　　要：针对基于适应值的选择交叉机制在优化具有欺骗性的最大团问题中性能退化的问题,提出一种新的基于匹配交叉的Memetic算法.该算法提出交叉匹配度的概念,用来估计两个体交叉所能获得的最佳适应值.通过匹配度的计算对交叉方向的选择进行控制,保证了交叉操作以较大的概率生成新的优良模式.在40个最大团问题标准算例上的测试结果表明,新算法优于目前在最大团问题求解中性能最好的多阶段动态局部搜索算法.Focused on the performance degradation problem of the fitness-based selection-crossover mechanism in solving the hard deceptive maximum clique problem（MCP）, a novel Memetic algorithm based on match-crossover（MC Memetic） is proposed. The concept of matching degree is defined to measure the best accessible fitness in two individuals’ crossover operations. Through the selection strategy based on matching degree, the crossover direction is optimized towards the solution with high matching degree value, which ensures that the new high quality schemes are produced with high probability. Simulation results on 40 benchmark graphs show that the MC Memetic algorithm is superior to the most effective phased local search algorithm in solving the maximum clique problem.

关 键 词：MEMETIC算法 最大团问题 局部搜索 

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