《目标规划与遗传算法精选文档.ppt》由会员分享，可在线阅读，更多相关《目标规划与遗传算法精选文档.ppt（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、目标规划与遗传算法本讲稿第一页，共四十二页一、多目标规划本讲稿第二页，共四十二页多目标规划是在一组刚性约束条件下，以多个柔性条件为目标函数的一种规划问题。为了能够同时达到多个目标的优化，往往是很难做到的。因为，目标函数是相互冲突的，一个目标的更优是要牺牲其他目标作为代价的。有效解（非劣解、Pareto解）在不牺牲其他目标函数的前提下，不能再改进任何一个目标函数值的可行解。本讲稿第三页，共四十二页求解方法;1、权重和方法：每个目标函数分配权重并将其组合成为一个目标函数 权重的选择原则：使每个目标在加权后的地位相当。比如：一个目标表示利润，另一个目标表示效率，两者相差 因此，权重应取相当数量级。本
2、讲稿第四页，共四十二页 2、妥协方法：是一种根据距离函数进行目标搜索行为的数学表达。设 表示是第i个目标在不考虑其他目标时的最优值。本讲稿第五页，共四十二页例 最小费用最大流本讲稿第六页，共四十二页网络最大流中不涉及费用问题，在实际问题中，在网络中的各边的运输费用是各不相同的，在满足最大流的情况下，求出最小费用，就是最小费用最大流问题。下图所示是最小费用最大流问题。每一条边上有两个数字，前者表示容量，后者表示单位费用。本讲稿第七页，共四十二页 设 是定义在网络图G的边集E上的一个实数函数，表示i-j运输量及最大量。设 是定义在网络图G的边集E上的一个实数函数，表示i-j运输的运费。满足：本讲稿
3、第八页，共四十二页（1）-每条边的流量不超过该边大弧容量。（2）-中间点流入与流出平衡。本讲稿第九页，共四十二页（3）-发点总流出与收点总流入平衡。其数学模型：-由发点1到其它点的流出量总和。N表示收点.本讲稿第十页，共四十二页-由发点1到其它点的费用总和。N表示收点.本讲稿第十一页，共四十二页二、目标规划目标规划是多目标优化的一种妥协模型，其特点是，每一个目标都有一个理想目标值，目标规划的目的是极小化各目标函数与理想目标值的正、负偏差。在目标之间，根据其重要性的不同，建立一个优先结构是非常必要的。即根据决策者的偏好对所有目标进行排序。本讲稿第十二页，共四十二页数学模型:本讲稿第十三页，共四十
4、二页解释:为优化因子,表示各目标的相对重要性为优先级j的第i个目标正、负偏差的权因子;为目标I偏离目标值的正、负偏差；N维决策变量；为目标约束，软性条件本讲稿第十四页，共四十二页系统约束，刚性条件第i个目标值优先级个数，目标约束个数，系统约束个数。目标函数另一种表示：表示按字典序极小化目标向量本讲稿第十五页，共四十二页续例 最小费用最大流在没有考虑费用的前提下,最大流显然是11.要完成最大流的费用的最小值是180.现在的问题:如何用最小的费用,完成最大流(至少5以上)?本讲稿第十六页，共四十二页(1)第一目标是费用S,理想值为180.越大越好.极大化本讲稿第十七页，共四十二页（2）第二目标是流
5、量，至少为5。越大流越大，极大化。本讲稿第十八页，共四十二页（3）字典序的目标函数 本讲稿第十九页，共四十二页三、遗传算法遗传算法是一种通过模拟自然进化过程搜索最优解的方法，对多目标规划问题的求解很有效。在优化问题中，如果目标函数是多峰的，或者搜索空间不规则，就要求所使用的算法必须具有高度的鲁棒性，以避免在局部最优解附近徘徊。遗传算法的优点恰好是全局搜索能力强。本讲稿第二十页，共四十二页遗传算法:染色体通常是一串数据(或数组),用来作为优化问题的解的代码,其本身不一定是解.1、随机产生一定数目的初始染色体，组成一个种群，种群中染色体的数目称为种群规模（pop_size);2、用评价函数（eva
6、l)来评价每一个染色体的优劣（即适应度）;3、遗传选择操作，根据适应度，从当前种群中选出优良的染色体，成为新一代染色体；本讲稿第二十一页，共四十二页4、对这个新的种群进行交叉操作，然后进行变异操作。5、重复进行选择、交叉、变异，经过一定次数的迭代处理以后，把最好的染色体作为优化问题的最优解。本讲稿第二十二页，共四十二页例1本讲稿第二十三页，共四十二页1、解的结构 种群pop_size=30;变量个数N=3；染色体CHROMOSOMEpop_size+1N+1;2、解的可行性 static void initialization(void)double xN+1;/*N is the numbe
7、r 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);本讲稿第二十五页，共四十二页static int constraint_check(double x)double a;
8、int n;for(n=1;n=N;n+)if(xn100)return 0;return 1;本讲稿第二十六页，共四十二页3、评价函数A、基于序的评价函数：i=1染色体最好，i=pop_size染色体最差根据偏好（多目标规划）、优先级（目标规划）将个体进行排序，好的染色体排前面，差的排后面。本讲稿第二十七页，共四十二页B、权重和评价函数适应值越小，染色体越好本讲稿第二十八页，共四十二页static void objective_function(void)double x1,x2,x3;int i;for(i=1;i=POP_SIZE;i+)x1=CHROMOSOMEi1;x2=CHROMO
9、SOMEi2;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*OBJECTIVEi2+OBJECTIVEi3;本讲稿第二十九页，共四十二页static vo
10、id 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;本讲稿第三十页，共四十二页for(i=0;iPOP_SIZE;i+)label=0;a=OBJECTIVEi0;for(j=i+1;j=POP_SIZE;j+)if(TYPE*a)(TYPE*OBJECTIVEj0)a=OBJECTIVEj0;label=j;if(label!=0)f
11、or(k=0;k=M;k+)a=OBJECTIVEik;本讲稿第三十一页，共四十二页 OBJECTIVEik=OBJECTIVElabelk;OBJECTIVElabelk=a;for(j=1;j=N;j+)a=CHROMOSOMEij;CHROMOSOMEij=CHROMOSOMElabelj;CHROMOSOMElabelj=a;本讲稿第三十二页，共四十二页4、选择过程 选择过程是以旋转轮盘赌pop_size次为基础的，赌轮上刻度是按染色体的适应值来划分的。刻度不是均匀分配的，染色体的适应值越大，该染色体所占赌盘的面积越大，该染色体被选中的概率越大。每次选择都会产生新一代染色体pop_si
12、ze个。无论使用何种评价函数，选择过程总可以表示以下步骤完成：1、对每个染色体 ，计算累积概率 本讲稿第三十三页，共四十二页2、从区间 中产生一个随机数r3、若 ，则选择第i个染色体4、重复步骤2和步骤3共pop_size次，这样可以得到pop_size个复制的染色体本讲稿第三十四页，共四十二页static void selection()double r,tempPOP_SIZE+1N+1;int i,j,k;for(i=1;i=POP_SIZE;i+)r=myu(0,qPOP_SIZE);for(j=0;j=POP_SIZE;j+)if(r=qj)for(k=1;k=N;k+)tempik
13、=CHROMOSOMEjk;本讲稿第三十五页，共四十二页break;for(i=1;i=POP_SIZE;i+)for(k=1;k=N;k+)CHROMOSOMEik=tempik;本讲稿第三十六页，共四十二页5、交叉操作 用种群（pop_size个）的染色体进行交叉操作产生新一代染色体，方法如下：1、定义概率参数 ，（表示每一次交叉操作后大约有 个染色体发生改变）。2、在0，1中产生随机数r,如果 ，则在1到pop_size中随机取两个染色体进行交叉操作，产生两个新的染色体取代旧的染色体，（注意：如果新的染色体不是可行解，则新的染色题无效，不取代，但交叉操作一次），重复步骤2共pop_siz
14、e/2次。本讲稿第三十七页，共四十二页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;本讲稿第三十八页，共四十二页yk=r*CHROMOSOMEjjk+(1-r)*CHROMOSOMEjk;if(constraint_
15、check(x)=1)for(k=1;k=N;k+)CHROMOSOMEjk=xk;if(constraint_check(y)=1)for(k=1;k=N;k+)CHROMOSOMEjjk=yk;本讲稿第三十九页，共四十二页6、变异操作 同交叉操作类似。1、定义概率参数 大数M，方向 （表示每一次变异后大约有 个染色体发生进化，其中 ）2、在区间0，1中产生随机数r,如果 ,则在1到pop_size中随机取一个染色体进行变异，如果是可行解，则取代该染色体。3、重复pop_size次步骤2。本讲稿第四十页，共四十二页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);本讲稿第四十二页，共四十二页