湘潭大学人工智能课件群智能

ArtificialIntelligence(AI)

人工智能第九章：群智能系统ArtificialIntelligence(AI)

人内容提要第九章：群智能系统1.粒子群优化算法2.蚁群算法……内容提要第九章：群智能系统1.粒子群优化算法2.蚁群算法……内容提要第九章：群智能系统1.粒子群优化算法2.蚁群算法……内容提要第九章：群智能系统1.粒子群优化算法2.蚁群算法……描述群智能作为一种新兴的演化计算技术已成为研究焦点，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的关系。特性指无智能的主体通过合作表现出智能行为的特性，在没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题求解方案提供了基础。群智能描述群智能优点灵活性：群体可以适应随时变化的环境；

稳健性：即使个体失败，整个群体仍能完成任务；自我组织：活动既不受中央控制，也不受局部监管。典型算法蚁群算法（蚂蚁觅食）粒子群算法（鸟群捕食）群智能优点群智能粒子群算法原理粒子群算法（PSO）粒子群算法原理粒子群算法（PSO）粒子群算法原理粒子群算法（PSO）粒子群算法原理粒子群算法（PSO）粒子群算法原理粒子群算法（PSO）粒子群算法原理粒子群算法（PSO）粒子群算法原理粒子群算法（PSO）粒子群算法原理粒子群算法（PSO）由JamesKenney（社会心理学博士）和RussEberhart（电子工程学博士，/~eberhart/

）于1995年提出粒子群算法（ParticleSwarmOptimization,PSO）

粒子群算法的提出粒子群算法原理由JamesKenney（社会心理学博士）和RussEb粒子群算法原理PSO的思想来源生物界现象群体行为群体迁徙生物觅食……社会心理学群体智慧个体认知社会影响……粒子群优化算法

人工生命鸟群觅食鱼群学习群理论粒子群算法原理PSO的思想来源生物界现象社会心理学粒子群人工粒子群算法原理从生物现象到PSO算法鸟群觅食现象粒子群优化算法粒子群算法原理从生物现象到PSO算法鸟群觅食现象粒子群优化粒子群算法原理从生物现象到PSO算法鸟群觅食现象鸟群觅食空间飞行速度所在位置个体认知与群体协作找到食物粒子群优化算法搜索空间的一组有效解问题的搜索空间解的速度向量解的位置向量速度与位置的更新找到全局最优解粒子群优化算法类比关系鸟群觅食现象粒子群算法原理从生物现象到PSO算法鸟群觅食现象粒子群优化源于对鸟群捕食行为的研究，是基于迭代的方法简单易于实现，需要调整的参数相对较少在函数优化、神经网络训练、工业系统优化和模糊系统控制等领域得到了广泛的应用。粒子群算法原理

粒子群算法的提出源于对鸟群捕食行为的研究，是基于迭代的方法粒子群算法原理鸟群：假设一个区域，所有的鸟都不知道食物的位置，但是它们知道当前位置离食物还有多远。PSO算法

每个解看作一只鸟，称为“粒子(particle)”，所有的粒子都有一个适应值，每个粒子都有一个速度决定它们的飞翔方向和距离，粒子们追随当前最优粒子在解空间中搜索。

粒子群算法的原理描述粒子群算法原理鸟群：粒子群算法的原理描述粒子群算法原理算法流程PSO算法的相关定义PSO中的个体，也叫粒子，在多维搜索空间中飞行。PSO中的每个粒子维护两个向量位置向量xi

：粒子在解空间中的当前位置速度向量vi

：粒子在解空间中的飞行速度pBest：粒子自身的历史最优位置gBest：群体全局最优向量

lBest：邻域中的最好位置算法流程PSO算法的相关定义PSO算法

