动态蚁群遗传混合算法1

动态蚁群遗传混合算法的研究及应用 河北工程学院 河北 邯郸 056038 摘要 摘要 蚁群算法是一种源于大自然生物世界的仿生类算法 该算法采 用分布式并行计算和正反馈机制 易于与其他方法结合 具有很强 的鲁棒性和适应性 但存在搜素时间长 易陷入局部最优解的缺点 为了克服这一缺点 文中给出一种新的蚁群算法 动态蚂蚁遗传 混合算法 在基本蚁群算法中引入变异机制 采用最佳融合点评估 策略来交叉地调用两种算法 动态地控制遗传算法与蚂蚁算法的调 用时机 并设计了相应的信息素更新方法 有效减少了算法的冗余 迭代次数 提高了搜索速度 同时引入迭代调整阈值控制算法后期的 遗传操作和蚂蚁规模 加快了种群进化速度 从而更快地找到最优 解 该法具有较快的收敛速度 节省计算时间 实验结果表明该方 法是行之有效的 关键词 关键词 蚁群算法 TSP 问题 遗传算法 动态蚂蚁遗传混合算法 1 引言引言 蚁群算法 Ant Colony Algorithms ACO 又称蚂蚁算法 是一种用来在图中寻找优 化路径的机率型技术 蚂蚁在寻找食物时 总是能找到较短的路径 受到蚁群系统信息共 享机制的启发 意大利学者Macro Dorigo于1992年在他的博士论文中首次系统提出了蚁群 算法 并成功地将该算法应用到求解旅行商问题 TSP 和二次分配问题 QAP 中 取得了 一系列较好的实验结果 解决一些实际问题也有很好的效果 但蚁群算法同其它生物进化 算法一样存在过早收敛易陷入局部极小值等问题 结合其它优化算法形成混合蚁群算法是 克服这些缺点的有效手段 遗传算法 genetic algorithm GA 以决策变量的编码作为运算 对象 在优化过程中借鉴生物学中染色体和基因的概念 模拟自然界中生物和遗传进化等 机理 通过个体适应度来进行概率选择操作 通过交叉变异产生新的个体 从而遗传算法 具有较强的全局性 为克服蚁群算法搜索速度慢 易陷入局部最优等缺点 本文提出了一种新的动态蚁群 遗传混合算法 Dynamic Ant Algorithm Genetic Algorithm DAAGA 该算法采用最佳融 合点评估策略来交叉地调用两种算法 其框架是用蚂蚁算法的解作为遗传操作的种子 每 当种群进化接近停滞时 调用蚂蚁算法 这种结构可以动态地控制遗传算法和蚂蚁算法的 调用时机 再配合相应的信息素更新方法 可以提高算法的收敛速度和收敛性能 同时这 种算法还引入了迭代调整阈值来控制算法后期的遗传操作和蚂蚁规模 即在种群已进化至 最优解附近 遗传算法作用减少时 只做变异操作以减少算法计算工作量 增加蚂蚁规模 以更快地找到最优解 2 2 基本蚁群算法的原理基本蚁群算法的原理 蚁群算法是一种由于受自然界生物的行为启发而产生的 自然 算法 它是从对蚁群 行为的研究中产生的 自然界中 诸如蚂蚁 蜜蜂等群居昆虫 虽然个体昆虫的行为极其 简单 但由单个简单的个体所组成的群体却表现出非常复杂有序的集体行为 经过大量观 察研究 仿生学家发现 蚂蚁个体之间通过一种称之为信息素 pheromone 的物质进行信 息传递 从而能相互协作 完成复杂的任务 蚁群算法计算过程主要包括两个阶段 信息素的积累阶段和蚂蚁间的相互协作阶段 前者包括各候选解积累的信息不断调整自身结构的过程 即蚂蚁不断选择从信息素量大的 路径上通过 使得此路径上蚂蚁留下的信息素越来越大 而信息素量小的路径 则蚂蚁选 择的概率越来越小 会逐渐被淘汰 在蚂蚁的协作阶段 候选解相互间用过信息交流 一 起发现更为优越的路径 产生更优的解 通过人工模拟蚂蚁搜索食物的过程 我们称这种算法为 人工蚁群算法 为了说明人 工蚁群系统的原理 我们先简要介绍一下蚂蚁搜索食物的具体过程 这里用图 1 形象说明 自然界蚂蚁的觅食行为 图 2 形象说明 人工蚁群算法 的路径搜素原理和机制 Fig 1 An example with real ant a 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 is laid down Fig 2 An example with artificial ants a 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 average preferred by ants 2 1 基本蚁群算法的数学模型基本蚁群算法的数学模型 蚁群算法的寻优是在有向图 G C L 上通过三个准则 转移概率准则 局部调整 准则和全局信息素调整准则 加以实现的 1 转移概率准则 转移概率准则 1 0 kk irir ijij k ij allowedsallowedj tt tt tp allowedkN 否则 其中 allowedk C tabuk 表示蚂蚁 k 下一步允许选择的城市 为信息启发式因子 ij t 为从 i 城市到 j 城市的路径信息素 表示轨迹的相对重要性 值越大 蚂蚁 选择该路径的可能性就越大 如果 过大其选择的随机性就越小 容易陷入局部最优解 反之 过小易造成算法收敛程度过慢 为期望启发式因子 表示能见度的相对重要性 越大 则该状态状态转移概率越接近于贪心规则 ij t 为启发函数 ij t 1 dij 式中 dij表示相邻两个城市之间的距离 对蚂蚁 k 而言 dij越小 则 ij t 越大 pijk也 就越大 显然 该启发函数表示蚂蚁从元素 城市 i 转移到元素 城市 j 的期望程度 2 2 局部调整准则 局部调整准则 这种局部调整准则模仿了真实世界的外激素挥发原则 随着时间的推移而历史信息素 逐步挥发 蚁群算法中 经过 h 个时刻 两个元素状态之间的局部信息素数量可根据以下 调整 2 1 1 min0 0 nl thtijij 其中 表示集合 C 中量个最近元素之间的距离 1 0 minl 3 3 全局信息素调整准则全局信息素调整准则 t n 时刻在路径 i j 上的信息量可按如下规则进行调整 4 3 1 1 tt ttnt m k k ij ij ijijij 式中 表示信息素挥发系数 则1 表示信息素残留因子 为了防止信息的无限积累 的取值范围为 0 1 ij t 表示本次循环中路径 i j 上的信息素增量 初始时刻 ij t 0 ijk t 表示第k只蚂蚁在本次循环中留在路径 i j 上的信息量 Ant Cycle模型对的定义 t k ij 否则 过 只蚂蚁在本次循环中经若第 5 0 jik K k ij L Q t 2 2 以基本蚁群算算法求解以基本蚁群算算法求解 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 蚂蚁数目 k k 1 5 如果到了算法规定的 H 时刻 根据式 2 进行信息素挥发 6 蚂蚁个体根据状态转移概率公式 1 计算的概率选择元素 城市 j 并前 ktabuCj 7 修改禁忌表指针 即选择好之后将蚂蚁移动到新的元素 城市 并把该元素 城市 移动 到该蚂蚁个体的禁忌表中 8 若集合 C 中元素 城市 未遍历完 即 k 则遗传算法只做变异 更新群体操作 步骤 6 判断是否判断是否大于遗传算法最小迭代次数 NGmin 如果小于等于 NGmin 则继 续进行一系列的遗传操作 如果大于 NGmin 则按式 6 进行最佳融合点评估 如 果种群不满足评估策略 则继续进行一系列的遗传操作 每次进行局部信息素更 新 如果满足评估策略则转步骤 8 步骤 7 判断是否达到遗传算法最大迭代次数 如达到则下一步 否 则继续进行遗传操 作 步骤 8 更新全局最优解 并用全局最优解根据 7 进行信息素更新操作 步骤 9 判断 NK 是否达到 NKmax 如没有达到 NKmax 若 NK 则直接转步骤 2 若 NK 则 转步骤 2 并增加蚂蚁算法的初始解规模 达到 NKmax 输出最优解 算法结束 4 4 实验结果与分析实验结果与分析 为了验证遗传蚁群混合算法的有效性 通过对 TSPLIB 中 Oliver30 问题和 Eil51 问题 进行仿真研究 平均运行 25 次作为仿真结果 实验中所采取的各项参数如下 1 5 Q 150 Oliver30 问题中蚂蚁数目 m 10 设置最大循环次数 250 次 在 Eil51 问题中蚂蚁数目 m 20 设置最大循环次数 600 次 实验数据结果如表 1 所示 表表1 1 3 3种算法最优解 平均解和进化代数种算法最优解 平均解和进化代数 问题算法平均值最优值平均进化代数 基本 ACA 438 12 425 12132 文献 7 算法 433 35424 7999Oliver30 本文算法 429 46423 7260 基本 ACA 443 36426 46295 文献 7 算法 436 59426 40243Eil51 本文算法 432 13425181 从表 1 中的实验数据可以看出 本文算法求出的平均解和最优解的结果都要比基本的 蚁群算法的求解结果好 同时本文算法收敛性能比基本蚁群算法好 本文给出的一类融入 遗传算法的蚁群算法的全局性和收敛性比基本蚁群算法都有所提高 是一种有效的改进算 法 5 5 结束语结