遗传算法在tsp问题上的应用

❶ 遗传算法解决tsp问题 为什么要交叉和变异

参考答案：
第一种是定值,一般而言,交叉概率在0.9-0.97之间任取,变异概率在0.1-0.001之间任取；第回二种是自适应取,按交答叉或变异个体的适应度值以及当代的平均适应度值计算,每代的个体都不一样,相关公式可以查资料得到.
谢谢采纳

❷ 利用遗传算法求解TSP问题 从北京出发 四个城市

太复杂了
还是找专业的吧

❸ 遗传算法解决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．遗传算法在网络分析中的应用

遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。

遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。

❹ 自适应遗传算法在求解TSP问题中的应用研究

利用基于分区搜索的自适应遗传算法求解TSP问题
江金龙,薛云灿,冯骏
为了提高用遗传算法求解旅行商问题(TSP)的收敛速度,结合自适应算子和父子竞争策略等优化思想,提出了基于分区搜索的自适应遗传算法.该算法将整个搜索区域分成若干个较小的搜索区域,先进行局部搜索,在得到局部较优的基因组合后,再进行全区域搜索,不但提高了遗传算法的收敛速度,而且改进了变异算子的操作性能.通过TSP问题的求解表明,基于分区搜索的自适应遗传算法是一种稳定、高效的优化算法.
【作者单位】：河海大学计算机及信息工程学院;河海大学计算机及信息工程学院;河海大学计算机及信息工程学院 江苏常州213022九江学院电子工程学院;江西九江332005;江苏常州213022;江苏常州213022
【关键词】：遗传算法;分区搜索;旅行商问题
【基金】：湖北省自然科学基金资助项目(2004ABA018);河海大学常州校区创新基金资助项目(2005B002-01)
【分类号】：TP18
【DOI】：cnki:ISSN:1009-1130.0.2005-03-001
【正文快照】：
1分区搜索自适应遗传算法的基本思想旅行商问题(Traveling Salesm an Problem,TSP)是指旅行商从某城市出发,在遍历N个城市后又回到出发点,且每个城市只经过一次,求旅行商行程最短的问题[1].TSP是一个N P难题,其可能的路径数目随城市数N的增加呈指数型增长.如果是对称TSP问题,则共有0.5(N-1)!种可能路线,如果是非对称TSP问题,可能的路线还会加倍.许多学者运用遗传算法的不同控制方法来求解TSP的最优解[2-3],但简单遗传算法(Sim ple G enetic A lgorithm,SG A)的收敛速度慢,且易陷入局部最优解.如果能找到某些局部优良的基因组合(…
推荐 CAJ下载 PDF下载
CAJViewer7.0阅读器支持所有CNKI文件格式，AdobeReader仅支持PDF格式

Solving Traveling Salesman Problem by the Adaptive Genetic Algorithm Based on the Regional Search
JIANG Jin-long1;2;XUE Yun-can1;FENG Jun1(1.College of Computer & Information Engineering;Hohai Univ.;Changzhou 213022;China;2.College of Electronic Engineering;Jiujiang Univ.;Jiujiang 332005;China)
To increase the convergence speed of the genetic algorithm in solving the traveling salesman problem(TSP),combined with adaptive operators and competitive strategy between parents and their children,an adaptive genetic algorithm based on the regional search is proposed. This algorithm divides the global space into regional space and makes the regional search first. The global space search is carried out based on the better local gene sequences obtained from the regional search,so as to improve the search speed. Moreover,this algorithm improves the mutation performance at the same time. The TSP simulations show that the improved algorithm is a steady and efficient optimal search method.
【Keyword】：genetic algorithms;regional search;traveling salesman problem(TSP)

❺ 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问题怎么调用实际距离

不知道，你网络吧

❼ 遗传算法求解tsp问题的matlab程序

把下面的（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问题上的对比分析

【原创】比遗传算法性能更好：蚁群算法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，C#，C++，Matlab都行。这个网址提供的算法行，可以运行，是30个城市，但是你要自行选择交叉概率，突变概率等。种群尽量要大：1000以上；

交叉概率要大：0.7以上；

突变概率要小：0.3以下；

最优个体我建议保存一个，因为你要看最好结果吗

剩下的呢自己测试；

结果（我自己取的参数）：

算法终止条件A.最多迭代次数：1000

算法终止条件B.最短路径连续保持不变代数：20

种群个体数量：500

交叉概率：0.7

交叉部分占整体的百分比：50

突变概率：0.2

最优个体保留最大数量：1

选择操作最优个体被保护概率：0.8

交叉操作最优个体被保护概率：0.8

突变操作最优个体被保护概率：0.8

得出的结果：Rlength=1.0213e+003，结果如图