第六章--群智能算法ppt课件.ppt

《第六章--群智能算法ppt课件.ppt》由会员分享，可在线阅读，更多相关《第六章--群智能算法ppt课件.ppt（84页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 n群智能（群智能（ Swarm Intelligence, SI ） 人们把群居昆虫的集体行为称作人们把群居昆虫的集体行为称作“群智能群智能”（“群群体智能体智能”、“群集智能群集智能”、“集群智能集群智能”等）等） n特点特点 个体的行为很简单，但当它们一起协同工作时，却个体的行为很简单，但当它们一起协同工作时，却能够能够突现突现出非常复杂（出非常复杂（智能智能）的行为特征。）的行为特征。 n描述描述 群智能群智能作为一种新兴的演化计算技术已成为研究焦作为一种新兴的演化计算技术已成为研究焦点，它与点，它与人工生命人工生命，特别是，特别是进化策略进化策略以及以及遗传算法遗传算法有着极为特殊的

2、关系。有着极为特殊的关系。n特性特性 指指无智能无智能的主体的主体通过合作通过合作表现出表现出智能行为智能行为的特性，的特性，在没有集中控制且不提供全局模型的前提下，为寻在没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题求解方案提供了基础。找复杂的分布式问题求解方案提供了基础。 n优点优点 灵活性：群体可以适应随时变化的环境；灵活性：群体可以适应随时变化的环境；稳健性：即使个体失败，整个群体仍能完成任务；稳健性：即使个体失败，整个群体仍能完成任务； 自我组织：活动既不受中央控制，也不受局部监管。自我组织：活动既不受中央控制，也不受局部监管。n典型算法典型算法 蚁群算法蚁群算法（蚂蚁

3、觅食）（蚂蚁觅食） 粒子群算法粒子群算法（鸟群捕食）（鸟群捕食） n蚁群的自组织行为蚁群的自组织行为 “双桥实验双桥实验” 通过遗留在来往路径通过遗留在来往路径 上的信息素上的信息素 （Pheromone）的挥）的挥 发性化学物质来进行发性化学物质来进行 通信和协调。通信和协调。 n蚁群的自组织行为蚁群的自组织行为 “双桥实验双桥实验” n提出蚁群系统提出蚁群系统 1992年，意大利学者年，意大利学者M. Dorigo在其博士论文中提出在其博士论文中提出 蚂蚁系统（蚂蚁系统（Ant System）。）。 近年来，近年来， M. Dorigo等人进一步将蚂蚁算法发展为一等人进一步将蚂蚁算法发展为

4、一种通用的优化技术种通用的优化技术蚁群优化蚁群优化（ant colony optimization, ACO）。）。 蚂蚁从蚂蚁从A点出发，随机选择路线点出发，随机选择路线ABD或或ACD。经过经过9个时间单位时：走个时间单位时：走ABD的蚂蚁到达终点，走的蚂蚁到达终点，走ACD的蚂蚁刚好走到的蚂蚁刚好走到C点。点。 蚁巢蚁巢食物食物 经过经过18个时间单位时：走个时间单位时：走ABD的蚂蚁到达终点的蚂蚁到达终点后得到食物又返回了起点后得到食物又返回了起点A，而走，而走ACD的蚂蚁刚好的蚂蚁刚好走到走到D点。点。蚁巢蚁巢食物食物 最后的极限是所有的蚂蚁只选择最后的极限是所有的蚂蚁只选择ABD路

5、线。路线。（正反馈正反馈过程）过程） 蚁巢蚁巢食物食物 n解决解决TSP问题问题 在算法的初始时刻，将在算法的初始时刻，将m只蚂蚁随机放到只蚂蚁随机放到n座城市座城市; 将每只蚂蚁将每只蚂蚁 k的禁忌表的禁忌表tabuk(s)的第一个元素的第一个元素tabuk(1)设置为它当前所在城市设置为它当前所在城市; 设各路径上的信息素设各路径上的信息素ij(0)=C（C为一较小的常数）为一较小的常数）; n解决解决TSP问题问题 每只蚂蚁根据路径上的每只蚂蚁根据路径上的信息素信息素和和启发式信息启发式信息（两城（两城市间距离）独立地选择下一座城市：市间距离）独立地选择下一座城市： 在时刻在时刻t，蚂蚁

