遗传算法论文精品毕业设计完整版.docx

遗传算法论文精品毕业设计完整版.docx

《遗传算法论文精品毕业设计完整版.docx》由会员分享，可在线阅读，更多相关《遗传算法论文精品毕业设计完整版.docx（16页珍藏版）》请在冰点文库上搜索。

遗传算法论文精品毕业设计完整版

论文名称：

遗传算法

*******

学号：

***********

班级：

计算机科学与技术1班

院系：

信息与电气工程学院

日期：

2014年6月18日

摘要

智能搜索算法包括遗传算法、禁忌算法、模拟退火算法等。

其中遗传算法（GA）是人类从基因遗传的生物进化思想的启发下提出的，它是一种进化计算，进化计算实质上是自适应的机器学习方法，遗传算法根据基因遗传时候的变化，它在运算的时候也分为选择、交叉、变异三种行为。

它比盲目的搜索效率高的多，又比专门的针对特定问题的算法通用性强，它是一种于问题无关的求解模式。

但是遗传算法又有很大的不确定性，以及过早的收敛性，所以可以和其他算法一起使用来对问题求解。

关键词：

遗传算法；GA；实现；应用；改进

第一章引言

1．1搜索法

人工智能问题广义地说，都可以看作是一个问题求解问题，在问题的求解过程中，人们所面临的大多数现实问题往往没有确定性的算法，通常需要用搜索算法来解决。

搜索法是人工智能中问题的求解的基本方法，搜索法可大致分为有信息搜索和无信息搜索，约束满足问题和博弈问题的求解均可表述为搜索过程。

搜索法的本质是再状态空间中从问题的初始状态搜索到通向目标状态的路径。

当前的智能搜索算法本质上也是搜索法，如遗传算法、蚁群算法、神经网络等。

一般搜索可以根据是否使用启发式信息分为盲目搜素和启发式搜索，也可以根据问题的表示方式分为状态空间搜索和与/或树搜索。

盲目搜索一般是指从当前状态到目标状态需要走多少步或者并不知道每条路径的花费，所能做的只是可以区分出哪个是目标状态。

启发式搜索时在搜索过程中加入了与问题有关的启发式信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解并找到最优解。

很显然盲目搜索不如启发式搜索效率高，但是由于启发式搜索需要和问题本身特性有关的信息而对很多问题这些信息很少，或者根本就没有，或者很难抽取，所以盲目搜索仍然是很重要的搜索策略。

1.2遗传算法

进化计算（EvolutionaryComputation，EC）是在达尔文的进化论和孟德尔的遗传变异理论的基础上产生的一种在基因和种群层次上模拟自然界生物进化过程与机制的问题求解技术。

它主要包括

遗传算法（GeneticAlgorithm，GA）

进化策略（EvolutionaryStrategy,ES）

进化规划（EvolutionaryProgramming,EP）

遗传规划（GeneticProgramming,GP）

它将生物进化过程中的繁殖（Reproduction）变异（Mutation）竞争（Competition）选择（Selection）引入到了算法中。

从而诞生了遗传算法。

第二章遗传算法（GeneticAlgorithms，GA）

2.1遗传算法的基本概念

2.1.1遗传算法的由来

生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优良物种。

自然界生物进化过程是进化计算的生物学基础，它主要包括遗传（Heredity）、变异（Mutation）和进化（Evolution）理论。

遗传算法是根据生物进化思想而启发得出的一种全局优化算法。

遗传算法的概念最早是由BagleyJ.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的J.H.Holland所实行。

当时，其主要目的是说明自然和人工系统的自适应过程。

遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。

Darwin进化论最重要的是适者生存原理。

它认为每一物种在发展中越来越适应环境。

物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。

在环境变化时，只有那些能适应环境的个体特征方能保留下来。

Mendel遗传学说最重要的是基因遗传原理。

它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。

每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。

基因突变和基因杂交可产生更适应于环境的后代。

经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。

由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。

2.1.2遗传算法的原理

遗传算法的基本思想是从初始种群出发，采用优胜劣汰、适者生存的自然法则选择个体，并通过杂交、变异来产生新一代种群，如此逐代进化，直到满足目标为止。

遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码（后来发展出了整数编码、实数编码等）的串。

并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。

然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。

这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

根据进化术语，对群体执行的操作有三种：

1．选择（Selection）

这是从群体中选择出较适应环境的个体。

这些选中的个体用于繁殖下一代。

故有时也称这一操作为再生（Reproduction）。

由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生（differentialreproduction）。

2．交叉（Crossover）

这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。

