摘要: 针对遗传算法在最大团求解中保持群体多样性能力不足、早熟、耗时长、成功率低等缺陷,依据均匀设计抽样理论对交叉操作进行重新设计,结合免疫机理定义染色体浓度设计克隆选择策略,提出求解最大团问题的均匀设计抽样免疫遗传算法。仿真算例表明,该算法在解的质量、收敛速度等各项指标上均有提高,与DLS-MC、QUALEX等经典搜索算法相比,对部分算例能得到更好解。
关键词:
最大团问题,
传算法,
匀设计抽样,
工免疫系统
Abstract: 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.
Key words:
Maximum Clique Problem(MCP),
Genetic Algorithm(GA),
niform Design Sampling(UDS),
Artificial Immune System(AIS)
中图分类号:
周本达, 岳芹, 陈明华. 求解最大团问题的均匀设计抽样免疫遗传算法[J]. 计算机工程, 2010, 36(18): 229-231.
ZHOU Ben-Da, YUE Qin, CHEN Meng-Hua. Immune Genetic Algorithm Based on Uniform Design Sampling for Solving Maximum Clique Problem[J]. Computer Engineering, 2010, 36(18): 229-231.