优化算法及其在软测量技术中的应用.pptx

《优化算法及其在软测量技术中的应用.pptx》由会员分享，可在线阅读，更多相关《优化算法及其在软测量技术中的应用.pptx（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、本章主要内容概述遗传算法微粒群算法蚁群算法第1页/共73页6.1 概述进化计算进化计算(Evolutionary Computation)是是通过模拟自然界中生物进化机制进行搜索的一通过模拟自然界中生物进化机制进行搜索的一种算法。种算法。遗传算法（遗传算法（Genetic Algorithms）进化策略（进化策略（Evolution Strategies）进化规划（进化规划（Evolution Programming）遗传算法遗传算法是模仿生物遗传学和自然选择机理，是模仿生物遗传学和自然选择机理，通过人工方式所构造的一类优化搜索算法，是通过人工方式所构造的一类优化搜索算法，是对生物进化过程进行

2、的一种数学仿真，是进化对生物进化过程进行的一种数学仿真，是进化计算的最重要的形式。计算的最重要的形式。第2页/共73页6.1 概述群智能群智能(Swarm Intelligence)这个概念来自对蜜蜂、这个概念来自对蜜蜂、蚂蚁、大雁等群居生物群体行为的观察和研究。任何蚂蚁、大雁等群居生物群体行为的观察和研究。任何启发于群居性昆虫群体和其它动物群体的集体行为而启发于群居性昆虫群体和其它动物群体的集体行为而设计的算法和分布式问题解决装置都称为群智能。设计的算法和分布式问题解决装置都称为群智能。群智能群智能是一种在自然界生物群体所表现出的智能现象是一种在自然界生物群体所表现出的智能现象启发下提出的人

3、工智能实现模式，是对简单生物群体启发下提出的人工智能实现模式，是对简单生物群体的智能涌现现象的具体模式研究，即简单智能的主体的智能涌现现象的具体模式研究，即简单智能的主体通过合作表现出复杂智能行为的特性。该智能模式需通过合作表现出复杂智能行为的特性。该智能模式需要以相当数目的智能个体来实现对问题的求解功能。要以相当数目的智能个体来实现对问题的求解功能。群智能群智能在没有集中控制并且不提供全局模型的前提下，在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了基础为寻找复杂的分布式问题的解决方案提供了基础。第3页/共73页6.1 概述群智能的特点：群智能的特点：分布式：

4、分布式：能够适应当前网络环境下的工作能够适应当前网络环境下的工作状态状态 鲁棒性：鲁棒性：没有中心的控制与数据，个体的没有中心的控制与数据，个体的故障不影响整个问题的求解故障不影响整个问题的求解 扩充性：扩充性：个体的增加，系统的通信开销增个体的增加，系统的通信开销增加小加小 简单性：简单性：个体简单，实现也比较简单个体简单，实现也比较简单第4页/共73页6.1 概述群智能的典型实现模式：群智能的典型实现模式：微粒群算法（微粒群算法（Particle swarm optimization,PSO）：）：模拟鸟群运动模式模拟鸟群运动模式 蚁群算法（蚁群算法（Ant colony algorith

5、m）：）：模拟生物蚁群运动行为模拟生物蚁群运动行为第5页/共73页6.2 遗传算法遗传算法的基本机理遗传算法的一般框架遗传算法 的模式理论Matlab遗传算法工具箱第6页/共73页6.2.1 遗传算法的基本机理遗传与进化的系统观点：1)1)生物的所有遗传信息的都包含在其染色体中，染色生物的所有遗传信息的都包含在其染色体中，染色体决定了生物的性状体决定了生物的性状2)2)染色体是由基因及其有规律的排列所构成的，遗传染色体是由基因及其有规律的排列所构成的，遗传进化过程发生在染色体上进化过程发生在染色体上3)3)生物的繁殖过程是由其基因的复制过程来完成的生物的繁殖过程是由其基因的复制过程来完成的4)

6、4)通过同源染色体之间的交叉或染色体的变异会产生通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状新的物种，使生物呈现新的性状5)5)对环境适应性好的基因或染色体经常比适应性差的对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代基因或染色体有更多的机会遗传到下一代第7页/共73页6.2.1 遗传算法的基本机理遗传算法的基本机理 模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传空模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传空间，把可能的解编码成一个向量间，把可能的解编码成一个向量染色体，向量的每个元素染色体，向量的每个元素称为基因。利用

