C语言遗传算法在求解TSP问题 毕业论文+源代码

目

录

摘要

I

Abstract

II

引

言

1

第一章

基本遗传算法

2

11

遗传算法的产生及发展

3

12

基本原理

3

13

遗传算法的特点

3

14

基本遗传算法描述

5

15

遗传算法构造流程

6

第二章

遗传算法的实现技术

6

21

编码方法

7

211

二进制编码

7

212

格雷码编码

7

213

符点数编码

8

214

参数编码

8

22

适应度函数

10

23

选择算子

10

24

交叉算子

10

241

单点交叉算子

10

242

双点交叉算子

11

243

均匀交叉算子

11

244

部分映射交叉

11

245

顺序交叉

12

25

变异算子

12

26

运行参数

12

27

约束条件的处理方法

13

28

遗传算法流程图

14

第三章

遗传算法在TSP上的应用

15

31

TSP问题的建模与描述

15

32

对TSP的遗传基因编码方法

16

33

针对TSP的遗传操作算子

17

331

选择算子

17

3311

轮盘赌选择

17

3312

最优保存策略选择

17

332

交叉算子

20

3321

单点交叉

20

3322

部分映射交叉

21

333

变异算子

23

34

TSP的混和遗传算法

26

第四章

实例分析

27

41

测试数据

27

42

测试结果

27

43

结果分析

27

摘

要

TSP

(Traveling

Salesman

Problem)旅行商问题是一类典型的NP完全问题，遗传算法是解决NP问题的一种较理想的方法。文章首先介绍了基本遗传算法的基本原理、特点及其基本实现技术；接着针对TSP

问题，论述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子变异算子这三种算子）等方面的应用情况，分别指出几种常用的编码方法的优点和缺点，并且结合TSP的运行实例详细分析了基本遗传算法的4个运行参数群体大小、遗传算法的终止进化代数、交叉概率、变异概率，对遗传算法的求解结果和求解效率的影响，经过多次的测试设定出了它们一组比较合理的取值。最后，简单说明了混合遗传算法在求解TSP问题中的应用并对遗传算法解决TSP问题的前景提出了展望。

关键词：TSP

遗传算法

遗传算子

编码

@@@需要的话按我的名字找我吧

最近研究了一下遗传算法，因为要用遗传算法来求解多元非线性模型。还好用遗传算法的工具

箱予以实现了，期间也遇到了许多问题。借此与大家分享一下。

首先，我们要熟悉遗传算法的基本原理与运算流程。

基本原理：遗传算法是一种典型的启发式算法，属于非数值算法范畴。它是模拟达尔文的自然

选择学说和自然界的生物进化过程的一种计算模型。它是采用简单的编码技术来表示各种复杂

的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定

搜索的方向。遗传算法的操作对象是一群二进制串（称为染色体、个体），即种群，每一个染

色体都对应问题的一个解。从初始种群出发，采用基于适应度函数的选择策略在当前种群中选

择个体，使用杂交和变异来产生下一代种群。如此模仿生命的进化进行不断演化，直到满足期

望的终止条件。

运算流程：

Step 1：对遗传算法的运行参数进行赋值。参数包括种群规模、变量个数、交叉概率、变异概

率以及遗传运算的终止进化代数。

Step 2：建立区域描述器。根据轨道交通与常规公交运营协调模型的求解变量的约束条件，设

置变量的取值范围。

Step 3：在Step 2的变量取值范围内，随机产生初始群体，代入适应度函数计算其适应度值。

Step 4：执行比例选择算子进行选择操作。

Step 5：按交叉概率对交叉算子执行交叉操作。

Step 6：按变异概率执行离散变异操作。

Step 7：计算Step 6得到局部最优解中每个个体的适应值，并执行最优个体保存策略。

Step 8：判断是否满足遗传运算的终止进化代数，不满足则返回Step 4，满足则输出运算结果

。

其次，运用遗传算法工具箱。

运用基于Matlab的遗传算法工具箱非常方便，遗传算法工具箱里包括了我们需要的各种函数库

