蚁群算法附带数据结果

%{

[代码说明]

蚁群算法解决VRP问题

[算法说明]

首先实现一个ant蚂蚁类，用此蚂蚁类实现搜索。

算法按照tsp问题去解决，但是在最后计算路径的时候有区别。

比如有10个城市,城市1是配送站，蚂蚁搜索的得到的路径是1,3,5,9,4,10,2,6,8,7。

计算路径的时候把城市依次放入派送线路中,

每放入一个城市前，检查该城市放入后是否会超过车辆最大载重 如果没有超过就放入

如果超过，就重新开始一条派送路线 ……

直到最后一个城市放完 就会得到多条派送路线

这样处理比较简单可以把vrp问题转为tsp问题求解 但是实际效果还需要验证。

[作者]

Wugsh@2011.12.16

wuguangsheng@hisense.com guangsheng.wu@163.com %}

%清除所有变量和类的定义 clear;

clear classes;

%蚁群算法参数(全局变量) global ALPHA; %启发因子 global BETA; %期望因子

global ANT_COUNT; %蚂蚁数量 global CITY_COUNT; %城市数量 global RHO; %信息素残留系数!!! global IT_COUNT; %迭代次数 global DAry; %两两城市间距离 global TAry; %两两城市间信息素 global CITYWAry; %城市货物需求量 global VW; %车辆最大载重

%===================================================================

%设置参数变量值 ALPHA=1.0; BETA=2.0; RHO=0.95;

IT_COUNT=200;

VW=100;

%=================================================================== %读取数据并根据读取的数据设置其他参数 load data.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=PBest^(1/CITY_COUNT);

TRate=(1-temp)/((CITY_COUNT/2-1)*temp); %最大信息素和最小信息素之间的比值

%信息素的最大最小值开始的时候设置成多大无所谓

%第一次搜索完成会生成一个最优解,然后用这个解会重新产生最大最小值 Tmax=1; %信息素最大值

Tmin=Tmax*TRate; %信息素最小值

% 计算两两城市间距离 DAry=zeros(CITY_COUNT); for i=1:CITY_COUNT

for j=1:CITY_COUNT

DAry(i,j)=sqrt((city_xy_ary(i,1)-city_xy_ary(j,1))^2+(city_xy_ary(i,2)-city_xy_ary(j,2))^2); end end

% 初始化城市间信息素 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; %一次搜索是否有更优解产生

%开始搜索

for i=1:IT_COUNT

fprintf('开始第%d次搜索 , 剩余%d次',i,IT_COUNT-i);

FoundBetter=0; %搜索前先置为没有更优解产生

for j=1:ANT_COUNT

%蚂蚁搜索一次 mayi=Search(mayi);

%得到蚂蚁搜索路径长度

Length_Ary(j)=get(mayi,'path_length');

%得到蚂蚁搜索的路径

Path_Ary{j}=get(mayi,'path');

%保存最优解

if (Length_Ary(j) < Best_Path_Length);

Best_Path_Length=Length_Ary(j); Best_Path=Path_Ary{j};

%有更优解产生,设置标志 FoundBetter=1; end end

%有更好解产生,进行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; for k=2:CITY_COUNT

m=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; %信息素最小值

for m=1:CITY_COUNT for n=1:CITY_COUNT if (TAry(m,n)>Tmax) TAry(m,n)=Tmax;

end

if (TAry(m,n)

TAry(m,n)=Tmin; end end end

%------------------------------------------------------------- %换行 fprintf('\\n'); end

tm2=datenum(clock); %记录算法结束执行时的时间

fprintf('\\n搜索完成 , 用时%.3f秒 , 最佳路径长为%.3f , 派送方案如下 :：\\n\\n[1]',(tm2-tm1)*86400,Best_Path_Length);

%=================================================================== %输出结果 dbW=0;

for i=2:CITY_COUNT

m=Best_Path(i-1); %上一个城市 n=Best_Path(i); %当前城市

if (dbW+CITYWAry(n)>VW) %运送的货物超过限制

fprintf(' (满载率 : %.1f%%)\\n[1]-%d',dbW*100/VW,n); dbW=CITYWAry(n); %运输的重量等于该城市的需求量 else %没有超过限制 fprintf('-%d',n);

dbW=dbW+CITYWAry(n); %运输的重量加上该城市的需求量 end end

fprintf(' (满载率 : %.1f%%)',dbW*100/VW);

fprintf('\\n\\n');

%====== [程序结束]=====================================================

%对结果进行2-OPT优化

function f=opt2(Line)

%数组长度

size=length(Line);

NewLine=Line; % 返回结果先设置成原来路径

Flag=1;

while (Flag == 1) Flag=0; for i=1:size-2 a=Line(1,1:i); %路径前段 b=fliplr(Line(1,i+1:size)); %路径后段倒置 c=cat(2,a,b); %新路径 %新路径更好就替换 if (PathLength(c)

%返回结果 f=NewLine; end

1 14.5 13.0 0.0 2 12.8 8.5 0.1 3 18.4 3.4 0.4 4 15.4 16.6 1.2 5 18.9 15.2 1.5 6 15.5 11.6 0.8 7 3.9 10.6 1.3 8 10.6 7.6 1.7 9 8.6 8.4 0.6 10 12.5 2.1 1.2

11 13.8 5.2 0.4 12 6.7 16.9 0.9 13 14.8 2.6 1.3 14 1.8 8.7 1.3 15 17.1 11.0 1.9 16 7.4 1.0 1.7 17 0.2 2.8 1.1 18 11.9 19.8 1.5 19 13.2 15.1 1.6 20 6.4 5.6 21 9.6 14.8

1 0 0 0 2 3639 1315 12 3 4177 2244 13 4 3712 1399 14 5 3488 1535 53 6 3326 1556 45 7 3238 1229 22 8 4196 1004 11 9 4312 790 11 10 4386 570 56 11 3007 1970 43 12 2562 1756 24 13 2788 1491 65 14 2381 1676 32 15 1332 695 56 16 3715 1678 67 17 3918 2179 67 18 4061 2370 22 19 3780 2212 34 20 3676 2578 56 21 4029 2838 24 22 4263 2931 25 23 3429 1908 26 24 3507 2367 46 25 3394 2643 87 26 3439 3201 33 27 2935 3240 22 28 3140 3550 24 29 2545 2357 56 30 2778 2826 24

1.7 1.5 31 2370 2975 43 32 1304 2312 12

本文来源：https://www.bwwdw.com/article/cey6.html