⑴ 如何提高蟻群路由演算法收斂速度
螞蟻演算法是一種新型隨機優化演算法,能有效解決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;
我現在也在研究它,希望能共同進步.建義可以看一下段海濱的關於蟻群演算法的書.講的不錯,李士勇的也可以,還有一本我在圖書館見過,記不得名字了.