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

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