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

高等运筹学大连海事大学刘巍目录第一篇运筹学发展历史第二篇运筹学中的数学规划第三篇运筹学中的组合优化第四篇运筹学中的随机优化第五篇运筹学中的博弈论第六篇运筹学中管理科学第七篇运筹学中智能计算第八篇运筹学发展势态第六篇运筹学中的智能计算第二十三章

遗传算法第二十四章

模拟退火第二十五章

蚁群算法第二十六章人工神经网络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蚁群优化算法—技术问题262.1蚁群算法原理

蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时．就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低.当后来的蚂蚁再次碰到这个路口的时候．选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大．而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。272.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路线。这也就是前面所提到的正反馈效应。302.3自然蚁群与人工蚁群算法基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如TSP问题。人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离。312.4蚁群算法与TSP问题1/3TSP问题表示为一个N个城市的有向图G=（N，A），其中 城市之间距离目标函数为，其中为城市1,2，…n的一个排列，。32

蚁群算法与TSP问题2/3

TSP问题的人工蚁群算法中，假设m只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：1信息素值也称信息素痕迹。2可见度，即先验值。信息素的更新方式有2种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值“好”(有蚂蚁走过)的边增加信息素。33蚁群算法与TSP问题3/3蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。342.5初始的蚁群优化算法—基于图的蚁群系统（GBAS）1/12初始的蚁群算法是基于图的蚁群算法，graph-basedantsystem,简称为GBAS，是由GutjahrWJ在2000年的FutureGenerationComputingSystems提出的，课本的参考文献2。算法步骤如下：STEP0

对n个城市的TSP问题，城市间的距离矩阵为，给TSP图中的每一条弧赋信息素初值，假设m只蚂蚁在工作，所有蚂蚁都从同一城市出发。当前最好解是 。35初始的蚁群优化算法—基于图的蚁群系统（GBAS）2/12STEP1

（外循环）如果满足算法的停止规则，则停止计算并输出计算得到的最好解。否则使蚂蚁s从起点出发，用表示蚂蚁s行走的城市集合，初始为空集，。STEP2(内循环)按蚂蚁的顺序分别计算。当蚂蚁在城市i，若 完成第s只蚂蚁的计算。否则，若，则以概率 ， 到达j， ；若则到达 重复STEP2。36初始的蚁群优化算法—基于图的蚁群系统（GBAS）3/12STRP3

对 ，若，按中城市的顺序计算路径程度；若，路径长度置为一个无穷大值（即不可达）。比较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次外循环后，得到。由于蚂蚁的一步转移概率是随机的，从到也是随机的，是一个马尔可夫过程。462.6一般蚁群算法的框架一般蚁群算法的框架和GBAS基本相同，有三个组成部分：蚁群的活动；信息素的挥发；信息素的增强；主要体现在前面的算法中步骤2和步骤3中的转移概率公式和信息素更新公式。472.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/6TSP问题中，蚁群优化算法根据信息素痕迹更新方式不同可以分为不同的算法，采用离线方式，并且时，其中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.](/members/payman/swarm/kennedy95-ijcnn.pdf)

65粒子群优化

SwarmTopologyInPSO,therehavebeentwobasictopologiesusedintheliteratureRingTopology(neighborhoodof3)StarTopology(globalneighborhood)

I4

I0

I1

I2

I3

I4

I0

I1

I2

I366特点分布式搜寻

具记忆性组件较少，容易实现

适合在连续性的范围内搜寻

67演算法介绍每个寻优的问题解都被想象成一只鸟，我们也称为“Particle”。所有的Particle都有一个fitnessfunction以判断目前的位置之好坏，

每一个Particle必须赋予记忆性，能记得所搜寻到最佳位置。每一个Particle还有一个速度以决定飞行的距离与方向。

68粒子群优化:

