遺傳演算法解決旅行商問題

⑴ 遺傳演算法具體應用

1、函數優化

函數優化是遺傳演算法的經典應用領域，也是遺傳演算法進行性能評價的常用算例，許多人構造出了各種各樣復雜形式的測試函數：連續函數和離散函數、凸函數和凹函數、低維函數和高維函數、單峰函數和多峰函數等。

2、組合優化

隨著問題規模的增大，組合優化問題的搜索空間也急劇增大，有時在目前的計算上用枚舉法很難求出最優解。對這類復雜的問題，人們已經意識到應把主要精力放在尋求滿意解上，而遺傳演算法是尋求這種滿意解的最佳工具之一。

此外，GA也在生產調度問題、自動控制、機器人學、圖象處理、人工生命、遺傳編碼和機器學習等方面獲得了廣泛的運用。

3、車間調度

車間調度問題是一個典型的NP-Hard問題，遺傳演算法作為一種經典的智能演算法廣泛用於車間調度中，很多學者都致力於用遺傳演算法解決車間調度問題，現今也取得了十分豐碩的成果。

從最初的傳統車間調度（JSP）問題到柔性作業車間調度問題（FJSP），遺傳演算法都有優異的表現，在很多算例中都得到了最優或近優解。

(1)遺傳演算法解決旅行商問題擴展閱讀：

遺傳演算法的缺點

1、編碼不規范及編碼存在表示的不準確性。

2、單一的遺傳演算法編碼不能全面地將優化問題的約束表示出來。考慮約束的一個方法就是對不可行解採用閾值，這樣，計算的時間必然增加。

3、遺傳演算法通常的效率比其他傳統的優化方法低。

4、遺傳演算法容易過早收斂。

5、遺傳演算法對演算法的精度、可行度、計算復雜性等方面，還沒有有效的定量分析方法。

⑵ 做數學建模用到的遺傳演算法，難不難，要怎麼學要不要用專門的工具箱

要看你用遺傳演算法解決什麼問題，一般情況下，有兩個方向使用遺傳演算法，一是自己編寫遺傳演算法代碼解決問題，二是用Matlab遺傳演算法工具箱。前者可以學習王小平的《遺傳演算法——理論、應用與軟體實現》這本書，後者可以學習 雷英傑的《MATLAB遺傳演算法工具箱及應用》這本書，網上都可以找到電子版。
你要是用遺傳演算法解決旅行商問題這樣的組合優化問題，建議你自己編碼實現吧，網上可以找到很多代碼參考。

⑶ 利用遺傳演算法求解TSP問題 從北京出發 四個城市

作為一種模擬生物自然遺傳與進化過程的優化方法,遺傳演算法(GA)因其具有隱並行性、不需目標函數可微等特點,常被用於解決一些傳統優化方法難以解決的問題。旅行商問題(TSP)是典型的NP難題組合優化問題之一,且被廣泛應用於許多領域,所以研究遺傳演算法求解TSP具有重要的理論意義和應用價值。具有量子計算諸多特點的量子遺傳演算法(OGA)作為—新的概率進化演算法,在解決實際問題時,其高度並行性能極大地提高計算效率,因而研究OGA求解TSP同樣有重要的價值;而將具有遍歷性和隨機性的「混沌」概念引入量子遺傳演算法求解較復雜的組合優化問題又為求解優化問題開拓了一個新的思路。

⑷ 遺傳演算法tsp問題求解~80高分求解還會繼續加分

遺傳演算法GA
遺傳演算法：
旅行商問題(traveling saleman problem,簡稱tsp)：
已知n個城市之間的相互距離，現有一個推銷員必須遍訪這n個城市，並且每個城市只能訪問一次，最後又必須返回出發城市。如何安排他對這些城市的訪問次序，可使其旅行路線的總長度最短？
用圖論的術語來說，假設有一個圖 g=(v,e)，其中v是頂點集，e是邊集，設d=(dij)是由頂點i和頂點j之間的距離所組成的距離矩陣，旅行商問題就是求出一條通過所有頂點且每個頂點只通過一次的具有最短距離的迴路。
這個問題可分為對稱旅行商問題(dij=dji,,任意i,j=1,2,3，…,n)和非對稱旅行商問題(dij≠dji,,任意i,j=1,2,3，…,n)。
若對於城市v={v1,v2,v3,…,vn}的一個訪問順序為t=(t1,t2,t3,…,ti,…,tn),其中ti∈v(i=1,2,3,…,n)，且記tn+1= t1，則旅行商問題的數學模型為：
min l=σd(t(i),t(i+1)) （i=1,…,n）
旅行商問題是一個典型的組合優化問題，並且是一個np難問題，其可能的路徑數目與城市數目n是成指數型增長的，所以一般很難精確地求出其最優解，本文採用遺傳演算法求其近似解。
遺傳演算法：
初始化過程：用v1,v2,v3,…,vn代表所選n個城市。定義整數pop-size作為染色體的個數，並且隨機產生pop-size個初始染色體，每個染色體為1到18的整數組成的隨機序列。
適應度f的計算：對種群中的每個染色體vi，計算其適應度，f=σd(t(i),t(i+1)).

評價函數eval(vi)：用來對種群中的每個染色體vi設定一個概率，以使該染色體被選中的可能性與其種群中其它染色體的適應性成比例，既通過輪盤賭，適應性強的染色體被選擇產生後台的機會要大，設alpha∈(0,1)，本文定義基於序的評價函數為eval(vi)=alpha*(1-alpha).^(i-1) 。[隨機規劃與模糊規劃]
選擇過程：選擇過程是以旋轉賭輪pop-size次為基礎，每次旋轉都為新的種群選擇一個染色體。賭輪是按每個染色體的適應度進行選擇染色體的。
step1 、對每個染色體vi,計算累計概率qi，q0=0;qi=σeval(vj) j=1,…,i;i=1,…pop-size.
step2、從區間(0,pop-size)中產生一個隨機數r；
step3、若qi-1<r<qi,則選擇第i個染色體 ；
step4、重復step2和step3共pop-size次，這樣可以得到pop-size個復制的染色體。
grefenstette編碼：由於常規的交叉運算和變異運算會使種群中產生一些無實際意義的染色體，本文採用grefenstette編碼《遺傳演算法原理及應用》可以避免這種情況的出現。所謂的grefenstette編碼就是用所選隊員在未選（不含淘汰）隊員中的位置，如：
8 15 2 16 10 7 4 3 11 14 6 12 9 5 18 13 17 1
對應：
8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1。
交叉過程：本文採用常規單點交叉。為確定交叉操作的父代，從 到pop-size重復以下過程：從[0，1]中產生一個隨機數r，如果r<pc ，則選擇vi作為一個父代。
將所選的父代兩兩組隊，隨機產生一個位置進行交叉，如：
8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1
6 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 1
交叉後為：
8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 1
6 12 3 5 6 8 5 6 3 7 3 4 3 2 4 2 2 1
變異過程：本文採用均勻多點變異。類似交叉操作中選擇父代的過程，在r<pm 的標准下選擇多個染色體vi作為父代。對每一個選擇的父代，隨機選擇多個位置，使其在每位置按均勻變異（該變異點xk的取值范圍為[ukmin,ukmax],產生一個[0，1]中隨機數r，該點變異為x'k=ukmin+r(ukmax-ukmin)）操作。如：
8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1
變異後：
8 14 2 13 10 6 3 2 2 7 3 4 5 2 4 1 2 1
反grefenstette編碼：交叉和變異都是在grefenstette編碼之後進行的，為了循環操作和返回最終結果，必須逆grefenstette編碼過程，將編碼恢復到自然編碼。
循環操作：判斷是否滿足設定的帶數xzome，否，則跳入適應度f的計算；是，結束遺傳操作，跳出。