3．变异（Mutation）

这是在选中的个体中，对个体中的某些基因执行异向转化。

在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。

2.1.3遗传算法涉及的基本因素

种群（Population）：

种群是指用遗传算法求解问题时，初始给定的多个解的集合。

遗传算法的求解过程是从这个子集开始的。

个体（Individual）：

个体是指种群中的单个元素，它通常由一个用于描述其基本遗传结构的数据结构来表示。

例如，可以用0、1组成的长度为l的串来表示个体。

染色体（Chromosome）：

染色体是指对个体进行编码后所得到的编码串。

染色体中的每1位称为基因，染色体上由若干个基因构成的一个有效信息段称为基因组。

适应度（fitness）：

借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。

适应度（Fitness）函数：

适应度函数是一种用来对种群中各个个体的环境适应性进行度量的函数。

它一般是一个实值函数，该函数就是遗传算法中指导搜索的评价函数。

其函数值是遗传算法实现优胜劣汰的主要依据。

遗传操作（GeneticOperator）：

遗传操作是指作用于种群而产生新的种群的操作。

标准的遗传操作包括以下3种基本形式：

选择（Selection）

杂交（Crosssover）

变异（Mutation）

2.2遗传算法的实现步骤

2.2.1遗传算法的流程框图，如图1所示：

图1：

基本遗传算法的算法流程图

2.2.2遗传算法的具体步骤，如：

图2所示

图2：

遗传算法的具体步骤

第1步.初始种群的产生：

可以随机产生（用编码方法表示）;种群的大小（依赖于计算机的计算能力和计算复杂度）。

第2步．编码方法：

编码方法有二进制编码（只允许出现01），顺序编码（编码不允许重复），实数编码（运算简单，但反映不出基因的特性），整数编码（编码可以重复）等。

第3步．适值函数:

在遗传算法中，适应函数是用来区分群体中个体好坏的标准，是算法演化过程的驱动力，同时也是进行自然选择的唯一依据。

第4步．遗传运算:

针对适值函数得到的适值概率，选择进行遗传的双亲进行杂交和变异以得到新的种群

第5步．选择策略（见下节）

第6步．停止准则:

可以人为的设定遗传进行的代数，或者设定计算终止的条件，如数据精确度等。

当停止准则满足，遗传算法终止。

2.2.3遗传算法中的选择策略

不同的选择策略将导致不同的选择压力，即下一代中父代个体的复制数目的不同分配关系。

一．转盘式选择

1.转盘式选择是基于适应值比例的选择中比较重要的选择策略。

2.先计算个体的相对适应值pi=

3.根据选择概率把一个圆盘分成N份

4.生成一个内的随机数r（0≤r≤1），若r（0≤r≤1），则选择个体i

从统计角度看，个体的适应度值越大，其对应的扇区的面积越大，被选中的可能性也越大。

这种方法有点类似于发放奖品使用的轮盘，并带有某种赌博的意思，因此亦被称为轮盘赌选择。

二．基于排名的选择

首先根据个体i的适应值在群体中的排名来分配其选择概率pi。

根据这个概率使用转盘选择

三．线性排名选择

线性排名选择方法是按适应值大小从好到坏依次排列为x1,x2,x3….xn，然后根据一个线性函数分配选择概率pi。

2.2.4遗传算子的设计

1.杂交算子

杂交运算是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。

分为单点杂交和双点杂交，均匀杂交和算术杂交等。

2.变异算子

变异运算是指将个体染色体编码串中的某些基因点上的基因值用的其它值得基因来替换，从而形成一个新的个体

遗传算法中使用变异算子主要有以下两个目的：

1）改善遗传算法的局部搜索能力

2）维持群体的多样性，防止出现早熟现象

对个体的每一个基因点，依变异概率pm指定其为变异点。

对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替，从而产生出一个新的个体。

2.2.5遗传算法的模式理论

在遗传算法中假定在给定的时间（代）t，一个特定的模式s在群体P（t）中包含有m个代表串。

每个串根据适应值的大小获得不同的复制概率。

模式s的代表串的数目随时间增长的幅度正比于模式s的适应值与群体平均适应值的比值。

即：

适应值高于群体平均值的模式在下一代的代表串数目将会增加，而适应值低于群体平均值的模式在下一代的代表串数目将会减少。

这样会逐渐优化种群，使其向问题的最优解靠近。

但是当个体形态很接近时，杂交算子会失去作用；此时变异算子有助于算法跳出局部最优，从而搜索到全局最优解。

第三章遗传算法的特点及应用

3.1遗传算法的特点

1．遗传算法从问题解的某个子集开始搜索，而不是从单个解开始。

这是遗传算法与传统优化算法的极大区别。

传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。

遗传算法从串集开始搜索，覆盖面大，利于全局择优。

2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。

由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。

遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。

3．遗传算法有极强的容错能力。

遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。

故而，遗传算法有很高的容错能力。

4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。

这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的覆盖。

5．遗传算法具有并行性。

遗传算法在操作上具有高度的并行性，对并行遗传算法的研究表明，只要通过保持多个群体和恰当地控制群体间的相互作用来模拟并行执行过程，即使不用并行计算机，我们也能提高算法的执行效率。

3.2遗传算法的应用

遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性。

所以，广泛应用于很多学科。

下面是遗传算法的一此主要应用领域：

1）函数优化

函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。

很多人构造出了各种各样的复杂形式的测试函数。

有连续函数也有离散函数，有凸函数也有凹函数，有低维函数也有高维函数，有确定函数也有随机函数，有单峰值函数也有多峰值函数等。

用这些几何特性各具特色的函数来评价遗传算法的性能，更能反映算法的本质效果而对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解。

而遗传算法却可以方便地得到较好的结果。

2）组合优化

随着问题规模的增大，组合优化问题的搜索空间也急剧扩大。

有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。

对这类复杂问题，人们已意识到应把主要精力放在寻求其满意解上，而遗传算法是寻求这种满意解的最佳工具之一。

实践证明，遗传算法已经在求解旅行商问题、背包问题、装箱问题、布局优化、图形划分问题等各种具有NP难度的问题得到成功的应用。

3）生产调度问题

生产调度问题在很多情况下建立起来的数学模难以精确求解，即使经过一些简化之后可以进行求解.也会因简化得太多而使得求解结果与实际相差甚远。

目前在现实生产中主要是靠一些经验来进行调度。

现在遗传算法已成为解决复杂调度问题的有效下具。

在单件生产车间调度、流水线生产间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。

4）自动控制

在自动控制领域中有很多与优化相关的问题需要求解。

遗传算法已在其中得到了初步的应用，并显示出良好的效果。

例如用遗传算法进行航空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等。

都显出了遗传算法在这此领域中应用的可能性。

5）遗传编程

1989年，美国Standford大学的Koza教授发展了遗传编程的概念,其基木思想是:

采用树型结构表示计算机程序,运用遗传算法的思想,通过自动生成计算机程序来解决问题。

虽然遗传编程的理论尚米成热,应用也有一此限制,但它已成功地应用于人工智能、机器学习等领域。

目前公开的遗传编程实验系统有十多个。

例如，Koza开发的ADF系统，While开发的GPELST系统等。

6）机器学习

学习能力是高级自适应系统所具备的能力之一，基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。

例如，遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地改进了模糊系统的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用于人工神经网络结构优化设计；分类器系统也在学习式多机器人路径规划系统中得到了成功的应用。

7）人工生命

人工生命是用计算机、机械等模拟或构造出的具有自然生物系统特有行为的人造系统。

自组织能力和自学习能力是人下生命的两大主要特征。

人工生命与遗传算法有着密切的关系。

基于遗传算法的进化模型是研究人工生命现象的重要基础理论。

虽然人工生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。

人工生命与遗传算法相辅相成，遗传算法为人工生命的研究提供一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。

而且遗传算法可以用来求解旅行商问题（TSP问题）、最大团问题等经典问题。

第四章遗传算法的缺点及发展

4.1遗传算法的缺点

1）早熟。

这是最大的缺点，即算法对新空间的探索能力是有限的，也容易收敛到局部最优解。

虽然在遗传算法中引入变异算子来解决运算陷入局部最优解的情况，但是由于变异概率很小（一般都小于5%）所以也不能完全克服这种缺陷

2）计算量大。

涉及到大量个体的计算，当问题复杂时，计算时间是个问题

3）处理规模小。

目前对于维数较高的问题，还是很难处理和优化的。

高维数的问题，编码难度大，编码长度长，存储和处理等都比较困难

4）稳定性差。

因为算法属于随机类算法，需要多次运算，结果的可靠性差，不能稳定的得到解。

由于算法可调的输入比较多，如种群数量、繁殖代数、交叉概率、变异概率等，导致算法的运算结果不稳定，若改动某个参数，前后得到的结果可能相差很大

4.2遗传算法的发展

遗传算法具有快速随机的全局搜索能力，但是对于系统中的反馈信息利用却无能为力，当求解到一定范围时往往做大量无意义的冗余迭代，求精确解效率低，所以可以结合蚁群算法的对最优路径的积累和更新，优势互补。