7、选择、交叉、变异等遗传算子产生新的染色体，称为基因。利用选择、交叉、变异等遗传算子产生新的染色体，通过不断计算各染色体的适应度值，选择最好的染色体，获得通过不断计算各染色体的适应度值，选择最好的染色体，获得最优解。最优解。第8页/共73页6.2.1 遗传算法的基本机理遗传学和遗传算法中基本术语对照表：自然界自然界染色体染色体(chromosome)基因基因(gene)等位基因等位基因(allele)染色体位置染色体位置(locus)基因型基因型(genotype)表型表型(phenotype)遗传算法遗传算法字符串字符串字符字符,特征特征特征值特征值字符串位置字符串位置结构结构参数集参数集,译

8、码结构译码结构第9页/共73页6.2.2 遗传算法的一般框架遗传算法的构成要素：染色体编码方法染色体编码方法 适应度函数适应度函数 遗传算子（选择、交叉、变异）遗传算子（选择、交叉、变异）遗传参数设置遗传参数设置第10页/共73页6.2.2 遗传算法的一般框架编码与解码：将问题结构变换为位串形式表示的过程叫编将问题结构变换为位串形式表示的过程叫编码，相反把位串形式表示变换为原问题结构的码，相反把位串形式表示变换为原问题结构的过程叫解码过程叫解码 GA常用的编码方法：二进制编码，实数编常用的编码方法：二进制编码，实数编码，格雷码，符号编码，多参数编码等码，格雷码，符号编码，多参数编码等 第11页

9、/共73页6.2.2 遗传算法的一般框架适应度函数：一般情况下，适应度函数由目标函数变换而一般情况下，适应度函数由目标函数变换而成，成，适应度函数要求为非负函数适应度函数要求为非负函数 若目标函数为最大化问题，则若目标函数为最大化问题，则 若目标函数为最小化问题，则若目标函数为最小化问题，则第12页/共73页6.2.2 遗传算法的一般框架遗传算子：选择（选择（Selection）：）：-从旧的种群中选择适应度高的染色体，放入匹从旧的种群中选择适应度高的染色体，放入匹配集（缓冲区），为以后染色体交叉、变异，产生新配集（缓冲区），为以后染色体交叉、变异，产生新的染色体作准备。的染色体作准备。-选择

10、方法：适应度比例法（轮盘赌法），即按选择方法：适应度比例法（轮盘赌法），即按各染色体适应度大小比例来决定其被选择数目的多少。各染色体适应度大小比例来决定其被选择数目的多少。某染色体被选的概率：某染色体被选的概率：第13页/共73页6.2.2 遗传算法的一般框架遗传算子：交叉（交叉（Crossover）：）：-随机选择二个染色体随机选择二个染色体(双亲染色体双亲染色体)，随机指定一，随机指定一点或多点，将两者部分码值进行交换，可得二个新的点或多点，将两者部分码值进行交换，可得二个新的染色体染色体(子辈染色体子辈染色体)。新的子辈染色体:A 11010001 B 01011110第14页/共73页

11、6.2.2 遗传算法的一般框架遗传算子：变异（变异（Mutation）：）：-模拟生物在自然界环境变化，引起基因的突变。模拟生物在自然界环境变化，引起基因的突变。-在染色体二进制编码中，在染色体二进制编码中，1变成变成0，或，或0变成变成1 -变异产生染色体的多样性，避免进化中早期成变异产生染色体的多样性，避免进化中早期成熟，陷入局部极值点，变异的概率很低。熟，陷入局部极值点，变异的概率很低。A 1 0 1 0 0 1 1 0A 1 0 1 1 0 1 1 0第15页/共73页6.2.2 遗传算法的一般框架遗传参数设置：N：群体大小，即群体中所含个体的数量，一般取群体大小，即群体中所含个体的数

