第十讲 粒群优化与蚁群算法

1、群智能（群智能（ Swarm Intelligence ）什么是群？什么是群？l蚁群l鱼群l鸟群l蜂群“群群”的特征的特征l相互影响的相邻的个体相互影响的相邻的个体l个体的行为简单个体的行为简单l既有竞争又有协作既有竞争又有协作l智能化的集体行为智能化的集体行为l个体之间不仅可以交换信息个体之间不仅可以交换信息,而且而且可以处理信息，根据信息来改变自可以处理信息，根据信息来改变自身行为身行为l没有一个集中控制中心，分布式，没有一个集中控制中心，分布式，自组织。自组织。l作为群体协作工作时，能够突显出作为群体协作工作时，能够突显出非常复杂的行为特征非常复杂的行为特征-智能行为，智能行为，群智能群

2、智能群智能（群智能（ Swarm Intelligence ）的提出和发展的提出和发展l1989年加利福尼亚大学的年加利福尼亚大学的Beni（贝尼）、（贝尼）、Hackwood教授在其细胞自动机中首次提出群教授在其细胞自动机中首次提出群智能的概念。细胞自动机中的主体在一维或二智能的概念。细胞自动机中的主体在一维或二维网格空间中与相邻个体相互作用，从而实现维网格空间中与相邻个体相互作用，从而实现自组织。自组织。l任何一种由昆虫群体或其它动物社会行为机制任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略而激发设计出的算法或分布式解决问题的策略均属于群智能。均属于群智能

3、。 1999年，年，Bonabeau（伯纳（伯纳堡）、堡）、Dorigo和和Theraulaz 在他们的著作在他们的著作“Swarm Intelligence: From Natural to Artificial Systems,群智能：从自然到人工系统群智能：从自然到人工系统”Beni（贝尼）Bonabeau（伯纳堡）群智能（群智能（ Swarm Intelligence ）的提出和发展的提出和发展l2001年肯尼迪和艾伯哈特合写了一本书年肯尼迪和艾伯哈特合写了一本书“群智能群智能”l群智能发展的历程碑群智能发展的历程碑l赞同伯纳堡关于群智能的基本定义精神赞同伯纳堡关于群智能的基本定义精神

4、l最重要的观点：智能源于社会性的相互作用最重要的观点：智能源于社会性的相互作用-群智群智能发展的基石。能发展的基石。l认为暂时无法给出合适的定义认为暂时无法给出合适的定义l群智能已经成为有别于传统人工智能中符号主义和群智能已经成为有别于传统人工智能中符号主义和链接主义的一种新的关于人工智能的研究路线链接主义的一种新的关于人工智能的研究路线Swarm IntelligencelSwarm Intelligence最重要的观点是：最重要的观点是：Mind is social，也就是认为人的智能是源于社会性的相互作用，也就是认为人的智能是源于社会性的相互作用，文化和认知是人类社会性不可分割的重要部分

5、，这一观点文化和认知是人类社会性不可分割的重要部分，这一观点成为了群智能发展的基石。群智能已成为有别于传统人工成为了群智能发展的基石。群智能已成为有别于传统人工智能中连接主义和符号主义的一种新的关于智能的描述方智能中连接主义和符号主义的一种新的关于智能的描述方法。法。 l群智能的思路，为在没有集中控制且不提供全局模型的前群智能的思路，为在没有集中控制且不提供全局模型的前提下寻找复杂的分布式问题求解方案提供了基础。在计算提下寻找复杂的分布式问题求解方案提供了基础。在计算智能领域已取得成功的两种基于智能领域已取得成功的两种基于SI的优化算法是蚁群算法的优化算法是蚁群算法和粒子群算法。和粒子群算法。

6、Swarm Intelligencel 目前，已有的基于目前，已有的基于SI的优化算法都是源于对动物社会通的优化算法都是源于对动物社会通过协作解决问题行为的模拟，它主要强调对社会系统中个体过协作解决问题行为的模拟，它主要强调对社会系统中个体之间相互协同作用的模拟。这一点与遗传算法之间相互协同作用的模拟。这一点与遗传算法Genetic Algorithms-GA不同，不同，GA是对生物演化中适者生存的模拟。是对生物演化中适者生存的模拟。l与与GA一样的是，一样的是，SI的目的并不是为了忠实地模拟自然现象，的目的并不是为了忠实地模拟自然现象，而是利用他们的某些特点去解决实际问题。另一个与而是利用他