TheAnatomyofaParticleAparticle(individual)iscomposedof:Threevectors:Thex-vectorrecordsthecurrentposition(location)oftheparticleinthesearchspace,Thep-vectorrecordsthelocationofthebestsolutionfoundsofarbytheparticle,andThev-vectorcontainsagradient(direction)forwhichparticlewilltravelinifundisturbed.IkX=<xk0,xk1,…,xkn-1>P=<pk0,pk1,…,pkn-1>V=<vk0,vk1,…,vkn-1>x_fitness=?p_fitness=?69粒子群优化:

TheAnatomyofaParticleAparticle(individual)iscomposedof:Twofitnessvalues:Thex-fitnessrecordsthefitnessofthex-vector,andThep-fitnessrecordsthefitnessofthep-vector.IkX=<xk0,xk1,…,xkn-1>P=<pk0,pk1,…,pkn-1>V=<vk0,vk1,…,vkn-1>x_fitness=?p_fitness=?70速度更新Vid ：每一Particle在第d维之速度i：Particle之编号d：维度w ：InertiaWeight c1、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粒子群优化:

SwarmSearchActually,wemustadjustthev-vectorbeforeaddingittothex-vectorasfollows:vid=vid+1*rnd()*(pid-xid) +2*rnd()*(pgd-xid);xid=xid+vid;Whereiistheparticle,1,2arelearningratesgoverningthecognitionandsocialcomponents

Wheregrepresentstheindexoftheparticlewiththebestp-fitness,andWheredisthedthdimension.73粒子群优化:

SwarmSearchIntiallythevaluesofthevelocityvectorsarerandomlygeneratedwiththerange[-Vmax,Vmax]whereVmaxisthemaximumvaluethatcanbeassignedtoanyvid.74粒子群优化:

SwarmTypesInpaper,[Kennedy,J.(1997),“TheParticleSwarm:SocialAdaptationofKnowledge”,Proceedingsofthe1997InternationalConferenceonEvolutionaryComputation,pp.303-308,IEEEPress.]Kennedyidentifies4typesofPSObasedon1and2.Given:vid=vid+1*rnd()*(pid-xid) +2*rnd()*(pgd-xid); xid=xid+vid;FullModel (1,2>0)CognitionOnly (1>0and2=0),SocialOnly (1=0and2>0)Selfless (1=0,2>0,andgi)75粒子群优化:

RelatedIssuesThereareanumberofrelatedissuesconcerningPSO:Controllingvelocities(determiningthebestvalueforVmax),SwarmSize,NeighborhoodSize,UpdatingXandVelocityVectors,RobustSettingsfor(1and2),AnOff-The-ShelfPSOCarlisle,A.andDozier,G.(2001).“AnOff-The-ShelfPSO”,Proceedingsofthe2001WorkshoponParticleSwarmOptimization,pp.1-6,Indianapolis,IN.(/publications/Off-The-Shelf_PSO.pdf)

76粒子群优化:

ControllingVelocitiesWhenusingPSO,itispossibleforthemagnitudeofthevelocitiestobecomeverylarge.PerformancecansufferifVmaxisinappropriatelyset.Twomethodsweredevelopedforcontrollingthegrowthofvelocities:Adynamicallyadjustedinertiafactor,andAconstrictioncoefficient.77粒子群优化

TheInertiaFactorWhentheinertiafactorisused,theequationforupdatingvelocitiesischangedto:vid=*vid+1*rnd()*(pid-xid) +2*rnd()*(pgd-xid);Where

isinitializedto1.0andisgraduallyreducedovertime(measuredbycyclesthroughthealgorithm).78粒子群优化:

TheConstrictionCoefficientIn1999,MauriceClercdevelopedaconstrictionCoefficientforPSO.vid=K[vid+1*rnd()*(pid-xid) +2*rnd()*(pgd-xid)];WhereK=2/|2--sqrt(2-4)|,=1+2,and>4.79粒子群优化:

