目标规划与遗传算法

目标规划与遗传算法第一页，共四十二页，2022年，8月28日一、多目标规划第二页，共四十二页，2022年，8月28日多目标规划是在一组刚性约束条件下，以多个柔性条件为目标函数的一种规划问题。为了能够同时达到多个目标的优化，往往是很难做到的。因为，目标函数是相互冲突的，一个目标的更优是要牺牲其他目标作为代价的。有效解（非劣解、Pareto解）在不牺牲其他目标函数的前提下，不能再改进任何一个目标函数值的可行解。第三页，共四十二页，2022年，8月28日求解方法;1、权重和方法：每个目标函数分配权重并将其组合成为一个目标函数

权重的选择原则：使每个目标在加权后的地位相当。比如：一个目标表示利润，另一个目标表示效率，两者相差

因此，权重应取相当数量级。第四页，共四十二页，2022年，8月28日

2、妥协方法：是一种根据距离函数进行目标搜索行为的数学表达。设表示是第i个目标在不考虑其他目标时的最优值。第五页，共四十二页，2022年，8月28日例最小费用最大流第六页，共四十二页，2022年，8月28日网络最大流中不涉及费用问题，在实际问题中，在网络中的各边的运输费用是各不相同的，在满足最大流的情况下，求出最小费用，就是最小费用最大流问题。下图所示是最小费用最大流问题。每一条边上有两个数字，前者表示容量，后者表示单位费用。第七页，共四十二页，2022年，8月28日

设是定义在网络图G的边集E上的一个实数函数，表示i->j运输量及最大量。设是定义在网络图G的边集E上的一个实数函数，表示i->j运输的运费。满足：第八页，共四十二页，2022年，8月28日（1）---每条边的流量不超过该边大弧容量。

（2）---中间点流入与流出平衡。

第九页，共四十二页，2022年，8月28日（3）---发点总流出与收点总流入平衡。

其数学模型：

-------由发点1到其它点的流出量总和。N表示收点.第十页，共四十二页，2022年，8月28日-------由发点1到其它点的费用总和。N表示收点.第十一页，共四十二页，2022年，8月28日二、目标规划目标规划是多目标优化的一种妥协模型，其特点是，每一个目标都有一个理想目标值，目标规划的目的是极小化各目标函数与理想目标值的正、负偏差。在目标之间，根据其重要性的不同，建立一个优先结构是非常必要的。即根据决策者的偏好对所有目标进行排序。第十二页，共四十二页，2022年，8月28日数学模型:第十三页，共四十二页，2022年，8月28日解释:为优化因子,表示各目标的相对重要性为优先级j的第i个目标正、负偏差的权因子;为目标I偏离目标值的正、负偏差；N维决策变量；为目标约束，软性条件第十四页，共四十二页，2022年，8月28日系统约束，刚性条件第i个目标值优先级个数，目标约束个数，系统约束个数。目标函数另一种表示：表示按字典序极小化目标向量第十五页，共四十二页，2022年，8月28日续例最小费用最大流在没有考虑费用的前提下,最大流显然是11.要完成最大流的费用的最小值是180.现在的问题:如何用最小的费用,完成最大流(至少5以上)?第十六页，共四十二页，2022年，8月28日第一目标是费用S,理想值为180.

越大越好.极大化第十七页，共四十二页，2022年，8月28日（2）第二目标是流量，至少为5。越大流越大，极大化。第十八页，共四十二页，2022年，8月28日（3）字典序的目标函数

第十九页，共四十二页，2022年，8月28日三、遗传算法遗传算法是一种通过模拟自然进化过程搜索最优解的方法，对多目标规划问题的求解很有效。在优化问题中，如果目标函数是多峰的，或者搜索空间不规则，就要求所使用的算法必须具有高度的鲁棒性，以避免在局部最优解附近徘徊。遗传算法的优点恰好是全局搜索能力强。第二十页，共四十二页，2022年，8月28日遗传算法:

染色体通常是一串数据(或数组),用来作为优化问题的解的代码,其本身不一定是解.1、随机产生一定数目的初始染色体，组成一个种群，种群中染色体的数目称为种群规模（pop_size);2、用评价函数（eval)来评价每一个染色体的优劣（即适应度）;3、遗传选择操作，根据适应度，从当前种群中选出优良的染色体，成为新一代染色体；第二十一页，共四十二页，2022年，8月28日4、对这个新的种群进行交叉操作，然后进行变异操作。5、重复进行选择、交叉、变异，经过一定次数的迭代处理以后，把最好的染色体作为优化问题的最优解。第二十二页，共四十二页，2022年，8月28日例1第二十三页，共四十二页，2022年，8月28日1、解的结构种群pop_size=30;