//c++的程序
#include<iostream.h>
#include<stdlib.h>
template<class T>
class Graph
{
public:
Graph(int vertices=10)
{
n=vertices;
e=0;
}
~Graph(){}
virtual bool Add(int u,int v,const T& w)=0;
virtual bool Delete(int u,int v)=0;
virtual bool Exist(int u,int v)const=0;
int Vertices()const{return n;}
int Edges()const{return e;}
protected:
int n;
int e;
};
template<class T>
class MGraph:public Graph<T>
{
public:
MGraph(int Vertices=10,T noEdge=0);
~MGraph();
bool Add(int u,int v,const T& w);
bool Delete(int u,int v);
bool Exist(int u,int v)const;
void Floyd(T**& d,int**& path);
void print(int Vertices);
private:
T NoEdge;
T** a;
};
template<class T>
MGraph<T>::MGraph(int Vertices,T noEdge)
{
n=Vertices;
NoEdge=noEdge;
a=new T* [n];
for(int i=0;i<n;i++){
a[i]=new T[n];
a[i][i]=0;
for(int j=0;j<n;j++)if(i!=j)a[i][j]=NoEdge;
}
}
template<class T>
MGraph<T>::~MGraph()
{
for(int i=0;i<n;i++)delete[]a[i];
delete[]a;
}
template<class T>
bool MGraph<T>::Exist(int u,int v)const
{
if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==NoEdge)return false;
return true;
}
template<class T>
bool MGraph<T>::Add(int u,int v,const T& w)
{
if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]!=NoEdge){
cerr<<"BadInput!"<<endl;
return false;
}
a[u][v]=w;
e++;
return true;
}
template<class T>
bool MGraph<T>:delete(int u,int v)
{
if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==NoEdge){
cerr<<"BadInput!"<<endl;
return false;
}
a[u][v]=NoEdge;
e--;
return true;
}
template<class T>
void MGraph<T>::Floyd(T**& d,int**& path)
{
d=new T* [n];
path=new int* [n];
for(int i=0;i<n;i++){
d[i]=new T[n];
path[i]=new int[n];
for(int j=0;j<n;j++){
d[i][j]=a[i][j];
if(i!=j&&a[i][j]<NoEdge)path[i][j]=i;
else path[i][j]=-1;
}
}
for(int k=0;k<n;k++){
for(i=0;i<n;i++)
for(int j=0;j<n;j++)
if(d[i][k]+d[k][j]<d[i][j]){
d[i][j]=d[i][k]+d[k][j];
path[i][j]=path[k][j];
}
}
}
template<class T>
void MGraph<T>::print(int Vertices)
{
for(int i=0;i<Vertices;i++)
for(int j=0;j<Vertices;j++)
{

cout<<a[i][j]<<' ';if(j==Vertices-1)cout<<endl;
}
}
#define noEdge 10000
#include<iostream.h>
void main()
{
cout<<"請輸入該圖的節點數："<<endl;
int vertices;
cin>>vertices;
MGraph<float> b(vertices,noEdge);
cout<<"請輸入u,v,w:"<<endl;
int u,v;
float w;
cin>>u>>v>>w;
while(w!=noEdge){
//u=u-1;
b.Add(u-1,v-1,w);
b.Add(v-1,u-1,w);
cout<<"請輸入u,v,w:"<<endl;
cin>>u>>v>>w;
}
b.print(vertices);
int** Path;
int**& path=Path;
float** D;
float**& d=D;
b.Floyd(d,path);
for(int i=0;i<vertices;i++){
for(int j=0;j<vertices;j++){
cout<<Path[i][j]<<' ';
if(j==vertices-1)cout<<endl;
}
}
int *V;
V=new int[vertices+1];
cout<<"請輸入任意一個初始H-圈："<<endl;
for(int n=0;n<=vertices;n++){

cin>>V[n];
}
for(n=0;n<55;n++){
for(i=0;i<n-1;i++){
for(int j=0;j<n-1;j++)
{
if(i+1>0&&j>i+1&&j<n-1){
if(D[V[i]][V[j]]+D[V[i+1]][V[j+1]]<D[V[i]][V[i+1]]+D[V[j]][V[j+1]]){
int l;
l=V[i+1];V[i+1]=V[j];V[j]=l;
}
}
}
}
}
float total=0;
cout<<"最小迴路："<<endl;
for(i=0;i<=vertices;i++){

cout<<V[i]+1<<' ';
}
cout<<endl;
for(i=0;i<vertices;i++)
total+=D[V[i]][V[i+1]];
cout<<"最短路徑長度："<<endl;
cout<<total;
}

