作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2010, Vol. 36 ›› Issue (18): 229-231. doi: 10.3969/j.issn.1000-3428.2010.18.079

• 人工智能及识别技术 • 上一篇    下一篇

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

周本达a,岳 芹a,陈明华b   

  1. (皖西学院 a. 数理系;b. 计算机科学与技术系,安徽 六安 237012)
  • 出版日期:2010-09-20 发布日期:2010-09-30
  • 作者简介:周本达(1974-),男,副教授、硕士,主研方向:遗传算法,贝叶斯网络,生物信息学,多Agent系统;岳 芹,讲师、 硕士;陈明华,教授

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

ZHOU Ben-daa, YUE Qina, CHEN Ming-huab   

  1. (a. Dept. of Mathematics & Physics; b. Dept. of Computer Science & Technology, West Anhui University, Lu’an 237012, China)
  • Online:2010-09-20 Published:2010-09-30

摘要: 针对遗传算法在最大团求解中保持群体多样性能力不足、早熟、耗时长、成功率低等缺陷,依据均匀设计抽样理论对交叉操作进行重新设计,结合免疫机理定义染色体浓度设计克隆选择策略,提出求解最大团问题的均匀设计抽样免疫遗传算法。仿真算例表明,该算法在解的质量、收敛速度等各项指标上均有提高,与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)

中图分类号: