《2022年遗传算法应用的分析与研 .pdf》由会员分享，可在线阅读，更多相关《2022年遗传算法应用的分析与研 .pdf（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、IOI2005 国家集训队论文遗传算法应用的分析与研究钱自强第 1 页共 11 页遗传算法应用的分析与研究福州八中钱自强【摘要】随着科技水平的不断发展， 人们在生产生活中遇到的问题也日益复杂，这些问题常常需要在庞大的搜索空间内寻找最优解或近似解，应用传统算法求解已经显得相当困难。而近年来，生物学的进化论被广泛地应用于工程技术、人工智能等领域中， 形成的一类有效的随机搜索算法进化算法，有效的解决了诸多生产生活中的难题而显得越来越流行。本文的首先将介绍进化算法的原理以及历史使大家对进化算法有一个初步的了解，其次将详细介绍应用遗传算法解题的步骤，并提出有效改进和应用建议。紧接着通过一个NP难题的优化
2、实例让大家对遗传算法有更深刻的了解，最后通过数据分析证明其方法的有效性。【关键词】人工智能；进化算法；遗传算法（GA ） ；多目标最小生成树目录一、进化算法理论11进化算法概述 2 12遗传算法介绍 2 二、遗传算法21遗传算法基本流程 3 22遗传算法中各重要因素分析 3 23重要参数设置 6 三、遗传算法在多目标最小生成树问题中的应用31多目标最小生成树 7 32应用遗传算法解决多目标最小生成树 9 33测试11四、结束语15附录16名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第
3、 1 页，共 11 页 - - - - - - - - - IOI2005 国家集训队论文遗传算法应用的分析与研究钱自强第 2 页共 11 页一. 进化算法理论11 进化算法概述从远古时代单细胞开始， 历经环境变迁的磨难，生命经历从低级到高级，从简单到复杂的演化历程。 生命不断地繁衍生息， 产生出具有思维和智能的高级生命体。人类得到生命的最佳结构与形式，它不仅可以被动地适应环境， 更重要的是它能够通过学习，模仿与创造，不断提高自己适应环境的能力。进化算法就是借鉴生物自然选择和遗传机制的随机搜索算法。进化算法通过模拟“优胜劣汰，适者生存”的规律激励好的结构，通过模拟孟德尔的遗传变异理论在迭代过程
4、中保持已有的结构，同时寻找更好的结构。 作为随机优化与搜索算法，进化算法具有如下特点： 进化算法不是盲目式的乱搜索，也不是穷举式的全面搜索， 它根据个体生存环境即目标函数来进行有指导的搜索。进化算法只需利用目标的取值信息而不需要其他信息，因而适用于大规模、 高度非线性的不连续、多峰函数的优化，具有很强的通用性；算法的操作对象是一组个体，而非单个个体，具有多条搜索轨迹。12 遗传算法遗传算法（ Genetic Algorithm）是进化算法的一个重要分支。它由John Holland 提出， 最初用于研究自然系统的适应过程和设计具有自适应性能的软件。近来，遗传算法作为问题求解和最优化的有效工具，
5、已被非常成功地应用与解决许多最优化问题并越来越流行。遗传算法的主要特点是群体搜索策略和群体中个体之间的信息互换, 它实际上是模拟由个体组成的群体的整体学习过程, 其中每个个体表示问题搜索空间中的一个解点 . 遗传算法从任一初始的群体出发, 通过随机选择，交叉和变异等遗传操作 , 使群体一代代地进化到搜索空间中越来越好的区域, 直至抵达最优解点 . 遗传算法和其它的搜索方法相比, 其优越性主要表现在以下几个方面：首先,遗传算法在搜索过程中不易陷入局部最优, 即使在所定义的适应度函数非连续.不规则也能以极大的概率找到全局最优解, 其次, 由于遗传算法固有的并行性, 使得它非常适合于大规模并行分布处
6、理, 此外, 遗传算法易于和别的技术(如神经网络. 模糊推理 . 混沌行为和人工生命等 ) 相结合 , 形成性能更优的问题求解方法. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 11 页 - - - - - - - - - IOI2005 国家集训队论文遗传算法应用的分析与研究钱自强第 3 页共 11 页二. 遗传算法21遗传算法的基本流程一个串行运算的遗传算法通常按如下过程进行：(1) 对待解决问题进行编码；t:=0 (2) 随机初始化群体X(0):=nxxx,21
7、；(3) 对当前群体 X(t) 中每个染色体ix 计算其适应度 F ix， 适应度表示了该个体对环境的适应能力，并决定他们在遗传操作中被抽取到的概率；(4) 对 X(t) 根据预定概率应用各种遗传算子，产生新一代群体X(t+1) ，这些算子的目的在于扩展有限个体的覆盖面，体现全局搜索的思想；(5) t:=t+1(新生成的一代群体替换上一代群体) ； 如果没有达到预定终止条件则继续 (3) 。22 遗传算法中各重要因素分析 编码理论遗传算法需要采用某种编码方式将解空间映射到编码空间（可以是位串、 实数、有序串）。类似于生物染色体结构，这样容易用生物遗传理论解释，各种遗传操作也易于实现。 编码理论
8、是遗传算法效率的重要决定因素之一。二进制编码是最常用的编码方式， 算子处理的模式较多也较易于实现。但是，在具体问题中，根据问题的不同， 采用适合解空间的形式的方式进行编码，可以有效地直接在解的表现型上进行遗传操作， 从而更易于引入相关启发式信息，往往可以取得比二名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 11 页 - - - - - - - - - IOI2005 国家集训队论文遗传算法应用的分析与研究钱自强第 4 页共 11 页进制编码更高的效率。 染色体每个编码串
9、对应问题的一个具体的解，称为染色体或个体。 一个染色体可以通过选用的编码理论与问题的一个具体的解相对应，一组固定数量的染色体则构成一代群体。群体中染色体可重复。 随机初始化随机或者有规律 （如从一个已知离解较近的单点，或者等间隔分布地生成可行解）生成第一代群体。 一次遗传算法中有目的采用多次初始化群体会使算法拥有更强的搜索全局最有解的能力 适应度一个染色体的适应度是对一个染色体生存能力的评价，它决定了该染色体在抽取操作中被抽取到的概率。 估价函数是评价染色体适应度的标准，常见的估价函数有：直接以解的权值（如01 背包问题以该方案装进背包物品的价值作为其适应度） ， 累计二进制串中 1/0 的个
10、数 （针对以二进制串为编码理论的遗传算法），累加该染色体在各个目标上的得分（针对多目标最优化问题，另外，对于此类问题，本文提出了一种更有效的估价函数） 。 遗传算子遗传算子作为遗传算法的核心部分，其直接作用于现有的一代群体，以生成下一代群体， 因此遗传算子的选择搭配， 各个算子所占的比例直接影响遗传算法的效率。一个遗传算法中一般包括多种遗传算子，每种算子都是独立运行，遗传算法本身只指定每种算子在生成下一代过程中作用的比例。算子运行时从当前这代群体中抽取相应数量的染色体，经过加工，得到一个新的染色体进入下一代群体。下面列出几种常见的遗传算子：名师资料总结 - - -精品资料欢迎下载 - - -
11、- - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - IOI2005 国家集训队论文遗传算法应用的分析与研究钱自强第 5 页共 11 页 保持算子：抽取 1 个染色体，直接进入下一代。 该算子使算法能够收敛。 交配算子：抽取 2 个染色体，交换其中的某些片段， 选择适应度高的 （或者都选） ，进入下一代群体。该算子使得遗传算法能够利用现有的解寻求更优的解。 变异算子：抽取 1 个染色体，对其进行随机的改变，进入下一代群体。该算子使得算法可以跳出局部最优解，拥有更强搜索全局最有解的能力，
12、防止陷入局部搜索，该算子的概率不可过高，否则将引起解的发散，使得算法无法收敛。 抽取抽取操作是遗传算法中一个重要基本操作，作用是按照“优胜劣汰”的原则根据各个染色体的适应度从当前这代群体中挑选用于遗传算子的染色体。通常采用的手段是偏置转盘：设算法中群体数量为population，首先计算当代群体的各染色体适应度之和populationiixFtS1)()(。将 1)(tS内的整数划分成population个区间段，每个染色体所占的区间段的长度既是它的适应度。这样，随机产生一个 1)(tS的整数，抽取该点所属区间段相对应的染色体，就可以保证任意一个染色体xi在抽取操作中被抽取到的概率为)()(t
13、SxFi。 终止条件遗传算法的终止条件用于防止遗传算法无止境的迭代下去，一般限制条件可以设为达到指定的迭代次数后终止，或当解的收敛速度低于一定值时自动终止。当遗传算法达到终止条件时，遗传算法结束，并按照要求返回中途最优的一个染色体（或所有满足条件的非劣最优解）F(x1)F(x2)F(x3)F(x4)F(x5)F(x6)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 11 页 - - - - - - - - - IOI2005 国家集训队论文遗传算法应用的分析与研究钱自强第
14、 6 页共 11 页23 重要参数设置在应用遗传算法解决问题的时候，往往需要根据实际情况的不同，对不同问题使用不同的遗传参数。 在大规模的问题上， 一次遗传算法的不同时期也可以设置不同的遗传参数。对遗传算法效率影响较大的参数如下：群体大小 ：一代群体中染色体的数量，群体大小越大所能容纳的染色体品种也越多，越有利于搜索全局最有解，但是会下降收敛的速度，所需的时间也更多。迭代次数 ：最多更新群体的次数，迭代次数的增加可以使得解收敛更精确但是所需的时间也越多，如果时间允许，采用多次初始化群体的操作要比设置很大的迭代次数来得更高效些。保持率 ：保持算子所占的比例，通常不超过70% 交配率 ：交配算子所
15、占的比例，通常不超过50% 变异率 ：变异算子所占的比例，通常不超过1% 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 11 页 - - - - - - - - - IOI2005 国家集训队论文遗传算法应用的分析与研究钱自强第 7 页共 11 页三. 遗传算法在多目标最小生成树问题中的应用生活中的很多问题，例如道路铺设，电网架设，网络构设等，其实都可以归结到最小生成树模型，经典的Prim 算法和 Kruskal 算法都可以解决该问题，算法的时间复杂度都是线形的， 但是
16、现实生活中的问题往往没有那么简单，一条边上可能不只带一个权，例如一条公路的铺设道路长度还要考虑环境和人文因素，电网架设时除了考虑线路费用还要考虑架设难度，一个网络连接除了考虑网络延时还要考虑传输稳定性和安全性等，于是问题就转化为求解多目标的最小生成树问题的非劣最优解，这个问题是NP难的， Prim 算法， Kruskal 算法等常规算法就显得无能为力，搜索算法的复杂度却又过高。32 应用遗传算法解决多目标最小生成树问题321 编码设计Cayley 证明了对于一个完全图G，连接所有 n 个顶点的树有nn-2棵。为此Pr fer 建立了一个这些树与从n个数取 n-2个数的所有组合之间的一一对应关系
17、，即如果对完全图中所有顶点从1 到 n 开始编号，则任意一个在从 1 到 n 的 n 个数中取 n-2 个数的组合都与唯一的一棵生成树相对应。本文对生成树的编码采用基于以上的一一对应建立起来的Pr fer 数编码机制，把每一棵树与一个长度为n-2 的数字串对应，而对于任意一个长度为n-2 的数字串也与唯一的一棵生成树相对应，生成树到数字串的编码与数字串到生成树的解码的详细证明可参考相关文献，本文这里只作简要描述。编码过程 编码串初始为空串 令 j 为树中编号最小的叶节点；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整
18、理 - - - - - - - 第 7 页，共 11 页 - - - - - - - - - IOI2005 国家集训队论文遗传算法应用的分析与研究钱自强第 8 页共 11 页 找到唯一于 j 相邻的点 i ，把 i 加入编码串的最右端 把 j 以及连接 i 和 j 的边从树中删除，这时候树只有n-1 个顶点 重复以上 3 个步骤直到树中只剩下一条边这时候得到的编码串即为相应树的 Pr fer 编码解码过程设 P 为编码串，P为图的顶点编号不出现在P 中的顶点的集合；设 i 为P中编号最小的顶点 ，j 为 P 中最左端的顶点，则将连接i 和 j 的边加入到树中，然后分别把i 和 j 从 P 和
19、P中删除，如果 P 中不在出现顶点j则把j加入到P中重复以上步骤，直到P 为空；当 P 为空串时，P中刚好剩下两个顶点， 将连接这两个顶点的边加入到树中，最后构成的树即为与最初P 对应的生成树。例如，图 3-1 则为一棵生成树以及其相对应的Pr fer 编码图 3-2。显然 Pr fer 编码是生成树的一个有效表示方式，应用该编码方式， 可以很容易地随机生成一棵生成树， 而且 Pr fer 数编码串的每个位置的信息量又相对均匀因此很适合遗传操作。322估价函数设置定义估价函数 g(x) 为kiixfi12100)(min，)(xfi表示当前的染色体在目标图 3-1 图 3-2 名师资料总结 -
20、 - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - - - - - IOI2005 国家集训队论文遗传算法应用的分析与研究钱自强第 9 页共 11 页i 的费用情况， mini 表示截止到上一代为止，产生的所有染色体在目标i 的费用的最小值。本文提出的这样定义比起常见的直接累加各目标上的权值的好处在于，其不仅很好的体现了一个染色体在各个目标上的优势，与此同时还避免了由于每个目标的取值范围不同或者取值的整体趋势不同而造成的某些个体在某些目标的优势无法被体现，使得算
21、法能够适应现实生活中各类问题。323 遗传操作定义交配算子随机在两个染色体中抽取等位的，片段进行互换， 然后选择适应度较高的进入下一代，具体操作方法如下图所示：小片段等位交叉算子示意图变异算子变异算子采用常规的单点变异，即随机生成一个数替换编码串中的某一位，如图所示。P 1 2 5 6 8 2 5 P 2 8 4 5 2 8 7 P 1 2 5 5 2 2 5 P 2 8 4 6 8 8 7 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - -
22、 - - - IOI2005 国家集训队论文遗传算法应用的分析与研究钱自强第 10 页共 11 页图 3-4 单点变异示意图可以看出单点变异也可以很大程度上保留了原染色体的性质。33测试我们将保持率定为80% ，交配率定为80% ，变异率定为 1% ，并且根据数据不同对迭代次数和群体大小进行调整331 小规模经典测试数据列表参数选择 N(NodeNum),M(MaxGen) 耗时(s) N=20,M=20 1.444027 N=40,M=20 5.953092 N=60,M=20 14.529738 N=40,M=20 5.90460 N=40,M=40 12.127869 N=40,M=60
23、 18.911336 332 中规模随机测试数据列表P 2 5 6 8 4 5 O 2 5 6 2 4 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - IOI2005 国家集训队论文遗传算法应用的分析与研究钱自强第 11 页共 11页参数选择 N(NodeNum),M(MaxGen) 耗时(s) N=100,M=150 1.444027 N=200,M=150 5.953092 N=150,M=100 14.529738
24、 N=150,M=200 5.90460 四结束语本文主要运用遗传算法的一些基本知识解决加油占选址的问题，通过测试结果看到了遗传算法在解决选址问题有着和其他算法无法比拟的强大优势。它的特点就是可以在较短的时间内，得到比较令人满意的解，而且算法相对简明。对于现实生活中的大量常规算法无法解决问题，遗传算法都有着良好的应用前景。参考文献Heuristic algorithms for siting alternative-fuel stations using the Flow-Refueling Location Model,Seow Lim, Michael Kuby MATLAB 遗传算法工具箱及应用, 雷英杰 , 西安电子科技大学出版社数据结构 ,张千帆 , 科学出版社名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -