基于抗体的蚁群优化算法研究

《基于抗体的蚁群优化算法研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于抗体的蚁群优化算法研究第２２卷第４期重庆邮电大学学报（自然科学版）Ｖｏｌ．２２　Ｎｏ．４２０１０年８月ＪｏｕｒｎａｌｏｆＣｈｏｎｇｑｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＰｏｓｔｓａｎｄＴｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）Ａｕｇ．２０１０基于抗体的蚁群优化算法研究收稿日期：２０１００１１２　修订日期：２０１００６０９　基金项目：重庆市自然科学基金（ＣＳＴＣ，２００６ＢＢ２２４２）ＦｏｕｎｄａｔｉｏｎＩｔｅｍ：ＣｈｏｎｇｑｉｎｇＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎ

2、Ｐｒｏｊｅｃｔ，ＣＳＴＣ（ＣＳＴＣ，２００６ＢＢ２２４２）．胡　勇（重庆交通大学应用技术学院，重庆４０００７４）摘　要：针对蚁群优化（ａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ，ＡＣＯ）容易陷入局部最优，提出一个基于抗体的新型蚁群优化算法（ａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎｂａｓｅｄｏｎｉｍｍｕｎｅａｌｇｏｒｉｔｈｍ，ＡＣＯＩ）。ＡＣＯＩ是利用免疫算法中抗体的概念来改善人工蚂蚁搜寻解空间的方式，使人工蚂蚁不仅会依随费洛蒙的指引，还会受到抗体的影响去搜寻解空间；而抗体也会随着环境的改变，使抗体成为有效的及无效的２种情

3、形，有效的抗体对人工蚂蚁会有影响，无效的抗体则没有影响。用旅行销售员问题（ｔｒａｖｅｌｉｎｇｓａｌｅｓｍｅｎｐｒｏｂｌｅｍ，ＴＳＰ）验证ＡＣＯＩ的效能，并与ＡＣＯ做比较，证明了在蚁群系统中加入抗体要比单纯的蚁群系统效率更高。关键词：蚁群优化（ＡＣＯ）；免疫算法；推销员问题（ＴＳＰ）；群体智能；抗体中图分类号：ＴＰ３０１．６　　　　　　　　　文献标识码：Ａ文章编号：１６７３８２５Ｘ（２０１０）０４０５０７０５ＲｅｓｅａｒｃｈｏｎａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎａｎｔｉｂｏｄｙＨ

4、ＵＹｏｎｇ（ＣｏｌｌｅｇｅｏｆＡｐｐｌｉｃａｔｉｏｎＴｅｃｈｎｏｌｏｇｙ，ＣｈｏｎｇｑｉｎｇＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｃｈｏｎｇｑｉｎｇ４０００７４，Ｐ．Ｒ．Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｔｈｅｐａｐｅｒｐｒｏｐｏｓｅｄａｎｅｗｔｙｐｅｏｆａｎｔｉｂｏｄｙｂａｓｅｄａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ（ＡＣＯ），ｋｎｏｗｎａｓｔｈｅＡＣＯＩ（ＡＣＯｂａｓｅｄｏｎｉｍｍｕｎｅａｌｇｏｒｉｔｈｍ）．ＡＣＯＩｗａｓｔｈｅｕｓｅｏｆａｎｔｉｂｏｄｉｅｓｉｎｔｈｅｃｏｎｃｅｐｔｏｆｉｍｍｕｎｅａｌｇｏｒｉｔｈｍｔ

5、ｏｉｍｐｒｏｖｅｔｈｅｗａｙｓｏｆａｒｔｉｆｉｃｉａｌａｎｔｓｓｅａｒｃｈｓｏｌｕｔｉｏｎｓｐａｃｅｉｎｗｈｉｃｈａｒｔｉｆｉｃｉａｌａｎｔｓｗｏｕｌｄｎｏｔｏｎｌｙｆｏｌｌｏｗｔｈｅｇｕｉｄｅｌｉｎｅｓｗｉｔｈｔｈｅｐｈｅｒｏｍｏｎｅ，ｂｕｔａｌｓｏｓｅａｒｃｈｔｈｅｓｏｌｕｔｉｏｎｓｐａｃｅｂｙｔｈｅｉｍｐａｃｔｏｆａｎｔｉｂｏｄｉｅｓ．Ｔｈｅａｎｔｉｂｏｄｙｗｏｕｌｄｂｅｅｆｆｅｃｔｉｖｅｏｒｉｎｅｆｆｅｃｔｉｖｅａｓｅｎｖｉｒｏｎｍｅｎｔｓｃｈａｎｇｅ．Ｔｈｅｅｆｆｅｃｔｉｖｅａｎｔｉｂｏｄｙｈａｄａｎｉｍｐａｃ

6、ｔｏｎａｒｔｉｆｉｃｉａｌａｎｔｓ，ｗｈｉｌｅｉｎｅｆｆｅｃｔｉｖｅｎｏｔ．ＡＣＯＩｐｒｏｖｅｄｂｙｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍｄｏｉｎｇｖａｌｉｄａｔｉｏｎ，ａｎｄｃｏｍｐａｒｅｄｗｉｔｈｔｈｅＡＣＯ，ｓｈｏｗｓｔｈａｔａｄｄｉｎｇａｎｔｉｂｏｄｉｅｓｔｏａｎｔｓｇｒｏｕｐｉｓｍｏｒｅｅｆｆｅｃｉｂｅｔｈａｎａｓｉｍｐｌｅａｎｔｃｏｌｏｎｙｓｙｓｔｅｍ．Ｋｅｙｗｏｒｄｓ：ａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ（ＡＣＯ）；ｉｍｍｕｎｅａｌｇｏｒｉｔｈｍ；ｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅ

7、ｍ（ＴＳＰ）；ｓｗａｒｍｉｎｔｅｌｌｉｇｅｎｃｅ；ａｎｔｉｂｏｄｙ０　引　言蚁群优化（ａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ，ＡＣＯ）由Ｄｏｒｉｇｏ提出，其理论基于自然界蚂蚁外出觅食的行为，应用于求近似解的一种人工智能启发式解法［１２］。ＡＣＯ的基本概念是自然界的蚂蚁会离开巢穴寻找食物，藉由它们自己本身所散发出来的特有化学分泌物—费洛蒙来帮助蚂蚁在找寻食物时，能够遗留下某些信息给其他的蚂蚁知道其寻找食物时曾经所走过的路径。而自然界的蚂蚁在经过不断地搜寻食物的过程中，往往会遗留许多的费洛蒙，随着越来越多的蚂蚁走过相同的

8、路径时，此路径的费洛蒙也随之增加；相对的，其余路径的费洛蒙则会慢慢蒸发；最后蚂蚁利用费洛蒙来找寻出离食物最近的相关路径。而蚁群优化就是利用模拟自然界蚂蚁的搜寻方式，演化出一种人工蚂蚁，代替一般的搜寻方法，进而达到搜寻最短路径。但大量的实践表明，ＡＣＯ容易陷入局部最优解（ｌｏｃａｌｏｐｔｉｍｉｚａｔｉｏｎ