遗传算法.doc

______________________________________________________________________________________________________________
1 遗传算法
1.1 遗传算法的定义
遗传算法 (GeneticAlgorithm，GA)是近多年来发展起来的一种全新的全局优化算法，它是基于了生物遗传学的观点，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。它通过自然选择、遗传、复制、变异等作用机制，实现各个个体的适应性的提高，从而达到全局优化。遗传算法151解决一个实际问题通常都是从一个种群开始，而这个种群通常都是含有问题的一个集合。这个种群是由一定数目的个体所构成的，利用生物遗传的知识我们可以知道这些个体正好组成了我们知道的染色体，也就是说染色体是由一个个有特征的个体组成的。另外我们还知道，遗传算法是由染色体组成，而染色体是由基因组成，可以这么说，基因就决定了个体的特性，所以对于遗传算法的最开始的工作就需要进行编码工作。然后形成初始的种群，最后进行选择、交叉和变异的操作。
1.2遗传算法的重要应用
在现实应用中，遗传算法在很多领域得到很好的应用，特别是在解决多维并且相当困难的优化问题中时表现出了很大的优势。在遗传算法的优化问题的应用中，其中最为经典的应用就是我们所熟悉的函数优化问题，它也是对遗传算法的性能进行评价的最普遍的一种算法;另外的一个最重要的应用，也就是我们本文所研究的应用—组合优化问题，一般的算法很难解决组合优化问题的搜索空间不断扩大的局面，而组合优化问题正好是解决这种问题的最有效的方法之一，在本文的研究中，比如求解TSP问题、VRP问题等方面都得到了很好的应用;另外遗传算法在航空控制系统中的应用、在图像处理和模式识别的应用、在生产调度方面的应用以及在工人智能、人工生命和机器学习方面都得到了很好的应用。其实在当今的社会中，有关于优化方面的问题应用于各行各业中，因此有关于优化问题已经变得非常重要，它对于整个社会的发展来说都是一个不可改变的发展方向，也是社会发展的一个非常重要的需要。
1.3 遗传算法的特点
遗传算法不同于传统的搜索与优化方法，它是随着问题种类的不同以及问题规模的扩大，能以有限的代价来很好的解决搜索和优化的方法。它的特点[9]主要如下:
(1)智能性。应用遗传算法求解问题时，在编码方案、适应度函数以及遗传算子群定后，遗传算法能够利用进化过程中获得的信息自行组织搜索。它具有自组织、自适应和自学习的能力，因此，利用遗传算法的方法，可以解决那些复杂的非结构化的问题。
(2)群体搜索特性。遗传算法采用同时对搜索空间中的多个解进行评估的方法，同时处理群体中多个个体，这样就避免了传统方法中采用单点搜索时所产生的局部某个单峰的极值点。它使遗传算法具有较好的全局搜索的性能。
(3)不需要辅助信息。遗传算法不需要求导或者其他辅助的知识。而只是需要影响搜索方向的目标函数和适应度函数。
(4)遗传算法的本质并行性。它具有固定的并行性和并行计算的能力。
(5)遗传算法强调概率转化规则，而不是确定的转化规则。
(6)遗传算法具有可扩展的能力。它易于同其他的技术结合起来使用。
1.4 基本遗传操作
1）.编码
编码(Encoding)就是要把问题的参数或者解转化成为遗传中的染色体或者个体。遗传算法不能直接的处理解空间里的数据，因此，我们必须通过编码把把它们表示成遗传里的基因结构数据模型。在遗传算法编码过程中我们必须考虑编码规则:完备性、健壮性、非冗余性。 DeJong在文献[’。]里提出了两条非常实用的编码的方法:第一种方法被叫做有意义的积木块的方法;第二种方法被叫做最小的字符串的方法。前一种方法它在求解问题的过程中利用了低阶和短定义长度的模式，所以说它的实现过程很简单，很容易实现，而后一种方法则是通过对所求问题能够表示成最小的编码字符串，从而实现它的编码。对于实际应用问题，如果要寻求一种对某一个问题描述最为方便、遗传算法效率最高的编码方案，则必须通过对编码方法、交叉方法、变异方法等进行统一的考虑。遗传算法中编码的方法有好多种，比如:二进制编码方法、格雷码编码方法、符号编码方法、实数编码方法、多参数级联编码方法等。对于在实际应用中的不同问题，应选择相应或合适的编码方案。尤其在几年来，遗传算法在求解高维或者复杂优化问题的时候大多数采用实数编码方案。这是因为实数编码能够使得问题解的表示比较自然。而月很容易引入相关领域的知识，所以一说它的使用将是越来越广泛[”]。高遗传算法的计算效率和全局的收敛性。选择通常分为两步[‘3]:首先是计算适应度，可以通过按比例的适应度计算 (ProportionalFitnessAssignment)或基于排序的适应度计算(Rank一 basedFitnessAssignment)等方法;其次根据实际的选择，按照适应度进行父代的选择，父代选择的算法有好多种，通常我们选择算子有:适应度比例选择、联赛选择方法、最佳个体保存方法、期望值方法。
2) 交叉
在中学我们都学过生物，从那时我们就了解到，不管是人类还是生物，在进化的过程中，他们产生新的个体都是通过交配两个同源的染色体而形成的。遗传算法就是根据生物体的这个特点利用了交叉算法来形成新的个体的。在整个遗传算法中，交叉操作是最主要的一个步骤，所以说交叉算子的设计与实现与你所研究的问题密切相关。交叉算子的设计要与个体编码的设计统一考虑。通过交叉操作可以得到新一代的个体，新个体继承了父代个体的特征。将群体中的各个体随机搭配成对，对每一个个体，以交叉概率交换他们的部分染色体。
3)变异
通过所学的生物学知识可以知道在生物的遗传进化过程当中，某个细胞由于在分裂复制的过程中可能会产生一些差错，一比如说A变异成了B，所以就有可能会导致个体上的一些基因发生了突变，这种突变会带来了新的染色体，从而形成了新的物种。人类中的一些疑难杂病，其实就是基因突变所引起的。我们都知道产生这种变异的可能性是非常小的，但是它却是存在的，而且他能够产生一个新的个体或者物种。遗传算法就是根据生物体的这个特点利用了变异算法来形成新的个体的。变异操作[l5珠口生物进化过程中类似，必须首先要确定一个个体，当然这个个体来源于某个种群，其次对这个个体通过变异概率去随机更改基因值。遗传算法中变异发生的概率很低，所以说变异为新个体产生了机会，而变异操作仅仅是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，维持了种群的多样性，防止它出现早熟现象。
在标准遗传算法当中使用变异操作主要有以下两个好处:
第一:它的变异能够产生新的种群，继而就维持群体的多样性，而且还能预防种群出现早熟的现象。
第二:如果没有变异算子，遗传算法的局部搜索能力很差，正是有了变异操作从而提高了遗传算法过程中的局部搜索的能力。遗传算法通过交叉操作和变异操作这两个既相互配合而又相互竞争的操作使遗传算法具有兼顾全局和局部的均衡搜索能力。因此，如何有效地配合这两种操作，是目前遗传算法研究中的一个重要内容。
1.5 遗传算法的基本框架
从上面的知识我们可以明显的知道，每一代个体要想传到下一代必须要包括三个主要的过程，他们分别是:选择操作 (selectionoPerator)、交叉操作(Ssove:operator)、变异操作 (Mutationoperator)。另外在整个遗传算法过程中，还要注意了下边几个基本的操作:比如说编码的确定、怎样设定它的初始种群、怎样设计它的适应度函数等其它的操作。
1.6 遗传算法的运算步骤
对于用基本的遗传算法求解一个问题的运算一般大致分为六个步骤:
SteP1:根据问题确定染色体，生成初始种群，该步其实是一个初始化的过程，在该步中只要设置一些参数就行了;
steP2:计算种群中各个个体的适应度，适应度函数一般是要以目标函数来确定的;
SteP3:选择操作，选择操作就是建立在对个体的适应度进行评价的基础上;
steP4:交叉操作，在整个遗传算法中，交叉操作是最主要的一步交叉算子的设计要与个体编码的设计统一考虑;
SteP5:变异操作，变异操作首先必须在群体中选择一个个体，对于选中的这个个体以变异概率随机改变染色体结构数据中的某个串的值，;
steP6:终止条件判断，若进化代数与最大进化代数相等的话，则整个算法就结束，否则进化代数的次数加1，然后转到stepZ进行循环操作。
2.初始化种群的生成
种群是由一定数量的个体组成的，种群规模是由种群中的个体的数目组成。种群规模是遗传算法几个控制参数之一。在遗传操作过程中，需要中群型的操作，所以一定要准备一个由若干个初始解组成的初始种群。在初始种群中的每一个个体都是通过随机地方法产生的，也就是我们平时所讲的进化的初始代。初始种群的选择对发挥遗传算法的效能产生重大影响。一般我们选择种群规模都在几十到几百之间取值，种群规模的选择跟问题的难度成正比例关系。初始种群的设置一般可采用以下规则I’2]:
(l)首先要确定分布范围，这个分布范围是根据整个问题的最优解来确定的，最后对初始种群进行设定。
(2)通过随机函数产生一定量的个体，从产生的个体中挑选最优的个体加入到种群中。
3.适应度及参数设置
适应度(Fitness)是各个个体对它的环境所适应的程度。适应度评价是对解质量的一种衡量。适应度函数一般是要以目标函数来确定的。适应度的好坏直接决定了个体的好坏，因为遗传算法在求解问题(搜索问题的时候)不需要其它的信息。所以可以这么说适应度也可以作为评判遗传操作的依据。怎样确定一个个体的适应度，必须进行下面两个操作:第一，，计算目标函数值，这里的目标值的对象是某个经过编码后所得到的个体;第二，根据上面过程所求得的目标函数值，通过一定的规则，从而求出这个个体的适应度。对于遗传算法的一些参数的设置，应该通常考虑以下的参数:串的长度、种群的规模、交叉概率、变异概率等，这些参数直接关系到遗传算法的性能的好坏。通常情况下，尤其在简单遗传算法中，这些参数都是人为设定不变的。可是对于复杂的遗传算法，这个时候可能会增加算法的复杂性程度以及会降低算法的效率，所以我们这个时候也必须要对参数进行相应的改进。
4.选择
选择其实是用来确定重组或者交叉个体、以及被选个体将产生多少个子代个体。只有对个体的适应度进行评价才能进行选择操作。因此，选择操作也是遗传算法中一个很重要的环节。因为选择操作不仅可以避免基因的遗漏，‘而且还能提高遗传算法的计算效率和全局的收敛性。选择通常分为两步[‘3]:首先是计算适应度，可以通过按比例的适应度计算 (ProportionalFitnessAssignment)或基于排序的适应度计算(Rank一 basedFitnessAssignment)等方法;其次根据实际的选择，按照适应度进行父代的选择，父代选择的算法有好多种，通常我们选择算子有:适应度比例选择、联赛选择方法、最佳个体保存方法、期望值方法。

