求解最大团问题的均匀设计抽样免疫遗传算法  

Immune Genetic Algorithm Based on Uniform Design Sampling for Solving Maximum Clique Problem

作　　者：周本达[1] 岳芹[1] 陈明华[2] 

机构地区：[1]皖西学院数理系,安徽六安237012 [2]皖西学院计算机科学与技术系,安徽六安237012

出　　处：《计算机工程》2010年第18期229-231,共3页Computer Engineering

摘　　要：针对遗传算法在最大团求解中保持群体多样性能力不足、早熟、耗时长、成功率低等缺陷,依据均匀设计抽样理论对交叉操作进行重新设计,结合免疫机理定义染色体浓度设计克隆选择策略,提出求解最大团问题的均匀设计抽样免疫遗传算法。仿真算例表明,该算法在解的质量、收敛速度等各项指标上均有提高,与DLS-MC、QUALEX等经典搜索算法相比,对部分算例能得到更好解。Aiming at the defects of Genetic Algorithm（GA） for the Maximum Clique Problem（MCP） in the deficiency of keeping population diversity, prematurity, time consuming, low success rate and so on, the crossover operation in GA is redesigned by Uniform Design Sampling（UDS）. Combined with immune mechanism, chromosome concentration is defined and clonal selection strategy is designed, thus an immune GA is given based on UDS for solving the MCP. Simulation examples show that solution quality, convergence rate and other various indices are improved by the new algorithm. The new algorithm is not inferior to such classical search algorithms as DLS-MC and QUALEX, and it gets better solutions to some examples.

关 键 词：最大团问题 遗传算法 均匀设计抽样 人工免疫系统 

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