论文--遗传算法应用的分析与研究

《论文--遗传算法应用的分析与研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、遗传算法应用的分析与研究遗传算法应用的分析与研究【摘要】随着科技水平的不断发展，人们在生产生活中遇到的问题也日益复杂，这些问题常常需要在庞大的搜索空间内寻找最优解或近似解，应用传统算法求解已经显得相当困难。而近年来，生物学的进化论被广泛地应用于工程技术、人工智能等领域中，形成的一类有效的随机搜索算法——进化算法，有效的解决了诸多生产生活中的难题而显得越来越流行。本文的首先将介绍进化算法的原理以及历史使大家对进化算法有一个初步的了解，其次将详细介绍应用遗传算法解题的步骤，并提出有效改进和应用建议。紧接着通过一个NP难题的优化实例让大家对遗传

2、算法有更深刻的了解，最后通过数据分析证明其方法的有效性。【关键词】人工智能；进化算法；遗传算法（GA）；多目标最小生成树目录一、进化算法理论1．1进化算法概述－2－1．2遗传算法介绍－2－二、遗传算法2．1遗传算法基本流程－3－2．2遗传算法中各重要因素分析－3－2．3重要参数设置－6－三、遗传算法在多目标最小生成树问题中的应用3．1多目标最小生成树－7－3．2应用遗传算法解决多目标最小生成树－9－3．3测试－11－四、结束语－15－附录－16－一.进化算法理论第23页共23页遗传算法应用的分析与研究1．1进化算法概述从远古时代单细胞开始

3、，历经环境变迁的磨难，生命经历从低级到高级，从简单到复杂的演化历程。生命不断地繁衍生息，产生出具有思维和智能的高级生命体。人类得到生命的最佳结构与形式，它不仅可以被动地适应环境，更重要的是它能够通过学习，模仿与创造，不断提高自己适应环境的能力。进化算法就是借鉴生物自然选择和遗传机制的随机搜索算法。进化算法通过模拟“优胜劣汰，适者生存”的规律激励好的结构，通过模拟孟德尔的遗传变异理论在迭代过程中保持已有的结构，同时寻找更好的结构。作为随机优化与搜索算法，进化算法具有如下特点：进化算法不是盲目式的乱搜索，也不是穷举式的全面搜索，它根据个体生存

4、环境即目标函数来进行有指导的搜索。进化算法只需利用目标的取值信息而不需要其他信息，因而适用于大规模、高度非线性的不连续、多峰函数的优化，具有很强的通用性；算法的操作对象是一组个体，而非单个个体，具有多条搜索轨迹。1．2遗传算法遗传算法（GeneticAlgorithm）是进化算法的一个重要分支。它由JohnHolland提出，最初用于研究自然系统的适应过程和设计具有自适应性能的软件。近来，遗传算法作为问题求解和最优化的有效工具，已被非常成功地应用与解决许多最优化问题并越来越流行。遗传算法的主要特点是群体搜索策略和群体中个体之间的信息互换,

5、它实际上是模拟由个体组成的群体的整体学习过程,其中每个个体表示问题搜索空间中的一个解点.遗传算法从任一初始的群体出发,通过随机选择，交叉和变异等遗传操作,使群体一代代地进化到搜索空间中越来越好的区域,直至抵达最优解点.遗传算法和其它的搜索方法相比,其优越性主要表现在以下几个方面：首先,遗传算法在搜索过程中不易陷入局部最优,即使在所定义的适应度函数非连续.不规则也能以极大的概率找到全局最优解,其次,由于遗传算法固有的并行性,使得它非常适合于大规模并行分布处理,此外,遗传算法易于和别的技术(如神经网络.模糊推理.混沌行为和人工生命等)相结合,

6、形成性能更优的问题求解方法.一.遗传算法第23页共23页遗传算法应用的分析与研究2．1遗传算法的基本流程一个串行运算的遗传算法通常按如下过程进行：(1)对待解决问题进行编码；t:=0(2)随机初始化群体X(0):=；(3)对当前群体X(t)中每个染色体计算其适应度F，适应度表示了该个体对环境的适应能力，并决定他们在遗传操作中被抽取到的概率；(4)对X(t)根据预定概率应用各种遗传算子，产生新一代群体X(t+1)，这些算子的目的在于扩展有限个体的覆盖面，体现全局搜索的思想；(5)t:=t+1(新生成的一代群体替换上一代群体)；如果没有达到预

7、定终止条件则继续(3)。2．2遗传算法中各重要因素分析▲编码理论遗传算法需要采用某种编码方式将解空间映射到编码空间（可以是位串、实数、有序串）。类似于生物染色体结构，这样容易用生物遗传理论解释，各种遗传操作也易于实现。编码理论是遗传算法效率的重要决定因素之一。二进制编码是最常用的编码方式，算子处理的模式较多也较易于实现。但是，在具体问题中，根据问题的不同，采用适合解空间的形式的方式进行编码，可以有效地直接在解的表现型上进行遗传操作，从而更易于引入相关启发式信息，往往可以取得比二进制编码更高的效率。▲染色体第23页共23页遗传算法应用的分析

8、与研究每个编码串对应问题的一个具体的解，称为染色体或个体。一个染色体可以通过选用的编码理论与问题的一个具体的解相对应，一组固定数量的染色体则构成一代群体。群体中染色体可重复。▲随机初始化随机或