《关于遗传算法的研究毕业论文》由会员分享，可在线阅读，更多相关《关于遗传算法的研究毕业论文（11页珍藏版）》请在金锄头文库上搜索。
1、 关于遗传算法的研究 摘要：在本篇论文主要讨论的是通过介绍生物的遗传问题，什么是遗传算法（genetic Algorithm），遗传算法的性质，应用，传统遗传算法的基本步骤和遗传算法的目前的发展趋向等等内容，使大家得到关于遗传算法的比较深厚的了解。中文关键词：遗传；遗传算法；染色体；基因；基因地点；基因特征值；适应度英文关键词：Genetic；Genetic Algorithm；Chronmosome；Gene；Locus；Gene Feature；Fitness关于遗传算法的研究1、 生物的遗传问题与自然选择：众所周知，生命的出现，变化以及其消亡是必然的。在地球上最早的生命出现以来，在自然界
2、中多种多样的生物一起存在着并且生命的形式与物种不断发生着变化。由于不同原因，一些物种相继消亡，有一些物种得以生存到现在且还有一些生物改变到另一种生物。那么到底是什么原因导致这种情况呢？我们先看一下达尔文的自然选择学说的主要内容。达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。这种学说认为，生物要生存下去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达
3、尔文把这种在生存斗争中适者生存，不适者淘汰的过程叫做自然选择。它表明，遗传和变异是决定生物进化的内在因素。自然界中的多种生物之所以能够适应环境而得以生存进化，是和遗传和变异生命现象分不开的。总之，在这个问题中，我们把主要原因概括在下列两个方面：一个是自然界为生命存在方式所提供的条件即有些生物由于对自然界的适应能力比较强，它们都能适应自然环境的各种变化，反而，还有一些生物的适应能力比较弱，所以它们不能适应自然环境和资源的变化并且很容易就被自然界淘汰。原因之二是生物自身的遗传与变异功能。生物的遗传能力使物体得以延续到至今。 2、 遗传算法及其性质和应用：就像我们上面所说的，不管在生命的延续还是消亡
4、过程中，我们最要关注的是提高生物的对自然界的适应度即使地球上的生命形式得到最优解。在这样，我们要使用遗传算法来解决该问题。2.1 遗传算法的定义：遗传算法（Genetic Algorithm）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。它是有美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著Adaptation in Natural and Artificial Systems，GA这个名称才逐渐为人所知，J.Hilland教授所提出的GA通常为简单遗传算法（SGA）。 遗传算法是从代表问题可
5、能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存检测”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参
6、数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。 作为一种新的全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于并行处理以及高效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。2.2 遗传算法的基本性质：遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法。遗传算法作为一种快捷、简便、容错性强的算法，在各类结构对象的优化过程中显示出明显的优势。与传统的优化算法相比，主要有以下特点： 搜索过程不直接作用在变量上，而是在参数集进
7、行了编码的个体。此编码操作，使得遗传算法可直接对结构对象（集合、序列、矩阵、树、图、链和表）进行操作。 搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法，降低了陷入局部最优解的可能性，并易于并行化。 采用概率的变迁规则来指导搜索方向，而不采用确定性搜索规则。对搜索空间没有任何特殊要求（如连通性、凸性等），只利用适应性信息，不需要导数等其它辅助信息，适应范围更广。 遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。 遗传算法使用多个点的搜索信息，具有隐含并行性。 遗传算法使用概率搜索技术，而非确定性规则。 遗传算法以决策变量的编码作为运算对象。2.3 遗传算法的主要应用
8、：由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学，下面我们将介绍遗传算法的一些主要应用领域：2.3.1 函数优化： 函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以
9、方便的得到较好的结果。2.3.2 组合优化： 随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效。例如遗传算法已经在求解旅行商问题、 背包问题、装箱问题、图形划分问题等方面得到成功的应用。此外，GA也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。2.3.3 利用遗传算法解最优化问题可以分为以下几个步骤:首先，对可行域行编码(一般采用二进制编码)。
10、然后，在可行域中随机挑选一些编码组成作为进化起点的第一代编码组，并计算每个解的目标函数值，也就是编码的适应度。接着，利用选择机制从编码组中随机挑选编码作为繁殖过程前的编码样本。选择机制应保证适应度较高的解能够保留较多的样本，而适应度较低的解保留较少的样本，甚至被淘汰。在接下去的繁殖过程中，遗传算法提供了交叉和变异两种算子对挑选后的样本进行交换。交叉算子交换随机挑选的两个编码的某些位，变异算子则对一个编码中的随机挑选的某一位进行反转,这样通过选择和繁殖就产生了下一代编码组。 重复上述选择和繁殖过程，直到结束条件得到满足为止。进化过程最后一代中的最优解就是用遗传算法解最优化问题所得到的最终结果。3
11、、 遗传算法的基本步骤和实际例子：对于一个实际问题应用GA寻求最优解的基本思想是:首先将问题的候选解进行编码,经过编码后的候选解称为个体许多候选解的编码(个体)组成了候选解群称之为群体对这样的群体像生物进化那样进行选择、交叉和变异的操作，产生新一代群体.在每一代群体中,保持个体数目为定值,且对各个个体通过适应度函数值的计算对其进行评价，其中的交叉和变异操作是为了保证得到具有全局最优的解。GA每完成一次这样的操作称为“一代”，经过若干代的进化，即可以得到问题的最优解。我们习惯上把 Holland 1975年提出的GA称为传统的GA。它的主要步骤如下： 编码：GA在进行搜索之前先将解空间的解数据表
12、示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。 初始群体的群体的形成：随机产生N个初始串结构数据，每个串数据结构称为一个个体，N个个体构成了一个群体。GA以这N个串数据结构作为初始点开始迭代。 适应性值评估检测：适应性函数表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。 选择：根据适者生存原则选择下一代的个体。在选择时,以适应度为选择原则。选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。 交叉：交叉操作是遗传算法中最主要的
13、遗传操作。通过交换操作可以得到新一代个体. 对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P在选中的位置实行交换。这个过程反映了随机信息交换:目的在于产生新的基因组合,也即产生新的个体。交叉时，可实行单点交叉或多点交叉。 变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。根据生物遗传中基因变异的原理，以变异概率PM对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率PM与生物变异极小的情况一致，所以，Pm的取值较小。变异不能在求解中得到好处。但是，它能保证算法过程不会产生无
14、法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。 全局最优收敛(Convergence to the global optimum)：当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。遗传算法的原理可以简要给出如下:编码和生成初始种群对种群中的个体适应度进行评价选择操作交叉操作变异操作 终止进化，输出结果是否满足终止条件？YesNo图 1 遗传算法的基
15、本算法的流程图上述过程中选择(Selection)、交叉(Crossover)、变异(Mutation)为基本的遗传算子，其算子的实现是多种多样的，而且近年来，不同的遗传基因表达方式，不同的交叉和变异算子，以及不同的再生和选择方法正在不断地提出，以改进GA的某些性能。其中串的编码方式、适应函数的确定、遗传算法自身参数设定是遗传算法在应用中最关键的问题.例子: 对于对象 X ,Random 产生8个初始值,不妨设得到4个值:6 ,13 ,20 ,29 . 用二进制来进行编码: 因为 称为个体的相对适应度. 按照上面公式,我们很容易得到下面的信息. 初始群体的编码表个体群体初始群体10011061560.855201101132471.353310100202401.35141110129870.476从表上的内容,我们可以看到的适应度最低, 的适应度最高 .所以我们取消.重新得到下面 新群体的编码表。新群体的编码表个体群体初始群体10011061560.85520110
