电机CAD技术：第5讲 电机数值优化方法(三)

1、第5讲 电机数值优化方法(三)-智能优化方法2022/7/191jiahaolai主要内容contents5.6.1 遗传优化方法(Genetic Algorithms,GA)5.6.2 禁忌搜索算法(Tabu Search,TS)5.6.3 粒子群优化方法(Prticle Swan Optimization,PSO)5.6.4 模拟退火算法(Simulated Annealing,SA)2022/7/192jiahaolai5.6.1遗传优化算法遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的一种最重要的形式。遗传算

2、法与传统数学模型截然不同，它为那些难以找到传统数学模型的难题指出了一个解决方法。自从霍兰德(Holland) 1975年在他的著作Adaptation in Natural and Artificial Systems中首次提出遗传算法以来，经过近30年研究，现在已发展到一个比较成熟的阶段，并且在实际中得到很好的应用。2022/7/193jiahaolai遗传算法的基本原理2022/7/194jiahaolai2022/7/19jiahaolai5遗传算法的基本思路遗传算法的基本原理1.编码与解码许多复杂的应用问题，可以化简为简单的位串形式编码表示，这种将问题结构变换为位串形式编码表示的过程叫

3、编码；而将位串形式的编码表示变换为原问题的过程称为解码或译码。编码是应用遗传算法解决问题的第一步。2022/7/196jiahaolai例如，最优问题 min f(x1,x2)=(x1-2)2+(x2-3)2，其解在范围 0 x13，0 x24。将变量解的范围分别用10位二进制(当然也可用其他位数的二进制)表示：x1的范围 0：00 0000 0000 00 0000 0001 3： 11 1111 1111 相应的位串编码形式可表示为： xx xxxx xxxx xx xxxx xxxx 前10位二进制为x1的二进制位串，后10位为二进制为x1的二进制位串。串形式表示的编码也称为染色体、个体

4、。x2的范围 0：00 0000 0000 00 0000 0001 4： 11 1111 11112022/7/197jiahaolai2.适应度函数为了体现染色体的适应能力，遗传算法引入了适应度函数(Fitness Function)，适应度函数决定了染色体的优劣程度，它体现了自然进化中的优胜劣汰原则。对优化问题，适应度函数就是目标函数。2022/7/198jiahaolai选择(Selection)交叉(Crossover)变异(Mutation)3. 遗传基本操作2022/7/199jiahaolai选择(Selection)选择操作也叫复制(Reproduction)操作，根据个体的

5、适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。一般地说，选择将使适应度较大(优良)个体有较大的存在机会，而适应度较小(低劣)的个体继续存在的机会也较小。简单遗传算法采用赌轮选择机制，令 表示群体的适应度值之总和， 表示群体中第i个染色体的适应度值，它产生后代的能力正好为其适应度值所占份额 2022/7/1910jiahaolai选择的原则-优胜劣汰1.轮盘赌选择(roulette wheel selection )2.随机遍历抽样(stochastic universal sampling)3.局部选择(local selection)4.截断选择(truncation sel

6、ection)5.锦标赛选择(tournament selection)2022/7/1911jiahaolai轮盘赌选择2022/7/1912jiahaolai产生初始种群计算适应度0001100000 0101111001 0000000101 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011（8） （5） （2） （10） （7）（12） （5） （19） （10） （14）2022/7/19jiahaolai13选择个体染色体适应度选择概率累积概率1000110000082010111

7、1001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111488521071251910140.08695758521071251910140.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521742022/7/19jiahaolai14选择个体染色体适应度选择概率累积概率1000110000082010111100153000000010124100111

8、010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000002022/7/19jiahaolai15选择在01之间产生一个随机数：个体染色体适应度选择概率累积概率100011

9、0000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000000.0702210.5459290.78

10、45670.4469300.5078930.2911980.7163400.2709010.3714350.854641淘汰！淘汰！2022/7/19jiahaolai16假设产生随机数序列为 0.070221，0.545929，0.784567， 0.44693， 0.507893，0.291198， 0.71634， 0.272901，0.371435， 0.854641将该随机序列与计算获得的累积概率比较，则依次序号为1，8，9，6，7，5，8，4，6，10个体被选中。显然适应度高的个体被选中的概率大，而且可能被选中；而适应度低的个体则很有可能被淘汰。在第一次生存竞争考验中，序号为2的个

11、体（0101111001）和3的个体（0000000101）被淘汰，代之以适应度较高的个体8和6,这个过程被称为再生( reproduction)。2022/7/19jiahaolai170001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011交叉0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1001110100 110000000

12、1 000101001100011110100000010110111100001011010110111100001001110100000110011101001100000001101010100010100100112022/7/19jiahaolai18交叉概率0.60.9是否进行交叉由交叉率来进行控制交叉率（记为Pc）定义为各代中交叉产生的后代数与种群中的个体数的比。显然，较高的交叉率将达到更大的解空间，从而减小停止在非最优解上的机会；但是交叉率太高，会因过多搜索不必要的解空间而耗费大量的计算时间。交叉操作是按照一定的交叉概率Pc,在配对库中随机地选取两个个体进行的,交叉的位置也是

13、随机2022/7/19jiahaolai19变异0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 000101001100011110100000010110111100001011010110111100001001010100000110011101001100000001101010100010100100110001100000 1110010110 1100000001 1001110100 10101010101110010110 100

14、1011011 1100000001 1001110100 000101001100011110100000010110111100001011010110111100001001110100000110011101001100000001101010100010100100112022/7/19jiahaolai20变异(Mutation)变异操作的简单方式是改变数码串的某个位置上的数码。先以最简单的二进制编码表示方式来说明，二进制编码表示的每一个位置的数码只有0与1这两个可能，比如对于上述二进制编码P1，随机产生一个1至12之间的数k，假如现在k=5，对从右往左的第5位进行变异操作，将原来

15、的1变为0，得到如下数码串 1110 0100 1101二进制编码表示的简单变异操作是将0与1互换：0变为1，1变为0。2022/7/19jiahaolai21变异率-不大于0.05变异可以提供初始种群中不含有的基因，或者找到选择过程中丢失的基因，为种群提供新的内容。染色体是否进行变异由变异率来进行控制。变异率（记为Pm）定义为种群中变异基因数在总基因数中的百分比。变异率控制着新基因导入种群的比例。若变异率太低，一些有用的基因就难以进入选择；若太高，即随机的变化太多，那么后代就可能失去从双亲继承下来的好特性，这样算法就会失去从过去的搜索中学习的能力。一般不大于0.05。变异操作的基本操作过程:

16、产生一个随机数rand,如果randPm,则进行变异操作2022/7/19jiahaolai22至下一代，适应度计算选择交叉变异，直至满足终止条件。遗传算法例12022/7/1923jiahaolai求一元函数求最大值优化问题: f(x)=sin(10*3.14159*x)+2.0 x-1,2(1)编码 变量x作为实数,可以视为遗传算法的表现型形式。从表现型到基因型的映射称为编码。设定求解精确到6位小数，由于区间长度为2-(-1)=3,必须将闭区间-1，2分为3106份，因为 2 097 152 = 2213106222=4 194 304所以，编码的二进制串长至少需要22位。二进制串表示-1

17、 表示2遗传算法例22022/7/1924jiahaolai（2）产生初始种群一个个体由串长为22的随机产生的二进制串组成染色体的基因码，我们可以产生一定数目的个体组成种群，种群的大小（规模）就是指种群中的个体数目（3）适应度计算考虑到本例目标函数在定义域内均大于0，而且是求函数最大值，所以直接引用目标函数作为适应度函数： f(s) = f(x)，这里二进制串s对应变量x的值2022/7/1925jiahaolai适应度计算例如，三个个体的二进制串为： s1= s2= s3=分别对应于变量值 x1=0.637197,x2=-0.958973,x3=1.627888个体的适应度计算如下 f(s1

18、)=f(x1)=2.586345 f(s2)=f(x2)=1.078878 f(s3)=f(x3)=3.250650显然，x3为最佳个体2022/7/1926jiahaolai（4）遗传操作-交叉下面是经过选择操作(轮盘赌选择方法)的两个个体，首先执行单点交叉s2=s3=随即选择一个交叉点，例如第五位与第六位之间的位置，交叉后产生新的个体 new_s2= new_s3=相应的个体的适应度分别为 f(new_s2) = f(-0.998113) = 1.940865 f(new_s3) = f(1.666028) = 3.459245个体new_s3的适应度比两个父个体适应度高2022/7/19

19、27jiahaolai变异操作假设已经以小概率选择了s3的第5个遗传因子(即第5位)变异,遗传因子由原来的0变为1,产生新的个体 s3=相应的适应度为 f(s3) = f(1.721638) = 0.917743比父个体的适应度下降了。2022/7/1928jiahaolai变异操作但如果选择第10个遗传因子变异，产生新的个体 s3= f(s3) = f(1.630818) = 3.343555发现个体s3的适应度比父个体的适应度改善了，说明了变异操作的扰动作用2022/7/1929jiahaolai(5)模拟结果设定种群大小为50,交叉概率pc=0.25,变异概率pm=0.01,按照上述基本

20、遗传算法,在运行到89代时获得最佳个体: Smax= xs=1.850549, f(xs)=3.850274表1给出了模拟世代的种群中的最佳个体的演变情况2022/7/1930jiahaolai2022/7/1931jiahaolai遗传算法的特点(1)遗传算法是对参数集合的编码而非针对参数本身进行进化；(2)遗传算法是从问题解的编码组开始而非从单个解开始搜索；(3)遗传算法利用目标函数的适应度这一信息而非利用导数或其他辅助信息来指导搜索；(4)遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。2022/7/1932jiahaolai遗传算法的求解步骤(l)随机产生一个由确定

21、长度的特征字符串组成的初始群体。(2)对该字符串群体迭代地执行下面的步骤和，直到满足停止标准： 计算群体中每个个体字符串的适应值； 应用复制、交叉和变异等遗传算子产生下一代群体。(3)把在后代中出现的最好的个体字符串指定为遗传算法的执行结果，这个结果可以表示问题的一个解。(4)算法的停止条件最简单的有如下两种：完成了预先给定的进化代数则停止；群体中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。2022/7/1933jiahaolai2022/7/19jiahaolai342022/7/19jiahaolai352022/7/19jiahaolai362022/7/1

22、9jiahaolai372022/7/19jiahaolai38通过繁殖过程, 产生新一代群体, 将新群体与父代合并, 组成一个大群体. 为避免父代中优质的串在遗传操作中丢掉, 直接用父代最好的串取代子代中最差的串, 使优质父串得以保留种群代换2022/7/19jiahaolai39 通过选种、杂交、突变等多次GA 操作, 各代群体的优良基因成分逐渐积累, 群体平均适应度和最优个体适应度不断上升, 迭代过程趋于收敛. 判定收敛条件可以根据最大代数, 或以连续几代平均适应度之差小于给定值作为收敛条件.获得最优解2022/7/19jiahaolai405.6.2 禁忌搜索 Tabu Search

23、2022/7/1941jiahaolai禁忌搜索概述2022/7/1942jiahaolai算法的提出 禁忌搜索（Tabu search）是局部邻域搜索算法的推广，Fred Glover在1986年提出这个概念，进而形成一套完整算法。算法的特点 禁忌禁止重复前面的工作。 跳出局部最优点。 它是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。/glover/禁忌搜索概述TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。相对于模拟退火和遗传算法，TS是又一种搜索特点不

24、同的算法。迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。2022/7/1943jiahaolaiTabu Search特点Neighborhood search + memoryNeighborhood searchMemory Record the search historyForbid cycling search2022/7/1944jiahaolai3的邻域搜索陷入循环1的邻域12的邻域24的邻域43在邻域中找到最好的解2022/7/1945jiahaolai加入禁忌表，避免陷入

25、循环禁忌表长度为3：, , 规则：不得接受与禁忌表中相同的解禁忌表的变化：第一步搜索时 第二步搜索时 第三步搜索时, , 第四步搜索时, , 2022/7/1946jiahaolai避免循环的原理：当前解为时，其邻域中最好的解为，原本下一步应为，但其与禁忌表中的元素相同，所以选择次好的解，从而避免死循环1的邻域12的邻域24的邻域4352022/7/1947jiahaolai禁忌表的更新更新原则：先进先出, , , , , , .2022/7/1948jiahaolai禁忌表中元素禁忌表中元素的可以是完整的解，可以是完整解的一部分，也可以是采取的一个生成相邻解的动作等等完整解：12345,13

26、245,31245生成相邻解的操作（如交换的动作）： 32, 31 从12345开始，取3出来，插入1245每个位置前面2022/7/1949jiahaolai禁忌表长度太短：计算速度快，但容易陷入死循环太长：计算速度慢在搜索过程中，禁忌表长度设为固定在搜索过程中，禁忌表长度可动态变化禁忌表长度：5102022/7/1950jiahaolai藐视准则（Aspiration criterion）如果找到了一个新的解比当前记录的最好解还要好，那么即使当前得到这个新的解被tabu list禁止，仍然接受这个新的解，并更新tabu list. 即tabu list对这个解没有禁止作用假设记录生成相邻解

27、的方法，Tabu list = , , ,下一步采用方法生成了迄今为止最好的解，仍然接受这个，更新Tabu list=, , ,2022/7/1951jiahaolai分散搜索（Diversification）和 集中搜索（Intensification）策略分散搜索：是为了对整个解的空间进行更广泛的覆盖，而不是仅仅局限在某个局部的区域。无邻域的搜索有邻域的搜索有邻域的搜索 &分散搜索策略2022/7/1952jiahaolai分散搜索（Diversification）和 集中搜索（Intensification）策略集中搜索：如果当前搜索区域内发现了比较好的解，如果进一步对当前区域进行更集中

28、的搜索，那么可能会发现更多更好的解。2022/7/1953jiahaolai分散搜索策略（Diversification strategy）在当前搜索区域内进行了一定次数的搜索了之后（如25次），若不能发现更好的解，那么就执行分散搜索策略。把tabu list清空，然后从一个新的初始解开始搜索。集中搜索：如果最好解的记录被更新，那么就执行集中搜索策略，即清空tabu list. 这样可以在当前区域进行更自由的搜索。2022/7/1954jiahaolai要设计一个禁忌搜索算法，需要确定以下环节1)初始解和适配值函数（目标函数）；2)邻域结构(如何生成相邻解)和禁忌对象(禁忌表中的元素)；3)候选解选择；4)禁忌表及其长度；5)藐视准则6)集中搜索和分散搜索策略7)终止准则。 2022/7/1955jiahaolai2022/7/19jiahaolai56四城市非对称TSP问题 第1步 解的形式 禁忌对象及长度 候选解 f(x0)=4ABCDBCDABC对换评价值CD4.5BC7.5BD82022/7/19jiahaolai57 此处评价值为目标值，即从A出发并返回A的一个TSP回路的长度.由于假设了A 城市为始