目标规划与遗传算法优秀课件.ppt

《目标规划与遗传算法优秀课件.ppt》由会员分享，可在线阅读，更多相关《目标规划与遗传算法优秀课件.ppt（42页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、目标规划与遗传算法第1页，本讲稿共42页一、多目标规划第2页，本讲稿共42页 多目标规划是在一组刚性约束条件下，以多个柔性条件为目标函数的一种规划问题。为了能够同时达到多个目标的优化，往往是很难做到的。因为，目标函数是相互冲突的，一个目标的更优是要牺牲其他目标作为代价的。有效解（非劣解、Pareto解）在不牺牲其他目标函数的前提下，不能再改进任何一个目标函数值的可行解。第3页，本讲稿共42页 求解方法;1、权重和方法：每个目标函数分配权重并将其组合成为一个目标函数 权重的选择原则：使每个目标在加权后的地位相当。比如：一个目标表示利润，另一个目标表示效率，两者相差 因此，权重应取相当数量级。第4

2、页，本讲稿共42页 2、妥协方法：是一种根据距离函数进行目标搜索行为的数学表达。设 表示是第i个目标在不考虑其他目标时的最优值。第5页，本讲稿共42页例 最小费用最大流第6页，本讲稿共42页 网络最大流中不涉及费用问题，在实际问题中，在网络中的各边的运输费用是各不相同的，在满足最大流的情况下，求出最小费用，就是最小费用最大流问题。下图所示是最小费用最大流问题。每一条边上有两个数字，前者表示容量，后者表示单位费用。第7页，本讲稿共42页 设 是定义在网络图G的边集E上的一个实数函数，表示i-j运输量及最大量。设 是定义在网络图G的边集E上的一个实数函数，表示i-j运输的运费。满足：第8页，本讲稿

3、共42页（1）-每条边的流量不超过该边大弧容量。（2）-中间点流入与流出平衡。第9页，本讲稿共42页（3）-发点总流出与收点总流入平衡。其数学模型：-由发点1到其它点的流出量总和。N 表示收点.第10页，本讲稿共42页-由发点1到其它点的费用总和。N 表示收点.第1 1页，本讲稿共42页二、目标规划 目标规划是多目标优化的一种妥协模型，其特点是，每一个目标都有一个理想目标值，目标规划的目的是极小化各目标函数与理想目标值的正、负偏差。在目标之间，根据其重要性的不同，建立一个优先结构是非常必要的。即根据决策者的偏好对所有目标进行排序。第12页，本讲稿共42页数学模型:第13页，本讲稿共42页解释:

4、为优化因子,表示各目标的相对重要性为优先级j的第i个目标正、负偏差的权因子;为目标I偏离目标值的正、负偏差；N维决策变量；为目标约束，软性条件第14页，本讲稿共42页系统约束，刚性条件第i个目标值优先级个数，目标约束个数，系统约束个数。目标函数另一种表示：表示按字典序极小化目标向量第15页，本讲稿共42页续例 最小费用最大流在没有考虑费用的前提下,最大流显然是11.要完成最大流的费用的最小值是180.现在的问题:如何用最小的费用,完成最大流(至少5以上)?第16页，本讲稿共42页(1)第一目标是费用S,理想值为180.越大越好.极大化第17页，本讲稿共42页（2）第二目标是流量，至少为5。越大

5、流越大，极大化。第18页，本讲稿共42页（3）字典序的目标函数 第19页，本讲稿共42页三、遗传算法 遗传算法是一种通过模拟自然进化过程搜索最优解的方法，对多目标规划问题的求解很有效。在优化问题中，如果目标函数是多峰的，或者搜索空间不规则，就要求所使用的算法必须具有高度的鲁棒性，以避免在局部最优解附近徘徊。遗传算法的优点恰好是全局搜索能力强。第20页，本讲稿共42页 遗传算法:染色体通常是一串数据(或数组),用来作为优化问题的解的代码,其本身不一定是解.1、随机产生一定数目的初始染色体，组成一个种群，种群中染色体的数目称为种群规模（pop_size);2、用评价函数（eval)来评价每一个染色

6、体的优劣（即适应度）;3、遗传选择操作，根据适应度，从当前种群中选出优良的染色体，成为新一代染色体；第21页，本讲稿共42页4、对这个新的种群进行交叉操作，然后进行变异操作。5、重复进行选择、交叉、变异，经过一定次数的迭代处理以后，把最好的染色体作为优化问题的最优解。第22页，本讲稿共42页例1第23页，本讲稿共42页1、解的结构 种群pop_size=30;变量个数N=3；染色体CHROMOSOMEpop_size+1N+1;2、解的可行性 static void initialization(void)double xN+1;/*N is the number of variables*/

7、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;j=N;j+)CHROMOSOMEij=xj;第24页，本讲稿共42页double myu(double a,double b)/*Uniform distribution*/double y;if(ab)printf(nThe first parameter should be less than the second!);exit(1);y=(double)rand()/(RAND

8、_MAX);return(a+(b-a)*y);第25页，本讲稿共42页static 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_functio

9、n(void)double x1,x2,x3;int i;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+)OBJEC

10、TIVEi0=10000*OBJECTIVEi1+100*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=PO

11、P_SIZE;j+)if(TYPE*a)(TYPE*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次为基础的，赌轮上刻度是按染色体的适应值来划分的。刻度不是均匀分配的，染色体的适应值越大，该染色体所占赌盘的面积越大，该染色体被选中的概率越大。每次选择都会产生新一代染色体pop_size个。无论使用何种评价函数，选择过程总可以表示以下步骤完成：1、对每个染色体，计算累积概率 第33页，本讲稿共42页2、从区间 中产生一个随机数r3、若，则选择第i个染色体4、重复步骤2和步骤3共pop_size次，这样可以得到pop_size个复制的染色体第34页，本讲稿共42页