动态蚁群遗传混合算法1

《动态蚁群遗传混合算法1》由会员分享，可在线阅读，更多相关《动态蚁群遗传混合算法1（6页珍藏版）》请在金锄头文库上搜索。

1、动态蚁群遗传混合算法的研究及应用（河北工程学院，河北 邯郸 056038）摘要：蚁群算法是一种源于大自然生物世界的仿生类算法，该算法采用分布式并行计算和正反馈机制。易于与其他方法结合，具有很强的鲁棒性和适应性，但存在搜素时间长、易陷入局部最优解的缺点。为了克服这一缺点, 文中给出一种新的蚁群算法动态蚂蚁遗传混合算法。在基本蚁群算法中引入变异机制, 采用最佳融合点评估策略来交叉地调用两种算法。动态地控制遗传算法与蚂蚁算法的调用时机，并设计了相应的信息素更新方法，有效减少了算法的冗余迭代次数，提高了搜索速度,同时引入迭代调整阈值控制算法后期的遗传操作和蚂蚁规模，加快了种群进化速度，从而更快地找到最

2、优解。 该法具有较快的收敛速度，节省计算时间，实验结果表明该方法是行之有效的。关键词：蚁群算法; TSP 问题; 遗传算法; 动态蚂蚁遗传混合算法1 引言蚁群算法 (Ant Colony Algorithms，ACO）又称蚂蚁算法。是一种用来在图中寻找优化路径的机率型技术。蚂蚁在寻找食物时，总是能找到较短的路径。受到蚁群系统信息共享机制的启发，意大利学者Macro Dorigo于1992年在他的博士论文中首次系统提出了蚁群算法，并成功地将该算法应用到求解旅行商问题（TSP)和二次分配问题（QAP)中。取得了一系列较好的实验结果。解决一些实际问题也有很好的效果。但蚁群算法同其它生物进化算法一样存

3、在过早收敛易陷入局部极小值等问题。结合其它优化算法形成混合蚁群算法是克服这些缺点的有效手段。遗传算法(genetic algorithm，GA)以决策变量的编码作为运算对象，在优化过程中借鉴生物学中染色体和基因的概念，模拟自然界中生物和遗传进化等机理，通过个体适应度来进行概率选择操作，通过交叉变异产生新的个体，从而遗传算法具有较强的全局性。为克服蚁群算法搜索速度慢、易陷入局部最优等缺点。本文提出了一种新的动态蚁群遗传混合算法(Dynamic Ant Algorithm -Genetic Algorithm，DAAGA)。该算法采用最佳融合点评估策略来交叉地调用两种算法，其框架是用蚂蚁算法的解作

4、为遗传操作的种子，每当种群进化接近停滞时，调用蚂蚁算法。这种结构可以动态地控制遗传算法和蚂蚁算法的调用时机，再配合相应的信息素更新方法，可以提高算法的收敛速度和收敛性能；同时这种算法还引入了迭代调整阈值来控制算法后期的遗传操作和蚂蚁规模，即在种群已进化至最优解附近，遗传算法作用减少时，只做变异操作以减少算法计算工作量，增加蚂蚁规模以更快地找到最优解。2 基本蚁群算法的原理蚁群算法是一种由于受自然界生物的行为启发而产生的“自然”算法。它是从对蚁群行为的研究中产生的。自然界中，诸如蚂蚁、蜜蜂等群居昆虫，虽然个体昆虫的行为极其简单，但由单个简单的个体所组成的群体却表现出非常复杂有序的集体行为。经过大

5、量观察研究，仿生学家发现，蚂蚁个体之间通过一种称之为信息素( pheromone) 的物质进行信息传递。从而能相互协作，完成复杂的任务。蚁群算法计算过程主要包括两个阶段：信息素的积累阶段和蚂蚁间的相互协作阶段，前者包括各候选解积累的信息不断调整自身结构的过程，即蚂蚁不断选择从信息素量大的路径上通过，使得此路径上蚂蚁留下的信息素越来越大，而信息素量小的路径，则蚂蚁选择的概率越来越小，会逐渐被淘汰；在蚂蚁的协作阶段，候选解相互间用过信息交流，一起发现更为优越的路径，产生更优的解。通过人工模拟蚂蚁搜索食物的过程，我们称这种算法为“人工蚁群算法” 。为了说明人工蚁群系统的原理, 我们先简要介绍一下蚂蚁

6、搜索食物的具体过程。这里用图 1 形象说明自然界蚂蚁的觅食行为，图 2 形象说明“人工蚁群算法”的路径搜素原理和机制。Fig. 1. An example with real anta) Ants follow a path between points A and E.b) An obstacle is interposed; ants can choose to go around it following one of the two different paths with equal probability.c) On the shorter path more pheromone

7、is laid down.Fig. 2. An example with artificial antsa) The initial graph with distances.b) At time t=0 there is no trail on the graph edges; therefore, ants choose whether to turn right or left with equal probability.c) At time t=1 trail is stronger on shorter edges, which are therefore, in the aver

