基于均匀免疫优化算法的最大团问题求解

J4 ›› 2015, Vol. 37 ›› Issue (03): 534-538.

基于均匀免疫优化算法的最大团问题求解

汪宏海1,2，张正球3

(1.西安电子科技大学计算机学院,陕西西安 710071；2.赣州师范高等专科学校计算机系,江西赣州 341000；3.福建师范大学软件学院,福建福州 350027)

收稿日期:2013-11-01 修回日期:2014-02-24 出版日期:2015-03-25 发布日期:2015-03-25
基金资助:
福建省教育厅JK类科技资助项目(JK2010010)；福建省自然科学基金资助项目(2011J01339)

A uniform immune clone based intelligent optimization
algorithm to solve the maximum clique problem

WANG Honghai 1，2，ZHANG Zhengqiu3

(1.School of Computer,Xidian University,Xi’an 710071;
2.Department of Computers Science,Ganzhou Teachers Colleage,Ganzhou 341000;
3.Faculty of Software,Fujian Normal University,Fuzhou 350027,China)

Received:2013-11-01 Revised:2014-02-24 Online:2015-03-25 Published:2015-03-25

摘要/Abstract

摘要：

最大团问题是一种典型的组合优化问题，具有广泛的应用背景。针对最大团问题的NP特性，提出了一种基于免疫克隆优化的智能求解算法。描述了最大团问题的数学模型，设计了求解最大团问题的抗体编码、亲和度函数、变异算子及抗体修正方法。在免疫克隆参数设置时，将其描述为多因素多水平的均匀设计，减少了设置参数的实验次数。通过最大团问题的基准算例进行了实验。结果表明，本算法求解效果较好，并且求解速度较快。

关键词: 免疫优化, 最大团问题, 抗体编码, 均匀设计

Abstract:

The maximum clique problem is a typical combinatorial optimization problem,which has wide application background.For the NP characteristic of the maximum clique problem, an immune clone based on intelligent optimization algorithm is proposed to solve it. The mathematical model of the maximum clique problem is described.For solving the maximum clique problem,antibody encoding, affinity function, mutation operator and antibody correction method are designed. To reduce the number of parameter setting for the experiment, it is converted into a uniform design problem of multifactor and multilevel.The Benchmark experimental results show that the algorithm has better performance and rapid solving speed.

Key words: immune optimization;maximum clique problem;antibody encoding;uniform design

汪宏海1,2，张正球3 . 基于均匀免疫优化算法的最大团问题求解[J]. J4, 2015, 37(03): 534-538.

WANG Honghai 1，2，ZHANG Zhengqiu3 . A uniform immune clone based intelligent optimization
algorithm to solve the maximum clique problem [J]. J4, 2015, 37(03): 534-538.

[1]	高雷阜，赵世杰，于冬梅，徒君. 果蝇耦合均匀设计算法及其优化SVM参数[J]. J4, 2016, 38(05): 954-959.
[2]	李长云，潘伟强，胡盛龙. 基于均匀设计的支持向量机参数优化方法[J]. J4, 2014, 36(04): 702-706.
[3]	杜波，金光，周经伦，张礼伟. 基于代理模型的武器装备体系优化算法研究[J]. J4, 2012, 34(6): 74-78.
[4]	刘波涛1，李会凯2. 公交车和驾驶员集成调度算法研究[J]. J4, 2011, 33(4): 150-153.
[5]	高尚[1,2] 陈建忠[3]. 免疫克隆算法参数的均匀设计[J]. J4, 2007, 29(10): 35-37.