本文目录索引 1，自然科学和理工学科有什么区别？ 2，大连理工大学计算方法 3，遗传算法和蚁群算法在求解TSP问题上的对比分析 4，遗传算法和蚁群算法的区别 5，遗传算法解决TSP问题 6，遗传算法求解tsp问题的matlab程序 7，应用遗传算法求解tsp问题程序有那
本文目录索引
- 1，自然科学和理工学科有什么区别？
- 2，大连理工大学计算方法
- 3，遗传算法和蚁群算法在求解TSP问题上的对比分析
- 4，遗传算法和蚁群算法的区别
- 5，遗传算法解决TSP问题
- 6，遗传算法求解tsp问题的matlab程序
- 7，应用遗传算法求解tsp问题程序有那个高手帮帮我啊谢谢啦
- 8，遗传算法tsp问题求解~80高分求解还会继续加分
- 9，TSP遗传算法的求问！！！！
1，自然科学和理工学科有什么区别？
理工有别，而且很明显： 理科是自然科学的理论研究；工科是自然科学在工程的应用。一个纯理论，一个面向应用。北京大学的理科全国第一，而清华大学的工科全国第一。 物理、化学、数学等研究理论的属于理科主要学习应用技术的属于工科，比如：土木工程、机械工程等比较特殊的是，计算机专业内部也分为理科方向和工科方向，理科方向也叫计算机科学，主要研究算法复杂度、程序设计语言原理、数据挖掘、形式语言与自动机理论、计算机体系结构；工科方向也叫计算机技术，主要研究图形图像处理、软件工程、软件体系结构、操作系统、数据库等等。。 人们总把理工合到一起说，是为了与文、农、医相区别。文、理、工、农、医是高校的五大重要基础领域。。
2，大连理工大学计算方法
计算方法又名数值分析，是为各种数学问题的数值解答研究提供最有效的算法。计算方法主要内容包括函数逼近论、数值微分、数值积分、误差分析等，常用方法有迭代法、差分法、插值法、有限元素法等，现代计算方法要求适应电子计算机的特点。随着计算机和计算方法的飞速发展，几乎所有学科都走向定量化和精确化，从而产生了一系列计算性的学科分支，如计算物理、计算化学、计算生物学、 计算地质学、计算气象学和计算材料学等， 计算数学中的数值计算方法则是解决“计算”问题的桥梁和工具。我们知道，计算能力是计算工具和计算方法的效率的乘积， 提高计算方法的效率与提高计算机硬件的效率同样重要。 科学计算已用到科学技术和社会生活的各个领域中。 数值计算方法，是一种研究并解决数学问题的数值近似解方法， 是在计算机上使用的解数学问题的方法，简称计算方法。 在科学研究和工程技术中都要用到各种计算方法。 例如，在航天航空、地质勘探、汽车制造、桥梁设计、 天气预报和汉字字样设计中都有计算方法的踪影。 计算方法既有数学类课程中理论上的抽象性和严谨性，又有实用性和实验性的技术特征， 计算方法是一门理论性和实践性都很强的学科。 在70年代，大多数学校仅在数学系的计算数学专业和计算机系开设计算方法这门课程。 随着计算机技术的迅速发展和普及， 现在计算方法课程几乎已成为所有理工科学生的必修课程。 计算方法的计算对象是微积分，线性代数，常微分方程中的数学问题。 内容包括：插值和拟合、数值微分和数值积分、求解线性方程组的直接法和迭代法、 计算矩阵特征值和特征向量和常微分方程数值解等问题。
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:aihuacheng@gmail.com
%% 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的巡游路径，
4，遗传算法和蚁群算法的区别
遗传算法(Genetic Algorithm，GA)是由Holland J．H．于20世纪70年代提出的一种优化方法，其最优解的搜索过程模拟达尔文的进化论和“适者生存”的思想。
蚁群算法(Ant Colony Optimization, ACO)，是一种用来在图中寻找优化路径的机率型算法。
两种算法从概念上都属于随机优化算法，遗传算法是进化算法，主要通过选择、变异和交叉算子，其中每个基因是由二进制串组成；蚁群算法是基于图论的算法，通过信息素选择交换信息。
5，遗传算法解决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．遗传算法在网络分析中的应用
遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。
遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。
6，遗传算法求解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]);
7，应用遗传算法求解tsp问题程序有那个高手帮帮我啊谢谢啦
#include
#include
#include
#include
#include
#include
#include
using namespace std;
float pcross = 0.85; //交叉率
float pmutation = 0.1; //变异率
int popsize = 300; //种群大小
const int lchrom = 20; //染色体长度
int gen; //当前世代
int maxgen = 100; //最大世代数
int run; //当前运行次数
int maxruns =10; //总运行次数
float max_var = 9 ; //路径最大连接开销!!
//基因定义(一个城市)
struct Gene
{
string name;
map linkCost; //该城市到其它城市的路程开销
};
//染色体定义(到各城市顺序的一种组合)
struct Chrom
{
vector chrom_gene; //染色体（到各城市去的顺序）
float varible; //路程总开销
float fitness; //个体适应度
};
//种群定义
struct Pop
{
vector pop_chrom; //种群里的染色体组
float sumfitness; //种群中个体适应度累计
};
Pop oldpop; //当前代种群
Pop newpop; //新一代种群
vector genes(lchrom); //保存全部基因
//产生一个随机整数(在low和high之间)
inline int randomInt(int low,int high)
{
if(low==high)
return low;
return low+rand()%(high-low+1);
}
//计算一条染色体的个体适应度
inline void chromCost(Chrom& chr)
{
float sum=0;
for(int i=0;i<chr.chrom_gene.size()-1;i++)
{
sum += (chr.chrom_gene[i])->linkCost[chr.chrom_gene[i+1]];
}
sum += (chr.chrom_gene.front())->linkCost[chr.chrom_gene.back()];
chr.varible=sum;
chr.fitness=max_var*(lchrom) - chr.varible;
}
//计算一个种群的个体适应度之和
inline void popCost(Pop &pop)
{
float sum=0;
for(int i=0;i<pop.pop_chrom.size();i++)
{
sum+=pop.pop_chrom[i].fitness;
}
pop.sumfitness = sum;
}
void outChrom(Chrom& chr);
//随机初始化一条染色体
inline void initChrom(Chrom& chr)
{
vector tmp(lchrom);
for(int i=0;i<lchrom;i++)
tmp[i]=i;
int choose;
while(tmp.size()>1)
{
choose=randomInt(0,tmp.size()-1);
chr.chrom_gene.push_back(&genes[tmp[choose]]);
tmp.erase(tmp.begin()+choose);
}
chr.chrom_gene.push_back(&genes[tmp[0]]);
chromCost(chr);
}
//随机初始化种群
inline void initpop(Pop& pop)
{
pop.pop_chrom.reserve(popsize);
Chrom tmp;
tmp.chrom_gene.reserve(lchrom);
for(int i=0;i<popsize;i++)
{
initChrom(tmp);
pop.pop_chrom.push_back(tmp);
tmp.chrom_gene.clear();
}
popCost(pop);
}
//轮盘赌选择,返回种群中被选择的个体编号
inline int selectChrom(const Pop& pop)
{
float sum = 0;
float pick = float(randomInt(0,1000))/1000;
int i = 0;
if(pop.sumfitness!=0)
{
while(1)
{
sum += pop.pop_chrom[i].fitness/pop.sumfitness;
i++;
if( (sum > pick) || i==pop.pop_chrom.size()-1)
return i-1; }
}
else
return randomInt(0,pop.pop_chrom.size()-2);
}
//精英策略，返回最优秀的一条染色体
inline int chooseBest(const Pop& pop)
{ int choose = 0;
float best = 0;
for(int i = 0;i< pop.pop_chrom.size();i++)
{ if(pop.pop_chrom[i].fitness > best)
{ best = pop.pop_chrom[i].fitness;
choose = i;}
}
return choose；}
//染色体交叉操作,由两个父代产生两个子代(顺序交叉OX)
inline void crossover(Chrom& parent1,Chrom& parent2,Chrom& child1,Chrom& child2)
{ child1.chrom_gene.resize(lchrom);
child2.chrom_gene.resize(lchrom);
vector::iterator v_iter,p1_beg,p2_beg,c1_beg,c2_beg,p1_end,p2_end,c1_end,c2_end;
p1_beg = parent1.chrom_gene.begin();
p2_beg = parent2.chrom_gene.begin();
c1_beg = child1.chrom_gene.begin();
c2_beg = child2.chrom_gene.begin();
p1_end = parent1.chrom_gene.end();
p2_end = parent2.chrom_gene.end();
c1_end = child1.chrom_gene.end();
c2_end = child2.chrom_gene.end();
vector v1(parent2.chrom_gene), v2(parent1.chrom_gene); //用于交叉的临时表
//随机选择两个交叉点
int pick1 = randomInt(1,lchrom-3);
int pick2 = randomInt(pick1+1,lchrom-2);
int dist = lchrom-1-pick2; //第二交叉点到尾部的距离
//子代保持两交叉点间的基因不变
copy(p1_beg+pick1, p1_beg+pick2+1, c1_beg+pick1);
copy(p2_beg+pick1, p2_beg+pick2+1, c2_beg+pick1);
//循环移动表中元素
rotate(v1.begin(), v1.begin()+pick2+1,v1.end());
rotate(v2.begin(), v2.begin()+pick2+1,v2.end());
//从表中除去父代已有的元素
for(v_iter = p1_beg+pick1; v_iter!=p1_beg+pick2+1; ++v_iter)
remove(v1.begin(),v1.end(),*v_iter);
for(v_iter = p2_beg+pick1; v_iter!=p2_beg+pick2+1; ++v_iter)
remove(v2.begin(),v2.end(),*v_iter);
//把表中元素复制到子代中
copy(v1.begin(), v1.begin()+dist, c1_beg+pick2+1);
copy(v1.begin()+dist, v1.begin()+dist+pick1, c1_beg);
copy(v2.begin(), v2.begin()+dist, c2_beg+pick2+1);
copy(v2.begin()+dist, v2.begin()+dist+pick1, c2_beg);
}
//染色体变异操作,随机交换两个基因
inline void mutation(Chrom& chr)
{
vector::iterator beg = chr.chrom_gene.begin();
int pick1,pick2;
pick1 = randomInt(0,lchrom-1);
do{
pick2 =randomInt(0,lchrom-1);
}while(pick1==pick2);
iter_swap(beg+pick1, beg+pick2);
}
//世代进化(由当前种群产生新种群)
void generation(Pop& oldpop,Pop& newpop)
{ newpop.pop_chrom.resize(popsize);
int mate1,mate2,j;
float pick;
float tmp;
Chrom gene1,gene2,tmp1,tmp2;
gene1.chrom_gene.resize(lchrom);
gene2.chrom_gene.resize(lchrom);
tmp1.chrom_gene.resize(lchrom);
tmp2.chrom_gene.resize(lchrom);
//将最佳染色体放入下一代
mate1 = chooseBest(oldpop);
newpop.pop_chrom[0] = oldpop.pop_chrom[mate1];
j = 1;
//产生两条新染色体
do{
int count = 0;
mate1 = selectChrom(oldpop);
mate2 = selectChrom(oldpop);
pick = float(randomInt(0,1000))/1000;
gene1= oldpop.pop_chrom[mate1];
gene2= oldpop.pop_chrom[mate1];
if(pick < pcross) //交叉操作
{
int count = 0;
bool flag1 = false;
bool flag2 = false;
while(1)
{
crossover(oldpop.pop_chrom[mate1],oldpop.pop_chrom[mate2],tmp1,tmp2);
chromCost(tmp1); //计算适应度
chromCost(tmp2);
if(tmp1.fitness > gene1.fitness)
{
gene1 = tmp1;
flag1 = true;}
if(tmp2.fitness > gene2.fitness)
{
gene2 = tmp2;
flag2 = true;
}
if((flag1==true && flag2==true) || count> 50)
{
newpop.pop_chrom[j] = gene1;
newpop.pop_chrom[j+1] = gene2;
break;
}
count++;
}
}
else
{
newpop.pop_chrom[j].chrom_gene = oldpop.pop_chrom[mate1].chrom_gene;
newpop.pop_chrom[j+1].chrom_gene = oldpop.pop_chrom[mate2].chrom_gene;
chromCost(newpop.pop_chrom[j]);
chromCost(newpop.pop_chrom[j+1]);
}
pick = float(randomInt(0,1000))/1000;
if(pick < pmutation) //变异操作
{
int count = 0;
do{
tmp = newpop.pop_chrom[j].fitness;
mutation(newpop.pop_chrom[j]);
chromCost(newpop.pop_chrom[j]); //计算适应度
count++;
}while(tmp > newpop.pop_chrom[j].fitness && count < 50);
}
pick = float(randomInt(0,1000))/1000;
if(pick < pmutation) //变异操作
{
int count = 0;
do{
tmp = newpop.pop_chrom[j+1].fitness;
mutation(newpop.pop_chrom[j+1]);
chromCost(newpop.pop_chrom[j+1]); //计算适应度
count++;
}while(tmp > newpop.pop_chrom[j+1].fitness && count < 50);
}
//chromCost(newpop.pop_chrom[j]); //计算适应度
//chromCost(newpop.pop_chrom[j+1]);
j += 2;
}while(j < popsize-1);
popCost(newpop); //计算新种群的适应度之和
}
//输出一条染色体信息
inline void outChrom(Chrom& chr)
{
cout<<endl<<"路径:";
for(int i=0;i<lchrom;i++)
{
coutname;
}
cout<<endl<<"回路总开销:"<<chr.varible<<endl;
cout<<"适应度:"<<chr.fitness<<endl;
}
int main()
{
cout<<"*************用遗传算法解决TSP(旅行商)问题******************"<<endl;
string names[lchrom]={"A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T"};//基因（城市）名称
//用矩阵保存各城市间的路程开销
float dist[lchrom][lchrom] ={{0, 1, 4, 6, 8, 1, 3, 7, 2, 9, 7, 3, 4, 5, 8, 9, 2, 8, 2, 8},{1, 0, 7, 5, 3, 8, 3, 4, 2, 4, 4, 6, 2, 8, 2, 9, 4, 5, 2, 1},{4, 7, 0, 3, 8, 3, 7, 9, 1, 2, 5, 8, 1, 8, 9, 4, 7, 4, 8, 4},{6, 5, 3, 0, 3, 1, 5, 2, 9, 1, 3, 5, 7, 3, 4, 7, 3, 4, 5, 2},
{8, 3, 8, 3, 0, 2, 3, 1, 4, 6, 3, 8, 4, 5, 2, 8, 1, 7, 4, 7},{1, 8, 3, 1, 2, 0, 3, 3, 9, 5, 4, 5, 2, 7, 3, 6, 2, 3, 7, 1},{3, 3, 7, 5, 3, 3, 0, 7, 5, 9, 3, 4, 5, 9, 3, 7, 3, 2, 8, 1},{7, 4, 9, 2, 1, 3, 7, 0, 1, 3, 4, 5, 2, 7, 6, 3, 3, 8, 3, 5},
{2, 2, 1, 9, 4, 9, 5, 1, 0, 1, 3, 4, 7, 3, 7, 5, 9, 2, 1, 7},{9, 4, 2, 1, 6, 5, 9, 3, 1, 0, 3, 7, 3, 7, 4, 9, 3, 5, 2, 5},{7, 4, 5, 3, 3, 4, 3, 4, 3, 3, 0, 5, 7, 8, 4, 3, 1, 5, 9, 3},{3, 6, 8, 5, 8, 5, 4, 5, 4, 7, 5, 0, 8, 3, 1, 5, 8, 5, 8, 3},
{4, 2, 1, 7, 4, 2, 5, 2, 7, 3, 7, 8, 0, 5, 7, 4, 8, 3, 5, 3},{5, 8, 8, 3, 5, 7, 9, 7, 3, 7, 8, 3, 5, 0, 8, 3, 1, 8, 4, 5},{8, 2, 9, 4, 2, 3, 3, 6, 7, 4, 4, 1, 7, 8, 0, 4, 2, 1, 8, 4},{9, 9, 4, 7, 8, 6, 7, 3, 5, 9, 3, 5, 4, 3, 4, 0, 4, 1, 8, 4},
{2, 4, 7, 3, 1, 2, 3, 3, 9, 3, 1, 8, 8, 1, 2, 4, 0, 4, 3, 7},{8, 5, 4, 4, 7, 3, 2, 8, 2, 5, 5, 5, 3, 8, 1, 1, 4, 0, 2, 6},{2, 2, 8, 5, 4, 7, 8, 3, 1, 2, 9, 8, 5, 4, 8, 8, 3, 2, 0, 4},{8, 1, 4, 2, 7, 1, 1, 5, 7, 5, 3, 3, 3, 5, 4, 4, 7, 6, 4, 0}};
//初始化基因(所有基因都保存在genes中)
int i,j;
for(i=0;i<lchrom;i++)
{
genes[i].name =names[i];
for(j=0;j<lchrom;j++)
{
genes[i].linkCost[&genes[j]] = dist[i][j];
}
}
//输出配置信息
cout<<"\n染色体长度:"<<lchrom<<"\n种群大小:"<<popsize<<"\n交叉率:"<<pcross<<"\n变异率:"<<pmutation;
cout<<"\n最大世代数:"<<maxgen<<"\n总运行次数:"<<maxruns<<"\n路径最大连接开销:"<<max_var<<endl;
//输出路径信息
cout<<endl<<" ";
for(i=0;i<lchrom;i++)
cout<<genes[i].name<<" ";
cout<<endl;
for(i=0;i<lchrom;i++)
{
cout<<genes[i].name<<":";
for(j=0;j<lchrom;j++)
{
cout<<genes[i].linkCost[&genes[j]]<<" ";
}
cout<<endl;
}
cout<<endl;
int best;
Chrom bestChrom; //全部种群中最佳染色体
bestChrom.fitness = 0;
float sumVarible = 0;
float sumFitness = 0;
//运行maxrns次
for(run = 1;run<=maxruns;run++)
{
initpop(oldpop); //产生初始种群
//通过不断进化，直到达到最大世代数
for(gen = 1;gen<=maxgen;gen++)
{
generation(oldpop,newpop); //从当前种群产生新种群
oldpop.pop_chrom.swap(newpop.pop_chrom);
oldpop.sumfitness = newpop.sumfitness;
newpop.pop_chrom.clear();
}
best = chooseBest(oldpop); //本次运行得出的最佳染色体
if(oldpop.pop_chrom[best].fitness > bestChrom.fitness)
bestChrom = oldpop.pop_chrom[best];
sumVarible += oldpop.pop_chrom[best].varible;
sumFitness += oldpop.pop_chrom[best].fitness;
cout<<run<<"次"<<"Best:";
outChrom(oldpop.pop_chrom[best]); //输出本次运行得出的最佳染色体
cout<<endl;
oldpop.pop_chrom.clear();
}
cout<<endl<<"一条最佳染色体:";
outChrom(bestChrom); //输出全部种群中最佳染色体
cout<<endl<<endl<<"最佳染色体平均开销:"<<sumVarible/maxruns;
cout<<endl<<"最佳染色体平均适应度:"<<sumFitness/maxruns<<endl;
system("PAUSE");
return 0;
}
上次做大作业的时候做的，可以运行的。有什么问题再问。
8，遗传算法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
#include
template
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 MGraph:public Graph
{
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
MGraph::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
MGraph::~MGraph()
{
for(int i=0;i<n;i++)delete[]a[i];
delete[]a;
}
template
bool MGraph::Exist(int u,int v)const
{
if(un-1||v>n-1||u==v||a[u][v]==NoEdge)return false;
return true;
}
template
bool MGraph::Add(int u,int v,const T& w)
{
if(un-1||v>n-1||u==v||a[u][v]!=NoEdge){
cerr<<"BadInput!"<<endl;
return false;
}
a[u][v]=w;
e++;
return true;
}
template
bool MGraph:delete(int u,int v)
{
if(un-1||v>n-1||u==v||a[u][v]==NoEdge){
cerr<<"BadInput!"<<endl;
return false;
}
a[u][v]=NoEdge;
e--;
return true;
}
template
void MGraph::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
void MGraph::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
void main()
{
cout<<"请输入该图的节点数："<<endl;
int vertices;
cin>>vertices;
MGraph 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;
}
这个你 看得懂么？
9，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)
下一篇：没有了