。目前，基于Matlab的遗传算法工具箱也很多，比较流行的有英国设菲尔德大学开发的遗传算

法工具箱GATBX、GAOT以及Math Works公司推出的GADS。实际上，GADS就是大家所看到的

Matlab中自带的工具箱。我在网上看到有问为什么遗传算法函数不能调用的问题，其实，主要

就是因为用的工具箱不同。因为，有些人用的是GATBX带有的函数，但MATLAB自带的遗传算法

工具箱是GADS，GADS当然没有GATBX里的函数，因此运行程序时会报错，当你用MATLAB来编写

遗传算法代码时，要根据你所安装的工具箱来编写代码。

以GATBX为例，运用GATBX时，要将GATBX解压到Matlab下的toolbox文件夹里，同时，set path

将GATBX文件夹加入到路径当中。

最后，编写Matlab运行遗传算法的代码。

这块内容主要包括两方面工作：1、将模型用程序写出来（M文件），即目标函数，若目标函

数非负，即可直接将目标函数作为适应度函数。2、设置遗传算法的运行参数。包括：种群规

模、变量个数、区域描述器、交叉概率、变异概率以及遗传运算的终止进化代数等等。

为方便大家理解，以下为例：

求解模型：TC=x1+2x2+3x3+4x4，-1<=x<=0

根据上面的求解模型，可以写出模型的M文件如下，即适应度函数

function TC=TotalCost(x)

TC=0;

for i=1:4

TC=TC+ix(i);

end

然后，可以利用遗传算法工具箱来写出遗传算法运行的主要程序，如下：

%定义遗传算法参数

NIND=20; %个体数目

MAXGEN=200; %最大遗传代数

NVAR=4; %变量维数

PRECI=20; %变量的二进制位数

GGAP=09; %代沟

trace=zeros(MAXGEN,2); %算法性能跟踪

%建立区域描述器

FieldD=[rep(PRECI,[1,NVAR]);rep([-1;0],[1,NVAR]);rep([1;0;1;1],[1,NVAR])];

Chrom=crtbp(NIND,NVARPRECI); %创建初始种群

gen=0; %代计数器

ObjV=TotalCost(bs2rv(Chrom,FieldD)); %计算初始种群个体的目

标函数值

while gen<MAXGEN,

FitnV=ranking(ObjV); %分配适应度值

SelCh=select('sus',Chrom,FitnV,GGAP); %选择

SelCh=recombin('xovsp',SelCh,07); %重组

SelCh=mut(SelCh,007); %变异

ObjVSel=TotalCost(bs2rv(SelCh,FieldD)); %计算子代目标函数值

[Chrom ObjV]=reins(Chrom,SelCh,1,1,ObjV,ObjVSel); %重插入

gen=gen+1;

%输出最优解及其对应的10个变量的十进制值

[Y,I]=min(ObjVSel);

Y,X=bs2rv(Chrom(I,:),FieldD);

trace(gen,1)=min(ObjV);

trace(gen,2)=sum(ObjV)/length(ObjV);

end

plot(trace(:,1));hold on;

plot(trace(:,2),'-');grid;

legend('种群均值的变换','最优解的变化');

显然，根据模型的特征，最优解应该是-10，自变量分别取-1，-1，-1，-1。大家可以安装

GATBX，在Matlab中建立目标函数的M文件以及遗传算法主程序的文件来进行试验。

希望以上内容对学习和运用遗传算法的同仁有所帮助，因为本人也是初学，因此有不详之处请

见谅。

////////////////////////////////////////////////////

matlab遗传算法工具箱函数及实例讲解（转引）

gaotv5

核心函数：

(1)function [pop]=initializega(num,bounds,eevalFN,eevalOps,options)--初始种群的生

成函数

输出参数

pop--生成的初始种群

输入参数

num--种群中的个体数目

bounds--代表变量的上下界的矩阵

eevalFN--适应度函数

eevalOps--传递给适应度函数的参数

options--选择编码形式(浮点编码或是二进制编码)[precision F_or_B],如

precision--变量进行二进制编码时指定的精度

F_or_B--为1时选择浮点编码，否则为二进制编码,由precision指定精度)