6、，蚂蚁k从城市从城市i转移到城市转移到城市j的概率为的概率为 、分别表示信分别表示信 息素和启发式因子息素和启发式因子 的相对重要程度。的相对重要程度。( )( ) ( ), ( )( ) ( )( )0, ( )( )1,2, 1/kijijijkijkisisijs JikkkttjJittptjJiJintabud下一步允许的城市的集合下一步允许的城市的集合 n解决解决TSP问题问题 当所有蚂蚁完成一次周游后，各路径上的信息素将当所有蚂蚁完成一次周游后，各路径上的信息素将进行更新：进行更新： 其中，其中，（0 q0时，时，S以以下以以下概率概率来选择：来选择：otherwiseSqqif

7、tjiuiualloweduk , ,)(maxarg0)( , 0)( ,)()(),()(iJjiJjttjipkkiJsisisijijkkn局部信息素更新局部信息素更新 使已选的边对后来的蚂蚁具有较小的影响力，从而使已选的边对后来的蚂蚁具有较小的影响力，从而使蚂蚁对没有选中的边有更强的探索能力。使蚂蚁对没有选中的边有更强的探索能力。 当蚂蚁从城市当蚂蚁从城市i转移到城市转移到城市j后，边后，边ij上的信息素更新上的信息素更新为：为： 其中，其中，0为常数，为常数， (0,1)为可调参数。为可调参数。0)1 (ijijn全局信息素更新全局信息素更新 只针对全局最优解进行更新：只针对全局最

8、优解进行更新： 否则包含在最优路径中如果边 , 0 ,/1) 1 , 0( ,)()1 () 1(ijLttgbgbijgbijijijn最大最小蚂蚁系统（最大最小蚂蚁系统（max-min ant system, MMAS）的改进之处）的改进之处 （1）每次迭代后，只有最优解（最优蚂蚁）所属）每次迭代后，只有最优解（最优蚂蚁）所属路径上的信息被更新；路径上的信息被更新； （2）为了避免过早收敛，将各条路径可能的信息）为了避免过早收敛，将各条路径可能的信息素限制于素限制于min ,max； （3）初始时刻，各路径上信息素设置为）初始时刻，各路径上信息素设置为max ，在，在算法初始时刻，算法初始

9、时刻，取较小值时算法有更好的发现较取较小值时算法有更好的发现较好解的能力。好解的能力。 n信息素的全局更新信息素的全局更新 使所有蚂蚁完成一次迭代后，进行信息素更新：使所有蚂蚁完成一次迭代后，进行信息素更新： 否则包含在最优路径中如果边 , 0 ,/1) 1 , 0( ),()()1 () 1(ijLtttbestbestijbestijijijn基于排序的蚂蚁系统（基于排序的蚂蚁系统（rank-based version of ant system, ASrank） 每次迭代完成后，蚂蚁所经路径按从小到大的顺序每次迭代完成后，蚂蚁所经路径按从小到大的顺序排列，并对它们赋予不同权值，排列，并对

10、它们赋予不同权值，路径越短权值越大路径越短权值越大。全局最优解权值为全局最优解权值为w，第，第r个最优解的权值为个最优解的权值为max0,w-r。 n基于排序的蚂蚁系统（基于排序的蚂蚁系统（rank-based version of ant system, ASrank） 信息素更新：信息素更新：gbgbijrrijgbijrijwrijijLttLttwtrwtt/ 1)( ),(/ 1)() 1 , 0( ),()()()()1 () 1(11n典型应用列表典型应用列表 n由由James Kenney（社会心理学博士）和（社会心理学博士）和Russ Eberhart（电子工程学博士，（电子

11、工程学博士， http:/www.engr.iupui.edu/eberhart/ ）于）于1995年提年提出粒子群算法（出粒子群算法（Particle Swarm Optimization, PSO） n源于对鸟群捕食行为的研究，是基于迭代的方法源于对鸟群捕食行为的研究，是基于迭代的方法n简单易于实现，需要调整的参数相对较少简单易于实现，需要调整的参数相对较少n在函数优化、神经网络训练、工业系统优化和模糊在函数优化、神经网络训练、工业系统优化和模糊系统控制等领域得到了广泛的应用。系统控制等领域得到了广泛的应用。n鸟群：鸟群： 假设一个区域，所有的鸟都不知道食物的位置，但假设一个区域，所有的鸟

12、都不知道食物的位置，但是它们知道当前位置离食物还有多远。是它们知道当前位置离食物还有多远。nPSO算法算法 每个解看作一只鸟，称为每个解看作一只鸟，称为“粒子粒子(particle)”，所有，所有的粒子都有一个适应值，每个粒子都有一个速度决的粒子都有一个适应值，每个粒子都有一个速度决定它们的飞翔方向和距离，粒子们追随当前最优粒定它们的飞翔方向和距离，粒子们追随当前最优粒子在解空间中搜索。子在解空间中搜索。nPSO算法算法 初始化为一群随机粒子，通过迭代找到最优。初始化为一群随机粒子，通过迭代找到最优。 每次迭代中，粒子通过跟踪每次迭代中，粒子通过跟踪“个体极值（个体极值（pbest）”和和“全

13、局极值全局极值(gbest)”来来 更新自己的位置。更新自己的位置。n粒子速度和位置的更新粒子速度和位置的更新 假设在假设在D维搜索空间中，有维搜索空间中，有m个粒子；个粒子； 其中第其中第i个粒子的位置为矢量个粒子的位置为矢量 其飞翔速度也是一个矢量，记为其飞翔速度也是一个矢量，记为 第第i个粒子搜索到的最优位置为个粒子搜索到的最优位置为 整个粒子群搜索到的最优位置为整个粒子群搜索到的最优位置为 第第i个粒子的位置和速度更新为：个粒子的位置和速度更新为：Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid, 2 , 1 ;, 2 , 1 )

