大连海事大学-刘巍-高等运筹第十六讲

高等运筹学 大连海事大学刘巍 目录 第一篇运筹学发展历史第二篇运筹学中的数学规划第三篇运筹学中的组合优化第四篇运筹学中的随机优化第五篇运筹学中的博弈论第六篇运筹学中管理科学第七篇运筹学中智能计算第八篇运筹学发展势态 第六篇运筹学中的智能计算 第二十三章遗传算法第二十四章模拟退火第二十五章蚁群算法第二十六章人工神经网络 4 第章群体智能与蚁群算法第1节群体智能 SwarmIntelligence 5 研究意义 群体智能概念 群体智能这个概念来自对蜜蜂和蚂蚁的观察 一组相互之间可以进行直接通信或者间接通信 通过改变局部环境 的主体 这组主体能够合作进行分布问题求解 任何启发于群居性昆虫群体和其它动物群体的集体行为而设计的算法和分布式问题解决装置都称为群体智能 群体智能在没有集中控制并且不提供全局模型的前提下 为寻找复杂的分布式问题的解决方案提供了基础 6 研究意义 群体智能的特点 分布式 能够适应当前网络环境下的工作状态 鲁棒性 没有中心的控制与数据 个体的故障不影响整个问题的求解 扩充性 个体的增加 系统的通信开销增加小 简单性 个体简单 实现也比较简单 7 研究意义 群体智能的研究不仅在多主体仿真 系统复杂性以及NP问题等方面为人工智能 认识科学 计算经济学等领域的基础理论问题的研究开辟了新的研究途径 同时也为诸如组合优化 机器人协作 电信路由控制等实际工程问题提供了新的解决方法 因此 群体智能的研究具有重要意义和广阔的应用前景 8 研究现状 国外 美国的SDG组织在系统复杂性方面开展了研究 他们主要通过多主体的仿真来研究系统复杂性 他们开发的SWARM软件包为多学科进行基于多主体的建模提供了一个基础平台 加州工学院专门开设了群体智能的课程 欧洲联盟资助的SWARM BOTS项目的主要目标是研究设计和实现自组织和自装配的装置的新途径 它的理论基础是群体智能和蚁群算法的近期研究成果 即对群居性昆虫和其它动物群体的自组织和自装配能力的研究 9 研究现状 国内 国家自然科学基金在 十五 期间学科交叉类优先资助领域第一类属于把握科学前沿 推动源头创新的项目 其中第7项认知科学及其信息处理的研究内容就明确列出了群体智能的进化 自适应与现场认知 相关项目还有第9项复杂系统与复杂性 10 主要研究方向 蚁群寻食行为研究 相对应组合优化算法和通信网络路由控制算法 群体分工和任务分配行为研究 相对应多主体分工协作算法 巢穴组织和自组织行为及群体分类行为研究 相对应数据分析和图的分割算法 建巢和自装配行为研究 相对应模拟建巢算法 群体合作搬运行为研究 相对应机器人合作搬运算法 11 所需解决的关键问题 蚁群算法效率与理论 由于没有标准的测试集 除了寻食模型 蚁卵聚类 蚁群分工和蚁巢自装配等模型都只处于证实阶段理论和实验 一个多主体自组织模型实验和测试平台 对于追求效率的实际问题 如何既保持群体智能系统的灵活性和鲁棒性等自组织特征又能保证系统的高效率也是一个关键问题 群体智能与分布式智能的智能主体研究相结合 将产生新的智能主体协作 建模等算法和机制 提出网络和网格环境的自适应多智能主体系统 12 蚁群算法原型 A 蚁群到达决策点 B 一些蚂蚁选择上方路径 一些蚂蚁选择下方路径 选择是随机的 C 下方短路径蚂蚁到达相反方向的决策点的时间早于选择上方长路径的蚂蚁 D 短路径上外激素以较高的速度积累 外激素多的短路径将吸收更多的蚂蚁 反过来 更多的蚂蚁在短路径上会留下更多的外激素 加上外激素挥发效应 最后 蚁群都选择了最短路径 13 蚁群优化算法研究现状1 7 90年代Dorigo最早提出了蚁群优化算法 蚂蚁系统 AntSystem AS 并将其应用于解决计算机算法学中经典的旅行商问题 TSP 从蚂蚁系统开始 基本的蚁群算法得到了不断的发展和完善 并在TSP以及许多实际优化问题求解中进一步得到了验证 这些AS改进版本的一个共同点就是增强了蚂蚁搜索过程中对最优解的探索能力 它们之间的差异仅在于搜索控制策略方面 而且 取得了最佳结果的ACO是通过引入局部搜索算法实现的 这实际上是一些结合了标准局域搜索算法的混合型概率搜索算法 有利于提高蚁群各级系统在优化问题中的求解质量 14 蚁群优化算法研究现状2 7 最初提出的AS有三种版本 Ant density Ant quantity和Ant cycle 在Ant density和Ant quantity中蚂蚁在两个位置节点间每移动一次后即更新信息素 而在Ant cycle中当所有的蚂蚁都完成了自己的行程后才对信息素进行更新 而且每个蚂蚁所释放的信息素被表达为反映相应行程质量的函数 通过与其它各种通用的启发式算法相比 在不大于75城市的TSP中 这三种基本算法的求解能力还是比较理想的 但是当问题规模扩展时 AS的解题能力大幅度下降 因此 其后的ACO研究工作主要都集中于AS性能的改进方面 较早的一种改进方法是精英策略 ElitistStrategy 其思想是在算法开始后即对所有已发现的最好路径给予额外的增强 并将随后与之对应的行程记为Tgb 全局最优行程 当进行信息素更新时 对这些行程予以加权 同时将经过这些行程的蚂蚁记为 精英 从而增大较好行程的选择机会 这种改进型算法能够以更快的速度获得更好的解 但是若选择的精英过多则算法会由于较早的收敛于局部次优解而导致搜索的过早停滞 15 蚁群优化算法研究现状3 7 为了进一步克服AS中暴露出的问题 提出了蚁群系统 AntColonySystem ACS 该系统的提出是以Ant Q算法为基础的 Ant Q将蚂蚁算法和一种增强型学习算法Q learning有机的结合了起来 ACS与AS之间存在三方面的主要差异 首先 ACS采用了更为大胆的行为选择规则 其次 只增强属于全局最优解的路径上的信息素 其中 0 1是信息素挥发参数 是从寻路开始到当前为止全局最优的路径长度 16 蚁群优化算法研究现状4 7 再次 还引入了负反馈机制 每当一只蚂蚁由一个节点移动到另一个节点时 该路径上的信息素都按照如下公式被相应的消除一部分 从而实现一种信息素的局部调整 以减小已选择过的路径再次被选择的概率 17 蚁群优化算法研究现状5 7 在对AS进行直接完善的方法中 MAX MINAntSystem是一个典型代表 该算法修改了AS的信息素更新方式 每次迭代之后只有一只蚂蚁能够进行信息素的更新以获取更好的解 为了避免搜索停滞 路径上的信息素浓度被限制在 MAX MIN 范围内 另外 信息素的初始值被设为其取值上限 这样有助于增加算法初始阶段的搜索能力 18 蚁群优化算法研究现状6 7 另一种对AS改进的算法是Rank basedVersionAS 与 精英策略 相似 在此算法中总是更新更好进程上的信息素 选择的标准是其行程长度决定的排序 且每个蚂蚁放置信息素的强度通过下式中的排序加权处理确定 其中 为每次迭代后放置信息素的蚂蚁总数 19 蚁群优化算法研究现状7 7 这种算法求解TSP的能力与AS 精英策略AS 遗传算法和模拟退火算法进行了比较 在大型TSP问题中 最多包含132座城市 基于AS的算法都显示出了优于GA和SA的特性 而且在Rank basedAS和精英策略AS均优于基本AS的同时 前者还获得了比精英策略AS更好的解 20 蚁群优化算法应用现状1 5 随着群智能理论和应用算法研究的不断发展 研究者已尝试着将其用于各种工程优化问题 并取得了意想不到的收获 多种研究表明 群智能在离散求解空间和连续求解空间中均表现出良好的搜索效果 并在组合优化问题中表现突出 蚁群优化算法并不是旅行商问题的最佳解决方法 但是它却为解决组合优化问题提供了新思路 并很快被应用到其它组合优化问题中 比较典型的应用研究包括 网络路由优化 数据挖掘以及一些经典的组合优化问题 21 蚁群优化算法应用现状2 5 蚁群算法在电信路由优化中已取得了一定的应用成果 HP公司和英国电信公司在90年代中后期都开展了这方面的研究 设计了蚁群路由算法 AntColonyRouting ACR 每只蚂蚁就像蚁群优化算法中一样 根据它在网络上的经验与性能 动态更新路由表项 如果一只蚂蚁因为经过了网络中堵塞的路由而导致了比较大的延迟 那么就对该表项做较大的增强 同时根据信息素挥发机制实现系统的信息更新 从而抛弃过期的路由信息 这样 在当前最优路由出现拥堵现象时 ACR算法就能迅速的搜寻另一条可替代的最优路径 从而提高网络的均衡性 负荷量和利用率 目前这方面的应用研究仍在升温 因为通信网络的分布式信息结构 非稳定随机动态特性以及网络状态的异步演化与ACO的算法本质和特性非常相似 22 蚁群优化算法应用现状3 5 基于群智能的聚类算法起源于对蚁群蚁卵的分类研究 Lumer和Faieta将Deneubourg提出将蚁巢分类模型应用于数据聚类分析 其基本思想是将待聚类数据随机地散布到一个二维平面内 然后将虚拟蚂蚁分布到这个空间内 并以随机方式移动 当一只蚂蚁遇到一个待聚类数据时即将之拾起并继续随机运动 若运动路径附近的数据与背负的数据相似性高于设置的标准则将其放置在该位置 然后继续移动 重复上述数据搬运过程 按照这样的方法可实现对相似数据的聚类 23 蚁群优化算法应用现状4 5 ACO还在许多经典组合优化问题中获得了成功的应用 如二次规划问题 QAP 机器人路径规划 作业流程规划 图着色 GraphColoring 等问题 经过多年的发展 ACO已成为能够有效解决实际二次规划问题的几种重要算法之一 AS在作业流程计划 Job shopScheduling 问题中的应用实例已经出现 这说明了AS在此领域的应用潜力 利用MAX MINAS解决PAQ也取得了比较理想的效果 并通过实验中的计算数据证明采用该方法处理PAQ比较早的SA算法更好 且与禁忌搜索算法性能相当 利用ACO实现对生产流程和特料管理的综合优化 并通过与遗传 模拟退火和禁忌搜索算法的比较证明了ACO的工程应用价值 24 蚁群优化算法应用现状5 5 许多研究者将ACO用于了武器攻击目标分配和优化问题 车辆运行路径规划 区域性无线电频率自动分配 Bayesiannetworks的训练和集合覆盖等应用优化问题 Costa和Herz还提出了一种AS在规划问题方面的扩展应用 图着色问题 并取得了可与其他启发式算法相比的效果 25 第2节蚁群优化算法概念 2 1蚁群算法原理2 2简化的蚂蚁寻食过程2 3自然蚁群与人工蚁群算法2 4蚁群算法与TSP问题2 5初始的蚁群优化算法 基于图的蚁群系统 GBAS 2 6一般蚁群算法的框架2 7蚁群优化算法 技术问题 26 2 1蚁群算法原理 蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法 蚂蚁在运动过程中 能够在它所经过的路径上留下一种称之为外激素 pheromone 的物质进行信息传递 而且蚂蚁在运动过程中能够感知这种物质 并以此指导自己的运动方向 因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象 某一路径上走过的蚂蚁越多 则后来者选择该路径的概率就越大 为了说明蚁群算法的原理 先简要介绍一下蚂蚁搜寻食物的具体过程 在蚁群寻找食物时 它们总能找到一条从食物到巢穴之间的最优路径 这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素 当它们碰到一个还没有走过的路口时 就随机地挑选一条路径前行 与此同时释放出与路径长度有关的信息素 路径越长 释放的激索浓度越低 当后来的蚂蚁再次碰到这个路口的时候 选择激素浓度较高路径概率就会相对较大 这样形成一个正反馈 最优路径上的激索浓度越来越大 而其它的路径上激素浓度却会随着时间的流逝而消减 最终整个蚁群会找出最优路径 27 2 2简化的蚂蚁寻食过程1 3 蚂蚁从A点出发 速度相同 食物在D点 可能随机选择路线ABD或ACD 假设初始时每条分配路线一只蚂蚁 每个时间单位行走一步 本图为经过9个时间单位时的情形 走ABD的蚂蚁到达终点 而走ACD的蚂蚁刚好走到C点 为一半路程 28 简化的蚂蚁寻食过程2 3 本图为从开始算起 经过18个时间单位时的情形 走ABD的蚂蚁到达终点后得到食物又返回了起点A 而走ACD的蚂蚁刚好走到D点 29 简化的蚂蚁寻食过程3 3 假设蚂蚁每经过一处所留下的信息素为一个单位 则经过36个时间单位后 所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物 此时ABD的路线往返了2趟 每一处的信息素为4个单位 而ACD的路线往返了一趟 每一处的信息素为2个单位 其比值为2 1 寻找食物的过程继续进行 则按信息素的指导 蚁群在ABD路线上增派一只蚂蚁 共2只 而ACD路线上仍然为一只蚂蚁 再经过36个时间单位后 两条线路上的信息素单位积累为12和4 比值为3 1 若按以上规则继续 蚁群在ABD路线上再增派一只蚂蚁 共3只 而ACD路线上仍然为一只蚂蚁 再经过36个时间单位后 两条线路上的信息素单位积累为24和6 比值为4 1 若继续进行 则按信息素的指导 最终所有的蚂蚁会放弃ACD路线 而都选择ABD路线 这也就是前面所提到的正反馈效应 30 2 3自然蚁群与人工蚁群算法 基于以上蚁群寻找食物时的最优路径选择问题 可以构造人工蚁群 来解决最优化问题 如TSP问题 人工蚁群中把具有简单功能的工作单元看作蚂蚁 二者的相似之处在于都是优先选择信息素浓度大的路径 较短路径的信息素浓度高 所以能够最终被所有蚂蚁选择 也就是最终的优化结果 两者的区别在于人工蚁群有一定的记忆能力 能够记忆已经访问过的节点 同时 人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径 而不是盲目的 例如在TSP问题中 可以预先知道当前城市到下一个目的地的距离 31 2 4蚁群算法与TSP问题1 3 TSP问题表示为一个N个城市的有向图G N A 其中城市之间距离目标函数为 其中为城市1 2 n的一个排列 32 蚁群算法与TSP问题2 3 TSP问题的人工蚁群算法中 假设m只蚂蚁在图的相邻节点间移动 从而协作异步地得到问题的解 每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定 1信息素值也称信息素痕迹 2可见度 即先验值 信息素的更新方式有2种 一是挥发 也就是所有路径上的信息素以一定的比率进行减少 模拟自然蚁群的信息素随时间挥发的过程 二是增强 给评价值 好 有蚂蚁走过 的边增加信息素 33 蚁群算法与TSP问题3 3 蚂蚁向下一个目标的运动是通过一个随机原则来实现的 也就是运用当前所在节点存储的信息 计算出下一步可达节点的概率 并按此概率实现一步移动 逐此往复 越来越接近最优解 蚂蚁在寻找过程中 或者找到一个解后 会评估该解或解的一部分的优化程度 并把评价信息保存在相关连接的信息素中 34 2 5初始的蚁群优化算法 基于图的蚁群系统 GBAS 1 12 初始的蚁群算法是基于图的蚁群算法 graph basedantsystem 简称为GBAS 是由GutjahrWJ在2000年的FutureGenerationComputingSystems提出的 课本的参考文献2 算法步骤如下 STEP0对n个城市的TSP问题 城市间的距离矩阵为 给TSP图中的每一条弧赋信息素初值 假设m只蚂蚁在工作 所有蚂蚁都从同一城市出发 当前最好解是 35 初始的蚁群优化算法 基于图的蚁群系统 GBAS 2 12 STEP1 外循环 如果满足算法的停止规则 则停止计算并输出计算得到的最好解 否则使蚂蚁s从起点出发 用表示蚂蚁s行走的城市集合 初始为空集 STEP2 内循环 按蚂蚁的顺序分别计算 当蚂蚁在城市i 若完成第s只蚂蚁的计算 否则 若 则以概率 到达j 若则到达重复STEP2 36 初始的蚁群优化算法 基于图的蚁群系统 GBAS 3 12 STRP3对 若 按中城市的顺序计算路径程度 若 路径长度置为一个无穷大值 即不可达 比较m只蚂蚁中的路径长度 记走最短路径的蚂蚁为t 若 则 用如下公式对W路径上的信息素痕迹加强 对其他路径上的信息素进行挥发 得到新的 重复步骤STEP1 37 初始的蚁群优化算法 基于图的蚁群系统 GBAS 4 12 在STEP3中 挥发因子对于一个固定的 满足并且经过k次挥发 非最优路径的信息素逐渐减少至消失 38 初始的蚁群优化算法 基于图的蚁群系统 GBAS 5 12 以上算法中 在蚂蚁的搜寻过程中 以信息素的概率分布来决定从城市i到城市j的转移 算法中包括信息素更新的过程1信息素挥发 evaporation 信息素痕迹的挥发过程是每个连接上的信息素痕迹的浓度自动逐渐减弱的过程 由表示 这个挥发过程主要用于避免算法过快地向局部最优区域集中 有助于搜索区域的扩展 2信息素增强 reinforcement 增强过程是蚁群优化算法中可选的部分 称为离线更新方式 还有在线更新方式 这种方式可以实现由单个蚂蚁无法实现的集中行动 也就是说 增强过程体现在观察蚁群 m只蚂蚁 中每只蚂蚁所找到的路径 并选择其中最优路径上的弧进行信息素的增强 挥发过程是所有弧都进行的 不于蚂蚁数量相关 这种增强过程中进行的信息素更新称为离线的信息素更新 在STEP3中 蚁群永远记忆到目前为止的最优解 39 图的蚁群系统 GBAS 6 12 可以验证 下式满足 即是一个随机矩阵 四个城市的非对称TSP问题 距离矩阵和城市图示如下 40 初始的蚁群优化算法 基于图的蚁群系统 GBAS 7 12 假设共4只蚂蚁 所有蚂蚁都从城市A出发 挥发因子 此时 观察GBAS的计算过程 矩阵共有12条弧 初始信息素记忆矩阵为 41 初始的蚁群优化算法 基于图的蚁群系统 GBAS 8 12 执行GBAS算法的步骤2 假设蚂蚁的行走路线分别为 当前最优解为 这个解是截止到当前的最优解 碰巧是实际最优解 42 初始的蚁群优化算法 基于图的蚁群系统 GBAS 9 12 按算法步骤3的信息素更新规则 得到更新矩阵这是第一次外循环结束的状态 43 初始的蚁群优化算法 基于图的蚁群系统 GBAS 10 12 重复外循环 由于上一次得到的W2已经是全局最优解 因此按算法步骤3的信息素更新规则 无论蚂蚁如何行走 都只是对W2路线上的城市信息素进行增强 其他的城市信息素进行挥发 得到更新矩阵这是第一次外循环结束的状态 44 初始的蚁群优化算法 基于图的蚁群系统 GBAS 11 12 重复外循环 由于W2全局最优解 GBAS只记录第一个最优解 因此一但得到了全局最优解 信息素的更新将不再依赖于以群的行走路线 而只是不断增强最优路线的信息素 同时进行挥发 第三次外循环后得到的信息素矩阵为 45 初始的蚁群优化算法 基于图的蚁群系统 GBAS 12 12 蚂蚁以一定的概率从城市i到城市j进行转移 信息素的更新在STEP3完成 并随K而变化 假设第K次外循环后得到信息素矩阵 得到当前最优解 第K次循环前的信息素和最优解为 经过第K次外循环后 得到 由于蚂蚁的一步转移概率是随机的 从到也是随机的 是一个马尔可夫过程 46 2 6一般蚁群算法的框架 一般蚁群算法的框架和GBAS基本相同 有三个组成部分 蚁群的活动 信息素的挥发 信息素的增强 主要体现在前面的算法中步骤2和步骤3中的转移概率公式和信息素更新公式 47 2 7蚁群优化算法 技术问题 1 解的表达形式与算法的实现 2 每一节点的记忆信息和系数的确定 3 蚁群的规模和停止规则 4 信息素的更改 48 1 解的表达形式与算法的实现1 4 解的表达形式 解的表达形式基于TSP问题的蚁群优化算法 其解的形式是所有城市的一个排列 闭圈 这种情况下谁在第一并不重要 信息素痕迹按每个弧记录 而对于一般以顺序作为解的优化问题 谁在第一是很重要的 蚁群算法在解决这类问题时 只需要建立一个虚拟的始终点 就可以把TSP问题的解法推广 用于诸多的优化问题 诸如车间作业及下料等问题 他们的共同特点是解以一个顺序表示 TSP问题寻找的是最短回路 而一般优化问题中 STEP3中的判断条件需要根据实际问题进行修改 49 解的表达形式与算法的实现2 4 算法的实现 例 0 1背包问题的解顺序表达形式与算法实现 设有一个容积为b的背包 n个尺寸分别为 价值分别为的物品 0 1背包问题的数学模型为 假设其解的顺序表达形式为 其中为的一个排列 50 解的表达形式与算法的实现3 4 算法的实现 建立有向图 其中A中共有条弧 初始信息素痕迹定义为 设第s只蚂蚁第k步所走的路线为 表示蚂蚁从0点出发 顺序到达 第步按TSP算法的转移概率公式行走选择 若则 否则 此蚂蚁不再继续行走 退回起点 51 解的表达形式与算法的实现4 4 算法的实现 对蚁群重复以上过程 比较m只蚂蚁的装包值并记忆具有最大装包值的蚂蚁为t 把GBAS算法中步骤3中的改为 若满足此条件则替换当前最好解为 对W上的弧进行信息素的加强 其他弧进行信息素的挥发 算法中记录了三个信息 信息素痕迹 行走路线 和问题的约束条件 以确定是否将加入 52 2 每一节点的记忆信息和系数的确定 需要记忆的信息1 3 算法中需要记忆的信息有三部分 第一部分信息是存在每个节点的路由表数据结构 由此决定的的转移概率为其中T可以看成节点i的邻域 53 每一节点的记忆信息和系数的确定 需要记忆的信息2 3 第二部分需要记忆的信息是每个蚂蚁的记忆表中存储着的自身的历史信息 这一部分主要由算法的中的记忆 表示蚂蚁已经行走过的节点 第三部分为问题的约束条件 在GBAS中 T集合表示满足约束条件的候选集 在背包问题的蚁群算法中由判别条件 来实现记忆功能 54 每一节点的记忆信息和系数的确定 系数的确定3 3 残留信息的相对重要程度和预见值的相对重要程度体现了相关信息痕迹和预见度对蚂蚁决策的相对影响 Dorigo在求解TSP问题时 推荐参数的最佳设置为 55 3 蚁群的规模和停止规则 一 蚁群大小一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数 二 终止条件1给定一个外循环的最大数目 表明已经有足够的蚂蚁工作 2当前最优解连续K次相同而停止 其中K是一个给定的整数 表示算法已经收敛 不再需要继续 3目标值控制规则 给定优化问题 目标最小化 的一个下界和一个误差值 当算法得到的目标值同下界之差小于给定的误差值时 算法终止 56 4 信息素的更改1 6 信息素的更新分为离线和在线两种方式 离线方式 同步更新方式 的主要思想是在若干只蚂蚁完成n个城市的访问后 统一对残留信息进行更新处理 信息素的在线更新 异步更新方式 即蚂蚁每行走一步 立即回溯并且更新行走路径上的信息素 57 信息素的更改2 6 离线方式的信息素更新可以进一步分为单蚂蚁离线更新和蚁群离线更新 蚁群离线更新方式是在蚁群中的m只蚂蚁全部完成n城市的访问 第k 1次蚁群循环 后 统一对残留信息进行更新处理 其中 为第k 1次循环后的的信息素的痕迹值 单蚂蚁离线更新是在第s只蚂蚁完成对所有n个城市的访问后 进行路径回溯 更新行走路径上的信息素 同时释放分配给它的资源 更新公式为第s 1只蚂蚁根据重新计算路由表 58 信息素的更改3 6 TSP问题中 蚁群优化算法根据信息素痕迹更新方式不同可以分为不同的算法 采用离线方式 并且时 其中W为t循环中m只蚂蚁所行走的最佳路线或第t只蚂蚁所行走的一条路径 Q为一个常数 该算法名为蚁环算法 ant cyclealgotithm 特点是行走的路径越短对应保存的信息素的值就越大 59 信息素的更改4 6 GBAS算法是典型的离线信息素更新方式 该算法中 蚁群中蚂蚁的先后出行顺序没有相关性 但是每次循环需要记忆m只蚂蚁的行走路径 以进行比较选择最优路径 相对而言 单蚂蚁离线更新方式记忆信息少 只需要记忆第s只蚂蚁的路径 并通过信息素更新后 释放该蚂蚁的所有记录信息 实际上这种方式等价于蚁群离线方式中只有一只蚂蚁 60 信息素的更改5 6 与单蚂蚁离线更新方式相比 信息量记忆更小的是信息素在线更新方式 即蚂蚁每走一步 马上回溯并且更新刚刚走过的路径上的信息素 其规则为其中 k为蚂蚁行走的第k步 61 信息素的更改6 6 蚁量算法 ant quantityalgorithm 的信息素更新为 Q为常量 表示i到j的距离 这样信息浓度会随城市距离的减小而加大 蚁密算法 ant densityalgorithm 信息素更新为 以上三种算法中 蚁环算法效果最好 因为他用的是全局信息 而其余两种算法用的是局部信息 蚁环离线更新方法很好地保证了残留信息不至于无限积累 非最优路径会逐渐随时间推移被忘记 62 蚁群优化算法 参考书1 智能蚁群算法及应用吴启迪上海科技出版社从基本结构 算法特点 改进方法 突破途径 实现模式及应用模式等方面进行了论述 主要内容有蚁群算法的由来 研究成果 应用综述 算法的具体描述及改进 算法的典型优化问题求解模式 算法的典型应用及拓展应用 63 蚁群优化算法 参考书2 蚁群算法及其应用李士勇哈工大出版社国内首部蚁群算法的专著 系统地阐述蚁群算法的基本原理 基本蚁群算法及改进算法 蚁群算法与遗传 免疫算法的融合 自适应蚁群算法 并行蚁群算法 蚁群算法的收敛性与理论模型及其在优化问题中的应用 本书可供人工智能 计算机科学 信息科学 控制工程 管理工程 交通工程 网络工程 智能优化算法及智能自动化等领域的广大师生和科技人员学习及参考 64 第4节粒子群优化 粒子群优化 ParticleSwarmOptimization PSO 又称微粒群算法 是由J Kennedy和RCEberhart等于1995年开发的一种演化机制 粒子 particle 是一个折衷的选择 因为既需要将群体中的成员描述为没有质量 没有体积的 同时也需要描述它的速度和加速状态 ParticleSwarmOptimization PSO appliestoconceptofsocialinteractiontoproblemsolving Itwasdevelopedin1995byJamesKennedyandRussEberhart Kennedy J andEberhart R 1995 ParticleSwarmOptimization Proceedingsofthe1995IEEEInternationalConferenceonNeuralNetworks pp 1942 1948 IEEEPress http dsp jpl nasa gov members payman swarm kennedy95 ijcnn pdf 65 粒子群优化SwarmTopology InPSO therehavebeentwobasictopologiesusedintheliteratureRingTopology neighborhoodof3 StarTopology globalneighborhood I4 I0 I1 I2 I3 I4 I0 I1 I2 I3 66 特点 分布式搜寻具记忆性组件较少 容易实现适合在连续性的范围内搜寻 67 演算法介绍 每个寻优的问题解都被想象成一只鸟 我们也称为 Particle 所有的Particle都有一个fitnessfunction以判断目前的位置之好坏 每一个Particle必须赋予记忆性 能记得所搜寻到最佳位置 每一个Particle还有一个速度以决定飞行的距离与方向 68 粒子群优化 TheAnatomyofaParticle Aparticle individual iscomposedof Threevectors Thex vectorrecordsthecurrentposition location oftheparticleinthesearchspace Thep vectorrecordsthelocationofthebestsolutionfoundsofarbytheparticle andThev vectorcontainsagradient direction forwhichparticlewilltravelinifundisturbed IkX P V x fitness p fitness 69 粒子群优化 TheAnatomyofaParticle Aparticle individual iscomposedof Twofitnessvalues Thex fitnessrecordsthefitnessofthex vector andThep fitnessrecordsthefitnessofthep vector IkX P V x fitness p fitness 70 速度更新 Vid 每一Particle在第d维之速度i Particle之编号d 维度w InertiaWeightc1 c2 学习Rand 一介于0至1的随机数Pid 每一Particle到目前为止 所出現的最佳位置Pgd 所有Particle到目前为止 所出現的最佳位置xid 每一Particle目前之所在 71 演算法流程 1 Initial将群族做初始化 以随机的方式求出每一Particle之初始位置与速度 2 Evaluation 依据fitnessfunction计算出其fitnessvalue以作为判断每一Particle之好坏 3 FinethePbest 找出每一Particle到目前为止的搜寻过程中最佳解 这个最佳解我们将之称为Pbest 4 FinetheGbest 找出所有Particle到目前为止所搜寻到的整体最佳解 此最佳解我们称之为Gbest 5 UpdatetheVelocity 依据式 1 与式 2 更新每一Particle之速度与位置 6 回到步骤2 继续执行 直到获得一个令人满意的结果或符合终止条件为止 72 粒子群优化 SwarmSearch Actually wemustadjustthev vectorbeforeaddingittothex vectorasfollows vid vid 1 rnd pid xid 2 rnd pgd xid xid xid vid Whereiistheparticle 1 2arelearningratesgoverningthecognitionandsocialcomponentsWheregrepresentstheindexoftheparticlewiththebestp fitness andWheredisthedthdimension 73 粒子群优化 SwarmSearch Intiallythevaluesofthevelocityvectorsarerandomlygeneratedwiththerange Vmax Vmax whereVmaxisthemaximumvaluethatcanbeassignedtoanyvid 74 粒子群优化 SwarmTypes Inpaper Kennedy J 1997 TheParticleSwarm SocialAdaptationofKnowledge Proceedingsofthe1997InternationalConferenceonEvolutionaryComputation pp 303 308 IEEEPress Kennedyidentifies4typesofPSObasedon 1and 2 Given vid vid 1 rnd pid xid 2 rnd pgd xid xid xid vid FullModel 1 2 0 CognitionOnly 1 0and 2 0 SocialOnly 1 0and 2 0 Selfless 1 0 2 0 andg i 75 粒子群优化 RelatedIssues ThereareanumberofrelatedissuesconcerningPSO Controllingvelocities determiningthebestvalueforVmax SwarmSize NeighborhoodSize UpdatingXandVelocityVectors RobustSettingsfor 1and 2 AnOff The ShelfPSOCarlisle A andDozier G 2001 AnOff The ShelfPSO Proceedingsofthe2001WorkshoponParticleSwarmOptimization pp 1 6 Indianapolis IN http antho huntingdon edu publications Off The Shelf PSO pdf 76 粒子群优化 ControllingVelocities WhenusingPSO itispossibleforthemagnitudeofthevelocitiestobecomeverylarge PerformancecansufferifVmaxisinappropriatelyset Twomethodsweredevelopedforcontrollingthegrowthofvelocities Adynamicallyadjustedinertiafactor andAconstrictioncoefficient 77 粒子群优化TheInertiaFactor Whentheinertiafactorisused theequationforupdatingvelocitiesischangedto vid vid 1 rnd pid xid 2 rnd pgd xid Where isinitializedto1 0andisgraduallyreducedovertime measuredbycyclesthroughthealgorithm 78 粒子群优化 TheConstrictionCoefficient In1999 MauriceClercdevelopedaconstrictionCoefficientforPSO vid K vid 1 rnd pid xid 2 rnd pgd xid WhereK 2 2 sqrt 2 4 1 2 and 4 79 粒子群优化 SwarmandNeighborhoodSize ConcerningtheswarmsizeforPSO aswithotherECsthereisatrade offbetweensolutionqualityandcost intermsoffunctionevaluations Globalneighborhoodsseemtobebetterintermsofcomputationalcosts Theperformanceissimilartotheringtopology orneighborhoodsgreaterthan3 TherehasbeenlittleresearchontheeffectsofswarmtopologyonthesearchbehaviorofPSO 80 Schwefel sfunction 81 搜寻过程 最初状态 82 搜寻过程 经过5代 83 搜寻过程 经过10代 84 搜寻过程 经过15代 85 搜寻过程 经过20代 86 搜寻过程 经过25代 87 搜寻过程 经过100代 88 搜寻过程 经过500代 89 搜寻结果 90 第5节人工鱼算法 获得了1996ACMDoctoralDissertationAward 91 人工鱼 92 人工鱼 93 人工鱼 94 人工鱼 2020 4 7 95 第章人工神经网络ArtificialNeuralNetwork 2020 4 7 96 第1节绪论 人类具有高度发达的大脑 大脑是思维活动的物质基础 而思维是人类智能的集中体现 思维是人脑的信息处理方式 人脑的思维有逻辑思维 形象思维和灵感思维三种基本方式 逻辑思维的基础是概念 判断与推理 即将信息抽象为概念 在根据逻辑规则进行逻辑推理 由于概念可用符号表示 而逻辑推理可按串行模式进行 这一过程可以写成串行指令由机器来完成 计算机就是这样一种用机器模拟人脑逻辑思维的人工智能系统 2020 4 7 97 什么是人工神经网络 生物神经网络人类的大脑大约有1 4 1011个神经细胞 亦称为神经元 每个神经元有数以千计的通道同其它神经元广泛相互连接 形成复杂的生物神经网络 人工神经网络以数学和物理方法以及信息处理的角度对人脑神经网络进行抽象 并建立某种简化模型 就称为人工神经网络 ArtificialNeuralNetwork 缩写ANN 2020 4 7 98 生物神经元模型 生物神经元主要由细胞体 树突和轴突组成 树突和轴突负责传入和传出信息 兴奋性的冲动沿树突抵达细胞体 在细胞膜上累积形成兴奋性电位 相反 抑制性冲动到达细胞膜则形成抑制性电位 两种电位进行累加 若代数和超过某个阈值 神经元将产生冲动 2020 4 7 99 2020 4 7 100 神经元对信息的接受和传递都是通过突触来进行的 单个神经元可以从别的细胞接受多达上千个的突触输入 这些输入可达到神经元的树突 胞体和轴突等不同部位 但其分布各不相同 对神经元的影响也不同 人类大脑皮质的全部表面积约有20 104mm2 平均厚度约2 5mm 皮质的体积则约为50 104mm3 如果皮质中突触的平均密度是6 l09 mm3左右 则可认为皮质中的全部突触数为3 1015个 如果再按上述人脑所含的全部神经元数目计算 则每个神经元平均的突触数目可能就有1 5 3 0万个左右 2020 4 7 101 神经元之间的联系主要依赖其突触的联接作用 这种突触的联接是可塑的 也就是说突触特性的变化是受到外界信息的影响或自身生长过程的影响 生理学的研究归纳有以下几个方面的变化 1 突触传递效率的变化 首先是突触的膨胀以及由此产生的突触后膜表面积扩大 从而突触所释放出的传递物质增多 使得突触的传递效率提高 其次是突触传递物质质量的变化 包括比例成分的变化所引起传递效率的变化 2 突触接触间隙的变化 在突触表面有许多形状各异的小凸芽 调节其形状变化可以改变接触间隙 并影响传递效率 2020 4 7 102 3 突触的发芽 当某些神经纤维被破坏后 可能又会长出新芽 并重新产生附着于神经元上的突触 形成新的回路 由于新的回路的形成 使得结合模式发生变化 也会引起传递效率的变化 4 突触数目的增减 由于种种复杂环境条件的刺激等原因 或者由于动物本身的生长或衰老 神经系统的突触数目会发生变化 并影响神经元之间的传递效率 2020 4 7 103 正是神经元这种整合作用 才使得亿万个神经元在神经系统中有条不紊 夜以继日地处理各种复杂的信息 执行着生物中枢神经系统的各种信息处理功能 多个神经元以突触联接形成了一个神经网络 研究表明 生物神经网络的功能决不是单个神经元生理和信息处理功能的简单叠加 而是一个有层次的 多单元的动态信息处理系统 它们有其独特的运行方式和控制机制 以接受生物内外环境的输入信息 加以综合分折处理 然后调节控制机体对环境作出适当的反应 2020 4 7 104 人工神经元模型 人工神经元模型 模仿生物神经元产生冲动的过程 可以建立一个典型的人工神经元数学模型 x1 xn T为输入向量 y为输出 f 为激发函数 为阈值 Wi为神经元与其它神经元的连接强度 也称权值 2020 4 7 105 人工神经元模型 常用的激发函数f的种类 1 阈值型函数 2020 4 7 106 人工神经元模型 2 饱和型函数 3 双曲函数 2020 4 7 107 工神经元模型 4 S型函数 5 高斯函数 2020 4 7 108 人工神经网络定义 人工神经网络是一个由许多简单的并行工作的处理单元组成的系统 其功能取决于网络的结构 连接强度以及各单元的处理方式 人工神经网络是一种旨在模仿人脑结构及其功能的信息处理系统 神经网络是由多个非常简单的处理单元彼此按某种方式相互连接而形成的计算系统 该系统是靠其状态对外部输入信息的动态响应来处理信息的 2020 4 7 109 神经网络的定义及特点 神经网络系统是由大量的神经元 通过广泛地互相连接而形成的复杂网络系统 定义 特点 1 非线性映射逼近能力 任意的连续非线性函数映射关系可由多层神经网络以任意精度加以逼近 2 自适应性和自组织性 神经元之间的连接具有多样性 各神经元之间的连接强度具有可塑性 网络可以通过学习与训练进行自组织 以适应不同信息处理的要求 3 并行处理性 网络的各单元可以同时进行类似的处理过程 整个网络的信息处理方式是大规模并行的 可以大大加快对信息处理的速度 4 分布存储和容错性 信息在神经网络内的存储按内容分布于许多神经元中 而且每个神经元存储多种信息的部分内容 网络的每部分对信息的存储具有等势作用 部分的信息丢失仍可以使完整的信息得到恢复 因而使网络具有容错性和联想记忆功能 5 便于集成实现和计算模拟 神经网络在结构上是相同神经元的大规模组合 特别适合于用大规模集成电路实现 2020 4 7 110 神经网络的基本功能之一 联想记忆功能 2020 4 7 111 神经网络的基本功能之二 非线性映射功能 2020 4 7 112 神经网络的基本功能之三 分类与识别功能 2020 4 7 113 神经网络的基本功能之四 优化计算功能 2020 4 7 114 神经网络的基本功能之五 知识处理功能 2020 4 7 115 第2节感知器模型 感知器 Perceptron 是由美国学者F Rosenblatt于1957年提出的 它是一个具有单层计算单元的神经网络 并由线性阈值元件组成 激发函数为阈值型函数 当其输入的加权和大于或等于阈值时 输出为1 否则为0或 1 它的权系W可变 这样它就可以学习 感知器的结构 2020 4 7 116 感知器模型 感知器的学习算法 为方便起见 将阈值 它也同样需要学习 并入W中 令Wn 1 X向量也相应地增加一个分量xn 1 1 则 学习算法 给定初始值 赋给Wi 0 各一个较小的随机非零值 这里Wi t 为t时刻第i个输入的权 1 i n Wn 1 t 为t时刻的阈值 输入一样本X xi xn 1 和它的希望输出d 计算实际输出 修正权W Wi t 1 Wi t d Y t xi i 1 2 n 1 转到 直到W对一切样本均稳定不变为止 2020 4 7 117 感知器模型 根据某样本训练时 均方差随训练次数的收敛情况 2020 4 7 118 感知器在形式上与MP模型差不多 它们之间的区别在于神经元间连接权的变化 感知器的连接权定义为可变的 这样感知器就被赋予了学习的特性 利用简单感知器可以实现逻辑代数中的一些运算 Y f w1x1 w2x2 1 与 运算 当取w1 w2 1 1 5时 上式完成逻辑 与 的运算 2020 4 7 119 2 或 运算 当取wl w2 1 0 5时 上式完成逻辑 或 的运算 3 非 运算 当取wl 1 w2 0 1时 完成逻辑 非 的运算 2020 4 7 120 与许多代数方程一样 上式中不等式具有一定的几何意义 对于一个两输入的简单感知