1、Artificial Intelligence (AI)人工智能人工智能第九章：群智第九章：群智能系统能系统内容提要第九章：群智能系统第九章：群智能系统1.1.粒子群优化算法粒子群优化算法2.2.蚁群算法蚁群算法内容提要第九章：群智能系统第九章：群智能系统1.1.粒子群优化算法粒子群优化算法2.2.蚁群算法蚁群算法n描述描述 群智能作为一种新兴的演化计算技术已成为研究焦群智能作为一种新兴的演化计算技术已成为研究焦点，它与人工生命，特别是进化策略以及遗传算法点，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的关系。有着极为特殊的关系。n特性特性 指无智能的主体通过合作表现出智能行为的特性，
2、指无智能的主体通过合作表现出智能行为的特性，在没有集中控制且不提供全局模型的前提下，为寻在没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题求解方案提供了基础。找复杂的分布式问题求解方案提供了基础。群智能n优点优点 灵活性：群体可以适应随时变化的环境；灵活性：群体可以适应随时变化的环境；稳健性：即使个体失败，整个群体仍能完成任务；稳健性：即使个体失败，整个群体仍能完成任务； 自我组织：活动既不受中央控制，也不受局部监管。自我组织：活动既不受中央控制，也不受局部监管。n典型算法典型算法 蚁群算法（蚂蚁觅食）蚁群算法（蚂蚁觅食） 粒子群算法（鸟群捕食）粒子群算法（鸟群捕食）群智能粒子群算
3、法原理粒子群算法原理粒子群算法原理粒子群算法原理n由由James Kenney（社会心理学博士）和（社会心理学博士）和Russ Eberhart（电子工程学博士，（电子工程学博士， http:/www.engr.iupui.edu/eberhart/ ）于）于1995年提年提出粒子群算法（出粒子群算法（Particle Swarm Optimization, PSO） 粒子群算法原理粒子群算法原理生物界现象生物界现象群体行为群体行为群体迁徙群体迁徙生物觅食生物觅食社会心理学社会心理学群体智慧群体智慧个体认知个体认知社会影响社会影响 人工生命人工生命鸟群觅食鸟群觅食鱼群学习鱼群学习群理论群理论粒
4、子群算法原理粒子群算法原理鸟群觅食现象鸟群觅食现象鸟群鸟群觅食空间觅食空间飞行速度飞行速度所在位置所在位置个体认知与群体协作个体认知与群体协作找到食物找到食物粒子群优化算法粒子群优化算法搜索空间的一组有效解搜索空间的一组有效解问题的搜索空间问题的搜索空间解的速度向量解的速度向量解的位置向量解的位置向量速度与位置的更新速度与位置的更新找到全局最优解找到全局最优解粒子群优化算法粒子群优化算法类比关系类比关系鸟群觅食现象鸟群觅食现象n源于对鸟群捕食行为的研究，是基于迭代的方法源于对鸟群捕食行为的研究，是基于迭代的方法n简单易于实现，需要调整的参数相对较少简单易于实现，需要调整的参数相对较少n在函数优
5、化、神经网络训练、工业系统优化和模糊在函数优化、神经网络训练、工业系统优化和模糊系统控制等领域得到了广泛的应用。系统控制等领域得到了广泛的应用。粒子群算法原理n鸟群：鸟群： 假设一个区域，所有的鸟都不知道食物的位置，但假设一个区域，所有的鸟都不知道食物的位置，但是它们知道当前位置离食物还有多远。是它们知道当前位置离食物还有多远。nPSO算法算法 每个解看作一只鸟，称为每个解看作一只鸟，称为“粒子粒子(particle)”，所有，所有的粒子都有一个适应值，每个粒子都有一个速度决的粒子都有一个适应值，每个粒子都有一个速度决定它们的飞翔方向和距离，粒子们追随当前最优粒定它们的飞翔方向和距离，粒子们追
6、随当前最优粒子在解空间中搜索。子在解空间中搜索。粒子群算法原理算法流程PSO中的个体，也叫中的个体，也叫粒子粒子，在多维搜索空间中飞行。，在多维搜索空间中飞行。PSO中的每个粒子维护两个向量中的每个粒子维护两个向量 位置向量位置向量xi ：粒子在解空间中的当前位置：粒子在解空间中的当前位置 速度向量速度向量vi ：粒子在解空间中的飞行速度：粒子在解空间中的飞行速度pBest ：粒子自身的历史最优位置：粒子自身的历史最优位置gBest ：群体全局最优向量：群体全局最优向量 lBest ：邻域中的最好位置：邻域中的最好位置nPSO算法算法 初始化为一群随机粒子，通过迭代找到最优。初始化为一群随机粒
7、子，通过迭代找到最优。 每次迭代中，粒子通过跟踪每次迭代中，粒子通过跟踪“个体极值（个体极值（pbest）”和和“全局极值全局极值(gbest)”来来 更新自己的位置。更新自己的位置。算法流程算法流程(t)iv 令令 表示表示t t时刻第时刻第i i 个粒子个粒子 在超空间的位置。在超空间的位置。把速度矢量把速度矢量 加至当前位置，则加至当前位置，则 的位置变为：的位置变为：(t)ixiP(t)(t1)(t)iiixxviP算法流程速度向量反映了粒子速度向量反映了粒子自身的经验知识自身的经验知识和和来自邻域粒子来自邻域粒子的社会交换信息的社会交换信息。粒子的经验知识通常叫做粒子的经验知识通常叫
8、做认知部分认知部分，它和粒子与其，它和粒子与其自自身的身的历史最优位置（历史最优位置（ pbest ）的距离成正比。）的距离成正比。社会交换信息叫做速度方程的社会交换信息叫做速度方程的社会部分社会部分。gbest PSO，全局最佳粒子群优化，全局最佳粒子群优化lbest PSO，局部最佳粒子群优化，局部最佳粒子群优化算法流程粒子群算法v粒子群算法的特点粒子群算法的特点PSO算法收敛速度快，特别是在算法的早期，但也存在算法收敛速度快，特别是在算法的早期，但也存在着精度较低，易发散等缺点。着精度较低，易发散等缺点。若加速系数、最大速度等参数太大，粒子群可能错过若加速系数、最大速度等参数太大，粒子群
9、可能错过最优解，算法不收敛；最优解，算法不收敛；而在收敛的情况下，由于所有的粒子都向最优解的方而在收敛的情况下，由于所有的粒子都向最优解的方向飞去，所以粒子趋向同一化（失去了多样性），使向飞去，所以粒子趋向同一化（失去了多样性），使得后期收敛速度明显变慢，同时算法收敛到一定精度得后期收敛速度明显变慢，同时算法收敛到一定精度时，无法继续优化，所能达到的精度也不高。时，无法继续优化，所能达到的精度也不高。内容提要第九章：群智能系统第九章：群智能系统1.1.粒子群优化算法粒子群优化算法2.2.蚁群算法蚁群算法蚁群算法原理蚁群算法原理蚁群算法原理蚁群算法原理育婴室育婴室储备室储备室寝室寝室蚁后室蚁后室
10、日光浴场日光浴场入口入口蚁群算法原理 通过遗留在来往路径上的信息素（通过遗留在来往路径上的信息素（Pheromone）的挥发性化学物质来进行的挥发性化学物质来进行 通信和协调。通信和协调。蚁群算法v蚁群觅食过程蚁群觅食过程算法基本原理自然界蚂蚁觅食行为自然界蚂蚁觅食行为蚁群优化算法蚁群优化算法蚁群蚁群搜索空间的一组有效解搜索空间的一组有效解问题的搜索空间问题的搜索空间信息素浓度变量信息素浓度变量一个有效解一个有效解问题的最优解问题的最优解觅食空间觅食空间信息素信息素蚁巢到食物的一条路径蚁巢到食物的一条路径找到的最短路径找到的最短路径对对应应关关系系算法基本原理 蚂蚁在寻找食物的过程中往往是蚂蚁
11、在寻找食物的过程中往往是随机选择路径随机选择路径的，但它们能的，但它们能感知当前地面上的信息素浓度感知当前地面上的信息素浓度，并倾向于往信息素浓度高的并倾向于往信息素浓度高的方向行进方向行进。信息素由蚂蚁自身释放，是实现蚁群内间接通信。信息素由蚂蚁自身释放，是实现蚁群内间接通信的物质。的物质。 由于较短路径上蚂蚁的往返时间比较短，单位时间内经过该由于较短路径上蚂蚁的往返时间比较短，单位时间内经过该路径的蚂蚁多，所以信息素的积累速度比较长路径快。因此，路径的蚂蚁多，所以信息素的积累速度比较长路径快。因此，当后续蚂蚁在路口时，就能感知先前蚂蚁留下的信息，并倾当后续蚂蚁在路口时，就能感知先前蚂蚁留下
12、的信息，并倾向于选择一条较短的路径前行。向于选择一条较短的路径前行。 这种这种正反馈机制正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的最使得越来越多的蚂蚁在巢穴与食物之间的最短路径上行进。由于其他路径上的信息素会短路径上行进。由于其他路径上的信息素会随着时间蒸发随着时间蒸发，最终所有的蚂蚁都在最优路径上行进。最终所有的蚂蚁都在最优路径上行进。蚁群算法流程路径构建路径构建每只蚂蚁都随机选择每只蚂蚁都随机选择一个城市作为其出发一个城市作为其出发城市，并维护一个路城市，并维护一个路径记忆向量，用来存径记忆向量，用来存放该蚂蚁依次经过的放该蚂蚁依次经过的城市。蚂蚁在构建路城市。蚂蚁在构建路径的每一步中
13、，按照径的每一步中，按照一个随机比例规则选一个随机比例规则选择下一个要到达的城择下一个要到达的城市。市。ACO基本要素基本要素信息素更新信息素更新当所有蚂蚁构建完路当所有蚂蚁构建完路径后，算法将会对所径后，算法将会对所有的路径进行全局信有的路径进行全局信息素的更新。注意，息素的更新。注意，我们所描述的是我们所描述的是AS的的ant-cycle版本版本，更新，更新是在全部蚂蚁均完成是在全部蚂蚁均完成了路径的构造后才进了路径的构造后才进行的，信息素的浓度行的，信息素的浓度变化与蚂蚁在这一轮变化与蚂蚁在这一轮中构建的路径长度相中构建的路径长度相关。关。 蚂蚁系统蚂蚁系统 (Ant System，AS
14、 ) 的蚂蚁圈（的蚂蚁圈（Ant -cycle）版本是最基本的）版本是最基本的ACO算法，是以算法，是以TSP作作为应用实例提出的。为应用实例提出的。蚁群算法流程伪随机比例选择规则伪随机比例选择规则 对于每只蚂蚁对于每只蚂蚁k，路径记忆向量，路径记忆向量Rk按照访问顺序记录了所有按照访问顺序记录了所有k已经已经经过的城市序号。经过的城市序号。 设蚂蚁设蚂蚁k当前所在城市为当前所在城市为i，则其选择城市，则其选择城市j作为下一个访问对象的作为下一个访问对象的概率如上式。概率如上式。Jk(i) 表示从城市表示从城市i 可以直接到达的、且又不在蚂蚁访可以直接到达的、且又不在蚂蚁访问过的城市序列问过的
15、城市序列Rk中的城市集合。中的城市集合。(i, j) 是一个启发式信息，通常由是一个启发式信息，通常由 (i, j)=1/dij 直接计算。直接计算。 (i, j) 表示边表示边(i, j)上的信息素量。上的信息素量。 ( )( , )( , ), if ( )( , )( , )( , ) 0, otherwisekkku Jii ji jjJipi ji ui u蚁群算法流程伪随机比例选择规则伪随机比例选择规则 长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。 和和是两个预先设置的参数，用来是两个预先设置的参数，用来控制启发式信息与信
16、息素浓度控制启发式信息与信息素浓度作用的权重关系作用的权重关系。 当当 =0时，算法演变成传统的随机贪心算法，最邻近城市被选中时，算法演变成传统的随机贪心算法，最邻近城市被选中的概率最大。当的概率最大。当 =0时，蚂蚁完全只根据信息素浓度确定路径，时，蚂蚁完全只根据信息素浓度确定路径，算法将快速收敛，这样构建出的最优路径与实际目标差异较大，算法将快速收敛，这样构建出的最优路径与实际目标差异较大，算法性能较差。算法性能较差。 ( )( , )( , ), if ( )( , )( , )( , ) 0, otherwisekkku Jii ji jjJipi ji ui u蚁群算法流程 (1)
17、在算法初始化时，问题空间中所有的边上的信息素都被在算法初始化时，问题空间中所有的边上的信息素都被初始化初始化为为0。 (2) 算法迭代每一轮，问题空间中的算法迭代每一轮，问题空间中的所有路径上的信息素都所有路径上的信息素都会发生蒸发会发生蒸发，我们为所有边上的信息素乘上一个小于，我们为所有边上的信息素乘上一个小于1的常的常数数( : 信息素的蒸发率信息素的蒸发率)。信息素蒸发是自然界本身固有的特。信息素蒸发是自然界本身固有的特征，在算法中能够帮助避免信息素的无限积累，使得算法可征，在算法中能够帮助避免信息素的无限积累，使得算法可以快速丢弃之前构建过的较差的路径。以快速丢弃之前构建过的较差的路径
18、。 (3) 蚂蚁根据自己构建的路径长度在它们本轮经过的边上释蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素。放信息素。蚂蚁构建的路径越短、释放的信息素就越多蚂蚁构建的路径越短、释放的信息素就越多。一。一条边被蚂蚁爬过的次数越多、它所获得的信息素也越多。条边被蚂蚁爬过的次数越多、它所获得的信息素也越多。 (4) 迭代迭代 (2)，直至算法终止。，直至算法终止。蚁群算法流程信息素的更新公式：信息素的更新公式： m：蚂蚁个数；：蚂蚁个数； ：信息素的蒸发率，规定：信息素的蒸发率，规定0r1。 (i, j)：第第k只蚂蚁在它经过的边上释放的信息素量，它等只蚂蚁在它经过的边上释放的信息素量，它
19、等于蚂蚁于蚂蚁k本轮构建路径长度的倒数。本轮构建路径长度的倒数。 Ck：路径长度，它是：路径长度，它是Rk中所有边的长度和。中所有边的长度和。11( , )(1)( , )( , ),(), if ( , ) ( , ) 0, otherwisemkkkkki ji ji jCi jRi j蚁群算法流程路径构建路径构建信息素更新信息素更新蚁群算法的应用车辆路径问题车辆路径问题（Vehicle Routing Problem，VRP）车间作业调度问题车间作业调度问题（Job-Shop Scheduling Problem，JSP）分配问题分配问题（Assignment problem, AP）网
20、络路由网络路由（ Network Routing）其他其他子集问题子集问题（Set Problem）ACOn共同特点共同特点 基于概率计算的随机搜索进化算法，在结构、研究基于概率计算的随机搜索进化算法，在结构、研究内容、方法以及步骤上有较大的相似性；内容、方法以及步骤上有较大的相似性；n存在的问题存在的问题 （1）数学理论基础相对薄弱；）数学理论基础相对薄弱； （2）参数设置没有确切的理论依据，对具体问题）参数设置没有确切的理论依据，对具体问题和应用环境的依赖性大；和应用环境的依赖性大；群智能优化的特点与不足n存在的问题存在的问题 （3）比较性研究不足，缺乏用于性能评估的标准）比较性研究不足，
21、缺乏用于性能评估的标准测试集；测试集； （4）不具备绝对的可信性，存在应用风险；）不具备绝对的可信性，存在应用风险；n进一步的工作进一步的工作 （1）进一步研究真实群居动物的行为特征；）进一步研究真实群居动物的行为特征； （2）进一步研究算法的收敛性；）进一步研究算法的收敛性； 群智能优化的特点与不足n存在的问题存在的问题 （3）进一步提高收敛速度，从而解决大规模优化）进一步提高收敛速度，从而解决大规模优化问题；问题； （4）进一步研究各种参数设置问题；）进一步研究各种参数设置问题； （5）研究群智能的并行算法；）研究群智能的并行算法； （6）进一步研究各算法的适用范围；）进一步研究各算法的适用范围； （7）研究与其它算法的混合技术。）研究与其它算法的混合技术。群智能优化的特点与不足其他计算智能方法v模拟退火模拟退火v人工免疫系统人工免疫系统v粗集理论粗集理论vEDA算法算法v文化进化计算文化进化计算v量子计算量子计算vDNA计算计算v智能智能Agentv
