⑴ 如何提高蚁群路由算法收敛速度
蚂蚁算法是一种新型随机优化算法,能有效解决Ad Hoc网络多约束的QoS路由问题,但存在收敛速度慢和易陷入局部最优等缺点.针对于此,在借鉴精英策略的基础上提出了一种基于双向收敛蚁群算法,并将该算法应用于Ad Hoc网络的QoS路由问题中.仿真结果表明,算法可明显提高数据包的投递率,降低端到端的传输时延.
可以
针对蚁群算法(ACA)寻优性质优良,但搜索时间长、收敛速度慢、易限于局部最优解,从而使其进一步推广应用受到局限的问题,对算法的全局收敛性进行了深入的理论研究,并从改善全局收敛性的角度对算法作了一系列改进,最后对Bayes29这一典型的TSP问题进行了仿真实验。实验结果证明,改进后的蚁群算法具有很好的全局收敛性能。这为蚁群算法的进一步理论研究打下了很好的基础,对其在各优化领域中的推广应用具有重要意义。
⑵ 遗传算法和蚁群算法在求解TSP问题上的对比分析
【原创】比遗传算法性能更好：蚁群算法TSP(旅行商问题)通用matlab程序
声明：本程序为本人原创，在研学论坛首次发表，本人保留一切权利，仅供学习交流用，如转载请注明原作者！
function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)
%%=========================================================================
%% ACATSP.m
%% Ant Colony Algorithm for Traveling Salesman Problem
%% ChengAihua,PLA Information Engineering University,ZhengZhou,China
%% Email:[email protected]
%% All rights reserved
%%-------------------------------------------------------------------------
%% 主要符号说明
%% C n个城市的坐标，n×2的矩阵
%% NC_max 最大迭代次数
%% m 蚂蚁个数
%% Alpha 表征信息素重要程度的参数
%% Beta 表征启发式因子重要程度的参数
%% Rho 信息素蒸发系数
%% Q 信息素增加强度系数
%% R_best 各代最佳路线
%% L_best 各代最佳路线的长度
%%=========================================================================
%%第一步：变量初始化
n=size(C,1);%n表示问题的规模（城市个数）
D=zeros(n,n);%D表示完全图的赋权邻接矩阵
for i=1:n
for j=1:n
if i~=j
D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
else
D(i,j)=eps;
end
D(j,i)=D(i,j);
end
end
Eta=1./D;%Eta为启发因子，这里设为距离的倒数
Tau=ones(n,n);%Tau为信息素矩阵
Tabu=zeros(m,n);%存储并记录路径的生成
NC=1;%迭代计数器
R_best=zeros(NC_max,n);%各代最佳路线
L_best=inf.*ones(NC_max,1);%各代最佳路线的长度
L_ave=zeros(NC_max,1);%各代路线的平均长度
while NC<=NC_max%停止条件之一：达到最大迭代次数
%%第二步：将m只蚂蚁放到n个城市上
Randpos=[];
for i=1:(ceil(m/n))
Randpos=[Randpos,randperm(n)];
end
Tabu(:,1)=(Randpos(1,1:m))';
%%第三步：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 length(find(visited==k))==0
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);
to_visit=J(Select(1));
Tabu(i,j)=to_visit;
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),:);
L_ave(NC)=mean(L);
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))
subplot(1,2,1)
DrawRoute(C,Shortest_Route)
subplot(1,2,2)
plot(L_best)
hold on
plot(L_ave)
function DrawRoute(C,R)
%%=========================================================================
%% DrawRoute.m
%% 画路线图的子函数
%%-------------------------------------------------------------------------
%% C Coordinate 节点坐标，由一个N×2的矩阵存储
%% R Route 路线
%%=========================================================================
N=length(R);
scatter(C(:,1),C(:,2));
hold on
plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)])
hold on
for ii=2:N
plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)])
hold on
end
设置初始参数如下：
m=31;Alpha=1;Beta=5;Rho=0.1;NC_max=200;Q=100;
31城市坐标为：
1304 2312
3639 1315
4177 2244
3712 1399
3488 1535
3326 1556
3238 1229
4196 1004
4312 790
4386 570
3007 1970
2562 1756
2788 1491
2381 1676
1332 695
3715 1678
3918 2179
4061 2370
3780 2212
3676 2578
4029 2838
4263 2931
3429 1908
3507 2367
3394 2643
3439 3201
2935 3240
3140 3550
2545 2357
2778 2826
2370 2975
运行后得到15602的巡游路径，
⑶ 蚁群算法求解TSP问题遇到“索引超出矩阵维度。”的问题跪求大神能解答
你检查一下坐标矩阵是否出现了重复数值。比如你给的例子中C矩阵的第二个和第三个数值就重复了。
⑷ 跪求tsp问题的蚁群算法，要vc++写的
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <cmath>
#include <ctime>
#include <iomanip>
#include <cassert>
using namespace std;
const int DIMENSION=535;//城市个数
const int PERSONS=1000;//种群个数
const int crosspob=0.75;//决定是否交叉的概率
const double mute=0.03;//变异概率
const int iternum=100000;//计划迭代次数
ofstream out("res100000.txt");
int nmutations;
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
struct chrom
{
unsigned int gene[DIMENSION-1];//固定第一个城市
int fitness;//该路径的长度
};//表征每个染色体特征
struct Population
{
struct chrom person[PERSONS];//有这么多个染色体
double fitsum;//适应值之和
int minfit; //最小适应度的下标
};//种群的一些属性
//function declare here*********************************
int select(Population* p);
bool Flip(float prob);
void Cross(unsigned int* table1,unsigned int* table2);
void Mutation(unsigned int* table);
void crossover(Population* pold,Population* pnew,int parent1,int parent2,int i);
void UpdateGen(Population* pold,Population* pnew);
void shuffle(unsigned int* table);
void ComputeFitness(Population* p,int* distance);
void InitData(Population* p,int* distance);
//function declare here*********************************
bool Flip(float pro)
{
float temp;
temp=(float)rand()/(float)RAND_MAX;
if(temp<=pro)
return true;
else
return false;
}
int find(unsigned int* table,unsigned int a,int start,int end)//返回a在数组table中的下标
{
for(int i=start;i<=end;i++)
{
if(a==table[i])
return i;
}
return -1;
}
void exchange(unsigned int* table,int index1,int index2)
{
unsigned int temp=table[index1];
table[index1]=table[index2];
table[index2]=temp;
}
void Cross(unsigned int* table1,unsigned int* table2)
//对两个基因进行交叉操作，生成子代的两个基因
{
int rand1=rand()%(DIMENSION-101)+50;
//assure rand1 range from 2 to DIMENSION-4,left and right side reserve at least 50 elements
int rand2=rand1;
do
{
rand2=rand()%(DIMENSION-101)+50;
}while(rand1==rand2);//assure rand1 differ from rand2
const int start=min(rand1,rand2);
const int end=max(rand1,rand2);
for(int i=start;i<=end;i++)
{
unsigned int t1=table1[i];
unsigned int t2=table2[i];
if(t1!=t2)
{
int a1=find(table1,t2,0,DIMENSION-2);
exchange(table1,a1,i);
int b1=find(table2,t1,0,DIMENSION-2);
exchange(table2,b1,i);
}
}
}
void Mutation(unsigned int* table)//依据一定概率对基因进行变异，变异操作是2-opt的
{
bool mut=Flip(mute);
if(mut)//如果发生了变异
{
nmutations++;
int rand1=rand()/(DIMENSION-1);
int rand2;
do
{
rand2=rand()/(DIMENSION-1);
}while(rand1==rand2);
exchange(table,rand1,rand2);
}
return;
}
void crossover(Population* pold,Population* pnew,int parent1,int parent2,int i)
//对群体中的两个个体杂交，生成新的个体,并将新个体保存进新的种群里
{
struct chrom* ch1=&(pnew->person[i]);
struct chrom* ch2=&(pnew->person[i+1]);
struct chrom* ch1_old=&(pold->person[parent1]);
struct chrom* ch2_old=&(pold->person[parent2]);
unsigned int* table1=ch1->gene;
unsigned int* table2=ch2->gene;
memcpy(table1,ch1_old->gene,sizeof(unsigned int)*(DIMENSION-1));
memcpy(table2,ch2_old->gene,sizeof(unsigned int)*(DIMENSION-1));
bool cro=Flip(crosspob);//依据交叉概率决定是否交叉
if(cro)
Cross(table1,table2);
Mutation(table1);//对交叉后的新基因进行变异
Mutation(table2);//对交叉后的新基因进行变异
}
void UpdateGen(Population* pold,Population* pnew,int* distance)
{
for(int i=0;i<PERSONS;i+=2)
{
int parent1=select(pold);
int parent2=select(pold);
crossover(pold,pnew,parent1,parent2,i);
}
//至此新的种群已经生成了，同时注意比较旧种群中最好适应度的个体和新种群中最好适应度的个体
ComputeFitness(pnew,distance);//计算新种群每个个体的适应度和总的适应度，最优个体
int newPopMinfit=pnew->person[pnew->minfit].fitness;
int oldPopMinfit=pold->person[pold->minfit].fitness;
if(oldPopMinfit<newPopMinfit)//如果旧种群的最优值优于新种群的最优值，替换新种群的最优值
{
struct chrom* ch_new=&(pnew->person[pnew->minfit]);
struct chrom* ch_old=&(pold->person[pold->minfit]);
unsigned int* table_new=ch_new->gene;
unsigned int* table_old=ch_old->gene;
memcpy(table_new,table_old,sizeof(unsigned int)*(DIMENSION-1));
ch_new->fitness=ch_old->fitness;
}
}
int select(Population* p)//从人口中选择合适的人来交配
{
double average_fit=(double)p->fitsum/(double)PERSONS;
int i;
while(true)
{
i=rand()%PERSONS;
struct chrom* ch1=&(p->person[i]);
double ratio=(double)ch1->fitness/average_fit;
double prob=1.0/(1.0+ratio);
bool sel=Flip(prob);
if(sel)
break;
}
return i;
}
void shuffle(unsigned int* table)
{
int num=2000;
while(num--)
{
int rand1=rand()%(DIMENSION-1);
int rand2;
do{
rand2=rand()%(DIMENSION-1);
}while(rand1==rand2);
exchange(table,rand1,rand2);
}
}
void ComputeFitness(Population* p,int* distance)
{
int i,j;
int minvalue=10000000;
double fitsum=0.0;
for(i=0;i<PERSONS;i++)
{
struct chrom* ch1=&(p->person[i]);
unsigned int *table=ch1->gene;
int length=distance[ (table[0]-1) ]+ distance[ (table[DIMENSION-2]-1)];
cout<<length<<endl;
//先将第一个城市到基因序列的第一个城市和最后的城市的距离计算在内
for(j=0;j<DIMENSION-2;j++)
{
int di=table[j]-1;
int dj=table[j+1]-1;
assert(di!=dj);
length+=distance[di*DIMENSION+dj];
}
ch1->fitness=length;
fitsum+=ch1->fitness;
if(ch1->fitness<minvalue)
{
minvalue=ch1->fitness;
p->minfit=i;
}
cout<<minvalue<<endl;
}
p->fitsum=fitsum;
cout<<fitsum<<endl;
}
void InitData(Population* p,int* distance)
{
srand(time(NULL));
int i;
unsigned int table[DIMENSION-1];
for(i=0;i<DIMENSION-1;i++)
table[i]=i+2;
for(i=0;i<PERSONS;i++)
{
struct chrom* ch1=&(p->person[i]);
shuffle(table);
memcpy(ch1->gene,table,sizeof(unsigned int)*(DIMENSION-1));
}
ComputeFitness(p,distance);
}
int main()
{
const double PI=3.1415926;
const double RRR=6378.388;
float* cord=new float[DIMENSION*2];
int* distance=new int[DIMENSION*DIMENSION];
//*******************读取城市坐标************************************//
ifstream in("ali535.tsp");
char str[256];
int i,j;
for(i=0;i<7;i++)
in.getline(str,256);
for(i=0;i<DIMENSION;i++)
{
int index;
float x,y;
in>> index>> x>> y;
int dx = (int) x;
float err_x = x- dx;
float latitude = PI * (dx + 5.0 * err_x/ 3.0) / 180.0;
int dy= (int)y;
float err_y= y- dy;
float longitude = PI * (dy + 5.0 * err_y/ 3.0) / 180.0;
cord[i*2]= latitude;
cord[i*2+1]= longitude;
}
in.close();
//*******************读取城市坐标************************************//
//*******************计算城市距离矩阵******************************//
for(i=0;i<DIMENSION;i++)
for(j=0;j<DIMENSION;j++)
{
if(i==j)
distance[i*DIMENSION+j]=0;
else
{
float xi,xj,yi,yj;
xi=cord[i*2];xj=cord[j*2];yi=cord[i*2+1];yj=cord[j*2+1];
double q1 = cos( yi-yj );
double q2 = cos( xi-xj );
double q3 = cos( xi+xj);
int dij = (int)(RRR * acos( 0.5*( (1.0+q1)*q2 - (1.0-q1)*q3 ) ) + 1.0);
distance[i*DIMENSION+j]= dij;
}
}
//*******************计算城市距离矩阵******************************//
Population* oldPop=new Population;
Population* newPop=new Population;
InitData(oldPop,distance);
long int start,end;
start=time(NULL);
for(int k=1;k<=iternum;k++)
{
UpdateGen(oldPop,newPop,distance);
Population* temp=oldPop;
oldPop=newPop;
newPop=temp;
int dis_tour=oldPop->person[oldPop->minfit].fitness;
out<<"第 "<<k<<" 代的最小距离＝ "<<setprecision(10)<<dis_tour<<endl;
}
end=time(NULL);
out<<"总的变异次数＝ "<<nmutations<<" 总共耗时＝ "<<end-start<<" 秒"<<endl;
delete [] distance;
delete [] cord;
delete oldPop;
delete newPop;
return 0;
}
⑸ MATLAB 蚁群算法求解TSP问题
n个城市，编号为1---n
for循环的次数是蚂蚁重复城市的次数，比如5个蚂蚁放到4个城市，需要重复两遍才能放完蚂蚁，每次循环产生n个1---n的随机数,相当于随机n个城市，产生城市序列
循环结束
Tabu一句表示将m个蚂蚁随机，每个蚂蚁放到前面产生的城市序列中，每个蚂蚁一个城市，需要m个，所以提取前面1：m个序列
'表示转置，没有多大用处，可能参与后面的计算方便。
我感觉如果m,n很大的话，你这样做会产生很大的浪费，计算很多的随机数，这样的话更好，一句就得：(如果变量Randpos后面没有用到的话，如果用到了，还要用你的程序)
Tabu=ceil(n*rand(1,m))'
⑹ 蚁群算法如何解决TSP问题的，求简单形象的说下，小妹谢过！！
有个食物（即目的地），一群蚂蚁开始按照自己的路去寻找这个食物，然后带回巢穴（即出发地），接着再去搬食物，慢慢地有一条路上留下来的信息素最多，这个时候，所有后来的蚂蚁都会按照这条路走，这条路就是TSP里的最优路径。
⑺ 蚁群算法求解TSP问题的源程序及简要说明
该程序试图对具有31个城市的VRP进行求解，已知的最优解为784.1，我用该程序只能优化到810左右，应该是陷入局部最优，但我不知问题出在什么地方。请用过蚁群算法的高手指教。
蚁群算法的matlab源码，同时请指出为何不能优化到已知的最好解
%
%
% the procere 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;
我现在也在研究它,希望能共同进步.建义可以看一下段海滨的关于蚁群算法的书.讲的不错,李士勇的也可以,还有一本我在图书馆见过,记不得名字了.