遺傳演算法tsp問題

㈠ matlab用遺傳演算法解決TSP的問題，求幫助

把下面的（1）-（7）依次存成相應的.m文件，在（7）的m文件下運行就可以了
（1） 適應度函數fit.m
function fitness=fit(len,m,maxlen,minlen)
fitness=len;
for i=1:length(len)
fitness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.0001)).^m;
end
(2)個體距離計算函數 mylength.m
function len=myLength(D,p)
[N,NN]=size(D);
len=D(p(1,N),p(1,1));
for i=1:(N-1)
len=len+D(p(1,i),p(1,i+1));
end

end
(3)交叉操作函數 cross.m
function [A,B]=cross(A,B)
L=length(A);
if L<10
W=L;
elseif ((L/10)-floor(L/10))>=rand&&L>10
W=ceil(L/10)+8;
else
W=floor(L/10)+8;
end
p=unidrnd(L-W+1);
fprintf('p=%d ',p);
for i=1:W
x=find(A==B(1,p+i-1));
y=find(B==A(1,p+i-1));
[A(1,p+i-1),B(1,p+i-1)]=exchange(A(1,p+i-1),B(1,p+i-1));
[A(1,x),B(1,y)]=exchange(A(1,x),B(1,y));
end

end
(4)對調函數 exchange.m
function [x,y]=exchange(x,y)
temp=x;
x=y;
y=temp;

end
(5)變異函數 Mutation.m
function a=Mutation(A)
index1=0;index2=0;
nnper=randperm(size(A,2));
index1=nnper(1);
index2=nnper(2);
%fprintf('index1=%d ',index1);
%fprintf('index2=%d ',index2);

temp=0;
temp=A(index1);
A(index1)=A(index2);
A(index2)=temp;
a=A;
end
(6)連點畫圖函數 plot_route.m
function plot_route(a,R)
scatter(a(:,1),a(:,2),'rx');
hold on;
plot([a(R(1),1),a(R(length(R)),1)],[a(R(1),2),a(R(length(R)),2)]);
hold on;
for i=2:length(R)
x0=a(R(i-1),1);
y0=a(R(i-1),2);
x1=a(R(i),1);
y1=a(R(i),2);
xx=[x0,x1];
yy=[y0,y1];
plot(xx,yy);
hold on;
end

end
(7)主函數
clear;
clc;
%%%%%%%%%%%%%%%輸入參數%%%%%%%%
N=50; %%城市的個數
M=100; %%種群的個數
C=100; %%迭代次數
C_old=C;
m=2; %%適應值歸一化淘汰加速指數
Pc=0.4; %%交叉概率
Pmutation=0.2; %%變異概率
%%生成城市的坐標
pos=randn(N,2);
%%生成城市之間距離矩陣
D=zeros(N,N);
for i=1:N
for j=i+1:N
dis=(pos(i,1)-pos(j,1)).^2+(pos(i,2)-pos(j,2)).^2;
D(i,j)=dis^(0.5);
D(j,i)=D(i,j);
end
end
%%如果城市之間的距離矩陣已知，可以在下面賦值給D，否則就隨機生成

%%生成初始群體
popm=zeros(M,N);
for i=1:M
popm(i,:)=randperm(N);
end
%%隨機選擇一個種群
R=popm(1,:);

figure(1);
scatter(pos(:,1),pos(:,2),'rx');
axis([-3 3 -3 3]);
figure(2);
plot_route(pos,R); %%畫出種群各城市之間的連線
axis([-3 3 -3 3]);
%%初始化種群及其適應函數
fitness=zeros(M,1);
len=zeros(M,1);
for i=1:M
len(i,1)=myLength(D,popm(i,:));
end
maxlen=max(len);
minlen=min(len);
fitness=fit(len,m,maxlen,minlen);
rr=find(len==minlen);
R=popm(rr(1,1),:);
for i=1:N
fprintf('%d ',R(i));
end
fprintf('\n');
fitness=fitness/sum(fitness);

distance_min=zeros(C+1,1); %%各次迭代的最小的種群的距離
while C>=0
fprintf('迭代第%d次\n',C);
%%選擇操作
nn=0;
for i=1:size(popm,1)
len_1(i,1)=myLength(D,popm(i,:));
jc=rand*0.3;
for j=1:size(popm,1)
if fitness(j,1)>=jc
nn=nn+1;
popm_sel(nn,:)=popm(j,:);
break;
end
end
end
%%每次選擇都保存最優的種群
popm_sel=popm_sel(1:nn,:);
[len_m len_index]=min(len_1);
popm_sel=[popm_sel;popm(len_index,:)];