针对传统GA的选择策略，可以改进为先遗传再选择，这样，样本空间扩大

了，可供选择的个体增多了。

针对GA的缺陷，可以采取拒绝策略，修复策略，惩罚策略等来改进遗传算法以达到优化算法的目的。

第五章遗传算法代码实现

详细代码见附录

本程序主要实现了函数优化的功能。

体现了基本的遗传算法的思想，实现了遗传算法的选择、遗传、变异步骤。

程序设定了种群大小pop_size，编码长度L，交叉概率pc变异概率pm等，同时定义了适值和，与平均适值，还定义了停止准则：

繁殖代数为NG为20

运行结果：

由适度平均值逐渐增大，可以得到种群逐渐向最优解靠近。

但是最终结果却不确定，通过手工运算求得当f（x）取得最大值时候，x应取10，但多次运行结果都不相同，最好的一次种群个数为8时候其中有5个是等于9的，就是可以接近最优解，但是不一定能得到，而且如果改动任一个参数，最后结果都会相差很多，而且每次运行的结果都不尽相同，说明遗传算法不稳定，仍然需要改进。

附录遗传算法代码（GACode）

//遗传算法GA

#include

#include

#include

usingnamespacestd;

constintL=5;//定义编码的长度

intf（intx）//定义测试f（x）

{

intresult;

result=x*x*x-60*x*x+900*x+100;

returnresult;

}

intmain（intargc,char*argv[]）

{

inta（0）,b（32）;//定义x的定义域范围

constintpop_size=8;//定义种群大小

//intL;//指定编码的长度

constintNG=20;//指定种群最大的繁殖的代数

intt=0;//当前繁殖的代数

intp[pop_size];//定义种群

intq[pop_size];//定义繁殖种群即种群的下一代

srand（50）;//定义随机数生成的种子

doublesum;//适值总和

doubleavl_sum;//适度平均值

doublep_probability[pop_size];//适值概率

doublepp[pop_size];

doublepro;//定义随机生成的概率

floatpc=0.90;//定义交叉的概率

floatpm=0.05;//定义变异的概率

cout<<"初始的种群";

for（inti=0;i

{

p[i]=rand（）%31;

cout<

}

cout<

cout<

voidXover（int&,int&）;//声明交叉函数

//当停止准则不满足即繁殖代数没到最大代数,继续繁殖

while（t<=NG）

{

cout<<"繁殖的代数：

t="<

sum=0.0;

for（inti=0;i

{

q[i]=p[i];

cout<

}

cout<

for（inti=0;i

sum+=f（p[i]）;

avl_sum=sum/pop_size;

cout<<"sum="<

cout<<"适度平均值="<

for（inti=0;i

{

p_probability[i]=f（p[i]）/sum;

if（i==0）

{

pp[i]=p_probability[i];

cout<<"pp"<

}

else

{

pp[i]=p_probability[i]+pp[i-1];

cout<<"pp"<

}

//cout<<"p_probability"<

}

//选择双亲

for（inti=0;i

{

pro=rand（）%1000/1000.0;

if（pro>=pp[0]&&pro

p[i]=q[0];

elseif（pro>=pp[1]&&pro

p[i]=q[1];

elseif（pro>=pp[2]&&pro

p[i]=q[2];

elseif（pro>=pp[3]&&pro

p[i]=q[3];

elseif（pro>=pp[4]&&pro

p[i]=q[4];

else

p[i]=q[5];

}

//杂交算子

intr=0;

intz=0;

for（intj=0;j

{

pro=rand（）%1000/1000.0;

if（pro

{

++z;

if（z%2==0）

Xover（p[r],p[j]）;

else

r=j;

}

}

//变异算子

for（inti=1;i<=pop_size;i++）

for（intj=0;j

{

pro=rand（）%1000/1000.0;//在[0,1]区间产生随机数

if（pro

{

bitsetv（p[i]）;

v.flip（j）;

p[i]=v.to_ulong（）;

}

}

t++;

cout<

}

cout<<"最终结果：

";

for（inti（0）;i

{

cout<

}

cout<

return0;

}

//定义杂交操作

voidXover（int&a,int&b）

{

intpos;//随机生成杂交点即第几个分量进行相互交换

pos=rand（）%5+1;//在n个分量中，随机确定第pos个分量

intj,k;

j=pos;

k=pos;

bitsete（a）;

bitsetf（b）;//前pos个分量进行相互交换

bitsetg;

bits