初始化为一群随机粒子，通过迭代找到最优。每次迭代中，粒子通过跟踪“个体极值（pbest）”和“全局极值(gbest)”来更新自己的位置。算法流程PSO算法算法流程算法流程粒子速度与位置的更新令表示t时刻第i个粒子在超空间的位置。把速度矢量加至当前位置，则的位置变为：算法流程粒子速度与位置的更新令表示t时刻算法流程PSO算法驱动优化过程的是速度vi(t)向量。速度向量反映了粒子自身的经验知识和来自邻域粒子的社会交换信息。粒子的经验知识通常叫做认知部分，它和粒子与其自身的历史最优位置（pbest）的距离成正比。社会交换信息叫做速度方程的社会部分。邻域大小不同的两种算法gbestPSO，全局最佳粒子群优化lbestPSO，局部最佳粒子群优化算法流程PSO算法驱动优化过程的是速度vi(t)向量。算法流程gbestPSO：全局最佳粒子群优化算法流程gbestPSO：全局最佳粒子群优化粒子群算法粒子群算法的特点PSO算法收敛速度快，特别是在算法的早期，但也存在着精度较低，易发散等缺点。若加速系数、最大速度等参数太大，粒子群可能错过最优解，算法不收敛；而在收敛的情况下，由于所有的粒子都向最优解的方向飞去，所以粒子趋向同一化（失去了多样性），使得后期收敛速度明显变慢，同时算法收敛到一定精度时，无法继续优化，所能达到的精度也不高。粒子群算法粒子群算法的特点内容提要第九章：群智能系统1.粒子群优化算法2.蚁群算法……内容提要第九章：群智能系统1.粒子群优化算法2.蚁群算法……蚁群算法原理蚁群的觅食行为蚁群算法原理蚁群的觅食行为蚁群算法原理蚁群的分工蚁群算法原理蚁群的分工蚁群算法原理蚁穴的结构蚁群算法原理蚁穴的结构蚁群算法原理蚁穴的结构育婴室储备室寝室蚁后室日光浴场入口蚁群算法原理蚁穴的结构育婴室储备室寝室蚁后室日光浴场入口蚁群算法原理蚁群觅食的“双桥实验”通过遗留在来往路径上的信息素（Pheromone）的挥发性化学物质来进行通信和协调。蚁群算法原理蚁群觅食的“双桥实验”通过遗留在来往路径上的蚁群算法蚁群觅食过程蚁群算法蚁群觅食过程算法基本原理自然界蚂蚁觅食行为蚁群优化算法蚁群搜索空间的一组有效解问题的搜索空间信息素浓度变量一个有效解问题的最优解觅食空间信息素蚁巢到食物的一条路径找到的最短路径对应关系算法基本原理自然界蚂蚁觅食行为蚁群优化算法蚁群搜索空间的一组算法基本原理蚁群优化算法（AntColonyOptimization

,ACO）蚂蚁在寻找食物的过程中往往是随机选择路径的，但它们能感知当前地面上的信息素浓度，并倾向于往信息素浓度高的方向行进。信息素由蚂蚁自身释放，是实现蚁群内间接通信的物质。由于较短路径上蚂蚁的往返时间比较短，单位时间内经过该路径的蚂蚁多，所以信息素的积累速度比较长路径快。因此，当后续蚂蚁在路口时，就能感知先前蚂蚁留下的信息，并倾向于选择一条较短的路径前行。这种正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的最短路径上行进。由于其他路径上的信息素会随着时间蒸发，最终所有的蚂蚁都在最优路径上行进。算法基本原理蚁群优化算法（AntColonyOptim蚁群算法流程路径构建每只蚂蚁都随机选择一个城市作为其出发城市，并维护一个路径记忆向量，用来存放该蚂蚁依次经过的城市。蚂蚁在构建路径的每一步中，按照一个随机比例规则选择下一个要到达的城市。ACO基本要素信息素更新当所有蚂蚁构建完路径后，算法将会对所有的路径进行全局信息素的更新。注意，我们所描述的是AS的ant-cycle版本，更新是在全部蚂蚁均完成了路径的构造后才进行的，信息素的浓度变化与蚂蚁在这一轮中构建的路径长度相关。

蚂蚁系统(AntSystem，AS)的蚂蚁圈（Ant-cycle）版本是最基本的ACO算法，是以TSP作为应用实例提出的。蚁群算法流程路径构建ACO基本要素信息素更新蚂蚁系蚁群算法流程路径构建：伪随机比例选择规则对于每只蚂蚁k，路径记忆向量Rk按照访问顺序记录了所有k已经经过的城市序号。设蚂蚁k当前所在城市为i，则其选择城市j作为下一个访问对象的概率如上式。Jk(i)表示从城市i可以直接到达的、且又不在蚂蚁访问过的城市序列Rk中的城市集合。η(i,j)是一个启发式信息，通常由η(i,j)=1/dij直接计算。τ