這個你 看得懂么？

⑸ 急求 蟻群混合遺傳演算法在matlab上的實現以解決TSP旅行商的問題 小弟感激不盡

建立m文件
function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)

%%-------------------------------------------------------------------------

%% 主要符號說明

%% 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; %i=j時不計算，應該為0，但後面的啟發因子要取倒數，用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 %開始時置0

J(Jc)=k;

Jc=Jc+1; %訪問的城市個數自加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); %cumsum，元素累加即求和

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); %開始距離為0，m*1的列向量

for i=1:m

R=Tabu(i,:);

for j=1:(n-1)

L(i)=L(i)+D(R(j),R(j+1)); %原距離加上第j個城市到第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); %開始時信息素為n*n的0矩陣

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);

%此次循環在路徑（i，j）上的信息素增量

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)); %找到最佳路徑（非0為真）

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,'r')

title('平均距離和最短距離') %標題

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)],'g')

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)],'g')

hold on

end

title('旅行商問題優化結果 ')

建m文件
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)],'g')

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)],'g')

hold on

end

title('TSP問題優化結果 ')

命令窗口運行
C=[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
];
m=31;Alpha=1;Beta=5;Rho=0.1;NC_max=200;Q=100;
[R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)

⑹ tSp Concorder演算法原理

tsp問題遺傳演算法將多目標按照線性加權的方式轉化為單目標，然後應用傳統遺傳演算法求解
其中w_i表示第i個目標的權重，f_k表示歸一化之後的第i個目標值。我們很容易知道，這類方法的關鍵是怎麼設計權重。比如，Random Weight Genetic Algorithm (RWGA) 採用隨機權重的方式，每次計算適應度都對所有個體隨機地產生不同目標的權重，然後進行選擇操作。Vector-Evaluated Genetic Algorithm (VEGA) 也是基於線性加權的多目標遺傳演算法。如果有K個目標，VEGA 會隨機地將種群分為K個同等大小子種群，在不同的子種群按照不同的目標函數設定目標值，然後再進行選擇操作。VEGA 實質上是基於線性加權的多目標遺傳演算法。VEGA 是第一個多目標遺傳演算法，開啟了十幾年的研究潮流。
1.TSP問題是指假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。本文使用遺傳演算法解決att30問題，即30個城市的旅行商問題。旅行商問題是一個經典的組合優化問題。一個經典的旅行商問題可以描述為：一個商品推銷員要去若干個城市推銷商品，該推銷員從一個城市出發，需要經過所有城市後，回到出發地。應如何選擇行進路線，以使總的行程最短。從圖論的角度來看，該問題實質是在一個帶權完全無向圖中，找一個權值最小的Hamilton迴路。由於該問題的可行解是所有頂點的全排列，隨著頂點數的增加，會產生組合爆炸，它是一個NP完全問題。TSP問題可以分為對稱和不對稱。在對稱TSP問題中，兩座城市之間來回的距離是相等的，形成一個無向圖，而不對稱TSP則形成有向圖。對稱性TSP問題可以將解的數量減少了一半。所以本次實驗的TSP問題使用att48數據，可在tsplib中下載數據包。演化演算法是一類模擬自然界遺傳進化規律的仿生學演算法，它不是一個具體的演算法，而是一個演算法簇。遺傳演算法是演化演算法的一個分支，由於遺傳演算法的整體搜索策略和優化計算是不依賴梯度信息，所以它的應用比較廣泛。我們本次實驗同樣用到了遺傳演算法（用MATLAB編寫）來解決TSP問題。