2 遗传算法
遗传算法模拟了达尔文进化现象。它把每一个可能的解编码为一个向量(二进制或十进制数字串), 称为一个染色体(chromosome,或个体), 向量的每一个元素称为基因(genes)。所有染色体组成群体(population, 或集团)。并按预定的目标函数(或某种评价指标)对每个染色体进行评价, 根据其结果给出一个适应度的值。遗传算法工作原理示意图如图 1:

图 1:遗传算法工作原理示意图
2.1 遗传算法的三个基本运算
1) 选 择 。
选择运算又称为繁殖、再生、或复制运算,用于模拟生物界去劣存优的自然选择现象。
2) 交 叉 。
它模拟生物进化过程中的繁殖现象, 通过两个染色体的交换组合, 来产生新的优良品种。例如: 从匹配集中选取一对染色体 A、B:随机产生的一个交叉点是 5, 交叉染色体 A、B中第 5 位右边的部分-110 和 001, 则得两个下一代(子代)染色体数字串 A′、B′:

3) 变异
变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变,它以很小的概率随机的改变遗传基因 (表示染色体的符号串的某一位)的值。在染色体以二进制编码的系统中, 它随机的将染色体的某一基因由 1变为 0, 或由 0 变为 1。

Welcome To
Download !!!

欢迎您的下载，资料仅供参考！

精品资料