(i,j)表示边(i,j)上的信息素量。蚁群算法流程路径构建：伪随机比例选择规则蚁群算法流程路径构建：伪随机比例选择规则长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。α和β是两个预先设置的参数，用来控制启发式信息与信息素浓度作用的权重关系。当α

=0时，算法演变成传统的随机贪心算法，最邻近城市被选中的概率最大。当β

=0时，蚂蚁完全只根据信息素浓度确定路径，算法将快速收敛，这样构建出的最优路径与实际目标差异较大，算法性能较差。蚁群算法流程路径构建：伪随机比例选择规则蚁群算法流程信息素更新：(1)在算法初始化时，问题空间中所有的边上的信息素都被初始化为τ0。(2)算法迭代每一轮，问题空间中的所有路径上的信息素都会发生蒸发，我们为所有边上的信息素乘上一个小于1的常数(ρ:

信息素的蒸发率)。信息素蒸发是自然界本身固有的特征，在算法中能够帮助避免信息素的无限积累，使得算法可以快速丢弃之前构建过的较差的路径。(3)蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素。蚂蚁构建的路径越短、释放的信息素就越多。一条边被蚂蚁爬过的次数越多、它所获得的信息素也越多。(4)迭代(2)，直至算法终止。蚁群算法流程信息素更新：蚁群算法流程信息素更新：信息素的更新公式：m：蚂蚁个数；ρ：信息素的蒸发率，规定0<r≤1。Δτ

(i,j)：第k只蚂蚁在它经过的边上释放的信息素量，它等于蚂蚁k本轮构建路径长度的倒数。Ck：路径长度，它是Rk中所有边的长度和。蚁群算法流程信息素更新：蚁群算法流程路径构建信息素更新蚁群算法流程路径构建信息素更新蚁群算法的应用车辆路径问题（VehicleRoutingProblem，VRP）车间作业调度问题（Job-ShopSchedulingProblem，JSP）分配问题（Assignmentproblem,AP）网络路由（NetworkRouting）其他……子集问题（SetProblem）ACO蚁群算法的应用车辆路径问题车间作业调度问题分配问题网络路由其共同特点基于概率计算的随机搜索进化算法，在结构、研究内容、方法以及步骤上有较大的相似性；存在的问题（1）数学理论基础相对薄弱；（2）参数设置没有确切的理论依据，对具体问题和应用环境的依赖性大；群智能优化的特点与不足共同特点群智能优化的特点与不足存在的问题（3）比较性研究不足，缺乏用于性能评估的标准测试集；（4）不具备绝对的可信性，存在应用风险；进一步的工作（1）进一步研究真实群居动物的行为特征；（2）进一步研究算法的收敛性；

群智能优化的特点与不足存在的问题群智能优化的特点与不足存在的问题（3）进一步提高收敛速度，从而解决大规模优化问题；（4）进一步研究各种参数设置问题；（5）研究群智能的并行算法；（6）进一步研究各算法的适用范围；（7）研究与其它算法的混合技术。群智能优化的特点与不足存在的问题群智能优化的特点与不足其他计算智能方法模拟退火人工免疫系统粗集理论EDA算法文化进化计算量子计算DNA计算智能Agent……其他计算智能方法模拟退火问题？问题？ArtificialIntelligence(AI)

人工智能第九章：群智能系统ArtificialIntelligence(AI)

人内容提要第九章：群智能系统1.粒子群优化算法2.蚁群算法……内容提要第九章：群智能系统1.粒子群优化算法2.蚁群算法……内容提要第九章：群智能系统1.粒子群优化算法2.蚁群算法……内容提要第九章：群智能系统1.粒子群优化算法2.蚁群算法……描述群智能作为一种新兴的演化计算技术已成为研究焦点，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的关系。特性指无智能的主体通过合作表现出智能行为的特性，在没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题求解方案提供了基础。群智能描述群智能优点灵活性：群体可以适应随时变化的环境；

稳健性：即使个体失败，整个群体仍能完成任务；自我组织：活动既不受中央控制，也不受局部监管。典型算法蚁群算法（蚂蚁觅食）粒子群算法（鸟群捕食）群智能优点群智能粒子群算法原理粒子群算法（PSO）粒子群算法原理粒子群算法（PSO）粒子群算法原理粒子群算法（PSO）粒子群算法原理粒子群算法（PSO）粒子群算法原理粒子群算法（PSO）粒子群算法原理粒子群算法（PSO）粒子群算法原理粒子群算法（PSO）粒子群算法原理粒子群算法（PSO）由JamesKenney（社会心理学博士）和RussEberhart（电子工程学博士，/~eberhart/