变量个数N=3；染色体CHROMOSOME[pop_size+1][N+1];2、解的可行性staticvoidinitialization(void){doublex[N+1];/*Nisthenumberofvariables*/inti,j;for(i=1;i<=POP_SIZE;i++){ mark: for(j=1;j<=N;j++)x[j]=myu(0,10); if(constraint_check(x)==0)gotomark; for(j=1;j<=N;j++)CHROMOSOME[i][j]=x[j];}}第二十四页，共四十二页，2022年，8月28日doublemyu(doublea,doubleb)/*Uniformdistribution*/{doubley;if(a>b){printf("\nThefirstparametershouldbelessthanthesecond!");exit(1);}y=(double)rand()/(RAND_MAX);return(a+(b-a)*y);}第二十五页，共四十二页，2022年，8月28日staticintconstraint_check(doublex[]){ doublea; intn; for(n=1;n<=N;n++)if(x[n]<0)return0; a=x[1]*x[1]+x[2]*x[2]+x[3]*x[3]; if(a>100)return0; return1;}第二十六页，共四十二页，2022年，8月28日3、评价函数A、基于序的评价函数：i=1染色体最好，i=pop_size染色体最差根据偏好（多目标规划）、优先级（目标规划）将个体进行排序，好的染色体排前面，差的排后面。第二十七页，共四十二页，2022年，8月28日B、权重和评价函数适应值越小，染色体越好第二十八页，共四十二页，2022年，8月28日staticvoidobjective_function(void){ doublex1,x2,x3;inti; for(i=1;i<=POP_SIZE;i++){ x1=CHROMOSOME[i][1]; x2=CHROMOSOME[i][2]; x3=CHROMOSOME[i][3]; OBJECTIVE[i][1]=3-sqrt(x1); if(OBJECTIVE[i][1]<0)OBJECTIVE[i][1]=0;OBJECTIVE[i][2]=4-sqrt(x1+2*x2); if(OBJECTIVE[i][2]<0)OBJECTIVE[i][2]=0; OBJECTIVE[i][3]=5-sqrt(x1+2*x2+3*x3); if(OBJECTIVE[i][3]<0)OBJECTIVE[i][3]=0; } for(i=1;i<=POP_SIZE;i++) OBJECTIVE[i][0]=10000*OBJECTIVE[i][1]+100*OBJECTIVE[i][2]+OBJECTIVE[i][3];}第二十九页，共四十二页，2022年，8月28日staticvoidevaluation(intgen){doublea;inti,j,k,label;objective_function();if(gen==0){ for(k=0;k<=M;k++)OBJECTIVE[0][k]=OBJECTIVE[1][k]; for(j=1;j<=N;j++)CHROMOSOME[0][j]=CHROMOSOME[1][j];}

第三十页，共四十二页，2022年，8月28日for(i=0;i<POP_SIZE;i++){ label=0;a=OBJECTIVE[i][0]; for(j=i+1;j<=POP_SIZE;j++)if((TYPE*a)<(TYPE*OBJECTIVE[j][0])){ a=OBJECTIVE[j][0];

label=j; } if(label!=0){ for(k=0;k<=M;k++){ a=OBJECTIVE[i][k];第三十一页，共四十二页，2022年，8月28日

OBJECTIVE[i][k]=OBJECTIVE[label][k]; OBJECTIVE[label][k]=a; } for(j=1;j<=N;j++){ a=CHROMOSOME[i][j];CHROMOSOME[i][j]=CHROMOSOME[label][j]; CHROMOSOME[label][j]=a; } }}}第三十二页，共四十二页，2022年，8月28日4、选择过程选择过程是以旋转轮盘赌pop_size次为基础的，赌轮上刻度是按染色体的适应值来划分的。刻度不是均匀分配的，染色体的适应值越大，该染色体所占赌盘的面积越大，该染色体被选中的概率越大。每次选择都会产生新一代染色体pop_size个。无论使用何种评价函数，选择过程总可以表示以下步骤完成：1、对每个染色体，计算累积概率第三十三页，共四十二页，2022年，8月28日2、从区间中产生一个随机数r3、若，则选择第i个染色体4、重复步骤2和步骤3共pop_size次，这样可以得到pop_size个复制的染色体第三十四页，共四十二页，2022年，8月28日staticvoidselection(){doubler,temp[POP_SIZE+1][N+1];inti,j,k;for(i=1;i<=POP_SIZE;i++){ r=myu(0,q[POP_SIZE]); for(j=0;j<=POP_SIZE;j++){ if(r<=q[j]){ for(k=1;k<=N;k++)temp[i][k]=CHROMOSOME[j][k];

第三十五页，共四十二页，2022年，8月28日break; } }}for(i=1;i<=POP_SIZE;i++) for(k=1;k<=N;k++) CHROMOSOME[i][k]=temp[i][k];}第三十六页，共四十二页，2022年，8月28日5、交叉操作用种群（pop_size个）的染色体进行交叉操作产生新一代染色体，方法如下：1、定义概率参数，（表示每一次交叉操作后大约有个染色体发生改变）。2、在[0，1]中产生随机数r,如果，则在1到pop_size中随机取两个染色体进行交叉操作，产生两个新的染色体取代旧的染色体，（注意：如果新的染色体不是可行解，则新的染色题无效，不取代，但交叉操作一次），重复步骤2共pop_size/2次。第三十七页，共四十二页，2022年，8月28日staticvoidcrossover(){inti,j,jj,k,pop;doubler,x[N+1],y[N+1];pop=POP_SIZE/2;for(i=1;i<=pop;i++){ if(myu(0,1)>P_CROSSOVER)continue; j=(int)myu(1,POP_SIZE); jj=(int)myu(1,POP_SIZE); r=myu(0,1); for(k=1;k<=N;k++){x[k]=r*CHROMOSOME[j][k]+(1-r)*CHROMOSOME[jj][k];第三十八页，共四十二页，2022年，8月28日y[k]=r*CHROMOSOME[jj][k]+(1-r)*CHROMOSOME[j][k]; }if(constraint_check(x)==1)for(k=1;k<=N;k++)CHROMOSOME[j][k]=x[k];if(constraint_check(y)==1)for(k=1;k<=N;k++)CHROMOSOME[jj][k]=y[k];}}第三十九页，共四十二页，2022年，8月28日6、变异操作同交叉操作类似。1、定义概率参数大数M，方向（表示每一次变异后大约有个染色体发生进化，其中）2、在区间[0，1]中产生随机数r,如果