（1） 适应度函数fit.m
function fitness=fit(len,m,maxlen,minlen)
fitness=len
for i=1:length(len)
fitness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.0001)).^m
end
(2)个体距离计算函数 mylength.m
function len=myLength(D,p)
[N,NN]=size(D)
len=D(p(1,N),p(1,1))
for i=1:(N-1)
len=len+D(p(1,i),p(1,i+1))
end
end
(3)交叉 *** 作函数 cross.m
function [A,B]=cross(A,B)
L=length(A)
if L<10
W=L
elseif ((L/10)-floor(L/10))>=rand&&L>10
W=ceil(L/10)+8
else
W=floor(L/10)+8
end
p=unidrnd(L-W+1)
fprintf('p=%d ',p)
for i=1:W
x=find(A==B(1,p+i-1))
y=find(B==A(1,p+i-1))
[A(1,p+i-1),B(1,p+i-1)]=exchange(A(1,p+i-1),B(1,p+i-1))
[A(1,x),B(1,y)]=exchange(A(1,x),B(1,y))
end
end
(4)对调函数 exchange.m
function [x,y]=exchange(x,y)
temp=x
x=y
y=temp
end
(5)变异函数 Mutation.m
function a=Mutation(A)
index1=0index2=0
nnper=randperm(size(A,2))
index1=nnper(1)
index2=nnper(2)
%fprintf('index1=%d ',index1)
%fprintf('index2=%d ',index2)
temp=0
temp=A(index1)
A(index1)=A(index2)
A(index2)=temp
a=A
end
(6)连点画图函数 plot_route.m
function plot_route(a,R)
scatter(a(:,1),a(:,2),'rx')
hold on
plot([a(R(1),1),a(R(length(R)),1)],[a(R(1),2),a(R(length(R)),2)])
hold on
for i=2:length(R)
x0=a(R(i-1),1)
y0=a(R(i-1),2)
x1=a(R(i),1)
y1=a(R(i),2)
xx=[x0,x1]
yy=[y0,y1]
plot(xx,yy)
hold on
end
end
(7)主函数
clear
clc
%%%%%%%%%%%%%%%输入参数%%%%%%%%
N=50 %%城市的个数
M=100 %%种群的个数
C=100 %%迭代次数
C_old=C
m=2 %%适应值归一化淘汰加速指数
Pc=0.4%%交叉概率
Pmutation=0.2 %%变异概率
%%生成城市的坐标
pos=randn(N,2)
%%生成城市之间距离矩阵
D=zeros(N,N)
for i=1:N
for j=i+1:N
dis=(pos(i,1)-pos(j,1)).^2+(pos(i,2)-pos(j,2)).^2
D(i,j)=dis^(0.5)
D(j,i)=D(i,j)
end
end
%%如果城市之间的距离矩阵伍宴已知，可以在下面赋值灶渗给D，否则就随机生成
%%生成初始群体
popm=zeros(M,N)
for i=1:M
popm(i,:)=randperm(N)
end
%%随机选择一个种群
R=popm(1,:)
figure(1)
scatter(pos(:,1),pos(:,2),'rx')
axis([-3 3 -3 3])
figure(2)
plot_route(pos,R) %%画出种群各城市之间的连线
axis([-3 3 -3 3])
%%初始化种群及其适应函数
fitness=zeros(M,1)
len=zeros(M,1)
for i=1:M
len(i,1)=myLength(D,popm(i,:))
end
maxlen=max(len)
minlen=min(len)
fitness=fit(len,m,maxlen,minlen)
rr=find(len==minlen)
R=popm(rr(1,1),:)
for i=1:N
fprintf('%d ',R(i))
end
fprintf('\n')
fitness=fitness/sum(fitness)
distance_min=zeros(C+1,1) %%各次迭代的最小的种群的距离
while C>=0
fprintf('迭代第%d次\n',C)
%%选择 *** 作
nn=0
for i=1:size(popm,1)
len_1(i,1)=myLength(D,popm(i,:))
jc=rand*0.3
for j=1:size(popm,1)
if fitness(j,1)>=jc
nn=nn+1
popm_sel(nn,:)=popm(j,:)
break
end
end
end
%%每次选择都保存最优的种群
popm_sel=popm_sel(1:nn,:)
[len_m len_index]=min(len_1)
popm_sel=[popm_selpopm(len_index,:)]
%%交叉 *** 作
nnper=randperm(nn)
A=popm_sel(nnper(1),:)
B=popm_sel(nnper(2),:)
for i=1:nn*Pc
[A,B]=cross(A,B)
popm_sel(nnper(1),:)=A
popm_sel(nnper(2),:)=B
end
%%变异 *** 作
for i=1:nn
pick=rand
while pick==0
pick=rand
end
if pick<=Pmutation
popm_sel(i,:)=Mutation(popm_sel(i,:))
end
end
%%求适应度函数
NN=size(popm_sel,1)
len=zeros(NN,1)
for i=1:NN
len(i,1)=myLength(D,popm_sel(i,:))
end
maxlen=max(len)
minlen=min(len)
distance_min(C+1,1)=minlen
fitness=fit(len,m,maxlen,minlen)
rr=find(len==minlen)
fprintf('minlen=%d\n',minlen)
R=popm_sel(rr(1,1),:)
for i=1:N
fprintf('%d ',R(i))
end
fprintf('\n')
popm=[]
popm=popm_sel
C=C-1
%pause(1)
end
figure(3)
plot_route(pos,R)
axis([-3 3 -3 3])
该程序试图对具有31个城市的VRP进行求解，已知的最优解为784.1，我用该程序只能优化到810左右，返茄应该是陷入局部最优，但我不知问题出在什么地方。请用过蚁群算法的高手指教。蚁群算法的matlab源码，同时请指出为何不能优化漏庆察到已知的最好解
%
%
%the procedure of ant colony algorithm for VRP
%
%%%%%%%%%%%
%initialize the parameters of ant colony algorithms
load data.txt
d=data(:,2:3)
g=data(:,4)
m=31% 蚂蚁数
alpha=1
belta=4% 决定tao和miu重要性的参数
lmda=0
rou=0.9%衰减系数
q0=0.95
% 概率
tao0=1/(31*841.04)%初始信息素
Q=1% 蚂蚁循环一周所释放的信息素
defined_phrm=15.0 % initial pheromone level value
QV=100 % 车辆容量
vehicle_best=round(sum(g)/QV)+1%所完成任务所需的最少车数
V=40
% 计算两点的距离
for i=1:32
for j=1:32
dist(i,j)=sqrt((d(i,1)-d(j,1))^2+(d(i,2)-d(j,2))^2)
end
end
%给tao miu赋初值
for i=1:32
for j=1:32
if i~=j
%s(i,j)=dist(i,1)+dist(1,j)-dist(i,j)
tao(i,j)=defined_phrm
miu(i,j)=1/dist(i,j)
end
end
end
for k=1:32
for k=1:32
deltao(i,j)=0
end
end
best_cost=10000
for n_gen=1:50
print_head(n_gen)
for i=1:m
%best_solution=[]
print_head2(i)
sumload=0
cur_pos(i)=1
rn=randperm(32)
n=1
nn=1
part_sol(nn)=1
%cost(n_gen,i)=0.0
n_sol=0 % 由蚂蚁产生的路径数量
M_vehicle=500
t=0 %最佳路径数组的元素数为0
while sumload<=QV
for k=1:length(rn)
if sumload+g(rn(k))<=QV
gama(cur_pos(i),rn(k))=(sumload+g(rn(k)))/QV
A(n)=rn(k)
n=n+1
end
end
fid=fopen('out_customer.txt','a+')
fprintf(fid,'%s %i\t','the current position is:',cur_pos(i))
fprintf(fid,'\n%s','the possible customer set is:')
fprintf(fid,'\t%i\n',A)
fprintf(fid,'差辩------------------------------\n')
fclose(fid)
p=compute_prob(A,cur_pos(i),tao,miu,alpha,belta,gama,lmda,i)
maxp=1e-8
na=length(A)
for j=1:na
if p(j)>maxp
maxp=p(j)
index_max=j
end
end
old_pos=cur_pos(i)
if rand(1)<q0
cur_pos(i)=A(index_max)
else
krnd=randperm(na)
cur_pos(i)=A(krnd(1))
bbb=[old_pos cur_pos(i)]
ccc=[1 1]
if bbb==ccc
cur_pos(i)=A(krnd(2))
end
end
tao(old_pos,cur_pos(i))=taolocalupdate(tao(old_pos,cur_pos(i)),rou,tao0)%对所经弧进行局部更新
sumload=sumload+g(cur_pos(i))
nn=nn+1
part_sol(nn)=cur_pos(i)
temp_load=sumload
if cur_pos(i)~=1
rn=setdiff(rn,cur_pos(i))
n=1
A=[]
end
if cur_pos(i)==1 % 如果当前点为车场,将当前路径中的已访问用户去掉后,开始产生新路径
if setdiff(part_sol,1)~=[]
n_sol=n_sol+1 % 表示产生的路径数,n_sol=1,2,3,..5,6...,超过5条对其费用加上车辆的派遣费用
fid=fopen('out_solution.txt','a+')
fprintf(fid,'%s%i%s','NO.',n_sol,'条路径是:')
fprintf(fid,'%i ',part_sol)
fprintf(fid,'\n')
fprintf(fid,'%s','当前的用户需求量是:')
fprintf(fid,'%i\n',temp_load)
fprintf(fid,'------------------------------\n')
fclose(fid)
% 对所得路径进行路径内3-opt优化
final_sol=exchange(part_sol)
for nt=1:length(final_sol)% 将所有产生的路径传给一个数组
temp(t+nt)=final_sol(nt)
end
t=t+length(final_sol)-1
sumload=0
final_sol=setdiff(final_sol,1)
rn=setdiff(rn,final_sol)
part_sol=[]
final_sol=[]
nn=1
part_sol(nn)=cur_pos(i)
A=[]
n=1
end
end
if setdiff(rn,1)==[]% 产生最后一条终点不为1的路径
n_sol=n_sol+1
nl=length(part_sol)
part_sol(nl+1)=1%将路径的最后1位补1
% 对所得路径进行路径内3-opt优化
final_sol=exchange(part_sol)
for nt=1:length(final_sol)% 将所有产生的路径传给一个数组
temp(t+nt)=final_sol(nt)
end
cost(n_gen,i)=cost_sol(temp,dist)+M_vehicle*(n_sol-vehicle_best) %计算由蚂蚁i产生的路径总长度
for ki=1:length(temp)-1
deltao(temp(ki),temp(ki+1))=deltao(temp(ki),temp(ki+1))+Q/cost(n_gen,i)
end
if cost(n_gen,i)<best_cost
best_cost=cost(n_gen,i)
old_cost=best_cost
best_gen=n_gen % 产生最小费用的代数
best_ant=i%产生最小费用的蚂蚁
best_solution=temp
end
if i==m %如果所有蚂蚁均完成一次循环，，则用最佳费用所对应的路径对弧进行整体更新
for ii=1:32
for jj=1:32
tao(ii,jj)=(1-rou)*tao(ii,jj)
end
end
for kk=1:length(best_solution)-1
tao(best_solution(kk),best_solution(kk+1))=tao(best_solution(kk),best_solution(kk+1))+deltao(best_solution(kk),best_solution(kk+1))
end
end
fid=fopen('out_solution.txt','a+')
fprintf(fid,'%s%i%s','NO.',n_sol,'路径是:')
fprintf(fid,'%i ',part_sol)
fprintf(fid,'\n')
fprintf(fid,'%s %i\n','当前的用户需求量是:',temp_load)
fprintf(fid,'%s %f\n','总费用是:',cost(n_gen,i))
fprintf(fid,'------------------------------\n')
fprintf(fid,'%s\n','最终路径是:')
fprintf(fid,'%i-',temp)
fprintf(fid,'\n')
fclose(fid)
temp=[]
break
end
end
end
end
我现在也在研究它,希望能共同进步.建义可以看一下段海滨的关于蚁群算法的书.讲的不错,李士勇的也可以,还有一本我在图书馆见过,记不得名字了.
概念：蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值其原理：为什么小小的蚂蚁能够找到食物？他们具有智能么？设想，如果我们要为蚂蚁设计一个人工智能的程序，那么这个程序要多么复杂呢？首先，你要让蚂蚁能够避开障碍物，就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物，其次，要让蚂蚁找到食物，就需要哗空让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路径，那么需要计算所有可能的路径并且比较它们的大小，而且更重要的是，你要小心翼翼的编程，因为程序的错误也许会让你前功尽弃。这是多么不可思议的程序！太复杂了，恐怕没人能够完成这样繁琐冗余的程序
应用范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内
引申：跟着蚂蚁的踪迹，你找到了什么？通过上面的原理叙述和实际 *** 作，我们不难发现蚂蚁之所以具有智能行为，完全归功于它的简单行为规则，而这些规则综合起来具有下面两个方面的特点： 1、多样性 2、正反馈 多样性保证了蚂蚁在觅食的时候不置走进死胡同而无限循环，正反馈机制则保证了相对优良的信息能够被保存下来。我们可以把多样性看成是一种创造能力，而正反馈是一种学习强化能力。正反馈的力量也可以比喻成权威的意见，而多样性是打破权威体现的创造厅芹性，正是这两点小心翼翼的巧妙结合才使得智能行为涌现出来了。 引申来讲，大自然的进化，社会的进步、人类的创新实际上都离不开这两样东西，多样性保证了系统的创新能力，正反馈保证了优良特性能够得到强化，两者要恰到好处的结合。如果多样性过剩，也就是系统过于活跃，这相当于蚂蚁会过多的随机运动，它就会陷入混沌状态；而相反，多样性不够，正反馈机制过强，那么系统就好比一潭死水。这在蚁群中来讲就表现为，蚂蚁的行为过于僵硬，当环境变化了，蚂蚁群仍然不能适当的调整。 既然复杂性、智能行为是根据底层规则涌现的，既然底层规则具有多样性和正反馈特点，那么也许你会问这些规则是哪里来的？多样性和正反馈又是哪里来的？我本人的意见：规则来源于大自然的进化。而大自然的进化根据刚才讲的也体现为多样性和正反馈的巧妙结合。而这样的巧妙结合又是为什么呢？为什么在你眼前呈现的世界是如此栩栩如生呢？答案在于环境造就了这一切，之所以你看到栩栩如生的世界，是因为那些不能够适应环境的多样性与正反馈的结合都已经死掉了，被环境淘汰了！ 蚁群算法的实现 下面的程序开始运行之后，蚂蚁们开始从窝里出动了，寻找食物；他们会顺着屏幕爬满整个画面，直到找到食物再返回窝。 其中，‘F’点表示食物，‘H’表示窝，白色块表示乱伏瞎障碍物，‘+’就是蚂蚁了。
具体参考http://baike.baidu.com/view/539346.htm
希望对你有帮助，谢谢。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）