SwarmandNeighborhoodSizeConcerningtheswarmsizeforPSO,aswithotherECsthereisatrade-offbetweensolutionqualityandcost(intermsoffunctionevaluations).Globalneighborhoodsseemtobebetterintermsofcomputationalcosts.Theperformanceissimilartotheringtopology(orneighborhoodsgreaterthan3).TherehasbeenlittleresearchontheeffectsofswarmtopologyonthesearchbehaviorofPSO.80Schwefel'sfunction81搜寻过程－最初状态82搜寻过程－经过5代83搜寻过程－经过10代84搜寻过程－经过15代85搜寻过程－经过20代86搜寻过程－经过25代87搜寻过程－经过100代88搜寻过程－经过500代89搜寻结果移动次数搜寻结果0416.2455995515.74879610759.40400615793.73201920834.813763100837.9115355000837.965771最佳解837.965890第5节人工鱼算法

获得了1996ACMDoctoralDissertationAward.91人工鱼

92人工鱼

93人工鱼

94人工鱼

2026/5/195第章人工神经网络

ArtificialNeuralNetwork2026/5/196第1节

绪论

人类具有高度发达的大脑，大脑是思维活动的物质基础，而思维是人类智能的集中体现。思维是人脑的信息处理方式。人脑的思维有逻辑思维、形象思维和灵感思维三种基本方式。逻辑思维的基础是概念、判断与推理，即将信息抽象为概念，在根据逻辑规则进行逻辑推理。由于概念可用符号表示，而逻辑推理可按串行模式进行，这一过程可以写成串行指令由机器来完成。计算机就是这样一种用机器模拟人脑逻辑思维的人工智能系统。2026/5/197什么是人工神经网络

生物神经网络

人类的大脑大约有1.4

1011个神经细胞，亦称为神经元。每个神经元有数以千计的通道同其它神经元广泛相互连接，形成复杂的生物神经网络。

人工神经网络

以数学和物理方法以及信息处理的角度对人脑神经网络进行抽象，并建立某种简化模型，就称为人工神经网络（ArtificialNeuralNetwork，缩写ANN）。2026/5/198生物神经元模型生物神经元主要由细胞体、树突和轴突组成，树突和轴突负责传入和传出信息，兴奋性的冲动沿树突抵达细胞体，在细胞膜上累积形成兴奋性电位；相反，抑制性冲动到达细胞膜则形成抑制性电位。两种电位进行累加，若代数和超过某个阈值，神经元将产生冲动。

2026/5/1992026/5/1100

神经元对信息的接受和传递都是通过突触来进行的。单个神经元可以从别的细胞接受多达上千个的突触输入。这些输入可达到神经元的树突、胞体和轴突等不同部位，但其分布各不相同．对神经元的影响也不同。人类大脑皮质的全部表面积约有20×104mm2，平均厚度约2．5mm，皮质的体积则约为50×104mm3。如果皮质中突触的平均密度是6×l09／mm3左右，则可认为皮质中的全部突触数为3×1015个。如果再按上述人脑所含的全部神经元数目计算，则每个神经元平均的突触数目可能就有1．5—3．0万个左右。2026/5/1101

神经元之间的联系主要依赖其突触的联接作用。这种突触的联接是可塑的，也就是说突触特性的变化是受到外界信息的影响或自身生长过程的影响。生理学的研究归纳有以下几个方面的变化：

(1)突触传递效率的变化。首先是突触的膨胀以及由此产生的突触后膜表面积扩大，从而突触所释放出的传递物质增多，使得突触的传递效率提高。其次是突触传递物质质量的变化，包括比例成分的变化所引起传递效率的变化。

(2)突触接触间隙的变化。在突触表面有许多形状各异的小凸芽，调节其形状变化可以改变接触间隙，并影响传递效率。

2026/5/1102(3)突触的发芽。当某些神经纤维被破坏后，可能又会长出新芽，并重新产生附着于神经元上的突触．形成新的回路。由于新的回路的形成，使得结合模式发生变化，也会引起传递效率的变化。

(4)突触数目的增减。由于种种复杂环境条件的刺激等原因，或者由于动物本身的生长或衰老，神经系统的突触数目会发生变化，并影响神经元之间的传递效率。

