蚁群算法附带数据结果

%代码说明蚁群算法解决VRP问题算法说明首先实现一个ant蚂蚁类，用此蚂蚁类实现搜索。算法按照tsp问题去解决，但是在最后计算路径的时候有区别。1,3,5,9,4,10,2,6,8,7。比如有10个城市,城市1是配送站，蚂蚁搜索的得到的路径是计算路径的时候把城市依次放入派送线路中,每放入一个城市前，检查该城市放入后是否会超过车辆最大载重如果没有超过就放入如果超过，就重新开始一条派送路线直到最后一个城市放完就会得到多条派送路线这样处理比较简单可以把vrp问题转为tsp问题求解但是实际效果还需要验证。作者Wugsh2011.12.16wuguangshengguangsheng.wu%清除所有变量和类的定义clear;clearclasses;%蚁群算法参数（全局变量）globalALPHA;%启发因子globalBETA;%期望因子globalANT_COUNT;%蚂蚁数量globalCITY_COUNT;%城市数量globalRHO;%信息素残留系数!globalIT_COUNT;%迭代次数globalDAry;%两两城市间距离globalTAry;%两两城市间信息素globalCITYWAry;%城市货物需求量globalVW;%车辆最大载重%=%设置参数变量值ALPHA=1.0;BETA=2.0;RHO=0.95;IT_COUNT=200;VW=100;%=%读取数据并根据读取的数据设置其他参数loaddata.txt;%从文本文件加载数据city_xy_ary=data(:,2:3);%得到城市的坐标数据CITYWAry=data(:,4);%得到每个城市的货物需求量CITY_COUNT=length(CITYWAry);%得到城市数量(包括配送站在内)ANT_COUNT=round(CITY_COUNT*2/3)+1;%根据城市数量设置蚂蚁数量,一般设置为城市数量的2/3%MMAS信息素参数%计算最大信息素和最小信息素之间的比值PBest=0.05;%蚂蚁一次搜索找到最优解的概率temp=PBesL(1/CITY_C0UNT);TRate=(1-temp)/(CITY_COUNT/2-1)*temp);%最大信息素和最小信息素之间的比值%信息素的最大最小值开始的时候设置成多大无所谓%第一次搜索完成会生成一个最优解,然后用这个解会重新产生最大最小值Tmax=1;%信息素最大值Tmin=Tmax*TRate;%信息素最小值%计算两两城市间距离DAry=zeros(CITY_C0UNT);fori=1:CITY_C0UNTforj=1:CITY_C0UNTDAry(i,j)=sqrt(city_xy_ary(i,1)-city_xy_ary(j,1)A2+(city_xy_ary(i,2)-city_xy_ary(j,2)A2);endend%初始化城市间信息素TAry=zeros(CITY_COUNT);TAry=TAry+Tmax;%=%初始化随机种子rand('state',sum(100*clock);%另一种方法%rand('twister',sum(100*clock)%定义蚂蚁mayi=ant();Best_Path_Length=10e9;%最佳路径长度，先设置成一个很大的值tm1=datenum(clock);%记录算法开始执行时的时间FoundBetter=0;%一次搜索是否有更优解产生%开始搜索fori=1:IT_COUNTfprintf('开始第%d次搜索,剩余%d次',i,IT_COUNT-i);FoundBetter=0;%搜索前先置为没有更优解产生forj=1:ANT_COUNT%蚂蚁搜索一次mayi=Search(mayi);%得到蚂蚁搜索路径长度Length_Ary(j)=get(mayi,'path_length');%得到蚂蚁搜索的路径Path_Aryj=get(mayi,'path');%保存最优解if(Length_Ary(j)<Best_Path_Length);Best_Path_Length=Length_Ary(j);Best_Path=Path_Aryj;%有更优解产生,设置标志FoundBetter=1;endend%有更好解产生,进行2-OPT优化if(FoundBetter=1)fprintf(',本次搜索找到更好解!');Best_Path=opt2(Best_Path);Best_Path_Length=PathLength(Best_Path);end%全部蚂蚁搜索完一次，更新环境信息素TAry=TAry*RHO;%只有全局最优蚂蚁释放信息素dbQ=1/Best_Path_Length;fork=2:CITY_COUNTm=Best_Path(k-1);%上一个城市编号n=Best_Path(k);%下一个城市编号%更新路径上的信息素TAry(m,n)=TAry(m,n)+dbQ;TAry(n,m)=TAry(m,n);end%更新最后城市返回出发城市路径上的信息素TAry(n,1)=TAry(n,1)+dbQ;TAry(1,n)=TAry(n,1);%更新完信息素,进行边界检查Tmax=1/(1-RHO)*Best_Path_Length);%信息素最大值Tmin=Tmax*TRate;%信息素最小值form=1:CITY_COUNTforn=1:CITY_COUNTif(TAry(m,n)>Tmax)TAry(m,n)=Tmax;endif(TAry(m,n)<Tmin)TAry(m,n)=Tmin;endendend%换行fprintf('n');endtm2=datenum(clock);%记录算法结束执行时的时间fprintf('n搜索完成,用时%.3f秒,最佳路径长为%.3f,派送方案如下nn1',(tm2-tm1)*86400,Best_Path_Length);%=%输出结果dbW=0;fori=2:CITY_COUNTm=Best_Path(i-1);%上一个城市n=Best_Path(i);%当前城市if(dbW+CITYWAry(n)>VW)%运送的货物超过限制fprintf('(满载率:%.1f%)n1-%d',dbW*100/VW,n);dbW=CITYWAry(n);%运输的重量等于该城市的需求量else%没有超过限制fprintf('-%d',n);dbW=dbW+CITYWAry(n);%运输的重量加上该城市的需求量endendfprintf('(满载率:%.1f%)',dbW*100/VW);fprintf('nn');%=程序结束=%对结果进行2-OPT优化functionf=opt2(Line)%数组长度size=length(Line);NewLine=Line;%返回结果先设置成原来路径Flag=1;while(Flag=1)Flag=0;fori=1:size-2a=Line(1,1:i);%路径前段b=fliplr(Line(1,i+1:size);%路径后段倒置c=cat(2,a,b);%新路径%新路径更好就替换优化成功!=');if(PathLength(c)<PathLength(NewLine)NewLine=c;Flag=1;fprintf('n=2-OPTendendend%返回结果f=NewLine;end114.513.00.0212.88.50.1318.43.40.4415.416.61.2518.915.21.5615.511.60.873.910.61.3810.67.61.798.68.40.61012.52.11.21113.85.20.4126.716.90.91314.82.61.3141.88.71.31517.111.01.9167.41.01.7170.22.81.11811.919.81.51913.215.11.6206.45.61.7219.614.81.51 0003639131512417722441337121399143488153553332615564532381229224196100411431279011438657056300719704325621756242788149165238116763213326955637151678673918217967406123702237802212343676257856402928382442632931253429190826350723674633942643873439320133293532402231403550242545235756277828262423702975431304231212