优化算法及其在软测量技术中的应用(1)

1、第六章第六章 优化算法及其优化算法及其 在软测量技术中的应用在软测量技术中的应用 黄福珍黄福珍 H 本章主要内容本章主要内容 概述概述 遗传算法遗传算法 微粒群算法微粒群算法 蚁群算法蚁群算法 6.1 概述概述 进化计算进化计算(Evolutionary Computation)是通过模是通过模 拟自然界中生物进化机制进行搜索的一种算法。拟自然界中生物进化机制进行搜索的一种算法。 遗传算法（遗传算法（Genetic Algorithms） 进化策略（进化策略（Evolution Strategies） 进化规划（进化规划（Evolution Programming） 遗传算法遗传算法是模仿生物

2、遗传学和自然选择机理，是模仿生物遗传学和自然选择机理， 通过人工方式所构造的一类优化搜索算法，是通过人工方式所构造的一类优化搜索算法，是 对生物进化过程进行的一种数学仿真，是进化对生物进化过程进行的一种数学仿真，是进化 计算的最重要的形式。计算的最重要的形式。 6.1 概述概述 群智能群智能(Swarm Intelligence)这个概念来自对蜜蜂、蚂蚁、这个概念来自对蜜蜂、蚂蚁、 大雁等群居生物群体行为的观察和研究。任何启发于群大雁等群居生物群体行为的观察和研究。任何启发于群 居性昆虫群体和其它动物群体的集体行为而设计的算法居性昆虫群体和其它动物群体的集体行为而设计的算法 和分布式问题解决装

3、置都称为群智能。和分布式问题解决装置都称为群智能。 群智能群智能是一种在自然界生物群体所表现出的智能现象启是一种在自然界生物群体所表现出的智能现象启 发下提出的人工智能实现模式，是对简单生物群体的智发下提出的人工智能实现模式，是对简单生物群体的智 能涌现现象的具体模式研究，即简单智能的主体通过合能涌现现象的具体模式研究，即简单智能的主体通过合 作表现出复杂智能行为的特性。该智能模式需要以相当作表现出复杂智能行为的特性。该智能模式需要以相当 数目的智能个体来实现对问题的求解功能。数目的智能个体来实现对问题的求解功能。 群智能群智能在没有集中控制并且不提供全局模型的前提下，在没有集中控制并且不提供

4、全局模型的前提下， 为寻找复杂的分布式问题的解决方案提供了基础为寻找复杂的分布式问题的解决方案提供了基础。 6.1 概述概述 群智能的特点：群智能的特点： 分布式：分布式：能够适应当前网络环境下的工作状态能够适应当前网络环境下的工作状态 鲁棒性：鲁棒性：没有中心的控制与数据，个体的故障没有中心的控制与数据，个体的故障 不影响整个问题的求解不影响整个问题的求解 扩充性：扩充性：个体的增加，系统的通信开销增加小个体的增加，系统的通信开销增加小 简单性：简单性：个体简单，实现也比较简单个体简单，实现也比较简单 6.1 概述概述 群智能的典型实现模式：群智能的典型实现模式： 微粒群算法（微粒群算法（P

5、article swarm optimization, PSO）：）：模拟鸟群运动模式模拟鸟群运动模式 蚁群算法（蚁群算法（Ant colony algorithm）：）：模拟生模拟生 物蚁群运动行为物蚁群运动行为 6.2 遗传算法遗传算法 遗传算法的基本机理遗传算法的基本机理 遗传算法的一般框架遗传算法的一般框架 遗传算法遗传算法 的模式理论的模式理论 Matlab遗传算法工具箱遗传算法工具箱 6.2.1 遗传算法的基本机理遗传算法的基本机理 遗传与进化的系统观点：遗传与进化的系统观点： 1)1) 生物的所有遗传信息的都包含在其染色体中，染色体决生物的所有遗传信息的都包含在其染色体中，染色体

6、决 定了生物的性状定了生物的性状 2)2) 染色体是由基因及其有规律的排列所构成的，遗传进化染色体是由基因及其有规律的排列所构成的，遗传进化 过程发生在染色体上过程发生在染色体上 3)3) 生物的繁殖过程是由其基因的复制过程来完成的生物的繁殖过程是由其基因的复制过程来完成的 4)4) 通过同源染色体之间的交叉或染色体的变异会产生新的通过同源染色体之间的交叉或染色体的变异会产生新的 物种，使生物呈现新的性状物种，使生物呈现新的性状 5)5) 对环境适应性好的基因或染色体经常比适应性差的基因对环境适应性好的基因或染色体经常比适应性差的基因 或染色体有更多的机会遗传到下一代或染色体有更多的机会遗传到

7、下一代 6.2.1 遗传算法的基本机理遗传算法的基本机理 遗传算法的基本机理遗传算法的基本机理 模拟自然界优胜劣汰的进化现象，把搜索空模拟自然界优胜劣汰的进化现象，把搜索空 间映射为遗传空间，把可能的解编码成一个向间映射为遗传空间，把可能的解编码成一个向 量量染色体，向量的每个元素称为基因。利染色体，向量的每个元素称为基因。利 用选择、交叉、变异等遗传算子产生新的染色用选择、交叉、变异等遗传算子产生新的染色 体，通过不断计算各染色体的适应度值，选择体，通过不断计算各染色体的适应度值，选择 最好的染色体，获得最优解。最好的染色体，获得最优解。 6.2.1 遗传算法的基本机理遗传算法的基本机理 遗

8、传学和遗传算法中基本术语对照表：遗传学和遗传算法中基本术语对照表： 自然界自然界 染色体染色体( (chromosome) ) 基因基因( (gene) 等位基因等位基因(allele) 染色体位置染色体位置(locus) 基因型基因型(genotype) 表型表型(phenotype) 遗传算法遗传算法 字符串字符串 字符字符, ,特征特征 特征值特征值 字符串位置字符串位置 结构结构 参数集参数集, ,译码结构译码结构 6.2.2 遗传算法的一般框架遗传算法的一般框架 遗传算法的构成要素：遗传算法的构成要素： 染色体编码方法染色体编码方法 适应度函数适应度函数 遗传算子（选择、交叉、变异）

9、遗传算子（选择、交叉、变异） 遗传参数设置遗传参数设置 6.2.2 遗传算法的一般框架遗传算法的一般框架 编码与解码：编码与解码： 将问题结构变换为位串形式表示的过程叫编码，将问题结构变换为位串形式表示的过程叫编码， 相反把位串形式表示变换为原问题结构的过程相反把位串形式表示变换为原问题结构的过程 叫解码叫解码 GA常用的编码方法：二进制编码，实数编码，常用的编码方法：二进制编码，实数编码， 格雷码，符号编码，多参数编码等格雷码，符号编码，多参数编码等 6.2.2 遗传算法的一般框架遗传算法的一般框架 适应度函数：适应度函数： 一般情况下，适应度函数由目标函数变换而成，一般情况下，适应度函数由

10、目标函数变换而成， 适应度函数要求为非负函数适应度函数要求为非负函数 若目标函数为最大化问题，则若目标函数为最大化问题，则 若目标函数为最小化问题，则若目标函数为最小化问题，则 min ( )( )( )( )FfxfxFfxfxc或 max ( )( )( )( )FfxfxFfxcfx 或 6.2.2 遗传算法的一般框架遗传算法的一般框架 遗传算子：遗传算子： 选择（选择（Selection）：）： - 从旧的种群中选择适应度高的染色体，放入匹配集从旧的种群中选择适应度高的染色体，放入匹配集 （缓冲区），为以后染色体交叉、变异，产生新的染色（缓冲区），为以后染色体交叉、变异，产生新的染色

11、体作准备。体作准备。 - 选择方法：适应度比例法（轮盘赌法），即按各染选择方法：适应度比例法（轮盘赌法），即按各染 色体适应度大小比例来决定其被选择数目的多少。某染色体适应度大小比例来决定其被选择数目的多少。某染 色体被选的概率：色体被选的概率： () () i r i fx P fx 6.2.2 遗传算法的一般框架遗传算法的一般框架 遗传算子：遗传算子： 交叉（交叉（Crossover）：）： - 随机选择二个染色体随机选择二个染色体(双亲染色体双亲染色体)，随机指定一点，随机指定一点 或多点，将两者部分码值进行交换，可得二个新的染色或多点，将两者部分码值进行交换，可得二个新的染色 体体(子

12、辈染色体子辈染色体)。 新的子辈染色体: A 11010001 B 01011110 6.2.2 遗传算法的一般框架遗传算法的一般框架 遗传算子：遗传算子： 变异（变异（Mutation）：）： - 模拟生物在自然界环境变化，引起基因的突变。模拟生物在自然界环境变化，引起基因的突变。 - 在染色体二进制编码中，在染色体二进制编码中，1变成变成0，或，或0变成变成1 - 变异产生染色体的多样性，避免进化中早期成熟，变异产生染色体的多样性，避免进化中早期成熟， 陷入局部极值点，变异的概率很低。陷入局部极值点，变异的概率很低。 A 1 0 1 0 0 1 1 0 A 1 0 1 1 0 1 1 0

13、6.2.2 遗传算法的一般框架遗传算法的一般框架 遗传参数设置：遗传参数设置： N：群体大小，即群体中所含个体的数量，一般取群体大小，即群体中所含个体的数量，一般取 20100 T：GA的终止进化代数，一般取的终止进化代数，一般取100500 Pc：交叉概率，一般取交叉概率，一般取0.40.99 Pm：变异概率，一般取变异概率，一般取0.00010.1 6.2.2 遗传算法的一般框架遗传算法的一般框架 遗传算法进行问题求解的过程：遗传算法进行问题求解的过程： 初始化群体初始化群体 计算群体中每个个体的适应度值计算群体中每个个体的适应度值 按由个体适应度值所决定的某个规则选择进入下一代按由个体适

14、应度值所决定的某个规则选择进入下一代 的个体的个体 按概率按概率Pc进行交叉操作进行交叉操作 按概率按概率Pm进行变异操作进行变异操作 若没有满足某种停止条件，就转到第若没有满足某种停止条件，就转到第2步，否则进入下步，否则进入下 一步一步 输出群体中适应度值最优的染色体作为问题的满意解输出群体中适应度值最优的染色体作为问题的满意解 或最优解或最优解 6.2.2 遗传算法的一般框架遗传算法的一般框架 遗传算法应用举例：遗传算法应用举例： 例例4-1 利用遗传算法求解区间利用遗传算法求解区间0,31上的二次函数上的二次函数y=x2的的 最大值。最大值。 y=x 2 31 X Y 分析： 原问题可

15、转化为在区间原问题可转化为在区间0, 31中中 搜索能使搜索能使y取最大值的点取最大值的点a的问题。的问题。 那么，那么，0, 31 中的点中的点x就是个体，函就是个体，函 数值数值f(x)恰好就可以作为恰好就可以作为x的适应度，的适应度， 区间区间0, 31就是一个解空间就是一个解空间 。这。这 样样, 只要能给出个体只要能给出个体x的适当染色体的适当染色体 编码，该问题就可以用遗传算法来编码，该问题就可以用遗传算法来 解决。解决。 6.2.2 遗传算法的一般框架遗传算法的一般框架 遗传算法应用举例：遗传算法应用举例： 解：(1) 设定种群规模，设定种群规模，编码染色体，编码染色体，产生初始

16、种群。产生初始种群。 将种群规模设定将种群规模设定为为4，用，用5位二进制数编码染色体，取下位二进制数编码染色体，取下 列个体组成列个体组成初始种群初始种群S1: : s1= 13 (01101), s2= 24 (11000) s3= 8 (01000), s4= 19 (10011) (2) 定义适应度函数：定义适应度函数：f (x)=x2 (3) 计算各代种群中的各个体的适应度计算各代种群中的各个体的适应度, 并对其染色体进并对其染色体进 行遗传操作，直到适应度最高的个体行遗传操作，直到适应度最高的个体(即即31（11111）)出出 现为止。现为止。 6.2.2 遗传算法的一般框架遗传算

17、法的一般框架 遗传算法应用举例：遗传算法应用举例： 首先计算种群首先计算种群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.31 1 ( ) ( ) ()

18、 i iN j j f x P x f x s4 0.31 s2 0.49 s1 0.14 s30.06 6.2.2 遗传算法的一般框架遗传算法的一般框架 遗传算法应用举例：遗传算法应用举例： 在算法中赌轮选择法可用下面的子过程来模拟：在算法中赌轮选择法可用下面的子过程来模拟： 在在0, 1区间内产生一个均匀分布的随机数区间内产生一个均匀分布的随机数r。 若若rq1，则染色体，则染色体x1被选中。被选中。 若若qk-1rqk(2kN)，则染色体，则染色体xk被选中。其中的被选中。其中的qi称称 为染色体为染色体xi (i=1, 2, , n)的积累概率，其计算公式为的积累概率，其计算公式为 ：

19、 1 () i ij j qP x 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 1 s2=11000 576 0.49 0.63 2 s3=01000 64 0.06 0.69 0 s4=10011 361 0.31 1.00 1 6.2.2 遗传算法

20、的一般框架遗传算法的一般框架 遗传算法应用举例：遗传算法应用举例： 于是，经复制得群体：于是，经复制得群体： 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） 6.2.2 遗传算法的一般框架遗传算法的一

21、般框架 遗传算法应用举例：遗传算法应用举例： 设变异率设变异率pm=0.001，这样，群体，这样，群体S1中共有中共有 540.001=0.02 位基因可以变异。位基因可以变异。0.02位显然不足位显然不足1位，所以本轮遗传操位，所以本轮遗传操 作不做变异。作不做变异。 于是，得到第二代种群于是，得到第二代种群S2： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16） 6.2.2 遗传算法的一般框架遗传算法的一般框架 遗传算法应用举例：遗传算法应用举例： 第二代种群第二代种群S2中各染色体的情况：中各染色体的情况： 染色体染色体 适应度适

22、应度选择概率选择概率积累概率积累概率 估计的估计的 选中次数选中次数 s1=11001 625 0.36 0.36 1 s2=01100 144 0.08 0.44 0 s3=11011 729 0.41 0.85 2 s4=10000 256 0.15 1.00 1 6.2.2 遗传算法的一般框架遗传算法的一般框架 遗传算法应用举例：遗传算法应用举例： 假设这一轮选择复制操作中，种群假设这一轮选择复制操作中，种群S2中的中的4个染色体都被选个染色体都被选 中，则得到群体：中，则得到群体： s1=11001（25）, s2= 01100（12） s3=11011（27）, s4= 10000（

23、16） 做交叉运算，让做交叉运算，让s1与与s2，s3与与s4 分别交换后三位基因：分别交换后三位基因： s1 =11100（28）, s2 = 01001（9） s3 =11000（24）, s4 = 10011（19） 这一轮仍然不会发生变异。这一轮仍然不会发生变异。 6.2.2 遗传算法的一般框架遗传算法的一般框架 遗传算法应用举例：遗传算法应用举例： 第三代种群第三代种群S3中各染色体的情况：中各染色体的情况： 染色体染色体 适应度适应度选择概率选择概率积累概率积累概率 估计的估计的 选中次数选中次数 s1=11100 784 0.44 0.44 2 s2=01001 81 0.04

24、0.48 0 s3=11000 576 0.32 0.80 1 s4=10011 361 0.20 1.00 1 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） 这一轮仍然不会发生变

25、异。这一轮仍然不会发生变异。 6.2.2 遗传算法的一般框架遗传算法的一般框架 遗传算法应用举例：遗传算法应用举例： 第四代种群第四代种群S 4中已经出现了适应度最高的染色体 中已经出现了适应度最高的染色体 s1=11111。于是，遗传操作终止，将。于是，遗传操作终止，将染色体染色体“11111”作作 为最终结果输出。为最终结果输出。然后，将染色体然后，将染色体“11111”解码为表现解码为表现 型，即得所求的最优解：型，即得所求的最优解：31。将。将31代入函数代入函数y=x2中，即中，即 得原问题的解，即函数得原问题的解，即函数y=x2的最大值为的最大值为961。 Y Y y=x2 8 1

26、3 19 24 X 第一代种群及其适应度第一代种群及其适应度 y=x2 12 16 25 27 X Y 第二代种群及其适应度第二代种群及其适应度 y=x2 9 19 24 28 X Y 第三代种群及其适应度第三代种群及其适应度 y=x2 16 24 28 31 X 第四代种群及其适应度第四代种群及其适应度 6.2.2 遗传算法的一般框架遗传算法的一般框架 遗传算法的特点：遗传算法的特点： GA是对参数集合的编码而非针对参数本身进行优化是对参数集合的编码而非针对参数本身进行优化 GA是从问题解的编码组开始而非单个解开始搜索是从问题解的编码组开始而非单个解开始搜索 GA利用目标函数的适应度这一信息

27、而非利用导数或利用目标函数的适应度这一信息而非利用导数或 其他辅助信息来指导搜索其他辅助信息来指导搜索 GA利用选择、交叉、变异等算子而不是确定性规则利用选择、交叉、变异等算子而不是确定性规则 进行随机操作进行随机操作 6.2.2 遗传算法的一般框架遗传算法的一般框架 遗传算法的局限性：遗传算法的局限性： 遗传算法在解决某些问题时速度较慢遗传算法在解决某些问题时速度较慢 遗传算法对编码方案的依赖性较强遗传算法对编码方案的依赖性较强 算法的鲁棒性不够好算法的鲁棒性不够好 6.2.3 遗传算法的模式理论遗传算法的模式理论 遗传算法的理论基础是遗传算法的二进制表达式及模遗传算法的理论基础是遗传算法的

28、二进制表达式及模 式的含义。式的含义。模式模式是能对染色体之间的相似性进行解释是能对染色体之间的相似性进行解释 的模板。的模板。 设设GA的个体的个体 ，记集合，记集合 则称则称 为一个模式，其中是通配符。为一个模式，其中是通配符。 即即模式模式(schema)是含有通配符是含有通配符(*)的一类字符串的通式的一类字符串的通式 表达。每个表达。每个“*”可以取可以取“1”或者或者“0”。 l Bp0,1,* l S Ss 6.2.3 遗传算法的模式理论遗传算法的模式理论 模式举例：模式举例： - 模式模式 * *1010111010101110与以下两个字符串匹配：与以下两个字符串匹配： 01

29、0101110 110101110 010101110 110101110 - 模式模式 * *10101010110110与以下四个字符串匹配：与以下四个字符串匹配： 010100110 010101110 010100110 010101110 110100110 110101110 110100110 110101110 6.2.3 遗传算法的模式理论遗传算法的模式理论 一个一个模式模式s的阶的阶(order)是出现在模式中的是出现在模式中的“0”和和“1” 的数目，记为的数目，记为o(s)。 - 如：模式如：模式“0*”的阶为的阶为1，模式，模式“10*1*”的阶为的阶为3 一个一个模

30、式模式s的长度的长度(Length)是出现在模式中第一个确定是出现在模式中第一个确定 位置和最后一个确定位置之间的距离，记为位置和最后一个确定位置之间的距离，记为 。 - 如：模式如：模式“01*”的长度为的长度为1，模式，模式“0*1”的长的长 度为度为3。 )(s 6.2.3 遗传算法的模式理论遗传算法的模式理论 复制对模式的影响：复制对模式的影响： 假定在给定的时间（代）假定在给定的时间（代）t，一个特定的模式，一个特定的模式s在群体在群体P(t) 中包含有中包含有m个代表串，记为个代表串，记为m=m(s,t)。每个串根据适应值每个串根据适应值 的大小获得不同的复制概率。串的大小获得不同

31、的复制概率。串i的复制概率为：的复制概率为： 则在群体则在群体P(t+1)中，模式中，模式s的代表串的数量的期望值为的代表串的数量的期望值为 1 ( )( ) n i j pf if j 1 ( ,1)( , )( )( ) n j E m s tm s tn f sf j 其中，其中， 表示模式表示模式s在在t时刻的所有代表串的适应值的时刻的所有代表串的适应值的 均值，称为模式均值，称为模式s的适应值。的适应值。 )(sf 6.2.3 遗传算法的模式理论遗传算法的模式理论 复制对模式的影响：复制对模式的影响： 若记若记P(t)中所有个体的适应值的平均值为：中所有个体的适应值的平均值为： 则有

32、：则有： 上式表明，模式上式表明，模式s的代表串的数目随时间增长的幅度正比的代表串的数目随时间增长的幅度正比 于模式于模式s的适应值与群体平均适应值的比值。即：的适应值与群体平均适应值的比值。即：适应值适应值 高于群体平均值的模式在下一代的代表串数目将会增加，高于群体平均值的模式在下一代的代表串数目将会增加， 而适应值低于群体平均值的模式在下一代的代表串数目将而适应值低于群体平均值的模式在下一代的代表串数目将 会减少。会减少。 1 ( ) n j f j f n ( ) ( ,1)( , ) f s E m s tm s t f 6.2.3 遗传算法的模式理论遗传算法的模式理论 复制对模式的影

33、响：复制对模式的影响： 假设模式的适应值为假设模式的适应值为 ，其中，其中c是一个常数，则有：是一个常数，则有： 上式表明，上式表明，在平均适应值之上（之下）的模式，将会按在平均适应值之上（之下）的模式，将会按 指数增长（衰减）的方式被复制。指数增长（衰减）的方式被复制。复制的结果并没有生成复制的结果并没有生成 新的模式新的模式。因而，为了探索搜索空间中的未搜索部分，需因而，为了探索搜索空间中的未搜索部分，需 要利用交叉和变异操作。要利用交叉和变异操作。 1 (1) ( ,1)( , ) ( , ) (1)( ,0) (1)t c f E m s tm s t f m s tcm sc fc)

34、1 ( 6.2.3 遗传算法的模式理论遗传算法的模式理论 交叉对模式的影响：交叉对模式的影响： 交叉会改变模式的一部分，模式的长度越长，被破坏的概交叉会改变模式的一部分，模式的长度越长，被破坏的概 率越大。率越大。 假定模式假定模式s在交叉后不被破坏的概率为在交叉后不被破坏的概率为ps，则：则： 若交叉概率为若交叉概率为pc，则，则s不被破坏的概率为：不被破坏的概率为： ( ) 1 1 s s p l ( ) 1 1 sc s pp l 6.2.3 遗传算法的模式理论遗传算法的模式理论 交叉对模式的影响：交叉对模式的影响： 若综合考虑复制和交叉的影响，特定模式在下一代中的数若综合考虑复制和交叉

35、的影响，特定模式在下一代中的数 量可用下式来估计：量可用下式来估计： 可见，可见，对于那些高于平均适应度且具有短短定义长度的对于那些高于平均适应度且具有短短定义长度的 模式将更多地出现在下一代中。模式将更多地出现在下一代中。 ( )( ) ( ,1)( , )1 1 c f ss E m s tm s tp lf 6.2.3 遗传算法的模式理论遗传算法的模式理论 变异对模式的影响：变异对模式的影响： 变异算子以概率变异算子以概率pm随机地改变个体某一位的值，只有当随机地改变个体某一位的值，只有当 o(s)个确定位的值不被破坏时，模式个确定位的值不被破坏时，模式s才不被破坏。才不被破坏。 模式模

36、式s在变异后不被破坏的概率：在变异后不被破坏的概率： 由于由于Pmgatool 图形界面如图：图形界面如图： 6.2.4 Matlab遗传算法工具箱遗传算法工具箱 GADS工具箱可通过命令行或工具箱可通过命令行或m文件调用，其核心函数为：文件调用，其核心函数为： x, fval, reason, output = ga(fitnessfcn, nvars, A, b, Aeq, beq, LB, UB, nonlcon, options) 函数参数说明如下：函数参数说明如下： 输输 入入 参参 数数 fitnessfcn：适应度函数：适应度函数f(x) nvars：变量数量：变量数量 A,b：

37、线性不等式约束条件下：线性不等式约束条件下A1xb1的参数的参数 Aeq,beq：线性等式约束条件：线性等式约束条件A2x=b2的参数的参数 LB：x的取值下限的取值下限v1 UB：x的取值上限的取值上限v2 nonlcon：非线性约束条件：非线性约束条件c1(x)0和和c2(x)=0 options:：与算法性能相关的参数：与算法性能相关的参数 输输 出出 参参 数数 x：最优值：最优值 fval：最优值下的适应度函数值：最优值下的适应度函数值 reason：算法停止原因：算法停止原因 output：每次迭代信息及其他算法信息：每次迭代信息及其他算法信息 6.2.4 Matlab遗传算法工具

38、箱遗传算法工具箱 影响遗传算法性能的参数由结构体影响遗传算法性能的参数由结构体options给定，可使用给定，可使用 如下命令查看如下命令查看options的默认值：的默认值： options=gaoptimset GADS中默认的中默认的options参数值为：参数值为： PopulationType: doubleVector种群数据类型种群数据类型 InitialPopulation: 初始种群初始种群 PopInitRange: 2*1 double初始种群中个体取值范围初始种群中个体取值范围InitialScores: 初始适应度初始适应度 PopulationSize: 20种群规

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

40、FitnessScalingFcn: fitscalingrank调节适应度的函数句柄调节适应度的函数句柄 MigrationFraction: 0.2000变异概率变异概率SelectionFcn: selectionstochunif选择函数句柄选择函数句柄 Generations: 100最大迭代次数最大迭代次数CrossoverFcn: crossoverscattered交叉函数句柄交叉函数句柄 TimeLimit: Inf最大运行时间最大运行时间MutationFcn: mutationgaussian变异函数句柄变异函数句柄 FitnessLimit: -Inf当适应度函数达该值

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

42、性约束的可行性非线性约束的可行性Vectorized: off适应度函数是否矢量化适应度函数是否矢量化 6.2.4 Matlab遗传算法工具箱遗传算法工具箱 如果需要修改上述如果需要修改上述options中的参数值，例如修改中的参数值，例如修改 PopulationSize至至100，可采用如下命令：，可采用如下命令： options=gaoptimset(PopulationSize,100) 也可通过上述命令同时修改多个参数也可通过上述命令同时修改多个参数 在实际应用中，通常需要根据应用需求编写适当的适应在实际应用中，通常需要根据应用需求编写适当的适应 度函数，在编写函数的时候需注意度函数

43、，在编写函数的时候需注意GADS是求最小值的，是求最小值的， 编写好的适应度函数需存成编写好的适应度函数需存成m文件放在同一目录下。文件放在同一目录下。 6.2.4 Matlab遗传算法工具箱遗传算法工具箱 例：例：当当x1-3.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

44、)*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(my_func1,2,opt1) 6.2.4 Matlab遗传算法工具箱遗传算法工具箱 运行结果如下：运行结果如下： Optimization terminated: stall generations limit exceeded.

45、x = 11.6288 5.7244 fval = -38.8354 需要注意到是：由于遗传算法是一种随机搜索算法，每需要注意到是：由于遗传算法是一种随机搜索算法，每 次运行得到的结果很可能不同，这主要是次运行得到的结果很可能不同，这主要是Matlab在每次在每次 迭代时，采用迭代时，采用rand和和randn这两个随机数生成函数来随机这两个随机数生成函数来随机 选择样本，每次选择样本，每次Matlab调用这两个函数时，他们的状态调用这两个函数时，他们的状态 是不同的，因此产生的随机数也不同，从而导致最终结是不同的，因此产生的随机数也不同，从而导致最终结 果也不同。果也不同。 6.3 微粒群算

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

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

48、历的最好位置，所经历的最好位置，Pg为群体中所有微粒所经过为群体中所有微粒所经过 的最好位置，则微粒的最好位置，则微粒i在第在第d维子空间中的飞行速度维子空间中的飞行速度vid根根 据下式进行调整：据下式进行调整： 微粒通过下式调整自身位置：微粒通过下式调整自身位置： 12 () ()() () ididididgdid Vw VcRandpxcRandpx ididid xxV 6.3 微粒群算法微粒群算法 微粒群算法数学描述：微粒群算法数学描述： 速度调整公式：速度调整公式： 第一项为微粒先前速度乘一个权值进行加速，表示微粒对当前自身第一项为微粒先前速度乘一个权值进行加速，表示微粒对当前自

49、身 速度状态的信任，依据自身的速度进行惯性运动，因此称这个权值速度状态的信任，依据自身的速度进行惯性运动，因此称这个权值 为惯性权值为惯性权值 第二项为微粒当前位置与自身最优位置之间的距离，为认知部分，第二项为微粒当前位置与自身最优位置之间的距离，为认知部分， 表示微粒本身的思考，即微粒的运动来源于自己经验的部分表示微粒本身的思考，即微粒的运动来源于自己经验的部分 第三项为微粒当前位置与群体最优位置之间的距离，为社会部分，第三项为微粒当前位置与群体最优位置之间的距离，为社会部分， 表示微粒间的信息共享与相互合作，即微粒的运动中来源于群体中表示微粒间的信息共享与相互合作，即微粒的运动中来源于群体

50、中 其他微粒经验的部分其他微粒经验的部分 12 () ()() () ididididgdid Vw VcRandpxcRandpx 6.3 微粒群算法微粒群算法 微粒群算法基本流程：微粒群算法基本流程： (1) Initial: 随机初始化每一微粒的位置和速度。随机初始化每一微粒的位置和速度。 (2) Evaluation：依据适应度函数计算每个微粒的适应度依据适应度函数计算每个微粒的适应度 值，以作为判断每一微粒之好坏。值，以作为判断每一微粒之好坏。 (3) Find the Pbest：找出每一微粒到目前为止的搜寻过找出每一微粒到目前为止的搜寻过 程中最佳解，这个最佳解称为程中最佳解，这

51、个最佳解称为Pbest。 (4) Find the Gbest：找出所有微粒到目前为止所搜寻到找出所有微粒到目前为止所搜寻到 的整体最佳解，此最佳解称之为的整体最佳解，此最佳解称之为Gbest。 (5) Update the Velocity：更新每一微粒的速度与位置更新每一微粒的速度与位置 (6) 回到步骤回到步骤(2)继续执行，直到获得一个令人满意的结果继续执行，直到获得一个令人满意的结果 或符合终止条件为止。或符合终止条件为止。 6.3 微粒群算法微粒群算法 微粒群算法基本流程：微粒群算法基本流程： 6.3 微粒群算法微粒群算法 PSO的参数设置：的参数设置： 种群规模种群规模: 一般取

52、一般取20-40 粒子长度：粒子长度：由优化问题决定，就是问题解的长度由优化问题决定，就是问题解的长度 粒子范围：粒子范围：由优化问题决定，每一维可设定不同的范围由优化问题决定，每一维可设定不同的范围 最大速度：最大速度：决定粒子在一个循环中最大的移动距离，通决定粒子在一个循环中最大的移动距离，通 常设为粒子的范围宽度常设为粒子的范围宽度 学习因子：学习因子：二者相等且在二者相等且在0,4之间，通常取为之间，通常取为2 终止条件：终止条件：最大循环次数以及最小错误要求，由具体问最大循环次数以及最小错误要求，由具体问 题确定题确定 惯性权值：惯性权值： 6.3 微粒群算法微粒群算法 PSO与与G

53、A的比较：的比较： (1) 共同之处共同之处: 两者都随机初始化种群，而且都使用适应两者都随机初始化种群，而且都使用适应 值来评价系统，并且都根据适应值来进行一定的随机搜值来评价系统，并且都根据适应值来进行一定的随机搜 索，两个系统都不是保证一定找到最优解索，两个系统都不是保证一定找到最优解 (2) 区别：区别： - PSO没有遗传操作如交叉、变异等，而是根据自己没有遗传操作如交叉、变异等，而是根据自己 的速度来决定搜索的速度来决定搜索 - 粒子还有一个重要的特点，就是有记忆，而粒子还有一个重要的特点，就是有记忆，而GA没有没有 - PSO的信息共享机制与的信息共享机制与GA也很不同，在也很不

54、同，在GA中染色中染色 体互相共享信息，整个种群的移动是比较平均的向最优体互相共享信息，整个种群的移动是比较平均的向最优 区域移动，而在区域移动，而在PSO中只有中只有Gbest给出信息给其他的粒给出信息给其他的粒 子，整个搜索更新过程是跟随当前最优解的过程。子，整个搜索更新过程是跟随当前最优解的过程。 6.4 蚁群算法蚁群算法 蚁群算法（蚁群算法（Ant colony algorithm）是是20世纪世纪90年代年代 初意大利学者初意大利学者M.Dorigo，V.Maniezzo，A.Colorni等从生等从生 物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路物进化的机制中受到启发，通过模拟

55、自然界蚂蚁搜索路 径的行为提出来的一种新型的模拟进化算法。蚂蚁在运径的行为提出来的一种新型的模拟进化算法。蚂蚁在运 动过程中，能够在它所经过的路径上留下一种称之为外动过程中，能够在它所经过的路径上留下一种称之为外 激素激素(pheromone)的物质进行信息传递，而且蚂蚁在运动的物质进行信息传递，而且蚂蚁在运动 过程中能够感知这种物质，并以此指导自己的运动方向，过程中能够感知这种物质，并以此指导自己的运动方向， 因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息 正反馈现象：某一路径上走过的蚂蚁越多，则后来者选正反馈现象：某一路径上走过的蚂蚁越多，

56、则后来者选 择该路径的概率就越大。最优路径上的激素浓度越来越择该路径的概率就越大。最优路径上的激素浓度越来越 大，而其它的路径上激素浓度却会随着时间的流逝而消大，而其它的路径上激素浓度却会随着时间的流逝而消 减。最终整个蚁群会找出最优路径。减。最终整个蚁群会找出最优路径。 6.4 蚁群算法蚁群算法 简单的蚂蚁寻食过程：简单的蚂蚁寻食过程： 蚂蚁从蚂蚁从A点出发，速度相同，食物在点出发，速度相同，食物在D点，可能随机选择路线点，可能随机选择路线ABD 或或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走。假设初始时每条分配路线一只蚂蚁，每个时间单位行走 一步，本图为经过一步，本图为经过9

57、个时间单位时的情形：走个时间单位时的情形：走ABD的蚂蚁到达终点，的蚂蚁到达终点， 而走而走ACD的蚂蚁刚好走到的蚂蚁刚好走到C点，为一半路程。点，为一半路程。 6.4 蚁群算法蚁群算法 简单的蚂蚁寻食过程：简单的蚂蚁寻食过程： 本图为从开始算起，经过本图为从开始算起，经过18个时间单位时的情形：走个时间单位时的情形：走ABD的蚂的蚂 蚁到达终点后得到食物又返回了起点蚁到达终点后得到食物又返回了起点A，而走，而走ACD的蚂蚁刚好的蚂蚁刚好 走到走到D点。点。 6.4 蚁群算法蚁群算法 简单的蚂蚁寻食过程：简单的蚂蚁寻食过程： 假设蚂蚁每经过一处所留下的信息素为一个单位，则经过假设蚂蚁每经过一处

58、所留下的信息素为一个单位，则经过36个时间个时间 单位后，所有开始一起出发的蚂蚁都经过不同路径从单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，点取得了食物， 此时此时ABD的路线往返了的路线往返了2趟，每一处的信息素为趟，每一处的信息素为4个单位，而个单位，而 ACD的的 路线往返了一趟，每一处的信息素为路线往返了一趟，每一处的信息素为2个单位，其比值为个单位，其比值为2：1。 寻找食物的过程继续进行，则按信息素的指导，蚁群在寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上路线上 增派一只蚂蚁（共增派一只蚂蚁（共2只），而只），而ACD路线上仍然为一只蚂蚁。再经过路

59、线上仍然为一只蚂蚁。再经过36 个时间单位后，两条线路上的信息素单位积累为个时间单位后，两条线路上的信息素单位积累为12和和4，比值为，比值为3：1。 若按以上规则继续，蚁群在若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共路线上再增派一只蚂蚁（共3只），只）， 而而ACD路线上仍然为一只蚂蚁。再经过路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上个时间单位后，两条线路上 的信息素单位积累为的信息素单位积累为24和和6，比值为，比值为4：1。 若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，路线， 而都选择而都选择A

60、BD路线。这也就是前面所提到的正反馈效应。路线。这也就是前面所提到的正反馈效应。 6.4 蚁群算法蚁群算法 人工蚁群算法：人工蚁群算法： 基于以上蚁群寻找食物时的最优路径选择问题，可以构基于以上蚁群寻找食物时的最优路径选择问题，可以构 造人工蚁群，来解决最优化问题，如造人工蚁群，来解决最优化问题，如TSP问题。问题。 人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者 的相似之处在于都是优先选择信息素浓度大的路径。较短的相似之处在于都是优先选择信息素浓度大的路径。较短 路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也路径的信息素浓度高，所以能够最