7、们的某些特点去解决实际问题。另一个与GA的的相同点是相同点是,基于基于SI的优化算法也是概率搜索算法。的优化算法也是概率搜索算法。Swarm Intelligencel 目前，已有的群智能理论和应用研究证明群智能方法目前，已有的群智能理论和应用研究证明群智能方法是一种能够是一种能够有效解决大多数优化问题的新方法有效解决大多数优化问题的新方法，更重要是，更重要是,群智能潜在的并行性和分布式特点为处理大量的以数据库群智能潜在的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。无论是从理论研究还是形式存在的数据提供了技术保证。无论是从理论研究还是应用研究的角度分析应用研究的角度分析

8、,群智能理论及应用研究都是具有重群智能理论及应用研究都是具有重要学术意义和现实价值的。要学术意义和现实价值的。Swarm Intelligence 由于由于SI的理论依据是源于对生物群社会性的模拟，因的理论依据是源于对生物群社会性的模拟，因此其相关数学分析还比较薄弱，这就导致了现有研究此其相关数学分析还比较薄弱，这就导致了现有研究还存在一些问题。还存在一些问题。数学理论基础薄弱数学理论基础薄弱：群智能算法的数学理论基础相对薄：群智能算法的数学理论基础相对薄弱，缺乏具备普遍意义的理论性分析，算法中涉及的弱，缺乏具备普遍意义的理论性分析，算法中涉及的各种参数设置一直没有确切的理论依据，通常都是按各

9、种参数设置一直没有确切的理论依据，通常都是按照经验型方法确定，对具体问题和应用环境的依赖性照经验型方法确定，对具体问题和应用环境的依赖性比较大。比较大。结果的可信性结果的可信性：同其它的自适应问题处理方法一样，群：同其它的自适应问题处理方法一样，群智能也不具备绝对的可信性，当处理突发事件时智能也不具备绝对的可信性，当处理突发事件时,系统系统的反应可能是不可测的的反应可能是不可测的,这在一定程度上增加了其应用这在一定程度上增加了其应用风险。风险。另外另外,群智能与其它各种先进技术群智能与其它各种先进技术(如如:神经网络、模糊逻神经网络、模糊逻辑、支持向量机等辑、支持向量机等) 的融合还不足的融合

10、还不足。 l无智能或简单智能的主体通过任何形式的聚集无智能或简单智能的主体通过任何形式的聚集协同而表现出智能行为的特性。协同而表现出智能行为的特性。 这里关心的不是个体之间的竞争，而是它们之间的协同（获取并共享信息）。 蚂蚁：信息素 鱼群：速度、方向、位置等，群体最佳和个体最佳位置 鸟群：速度、方向、位置等。 Swarm Intelligence(续续)基于群智能的优化算法基于群智能的优化算法l典型算法蚁群算法（蚂蚁觅食）粒子群算法（蜂群或鸟群觅食）鱼群算法（鱼群觅食）l优点灵活性稳健性自组织潜在的并行和分布 已有的群智能理论的研究和应用证明群智能方法是一已有的群智能理论的研究和应用证明群智能

11、方法是一种能够有效解决大多数优化问题的新方法。种能够有效解决大多数优化问题的新方法。粒子群优化算法粒子群优化算法（Particle Swarm Optimization, PSO）l由James Kenney（社会心理学（社会心理学博士）博士）肯尼迪和Russ Eberhart（电子工程学博士（电子工程学博士）艾伯哈特，1995年提出l模拟鸟群或蜂群的觅食行为l基本思想：通过群体中个体之间的协作和信息共享来寻找最优解, 肯尼迪鸟类的觅食鸟类的觅食l一群鸟在随机的搜索食物，在一块区域里只有一块食物，所有的鸟都不知道食物在哪。但是它们知道自己的当前位置距离食物有多远。l那么这群鸟找到食物的最优策略

12、是什么？群体协作群体协作-获取信息、共享信息获取信息、共享信息粒子群优化算法粒子群优化算法粒子群优化算法粒子群优化算法l每个鸟抽象为一个无质量，无体积的“粒子”l每个粒子有一个适应度函数以模拟每只鸟与食物的距离l每个粒子有一个速度决定它的飞行方向和距离，初始值可以随机确定l每一次单位时间的飞行后，所有粒子分享信息，下一步将飞向自身最佳位置和全局最优位置的加权中心粒子群优化算法流程粒子群优化算法流程wPSO算法算法 初始化为一群随机粒子，通过迭代找到最优。 每次迭代中，粒子通过跟踪“个体极值（pbest）”和“全局极值(gbest)”来 更新自己的位置。粒子群优化算法粒子群优化算法w粒子速度和位

