智能优化方法详解课件

1、第七章 现代优化方法第二节 遗传算法第三节 蚁群算法第四节 基于神经网络的优化方法第一节 绪论1.现代机械产品的系统性,综合性、复杂性和规模化导致设计模型的横向扩展.例如,由零件的优化发展到部件,整机、系列和组合产品的优化,由单学科领域的优化发展到机、液、光、电、信息的集成优化；2.对产品寿命周期优化的市场需求导致设计模型的纵向扩展,例如从功能优化、原理方案设计优化到技术设计优化;从性能参数优化、结构参数优化到面向制造的优化;从设计参数优化到加工方案和工艺参数,也即的优化;最终直至考虑产品可装配性、可使用性,可维修性和可回用性等的全寿命周期优化；3. 对产品的要求由技术性扩展到经济性和社会性,

2、导致基于全性能的多目标优化。第一节 绪论广义优化设计方法产生的背景工程优化的发展历程传统优化往往只适用于简单零部件，广义优化把对象由此扩展到复杂零部件、整机、系列产品和组合产品的整体优化，可统称为全系统优化。现代优化是全系统优化传统优化往往只侧重于某一方面性能的优化，处理不同类性能时一般分先后而优之。广义优化把优化准则由某方面性能扩展到各方面性能，要实现技术性、经济性和社会性的综合评估和优化。现代优化是全性能协调优化传统优化往往局限于产品技术设计阶段的优化，广义优化则把优化的范围扩展到包含功能、原理方案和原理参数、结构方案、结构参数、结构形状和公差优化的全设计过程，进而面向制造、经销、使用和用

3、后处置的寿命周期设计过程。现代优化是全设计过程优化传统优化的搜索策略以数学规划方法为主，对模型数学形态的要求苛刻。广义优化设计注重开发、综合运用人类智能、人工智能和各种数学工具的新一代搜索策略，处理大规模复杂形态模型的能力显著提高，从而为全系统、全性能和全寿命周期优化模型的综合求解提供了可能。现代优化是智能优化传统优化一般是单学科、单方面性能、单计算机串行优化的过程，不但费时，而且难以得到综合优化解。广义优化实现了多学科、多方面性能、多计算机分布式并行协同优化,以追求综合优化解。现代优化是多学科优化 航天、航空、通讯设备等的快速发展，提出了大量的复杂优化设计问题，为现代优化方法的产生提供了动力

4、。 生物技术、并行计算技术和人工智能技术以及商用软件等的发展为现代优化方法提供了技术支撑。现代优化设计方法遗传算法神经网络拓扑优化蚁群算法模拟退火混沌优化禁忌算法常用现代优化方法遗传算法(Genetic Algorithm) 是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是自然遗传学和计算机科学相互结合与渗透而形成的新的计算方法。 该方法最早是由美国Michigan大学的Holland教授于1975年提出。生物进化遗传算法基因染色体种群环境适应性进化字符字符串解集目标函数值算子关键技术编码适应度遗传算子第二节 遗传算法遗传算法的二进制编码过程对设计变量进行离散化处理，得出每一个分量

5、的离散值和离散值个数：确定每一个设计变量的编码长度 (二进制位数)：对每一个设计变量进行编码：将所有设计变量编码按顺序排列在一起，变形成一个染色体。染色体长度为二进制编码选例在直齿圆柱齿轮减速器优化设计中，设计变量为： 0 0 1 1 1 0 1 0 1 0 0 0 1 1 1 1 适应度函数的确定遗传算子选择(Selection)交叉(Crossover)变异(Mutation)移民(Immigrant)遗传算子遗传算法的流程框图开 始输入种群数、交叉概率、变异概率随机产生一组初始种群依据个体的适应度，随机进行选择依据交叉概率，随机进行交叉依据变异概率，随机进行变异达到进化代数NY结 束确定

6、种群规模n（一般=40-300) 、交叉概率pc（0.6到1.0之间)、交叉概率pm（0.001到0.01之间) 和迭代代数，令k=0；随机产生的一组初始种群；计算种群中每个解(个体)相应的目标函数值(适应度)，按每个个体的适应度占种群适应度的百分数分配选择率；在所有个体中，选出适应度较大的个个体(有些个体是重复的)，这个过程称为选择；在选择后的种群中，按交叉概率随机选取一对个体，进行交叉运算，产生一对新的个体，重复该过程；在交叉后的种群中，按变异概率随机选取一个个体，进行变异运算，产生一个新的个体，重复该过程；K=k+1，若达到预定的迭代代数，则将种群中适应度最大的个体作为最优解输出，停止迭

7、代；否则，转(3)。遗传算法实现遗传算法收敛判据达到规定迭代的次数;设定连续几次得到的解群中最好的解没有变化;解群中最好的解的适应值与平均值之差占平均适应值的百分数小于某一设定值.遗传算法理论研究Holland (1975)的模式理论模式：具有部分相同字符的字符串组合如模式： 0*10 表示 0010, 0110Number of instance ofschema s at time tAverage fitness ofindividuals in schema s at time tProbabilityof mutationNumber ofdefined bitsin schema

8、sProbabilityof crossoverDistance betweendefined bits in s选择算子父辈群体个体编码个体译码适应度值10100111001101011101010100111111011011011010011030, 5, 25.7645.711101100001101001111110001001110.19, 4, 21.028, 6, 22.539, 7, 25.027, 3, 24.5735.1545.1724.4656.9父辈群体为选择算子与运算对象，作为选择池。10100111001101011001010100111011110101010

9、0111111110101010011111111010101001111111010011100110101101001110011010110100111001101011010011100110101子辈群体1个体编码个体译码适应度值1010011100110101011011011010011030, 5, 25.7645.711101100001101001101010100111111.19, 4, 21.028, 6, 22.527, 3, 24.527, 3, 24.5735.1545.1724.4735.11101010100111111选择算子执行过程交叉算子执行过程011

10、0110101110111随机选取一对染色体1110110100101010随机选择交叉位置01101101011101111110110100101010子辈群体1个体编码1010011100110101111011010010101001101101011101111110111000110000.交换后部基因串子辈群体2个体编码11101101011101110110110100101010.各种交叉算子1010011100110101随机选取一个染色体随机选择变异位置1010011100110101子辈群体2个体编码11100011001101110101011100111000101

11、0011100110101111000111000101.对基因进行变异变异算子执行过程子辈群体3个体编码1010011100110111.第三节 蚁群算法(Ant colony algorithm)1991年，Mdorigo等人首先开始了对蚁群行为进行研究。深入考察了相对弱小，功能并不强大的个体是如何完成复杂的工作的(如寻找到食物的最佳路径并返回等)。在此基础上形成了一种很好的优化算法。特别是对于离散规划问题更为有效。研究中发现，蚂蚁在行进中会沿途留下一种叫信息素的挥发性物质，其他蚂蚁能根据这种物质浓度的大小选择路径前进，并且沿途又留下这种信息素，使这种浓度加强，于是又吸引更多的蚂蚁沿此路前

12、进。在一段时间后，较短路径上信息素由于挥发的少，同时访问的蚂蚁多，使其浓度远远超过较长路径上的信息素，此过程持续进行，直到所有蚂蚁都选择最短路径为止。受此启发而提出的ACA，能通过功能相对简单的人工蚂蚁之间的协作，解决复杂的问题。1. 概述 基于蚂蚁觅食建立最短路径的机理，是一种自然算法；具有本质并行性。所有蚂蚁独立、无监督的同时搜索解空间中许多点而不是一个点，因而能够快速全局收敛；协同工作机制。蚂蚁选择路径时，根据以前蚂蚁留下的信息素进行搜索，能以很大的概率找到优化问题的最优解；鲁棒性。使用概率规则而不是确定性规则指导搜索，不必知道其他辅助信息，有极好的鲁棒性和广泛的适应性；易于与其他启发式

13、算法结合，以改进算法的性能。2. 蚁群算法的特点3. 人工蚁群算法原理蚂蚁在寻找食物源时，能在其走过的路径上释放一种蚂蚁特有的分泌物信息素；蚂蚁在运动过程中能够感知信息素的存在及其强度，并以此指导自己的运动方向，使蚂蚁倾向于朝着该物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象；某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大，蚂蚁这种选择路径的过程被称之为蚂蚁的自催化行为，也可将蚂蚁行为理解成所谓的增强型学习系统。现以旅行商(Traveling Salesman Problem)问题的求解为例说明蚁群系统模型。4. 人工蚁群系统模型及算法实现TSP

14、: 一个商人欲到n个城市推销商品，每两个城市i和j间的距离为dij，如何选择一条道路，使得商人每个城市走一遍后回到起点，且所走路径最短。计变量xij : 当商人选择走城市i和j间的距离时xij1； 当商人不选择走城市i和j间的距离时xij0。由城市i出发1次TSP的数学模型：进入城市j1次在城市子集中不形成回路m蚁群中蚂蚁的数量;dij两城市i和j之间距离;bi(t)t时刻位于城市i的蚂蚁的个数,m=ni=1 bi(t) ;ij(t)t时刻边弧(i,j)的轨迹强度(即ij连线上残留的信息量)，且设ij(0) =C(C为常数)，i,j=0,1,n-1; ij(t)t时刻边弧(i,j)的能见度，反

15、映由城市i转移到城市j的期望程度；首先引进如下记号:蚂蚁k(k=1,2,m)在运动过程中根据各条路径上的信息量决定转移方向。与真实蚁群系统不同，人工蚁群系统具有一定的记忆功能，随着时间的推移，以前留下的信息逐渐消逝，经n个时刻，蚂蚁完成一次循环，各路径上信息量要作调整。由此得到下述的人工蚁群系统模型:5. 蚁群算法步骤设人工蚁群在并行地搜索TSP的解，并通过一种信息素做媒介相互通信，在每个结点上且和该结点相连的边的长度以信息素量做搜索下一结点的试探依据，直到找到一个TSP的可行解。在时刻t人工蚁k由位置i 转移至位置j (即从一个结点转移到下一个结点)的转移概率为pkij(t)=ij(t)ij

16、(t)sSis(t)is(t),sS0,s S 其中参数轨迹的相对重要性( 0); 能见度的相对重要性( 0); S可行顶点集，即蚂蚁k下一步允许选择的城市。,分别反映了蚂蚁在运动过程中所积累的信息及启发式因子在蚂蚁选择路径中所起的不同作用。当m个人工蚁按(1)式找到了可行解，则将各边的信息量用下式修改，即调整信息量的轨迹强度，更新方程为 ij(t+n)=.ij(t)+ij,(0,1) ij=mk=1kij其中kij第k只蚂蚁在本次循环中留在路径(i,j)上的信息量;ij本次循环中路径ij上的信息量的增量;参数轨迹的持久性;1-轨迹衰减度,表示信息消逝程度.对上述系统模型,采用人工蚁群方法求解

17、的算法步骤可归结为:Step1: NC0(NC为迭代步数或搜索次数)；各ij和ij的初始化；将m个蚂蚁置于n个顶点上；Step2: 将各蚂蚁的初始出发点置于当前解集中；对每个蚂蚁k(k=1,m)按概率pkij移至下一顶点j；将顶点j置于当前解集；Step3: 计算各蚂蚁的目标函数值zk(k=1,m)，记录当前的最好解；Step4: 按更新方程修改轨迹强度；Step5: 对各边弧(i，j)(即路径ij)，置ij0；NCNC+1.Step6: 若NC预定的迭代次数且无退化行为(即找到的都是相同解),则转Step2.6. 蚁群算法框图 人工神经网络(Artificial Neural Network

18、s)的早期工作可以追溯到1943年McCulloch和 Pitts建立的第一个用于分类的认知模型。20世纪80年代，Hopfield将人工神经网络成功地应用在组合优化问题。 人工神经网络模型是基于生物学中的神经网络的基本原理而建立的。生物学中的神经网络简图如下：第四节 基于神经网络的优化方法人工神经元x1x2xnw1w2wny轴突突触晶枝内核 轴突输入输出称为阈值转移函数或输出函数其中F(x)x01F(x)x011/2常用转移函数符号函数S形函数神经网络的工作原理神经网络训练过程：神经网络工作过程：输入自变量值神经网络模型确定权系数输出因变量值输出因变量值与预期输出比较调整权系数输入自变量值神经网络模型确定权系数 常用网络模型 前向网络 反馈网络层状结构同层单元间无信息交流信息向前传递环状结构单元间