粒子群算法最全的ppt

第六章群智能算法智能优化计算华东理工大学自动化系2007年6.1群智能6.1.1群智能的概念6.1.2群智能算法6.2蚁群优化算法原理6.2.1蚁群算法的起源6.2.2蚁群算法的原理分析6.3基本蚁群优化算法6.3.1蚂蚁系统的模型与实现6.3.2蚂蚁系统的参数设置和基本属性6.4改进的蚁群优化算法6.4.1蚂蚁系统的优点与不足6.4.2最优解保留策略蚂蚁系统6.4.3蚁群系统6.4.4最大－最小蚂蚁系统6.4.5基于排序的蚂蚁系统6.4.6各种蚁群优化算法的比较智能优化计算华东理工大学自动化系2007年6.5蚁群优化算法的应用6.5.1典型应用6.5.2医学诊断的数据挖掘6.6粒子群算法的基本原理6.6.1粒子群算法的提出6.6.2粒子群算法的原理描述6.7基本粒子群优化算法6.7.1基本粒子群算法描述6.7.2参数分析6.7.3与遗传算法的比较6.8改进粒子群优化算法6.8.1离散二进制PSO6.8.2惯性权重模型6.8.3收敛因子模型6.8.4研究现状智能优化计算华东理工大学自动化系2007年6.9粒子群优化算法的应用6.9.1求解TSP问题6.9.2其它应用6.10群智能算法的特点与不足智能优化计算华东理工大学自动化系2007年6.1群智能智能优化计算华东理工大学自动化系2007年群智能（SwarmIntelligence,SI）人们把群居昆虫的集体行为称作“群智能”（“群体智能”、“群集智能”、“集群智能”等）特点个体的行为很简单，但当它们一起协同工作时，却能够突现出非常复杂（智能）的行为特征。6.1.1群智能的概念6.1群智能智能优化计算华东理工大学自动化系2007年描述群智能作为一种新兴的演化计算技术已成为研究焦点，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的关系。特性指无智能的主体通过合作表现出智能行为的特性，在没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题求解方案提供了基础。6.1.2群智能算法6.1群智能智能优化计算华东理工大学自动化系2007年优点灵活性：群体可以适应随时变化的环境；稳健性：即使个体失败，整个群体仍能完成任务；自我组织：活动既不受中央控制，也不受局部监管。典型算法蚁群算法（蚂蚁觅食）粒子群算法（鸟群捕食）6.1.2群智能算法6.2蚁群优化算法原理智能优化计算华东理工大学自动化系2007年蚁群的自组织行为“双桥实验”通过遗留在来往路径上的信息素（Pheromone）的挥发性化学物质来进行通信和协调。6.2.1蚁群算法的起源6.2蚁群优化算法原理智能优化计算华东理工大学自动化系2007年蚁群的自组织行为“双桥实验”6.2.1蚁群算法的起源6.2蚁群优化算法原理智能优化计算华东理工大学自动化系2007年提出蚁群系统1992年，意大利学者M.Dorigo在其博士论文中提出蚂蚁系统（AntSystem）。近年来，M.Dorigo等人进一步将蚂蚁算法发展为一种通用的优化技术——蚁群优化（antcolonyoptimization,ACO）。6.2.1蚁群算法的起源蚂蚁从A点出发，随机选择路线ABD或ACD。经过9个时间单位时：走ABD的蚂蚁到达终点，走ACD的蚂蚁刚好走到C点。6.2蚁群优化算法原理智能优化计算华东理工大学自动化系2007年6.2.2蚁群算法的原理分析蚁巢食物6.2蚁群优化算法原理智能优化计算华东理工大学自动化系2007年经过18个时间单位时：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。6.2.2蚁群算法的原理分析蚁巢食物最后的极限是所有的蚂蚁只选择ABD路线。（正反馈过程）6.2蚁群优化算法原理智能优化计算华东理工大学自动化系2007年6.2.2蚁群算法的原理分析蚁巢食物6.3基本蚁群优化算法智能优化计算华东理工大学自动化系2007年解决TSP问题在算法的初始时刻，将m只蚂蚁随机放到n座城市;将每只蚂蚁k的禁忌表tabuk(s)的第一个元素tabuk(1)设置为它当前所在城市;设各路径上的信息素τij(0)=C（C为一较小的常数）;6.3.1蚂蚁系统的模型与实现6.3基本蚁群优化算法智能优化计算华东理工大学自动化系2007年解决TSP问题每只蚂蚁根据路径上的信息素和启发式信息（两城市间距离）独立地选择下一座城市：在时刻t，蚂蚁k从城市i转移到城市j的概率为α、β分别表示信息素和启发式因子的相对重要程度。6.3.1蚂蚁系统的模型与实现ijijkkkkiJsisisijijkijdtabuniJiJjiJjtttttpk/1,,,2,1)()(,0)(,)]([)]([)]([)]([)()(下一步允许的城市的集合6.3基本蚁群优化算法智能优化计算华东理工大学自动化系2007年解决TSP问题当所有蚂蚁完成一次周游后，各路径上的信息素将进行更新：其中，ρ（0ρ1）表示路径上信息素的蒸发系数，Q为正常数，Lk表示第k只蚂蚁在本次周游中所走过路径的长度。6.3.1蚂蚁系统的模型与实现否则在本次周游中经过边若蚂蚁,0,,)()1()(1ijkLQtntkkijmkkijijijijij6.3基本蚁群优化算法智能优化计算华东理工大学自动化系2007年算法流程6.3.1蚂蚁系统的模型与实现初始化：t=0;NC=0;τij(t)=C;Δτij(t)=0;将m只蚂蚁放到n座城市上禁忌表已满？s=s+1将m只蚂蚁按照其各自计算的转移概率pijk选择下一城市，并将该城市加入到禁忌表中。计算所有m只蚂蚁走过的周游长度Lk；更新当前的最优路径。计算Δτijk，更新信息素；t=t+n；NC=NC+1终止条件满足否？清空所有禁忌表置禁忌表索引s=1;并将其起点城市加入各自禁忌表中输出最优结果YNYN6.3基本蚁群优化算法ijijkkkkiJsisisijijkijdtabuniJiJjiJjtttttpk/1,,,2,1)()(,0)(,)]([)]([)]([)]([)()(智能优化计算华东理工大学自动化系2007年初始参数城市数30;蚂蚁数30；α=1;β=5;ρ=0.5;最大迭代代数200;Q=100;6.3.1蚂蚁系统的模型与实现否则经过边蚂蚁,0,,)()1()(1ijkLQtntkkijmkkijijijijij6.3基本蚁群优化算法智能优化计算华东理工大学自动化系2007年运行结果6.3.1蚂蚁系统的模型与实现6.3基本蚁群优化算法智能优化计算华东理工大学自动化系2007年运行结果6.3.1蚂蚁系统的模型与实现6.3基本蚁群优化算法智能优化计算华东理工大学自动化系2007年运行结果6.3.1蚂蚁系统的模型与实现6.3基本蚁群优化算法智能优化计算华东理工大学自动化系2007年运行结果6.3.1蚂蚁系统的模型与实现6.3基本蚁群优化算法智能优化计算华东理工大学自动化系2007年运行结果6.3.1蚂蚁系统的模型与实现6.3基本蚁群优化算法智能优化计算华东理工大学自动化系2007年运行结果6.3.1蚂蚁系统的模型与实现智能优化计算华东理工大学自动化系2007年三种模型ant-cycle：（蚁周）ant-quantity：（蚁量）ant-density:（蚁密）否则在本次周游中经过蚂蚁,0,ijkLQkkij否则经过和在时刻蚂蚁,01,ijttkQkij否则经过和在时刻蚂蚁,01,ijttkdQijkij6.3基本蚁群优化算法6.3.1蚂蚁系统的模型与实现智能优化计算华东理工大学自动化系2007年三种模型在Ant-density和Ant-quantity中蚂蚁在两个位置节点间每移动一次后即更新信息素（局部信息），而在Ant-cycle中当所有的蚂蚁都完成了自己的行程后（全局信息）才对信息素进行更新。6.3基本蚁群优化算法6.3.1蚂蚁系统的模型与实现智能优化计算华东理工大学自动化系2007年三种模型的比较模型ant-density,ant-quantity,ant-cycle的比较(M.Dorigo,1996)6.3基本蚁群优化算法6.3.1蚂蚁系统的模型与实现模型参数集最好参数集平均结果最好结果ant-densityα＝1,β=5,ρ=0.01426.740424.635ant-quantityα＝1,β=5,ρ=0.01427.315426.255☻ant-cycleα＝1,β=5,ρ=0.5424.250423.741智能优化计算华东理工大学自动化系2007年信息素的分布6.3基本蚁群优化算法6.3.2蚂蚁系统的参数设置和基本属性智能优化计算华东理工大学自动化系2007年信息素的分布蒸发系数的影响：6.3基本蚁群优化算法6.3.2蚂蚁系统的参数设置和基本属性ρ＝0.05ρ＝0.95否则经过边蚂蚁,0,,)()1()(1ijkLQtntkkijmkkijijijijij智能优化计算华东理工大学自动化系2007年参数α、β对算法性能的影响停滞现象（Stagnationbehavior）：所有蚂蚁都选择相同的路径，即系统不再搜索更好的解。原因在于较好路径上的信息素远大于其他边上的，从而使所有蚂蚁都选择该路径。6.3基本蚁群优化算法6.3.2蚂蚁系统的参数设置和基本属性智能优化计算华东理工大学自动化系2007年参数α、β对算法性能的影响α取较大值时，意味着在选择路径时，路径上的信息素非常重要；当α取较小值时，变成随机的贪婪算法。6.3基本蚁群优化算法6.3.2蚂蚁系统的参数设置和基本属性智能优化计算华东理工大学自动化系2007年参数α、β对算法性能的影响α＝0，蚂蚁之间无协同作用；α＝1，有协同作用6.3基本蚁群优化算法6.3.2蚂蚁系统的参数设置和基本属性α＝0α＝1智能优化计算华东理工大学自动化系2007年蚂蚁数m对算法的影响m≈n时，ant-cycle可以在最少迭代次数内找到最优解。6.3基本蚁群优化算法6.3.2蚂蚁系统的参数设置和基本属性m＝15m＝150m＝30智能优化计算华东理工大学自动化系2007年蚂蚁的初始分布两种情况实验：（1）所有蚂蚁初始时刻放在同一城市；（2）蚂蚁分布在不同城市中。第（2）中情况可获得较高性能。（3）在不同城市分布时，随机分布与统一分布的差别不大。6.3基本蚁群优化算法6.3.2蚂蚁系统的参数设置和基本属性智能优化计算华东理工大学自动化系2007年优点较强的鲁棒性；分布式计算；易于与其他方法结合。缺点搜索时间较长；容易出现停滞现象。6.4改进的蚁群优化算法6.4.1蚂蚁系统的优点与不足智能优化计算华东理工大学自动化系2007年最优解保留策略（AntSystemwithElitist,ASelite）每次迭代完成后，对全局最优解更进一步地进行利用；信息素更新策略σ为最优蚂蚁数，Lgb为全局最优解。6.4改进的蚁群优化算法6.4.2最优解保留策略蚂蚁系统否则是当前最优解的一部分如果边,0,)()1()1(**ijLQttgbijijijijij智能优化计算华东理工大学自动化系2007年最优解保留策略（AntSystemwithElitist,ASelite）该策略能够以更快的速度获得最好解，但是如果选择的精英过多则算法会由于较早收敛于局部次优解而导致搜索的过早停滞。6.4改进的蚁群优化算法6.4.2最优解保留策略蚂蚁系统智能优化计算华东理工大学自动化系2007年蚁群系统（AntColonySystem,ACS）的改进之处（1）在选择下一城市时，更多地利用了当前最好解；（2）只在全局最优解所属边上增加信息素；（3）每次蚂蚁从城市i转移到城市j时，边ij上的信息素将会适当减少，从而实现一种信息素的