）于1995年提出粒子群算法（ParticleSwarmOptimization,PSO）

粒子群算法的提出粒子群算法原理由JamesKenney（社会心理学博士）和RussEb粒子群算法原理PSO的思想来源生物界现象群体行为群体迁徙生物觅食……社会心理学群体智慧个体认知社会影响……粒子群优化算法

人工生命鸟群觅食鱼群学习群理论粒子群算法原理PSO的思想来源生物界现象社会心理学粒子群人工粒子群算法原理从生物现象到PSO算法鸟群觅食现象粒子群优化算法粒子群算法原理从生物现象到PSO算法鸟群觅食现象粒子群优化粒子群算法原理从生物现象到PSO算法鸟群觅食现象鸟群觅食空间飞行速度所在位置个体认知与群体协作找到食物粒子群优化算法搜索空间的一组有效解问题的搜索空间解的速度向量解的位置向量速度与位置的更新找到全局最优解粒子群优化算法类比关系鸟群觅食现象粒子群算法原理从生物现象到PSO算法鸟群觅食现象粒子群优化源于对鸟群捕食行为的研究，是基于迭代的方法简单易于实现，需要调整的参数相对较少在函数优化、神经网络训练、工业系统优化和模糊系统控制等领域得到了广泛的应用。粒子群算法原理

粒子群算法的提出源于对鸟群捕食行为的研究，是基于迭代的方法粒子群算法原理鸟群：假设一个区域，所有的鸟都不知道食物的位置，但是它们知道当前位置离食物还有多远。PSO算法

每个解看作一只鸟，称为“粒子(particle)”，所有的粒子都有一个适应值，每个粒子都有一个速度决定它们的飞翔方向和距离，粒子们追随当前最优粒子在解空间中搜索。

粒子群算法的原理描述粒子群算法原理鸟群：粒子群算法的原理描述粒子群算法原理算法流程PSO算法的相关定义PSO中的个体，也叫粒子，在多维搜索空间中飞行。PSO中的每个粒子维护两个向量位置向量xi

：粒子在解空间中的当前位置速度向量vi

：粒子在解空间中的飞行速度pBest：粒子自身的历史最优位置gBest：群体全局最优向量

lBest：邻域中的最好位置算法流程PSO算法的相关定义PSO算法

初始化为一群随机粒子，通过迭代找到最优。每次迭代中，粒子通过跟踪“个体极值（pbest）”和“全局极值(gbest)”来更新自己的位置。算法流程PSO算法算法流程算法流程粒子速度与位置的更新令表示t时刻第i个粒子在超空间的位置。把速度矢量加至当前位置，则的位置变为：算法流程粒子速度与位置的更新令表示t时刻算法流程PSO算法驱动优化过程的是速度vi(t)向量。速度向量反映了粒子自身的经验知识和来自邻域粒子的社会交换信息。粒子的经验知识通常叫做认知部分，它和粒子与其自身的历史最优位置（pbest）的距离成正比。社会交换信息叫做速度方程的社会部分。邻域大小不同的两种算法gbestPSO，全局最佳粒子群优化lbestPSO，局部最佳粒子群优化算法流程PSO算法驱动优化过程的是速度vi(t)向量。算法流程gbestPSO：全局最佳粒子群优化算法流程gbestPSO：全局最佳粒子群优化粒子群算法粒子群算法的特点PSO算法收敛速度快，特别是在算法的早期，但也存在着精度较低，易发散等缺点。若加速系数、最大速度等参数太大，粒子群可能错过最优解，算法不收敛；而在收敛的情况下，由于所有的粒子都向最优解的方向飞去，所以粒子趋向同一化（失去了多样性），使得后期收敛速度明显变慢，同时算法收敛到一定精度时，无法继续优化，所能达到的精度也不高。粒子群算法粒子群算法的特点内容提要第九章：群智能系统1.粒子群优化算法2.蚁群算法……内容提要第九章：群智能系统1.粒子群优化算法2.蚁群算法……蚁群算法原理蚁群的觅食行为蚁群算法原理蚁群的觅食行为蚁群算法原理蚁群的分工蚁群算法原理蚁群的分工蚁群算法原理蚁穴的结构蚁群算法原理蚁穴的结构蚁群算法原理蚁穴的结构育婴室储备室寝室蚁后室日光浴场入口蚁群算法原理蚁穴的结构育婴室储备室寝室蚁后室日光浴场入口蚁群算法原理蚁群觅食的“双桥实验”通过遗留在来往路径上的信息素（Pheromone）的挥发性化学物质来进行通信和协调。蚁群算法原理蚁群觅食的“双桥实验”通过遗留在来往路径上的蚁群算法蚁群觅食过程蚁群算法蚁群觅食过程算法基本原理自然界蚂蚁觅食行为蚁群优化算法蚁群搜索空间的一组有效解问题的搜索空间信息素浓度变量一个有效解问题的最优解觅食空间信息素蚁巢到食物的一条路径找到的最短路径对应关系算法基本原理自然界蚂蚁觅食行为蚁群优化算法蚁群搜索空间的一组算法基本原理蚁群优化算法（AntColonyOptimization