8、age, preferred by ants.2.1 基本蚁群算法的数学模型蚁群算法的寻优是在有向图 G=(C,L,)上通过三个准则（转移概率准则、局部调整准则和全局信息素调整准则）加以实现的。（1）转移概率准则： )1(,0)()()( kkirirjjkij alowedsalowedjtttpalowedkN ，否 则 其中 allowedk=C-tabuk表示蚂蚁 k 下一步允许选择的城市； 为信息启发式因子， ij(t)为从 i 城市到 j 城市的路径信息素。 表示轨迹的相对重要性， 值越大，蚂蚁选择该路径的可能性就越大。如果 过大其选择的随机性就越小，容易陷入局部最优解，反之 过小

9、易造成算法收敛程度过慢； 为期望启发式因子，表示能见度的相对重要性, 越大，则该状态状态转移概率越接近于贪心规则； ij(t)为启发函数, ij(t) =1/dij；式中 dij表示相邻两个城市之间的距离。对蚂蚁 k 而言，d ij越小，则 ij(t)越大，p ijk也就越大。显然，该启发函数表示蚂蚁从元素（城市）i 转移到元素（城市）j 的期望程度。（2）局部调整准则这种局部调整准则模仿了真实世界的外激素挥发原则，随着时间的推移而历史信息素逐步挥发。蚁群算法中，经过 h 个时刻，两个元素状态之间的局部信息素数量可根据以下调整：)2()/(1(min0 0lttijij其中， ， 表示集合 C

10、 中量个最近元素之间的距离。1,0minl（3）全局信息素调整准则（t+n）时刻在路径(i, j)上的信息量可按如下规则进行调整 )4()()( 31(1ttntmkkijij ijijij 式中，表示信息素挥发系数，则1-表示信息素残留因子，为了防止信息的无限积累， 的取值范围为0，1), ij(t)表示本次循环中路径(i, j)上的信息素增量，初始时刻 ij(t) =0, ijk(t) 表示第k只蚂蚁在本次循环中留在路径(i, j)上的信息量。Ant-Cycle模型对 的定义)(tij ）（否 则 ）过 （只 蚂 蚁 在 本 次 循 环 中 经若 第 5,0, ,jikKkijLQt2.2

11、 以基本蚁群算算法求解 TSP 问题为例，具体步骤如下：(1)参数初始化。令时间 t=0 和循环次数 Nc=0，设置最大循环次数 Ncmax, 将 m 个蚂蚁置于n 个元素(城市)上，令有向图上每条边(i, j)的初始化信息量 ij(t)=const, 其中const 表示常数，且初始时刻 ij(0)=0(2)循环次数 Nc Nc+1。(3)蚂蚁的禁忌表索引号 k=1。(4)蚂蚁数目 kk+1 。 (5)如果到了算法规定的 H 时刻，根据式（2）进行信息素挥发。(6)蚂蚁个体根据状态转移概率公式(1)计算的概率选择元素(城市)j 并前，。ktabuCj(7)修改禁忌表指针，即选择好之后将蚂蚁移

12、动到新的元素(城市)，并把该元素(城市)移动 到该蚂蚁个体的禁忌表中。(8)若集合 C 中元素(城市)未遍历完，即 k，则遗传算法只做变异、更新群体操作。步骤 6 判断是否判断是否大于遗传算法最小迭代次数 NGmin，如果小于等于 NGmin，则继续进行一系列的遗传操作；如果大于 NGmin，则按式(6)进行最佳融合点评估；如果种群不满足评估策略，则继续进行一系列的遗传操作。每次进行局部信息素更新。如果满足评估策略则转步骤 8.步骤 7 判断是否达到遗传算法最大迭代次数。如达到则下一步；否，则继续进行遗传操作。步骤 8 更新全局最优解，并用全局最优解根据（7）进行信息素更新操作。步骤 9 判断

13、 NK 是否达到 NKmax。如没有达到 NKmax，若 NK，则直接转步骤 2；若 NK,则转步骤 2，并增加蚂蚁算法的初始解规模。达到 NKmax 输出最优解，算法结束。4 实验结果与分析为了验证遗传蚁群混合算法的有效性，通过对 TSPLIB 中 Oliver30 问题和 Eil51 问题进行仿真研究，平均运行 25 次作为仿真结果。实验中所采取的各项参数如下： = 1， = 5，Q =150，Oliver30 问题中蚂蚁数目 m = 10，设置最大循环次数 250 次；在 Eil51 问题中蚂蚁数目 m = 20，设置最大循环次数 600 次。实验数据结果如表 1 所示。表1 3种算法最

14、优解、平均解和进化代数问题 算法 平均值 最优值 平均进化代数基本 ACA 438.12 425.12 132文献7算法 433.35 424.79 99Oliver30本文算法 429.46 423.72 60基本 ACA 443.36 426.46 295文献7算法 436.59 426.40 243Eil51本文算法 432.13 425 181从表 1 中的实验数据可以看出，本文算法求出的平均解和最优解的结果都要比基本的蚁群算法的求解结果好，同时本文算法收敛性能比基本蚁群算法好，本文给出的一类融入遗传算法的蚁群算法的全局性和收敛性比基本蚁群算法都有所提高，是一种有效的改进算法。5 结束语本文根据遗传算法和蚁群算法的优缺点, 把两者融合起来取其优点。蚁群算法是一种新型的进化算法，它与其它进化算法同样存在易陷入局部最优解的的现象。本文通过融入遗传算法，采用最佳融合点评估策略，设计了相应的信息素更新方法，引入迭代调整阈值较好地克服了停滞, 并能达到更好的优化效果。引入遗传算法后使最优路径加快了算法的收敛速度，改进后蚁群算法可以提高算法的全局搜索能力和收敛性能。实验结果表明, 动态蚂蚁遗传混合算法具有收敛速度快等特点和实用价值。