13、置的更新粒子速度和位置的更新 假设在假设在D维搜索空间中，有维搜索空间中，有m个粒子；个粒子； 其中第其中第i个粒子的位置为矢量个粒子的位置为矢量 其飞翔速度也是一个矢量，记为其飞翔速度也是一个矢量，记为 第第i个粒子搜索到的最优位置为个粒子搜索到的最优位置为 整个粒子群搜索到的最优位置为整个粒子群搜索到的最优位置为 第第i个粒子的位置和速度更新为：个粒子的位置和速度更新为：Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid, 2 , 1 ;, 2 , 1 )()()()(11211),(21iDiiipppp),(21gbestDgbes

14、tgbestgbestpppp),(21iDiiixxxx),(21iDiiivvvv粒子群优化算法粒子群优化算法w粒子速度和位置的更新粒子速度和位置的更新 其中，其中，w称为惯性权重，称为惯性权重， c1和和c2为两个正常系数，称为加速因子。为两个正常系数，称为加速因子。 将将 vidk 限制在一个最大速度限制在一个最大速度 vmax 内。内。Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid, 2 , 1 ;, 2 , 1 )()()()(11211Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkid

15、idkidkid, 2 , 1 ;, 2 , 1 )()()()(11211“惯性部分惯性部分”，对自身运动状对自身运动状态的信任态的信任“认知部分认知部分”，对粒子，对粒子本身的思考，即来源本身的思考，即来源于自己经验的部分于自己经验的部分“社会部分社会部分”，粒间子的，粒间子的信息共享，来源于群体中信息共享，来源于群体中的其它优秀微粒的经验的其它优秀微粒的经验粒子群优化算法粒子群优化算法w算法流程算法流程 StartInitialize particles with random position and velocity vectors.For each particles positi

16、on (xi) evaluate fitnessIf fitness(xi) better than fitness(p) then p= xiLoop until all particles exhaustSet best of Ps as gBestUpdate particles velocity and positionLoop until max iterStop: giving gBest, optimal solution.基本粒子群算法描述基本粒子群算法描述粒子群优化算法粒子群优化算法w惯性权重惯性权重w 使粒子保持运动惯性，使其有扩展搜索空间的趋势，使粒子保持运动惯性，使其有

17、扩展搜索空间的趋势，有能力探索新的区域。有能力探索新的区域。 表示微粒对当前自身运动状态的信任，依据自身的表示微粒对当前自身运动状态的信任，依据自身的速度进行惯性运动。速度进行惯性运动。 较大的较大的w有利于跳出局部极值，而较小的有利于跳出局部极值，而较小的w有利于有利于算法收敛。算法收敛。Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid, 2 , 1 ;, 2 , 1 )()()()(11211粒子群优化算法粒子群优化算法w加速常数加速常数c1和和c2 代表将粒子推向代表将粒子推向pbest和和gbest位置的统计加速项的位置的统计加速

18、项的权重。权重。 表示粒子的动作来源于自己经验的部分和其它粒子表示粒子的动作来源于自己经验的部分和其它粒子 经验的部分。经验的部分。 较小的值允许粒子在被拉回之前可以在目标区域外较小的值允许粒子在被拉回之前可以在目标区域外徘徊，而较大的值则导致粒子突然冲向或越过目标徘徊，而较大的值则导致粒子突然冲向或越过目标区域。区域。 Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid, 2 , 1 ;, 2 , 1 )()()()(11211粒子群优化算法粒子群优化算法w加速常数加速常数c1和和c2 将将c1和和c2统一为一个控制参数，统一为一个控制参

19、数，= c1+c2 如果如果很小，粒子群运动轨迹将非常缓慢；很小，粒子群运动轨迹将非常缓慢； 如果如果很大，则微粒位置变化非常快；很大，则微粒位置变化非常快； 实验表明，当实验表明，当=4.1（通常（通常c1=2.0，c2=2.0）时，具）时，具有很好的有很好的收敛效果收敛效果。粒子群优化算法粒子群优化算法w粒子数粒子数 一般取一般取2040，对较难或特定类别的问题可以取，对较难或特定类别的问题可以取 100200。w最大速度最大速度vmax 决定粒子在一个循环中最大的移动距离，通常设定决定粒子在一个循环中最大的移动距离，通常设定为粒子的范围宽度。为粒子的范围宽度。w终止条件终止条件 最大循环

20、数以及最小错误要求。最大循环数以及最小错误要求。粒子群优化算法粒子群优化算法w共性共性 （1）都属于仿生算法；）都属于仿生算法； （2）都属于全局优化方法；）都属于全局优化方法； （3）都属于随机搜索算法；）都属于随机搜索算法； （4）都隐含并行性；）都隐含并行性； （5）根据个体的适配信息进行搜索，因此不受函）根据个体的适配信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等；数约束条件的限制，如连续性、可导性等； （6）对高维复杂问题，往往会遇到早熟收敛和收）对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证收敛到最优点。敛性能差的缺点，都无法保证收敛到最优点。 粒子

21、群优化算法粒子群优化算法w差异差异 （1）PSO有记忆，所有粒子都保存较优解的知识，有记忆，所有粒子都保存较优解的知识，而而GA，以前的知识随着种群的改变被改变；，以前的知识随着种群的改变被改变； （2）PSO中的粒子是一种单向共享信息机制。而中的粒子是一种单向共享信息机制。而GA中的染色体之间相互共享信息，使得整个种群中的染色体之间相互共享信息，使得整个种群都向最优区域移动；都向最优区域移动； （3）GA需要编码和遗传操作，而需要编码和遗传操作，而PSO没有交叉和没有交叉和变异操作，粒子只是通过内部速度进行更新，因此变异操作，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易

22、。原理更简单、参数更少、实现更容易。粒子群优化算法流程粒子群优化算法流程1、初始化一群粒子（群体规模），包括随机的位置和速度2、评价每个粒子的适应度3、对每个粒子更新个体最优位置4、更新全局最优位置5、根据速度和位置方程更新每个粒子的速度和位置6、如未满足结束条件（通常为满足足够好的适应值或达到设定的最大迭代次数），返回2粒子群优化算法的应用粒子群优化算法的应用广泛应用于各类优化问题上在军事领域中的应用对巡航导弹的飞行高度进行优化不同的飞行高度对巡航导弹的创地概率和突破防空系统的成功概率有较大影响，通过优化可以得到在防空阶段损失最小的最佳飞行高度美国“战斧”Block IV型攻陆巡航导弹粒子群

23、优化算法的应用粒子群优化算法的应用车辆路径问题的应用邮政投递火车及汽车的调度港口装卸集装箱蚁群算法蚁群算法l1992年由意大利的学者多里戈提出l模拟自然界中蚂蚁寻找从巢穴到食物的最佳路径的行为l一种新型的优化算法l蚁群的自组织行为蚁群的自组织行为 1989年，年，戈斯戈斯等研究蚂蚁觅等研究蚂蚁觅食的食的“双桥实验双桥实验” 通过遗留在来往路径通过遗留在来往路径 上的信息素上的信息素 （Pheromone）的挥）的挥 发性化学物质来进行发性化学物质来进行 通信和协调。通信和协调。蚁穴蚁穴食物食物神奇的信息素神奇的信息素l蚂蚁觅食的过程l随机移动l遇到食物返回的路上分泌信息素l信息素：易挥发性的化

24、学物质l在回家的路上留下信息素l其它蚂蚁发现留有信息素的路径结束漫游，沿着该路径移动，遇到食物同样返回途中分泌信息素。l信息素会随着时间慢慢挥发，关键路径上的信息素相对浓度高初始运行一段时间蚂蚁系统蚂蚁系统l多里戈在其博士论文中提出了一种蚂蚁系统（ANT SYSTEM AS）,以解决旅行商问题（TSP）l一个售货员希望去访问若干个城市，开始和结束于同一城市，每两个城市之间都有一条直接通路，怎样行走才能使走过的路径最短？蚁群算法蚁群算法l蚂蚁在两个城市之间移动l两个城市之间的信息素越多，蚂蚁就越有可能选择它们之间的路径l能够成功完成遍历的蚂蚁会在路径上留下信息素，路径越短留下的信息素会越多。蚁群

25、算法原理蚁群算法原理l基于蚂蚁觅食时的最优路径选择问题，可以构造人工蚁群，来解决最优问题。l人工蚁群中把具有简单功能的工作单元看作蚂蚁l人工蚂蚁与自然蚁群l相似之处：优先选择信息素浓度大的路径l区别：人工蚂蚁有一定的记忆能力，能够记忆已经访问过的节点l人工蚁群在选择下一条路径的时候是按一定的算法有意识的寻找最短路径，而不是盲目的。蚁群算法中的各种行为因子蚁群算法中的各种行为因子范围范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径，那么它能观察到的范围以及能够移动的范围都会发生在这样的一个范围之内环境环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有其他的蚂蚁，还有信息素，信息

26、素可以设计为单一种类也可以多种类（如两种），一种是找到食物的蚂蚁撒下的食物信息素，另外一种是找到食物的蚂蚁洒下的蚁窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。同时环境也以一定的速率让信息素消失。蚁群算法中的各种行为因子蚁群算法中的各种行为因子觅食规则觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则通过比较在能感知的范围内的信息素的多少，然后它会向信息素最多的方向移动。同时每只蚂蚁还以小概率来进行“犯错”。从而并不总是向信息素最多的方向移动。蚂蚁找到窝的规则和上面的相同，只不过它只对窝的信息素进行反应，而对食物信息素没有任何反应移动规则移动规则：每只蚂蚁都向信息素最多的方向前进，并且在运动方向上有一个随机的小扰动。为了防止蚂蚁原地转圈，它会记住刚才走过了那些点，