,ACO）蚂蚁在寻找食物的过程中往往是随机选择路径的，但它们能感知当前地面上的信息素浓度，并倾向于往信息素浓度高的方向行进。信息素由蚂蚁自身释放，是实现蚁群内间接通信的物质。由于较短路径上蚂蚁的往返时间比较短，单位时间内经过该路径的蚂蚁多，所以信息素的积累速度比较长路径快。因此，当后续蚂蚁在路口时，就能感知先前蚂蚁留下的信息，并倾向于选择一条较短的路径前行。这种正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的最短路径上行进。由于其他路径上的信息素会随着时间蒸发，最终所有的蚂蚁都在最优路径上行进。算法基本原理蚁群优化算法（AntColonyOptim蚁群算法流程路径构建每只蚂蚁都随机选择一个城市作为其出发城市，并维护一个路径记忆向量，用来存放该蚂蚁依次经过的城市。蚂蚁在构建路径的每一步中，按照一个随机比例规则选择下一个要到达的城市。ACO基本要素信息素更新当所有蚂蚁构建完路径后，算法将会对所有的路径进行全局信息素的更新。注意，我们所描述的是AS的ant-cycle版本，更新是在全部蚂蚁均完成了路径的构造后才进行的，信息素的浓度变化与蚂蚁在这一轮中构建的路径长度相关。

蚂蚁系统(AntSystem，AS)的蚂蚁圈（Ant-cycle）版本是最基本的ACO算法，是以TSP作为应用实例提出的。蚁群算法流程路径构建ACO基本要素信息素更新蚂蚁系蚁群算法流程路径构建：伪随机比例选择规则对于每只蚂蚁k，路径记忆向量Rk按照访问顺序记录了所有k已经经过的城市序号。设蚂蚁k当前所在城市为i，则其选择城市j作为下一个访问对象的概率如上式。Jk(i)表示从城市i可以直接到达的、且又不在蚂蚁访问过的城市序列Rk中的城市集合。η(i,j)是一个启发式信息，通常由η(i,j)=1/dij直接计算。τ

(i,j)表示边(i,j)上的信息素量。蚁群算法流程路径构建：伪随机比例选择规则蚁群算法流程路径构建：伪随机比例选择规则长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。α和β是两个预先设置的参数，用来控制启发式信息与信息素浓度作用的权重关系。当α

=0时，算法演变成传统的随机贪心算法，最邻近城市被选中的概率最大。当β

=0时，蚂蚁完全只根据信息素浓度确定路径，算法将快速收敛，这样构建出的最优路径与实际目标差异较大，算法性能较差。蚁群算法流程路径构建：伪随机比例选择规则蚁群算法流程信息素更新：(1)在算法初始化时，问题空间中所有的边上的信息素都被初始化为τ0。(2)算法迭代每一轮，问题空间中的所有路径上的信息素都会发生蒸发，我们为所有边上的信息素乘上一个小于1的常数(ρ:

信息素的蒸发率)。信息素蒸发是自然界本身固有的特征，在算法中能够帮助避免信息素的无限积累，使得算法可以快速丢弃之前构建过的较差的路径。(3)蚂蚁根据自己构建的路径长度在它们本轮经过的