12、量，一般取20100 T：GA的终止进化代数，一般取的终止进化代数，一般取100500 Pc：交叉概率，一般取交叉概率，一般取0.40.99 Pm：变异概率，一般取变异概率，一般取0.00010.1 第16页/共73页6.2.2 遗传算法的一般框架遗传算法进行问题求解的过程：初始化群体初始化群体 计算群体中每个个体的适应度值计算群体中每个个体的适应度值 按由个体适应度值所决定的某个规则选择进入下按由个体适应度值所决定的某个规则选择进入下一代的个体一代的个体 按概率按概率Pc进行交叉操作进行交叉操作 按概率按概率Pm进行变异操作进行变异操作 若没有满足某种停止条件，就转到第若没有满足某种停止条件

13、，就转到第2步，否则进步，否则进入下一步入下一步 输出群体中适应度值最优的染色体作为问题的满输出群体中适应度值最优的染色体作为问题的满意解或最优解意解或最优解第17页/共73页第18页/共73页6.2.2 遗传算法的一般框架遗传算法应用举例：例4-1 利用遗传算法求解区间0,31上的二次函数y=x2的最大值。y=x2 31 XY分析：原问题可转化为在区间原问题可转化为在区间0,31中中搜索能使搜索能使y取最大值的点取最大值的点a的问题。的问题。那么，那么，0,31 中的点中的点x就是个体，函就是个体，函数值数值f(x)恰好就可以作为恰好就可以作为x的适应度，的适应度，区间区间0,31就是一个解

14、空间就是一个解空间。这。这样样,只要能给出个体只要能给出个体x的适当染色体的适当染色体编码，该问题就可以用遗传算法来编码，该问题就可以用遗传算法来解决。解决。第19页/共73页6.2.2 遗传算法的一般框架遗传算法应用举例：解：(1)设定种群规模，编码染色体，产生初始种群。将种群规模设定为4，用5位二进制数编码染色体，取下列个体组成初始种群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)(2)定义适应度函数：f(x)=x2 (3)计算各代种群中的各个体的适应度,并对其染色 体 进 行 遗 传 操 作，直 到 适 应 度 最 高 的 个 体

15、(即31（11111）)出现为止。第20页/共73页6.2.2 遗传算法的一般框架遗传算法应用举例：首先计算种群S1中各个体的适应度f(si)：f(s1)=f(13)=132=169，f(s2)=f(24)=242=576 f(s3)=f(8)=82=64，f(s4)=f(19)=192=361 再计算种群S1中各个体的选择概率：P(s1)=P(13)=0.14 P(s2)=P(24)=0.49 P(s3)=P(8)=0.06 P(s4)=P(19)=0.31s40.31s20.49s10.14s30.06第21页/共73页6.2.2 遗传算法的一般框架遗传算法应用举例：在算法中赌轮选择法可用

16、下面的子过程来模拟：在0,1区间内产生一个均匀分布的随机数r。若rq1，则染色体x1被选中。若qk-1rqk(2kN)，则染色体xk被选中。其中的qi称为染色体xi(i=1,2,n)的积累概率，其计算公式为：第22页/共73页6.2.2 遗传算法的一般框架遗传算法应用举例：设从区间0,1中产生4个随机数如下：r1=0.450126,r2=0.110347 r3=0.572496,r4=0.98503 染色体染色体 适应度适应度选择概率选择概率积累概率积累概率选中次数选中次数s1=01101 169 0.14 0.14 1s2=11000 576 0.49 0.63 2s3=01000 64 0

17、.06 0.69 0s4=10011 361 0.31 1.00 1第23页/共73页6.2.2 遗传算法的一般框架遗传算法应用举例：于是，经复制得群体：s1=11000（24）,s2=01101（13）s3=11000（24）,s4=10011（19）设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1与s2配对，s3与s4配对。分别交换后两位基因，得新染色体：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）第24页/共73页6.2.2 遗传算法的一般框架遗传算法应用举例：设变异率pm=0.001，这样，群体S1中共有 540

18、.001=0.02 位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。于是，得到第二代种群S2：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）第25页/共73页6.2.2 遗传算法的一般框架遗传算法应用举例：第二代种群S2中各染色体的情况：染色体染色体 适应度适应度选择概率选择概率积累概率积累概率 估计的估计的选中次数选中次数s1=11001 625 0.36 0.36 1s2=01100 144 0.08 0.44 0s3=11011 729 0.41 0.85 2s4=10000 256 0.15 1.00 1第26页/

19、共73页6.2.2 遗传算法的一般框架遗传算法应用举例：假设这一轮选择复制操作中，种群S2中的4个染色体都被选中，则得到群体：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）做交叉运算，让s1与s2，s3与s4 分别交换后三位基因：s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19）这一轮仍然不会发生变异。第27页/共73页6.2.2 遗传算法的一般框架遗传算法应用举例：第三代种群S3中各染色体的情况：染色体染色体 适应度适应度选择概率选择概率积累概率积累概率 估计的估计的选中次数选中次数s1=1

20、1100 784 0.44 0.44 2s2=01001 81 0.04 0.48 0s3=11000 576 0.32 0.80 1s4=10011 361 0.20 1.00 1第28页/共73页6.2.2 遗传算法的一般框架遗传算法应用举例：设这一轮的选择复制结果为：s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19）做交叉运算，让s1与s2，s3与s4 分别交换后三位基因：s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）这一轮仍然不会发生变异。第29页/共73页6.2.2 遗传算法的一般框

21、架遗传算法应用举例：第四代种群S4中已经出现了适应度最高的染色体s1=11111。于 是，遗 传 操 作 终 止，将 染 色 体“11111”作 为 最 终 结 果 输 出。然 后，将 染 色 体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。第30页/共73页YYy=x2 8 13 19 24 X第一代种群及其适应度第一代种群及其适应度y=x2 12 16 25 27 XY第二代种群及其适应度第二代种群及其适应度y=x2 9 19 24 28 XY第三代种群及其适应度第三代种群及其适应度y=x2 16 24 28

22、31 X第四代种群及其适应度第四代种群及其适应度第31页/共73页6.2.2 遗传算法的一般框架遗传算法的特点：GA是对参数集合的编码而非针对参数本身进行优是对参数集合的编码而非针对参数本身进行优化化 GA是从问题解的编码组开始而非单个解开始搜索是从问题解的编码组开始而非单个解开始搜索 GA利用目标函数的适应度这一信息而非利用导数利用目标函数的适应度这一信息而非利用导数或其他辅助信息来指导搜索或其他辅助信息来指导搜索 GA利用选择、交叉、变异等算子而不是确定性规利用选择、交叉、变异等算子而不是确定性规则进行随机操作则进行随机操作 第32页/共73页6.2.2 遗传算法的一般框架遗传算法的局限性

23、：遗传算法在解决某些问题时速度较慢遗传算法在解决某些问题时速度较慢 遗传算法对编码方案的依赖性较强遗传算法对编码方案的依赖性较强 算法的鲁棒性不够好算法的鲁棒性不够好 第33页/共73页6.2.3 遗传算法的模式理论遗传算法的理论基础是遗传算法的二进制表达式及模式的含义。模式是能对染色体之间的相似性进行解释的模板。设GA的个体 ，记集合 则称 为一个模式，其中是通配符。即模式(schema)是含有通配符(*)的一类字符串的通式表达。每个“*”可以取“1”或者“0”。第34页/共73页6.2.3 遗传算法的模式理论模式举例：-模式*10101110*10101110与以下两个字符串匹配：0101

24、01110 110101110 010101110 110101110 -模式*1010*1010110110与以下四个字符串匹配：010100110 010101110 010100110 010101110 110100110 110101110 110100110 110101110第35页/共73页6.2.3 遗传算法的模式理论一个模式s的阶(order)是出现在模式中的“0”和“1”的数目，记为o(s)。-如：模式“0*”的阶为1，模式“10*1*”的阶为3一个模式s的长度(Length)是出现在模式中第一个确定位置和最后一个确定位置之间的距离，记为 。-如：模式“01*”的长度为1

25、，模式“0*1”的长度为3。第36页/共73页6.2.3 遗传算法的模式理论复制对模式的影响：假定在给定的时间（代）t，一个特定的模式s在群体P(t)中包含有m个代表串，记为m=m(s,t)。每个串根据适应值的大小获得不同的复制概率。串i的复制概率为：则在群体P(t+1)中，模式s的代表串的数量的期望值为 其中，表示模式s在t时刻的所有代表串的适应值的均值，称为模式s的适应值。第37页/共73页6.2.3 遗传算法的模式理论复制对模式的影响：若记P(t)中所有个体的适应值的平均值为：则有：上式表明，模式s的代表串的数目随时间增长的幅度正比于模式s的适应值与群体平均适应值的比值。即：适应值高于群

26、体平均值的模式在下一代的代表串数目将会增加，而适应值低于群体平均值的模式在下一代的代表串数目将会减少。第38页/共73页6.2.3 遗传算法的模式理论复制对模式的影响：假设模式的适应值为 ，其中c是一个常数，则有：上式表明，在平均适应值之上（之下）的模式，将会按指数增长（衰减）的方式被复制。复制的结果并没有生成新的模式。因而，为了探索搜索空间中的未搜索部分，需要利用交叉和变异操作。第39页/共73页6.2.3 遗传算法的模式理论交叉对模式的影响：交叉会改变模式的一部分，模式的长度越长，被破坏的概率越大。假定模式s在交叉后不被破坏的概率为ps，则：若交叉概率为pc，则s不被破坏的概率为：第40页

27、/共73页6.2.3 遗传算法的模式理论交叉对模式的影响：若综合考虑复制和交叉的影响，特定模式在下一代中的数量可用下式来估计：可见，对于那些高于平均适应度且具有短短定义长度的模式将更多地出现在下一代中。第41页/共73页6.2.3 遗传算法的模式理论变异对模式的影响：变异算子以概率pm随机地改变个体某一位的值，只有当o(s)个确定位的值不被破坏时，模式s才不被破坏。模式s在变异后不被破坏的概率：由于Pmgatool 图形界面如图：第46页/共73页6.2.4 Matlab遗传算法工具箱GADS工具箱可通过命令行或m文件调用，其核心函数为：x,fval,reason,output=ga(fitn

28、essfcn,nvars,A,b,Aeq,beq,LB,UB,nonlcon,options)函数参数说明如下：输输入入参参数数fitnessfcn：适应度函数：适应度函数f(x)nvars：变量数量：变量数量A,b：线性不等式约束条件下：线性不等式约束条件下A1xb1的参数的参数Aeq,beq：线性等式约束条件：线性等式约束条件A2x=b2的参数的参数LB：x的取值下限的取值下限v1UB：x的取值上限的取值上限v2nonlcon：非线性约束条件：非线性约束条件c1(x)0和和c2(x)=0options:：与算法性能相关的参数：与算法性能相关的参数输输出出参参数数x：最优值：最优值fval：

29、最优值下的适应度函数值：最优值下的适应度函数值reason：算法停止原因：算法停止原因output：每次迭代信息及其他算法信息：每次迭代信息及其他算法信息第47页/共73页6.2.4 Matlab遗传算法工具箱影响遗传算法性能的参数由结构体options给定，可使用如下命令查看options的默认值：options=gaoptimset GADS中默认的options参数值为：PopulationType:doubleVector种群数据类型种群数据类型 InitialPopulation:初始种群初始种群PopInitRange:2*1 double初始种群中个体取值范围初始种群中个体取值范

30、围InitialScores:初始适应度初始适应度PopulationSize:20种群规模种群规模InitialPenalty:10初始惩罚参数初始惩罚参数EliteCount:2在每代中保留下来的个体数量在每代中保留下来的个体数量PenaltyFactor:100惩罚更新参数惩罚更新参数CrossoverFraction:0.8000交叉概率交叉概率PlotInterval:1绘制函数调用间隔绘制函数调用间隔Migrationdirection:forword变异方向变异方向CreationFcn:gacreationuniform初始种群函数的句柄初始种群函数的句柄MigrationIn

31、terval:20子群中发生变异的代数间隔子群中发生变异的代数间隔FitnessScalingFcn:fitscalingrank调节适应度的函数句柄调节适应度的函数句柄MigrationFraction:0.2000变异概率变异概率SelectionFcn:selectionstochunif选择函数句柄选择函数句柄Generations:100最大迭代次数最大迭代次数CrossoverFcn:crossoverscattered交叉函数句柄交叉函数句柄TimeLimit:Inf最大运行时间最大运行时间MutationFcn:mutationgaussian变异函数句柄变异函数句柄Fitne

32、ssLimit:-Inf当适应度函数达该值时算法停止当适应度函数达该值时算法停止HybridFcn:GA终止后继续优化的函数句柄终止后继续优化的函数句柄StallGenLimit:50算法停止的代数算法停止的代数Display:final显示方式显示方式StallTimeLimit:20算法停止的时间算法停止的时间PlotFcns:绘制函数的句柄绘制函数的句柄TolFun:1.0000e-006当适应度函数在当适应度函数在StallGenLimit设定设定的代数内变化小于该值算法停止的代数内变化小于该值算法停止OutputFcns:在每代中调用的函数在每代中调用的函数TolCon:1.0000

33、e-006非线性约束的可行性非线性约束的可行性Vectorized:off适应度函数是否矢量化适应度函数是否矢量化第48页/共73页6.2.4 Matlab遗传算法工具箱如果需要修改上述options中的参数值，例如修改PopulationSize至100，可采用如下命令：options=gaoptimset(PopulationSize,100)也可通过上述命令同时修改多个参数在实际应用中，通常需要根据应用需求编写适当的适应度函数，在编写函数的时候需注意GADS是求最小值的，编写好的适应度函数需存成m文件放在同一目录下。第49页/共73页6.2.4 Matlab遗传算法工具箱例：当x1-3.

