function [Shortest_Route,Shortest_Length]=anttsp(city,iter_max,m,Alpha,Beta,Rho,Q)
n=size(city,1)
d=zeros(n,n)
d=squareform(pdist(city))
Eta=1./d
Tau=ones(n,n)
Tabu=zeros(m,n)
nC=1
R_best=zeros(iter_max,n)
L_best=inf.*ones(iter_max,1)
while nC<猜码枯=iter_max
route=[]
for i=1:ceil(m/n)
route=[route,randperm(n)]
end
Tabu(:,1)=(route(1,1:m))'
for j=2:n
for i=1:m
visited=Tabu(i,1:(j-1))
J=zeros(1,(n-j+1))
P=J
Jc=1
for k=1:n
if isempty(find(visited==k, 1))
J(Jc)=k
Jc=Jc+1
end
end
for k=1:length(J)
P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta)
end
P=P/(sum(P))
Pcum=cumsum(P)
Select=find(Pcum>=rand)
if isempty(Select)%是不是一定能保证Select不为空
Tabu(i,j)=round(1+(n-1)*rand)
else
next_visit=J(Select(1))
Tabu(i,j)=next_visit
end
end
end
if nC>=2
Tabu(1,:)=R_best(nC-1,:)
end
L=zeros(m,1)
for i=1:m
R=Tabu(i,:)
for j=1:(n-1)
L(i)=L(i)+d(R(j),R(j+1))
end
L(i)=L(i)+d(R(1),R(n))
end
L_best(nC)=min(L)
pos=find(L==L_best(nC))
R_best(nC,:)=Tabu(pos(1),:)
nC=nC+1
Delta_Tau=zeros(n,n)
for i=1:m
for j=1:(n-1)
Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i)
end
Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i)
end
Tau=(1-Rho).*Tau+Delta_Tau
Tabu=zeros(m,n)
end
Pos=find(L_best==min(L_best))
Shortest_Route=R_best(Pos(1),:)
Shortest_Length=L_best(Pos(1))
end
该程序试图对具有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
我现在也在研究它,希望能共同进步.建义可以看一下段海滨的关于蚁群算法的书.讲的不错,李士勇的也可以,还有一本我在图书馆见过,记不得名字了.
很多优化问题涉及到离散或二值的变量，典型的例子包括调度问题或路由问题。而PSO算法的更新公式和过程是面向连续空间并为其设计的，因此需要做一些修改使之适应离散空间的情况。编码的修改可能很简单，难点在于定义速度的意义和确定轨迹的变化。
Kennedy定义了第一个离散二进制版本的PSO算法。微粒使用二进制字符串进行编码。通过使用sigmoid函数，速度被限制在[0, 1]区间之内，并被解释为“概率的变化”。Yang对该方法在量子空间进行了扩展。
Mohan提出了几种二进制方法（直接方法、量子方法、正则方法、偏差向量方法以及混合方法），但是从有限的实验中没有得出什么结论。Clerc对一些专用于某些约束优化问题如TSP问题的PSO算法变种进行了试验，结果显示该方法比较有前途。Pang使用模糊矩阵来表示微粒的位置和速度，对PSO算法的算符进行了重定义，并将其应用到TSP问题的求解。Pampara将PSO算法与信号处理中的角调制技术结合起来，将高维二进制问题降维为一个在连续空间中定义的四维问题，并通过求解该四维问题来获得原问题的解。Afshinmanesh重新定义了离散PSO算法中的加法与乘法，并使用人工免疫系统中的阴性选择来实现速度限制Vmax。
Hu提出了一种改进PSO算法来处理排列问题。微粒被定义为一组特定值的排列，速度基于两个微粒的相似度重新定义，微粒根据由它们的速度所定义的随机率来变换到一个新的排列。引入了一个变异因子来防止当前的pBest陷入局部最小。在n皇后问题上的初步研究显示改进的PSO算法在解决约束满意问题方面很有前途。
Migliore对原始的二进制PSO算法进行了一些改进，提出了可变行为二进制微粒群算法（VB-BPSO）和可变动态特性二进制微粒群算法（VD-BPSO）。VB-BPSO算法按照连续PSO算法的速度更新公式的思想设计了一个新的速度更新公式，用来确定微粒位置向量每一位为1的概率。而VD-BPSO算法则是根据一定规则在两组不同参数确定的VB-BPSO算法之间切换。Migliore应用该算法设计出一种简单鲁棒的自适应无源天线。
Parsopoulos以标准函数为例测试微粒群优化算法液洞氏解决整数规划问题的能力。Salman将任务分配问题抽象为整数规颤没划模型并提出基于微粒群优化算法的解决方法。两者对迭代产生的连续解均进行舍尾取整后评价其质量。但是PSO算法生成的连续解与整数规划问题的目标函数评价值之间存在多对一的映射，以整型变量表示的目标函数不能准确反映算法中连续解的质量，而由此导致的冗余解空间与相应的冗余搜索降低了算法的收敛效率。
高尚采用交叉策略和变异策略，将PSO算法用来解决集合划分问题。赵传信重新定义了微粒群位置和速度闹散的加法与乘法 *** 作，并将PSO算法应用到0/1背包问题求解中。EL-Gallad在PSO算法中引入探索和勘探两个算子，用于求解排序问题。Firpi提出了BPSO算法的一种保证收敛的版本（但是并未证明其保证收敛性），并将其应用到特征选择问题。
上述离散PSO算法都是间接的优化策略，根据概率而非算法本身确定二进制变量，未能充分利用PSO算法的性能。在处理整数变量时，PSO算法有时候很容易陷入局部最小。原始PSO算法的思想是从个体和同伴的经验进行学习，离散PSO算法也应该借鉴该思想。高海兵基于传统算法的速度—位移更新 *** 作，在分析微粒群优化机理的基础上提出了广义微粒群优化模型（GPSO），使其适用于解决离散及组合优化问题。GPSO 模型本质仍然符合微粒群优化机理，但是其微粒更新策略既可根据优化问题的特点设计，也可实现与已有方法的融合。基于类似的想法，Goldbarg将局部搜索和路径重连过程定义为速度算子，来求解TSP问题。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）