14、()()()(11211),(21iDiiipppp),(21gbestDgbestgbestgbestpppp),(21iDiiixxxx),(21iDiiivvvvn粒子速度和位置的更新粒子速度和位置的更新 其中，其中，w称为惯性权重，称为惯性权重， c1和和c2为两个正常数，称为两个正常数，称 为加速因子。为加速因子。 将将 vidk 限制在一个最大速限制在一个最大速 度度 vmax 内。内。Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid, 2 , 1 ;, 2 , 1 )()()()(11211xkvkppgbestxk+1vk

15、+1kkk+1k+1n粒子速度和位置的更新粒子速度和位置的更新 Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid, 2 , 1 ;, 2 , 1 )()()()(11211“惯性部分惯性部分”，对自身运动状对自身运动状态的信任态的信任“认知部分认知部分”，对微粒，对微粒本身的思考，即来源本身的思考，即来源于自己经验的部分于自己经验的部分“社会部分社会部分”，微粒间的，微粒间的信息共享，来源于群体中信息共享，来源于群体中的其它优秀微粒的经验的其它优秀微粒的经验n迭代过程迭代过程 n算法流程算法流程 StartInitialize parti

16、cles with random position and velocity vectors.For each particles position (xi) evaluate fitnessIf fitness(xi) better than fitness(p) then p= xiLoop until all particles exhaustSet best of ps as gBestUpdate particles velocity and positionLoop until max iterStop: giving gBest, optimal solution.n惯性权重惯性

17、权重w 使粒子保持运动惯性，使其有扩展搜索空间的趋势，使粒子保持运动惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。有能力探索新的区域。 表示微粒对当前自身运动状态的信任，依据自身的表示微粒对当前自身运动状态的信任，依据自身的速度进行惯性运动。速度进行惯性运动。 较大的较大的w有利于跳出局部极值，而较小的有利于跳出局部极值，而较小的w有利于有利于算法收敛。算法收敛。Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid, 2 , 1 ;, 2 , 1 )()()()(11211n加速常数加速常数c1和和c2 代表将微粒推向代表将微粒推向pb

18、est和和gbest位置的统计加速项的位置的统计加速项的权重。权重。 表示粒子的动作来源于自己经验的部分和其它粒子表示粒子的动作来源于自己经验的部分和其它粒子 经验的部分。经验的部分。 低的值允许粒子在被拉回之前可以在目标区域外徘低的值允许粒子在被拉回之前可以在目标区域外徘 徊，而高的值则导致粒子突然冲向或越过目标区徊，而高的值则导致粒子突然冲向或越过目标区 域。域。 Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid, 2 , 1 ;, 2 , 1 )()()()(11211n加速常数加速常数c1和和c2 将将c1和和c2统一为一个控制参

19、数，统一为一个控制参数，= c1+c2 如果如果很小，微粒群运动轨迹将非常缓慢；很小，微粒群运动轨迹将非常缓慢； 如果如果很大，则微粒位置变化非常快；很大，则微粒位置变化非常快； 实验表明，当实验表明，当=4.1（通常（通常c1=2.0，c2=2.0）时，具）时，具有很好的收敛效果。有很好的收敛效果。n粒子数粒子数 一般取一般取2040，对较难或特定类别的问题可以取，对较难或特定类别的问题可以取 100200。n最大速度最大速度vmax 决定粒子在一个循环中最大的移动距离，通常设定决定粒子在一个循环中最大的移动距离，通常设定为粒子的范围宽度。为粒子的范围宽度。n终止条件终止条件 最大循环数以及

20、最小错误要求。最大循环数以及最小错误要求。n共性共性 （1）都属于仿生算法；）都属于仿生算法； （2）都属于全局优化方法；）都属于全局优化方法； （3）都属于随机搜索算法；）都属于随机搜索算法； （4）都隐含并行性；）都隐含并行性； （5）根据个体的适配信息进行搜索，因此不受函）根据个体的适配信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等；数约束条件的限制，如连续性、可导性等； （6）对高维复杂问题，往往会遇到早熟收敛和收）对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证收敛到最优点。敛性能差的缺点，都无法保证收敛到最优点。 n差异差异 （1）PSO有记忆，所有粒

21、子都保存较优解的知识，有记忆，所有粒子都保存较优解的知识，而而GA，以前的知识随着种群的改变被改变；，以前的知识随着种群的改变被改变； （2）PSO中的粒子是一种单向共享信息机制。而中的粒子是一种单向共享信息机制。而GA中的染色体之间相互共享信息，使得整个种群中的染色体之间相互共享信息，使得整个种群都向最优区域移动；都向最优区域移动； （3）GA需要编码和遗传操作，而需要编码和遗传操作，而PSO没有交叉和没有交叉和变异操作，粒子只是通过内部速度进行更新，因此变异操作，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易。原理更简单、参数更少、实现更容易。n用途用途 基本基本PSO

22、是用来解决连续问题优化的，离散二进制是用来解决连续问题优化的，离散二进制PSO用来解决组合优化问题。用来解决组合优化问题。n运动方程不同运动方程不同 粒子的位置只有粒子的位置只有(0,1)两种状态。速度值越大，则粒两种状态。速度值越大，则粒子位置取子位置取1的可能性越大，反之越小。的可能性越大，反之越小。维分量。的第是随机矢量dvvSxelsexthenvS ifxprandcxprandcwvvkikidkidkidkidkidkidkidkidgbestkididkidkid11111111211 1 , 0 ,)exp(11)(0 ; 1 )( )()()()(n思路思路 在考虑实际优化

23、问题时在考虑实际优化问题时，往往希望先采用全局搜索往往希望先采用全局搜索，使使搜索空间快速收敛于某一区域搜索空间快速收敛于某一区域，然后采用局部精然后采用局部精细搜索以获得高精度的解细搜索以获得高精度的解。 研究发现，较大的研究发现，较大的 w 值有利于跳出局部极小点，而值有利于跳出局部极小点，而 较小的较小的 w 值有利于算法收敛，因此提出了自适应调值有利于算法收敛，因此提出了自适应调 整的策略，即随着迭代的进行，线性地减小整的策略，即随着迭代的进行，线性地减小 w 的的 值。值。n变化的惯性权重变化的惯性权重 wmax、wmin分别是分别是w的最大值和最小值；的最大值和最小值；iter、i

24、termax分别是当前迭代次数和最大迭代次数。分别是当前迭代次数和最大迭代次数。iteriterwwwwmaxminmaxmaxn提出提出 1999年年Clerc对算法的研究证明，采用收敛因子能对算法的研究证明，采用收敛因子能 够确保算法的收敛够确保算法的收敛。n收敛因子模型收敛因子模型 通常将通常将设为设为4.1，经计算，经计算k为为0.729。4,422)()(212211cckxprandcxprandcvkvkidgbestkididkidkid其中n主要研究方向主要研究方向 主要集中于对算法结构和性能的改善方面，包括：主要集中于对算法结构和性能的改善方面，包括：参数设置、粒子多样性、

25、种群结构和算法的融合。参数设置、粒子多样性、种群结构和算法的融合。n发展方向发展方向 目前大部分成果都是通过大量试验获得的，缺少对目前大部分成果都是通过大量试验获得的，缺少对算法机理的研究，对算法机理的研究，对PSO中的参数分析没有实质性中的参数分析没有实质性的认识，还处于试验分析阶段。的认识，还处于试验分析阶段。n交换子和交换序交换子和交换序 设设n个节点的个节点的TSP问题的解序列为问题的解序列为s=(ai)，i=1n。定义。定义交换子交换子SO(i1,i2)为交换解为交换解S中的点中的点ai1和和ai2，则，则S=S+SO(i1,i2)为解为解S经算子经算子SO(i1,i2)操作后的操作

26、后的新解。新解。 一个或多个交换子的有序队列就是一个或多个交换子的有序队列就是交换序交换序，记，记作作SS，SS=(SO1,SO2,SON)。其中，。其中，SO1,SON等等是交换子，之间的顺序是有意义的是交换子，之间的顺序是有意义的, 意味着所有的意味着所有的交换子依次作用于某解上。交换子依次作用于某解上。n符号的定义符号的定义 若干个交换序可以合并成一个新的交换序，定若干个交换序可以合并成一个新的交换序，定义义 为两个交换序的合并算子。为两个交换序的合并算子。 设两个交换序设两个交换序SS1和和SS2按先后顺序作用于解按先后顺序作用于解S上，得到新解上，得到新解S。假设另外有一个交换序。假

27、设另外有一个交换序SS作用作用于同一解于同一解S上，能够得到形同的解上，能够得到形同的解S，可定义，可定义21SSSSSSn符号的定义符号的定义 和和 属于同一属于同一等价集等价集，在交换序等，在交换序等价集中，拥有最少交换子的交换序称为该等价集的价集中，拥有最少交换子的交换序称为该等价集的基本交换序基本交换序。SS21SSSS n解决解决TSP问题的速度算式定义问题的速度算式定义 、为为0,1上的随机数。上的随机数。 vid表示交换序，表示交换序，xid表示路径序列（解）。表示路径序列（解）。()()ididididgdididididvvpxpxxxvn算法流程算法流程 1. 初始化粒子群

28、，给每个粒子一个初始解初始化粒子群，给每个粒子一个初始解(xid)和随和随机的交换序机的交换序(vid); 2. 如果满足结束条件，转步骤如果满足结束条件，转步骤5; 3. 根据粒子当前位置根据粒子当前位置xid计算下一新解计算下一新解xid; 4. 如果整个群体找到一个更好的解，更新如果整个群体找到一个更好的解，更新Pgd，转，转步骤步骤2; 5. 显示结果。显示结果。n算法流程算法流程 3. 根据粒子当前位置根据粒子当前位置xid计算下一新解计算下一新解xid: 1）计算）计算A=pid-xid，A是一个基本交换序，表示是一个基本交换序，表示A作用于作用于xid得到得到pid； 2）计算）

29、计算B=pgd-xid，B也是一个基本交换序；也是一个基本交换序； 3）更新速度）更新速度 ，并将，并将其转换为一个基本交换序；其转换为一个基本交换序； 4）更新解）更新解 ； 5）如果找到一个更好得解，更新）如果找到一个更好得解，更新pid。)()(idgdididididxpxpvvidididvxxn运行结果运行结果 =0.25 =0.25 迭代次数迭代次数=200 粒子数粒子数=8010城市城市TSP问题（问题（d*=2.691）0.4 0.4439; 0.2439 0.1463; 0.1707 0.2293; 0.2293 0.761;0.5171 0.9414;0.8732 0.6

30、536; 0.6878 0.5219; 0.8488 0.3609;0.6683 0.2536; 0.6195 0.2634n运行结果运行结果 n运行结果运行结果 n运行结果运行结果 n运行结果运行结果 n运行结果运行结果 n运行结果运行结果 n运行结果运行结果 n神经网络的训练神经网络的训练 主要包含主要包含3个方面：连接权重、网络拓扑结构及传个方面：连接权重、网络拓扑结构及传 递函数、学习算法递函数、学习算法。 每个粒子包含神经网络的所有参数，通过迭代来优每个粒子包含神经网络的所有参数，通过迭代来优 化这些参数，从而达到训练的目的化这些参数，从而达到训练的目的。 与与BP算法相比，使用算法

31、相比，使用PSO训练神经网络的优点在于训练神经网络的优点在于 不使用梯度信息，可使用一些不可微的传递函数。不使用梯度信息，可使用一些不可微的传递函数。 多数情况下其训练结果优于多数情况下其训练结果优于BP算法，而且训练速算法，而且训练速 度非常快。度非常快。n参数优化参数优化 模糊控制器的设计模糊控制器的设计 机器人路径规划机器人路径规划 信号处理和模式识别等问题信号处理和模式识别等问题n组合优化组合优化 背包问题背包问题 目标分配问题目标分配问题 作业调度问题作业调度问题n其他应用其他应用 多目标优化多目标优化 自动目标检测自动目标检测 生物信号识别生物信号识别 决策调度决策调度 系统辨识系

32、统辨识 游戏训练游戏训练n共同特点共同特点 基于概率计算的随机搜索进化算法，在结构、研究基于概率计算的随机搜索进化算法，在结构、研究内容、方法以及步骤上有较大的相似性；内容、方法以及步骤上有较大的相似性；n存在的问题存在的问题 （1）数学理论基础相对薄弱；）数学理论基础相对薄弱； （2）参数设置没有确切的理论依据，对具体问题）参数设置没有确切的理论依据，对具体问题和应用环境的依赖性大；和应用环境的依赖性大；n存在的问题存在的问题 （3）比较性研究不足，缺乏用于性能评估的标准）比较性研究不足，缺乏用于性能评估的标准测试集；测试集； （4）不具备绝对的可信性，存在应用风险；）不具备绝对的可信性，存在应用风险；n进一步的工作进一步的工作 （1）进一步研究真实群居动物的行为特征；）进一步研究真实群居动物的行为特征； （2）进一步研究算法的收敛性；）进一步研究算法的收敛性； n存在的问题存在的问题 （3）进一步提高收敛速度，从而解决大规模优化）进一步提高收敛速度，从而解决大规模优化问题；问题； （4）进一步研究各种参数设置问题；）进一步研究各种参数设置问题； （5）研究群智能的并行算法；）研究群智能的并行算法； （6）进一步研究各算法的适用范围；）进一步研究各算法的适用范围； （7）研究与其它算法的混合技术。）研究与其它算法的混合技术。