网格法优化目标程序.doc

网格法求解优化问题1.1网格法11.1.1网格法求解高速公路问题运行结果：11.1.2求解高速公路问题的网格法程序：21.2多重网格法31.2.2多重网格法主程序41.2.3多重网格法函数52004/12/3思考题：请结合实例对比网格法与随机跳跃法的特点。已知通过Matlab的优化工具箱函数fmincon得到花钱最少为 万元；用其他解法求解并比较。这里采用的随机跳跃法模拟10万次求解。其运行输出为：optans = 2.2584e+004len = 38.9350ans = 12.1731 14.3323 15.6677 17.82691.1 网格法1.1.1 网格法求解高速公路问题运行结果：count = 923521最优目标 22603.376739x(1)= 30.000000x(2)= 30.000000x(3)= 30.000000x(4)= 30.000000exp_time = 105.7900len = 39.31801.1.2 求解高速公路问题的网格法程序：%2004-12-3%网格法示例：求解高速公路问题%clear allglobal C LC=400 800 1200;L=4 4 4 4 4;time_begin = clock;N=4;%决策变量个数a=0; b=30; opt_obj = inf;%init opt_dec = zeros(1,4);gridnum=30; step=b/gridnum count=0; for x1=0:step: b, for x2=0:step:b, for x3=0:step:b, for x4=0:step:b, x = x1 x2 x3 x4; count=count+1; cur_obj = objfun_97(x); if cur_obj opt_objopt_obj = 2.260337673850411e+004略微优于前面的网格法1.2.1.2 第二次运行depth=2;%递归调用深度numband=2;%局部搜索个数（前numband个较优点扩展搜索，递归调用网格法）width=2;%公里，递归调用子区间宽度step=1;%划分区间步长运行输出：opt_obj = 2.2586e+004opt_dec = 12.2500 14.5000 15.7500 18.0000通过以上分析发现，以上结果大大好于前面单个网格法结果，并与Maltab优化工具箱找到的最优解相对误差不到万分之一。可见效果非常好。1.2.2 多重网格法主程序%调用多重网格法程序：求解高速公路问题clear allglobal C LC=400 800 1200;L=4 4 4 4 4;lb=zeros(1,4);%决策变量下限ub=30*ones(1,4);%决策变量上限depth=2;%递归调用深度numband=2;%局部搜索个数（前numband个较优点扩展搜索，递归调用网格法）width=2;%公里，递归调用子区间宽度step=1;%划分区间步长%注意：这里width,step可以根据各个决策变量的区间长度进行设置，%那么就可以用向量存储opt_obj,opt_dec = solvP97multigrid_r(lb,ub,depth,numband,width,step)1.2.3 多重网格法函数function opt_obj,opt_dec=solvP97multigrid_r(lb,ub,depth,numband,width,step)%lb:决策变量下届%ub:决策变量上届%lb,ub为向量，元素个数与决策变量个数相同%depth：递归调用深度，每次增加1%numband：分段个数，%width:每个区间宽度%返回值：%opt_obj：近似最优目标%opt_dec：对应决策变量%2004-12-3%网格法示例：求解高速公路问题%高级求解算法：结合递归算法实现多级网格法%global C Ldepth=depth - 1;N =length(lb);%决策变量个数%C=400 800 1200;%L=4 4 4 4 4;arr_opt_obj=inf*ones(1,N);arr_opt_dec=ones(numband,N);%time_begin = clock;%N=4;%决策变量个数%a=0; %b=30; opt_obj = inf;%init opt_dec = zeros(1,4);%gridnum=30; %step=width;%/gridnum count=0; for x1=lb(1):step: ub(1), for x2=lb(2):step:ub(2), for x3=lb(3):step:ub(3), for x4=lb(4):step:ub(4), x = x1 x2 x3 x4; %count=count+1; cur_obj = objfun_97(x); %if cur_obj opt_obj, % opt_obj = cur_obj; % opt_dec = x; %end arr_opt_obj,arr_opt_dec=. cmp_opt(arr_opt_obj,arr_opt_dec,cur_obj,x); end %for x4 end %for x3 end %for x2 end %for x1 %下面根据numband来一次比较选择最优 if depth=0, opt_obj=arr_opt_obj(1);%返回最佳 opt_dec=arr_opt_dec(1,:); return%递归深度最大，故返回 end for i=1:numband, lb=arr_opt_dec(i,:) - width/2; ub=arr_opt_dec(i,:) + width/2;%new ver step=step/2; tmp_obj,tmp_dec=solvP97multigrid_r(lb,ub,depth,numband,width,step); arr_opt_obj,arr_opt_dec=. cmp_opt(arr_opt_obj,arr_opt_dec,tmp_obj,tmp_dec); end opt_obj=arr_opt_obj(1);%返回最佳 opt_dec=arr_opt_dec(1,:); function myobj,mydec= cmp_opt(arr_opt_obj,arr_opt_dec,cur_opt_obj,cur_opt_dec)%arr_opt_obj 存储numband个前面“最优”目标，决策%arr_opt_dec%cur_opt_obj 当前用来比较的目标，决策%cur_opt_dec%如果当前的较优（根据obj越小），则替换原决策中的相对不优%old ver:n=length(arr_opt_dec);%存储的前面n个为一次最优（第1个目标值最小）%n,tmp_tmp=size(arr_opt_dec);%new ver%测试例子：%arr_opt_obj= 1 3 5;% arr_opt_dec=0.1 0.2 0.3;0.4 0.5 0.6;0.7 0.8 0.9%myobj,mydec=tmp_cmp_opt(arr_opt_obj,arr_opt_dec,4,11 22 33)%说明：目前solvP97multigrid_r中要用到这个函数n=length(arr_opt_obj);%old ver:arr_opt_obj(end)=cur_opt_obj;%目标值加入（最后要删除一个）arr_opt_obj(end+1)=cur_opt_obj;%目标值加入（最后要删除一个）%new verarr_opt_dec(n+1,:)=cur_opt_dec;Y,I= sort(arr_opt_obj); myobj =Y(1:n);% mydec =arr_opt