2026/5/1103正是神经元这种整合作用，才使得亿万个神经元在神经系统中有条不紊、夜以继日地处理各种复杂的信息，执行着生物中枢神经系统的各种信息处理功能。多个神经元以突触联接形成了一个神经网络。研究表明，生物神经网络的功能决不是单个神经元生理和信息处理功能的简单叠加，而是一个有层次的、多单元的动态信息处理系统。它们有其独特的运行方式和控制机制，以接受生物内外环境的输入信息，加以综合分折处理，然后调节控制机体对环境作出适当的反应。

2026/5/1104人工神经元模型人工神经元模型模仿生物神经元产生冲动的过程，可以建立一个典型的人工神经元数学模型[x1,…,xn]T为输入向量，y为输出，f(·)为激发函数，θ为阈值。Wi为神经元与其它神经元的连接强度，也称权值。2026/5/1105人工神经元模型常用的激发函数f的种类：1）阈值型函数2026/5/1106人工神经元模型2）饱和型函数3）双曲函数2026/5/1107工神经元模型4）S型函数5）高斯函数2026/5/1108人工神经网络定义

人工神经网络是一个由许多简单的并行工作的处理单元组成的系统，其功能取决于网络的结构、连接强度以及各单元的处理方式。

人工神经网络是一种旨在模仿人脑结构及其功能的信息处理系统。

神经网络是由多个非常简单的处理单元彼此按某种方式相互连接而形成的计算系统，该系统是靠其状态对外部输入信息的动态响应来处理信息的。2026/5/1109神经网络的定义及特点神经网络系统是由大量的神经元，通过广泛地互相连接而形成的复杂网络系统。

定义

特点（1）非线性映射逼近能力。任意的连续非线性函数映射关系可由多层神经网络以任意精度加以逼近。（2）自适应性和自组织性。神经元之间的连接具有多样性，各神经元之间的连接强度具有可塑性，网络可以通过学习与训练进行自组织，以适应不同信息处理的要求。（3）并行处理性。网络的各单元可以同时进行类似的处理过程，整个网络的信息处理方式是大规模并行的，可以大大加快对信息处理的速度。（4）分布存储和容错性。信息在神经网络内的存储按内容分布于许多神经元中，而且每个神经元存储多种信息的部分内容。网络的每部分对信息的存储具有等势作用，部分的信息丢失仍可以使完整的信息得到恢复，因而使网络具有容错性和联想记忆功能。（5）便于集成实现和计算模拟。神经网络在结构上是相同神经元的大规模组合，特别适合于用大规模集成电路实现。2026/5/1110神经网络的基本功能之一联想记忆功能2026/5/1111神经网络的基本功能之二非线性映射功能2026/5/1112神经网络的基本功能之三分类与识别功能2026/5/1113神经网络的基本功能之四优化计算功能2026/5/1114

神经网络的基本功能之五知识处理功能2026/5/1115第2节感知器模型感知器(Perceptron)是由美国学者F.Rosenblatt于1957年提出的，它是一个具有单层计算单元的神经网络，并由线性阈值元件组成。

激发函数为阈值型函数，当其输入的加权和大于或等于阈值时，输出为1，否则为0或-1。它的权系W可变，这样它就可以学习。

感知器的结构2026/5/1116感知器模型感知器的学习算法为方便起见，将阈值θ(它也同样需要学习)并入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对一切样本均稳定不变为止。

2026/5/1117

感知器模型根据某样本训练时，均方差随训练次数的收敛情况2026/5/1118

感知器在形式上与MP模型差不多，它们之间的区别在于神经元间连接权的变化。感知器的连接权定义为可变的，这样感知器就被赋予了学习的特性。利用简单感知器可以实现逻辑代数中的一些运算。

Y=f(w1x1+w2x2-θ)(1)“与”运算。当取w1＝w2＝1，θ＝1.5时，上式完成逻辑“与”的运算。2026/5/1119(2)“或”运算，当取wl＝w2＝1，θ

＝0.5时，上式完成逻辑“或”的运算。(3)“非”运算，当取wl=-1，w2＝0，θ

