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 think58 [资料来源：http://THINK58.com]
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  遗传算法  遗传算子   编码

第一章   基本遗传算法
1.1 遗传算法的产生及发展
最早美国Ｍichigan(密执安大学)的Holland教授提出，起源于60年代对自然和人工自适应系统的研究。70年代De Jong基于遗传算法的思想在计算机上进行了大量纯数值函数优化计算实验。在一系列研究工作的基础上80年代Goldberg进行总结归纳，形成了遗传算的基本框架。
主要以一些关键人物所做出的主要贡献见证了遗传算法的发展进程:  
1  J.H.Holland
   60年代提出在研究和设计人工自适应系统时,可以借鉴生物遗传的机制； 
 　 70年代初提出了遗传算法的基本定理－模式定理(Schema Theorem)，从而奠定了遗传算法的理论基础；　
80年代实现了第一个基于遗传算法的机器学系统－分类器系统(Classifier Systems),开创了基于遗传算法的机器学习的新概念。
2  J.D.Bagley
1967年在其博士论文中首次提出了：“遗传算法”一词，发展了复制、交叉、变异、显性、倒位等遗传算子，创立了自适应遗传算法的概念。
3  K.A.De Jong
1975年在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验，树立了遗传算法的工作框架，定义了评价遗传算法性能的在线指标和离线指标。 think58好，好think58

4  D.J.Golgberg   
1989年出版了专著《搜索、优化和机器学习中的遗传算法(Genetic Algorithms in Search，Optimization and Machine Learning)》，系统总结了遗传算法的主要研究成果，全面而完整的论述了遗传算法的基本原理及其应用。
5  L.Davis  
1991年编辑出版了《遗传算法手册 (Handbook of Genetic Algorithms)》书中包括遗传算法在科学计算、工程技术和社会经济中的大量应用实例。
6  J.R.Koza 
    1992年将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程 (Genetic Programming) 的概念，并成功的将其提出的遗传编程应用于人工智能、机器学习符号处理等方面。
1.2 基本原理
遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法，由美国J.Holland教授提出，其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。它是一种全局化搜索算法，尤其适用于传统搜索算法难于解决的复杂和非线性问题。
选择(selection)算子、交叉(crossover)算子和变异(mutation)算子是遗传算法的3个主要操作算子。遗传算法中包含了如下5个基本要素:
(1) 对参数进行编码； think58 [来源：http://think58.com]
(2) 设定初始种群大小；
(3) 适应度函数的设计；
(4) 遗传操作设计；
(5) 控制参数设定(包括种群大小、最大进化代数、交叉率、变异率等)。
1.3 遗传算法的特点
(1) 遗传算法对优化问题没有太多的数学要求，而且只要知道目标函数的信息即可；
(2) 遗传算法采用的是启发性的知识智能搜索算法，在搜索高度空间复杂问题上比以往有更好的效果；
(3) 遗传算法是对问题参数或者变量编码群进行优化，而不是参数或变量本身；
(4) 遗传算法使用的选择、交叉、变异算子都是随机的；
1.4 基本遗传算法描述
基于对自然界中生物遗传与进化机理的模仿，针对不同的问题，很多学者设计了许多不同的编码方法来表示问题的可行解，开发出了许多种不同的遗传算子来模仿不同环境下生物遗传特性。这样，由不同的编码方法和不同的遗传算子就构成了各种不同的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。基于这个特点，Goldberg总结出了一种统一的最基本的遗传算法——基本遗传算法（Simple Genetic Algorithms，简称SGA）。基本遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。 think58好，好think58
基本遗传算法描述：
基本遗传算法只使用选择算子 ( Selection Operator)、交叉算子(Crossover Operator)、变异算子(Mutation Operator)这三种算子。
基本遗传算法可以形式化定义为一个八元组：SGA=(C,E,Po,M,φ,τ,ψ,T)
 C ——个体的编码方法；
 E ——个体适应度评价函数；
 Po——初始群体；
 M ——群体大小；
φ ——选择算子；
τ ——交叉算子；
ψ ——变异算子；
 T ——遗传运算终止条件。
遗传算法的应用步骤：
第一步： 确定决策变量及其各种约束条件，即确定出个体的表现型X和问题的解空间。
第二步： 建立优化模型，即确定出目标函数的类型(是求目标函数的最大值还是求目标函数的最小值？)及其数学描述形式或量化方法。
第三步：确定表示可行解的染色体编码方法，也即确定出个体的基因型X及遗传算法的搜索空间。
第四步：确定解码方法，即确定出个体基因型X到个体表现型X的对应关系转换方法。
第五步：确定个体适应度的量化评价方法，即确定出由目标函数值f(X)到个体适应度F(X)的转换规则。
第六步：设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法。
第七步：确定遗传算法的有关运行参数，即确定出遗传算法的M、T、Pc、Pm等参数。

内容来自think58 [版权所有：http://think58.com]

  copyright think58

[资料来源：THINK58.com]

第二章   遗传算法的实现技术
2.1  编码方法
在遗传算法中如何描述问题的可行解，即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称为编码。
编码是应用遗传算法时要解决的主要问题，也是设计遗传算法的一个关键步骤。编码方法除了决定个体染色体排列形式之外，还决定了个体从搜索空间的基因型变换到解空间的表现型时的解码方法，编码方法也影响到交叉算子、变异算子等遗传算子的运算方法。
针对一个具体问题，如何设计一个完美的编码方案一直是遗传算法的应用难点之一，也是遗传算法的一个重要研究方向。目前还没有一套既严密有完整的指导理论及评价准则能够指导我们设计编码方案。De Jong曾提出了两条操作性较强的实用编码原则：
编码原则一(有意义积木块编码原则):应使用能易于产生与所求问题相关的且具有低阶，短定义长度的编码方案。
编码原则二(最小字符集编码原则):应使用能使问题得到自然表示或描述的具有最小字符集的编码方案。
迄今为止人们已经提出了许多的编码方法，总的来说，可以分为三类：二进制编码方法，浮点数编码方法，符号编码方法。
2.1.1 二进制编码
二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集是由二进制符号0和0组成的二值符号集｛0，1｝，它所构成的个体基因型是一个二进制编码符号串。它有如下几个优点： copyright think58 [资料来源：THINK58.com]
(1)编码，解码简单易行。
(2)交叉，变异等遗传操作便于实现。
(3)符合最小字符集编码原则。
(4)便于利用模式定理对算法进行理论分析。
二进制编码符号串的长度与问题所要求的精度有关。
由于二进制不便于反映所求问题的结构特征，对于一些连续函数的优化问题等，也由于遗传运算的随机特性而使得其局部搜索能力较差，因而人们提出了用格雷码来对个体进行编码。 think58好，好think58 [资料来源：http://THINK58.com]

2.1.2 格雷码编码
格雷码，连续的两个整数所对应的编码值之间只有一个码位不相同。格雷码有这样一个特点：任意两个整数的差是这两个整数所对应的海明距离（Hamming distance）。这个特点是遗传算法中使用格雷码进行个体编码的主要原因。格雷码编码方法的主要优点是：
(1)便于提高遗传算法的局部搜索能力。
(2)交叉，变异等遗传操作易于实现。
(3)符合最小字符集编码原则。
(4)便于用模式定理对算法进行理论分析。
假设一个二进制编码为 B=bnbn-1…b2b1，其对应的格雷码为 G=gngn-1…g2g1。格雷码到二进制码的转换公式：

内容来自think58 [资料来源：THINK58.com]

  
格雷码编码方法是二进制编码方法的一种变形，其编码精度与相同长度二进制编码方法的精度相同。
由于二进制编码存在着连续函数离散化时的映射误差，而且不便于反映所求问题的特定知识，因而人们提出了用符点数来对个体进行编码。
2.1.3 符点数编码
符点数编码方法:指个体的每个基因值用某一范围内的一个浮点数来表示个体的编码长度等于其决策变量的个数，个体变量的长度等于去决策变量的真实值，所以也叫真值编码方法．它有以下几个优点：
(1)适合于在遗传算法中表示范围较大的数。
(2)适合于精度较高的遗传算法。
(3)便于较大空间的遗传搜索。
(4)改善了遗传算法的复杂性，提高了运算效率。
(5)便于遗传算法与经典优化方法的混合使用。
(6)便于设计针对问题的专门知识的知识型遗传算子。
(7)便于处理复杂的决策变量约束条件。
符号编码方法是指个体染色体编码串中的基因值取自一个无数值含义，而只有代码含义的符号集．它的主要优点如下：
(1)符合有意义积木块编码原则。
(2)便于在遗传算法中利用所求解问题的专门知识。
(3)便于遗传算法与相近似算法之间的混合使用。
但对于使用符号编码方法的遗传算法，一般需要认真设计交叉、变异等遗传运算的操作方法，以满足问题的各种约束要求，这样才能提高算法的搜索性能。 copyright think58 [资料来源：http://THINK58.com]
最后，简要介绍一下参数编码方法。
2.1.4 参数编码
参数编码方法是对含有多个变量的个体进行编码的方法，包含两种编码方法：
多参数级联编码方法：将各个参数分别以某种编码方法进行编码，然后再将它们的编码按一定顺序联接在一起就组成了表示全部参数的个体编码。
多参数交叉编码方法：将各个参数中起主要作用的码位集中在一起。
2.2  适应度函数
在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对其生存环境的适应程度。对生存环境适应程度较高的物种将有更多的繁殖机会；而对生存环境适应度较低的物种，其繁殖的机会就相对较少，甚至会逐渐灭绝。适应度较高的个体遗传到下一代的概率就相对大一些；而适应度较低的个体遗传到下一代的概率就相对较小一些。度量个体适应度的函数就称为适应度函数。
根据个体的适应值，就可决定在此环境下的生存能力。个体适应度大小决定该个体被遗传到下一代群体中的概率。遗传算法仅使用所求问题的目标函数值就可以得到下一步的有关搜索信息。目标函数值的使用是通过评价个体适应度来体现的。
由于个体适应度大小决定该个体被遗传到下一代群体中的概率。评价个体适应度的一般过程：
(1)对个体编码串进行解码处理后，可得到个体的表现型。 think58.com [资料来源：THINK58.com]
(2)由个体的表现型可计算出对应个体的目标函数值。
(3)根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。
但是，在仅用适应度函数来计算个体适应度时,有些遗传算法收敛很快,有些遗传算法收敛很慢，因此在运行到不同的阶段时须对个体的适应度进行适当的扩大或缩小。
适应度尺度变换(Fitness Scaling):对个体的适应度进行适当的扩大或缩小变换。
个体适应度尺度变换的三种方法： 
线性尺度变换公式如下：
F＇=aF+b
F—原适应度； 
F＇—尺度变换后的新适应度；
a和b—系数。
乘幂尺度变换公式如下：
F＇=F ⁿ
幂指数n与所求解的问题有关。
指数尺度变换公式如下：
F＇=exp(-βF)
系数β决定了选择的强制性。
参考文献
[1]王小平，曹立明编著，<<遗传算法——理论、应用与软件实现>>，西安：西安交通大学出版社，2002.1
[2]周明，孙树编著，<<遗传算法原理及应用>>，北京：国防工业出版社，1999.6
[3]谢政，李建平编著，<<网络算法与复杂性理论>>，长沙：国防科技大学出版社，1995
[4]陈国良等，<<遗传算法及其应用>>，北京：人民邮电出版社，1995

内容来自think58

[来源：http://think58.com]

[5]刘勇等，<<非数值并行算法（二）>>——遗传算法，北京：科学出版社，1995
[6]刘值义等，<<遗传学>>，北京：人民教育出版社，1982

think58好，好think58

[来源：http://www.think58.com]

[资料来源：http://THINK58.com]