摘要
针对遗传算法在最大团求解中保持群体多样性能力不足、早熟、耗时长、成功率低等缺陷,依据均匀设计抽样理论对交叉操作进行重新设计,结合免疫机理定义染色体浓度设计克隆选择策略,提出求解最大团问题的均匀设计抽样免疫遗传算法。仿真算例表明,该算法在解的质量、收敛速度等各项指标上均有提高,与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.
出处
《计算机工程》
CAS
CSCD
北大核心
2010年第18期229-231,共3页
Computer Engineering
关键词
最大团问题
遗传算法
均匀设计抽样
人工免疫系统
Maximum Clique Problem（MCP）
Genetic Algorithm（GA）
Uniform Design Sampling（UDS）
Artificial Immune System（AIS）