(2)function [x,endPop,bPop,traceInfo] = ga(bounds,evalFN,evalOps,startPop,opts,

termFN,termOps,selectFN,selectOps,xOverFNs,xOverOps,mutFNs,mutOps)--遗传

算法函数

输出参数

x--求得的最优解

endPop--最终得到的种群

bPop--最优种群的一个搜索轨迹

输入参数

bounds--代表变量上下界的矩阵

evalFN--适应度函数

evalOps--传递给适应度函数的参数

startPop-初始种群

opts[epsilon prob_ops display]--opts(1:2)等同于initializega的options参数，第三

个参数控制是否输出，一般为0。如[1e-6 1 0]

termFN--终止函数的名称,如['maxGenTerm']

termOps--传递个终止函数的参数,如[100]

selectFN--选择函数的名称,如['normGeomSelect']

selectOps--传递个选择函数的参数,如[008]

xOverFNs--交叉函数名称表，以空格分开，如['arithXover heuristicXover

simpleXover']

xOverOps--传递给交叉函数的参数表，如[2 0;2 3;2 0]

mutFNs--变异函数表，如['boundaryMutation multiNonUnifMutation nonUnifMutation

unifMutation']

mutOps--传递给交叉函数的参数表,如[4 0 0;6 100 3;4 100 3;4 0 0]

注意matlab工具箱函数必须放在工作目录下

问题求f(x)=x+10sin(5x)+7cos(4x)的最大值，其中0<=x<=9

分析选择二进制编码，种群中的个体数目为10，二进制编码长度为20，交叉概率为095,

变异概率为008

程序清单

%编写目标函数

function[sol,eval]=fitness(sol,options)

x=sol(1);

eval=x+10sin(5x)+7cos(4x);

%把上述函数存储为fitnessm文件并放在工作目录下

initPop=initializega(10,[0 9],'fitness');%生成初始种群，大小为10

[x endPop,bPop,trace]=ga([0 9],'fitness',[],initPop,[1e-6 1

1],'maxGenTerm',25,'normGeomSelect',

[008],['arithXover'],[2],'nonUnifMutation',[2 25 3]) %25次遗传迭代

运算借过为：x =

78562 248553(当x为78562时，f（x）取最大值248553)

注：遗传算法一般用来取得近似最优解，而不是最优解。

遗传算法实例2

问题在－5<=Xi<=5,i=1,2区间内，求解

f(x1,x2)=-20exp(-02sqrt(05(x1^2+x2^2)))-exp(05(cos(2pix1)+cos

(2pix2)))+2271282的最小值。

分析种群大小10，最大代数1000，变异率01,交叉率03

程序清单

％源函数的matlab代码

function [eval]=f(sol)

numv=size(sol,2);

x=sol(1:numv);

eval=-20exp(-02sqrt(sum(x^2)/numv)))-exp(sum(cos(2pix))/numv)

+2271282;

%适应度函数的matlab代码

function [sol,eval]=fitness(sol,options)

numv=size(sol,2)-1;

x=sol(1:numv);

eval=f(x);

eval=-eval;

%遗传算法的matlab代码

bounds=ones(2,1)[-5 5];

[p,endPop,bestSols,trace]=ga(bounds,'fitness')

注：前两个文件存储为m文件并放在工作目录下，运行结果为

p =

00000 -00000 00055

大家可以直接绘出f(x)的图形来大概看看f（x）的最值是多少，也可是使用优化函数来验证。

matlab命令行执行命令：

fplot('x+10sin(5x)+7cos(4x)',[0,9])

evalops是传递给适应度函数的参数，opts是二进制编码的精度，termops是选择maxGenTerm结

束函数时传递个maxGenTerm的参数，即遗传代数。xoverops是传递给交叉函数的参数。mutops

是传递给变异函数的参数。

有两种方法，一种是用matlab自带的遗传算法工具箱；还有一种是自己编写遗传算法解决问题。第二种方法的话，网上可以找到很多遗传算法的matlab代码，我也可以提供。第一种的话，有一定的局限性。