8智能优化方法讲解

工程优化的发展历程工程优化的发展历程传统优化往往只适传统优化往往只适用于简单零部件，用于简单零部件，广义优化把对象由广义优化把对象由此扩展到复杂零部此扩展到复杂零部件、整机、系列产件、整机、系列产品和组合产品的整品和组合产品的整体优化，可统称为体优化，可统称为全系统优化。全系统优化。传统优化往往只侧重于某传统优化往往只侧重于某一方面性能的优化，处理一方面性能的优化，处理不同类性能时一般分先后不同类性能时一般分先后而优之。广义优化把优化而优之。广义优化把优化准则由某方面性能扩展到准则由某方面性能扩展到各方面性能，要实现技术各方面性能，要实现技术性、经济性和社会性的综性、经济性和社会性的综合评估和优化。合评估和优化。传统优化往往局限传统优化往往局限于产品技术设计阶于产品技术设计阶段的优化，广义优段的优化，广义优化则把优化的范围化则把优化的范围扩展到包含功能、扩展到包含功能、原理方案和原理参原理方案和原理参数、结构方案、结数、结构方案、结构参数、结构形状构参数、结构形状和公差优化的全设和公差优化的全设计过程，进而面向计过程，进而面向制造、经销、使用制造、经销、使用和用后处置的寿命和用后处置的寿命周期设计过程。周期设计过程。传统优化的搜索策略以数学规划方法为主，对模型传统优化的搜索策略以数学规划方法为主，对模型数学形态的要求苛刻。广义优化设计注重开发、综数学形态的要求苛刻。广义优化设计注重开发、综合运用人类智能、人工智能和各种数学工具的新一合运用人类智能、人工智能和各种数学工具的新一代搜索策略，处理大规模复杂形态模型的能力显著代搜索策略，处理大规模复杂形态模型的能力显著提高，从而为全系统、全性能和全寿命周期优化模提高，从而为全系统、全性能和全寿命周期优化模型的综合求解提供了可能。型的综合求解提供了可能。传统优化一般是单学传统优化一般是单学科、单方面性能、单科、单方面性能、单计算机串行优化的过计算机串行优化的过程，不但费时，而且程，不但费时，而且难以得到综合优化解。难以得到综合优化解。广义优化实现了多学广义优化实现了多学科、多方面性能、多科、多方面性能、多计算机分布式并行协计算机分布式并行协同优化同优化,以追求综合优以追求综合优化解。化解。现代优化设计方法现代优化设计方法常用现代优化方法常用现代优化方法生物进化生物进化遗传算法遗传算法关键技术关键技术对设计变量进行离散化处理，得出每一个分量对设计变量进行离散化处理，得出每一个分量的离散值和离散值个数：的离散值和离散值个数：()(1)(2),1,2,imiiiixxxxin2intlog 1iibm对每一个设计变量进行对每一个设计变量进行编码编码：将所有设计变量将所有设计变量编码编码按顺序排列在一起，变形成按顺序排列在一起，变形成一个染色体。染色体长度为一个染色体。染色体长度为1niiLb11232 xzXxmxb主动轮齿数两齿轮模数从动轮齿宽2 2.5 3 4 5 6 810m取，共8个离散值，采用3位二进制码210300.1201b，精确到，故共有个离散值，采用8位二进制码11749z 取值为，共32个离散值，采用5位二进制码24,3,24.4TX 2211min (,)()max(0,()()pqjkjkp X rf XrgXrhXmin ().()0 1,2,()0 1,2,njkf XXRstgXjphXkqnmax ()1/()F XCp XNY遗传算法实现遗传算法实现Holland(1975)的模式理论的模式理论模式：具有部分相同字符的字符串组合模式：具有部分相同字符的字符串组合如模式：如模式：0*10 表示表示 0010,0110()(,)()(,1)(,)1(1)()1o scmu s td sE m s tm s tppf tlNumber of instance ofschema s at time tAverage fitness ofindividuals in schema s at time tProbabilityof mutationNumber ofdefined bitsin schema sProbabilityof crossoverDistance betweendefined bits in s父辈群体父辈群体个体编码个体编码个体译码个体译码适应度值适应度值jjiixxxP)(Fitness)(Fitnessselect 子辈群体子辈群体1个体编码个体编码个体译码个体译码适应度值适应度值随机选取一对染色体随机选取一对染色体随机选择交叉位置随机选择交叉位置子辈群体子辈群体1个体编码个体编码交换后部基因串交换后部基因串子辈群体子辈群体2个体编码个体编码随机选取一个染色体随机选取一个染色体随机选择变异位置随机选择变异位置子辈群体子辈群体2个体编码个体编码对基因进行变异对基因进行变异子辈群体子辈群体3个体编码个体编码第三节第三节 蚁群算法蚁群算法(Ant colony algorithm)Ant colony algorithm)1991年，年，Mdorigo等人首先开始了对蚁群行等人首先开始了对蚁群行为进行研究。深入考察了相对弱小，功能为进行研究。深入考察了相对弱小，功能并不强大的个体是如何完成复杂的工作的并不强大的个体是如何完成复杂的工作的(如寻找到食物的最佳路径并返回等如寻找到食物的最佳路径并返回等)。在此。在此基础上形成了一种很好的优化算法。特别基础上形成了一种很好的优化算法。特别是对于离散规划问题更为有效。是对于离散规划问题更为有效。研究中发现，蚂蚁在行进中会沿途留下一种叫信息素的挥发研究中发现，蚂蚁在行进中会沿途留下一种叫信息素的挥发性物质，其他蚂蚁能根据这种物质浓度的大小选择路径前进，性物质，其他蚂蚁能根据这种物质浓度的大小选择路径前进，并且沿途又留下这种信息素，使这种浓度加强，于是又吸引并且沿途又留下这种信息素，使这种浓度加强，于是又吸引更多的蚂蚁沿此路前进。在一段时间后，较短路径上信息素更多的蚂蚁沿此路前进。在一段时间后，较短路径上信息素由于挥发的少，同时访问的蚂蚁多，使其浓度远远超过较长由于挥发的少，同时访问的蚂蚁多，使其浓度远远超过较长路径上的信息素，此过程持续进行，直到所有蚂蚁都选择最路径上的信息素，此过程持续进行，直到所有蚂蚁都选择最短路径为止。受此启发而提出的短路径为止。受此启发而提出的ACA，能通过功能相对简单，能通过功能相对简单的人工蚂蚁之间的协作，解决复杂的问题。的人工蚂蚁之间的协作，解决复杂的问题。1.概述概述 基于蚂蚁觅食建立最短路径的机理，是一种自然算法；基于蚂蚁觅食建立最短路径的机理，是一种自然算法；具有本质并行性。所有蚂蚁独立、无监督的同时搜索解具有本质并行性。所有蚂蚁独立、无监督的同时搜索解空间中许多点而不是一个点，因而能够快速全局收敛；空间中许多点而不是一个点，因而能够快速全局收敛；协同工作机制。蚂蚁选择路径时，根据以前蚂蚁留下的协同工作机制。蚂蚁选择路径时，根据以前蚂蚁留下的信息素进行搜索，能以很大的概率找到优化问题的最优信息素进行搜索，能以很大的概率找到优化问题的最优解；解；鲁棒性。使用概率规则而不是确定性规则指导搜索，不鲁棒性。使用概率规则而不是确定性规则指导搜索，不必知道其他辅助信息，有极好的鲁棒性和广泛的适应性；必知道其他辅助信息，有极好的鲁棒性和广泛的适应性；易于与其他启发式算法结合，以改进算法的性能。易于与其他启发式算法结合，以改进算法的性能。2.蚁群算法的特点蚁群算法的特点3.3.人工蚁群算法原理人工蚁群算法原理v蚂蚁在寻找食物源时，能在其走过的路径上释放一种蚂蚁蚂蚁在寻找食物源时，能在其走过的路径上释放一种蚂蚁特有的分泌物特有的分泌物信息素；信息素；v蚂蚁在运动过程中能够感知信息素的存在及其强度，并以蚂蚁在运动过程中能够感知信息素的存在及其强度，并以此指导自己的运动方向，使蚂蚁倾向于朝着该物质强度高此指导自己的运动方向，使蚂蚁倾向于朝着该物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象；表现出一种信息正反馈现象；v某一路径上走过的蚂蚁越多，则后来者选择该路径的概率某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大，蚂蚁这种选择路径的过程被称之为蚂蚁的自催化就越大，蚂蚁这种选择路径的过程被称之为蚂蚁的自催化行为，也可将蚂蚁行为理解成所谓的增强型学习系统。行为，也可将蚂蚁行为理解成所谓的增强型学习系统。现以旅行商现以旅行商(Traveling Salesman Problem)问题的求解为例说问题的求解为例说明蚁群系统模型。明蚁群系统模型。4.4.人工蚁群系统模型及算法实现人工蚁群系统模型及算法实现TSP:一个商人欲到一个商人欲到n个城市推销商品，每两个城市个城市推销商品，每两个城市i和和j间的间的距离为距离为dij，如何选择一条道路，使得商人每个城市走，如何选择一条道路，使得商人每个城市走一遍后回到起点，且所走路径最短。一遍后回到起点，且所走路径最短。计变量计变量xij :当商人选择走当商人选择走城市城市i和和j间的间的距离时距离时xij1；当商人不选择当商人不选择走城市走城市i和和j间间的距离时的距离时xij0。11,min.1,1,2,1,1,2,1,22,1,2,0,1,1,2,ijijijnijjnijiiji j Sijd xstxinxinxSSnSnxin ij由城市由城市i出发出发1次次TSP的数学模型：的数学模型：进入城市进入城市j1次次在城市子集中在城市子集中不形成回路不形成回路m蚁群中蚂蚁的数量蚁群中蚂蚁的数量;dij两城市两城市i i和和j j之间距离之间距离;bi(t)t时刻位于城市时刻位于城市i的蚂蚁的个数的蚂蚁的个数,m=ni=1=1 bi(t);ij(t)t时刻边弧时刻边弧(i,j)的轨迹强度的轨迹强度(即即ij连线上残留的信连线上残留的信息量息量)，且设，且设ij(0)=C(C=C(C为常数为常数)，i,j=0,1,=0,1,n-1;-1;ij(t)t时刻边弧时刻边弧(i,j)的能见度，反映由城市的能见度，反映由城市i转移到转移到城市城市j的期望程度；的期望程度；首先引进如下记号首先引进如下记号:蚂蚁蚂蚁k(k=1,2,m)在运动过程中根据各条路径上的信息在运动过程中根据各条路径上的信息量决定转移方向。与真实蚁群系统不同，人工蚁群系统量决定转移方向。与真实蚁群系统不同，人工蚁群系统具有一定的记忆功能，随着时间的推移，以前留下的信具有一定的记忆功能，随着时间的推移，以前留下的信息逐渐消逝，经息逐渐消逝，经n个时刻，蚂蚁完成一次循环，各路径个时刻，蚂蚁完成一次循环，各路径上信息量要作调整。由此得到下述的人工蚁群系统模型上信息量要作调整。由此得到下述的人工蚁群系统模型:5.5.蚁群算法步骤蚁群算法步骤1)设人工蚁群在并行地搜索设人工蚁群在并行地搜索TSP的解，并通过一种信息素做的解，并通过一种信息素做媒介相互通信，在每个结点上且和该结点相连的边的长度媒介相互通信，在每个结点上且和该结点相连的边的长度以信息素量做搜索下一结点的试探依据，直到找到一个以信息素量做搜索下一结点的试探依据，直到找到一个TSP的可行解。的可行解。2)在时刻在时刻t人工蚁人工蚁k由位置由位置i 转移至位置转移至位置j(即从一个结点转移到下即从一个结点转移到下一个结点一个结点)的转移概率为的转移概率为pkij(t)=ij(t)ij(t)sSis(t)is(t),sS0,s S 其中参数其中参数轨迹的相对重要性轨迹的相对重要性(0);能见度的相对重要性能见度的相对重要性(0);S可行顶点集，即蚂蚁可行顶点集，即蚂蚁k下一步允许选择的城市。下一步允许选择的城市。,分别反映了蚂蚁在运动过程中所积累的信息及启发式因子分别反映了蚂蚁在运动过程中所积累的信息及启发式因子在蚂蚁选择路径中所起的不同作用。在蚂蚁选择路径中所起的不同作用。3)3)当当m个人工蚁按个人工蚁按(1)(1)式找到了可行解，则将各边的信式找到了可行解，则将各边的信息量用下式修改，即调整信息量的轨迹强度，更新息量用下式修改，即调整信息量的轨迹强度，更新方程为方程为 ijij(t+n)=.ij(t)+(t+n)=.ij(t)+ijij,(0,1),(0,1)ij=mk=1ij=mk=1kijkij其中其中kijkij第第k k只蚂蚁在本次循环中留在路径只蚂蚁在本次循环中留在路径(i,j)(i,j)上的信息量上的信息量;ijij本次循环中路径本次循环中路径ijij上上的信息量的增量的信息量的增量;参数参数轨迹的持久性轨迹的持久性;1-;1-轨迹衰减度轨迹衰减度,表示信息消逝程度表示信息消逝程度.对上述系统模型对上述系统模型,采用人工蚁群方法求解的算法步骤可归结为采用人工蚁群方法求解的算法步骤可归结为:Step1:NC0(NCStep1:NC0(NC为迭代步数或搜索次数为迭代步数或搜索次数)；各；各ij和和ij的初始的初始化；将化；将m个蚂蚁置于个蚂蚁置于n个顶点上；个顶点上；Step2:Step2:将各蚂蚁的初始出发点置于当前解集中；对每个蚂蚁将各蚂蚁的初始出发点置于当前解集中；对每个蚂蚁k(k=1,=1,m)按概率按概率p pkij移至下一顶点移至下一顶点j j；将顶点；将顶点j j置于当置于当前解集；前解集；Step3:Step3:计算各蚂蚁的目标函数值计算各蚂蚁的目标函数值z zk(k=1,(k=1,m),m)，记录当前的最，记录当前的最好解；好解；Step4:Step4:按更新方程修改轨迹强度；按更新方程修改轨迹强度；Step5:Step5:对各边弧对各边弧(i，j)(即路径即路径ij)，置，置ij00；NCNC+1.NCNC+1.Step6:Step6:若若NCNC预定的迭代次数且无退化行为预定的迭代次数且无退化行为(即找到的都是相即找到的都是相同解同解),),则转则转Step2.Step2.6.6.蚁群算法框图蚁群算法框图iixwz)(zf1()()niiiyf zfw xF(x)x011 0()0 0 xf xxF(x)x011/21()1 exp()f xx层状结构层状结构同层单元间无信息交流同层单元间无信息交流信息向前传递信息向前传递环状结构环状结构单元间皆有信息交流单元间皆有信息交流信息多向传递信息多向传递单层前向网络单层前向网络多层前向网络多层前向网络线性前向网络线性前向网络非线性前向网络非线性前向网络连续型反馈网络连续型反馈网络离散型反馈网络离散型反馈网络单层前向网络单层前向网络单层前向网络单层前向网络(,)zf W V X1inx1xixn1jmkzkw11w1jw1mvijvjvmwnm1z1rzrvj11(1)(1)(1)(1)12(1)(1)11(1)2(1)1(1)0,()()()()()TnniiiniiininiiYyyyF WXfw xfw xF Zfw x1inx1xixn1jn1w(1)11y1yjyn1w(1)1n1w(1)1jw(1)nn1w(1)n1w(1)i11111()()()()12(1)(1)()(1)11()(1)2()1()(1)0,()()()()()kkkkTkkkknknkkiiinkkiikinkkiniiYyyyF WYfwyfwyF Zfwy1ink-1yk-111jnkw(k)11w(k)1n1w(k)1jw(k)nn1w(k)n1w(k)i1yk-1iyk-1nk-1ykjyk1yknk1112()()()(),knkTnTkKKKDd ddYyyy设为理想输出，为实际输出()()min ()()()kTkF WDYDY学习的原则是：确定所有的权系数，使0minzz1inx1xixn1jmrzw11w1jw1mv1vjvmwnm(,)zf W V X1inx1(t)xi(t)xn(t)1inw11w1jw1nwnnx1(t+1)xi(+1 t)xn(t+1)t t t2211 E(,)()max(0,()()pqjkjkX rf XrgXrhXmin ().()0 1,2,()0 1,2,njkf XXRstgXjphXkqn(0)(,)()(0)ikidxE X rtdtxXX 谢谢谢谢!