34、0,12.1，x2 4.1,5.8时，求函数 f(x1,x2)=21.5+x1*sin(4*pi*x1)+x2*sin(20*pi*x2)的极大值。解：首先编写适应度函数如下：function score=my_func1(x)score=-21.5-x(1)*sin(4*pi*x(1)-x(2)*sin(20*pi*x(2);然后选用合适的参数调用ga函数：opt1=gaoptimset;opt1.PopInitRange=-3.0 4.1;12.1 5.8;opt1.PopulationSize=1000;opt1.MutationFcn=mutationuniform;x,fval=ga

35、(my_func1,2,opt1)第50页/共73页6.2.4 Matlab遗传算法工具箱运行结果如下：Optimization terminated:stall generations limit exceeded.x=11.6288 5.7244 fval=-38.8354 需要注意到是：由于遗传算法是一种随机搜索算法，每次运行得到的结果很可能不同，这主要是Matlab在每次迭代时，采用rand和randn这两个随机数生成函数来随机选择样本，每次Matlab调用这两个函数时，他们的状态是不同的，因此产生的随机数也不同，从而导致最终结果也不同。第51页/共73页6.3 微粒群算法微粒群算法的

36、基本思想：微粒群算法的基本思想：PSO是是J.Kennedy和和R.C.Eberhart于于1995年提出的一种新的优化算法，年提出的一种新的优化算法，其基本思想来源于鸟群捕食过程的社会行为研究。其基本思想来源于鸟群捕食过程的社会行为研究。PSO将群体中的成员描述为空间内一个没有质量、没将群体中的成员描述为空间内一个没有质量、没有体积的微粒，所有微粒通过一个适应度函数来确定有体积的微粒，所有微粒通过一个适应度函数来确定其在空间中的适应度。进化初期，每个微粒的位置和其在空间中的适应度。进化初期，每个微粒的位置和速度都被随机初始化，微粒在飞行过程中相互合作，速度都被随机初始化，微粒在飞行过程中相互

37、合作，根据自身和同伴的运动状态及时调整自己的速度和位根据自身和同伴的运动状态及时调整自己的速度和位置，以便在适应度较好的位置降落。置，以便在适应度较好的位置降落。第52页/共73页6.3 微粒群算法微粒群算法数学描述：微粒群算法数学描述：设微粒群体规模为设微粒群体规模为N，其中每个微粒在，其中每个微粒在D维空间中的维空间中的坐标位置可表示为坐标位置可表示为Xi=(xi1,xi2,xiD)，微粒，微粒i的速度的速度定义为每次迭代中微粒移动的距离，表示为定义为每次迭代中微粒移动的距离，表示为Vi=(vi1,vi2,viD)，Pi表示微粒表示微粒i所经历的最好位置，所经历的最好位置，Pg为群体中所有

38、微粒所经过的最好位置，则微粒为群体中所有微粒所经过的最好位置，则微粒i在在第第d维子空间中的飞行速度维子空间中的飞行速度vid根据下式进行调整：根据下式进行调整：微粒通过下式调整自身位置：微粒通过下式调整自身位置：第53页/共73页6.3 微粒群算法微粒群算法数学描述：微粒群算法数学描述：速度调整公式：速度调整公式：第一项为微粒先前速度乘一个权值进行加速，表示微粒对当前第一项为微粒先前速度乘一个权值进行加速，表示微粒对当前自身速度状态的信任，依据自身的速度进行惯性运动，因此称自身速度状态的信任，依据自身的速度进行惯性运动，因此称这个权值为惯性权值这个权值为惯性权值 第二项为微粒当前位置与自身最

39、优位置之间的距离，为认知部第二项为微粒当前位置与自身最优位置之间的距离，为认知部分，表示微粒本身的思考，即微粒的运动来源于自己经验的部分，表示微粒本身的思考，即微粒的运动来源于自己经验的部分分 第三项为微粒当前位置与群体最优位置之间的距离，为社会部第三项为微粒当前位置与群体最优位置之间的距离，为社会部分，表示微粒间的信息共享与相互合作，即微粒的运动中来源分，表示微粒间的信息共享与相互合作，即微粒的运动中来源于群体中其他微粒经验的部分于群体中其他微粒经验的部分第54页/共73页6.3 微粒群算法微粒群算法基本流程：微粒群算法基本流程：(1)Initial:随机初始化每一微粒的位置和速度。随机初始

40、化每一微粒的位置和速度。(2)Evaluation：依据适应度函数计算每个微粒的依据适应度函数计算每个微粒的适应度值，以作为判断每一微粒之好坏。适应度值，以作为判断每一微粒之好坏。(3)Find the Pbest：找出每一微粒到目前为止的找出每一微粒到目前为止的搜寻过程中最佳解，这个最佳解称为搜寻过程中最佳解，这个最佳解称为Pbest。(4)Find the Gbest：找出所有微粒到目前为止所找出所有微粒到目前为止所搜寻到的整体最佳解，此最佳解称之为搜寻到的整体最佳解，此最佳解称之为Gbest。(5)Update the Velocity：更新每一微粒的速度更新每一微粒的速度与位置与位置

41、(6)回到步骤回到步骤(2)继续执行，直到获得一个令人满意继续执行，直到获得一个令人满意的结果或符合终止条件为止。的结果或符合终止条件为止。第55页/共73页6.3 微粒群算法微粒群算法基本流程：微粒群算法基本流程：第56页/共73页6.3 微粒群算法PSO的参数设置：的参数设置：种群规模种群规模:一般取一般取20-40 粒子长度：粒子长度：由优化问题决定，就是问题解的长度由优化问题决定，就是问题解的长度 粒子范围：粒子范围：由优化问题决定，每一维可设定不同的由优化问题决定，每一维可设定不同的范围范围 最大速度：最大速度：决定粒子在一个循环中最大的移动距离，决定粒子在一个循环中最大的移动距离，

42、通常设为粒子的范围宽度通常设为粒子的范围宽度 学习因子：学习因子：二者相等且在二者相等且在0,4之间，通常取为之间，通常取为2 终止条件：终止条件：最大循环次数以及最小错误要求，由具体最大循环次数以及最小错误要求，由具体问题确定问题确定 惯性权值：惯性权值：第57页/共73页6.3 微粒群算法PSO与与GA的比较：的比较：(1)共同之处共同之处:两者都随机初始化种群，而且都使用两者都随机初始化种群，而且都使用适应值来评价系统，并且都根据适应值来进行一定的适应值来评价系统，并且都根据适应值来进行一定的随机搜索，两个系统都不是保证一定找到最优解随机搜索，两个系统都不是保证一定找到最优解 (2)区别

43、：区别：-PSO没有遗传操作如交叉、变异等，而是根没有遗传操作如交叉、变异等，而是根据自己的速度来决定搜索据自己的速度来决定搜索 -粒子还有一个重要的特点，就是有记忆，而粒子还有一个重要的特点，就是有记忆，而GA没有没有 -PSO的信息共享机制与的信息共享机制与GA也很不同，在也很不同，在GA中中染色体互相共享信息，整个种群的移动是比较平均的染色体互相共享信息，整个种群的移动是比较平均的向最优区域移动，而在向最优区域移动，而在PSO中只有中只有Gbest给出信息给给出信息给其他的粒子，整个搜索更新过程是跟随当前最优解的其他的粒子，整个搜索更新过程是跟随当前最优解的过程。过程。第58页/共73页

44、6.4 蚁群算法蚁群算法（Ant colony algorithm）是是20世世纪纪90年代初意大利学者年代初意大利学者M.Dorigo，V.Maniezzo，A.Colorni等从生物进化的机制中受到启发，通过模等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为提出来的一种新型的模拟自然界蚂蚁搜索路径的行为提出来的一种新型的模拟进化算法。蚂蚁在运动过程中，能够在它所经过的拟进化算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素路径上留下一种称之为外激素(pheromone)的物质进的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物行信息传递，而且蚂蚁在运动过程

45、中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。最优路径上的激素浓度越来越大，而其它率就越大。最优路径上的激素浓度越来越大，而其它的路径上激素浓度却会随着时间的流逝而消减。最终的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。整个蚁群会找出最优路径。第59页/共73页6.4 蚁群算法简单的蚂蚁寻食过程：蚂蚁从蚂蚁从A点出发，

46、速度相同，食物在点出发，速度相同，食物在D点，可能随机选择路线点，可能随机选择路线ABD或或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过步，本图为经过9个时间单位时的情形：走个时间单位时的情形：走ABD的蚂蚁到达终点，的蚂蚁到达终点，而走而走ACD的蚂蚁刚好走到的蚂蚁刚好走到C点，为一半路程。点，为一半路程。第60页/共73页6.4 蚁群算法简单的蚂蚁寻食过程：本图为从开始算起，经过本图为从开始算起，经过18个时间单位时的情形：走个时间单位时的情形：走ABD的蚂的蚂蚁到达终点后得到食物又返回了起点蚁到达终点后得到食

47、物又返回了起点A，而走，而走ACD的蚂蚁刚好的蚂蚁刚好走到走到D点。点。第61页/共73页6.4 蚁群算法简单的蚂蚁寻食过程：假设蚂蚁每经过一处所留下的信息素为一个单位，则经过假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取点取得了食物，此时得了食物，此时ABD的路线往返了的路线往返了2趟，每一处的信息素为趟，每一处的信息素为4个单个单位，而位，而 ACD的路线往返了一趟，每一处的信息素为的路线往返了一趟，每一处的信息素为2个单位，其个单位，其比值为比值为2：1。寻找食物的过程继

48、续进行，则按信息素的指导，蚁群在寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路路线上增派一只蚂蚁（共线上增派一只蚂蚁（共2只），而只），而ACD路线上仍然为一只蚂蚁。再路线上仍然为一只蚂蚁。再经过经过36个时间单位后，两条线路上的信息素单位积累为个时间单位后，两条线路上的信息素单位积累为12和和4，比值为比值为3：1。若按以上规则继续，蚁群在若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共路线上再增派一只蚂蚁（共3只），而只），而ACD路线上仍然为一只蚂蚁。再经过路线上仍然为一只蚂蚁。再经过36个时间单位后，个时间单位后，两条线路上的信息素单位积累为两条线路上的信息素单位积累为

49、24和和6，比值为，比值为4：1。若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择路线，而都选择ABD路线。这也就是前面所提到的正反馈效路线。这也就是前面所提到的正反馈效应。应。第62页/共73页6.4 蚁群算法人工蚁群算法：基于以上蚁群寻找食物时的最优路径选择问题，可基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如以构造人工蚁群，来解决最优化问题，如TSP问题。问题。人工蚁群中把具有简单功能的工作单元看作蚂蚁。人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素

50、浓度大的路径。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。择，也就是最终的优化结果。两者的区别在于人工蚁群有一定的记忆能力，能够两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。例如在而不是盲目的。例如在TSP问题中，可以预先知道当前问题中，可以预先知道当前城市到下一个目