基于免疫记忆的蚁群算法
竺兰童竺：！塑塑篁！！鱼塞竺兰！！旦文章编号：１００６—９３４８（２００７）１０－０１６５—０４
基于免疫记忆的蚁群算法
苏淼，钱海，王煦法
（中国科学技术大学计算机科学技术系．安徽合肥２３００２７）
摘要：充分利用前期迭代中解的信息是掏造高艘蚁群算法实现的关键之一。文中把免疫记忆和克隆选择的思想引入蚁群算法，提出了基于免疫记忆的蚁群算法（ＩＭＢＡＣＡ）。算法通过在原有蚊群模型上增加一十免疫记忆库．将记忆库中的解对应为免疫记忆细胞（及其产生的抗体）．将问题对应为抗原，并借鉴克隆选择和免疫记忆的思想进行解的掏造和信息素更新。算法从解的质量和时问方面与传统蚊群算法进行了比较．实验结果表明．所提出的ＩＭＢＡＣＡ算法可明显提高传统蚊群算法的性能，同时也为解决其他组合优化问题提出了一个新的思路。
关键词：免疫记忆；克隆选择；蚁群算法
中圈分类号：ＴＰ３０１６文献标识码：Ａ
ＡｎＩｍｍｕｎｅＭｅｍｏｒｙ—－ＢａｓｅｄＡｎｔＣｏｌｏｎｙＡｌｇｏｒｉｔｈｍ
ＳＵＭｉａｏ，ＱＩＡＮＨａｉ，ＷＡＮＧＸｕ—ｆａ
（ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙｏｆＣｈｉｎａ，
ＨｅｉｆｏｉＡｎｈｕｉ２３００２７，Ｃｈｉｎａ）
ＡＢＳＴＲＡＣＴ：ＴａｋｉｎｇｆａｌｌａｄｖａｎｔａｇｅｏｆｔｈｅｉｎｆｏｒｍａｔｉｏｎｏｆｔｈｅｐｒｅｖｉｏｕｓｓｏＩｎｔｉｏｎｓｉｓｏｎｅｏｆｔｈｅｋｅｙｓｆｏｒｃｏｎｓｔｒｕｃｔｉｎｇｈｉｇｈｔｙｅｆｆｅｃｔｉｖｅｉｍｐｌｅｍｅｎｔａｔｉｏｎｏｆａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ．ＴｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓａｎＩｍｍｕｎｅＭｅｍｏｒｙ—ＢａｓｅｄＡｎｔＣｏｌｏｎｙＡｌｇｏｒｉｔｈｍ（ＩＭＢＡＣＡ）ｂｙｉｎｔｒｏｄｕｃｉｎｇｔｈｅｉｄｅａｏｆｉｍｍｕｎｅｍｅｍｏｒｙａｎｄｃｌｏｎｅｓｅｌｅｃｔｉｏｎｉｎｔｏａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ．ＩＭＢＡＣＡａｄｄｓａｎｉｍｍｕｎｅｍｅｍｏｒｙｌｉｂｒａｒｙｔｏｔｈｅａｎｔｃｏｌｏｎｙｍｏｄｅｌ，ｒｅｇａｒｄｉｎｇｔｈｅｓｏｌｕｔｉｏｎｓｉｎｔｈｅｉｍｍｕｎｅｍｅｍｏｒｙｌｉｂｒａｒｙａ８ａｎｔｉｂｏｄｉｅｓａｎｄｔｈｅｐｒｏｂｌｅｍ∞ａｎｔｉｇｅｎ．Ｉｔｕｓｅ８ｔｈｅａｂｏｖｅｉｄｅａｆｏｒｓｏｌｕｔｉｏｎｃｏｎｓｔｒｕｃｔｉｏｎａｎｄｐｈｅｒｏｍｏｎｅｃｏｎｃｅｎｔｒａｔｉｏｎｕｐｄａｔｅ．ＩＭＢＡＣＡｉｓｃｏｍｐａｒｅｄｔｏｔｈｅｔｒａｄｉｔｉｏｎａｌａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｉｎｔｅｒｍｓｏｆｂｏｔｈｓｏｌｕｔｉｏｎｑｕａｌｉｔｙａｎｄｓｐｅｅｄ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｉｎｄｉｃａｔｅｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｃ∞ｅｖｉｄｅｎｄｙｉｍｐｒｏｖｅｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆｔｈｅｔｒａｄｉｔｉｏｎａｌａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ．ＩｔａｌｓｏｐｒｏｖｉｄｅｓａＨｅＷｉｄｅａｆｏｒｓｏｌｖｉｎｇｏｔｈｅｒｃｏｍｂｉｎａｔｉｏｎａｌｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓ．
ＫＥＹＷＯＲＤＳ：Ｉｍｍｕｎｅｍｅｍｏｒｙ；Ｃｌｏｎｅｓｅｌｅｃｔｉｏｎ；Ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ
、
１引言
蚁群算法（ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ）是２０世纪９０年代以来发展起来的一种新型仿生进化算法。算法模拟自然界蚂蚁觅食过程中的群体寻径行为，简单个体之间通过信息紊进行信息交流和协作，从而逐步找到问题的最优解。正反馈和分布式并行计算机制是蚁群算法的两个重要特征：正反馈使得系统中的较优解得以不断“自我增强”，从而使解向着全局最优的方向演变；算法在全局的多点进行并行搜索，这种分布式并行机制能在相当程度上避免搜索陷人局部最优。蚁群算法的内在并行性、鲁棒性等良好特性使其成为解决复杂优化问
收穑日期：２００６—０９—２３修回日期：２００６—０９—２７题、分布控制问题和聚类分析等问题的一种有效计算模型。特别地，蚁群算法已在多种组合优化（如ＴＳＰ、ＱＡＰ、ＪＳＰ、ＶＲＰ等）、连续优化和动态优化（如网络路由）问题中得到了成功的应用。
蚁群算法也存在着进化速度慢、易陷入局部最优等缺点．自最初的蚂蚁系统（ＡｎｔＳｙｓｔｅｍ）”“引提出以来，许多学者为此进行了大量改进。代表性的工作有”１：蚁群系统（ＡＣＳ）、最大一最小蚂蚁系统（ＭＭＡＳ）、基于优化排序的蚂蚁系统（Ａｓ吐）、最优一最差蚂蚁系统（ＢＷＡＳ）等。已有工作大致包括以下几个方面的改进：①信息紊的限界和各种动态更新策略；②局部搜索机制的加人；③运用ＣＡ等算法形成更有效的初始信息素分布，等等。正如文献［５］中所指出的．高效的蚁群算法的关键在于如何保持“探索（ｅｘｐｌｏｒａｔｉｏｎ）”和。利用（ｅｘｐｌｏｉｔａｔｉｏｎ）”的平衡。从“利用
一１６５—
万方数据万方数据