关于遗传算法的研究毕业论文.doc

关于遗传算法的研究 摘要：在本篇论文主要讨论的是通过介绍生物的遗传问题，什么是遗传算法（genetic Algorithm），遗传算法的性质，应用，传统遗传算法的基本步骤和遗传算法的目前的发展趋向等等内容，使大家得到关于遗传算法的比较深厚的了解。中文关键词：遗传；遗传算法；染色体；基因；基因地点；基因特征值；适应度英文关键词：Genetic；Genetic Algorithm；Chronmosome；Gene；Locus；Gene Feature；Fitness关于遗传算法的研究1、 生物的遗传问题与自然选择：众所周知，生命的出现，变化以及其消亡是必然的。在地球上最早的生命出现以来，在自然界中多种多样的生物一起存在着并且生命的形式与物种不断发生着变化。由于不同原因，一些物种相继消亡，有一些物种得以生存到现在且还有一些生物改变到另一种生物。那么到底是什么原因导致这种情况呢？我们先看一下达尔文的自然选择学说的主要内容。达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。这种学说认为，生物要生存下去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存，不适者淘汰的过程叫做自然选择。它表明，遗传和变异是决定生物进化的内在因素。自然界中的多种生物之所以能够适应环境而得以生存进化，是和遗传和变异生命现象分不开的。总之，在这个问题中，我们把主要原因概括在下列两个方面：一个是自然界为生命存在方式所提供的条件即有些生物由于对自然界的适应能力比较强，它们都能适应自然环境的各种变化，反而，还有一些生物的适应能力比较弱，所以它们不能适应自然环境和资源的变化并且很容易就被自然界淘汰。原因之二是生物自身的遗传与变异功能。生物的遗传能力使物体得以延续到至今。 2、 遗传算法及其性质和应用：就像我们上面所说的，不管在生命的延续还是消亡过程中，我们最要关注的是提高生物的对自然界的适应度即使地球上的生命形式得到最优解。在这样，我们要使用遗传算法来解决该问题。2.1 遗传算法的定义：遗传算法（Genetic Algorithm）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。它是有美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著Adaptation in Natural and Artificial Systems，GA这个名称才逐渐为人所知，J.Hilland教授所提出的GA通常为简单遗传算法（SGA）。 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存检测”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。 作为一种新的全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于并行处理以及高效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。2.2 遗传算法的基本性质：遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法。遗传算法作为一种快捷、简便、容错性强的算法，在各类结构对象的优化过程中显示出明显的优势。与传统的优化算法相比，主要有以下特点： 搜索过程不直接作用在变量上，而是在参数集进行了编码的个体。此编码操作，使得遗传算法可直接对结构对象（集合、序列、矩阵、树、图、链和表）进行操作。 搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法，降低了陷入局部最优解的可能性，并易于并行化。 采用概率的变迁规则来指导搜索方向，而不采用确定性搜索规则。对搜索空间没有任何特殊要求（如连通性、凸性等），只利用适应性信息，不需要导数等其它辅助信息，适应范围更广。 遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。 遗传算法使用多个点的搜索信息，具有隐含并行性。 遗传算法使用概率搜索技术，而非确定性规则。 遗传算法以决策变量的编码作为运算对象。2.3 遗传算法的主要应用：由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学，下面我们将介绍遗传算法的一些主要应用领域：2.3.1 函数优化： 函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。2.3.2 组合优化： 随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效。例如遗传算法已经在求解旅行商问题、 背包问题、装箱问题、图形划分问题等方面得到成功的应用。此外，GA也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。2.3.3 利用遗传算法解最优化问题可以分为以下几个步骤:首先，对可行域行编码(一般采用二进制编码)。然后，在可行域中随机挑选一些编码组成作为进化起点的第一代编码组，并计算每个解的目标函数值，也就是编码的适应度。接着，利用选择机制从编码组中随机挑选编码作为繁殖过程前的编码样本。选择机制应保证适应度较高的解能够保留较多的样本，而适应度较低的解保留较少的样本，甚至被淘汰。在接下去的繁殖过程中，遗传算法提供了交叉和变异两种算子对挑选后的样本进行交换。交叉算子交换随机挑选的两个编码的某些位，变异算子则对一个编码中的随机挑选的某一位进行反转,这样通过选择和繁殖就产生了下一代编码组。 重复上述选择和繁殖过程，直到结束条件得到满足为止。进化过程最后一代中的最优解就是用遗传算法解最优化问题所得到的最终结果。3、 遗传算法的基本步骤和实际例子：对于一个实际问题应用GA寻求最优解的基本思想是:首先将问题的候选解进行编码,经过编码后的候选解称为个体许多候选解的编码(个体)组成了候选解群称之为群体对这样的群体像生物进化那样进行选择、交叉和变异的操作，产生新一代群体.在每一代群体中,保持个体数目为定值,且对各个个体通过适应度函数值的计算对其进行评价，其中的交叉和变异操作是为了保证得到具有全局最优的解。GA每完成一次这样的操作称为“一代”，经过若干代的进化，即可以得到问题的最优解。我们习惯上把 Holland 1975年提出的GA称为传统的GA。它的主要步骤如下： 编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。 初始群体的群体的形成：随机产生N个初始串结构数据，每个串数据结构称为一个个体，N个个体构成了一个群体。GA以这N个串数据结构作为初始点开始迭代。 适应性值评估检测：适应性函数表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。 选择：根据适者生存原则选择下一代的个体。在选择时,以适应度为选择原则。选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。 交叉：交叉操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一代个体. 对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P>在选中的位置实行交换。这个过程反映了随机信息交换:目的在于产生新的基因组合,也即产生新的个体。交叉时，可实行单点交叉或多点交叉。 变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。根据生物遗传中基因变异的原理，以变异概率PM对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率PM与生物变异极小的情况一致，所以，Pm的取值较小。变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。 全局最优收敛(Convergence to the global optimum)：当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。遗传算法的原理可以简要给出如下:编码和生成初始种群对种群中的个体适应度进行评价选择操作交叉操作变异操作 终止进化，输出结果是否满足终止条件？YesNo图 1 遗传算法的基本算法的流程图上述过程中选择(Selection)、交叉(Crossover)、变异(Mutation)为基本的遗传算子，其算子的实现是多种多样的，而且近年来，不同的遗传基因表达方式，不同的交叉和变异算子，以及不同的再生和选择方法正在不断地提出，以改进GA的某些性能。其中串的编码方式、适应函数的确定、遗传算法自身参数设定是遗传算法在应用中最关键的问题.例子: 对于对象 X ,Random 产生8个初始值,不妨设得到4个值:6 ,13 ,20 ,29 . 用二进制来进行编码: 因为 称为个体的相对适应度. 按照上面公式,我们很容易得到下面的信息. 初始群体的编码表个体群体初始群体1001106待添加的隐藏文字内容31560.855201101132471.353310100202401.35141110129870.476从表上的内容,我们可以看到的适应度最低, 的适应度最高 .所以我们取消.重新得到下面 新群体的编码表。新群体的编码表个体群体初始群体10011061560.855201101132471.353301101132471.35341110129870.476注意到没有产生新个体为产生可以依照生物学杂交办法,对染色体(字符串)的某些片段进行交叉换位,交叉换位是在成对染色体上 进行的一般采用random法进行配对不妨将1号与2号;3号与4号进行配对.方法是:先random确定字符串上交叉换位的位置,比如选择.1号 00110 00101 2号 01101 01110 3号 01101 01100 4号 10100 10101 突变:遗传算法还模仿基因突变将个体字符串中的某位符号进行逆变即0 变为 1 , 1 变为 0 .4、 遗传算法的研究历史和现状：遗传算法研究的兴起是在80年代末和90年代初期，但它的历史起源可追溯至60年代初期。早期的研究大多以对自然系统的计算机模拟为主。如Fraser的模拟研究，他提出了和现在的遗传算法十分相似的概念和思想。Holland和DeJong的创造性研究成果改变了早期遗传算法研究的无目标性和理论指导的缺乏。其中，Holland于1975年出版的著名著作<<自然系统和人工系统的适配>>系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论。这一理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，DeJong的重要论文<<遗传自适应系统到的行为分析>>将Holland的模式理论与他的计算实验结合起来，并提出了诸如代沟等新的遗传操作技术。可以认为，DeJong所作的研究工作是遗传算法发展过程中的一个里程碑。进入80年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用领域也不断扩大。目前遗传算法所涉及的主要领域有自动控制、规划设计、组合优化、图象处理、信号处理、人工生命等。可见，遗传算法的应用研究已从初期的组合优化求解拓展到了许多更新。更工程化的应用方面。进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。遗传算法还有大量的问题需要研究，还需要进一步研究其数学基础理论;还需要在理论上证明它与其它优化技术的优劣及原因;还需研究硬件化的遗传算法;以及遗传算法的通用编程和形式等。5、 结束语：遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术之一。遗传算法是一种模拟自然界生物进化的搜索算法,由于它的简单易行、鲁棒性强尤其是其不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程,从而使它的应用范围极为广泛,并且己在众多领域得到了实际应用,取得了许多令人瞩目的成果,引起了广大学者和工程人员的关注。 遗传算法是一种新兴的技术,正处于发展期,虽然在应用领域获得了丰收,但其理论基础还较薄弱,有许多地方需要研究和发展充实。 本文对遗传算法理论与应用进行了一些研究与分析工作。首先,分析了遗传算法基础原理模式定理在一维染色体编码方案上的适用性,提出了遗传算法设计的一些原则;其次,在对传统遗传算法的基本结构和基本流程的研究分析基础上,对传统遗传算法作了一些改进:扩展了传统遗传算法的群体概念,根据生物学上的“大量繁殖,生存竞争”的原理,细分了原来传统遗传算法的单一群体概念,提出了根据遗传的不同阶段分为两个不同的群体竞争群体和适应性群体,并给出了新概念建立的依据,分析了其意义;在此基础上,提出相关的遗传算子繁殖因子。并且,根据分析遗传算法局部搜索能力弱的特点,提出将运筹学中的单纯形法应用于遗传算法中,增强了遗传算法的局部搜索能力。6、 关键词说明： 遗传（Genetic）：是指生物体的构造和生理机能等由上代传给下代。在遗传过程中，DNA和基因的作用很重要。DNA分子是生命体中携带遗传信息的基本物质。现代分子遗传学把一个有特定遗传功能的DNA节段成为一个基因。 遗传算法（genetic Algorithm）：是一种模拟生物群体遗传和进化机理的启发式优化算法，该算法进行搜索的主要依据是个体的适应度值和个体间的基因相似性，达尔文的“适者生存，优胜劣汰”理论是其基因的优化思想。 染色体(Chronmosome)：染色体又可以叫做基因型个体(individuals),一定数量的个体组成了群体(population),群体中个体的数量叫做群体大小。 基因(Gene)：基因是串中的元素，基因用于表示个体的特征。例如有一个串S1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。 基因地点(Locus)：基因地点在算法中表示一个基因在串中的位置称为基因位置(Gene Position)，有时也简称基因位。基因位置由串的左向右计算，例如在串 S1101 中，0的基因位置是3。 基因特征值(Gene Feature)：在用串表示整数时，基因的特征值与二进制数的权一致；例如在串 S=1011 中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。 适应度(Fitness)：各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数. 这个函数是计算个体在群体中被使用的概率。参考文献：1 刑文训，谢金星，现代优化计算方法，北京，清华大学出版社，2版2 王利，计算机教育第10期3 王小平、曹立明，遗传算法理论、应用与软件实现，西安交通大学出版社，20024 同济大学计算机系 王小平编写的程序代码.