湘潭大学人工智能课件群

,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,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,（电子工程学博士，,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,问题？,