遗传算法和蚁群算法的比较

全局优化报告 遗传算法和蚁群算法的比较 姓 名 郑 玄 玄 学 号 3112054023 班 级 硕 2041 1 遗传算法 1 1 遗传算法的发展历史遗传算法的发展历史 遗传算法是一种模拟自然选择和遗传机制的寻优方法 20 世纪 60 年代初期 Holland 教授开始认识到生物的自然遗传现象与人工自 适应系统行为的相似性 他认为不仅要研究自适应系统自身 也要 研究与之相关的环境 因此 他提出在研究和设计人工自适应系统 时 可以借鉴生物自然遗传的基本原理 模仿生物自然遗传的基本 方法 1967 年 他的学生 Bagley 在博士论文中首次提出了 遗传算 法 一词 到 70 年代初 Holland 教授提出了 模式定理 一般认 为是遗传算法的基本定理 从而奠定了遗传算法的基本理论 1975 年 Holland 出版了著名的 自然系统和人工系统的自适应性 这 是第一本系统论述遗传算法的专著 因此 也有人把 1975 年作为遗 传算法的诞生年 1985 年 在美国召开了第一届两年一次的遗传算法国际会议 并且成立了国际遗传算法协会 1989 年 Holland 的学生 Goldberg 出版了 搜索 优化和机器学习中的遗传算法 总结了遗传算法研 究的主要成果 对遗传算法作了全面而系统的论述 一般认为 这 个时期的遗传算法从古典时期发展了现代阶段 这本书则奠定了现 代遗传算法的基础 遗传算法是建立在达尔文的生物进化论和孟德尔的遗传学说基 础上的算法 在进化论中 每一个物种在不断发展的过程中都是越 来越适应环境 物种每个个体的基本特征被后代所继承 但后代又 不完全同于父代 这些新的变化 若适应环境 则被保留下来 否 则 就将被淘汰 在遗传学中认为 遗传是作为一种指令遗传码封 装在每个细胞中 并以基因的形式包含在染色体中 每个基因有特 殊的位置并控制某个特殊的性质 每个基因产生的个体对环境有一 定的适应性 基因杂交和基因突变可能产生对环境适应性强的后代 通过优胜劣汰的自然选择 适应值高的基因结构就保存下来 遗传 算法就是模仿了生物的遗传 进化原理 并引用了随机统计原理而 形成的 在求解过程中 遗传算法从一个初始变量群体开始 一代 一代地寻找问题的最优解 直到满足收敛判据或预先假定的迭代次 数为止 遗传算法的应用研究比理论研究更为丰富 已渗透到许多学科 并且几乎在所有的科学和工程问题中都具有应用前景 一些典型的 应用领域如下 1 复杂的非线性最优化问题 对具体多个局部极值的非线性最优 化问题 传统的优化方法一般难于找到全局最优解 而遗传算法可 以克服这一缺点 找到全局最优解 2 复杂的组合优化或整数规划问题 大多数组合优化或整数规划 问题属于 NP 难问题 很难找到有效的求解方法 而遗传算法即特别 适合解决这一类问题 能够在可以接受的计算时间内求得满意的近 似最优解 如著名的旅行商问题 装箱问题等都可以用遗传算法得 到满意的解 3 工程应用方面 工程方法的应用是遗传算法的一个主要应用领 域 如管道优化设计 通风网络的优化设计 飞机外型设计 超大 规模集成电路的布线等 4 计算机科学 遗传算法广泛应用于计算机科学的研究 如用于 图像处理和自动识别 文档自动处理 VLSI 设计等 5 生物学 遗传算法起源于对生物和自然现象的模拟 现在又反 过来用于生物领域的研究 如利用遗传算法进行生物信息学的研究 等 6 社会科学 遗传算法在社会科学的许多领域也有广泛应用 如 人类行为规范进化过程的模拟 人口迁移模型的建立等 7 经济领域 经济学领域也用到遗传算法 例如 国民经济预测 模型 市场预测模型和期货贸易模型等 遗传算法与神经网络相结 合正成功地被应用于从时间序列分析来进行财政预算等 1 2 遗传算法的基本原理遗传算法的基本原理 遗传算法是一种基于自然选择和群体遗传机制的搜索算法 它 模拟了自然选择和自然遗传过程中的繁殖 杂交和突变现象 在利 用遗传算法求解问题时 问题的每个可能的解都被编码成一个 染 色体 即个体 若干个个体构成了群体 所有可能解 在遗传算 法开始时 总是随机地产生一些个体 即初始解 根据预定的目标 函数对每个个体进行评估 给出了一个适应度值 基于此适应度值 选择个体用来复制下一代 选择操作体现了 适者生存 的原理 好 的个体被选择用来复制 而 坏 的个体则被淘汰 然后选 择出来的个体经过交叉和变异算子进行再结合生成新的一代 这一 群新个体由于继承了上一代的一些优良性状 因而在性能上要优于 上一代 这样逐步朝着更优解的方向进化 因此 遗传算法可以看 成是一个由可行解组成的群体逐步进化的过程 图给出了简单遗传 算法的基本过程 下面介绍遗传算法的编码及基本遗传操作过程 1 2 1 编码编码 利用遗传算法求解问题时 首先要确定问题的目标函数和变量 然后对变量进行编码 这样做主要是因为在遗传算法中 问题的解 是用数字串来表示的 而且遗传算子也是直接对串进行操作的 编 码方式可以分为二进制编码和实数编码 若用二进制数表示个体 则将二进制数转化为十进制数的解码公式可以为 l j j ij l ii iilii b RT RbbbF 1 1 21 2 12 其中 为某个个体的第 段 每段段长都为 每个 ilii bbb 21 il 都是 0 或者 1 和是第 段分量的定义域的两个端点 ik b i T i Ri i X 1 2 2 遗传操作遗传操作 遗传操作是模拟生物基因的操作 它的任务就是根据个体的适 应度对其施加一定的操作 从而实现优胜劣汰的进化过程 从优化 搜索的角度看 遗传操作可以使问题的解逐代的优化 逼近最优解 遗传操作包括以下三个基本遗传算子 选择 交叉 变异 选择和 交叉基本上完成了遗传算法的大部分搜索功能 变异增加了遗传算 法找到最接近最优解的能力 1 选择 选择是指从群体中选择优良的个体并淘汰劣质个体的操作 它 建立在适应度评估的基础上 适应度越大的个体 被选择的可能性 就越大 它的 子孙 在下一代的个数就越多 选择出来的个体被 放入配对库中 目前常用的选择方法有轮赌盘方法 也称适应度比例法 最佳 个体保留法 期望值法 排序选择法 竞争法 线性标准化方法等 2 交叉 交叉是指把两个父代个体的部分结构加以替换重组而生成新个 体的操作 交叉的目的是为了能够在下一代产生新的个体 通过交 叉操作 遗传算法的搜索能力得以飞跃性的提高 交叉是遗传算法 获得新优良个体的最重要的手段 交叉操作是按照一定的交叉概率在配对库中随机地选取两个 c P 个体进行的 交叉的位置也是随机确定的 交叉概率的值一般取 c P 得很大 为 0 6 0 9 3 变异 变异就是以很小的变异概率随机地改变群体中个体的某些基 m P 因的值 变异操作的基本过程是 产生一个之间的随机数 10rand 如果 则进行变异操作 m Prand 变异操作本身是一种局部随机搜索 与选择 交叉算子结合在 一起 能够避免由于选择和交叉算子而引起的某些信息的永久性丢 失 保证了遗传算法的有效性 使遗传算法具有局部的随机搜索能 力 同时使得遗传算法能够保持群体的多样性 以防止出现未成熟 收敛 变异操作是一种防止算法早熟的措施 在变异操作中 变异 概率不能取值太大 如果 遗传算法就退化为随机搜索 50 m P 而遗传算法的一些重要的数学特性和搜索能力也就不复存在了 1 3 基本步骤基本步骤 遗传算法的基本步骤如下 1 在一定编码方案下 随机产生一个初始种群 2 用相应的解码方法 将编码后的个体转换成问题空间的决策变量 并求得个体的适应值 3 按照个体适应值的大小 从种群中选出适应值较大的一些个体构 成交配池 4 由交叉和变异这两个遗传算子对交配池中的个体进行操作 并形 成新一代的种群 5 反复执行步骤 2 4 直至满足收敛判据为止 使用遗传算法需要决定的运行参数有 编码串长度 种群大小 交叉和变异概率 编码串长度优优化问题所要求的求解精度决定 种群大小表示种群中所含个体的数量 种群较小时 可提高遗传算 法的运算速度 但却降低了群体的多样性 可能找不到最优解 种 群较大时 又会增加计算量 使遗传算法的运行效率降低 一般取 种群数目为 20 100 交叉概率控制着交叉操作的频率 由于交叉操作 是遗传算法中产生新个体的主要方法 所以交叉概率通常应取较大 值 但若过大的话 又可能破坏群体的优良模式 一般取 0 4 0 99 变异概率也是影响新个体产生的一个因素 变异概率小 产生新个 体少 变异概率太大 又会使遗传算法变成随机搜索 一般取变异 概率为 0 0001 0 1 遗传算法常采用的收敛判据有 规定遗传代数 连续几次得到的最优个体的适应值没有变化或变化很小等 1 4 用用 MATLAB 实现遗传算法实现遗传算法 MATLAB 是 Matwork 公司的产品 是一个功能强大的数学软件 其优秀的数值计算能力使其在工业界和学术界的使用率都非常高 MATLAB 还十分便于使用 它以直观 简洁并符合人们思维习惯的 代码给用户提供了一个非常友好的开发环境 利用 MATLAB 处理矩 阵运算的强大功能来编写遗传算法程序有着巨大的优势 1 4 1 编码编码 遗传算法不对优化问题的实际决策变量进行操作 所以应用遗 传算法首要的问题是通过编码将决策变量表示成串结构数据 本文 中我们采用最常用的二进制编码方案 即用二进制数构成的符号串 来表示一个个体 用下面的 encoding 函数来实现编码并产生初始种 群 function bin gen bits encoding min var max var scale var popsize bits ceil log2 max var min var scale var bin gen round rand popsize sum bits end 在上面的代码中 首先根据各决策变量的下界 min var 上 界 max var 及其搜索精度 scale var 来确定表示各决策变量的二 进制串的长度 bits 然后随机产生一个种群大小为 popsize 的初始种 群 bit gen 编码后的实际搜索精度为 scale dec max var min var 2 bits 1 该精度会在解码时用到 1 4 2 解码解码 解码后的个体构成的种群 bin gen 必须经过解码 以转换成原问题 空间的决策变量构成的种群 var gen 方能计算相应的适应值 我们 用下面的代码实现 function var gen fitness decoding funname bin gen bits min var max var num var length bits popsize size bin gen 1 scale dec max var min var 2 bits 1 bits cumsum bits bits 0 bits for i 1 num var bin var i bin gen bits i 1 bits i 1 var i sum ones popsize 1 2 size bin var i 2 1 1 0 bin var i 2 scale dec i min var i end var gen var 1 for i 1 popsize fitness i eval funname var gen i end end 解码函数的关键在于先由二进制数求得对应的十进制数 D 并根据 下式求得实际决策变量值 X varmin scale decDX 1 4 3 选择选择 选择过程是利用解码后求得的各个适应值大小 淘汰一些较差个体 而选出一些比较优良的个体 以进行下一步的交叉和变异操作 选 择算子的程序如下 function evo gen best indiv best var max fitness selection old gen fitness var gen popsize length fitness max fitness index1 max fitness min fitness index2 min fitness best indiv old gen index1 best var var gen index1 index 1 popsize index index1 0 index index2 0 index nonzeros index evo gen old gen index evo fitness fitness index evo popsize length index ps evo fitness sum evo fitness pscum transpose cumsum ps r rand 1 evo popsize selected sum pscum ones 1 evo popsize ones evo popsize 1 r 1 evo gen evo gen selected end 在该算子中 采用了最优保存策略和比例选择法相结合的思路 即 首先找出当前群体中适应值最高和最低的个体 将最佳个体 best indiv 保存并用其替换掉最差个体 为保证当前最佳个体不被交 叉 变异操作所破坏 允许其不参与交叉和变异而直接进入下一代 然后将剩下的个体 evo gen 按比例选择法进行操作 所谓比例选择 法 也叫赌轮算法 是指个体被选中的概率与该个体的适应值大小 成正比 将这两种方法想结合的目的是 在遗传操作中 不仅能不 断提高群体的平均适应值 而且能保证最佳个体的适应值不减小 1 4 4 交叉交叉 下面采用单点交叉的方法来实现交叉算子 即按选择概率 PC 在两两 配对的个体编码串 cpairs 中随机设置一个交叉点 cpoints 然后在该 点相互交换两个配对个体的部分基因 从而形成两个新的个体 交 叉算子的程序如下 function new gen crossover old gen pc nouse mating sort rand size old gen 1 1 mat gen old gen mating pairs size mat gen 1 2 bits size mat gen 2 cpairs rand pairs 1 pc cpoints randint pairs 1 1 bits cpoints cpairs cpoints for i 1 pairs new gen 2 i 1 2 i mat gen 2 i 1 2 i 1 cpoints i mat gen 2 i 2 i 1 cpoints i 1 bits end end 1 4 5 变异变异 对于二进制的基因串而言 变异操作就是按照变异概率 pm 随机选 择变异点 mpoints 在变异点处将其位取反即可 变异算子的实现过 程如下 function new gen mutation old gen pm mpoints find rand size old gen pm new gen old gen new gen mpoints 1 old gen mpoints 1 5 应用实例应用实例 上述程序已经考虑了多参数编码问题 可以用于搜索多变量函数的 最优解 为简单起见 下面仅以一个单变量函数为例 来验证所编 遗传算法程序的全局寻优能力 设函数为 函数特性如图 1 所示 cos 7 5sin 10914 xxxxy 图 1 函数特性示意图 取种群大小 popsize 40 搜索精度 scale var 0 0001 交叉概率 pc 0 85 变异概率 pm 0 05 图 2 和图 3 是某一次运算遗传 40 代后 最佳个体和最佳适应值的变化情况 图 2 最佳个体的变化情况 图 3 最佳个体适应值的增长情况 由于采用了最优保存策略 所以在图 3 中未看到最佳个体适应值减 少的现象 由图 2 可见 在前三代种群中适应值最大的个体解码后 的值为 7 8681 落在函数的一个局部极值处 但是搜索并没有在此 处停滞 很快就跃到了另一个更大的极值点 7 8538 附近 搜索继续 经过几次跳跃 我们发现在 7 85 附近搜索多次后 连续几次得到的 最优个体的适应值变化很小 可以认为找到全局最大值 全局最大 值点为 7 8567 最大值为 24 8554 下列程序为主函数 Example clear clc close popsize 40 种群的个体个数 scale var 0 0001 搜索精度 pc 0 85 交叉概率 pm 0 05 变异概率 min var 0 函数定义域下界 max var 9 函数定义域上界 bin gen bits encoding min var max var scale var popsize 随机产生初始群体 old gen bin gen t 0 T 40 Max f Best var while t T var gen fitness decoding fun old gen bits min var max var evo gen best indiv best var max fitness selection old gen fitness var gen conew gen crossover evo gen pc munew gen mutation conew gen pm new gen munew gen best indiv best indiv old gen new gen Best var Best var best var Max f Max f max fitness t t 1 end disp 最大值为 num2str max fitness disp 全局最大值点为 num2str best var figure ezplot fun min var max var xlabel x ylabel f x title f x x 10sin 5x 7cos 4x figure plot Best var g linewidth 5 xlabel 遗传代数 ylabel 最佳个体解码值 title 最佳个体的变化情况 figure plot Max f c linewidth 5 xlabel 遗传代数 ylabel 最佳适应值 title 最佳适应值的变化情况 定义的函数为 function f fun x f x 10 sin 5 x 7 cos 4 x 2 蚁群算法 2 1 蚁群算法起源及发展蚁群算法起源及发展 蚁群算法是一种源于大自然生物世界的仿生类算法 作为通用 型随机优化方法 它吸收了昆虫王国中蚂蚁的行为特性 通过其内 在的搜索机制 在一系列困难的组合优化问题求解中取得了成效 由于在模拟仿真中使用的是人工蚂蚁概念 因此 有时也称为蚂蚁 系统 蚂蚁是一种古老的社会性昆虫 种类成千上万 分布遍及世界 各地 其共同特征是群居生活 每一种群都有着严格的社会结构 不同蚂蚁有着不同的分工 因此 虽然蚂蚁个体的结构和行为都比 较简单 但是由这些简单个体组成的群体 即 蚁群 系统却高度 复杂 所能完成的任务复杂程度远远超出每个个体的能力 除了 蚁群 系统具有高度的分工协作之外 蚂蚁个体之间还存在着一 种信息传递机制 这也是使得系统能够高效有序运转的重要原因 据昆虫学家的观察和研究发现 生物世界中的蚂蚁有能力在没有任 何可见提示下找出其巢穴至食物源的最短路径 并能随环境的变化 而变化 适应性地搜索新的路径 产生新的选择 作为昆虫的蚂蚁 在寻找食物源时 能在其走过的路径上释放一种蚂蚁特有的分泌物 信息素 使得一定范围内的其他蚂蚁能够察觉到并由此影响它 们以后的行为 当一些路径上通过的蚂蚁越来越多时 其留下的信 息素轨迹也越来越多 以致信息素强度增大 随时间的推移会逐渐 减弱 后来蚂蚁选择该路径的概率也越高 从而更增加了该路径的 信息素强度 这种选择过程被称为蚂蚁的自催化行为 受到蚁群系统信息共享机制的启发 意大利学者 Dorigo 于 1992 年在他的博士论文中首次系统提出了蚁群算法 并成功地将该方法 应用于其解旅行商问题和二次分配问题 QAP 中 引起了大家的 广泛关注 之后 蚁群算法很快陆续渗透到其他问题领域中 如工 件排序问题 图着色问题 车辆调度问题 大规模集成电路设计 通信网络中的负载平衡问题等 蚁群算法越来越引起人们的重视 2 2 蚁群算法的原理蚁群算法的原理 用于优化领域的蚁群算法吸收了生物界中蚁群群体行为特征 其原理在于 1 感知小范围区域内状况 并判断出是否有食物或其他同伴 的信息素轨迹 2 释放自己的信息素 3 所遗留的信息素数量会随时间而逐步减少 由于自然界中的蚂蚁基本没有视觉 既不知向何处去寻找和获 取食物 也不知发现食物后如何返回自己的巢穴 因此 它们仅仅 依赖于同类散发在周围环境中的信息素来决定自己何去何从 有趣 的是 尽管没有任何先验知识 但蚂蚁们还是有能力找到从巢穴到 食物源的最佳路径 甚至在该路线设置障碍物之后 它们仍然能很 快重新找到新的最佳路线 这里 用一个形象化的图来说明蚁群算 法的路径搜索原理和机制 a b c 注 a 是初始的距离图 d 表示距离 b 在 t 0 时刻 在各路径上没有信息素的遗 留 蚂蚁以等概率选择路径 c 在 t 1 时刻 比较短的边上信息素的遗留比较多 因此 这样的边容易被蚂蚁选择 在图 a 中 假设 F 是食物源 E 是蚁穴 蚂蚁的目的是把食 物带回蚁穴 显然 较短的路径比较长的路径有优势 假设在 t 0 时刻 这里有 150 只蚂蚁在点 C 另有 150 只蚂蚁在点 A 并且在 这一时刻任何一段路径都没有信息素的遗留 这样 每只蚂蚁都以 相同的概率随机地选择它们的路径 所以 从点 C 和 A 出发点蚂蚁 按概率都将各有 75 只走向 D 另外 75 只走向 B 图 b 当 t 1 时 又有 150 只蚂蚁从 F 走向 C 此时在 C 到 D 的路径上遗留了先 前从 C 经 D 到 A 的 75 只蚂蚁所遗留的信息素 而在 C 到 B 的路径 上则遗留了先前从 C 经 B 到 A 的 75 只蚂蚁以及从 A 经 B 到 C 的 75 只蚂蚁所遗留的信息素 蚂蚁在选择路径的时候依据各路径所遗留 信息素的浓度来进行选择 因此 按概率将有 100 只蚂蚁朝点 B 走 有 50 只蚂蚁朝点 D 走 由 E 点到 A 点也是相同的情况 图 c 这一过程反复进行 最终所有点蚂蚁都将选择到这条最短路径 即 CBA 这条边 蚂蚁有能力在没有任何提示下找到从其巢穴到食物源的最短路 径 并且能随环境的变化而变化 适应性地搜索新的路径 产生新 的选择 其根本原因是蚂蚁在寻找食物源时 能在其走过的路上释 放信息素 随着时间的推移该物质会逐渐挥发 后来的蚂蚁选择该 路径的概率与当时这条路径上该物质的强度成正比 当一定路径上 通过的蚂蚁越来越多时 其留下的信息素轨迹也越来越多 后来蚂 蚁选择该路径的概率也越高 从而更增加了该路径的信息素强度 而强度大的信息素会吸引更多的蚂蚁 从而形成一种正反馈机制 通过这种正反馈机制 蚂蚁最终可以发现最短路径 特别地 当蚂 蚁巢穴与食物源之间出现障碍物时 蚂蚁不仅可以绕过障碍物 而 且通过蚁群信息素轨迹在不同路径上的变化 经过一段时间的正反 馈 最终收敛到最短路径上 2 3 基本蚁群算法数学模型基本蚁群算法数学模型 为了便于理解 现用求解平面上 个城市的 TSP 问题为例来说明n 基本蚁群算法模型 假设将只蚂蚁随机放在 个城市上 表示城市 和城市之mn ij dij 间的距离 表示 时刻城市 和城市连线上的信息量 即路 t ij tij 径的信息量 初始时刻 各条路径上信息量相等 设 ji 为一个正常数 蚂蚁在运动过程中根C ij 0 C mkk21 据各条路径的信息量决定其转移方向 这里用禁忌表 来记录蚂蚁当前所走过的城市 集合随着 mktabuk21 k k tabu 蚁群进化过程做动态调整 表示 时刻蚂蚁由城市 转移到城 tp k ij tki 市的状态转移概率j 2 1 否否则则 若若 0 k alloweds isis ijij k ij allowedj tt tt tp k 其中 表示蚂蚁下一步允许选择的城市集合 则 k allowedk 为信息启发因子 为期望启发因子 kk tabuCallowed 为启发函数 对于某个确定的 TSP 问题 是一个常数 t ij t ij 其表达式如下 ij ij d t 1 其中 表示城市 和城市之间的距离 且 ij dij 22 jijiij yyxxd 其中 和分别是城市 和城市的坐标 ii yx jj yxij 为了避免路径上信息素的无限累计 导致某路径上残留的信息 素过多而淹没启发信息 在每只蚂蚁走完一步或者一个循环结束后 要对路径上的信息素进行更新处理 由此 在时刻 路径1 t 上的信息量可按如下规则调整 ji 2 2 ttt ijijij 11 2 3 m i k ijij tt 1 其中 是信息素挥发系数 则是信息素残留因子 且 1 10 表示本次循环中路径上信息素增量 初始时刻信息素的 t ij ji 增量为 0 即 为第只蚂蚁在本次循环中留在路00 ij t k ij k 径上的信息素 ji 这里 根据信息素不同的更新策略 即的不同求法将蚁 t k ij 群算法模型分为以下三种 Ant Cycle 模型 Ant Auantity 模型和 Ant Density 模型 1 Ant Cycle 模型 2 否否则则 之之间间经经过过和和只只蚂蚂蚁蚁在在若若第第 0 1jittk L Q t k k ij 4 2 Ant Quantity 模型 2 否否则则 之之间间经经过过和和只只蚂蚂蚁蚁在在若若第第 0 jittk d Q t ij k ij 1 5 3 Ant Density 模型 2 否否则则 之之间间经经过过和和只只蚂蚂蚁蚁在在若若第第 0 1jittkQ t k ij 6 以上各式中 均表示信息素强度 是一个常数 在这三个模型中 Q Ant Quantity 模型和 Ant Density 模型是当蚂蚁走完一步后更新其所 走路径上的信息素 是局部信息素更新 而 Ant Cycle 模型则是蚂蚁 完成一个循环后更新所有路径上的信息素 利用的是整体信息素更 新 我们通常采用 Ant Cycle 模型作为蚂蚁算法的基本模型 2 4 基本蚁群算法实现过程基本蚁群算法实现过程 以 Ant Cycle 模型为例来说明基本蚁群算法的具体实现步骤 Step1 初始化 设定算法迭代次数 设置最大循环次数 0 NC max NC 设置路径初始时刻的信息量 为常数 信息素 jiC ij 0 CQ 且初始时路径上的信息素增量为 0 即 ji00 ij Step2 算法的迭代过程 While NC NCmax for i 1 n 1 确保遍历所有的城市 for k 1 m 对 m 只蚂蚁进行循环 for j 1 n 对 n 个城市进行循环 蚂蚁 k 根据公式 2 1 选择转移到的下一个城市 j 并将城市 j 置入蚂蚁 k 的禁忌表 tabuk中 end 结束对城市的循环 end 结束对蚂蚁的循环 end 结束对 i 的循环 计算所有蚂蚁求得的路径长度 根据公式 2 2 2 3 和 2 4 更新路径 i j 上的信息素 NC NC 1 end Step3 结束算法 输出结果 2 5 用于连续函数优化的蚁群算法用于连续函数优化的蚁群算法 2 5 1 一元连续函数优化一元连续函数优化 对于任何一个连续函数优化问题 都可以通过一定的变换而成 为一个在 0 1 上的函数最小化问题 其中 加上Cxf min 10 x 一个常数以使函数值大于 0 对于端点值 可以通过直接与除去端C 点计算出的最小值比较的方法确定是否为最小 因此下面不考虑端 点值 设问题要求自变量精确到小数点后位 则自变量可以用个dxd 十进制数来近似表示 就可以构造如下个 城市 这些城210 d 市分为层 其中首尾两层分别仅含一个城市 一个为起始城市 2 d 一个为终止城市 中间层 从左往右分别表示自变量的十分位 d 百分位 这些城市中 只有与层 1 kk 22 dk 之间的各个城市有连接通路 记层中代表十进制数 的城市与1 ka 层中代表十进制数 的城市之间的连接上残留的信息量为 蚂kb k ab 蚁 在一次循环中的第步所在的城市用表示 设蚂蚁总数为nm mnT 0 N 首先用一个较小的值初始化所有的 让每只蚂蚁的第一步 0 k ab 为 0 即令 然后 就为每一只蚂蚁选择路 0 2101NnnT 径 若蚂蚁 当前所在的城市为 根据如下公式选择每naknT 1 只蚂蚁下一步应该到达的城市 2 7 否否则则 如如果果 max arg r k ab S Qq knT 0 其中 是随机数 是一个上的常数 用于确定伪随机选择的q 0 Q 10 概率 表示用伪随机选择来确定下一步要走的城市 也就是根据 r S 下式选择下一层中每一个城市的概率 然后按此概率用遗传算法中 的转盘式选择法确定要选择的城市 2 8 9 0 x k ax k ab bap 其中 表示从当前城市 转移到下一层的城市 的概率 由于 bapab 本算法中仅允许蚂蚁由上一层城市向下一层转移 所以这个公式与 普通蚁群算法的转移概率计算公式有所不同 当每只蚂蚁按上面的公式到达了层时 都将转移到层1 d2 d 的唯一的城市 0 蚂蚁在城市上建立路径的过程中 要不断地在经过的路径上按 公式 2 9 减弱上面残留的信息 这样可以减少下一只蚂蚁选择同 样路径的概率 除非经过多次循环后已确定一条极优的路径 这个 过程叫做残留信息的局部更新 2 9 011 1 k knTknT k knTknT 其中 为常数 表示路径上残留信息减弱的速度 10 当所有蚂蚁都按上面的步骤完成了一次循环 这时就对路径上 的信息进行全局更新 首先对蚂蚁选择的路径解码 计算出蚂蚁 对应的自变量值 n 2 10 1 2 1 10 d k k knTnx 计算每只蚂蚁对应的函数值 并选择出函数值最小的蚂蚁 2 11 min arg min nxfn 对这只最优蚂蚁经过的路径按下式做全局更新 2 12 1 1 min nfa k ij k ij 其中 为上的常 minmin 221 dkknTjknTi 10 数 至此就完成了一个循环 反复进行上面的步骤直到达到指定的 循环次数或得到的解在一定循环次数后没有改进 文中提出的求解一元连续函数优化问题的蚁群算法具体描述如 下 1 初始化 2 将所有蚂蚁置于初始城市 3 对所有的到层城市执行步骤 4 8 1 kk 4 对每只蚂蚁执行步骤 5 6 5 根据公式 2 7 和 2 8 选择蚂蚁在第层应该到达的城市 k 6 每只蚂蚁选择城市后都立即按公式 2 9 执行局部更新规则 7 根据公式 2 10 2 12 评选出最优蚂蚁并执行全局更新规 则 8 判断是否满足终止条件 满足则输出结果结束计算 2 5 2 多元连续函数优化多元连续函数优化 对于多元连续函数的优化问题 设自变量由个分量组成 并 x n 要求自变量的每一个分量都精确到小数点后位 则可构造一副由d 层城市组成 且第1 xx ndn 层由 1 个标号为 0 的城市组成 13221 xx ndndd 其余层都由标号为 0 到 9 的 10 个城市组成 第到211 dk 层表示自变量的第个分量 其余层都是 1 dk x nk21 k 辅助层 解码时 就对各分量对应的层分别解码 采用这种方法 每个自变量分量的最后一位与下一个分量的第 一位之间都有辅助层隔开 因此前面一个分量的末位就不会影响后 面一个分量首位 除了这一点以外 其余部分都与一元连续函数的优化方法相同 这里就不再详细介绍了 2 5 3 应用实例应用实例 为了与遗传算法作比较 下面取与 1 5 中一样的函数为 采用的参数如下 cos 7 5sin 10914 xxxxy80 运行循环次数为 80 80 0 Q010 10 d20 0 N 50 2 5 3 1 算法具体代码描述算法具体代码描述 具体分成两部分 调用函数部分和主函数部分 一 调用函数部分 转移规则子函数 5 根据公式 1 和 2 选择蚂蚁 n 在第 k 层应该到达的城市 Tau 任意两个城市之间的信息素 三个维度 第一维表示第几层 第二维表示 Q0 是一个常数 主要是作为轮盘赌法的临界点 k 代表目前进展到第几层 1 d 2 a 第 k 1 层的节点下标 d 代表小数位数 T 每只蚂蚁的路径矩阵 n 第 n 只蚂蚁 function b select k city Tau Q0 n k T a T n k 1 1 第 n 只蚂蚁第 k 1 层的所在城市编码 注意 城市编码从 1 10 q rand num 100 轮盘赌次数 P Select if q Q0 b find Tau k a max Tau k a else P Tau k a sum Tau k a Select Roulette P num row col len size Tau for i 1 len Ps i sum Select i num end b find Ps max Ps end 轮盘赌法子函数 轮盘赌法程序 function Select Roulette P num m length P Select zeros 1 num r rand 1 num for i 1 num sumP 0 j ceil m rand 产生 1 m 之间的随机整数 while sumP r i sumP sumP P mod j 1 m 1 j j 1 end Select i mod j 2 m 1 end 局部更新规则子函数 6 每只蚂蚁选择城市后都立即按公式 3 执行局部更新规则 需要输入 rou tao0 T Tau k 第 k 层 Tau 两层之间的信息素 Rho 比例 tao0 剩余信息素 0 01 T 每一只蚂蚁下一步到达的城市 第一维是第几只蚂蚁 第二位是目前是第几步 n 第几只蚂蚁 function Tau update tao Tau Rho tao0 T k n i T n k 1 j T n k 1 1 Tau k j i 1 Rho Tau k j i Rho tao0 全局更新规则子函数 test7 7 根据公式 4 6 评选出最优蚂蚁并执行全局更新规则 共有 n 只蚂蚁 tau 层与层之间的信息素 d 是小数点后精确到 d 位 X 所有蚂蚁的具体数值数组 idx 最小的蚂蚁编码 也就是数组下标 alpha 是一常量 function Tau f min var min update all tao Tau N alpha d T X zeros N 1 for j 1 N for i 2 d 1 X j X j T j i 10 1 i end end 选择出蚂蚁的最小值 F for i 1 N f myfunction X i F F f end f min min F idx find F f min var min X idx 1 蚂蚁经过路径全局性更新 for k 2 d 1 i T idx k 1 1 j T idx k 1 Tau k i j 1 alpha Tau k i j alpha 1 f min end 定义连续函数子函数 function myvalue myfunction x y 8 x 1 myvalue y 10 sin 5 y 7 cos 4 y 30 二 主函数部分 主函数 test lianxu function 第一层和最后一层只有 0 中间层都是 0 9 len T