基于免疫修复,利用领域知识,加快蚁群优化算法搜索过程。

第24卷第10期

Vol.24No.10

控　制　与　决　策

Control

and

Decision

　2009年10月

　　　Oct.2009

　　文章编号:100120920(2009)1021509204

基于免疫修复的快速蚁群优化算法

闭应洲1,2,丁立新1,陆建波2

(1.武汉大学软件工程国家重点实验室,武汉430072;2.广西师范学院信息技术系,南宁530001)

摘　要:蚁群优化算法通过信息素记录搜索过程中获取的知识,并基于信息素搜索新的解.主要是信息素更新策略和蚂蚁已找到的候选解的质量.中的“病变”成分,并对其“病变”成分进行修复.经免疫修复后,映了优质解的特点,从而加快了信息的正反馈过程..关键词:蚁群优化算法;免疫修复;中图分类号:TP301.A

Fastantoptimizationalgorithmwithimmunityrepairing

BIYing2zhou

1,2

,DINGLi2xin,LUJian2bo

12

(1.StateKeyLaboratoryofSoftwareEngineering,WuhanUniversity,Wuhan430072,China;DepartmentofInformationTechnology,GuangxiTeachersEducationUniversity,Nanning530001,China.Correspondent:BIYing2zhou,E2mail:byzhou@163.com)

Abstract:Thepheromoneinantcolonyoptimization(ACO)areusedtoreflecttheants’searchexperience,andtheantsexploitthemtoprobabilisticallyconstructsolutionstotheproblem.Themainfactorsaffectingthequalityofthepheromoneincludethepolicyofupdatingthepheromoneandthequalityoftheconstructedsolutions.Inordertoimprovetheconstructedsolutions,amethodispresentedtoanalyzetheinvalidcomponentsoftheconstructedsolution,andtheinvalidcomponentsarerepairedwithimmunityoperator.Afterimmunityrepairing,thequalityoftheconstructedsolutionsisimproved,whichcanexactlyreflectthecharacterofhighqualitysolution,andspeedupthepositivefeedbackprocedure.Experimentresultsshowtheeffectivenessofthemethod.Keywords:Antcolonyoptimization;Immunityrepairing;Policyofupdatingthepheromone.

1　引　　言

蚁群优化算法和其他启发式算法一样,都是通

过对已有候选解进行学习,获取启发性知识来指导下一步的搜索,但它属于基于模型的搜索[123].蚁群优化算法通过信息素记录搜索过程中获取的知识,并基于信息素搜索新的解,因此信息素的质量十分重要,而影响信息素质量的因素主要有:蚂蚁释放信息素的策略和蚂蚁已找到的候选解的质量.最初的蚂蚁系统(AS)算法有3个不同的版本,分别为蚂蚁密度、蚂蚁数量和蚂蚁周期.在蚂蚁密度和蚂蚁数量这两个版本中,蚂蚁从一个城市转移到另一个城市后就直接释放信息素.但在蚂蚁周期中,只有所有蚂蚁都构建出一条路径后才执行信息素更新.实践证明,蚂蚁周期算法性能更高,蚂蚁密度和蚂蚁数量已被淘汰[4].

收稿日期:2008212219;修回日期:2009203209.

为了进一步提高算法的性能,大量的人类智慧已被集成到ACO算法当中.其中包括:1)每一代中只有构建最好路径的蚂蚁,或是构建至今最优路径的蚂蚁,才被允许释放信息素;2)对路径上的信息素浓度取值范围进行限制[4,5];3)信息素动态更新策略[6]等.通过改进信息素更新策略,这些新的算法又比AS算法获得更好的性能.为了克服蚂蚁算法初期信息素匮乏,求解速度慢的问题,文献[7,8]提出将遗传算法与蚂蚁算法融合,采用遗传算法生成信息素分布.

在演化算法中,为了降低传统交叉算子的破坏性,文献[9,10]提出将生命科学中的免疫学原理与遗传算法结合起来,基于免疫算子(利用领域知识)对交叉结果进行修复、改进,整体提高算法的性能.其原理是基于领域知识发现染色体中的“病变基因,

基金项目:国家自然科学基金项目(40761027);广西教育厅科研项目(200707MS171).

),男,广西横县人,副教授,博士,从事智能计算、作者简介:闭应洲(1967—智能信息处理的研究;丁立新

(1967—),男,湖南益阳人,教授,博士生导师,从事演化计算、智能信息处理的研究.