＝-1时．完成逻辑“非”的运算。2026/5/1120与许多代数方程一样，上式中不等式具有一定的几何意义。对于一个两输入的简单感知器，每个输入取值为0和1，如上面结出的逻辑运算，所有输入样本有四个，记为(x1，x2)：(0，0)，(0，1)，(1，0)，(1，1)，构成了样本输入空间。例如，在二维平面上，对于“或”运算，各个样本的分布如下图所示。直线

1*x1+1*x2-0．5＝0将二维平面分为两部分，上部为激发区(y，=1，用★表示)，下部为抑制区(y＝0，用☆表示)。2026/5/1121简单感知器引入的学习算法称之为误差学习算法。该算法是神经网络学习中的一个重要算法，并已被广泛应用。现介绍如下：

误差型学习规则：

(1)选择一组初始权值wi(0)。

(2)计算某一输入模式对应的实际输出与期望输出的误差δ

2026/5/1122(3)如果δ小于给定值，结束，否则继续。(4)更新权值(阈值可视为输入恒为1的一个权值)：Δwi（t+1）＝wi（t+1）-wi（t）＝η[d—y(t)]xi。式中η为在区间(0，1)上的一个常数，称为学习步长，它的取值与训练速度和w收敛的稳定性有关；d、y为神经元的期望输出和实际输出；xi为神经元的第i个输入。

(5)返回(2)，重复，直到对所有训练样本模式，网络输出均能满足要求。2026/5/11232026/5/1124对于学习步长V的取值一般是在(0，1)上的一个常数，但是为了改进收敛速度，也可以采用变步长的方法，这里介绍一个算法如下式：式中，α为一个正的常量．这里取值为0.1。所以，对应于输入(0，0)，修正权值(注意：θ=w0,x0=-1)

Δw0（1）＝η[d—y]x0

＝0.1(1—0)(—1)＝—0.1，

W0(1)=0.1+Δw0（1）=0.1-0.1=0.0依次进行。

2026/5/1125同样的方法，对其他输入样本都进行学习。整个学习过程就是某一超平面在样本空间中几何位置调整的过程。初值w1(7)＝—0．225．w2(7)＝—0．0875，

θ(7)＝—0．1875。这样的一组网络参数满足计算要求。2026/5/11262026/5/1127

感知器对线性不可分问题的局限性决定了它只有较差的归纳性，而且通常需要较长的离线学习才能达到收效。2026/5/1128第3节

多层前向BP神经网络最早由werbos在1974年提出的，1985年由Rumelhart再次进行发展。

多层前向神经网络的结构多层前向神经网络由输入层、隐层（不少于1层）、输出层组成，信号沿输入——>输出的方向逐层传递。2026/5/1129多层前向BP神经网络沿信息的传播方向，给出网络的状态方程，用Inj(i)，Outj(i)表示第i层第j个神经元的输入和输出，则各层的输入输出关系可描述为：第一层（输入层）：将输入引入网络第二层（隐层）第三层（输出层）2026/5/1130前向神经网络用途弄这么个东西有用么？怎么用呢？2026/5/1131前向神经网络用途用途非常广泛非线性映照能力：神经网络能以任意精度逼近任何非线性连续函数。在建模过程中的许多问题正是具有高度的非线性。并行分布处理方式：在神经网络中信息是分布储存和并行处理的，这使它具有很强的容错性和很快的处理速度。自学习和自适应能力：神经网络在训练时，能从输入、输出的数据中提取出规律性的知识，记忆于网络的权值中，并具有泛化能力，即将这组权值应用于一般情形的能力。神经网络的学习也可以在线进行。多变量系统：神经网络的输入和输出变量的数目是任意的，对单变量系统与多变量系统提供了一种通用的描述方式，不必考虑各子系统间的解耦问题。2026/5/1132前向神经网络用途Bool函数任何bool函数都可以用一个单隐层的网络来表示但是可能要求指数级的隐层单元个数连续函数每一个有界的连续函数都可以有一个两级的网络以任意小的误差（在有限的范数下）逼近任意函数任意函数都可以被一个由三级的网络以任意精度逼近2026/5/1133网络的学习学习的基本思想是：误差反传算法调整网络的权值，使网络的实际输出尽可能接近期望的输出。假设有M个样本:

将第K个样本Xk输入网络，得到的输出为k

定义学习的目标函数为：2026/5/1134

多层前向BP神经网络为使目标函数最小，训练算法是：令则2026/5/1135多层前向BP神经网络学习的步骤：（1）依次取第k组样本，将Xk输入网络。（2）依次计算

，如果

，退出。（3）计算（4）计算（5），修正权值，返回（1）

如果样本数少，则学习知识不够；如果样本多，则需计算更多的dJk/dw,，训练时间长。可采用随机学习法每次以样本中随机选取几个样本，计算

dJk/dw,，调整权值。

2026/5/1136例9.1多层前向BP网络训练训练样本SISO：SampleInput=[00.10.20.30.4];SampleOutput=[42222];网络结构：2026/5/1137网络输入输出关系：需训练的量：2026/5/1138训练算法：2026/5/1139训练初始参数：W1=rand(1,5);W2=rand(1,5);theta=rand(1,5);beta=rand(1,5);LearningRate1=0.2;LearningRate2=0.4;LearningRate3=0.2;LearningRate4=0.2;2026/5/1140训练后参数：W1＝[-0.40598.5182-0.5994-0.1153-1.1916];W2=[0.62452.83820.66320.57833.5775];Beta=[1.6219-4.94031.60411.5145-0.3858];Theta=[1.58320.19001.54061.6665-0.1441];2026/5/1141训练1000次目标函数的变化曲线：2026/5/1142训练结束后神经网络的输出与样本的拟和情况2026/5/1143算法设计输入/输出变量的确定及其数据的预处理网络的输入变量即为待分析系统的内生变量（影响因子或自变量）数，一般根据专业知识确定。若输入变量较多，一般可通过主成份分析方法压减输入变量，也可根据剔除某一变量引起的系统误差与原系统误差的比值的大小来压减输入变量。输出变量即为系统待分析的外生变量（系统性能指标或因变量），可以是一个，也可以是多个。一般将一个具有多个输出的网络模型转化为多个具有一个输出的网络模型效果会更好，训练也更方便。2026/5/1144算法设计样本数据收集和整理分组采用BP神经网络方法建模的首要和前提条件是有足够多典型性好和精度高的样本。为训练过程使之不发生“过拟合”和评价建立的网络模型的性能和泛化能力，必须将收集到的数据随机分成训练样本、检验样本（10%以上）和测试样本（10%以上）3部分。此外，数据分组时还应尽可能考虑样本模式间的平衡。2026/5/1145算法设计

由于采用Sigmoid转换函数，为提高训练速度和灵敏性以及有效避开Sigmoid函数的饱和区，一般要求输入数据的值在0~1之间。因此，要对输入数据进行预处理。如果输出层节点也采用Sigmoid转换函数，输出变量也必须作相应的预处理，否则，输出变量也可以不做预处理。预处理的方法有多种多样，各文献采用的公式也不尽相同。预处理的数据训练完成后，网络输出的结果要进行反变换才能得到实际值。为保证建立的模型具有一定的外推能力，最好使数据预处理后的值在0.2~0.8之间。2026/5/1146算法设计隐层数一般认为，增加隐层数可以降低网络误差（也有文献认为不一定能有效降低），提高精度，但也使网络复杂化，从而增加了网络的训练时间和出现“过拟合”的倾向。应优先考虑3层BP网络（即有1个隐层）。一般地，靠增加隐层节点数来获得较低的误差，其训练效果要比增加隐层数更容易实现。对于没有隐层的神经网络模型，实际上就是一个线性或非线性（取决于输出层采用线性或非线性转换函数型式）回归模型。因此，一般认为，应将不含隐层的网络模型归入回归分析中，技术已很成熟，没有必