1. 遺傳演算法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;
}
這個你 看得懂么？
2. 用遺傳演算法求解TSP問題能獲得最優解么
遺傳演算法屬於啟發式演算法的一種，啟發式演算法與精確演算法的區別之一就是不能得到最優解，但是可以得到次優解。
3. 遺傳演算法解決TSP問題
遺傳演算法在很多領域都得到應用；從神經網路研究的角度上考慮，最關心的是遺傳演算法在神經網路的應用。在遺傳演算法應用中，應先明確其特點和關鍵問題，才能對這種演算法深入了解，靈活應用，以及進一步研究開發。
一、遺傳演算法的特點
1．遺傳演算法從問題解的中集開始嫂索，而不是從單個解開始。
這是遺傳演算法與傳統優化演算法的極大區別。傳統優化演算法是從單個初始值迭代求最優解的；容易誤入局部最優解。遺傳演算法從串集開始搜索，復蓋面大，利於全局擇優。
2．遺傳演算法求解時使用特定問題的信息極少，容易形成通用演算法程序。
由於遺傳演算法使用適應值這一信息進行搜索，並不需要問題導數等與問題直接相關的信息。遺傳演算法只需適應值和串編碼等通用信息，故幾乎可處理任何問題。
3．遺傳演算法有極強的容錯能力
遺傳演算法的初始串集本身就帶有大量與最優解甚遠的信息；通過選擇、交叉、變異操作能迅速排除與最優解相差極大的串；這是一個強烈的濾波過程；並且是一個並行濾波機制。故而，遺傳演算法有很高的容錯能力。
4．遺傳演算法中的選擇、交叉和變異都是隨機操作，而不是確定的精確規則。
這說明遺傳演算法是採用隨機方法進行最優解搜索，選擇體現了向最優解迫近，交叉體現了最優解的產生，變異體現了全局最優解的復蓋。
5．遺傳演算法具有隱含的並行性
遺傳演算法的基礎理論是圖式定理。它的有關內容如下：
(1)圖式(Schema)概念
一個基因串用符號集{0，1，*}表示，則稱為一個因式；其中*可以是0或1。例如：H=1x x 0 x x是一個圖式。
(2)圖式的階和長度
圖式中0和1的個數稱為圖式的階，並用0(H)表示。圖式中第1位數字和最後位數字間的距離稱為圖式的長度，並用δ(H)表示。對於圖式H＝1x x0x x，有0(H)＝2，δ(H)＝4。
(3)Holland圖式定理
低階，短長度的圖式在群體遺傳過程中將會按指數規律增加。當群體的大小為n時，每代處理的圖式數目為0(n3)。
遺傳演算法這種處理能力稱為隱含並行性(Implicit Parallelism)。它說明遺傳演算法其內在具有並行處理的特質。
二、遺傳演算法的應用關鍵
遺傳演算法在應用中最關鍵的問題有如下3個
1．串的編碼方式
這本質是問題編碼。一般把問題的各種參數用二進制編碼，構成子串；然後把子串拼接構成「染色體」串。串長度及編碼形式對演算法收斂影響極大。
2．適應函數的確定
適應函數(fitness function)也稱對象函數(object function)，這是問題求解品質的測量函數；往往也稱為問題的「環境」。一般可以把問題的模型函數作為對象函數；但有時需要另行構造。
3．遺傳演算法自身參數設定
遺傳演算法自身參數有3個，即群體大小n、交叉概率Pc和變異概率Pm。
群體大小n太小時難以求出最優解，太大則增長收斂時間。一般n＝30-160。交叉概率Pc太小時難以向前搜索，太大則容易破壞高適應值的結構。一般取Pc=0.25-0.75。變異概率Pm太小時難以產生新的基因結構，太大使遺傳演算法成了單純的隨機搜索。一般取Pm＝0．01—0．2。
三、遺傳演算法在神經網路中的應用
遺傳演算法在神經網路中的應用主要反映在3個方面：網路的學習，網路的結構設計，網路的分析。
1．遺傳演算法在網路學習中的應用
在神經網路中，遺傳演算法可用於網路的學習。這時，它在兩個方面起作用
(1)學習規則的優化
用遺傳演算法對神經網路學習規則實現自動優化，從而提高學習速率。
(2)網路權系數的優化
用遺傳演算法的全局優化及隱含並行性的特點提高權系數優化速度。
2．遺傳演算法在網路設計中的應用
用遺傳演算法設計一個優秀的神經網路結構，首先是要解決網路結構的編碼問題；然後才能以選擇、交叉、變異操作得出最優結構。編碼方法主要有下列3種：
(1)直接編碼法
這是把神經網路結構直接用二進制串表示，在遺傳演算法中，「染色體」實質上和神經網路是一種映射關系。通過對「染色體」的優化就實現了對網路的優化。
(2)參數化編碼法
參數化編碼採用的編碼較為抽象，編碼包括網路層數、每層神經元數、各層互連方式等信息。一般對進化後的優化「染色體」進行分析，然後產生網路的結構。
(3)繁衍生長法
這種方法不是在「染色體」中直接編碼神經網路的結構，而是把一些簡單的生長語法規則編碼入「染色體」中；然後，由遺傳演算法對這些生長語法規則不斷進行改變，最後生成適合所解的問題的神經網路。這種方法與自然界生物地生長進化相一致。
3．遺傳演算法在網路分析中的應用
遺傳演算法可用於分析神經網路。神經網路由於有分布存儲等特點，一般難以從其拓撲結構直接理解其功能。遺傳演算法可對神經網路進行功能分析，性質分析，狀態分析。
遺傳演算法雖然可以在多種領域都有實際應用，並且也展示了它潛力和寬廣前景；但是，遺傳演算法還有大量的問題需要研究，目前也還有各種不足。首先，在變數多，取值范圍大或無給定范圍時，收斂速度下降；其次，可找到最優解附近，但無法精確確定最擾解位置；最後，遺傳演算法的參數選擇尚未有定量方法。對遺傳演算法，還需要進一步研究其數學基礎理論；還需要在理論上證明它與其它優化技術的優劣及原因；還需研究硬體化的遺傳演算法；以及遺傳演算法的通用編程和形式等。
4. 遺傳演算法和蟻群演算法在求解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的巡遊路徑，
5. TSP遺傳演算法的作用是什麼
你是問為什麼要用遺傳演算法求解TSP？那麼答案就是，TSP問題如果用窮舉的方法搜索，會由於可行解太多而無法在有效時間之內完成，而遺傳演算法則是不使用窮舉的方法之一。
如果你是想問為什麼要求解TSP，那麼就是因為兩個原因，一個是TSP本身是實際問題抽象而來的，而且和tsp近似的還有很多不同的最短路徑問題，都是實際生活中會出現的，不管是規劃人的路徑還是機械手臂的路徑，都會用到。第二個原因是tsp是NP完全問題，和很多其他問題一樣，都是NP完全的，這就意味著，只要其中一個問題解決了，另外的NP完全問題也能夠解決，所以研究它也具有理論價值。
6. 遺傳演算法在求解TSP問題中是如何編碼解碼的 二進制如何編碼 如何求解
路徑表示是按照城市的訪問順序排列的一種編碼方式，是最自然、簡單和符合邏輯的表示方法。然而，除非初始基因是固定的，否則這種編碼方式不具備唯一性。例如，旅程（5-1-7-8-9-4-6-2-3）與（1-7-8-9-4-6-2-3-5）表示的是同一條旅程，因為路徑表示法是遍歷了每一個節點，所以不會產生子迴路。
考慮到此次研究對象的初始基因是固定的，不會出現漏選，所以運用這種編碼方法。
初始種群可以隨機產生，也可以通過某種演算法生成，但需要保證群體的多樣性。在種群初始化時，需要可慮以下幾個方面的因素：
1、根據問題固有的知識，設法把握最優解所佔的空間在整個問題空間中的分布范圍，然後，在次分布范圍內設定初始群體。
2、隨機生成一定數目的個體，然後從中挑選出最好的個體加入群體。這一過程不斷進行迭代，直到初始種群中個體數達到了預先確定的規模。
親和度設置為1/f f為總路徑長度
此後根據城市序號在進行選擇，交叉，變異即可