《目标规划与遗传算法优秀PPT.ppt》由会员分享，可在线阅读，更多相关《目标规划与遗传算法优秀PPT.ppt（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、目标规划与遗传算法现在学习的是第1页，共42页一、多目标规划现在学习的是第2页，共42页多目标规划是在一组刚性约束条件下，以多个柔性条件为目标函数的一种规划问题。为了能够同时达到多个目标的优化，往往是很难做到的。因为，目标函数是相互冲突的，一个目标的更优是要牺牲其他目标作为代价的。有效解（非劣解、Pareto解）在不牺牲其他目标函数的前提下，不能再改进任何一个目标函数值的可行解。现在学习的是第3页，共42页求解方法;1、权重和方法：每个目标函数分配权重并将其组合成为一个目标函数 权重的选择原则：使每个目标在加权后的地位相当。比如：一个目标表示利润，另一个目标表示效率，两者相差 因此，权重应取相
2、当数量级。现在学习的是第4页，共42页 2、妥协方法：是一种根据距离函数进行目标搜索行为的数学表达。设 表示是第i个目标在不考虑其他目标时的最优值。现在学习的是第5页，共42页例 最小费用最大流现在学习的是第6页，共42页网络最大流中不涉及费用问题，在实际问题中，在网络中的各边的运输费用是各不相同的，在满足最大流的情况下，求出最小费用，就是最小费用最大流问题。下图所示是最小费用最大流问题。每一条边上有两个数字，前者表示容量，后者表示单位费用。现在学习的是第7页，共42页 设 是定义在网络图G的边集E上的一个实数函数，表示i-j运输量及最大量。设 是定义在网络图G的边集E上的一个实数函数，表示i
3、-j运输的运费。满足：现在学习的是第8页，共42页（1）-每条边的流量不超过该边大弧容量。（2）-中间点流入与流出平衡。现在学习的是第9页，共42页（3）-发点总流出与收点总流入平衡。其数学模型：-由发点1到其它点的流出量总和。N表示收点.现在学习的是第10页，共42页-由发点1到其它点的费用总和。N表示收点.现在学习的是第11页，共42页二、目标规划目标规划是多目标优化的一种妥协模型，其特点是，每一个目标都有一个理想目标值，目标规划的目的是极小化各目标函数与理想目标值的正、负偏差。在目标之间，根据其重要性的不同，建立一个优先结构是非常必要的。即根据决策者的偏好对所有目标进行排序。现在学习的是
4、第12页，共42页数学模型:现在学习的是第13页，共42页解释:为优化因子,表示各目标的相对重要性为优先级j的第i个目标正、负偏差的权因子;为目标I偏离目标值的正、负偏差；N维决策变量；为目标约束，软性条件现在学习的是第14页，共42页系统约束，刚性条件第i个目标值优先级个数，目标约束个数，系统约束个数。目标函数另一种表示：表示按字典序极小化目标向量现在学习的是第15页，共42页续例 最小费用最大流在没有考虑费用的前提下,最大流显然是11.要完成最大流的费用的最小值是180.现在的问题:如何用最小的费用,完成最大流(至少5以上)?现在学习的是第16页，共42页(1)第一目标是费用S,理想值为1
5、80.越大越好.极大化现在学习的是第17页，共42页（2）第二目标是流量，至少为5。越大流越大，极大化。现在学习的是第18页，共42页（3）字典序的目标函数 现在学习的是第19页，共42页三、遗传算法遗传算法是一种通过模拟自然进化过程搜索最优解的方法，对多目标规划问题的求解很有效。在优化问题中，如果目标函数是多峰的，或者搜索空间不规则，就要求所使用的算法必须具有高度的鲁棒性，以避免在局部最优解附近徘徊。遗传算法的优点恰好是全局搜索能力强。现在学习的是第20页，共42页遗传算法:染色体通常是一串数据(或数组),用来作为优化问题的解的代码,其本身不一定是解.1、随机产生一定数目的初始染色体，组成一
6、个种群，种群中染色体的数目称为种群规模（pop_size);2、用评价函数（eval)来评价每一个染色体的优劣（即适应度）;3、遗传选择操作，根据适应度，从当前种群中选出优良的染色体，成为新一代染色体；现在学习的是第21页，共42页4、对这个新的种群进行交叉操作，然后进行变异操作。5、重复进行选择、交叉、变异，经过一定次数的迭代处理以后，把最好的染色体作为优化问题的最优解。现在学习的是第22页，共42页例1现在学习的是第23页，共42页1、解的结构 种群pop_size=30;变量个数N=3；染色体CHROMOSOMEpop_size+1N+1;2、解的可行性 static void init
7、ialization(void)double xN+1;/*N is the number of variables*/int i,j;for(i=1;i=POP_SIZE;i+)mark:for(j=1;j=N;j+)xj=myu(0,10);if(constraint_check(x)=0)goto mark;for(j=1;jb)printf(nThe first parameter should be less than the second!);exit(1);y=(double)rand()/(RAND_MAX);return(a+(b-a)*y);现在学习的是第25页，共42页s
8、tatic int constraint_check(double x)double a;int n;for(n=1;n=N;n+)if(xn100)return 0;return 1;现在学习的是第26页，共42页3、评价函数A、基于序的评价函数：i=1染色体最好，i=pop_size染色体最差根据偏好（多目标规划）、优先级（目标规划）将个体进行排序，好的染色体排前面，差的排后面。现在学习的是第27页，共42页B、权重和评价函数适应值越小，染色体越好现在学习的是第28页，共42页static void objective_function(void)double x1,x2,x3;int i
9、;for(i=1;i=POP_SIZE;i+)x1=CHROMOSOMEi1;x2=CHROMOSOMEi2;x3=CHROMOSOMEi3;OBJECTIVEi1=3-sqrt(x1);if(OBJECTIVEi10)OBJECTIVEi1=0;OBJECTIVEi2=4-sqrt(x1+2*x2);if(OBJECTIVEi20)OBJECTIVEi2=0;OBJECTIVEi3=5-sqrt(x1+2*x2+3*x3);if(OBJECTIVEi30)OBJECTIVEi3=0;for(i=1;i=POP_SIZE;i+)OBJECTIVEi0=10000*OBJECTIVEi1+100
10、*OBJECTIVEi2+OBJECTIVEi3;现在学习的是第29页，共42页static void evaluation(int gen)double a;int i,j,k,label;objective_function();if(gen=0)for(k=0;k=M;k+)OBJECTIVE0k=OBJECTIVE1k;for(j=1;j=N;j+)CHROMOSOME0j=CHROMOSOME1j;现在学习的是第30页，共42页for(i=0;iPOP_SIZE;i+)label=0;a=OBJECTIVEi0;for(j=i+1;j=POP_SIZE;j+)if(TYPE*a)(T
11、YPE*OBJECTIVEj0)a=OBJECTIVEj0;label=j;if(label!=0)for(k=0;k=M;k+)a=OBJECTIVEik;现在学习的是第31页，共42页 OBJECTIVEik=OBJECTIVElabelk;OBJECTIVElabelk=a;for(j=1;j=N;j+)a=CHROMOSOMEij;CHROMOSOMEij=CHROMOSOMElabelj;CHROMOSOMElabelj=a;现在学习的是第32页，共42页4、选择过程 选择过程是以旋转轮盘赌pop_size次为基础的，赌轮上刻度是按染色体的适应值来划分的。刻度不是均匀分配的，染色体的
12、适应值越大，该染色体所占赌盘的面积越大，该染色体被选中的概率越大。每次选择都会产生新一代染色体pop_size个。无论使用何种评价函数，选择过程总可以表示以下步骤完成：1、对每个染色体 ，计算累积概率 现在学习的是第33页，共42页2、从区间 中产生一个随机数r3、若 ，则选择第i个染色体4、重复步骤2和步骤3共pop_size次，这样可以得到pop_size个复制的染色体现在学习的是第34页，共42页static void selection()double r,tempPOP_SIZE+1N+1;int i,j,k;for(i=1;i=POP_SIZE;i+)r=myu(0,qPOP_SI
13、ZE);for(j=0;j=POP_SIZE;j+)if(r=qj)for(k=1;k=N;k+)tempik=CHROMOSOMEjk;现在学习的是第35页，共42页break;for(i=1;i=POP_SIZE;i+)for(k=1;k=N;k+)CHROMOSOMEik=tempik;现在学习的是第36页，共42页5、交叉操作 用种群（pop_size个）的染色体进行交叉操作产生新一代染色体，方法如下：1、定义概率参数 ，（表示每一次交叉操作后大约有 个染色体发生改变）。2、在0，1中产生随机数r,如果 ，则在1到pop_size中随机取两个染色体进行交叉操作，产生两个新的染色体取代旧
14、的染色体，（注意：如果新的染色体不是可行解，则新的染色题无效，不取代，但交叉操作一次），重复步骤2共pop_size/2次。现在学习的是第37页，共42页static void crossover()int i,j,jj,k,pop;double r,xN+1,yN+1;pop=POP_SIZE/2;for(i=1;iP_CROSSOVER)continue;j=(int)myu(1,POP_SIZE);jj=(int)myu(1,POP_SIZE);r=myu(0,1);for(k=1;k=N;k+)xk=r*CHROMOSOMEjk+(1-r)*CHROMOSOMEjjk;现在学习的是第3
15、8页，共42页yk=r*CHROMOSOMEjjk+(1-r)*CHROMOSOMEjk;if(constraint_check(x)=1)for(k=1;k=N;k+)CHROMOSOMEjk=xk;if(constraint_check(y)=1)for(k=1;k=N;k+)CHROMOSOMEjjk=yk;现在学习的是第39页，共42页6、变异操作 同交叉操作类似。1、定义概率参数 大数M，方向 （表示每一次变异后大约有 个染色体发生进化，其中 ）2、在区间0，1中产生随机数r,如果 ,则在1到pop_size中随机取一个染色体进行变异，如果是可行解，则取代该染色体。3、重复pop_s
16、ize次步骤2。现在学习的是第40页，共42页static void mutation(void)int i,j,k;double xN+1,yN+1,infty,directionN+1;double INFTY=10,precision=0.0001;for(i=1;iP_MUTATION)continue;for(k=1;k=N;k+)xk=CHROMOSOMEik;for(k=1;k=N;k+)if(myu(0,1)precision)for(j=1;j=N;j+)yj=xj+infty*directionj;if(constraint_check(y)=1)for(k=1;k=N;k+)CHROMOSOMEik=yk;break;infty=myu(0,infty);现在学习的是第42页，共42页