%%交叉操作
nnper=randperm(nn);
A=popm_sel(nnper(1),:);
B=popm_sel(nnper(2),:);
for i=1:nn*Pc
[A,B]=cross(A,B);
popm_sel(nnper(1),:)=A;
popm_sel(nnper(2),:)=B;
end
%%變異操作
for i=1:nn
pick=rand;
while pick==0
pick=rand;
end
if pick<=Pmutation
popm_sel(i,:)=Mutation(popm_sel(i,:));
end
end
%%求適應度函數
NN=size(popm_sel,1);
len=zeros(NN,1);
for i=1:NN
len(i,1)=myLength(D,popm_sel(i,:));
end
maxlen=max(len);
minlen=min(len);
distance_min(C+1,1)=minlen;
fitness=fit(len,m,maxlen,minlen);
rr=find(len==minlen);
fprintf('minlen=%d\n',minlen);
R=popm_sel(rr(1,1),:);
for i=1:N
fprintf('%d ',R(i));
end
fprintf('\n');
popm=[];
popm=popm_sel;
C=C-1;
%pause(1);
end
figure(3)
plot_route(pos,R);
axis([-3 3 -3 3]);

㈡ 遺傳演算法在求解TSP問題中是如何編碼解碼的 二進制如何編碼 如何求解

路徑表示是按照城市的訪問順序排列的一種編碼方式，是最自然、簡單和符合邏輯的表示方法。然而，除非初始基因是固定的，否則這種編碼方式不具備唯一性。例如，旅程（5-1-7-8-9-4-6-2-3）與（1-7-8-9-4-6-2-3-5）表示的是同一條旅程，因為路徑表示法是遍歷了每一個節點，所以不會產生子迴路。
考慮到此次研究對象的初始基因是固定的，不會出現漏選，所以運用這種編碼方法。
初始種群可以隨機產生，也可以通過某種演算法生成，但需要保證群體的多樣性。在種群初始化時，需要可慮以下幾個方面的因素：
1、根據問題固有的知識，設法把握最優解所佔的空間在整個問題空間中的分布范圍，然後，在次分布范圍內設定初始群體。
2、隨機生成一定數目的個體，然後從中挑選出最好的個體加入群體。這一過程不斷進行迭代，直到初始種群中個體數達到了預先確定的規模。
親和度設置為1/f f為總路徑長度

此後根據城市序號在進行選擇，交叉，變異即可

㈢ C語言遺傳演算法在求解TSP問題 畢業論文+源代碼

目
錄
摘要
I
Abstract
II
引
言
1
第一章
基本遺傳演算法
2
1.1
遺傳演算法的產生及發展
3
1.2
基本原理
3
1.3
遺傳演算法的特點
3
1.4
基本遺傳演算法描述
5
1.5
遺傳演算法構造流程
6
第二章
遺傳演算法的實現技術
6
2.1
編碼方法
7
2.1.1
二進制編碼
7
2.1.2
格雷碼編碼
7
2.1.3
符點數編碼
8
2.1.4
參數編碼
8
2.2
適應度函數
10
2.3
選擇運算元
10
2.4
交叉運算元
10
2.4.1
單點交叉運算元
10
2.4.2
雙點交叉運算元
11
2.4.3
均勻交叉運算元
11
2.4.4
部分映射交叉
11
2.4.5
順序交叉
12
2.5
變異運算元
12
2.6
運行參數
12
2.7
約束條件的處理方法
13
2.8
遺傳演算法流程圖
14
第三章
遺傳演算法在TSP上的應用
15
3.1
TSP問題的建模與描述
15
3.2
對TSP的遺傳基因編碼方法
16
3.3
針對TSP的遺傳操作運算元
17
3.3.1
選擇運算元
17
3.3.1.1
輪盤賭選擇
17
3.3.1.2
最優保存策略選擇
17
3.3.2
交叉運算元
20
3.3.2.1
單點交叉
20
3.3.2.2
部分映射交叉
21
3.3.3
變異運算元
23
3.4
TSP的混和遺傳演算法
26
第四章
實例分析
27
4.1
測試數據
27
4.2
測試結果
27
4.3
結果分析
27
摘
要
TSP
(Traveling
Salesman
Problem)旅行商問題是一類典型的NP完全問題，遺傳演算法是解決NP問題的一種較理想的方法。文章首先介紹了基本遺傳演算法的基本原理、特點及其基本實現技術；接著針對TSP
問題，論述了遺傳演算法在編碼表示和遺傳運算元（包括選擇運算元、交叉運算元變異運算元這三種運算元）等方面的應用情況，分別指出幾種常用的編碼方法的優點和缺點，並且結合TSP的運行實例詳細分析了基本遺傳演算法的4個運行參數群體大小、遺傳演算法的終止進化代數、交叉概率、變異概率，對遺傳演算法的求解結果和求解效率的影響，經過多次的測試設定出了它們一組比較合理的取值。最後，簡單說明了混合遺傳演算法在求解TSP問題中的應用並對遺傳演算法解決TSP問題的前景提出了展望。
關鍵詞：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;
}

這個你 看得懂么？

㈤ 在遺傳演算法解決Tsp問題中如何保持種群的數量不變啊

function f=fitness(fmin,fmax,froad)
%this function to computer the fitness this road
%this the f is 0 or 1 froad more less the f more posible 1
if fmin<fmax
f=1-(froad-fmin)/(fmax-fmin);
elseif fmin==fmax
f=1;
else
'error'
end

㈥ 遺傳演算法tsp 城市100個 種群個數應該是多少

個體基因數為100，建議種群數為100*（3~5）
遺傳代數為100*（8~10）

㈦ 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問題。

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

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