遗传算法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同样有重要的价值;而将具有遍历性和随机性的“混沌”概念引入量子遗传算法求解较复杂的组合优化问题又为求解优化问题开拓了一个新的思路。