当前位置：文档之家 › 遗传算法综述

遗传算法综述

  • 格式：docx
  • 大小：79.98 KB
  • 文档页数：7

遗传算法综述摘要遗传算法是通过模拟大自然中自然进化的过程并遵循遗传机制来求解问题的最优解的算法。

本文介绍了遗传算法的发展史，并对算法过程中编码方式、适应度函数选择、选择策略、遗传算子处理、参数控制进行了详尽探讨。

关键词：遗传算法；编码；适应度函数；选择策略；遗传算子一、引言遗传算法是在20世纪80年代迅速发展起来的一种随机搜索与优化算法，近年其成功的应用于工业、经济管理、交通运输等不同领域[1]，应用前景广泛，本文将从其起源，发展，重要人物，重要文章开始讨论，重点探讨算法过程中的一些关键步骤中的问题。

二、遗传算法的起源和发展分支遗传算法是通过模拟大自然中自然进化的过程并遵循遗传机制来求解问题的最优解的算法。

其核心的进化思想要追溯到Darwin的进化论与Mendel的遗传学说。

Darwin提出了“物竞天择，适者生存”，生物的遗传使得父代性状可以传至子代，而交叉，变异则产生新基因，为自然选择提供了丰富的原材料。

Mendel 则提出了分离率和自由组合率，奠定了现代遗传学的基础。

遗传算法是由密西根大学的Holland教授和他的学生在二十世纪六十年代对细胞自动机进行研究时率先提出的，并在1975年出版了《Adaptation in Natural and Artificial Systems》[2]。

以后，Holland将该算法加以推广。

其后，遗传算法不断在许多领域得到应用，算法本身也越来越成熟。

在20世纪80年代，在美国召开了第一届国际遗传算法会议，遗传算法迎来了其蓬勃发展时期，随着计算机计算能力的发展与实际需求的增多，遗传算法也更加广泛的在许多领域得到应用。

比如机器智能设计和机器人学习、计算机自动设计、系统优化设计、生产调度、时间表安排等等[1]。

正是由于其在许多重要领域获得了成功，因此受到了普遍关注并成为一个热门研究领域。

三、遗传算法发展中的重要人物与经典文章遗传算法是从Holland开始逐渐为世人所熟悉，其提出了模式定理[2]，而他的《Adaptation in Natural and Artificial Systems》也成了一部经典之作。

1975年，De Jong则尝试了将遗传算法用于函数优化。

1989年，Goldberg出版的《Genetic Algorithm in Search, Optimization, and Machine learning》[3]，对遗传算法的研究产生了一定影响。

1992年，Michalewicz出版了一个具有影响力的著作《Genetic Algorithm + Data Structure = Evolutionary Programming》[4]。

四、算法详析（一）遗传算法的基本步骤1．初始化群体，随机产生初始群体。

2．计算群体中每个个体的适应度值，维护最优解，进行精英保留。

3．模拟自然选择的过程，根据每个个体的适应度利用某种方法产生新一代的个体。

4．模拟交叉过程。

5．模拟变异过程。

6．判断是否达到停止要求，没有则回到第2步重复，达到即可进入下一步。

7．输出结果。

根据该过程，我们可以得到如图一所示的流程图。

接下来我们将从具体的几个方面详细探讨遗传算法的实现。

（二）编码问题毫无疑问，我们在利用遗传算法解决问题时，就要将问题模型化，将其转化为我们希望使用的抽象模型。

我们在算法中，总是首先生成一些可能解，对于这些群体，进行自然选择的操作，以希望从这些原始群体中进化出最优解。

但是我们首先遇到的问题就是如何来进行编码表示这些可能解。

Holland在运用模式定理分析编码机制时建议使用二进制编码，即只用0和1组成的字符串来表示染色体。

二进制编码也是目前最常用的编码方式。

使用二进制编码有很多优点，比如简单易行，变异杂交操作都比较方便，而且也便于使用模式定理对其进行理论分图一，遗传算法流程图析，但是其精度不够，占用内存较多。

除了二进制编码之外，还有很多其它的编码方式。

常见的还有实数编码[5]，格雷码编码[5]，符号编码方法[1]，还有复数编码[6]等。

采用何种编码方式应该视具体情况决定，具体的问题会有其较为适合的编码方式。

而目前不同的编码方式中，许多也是为了解决某些具体问题而寻找到的合适编码方式。

比如复数编码的GA就是为了描述和解决二维问题，而让基因采取x+yi的方式进行编码[6]。

在实际决定采取何种编码方式的时候，我们必须要注意以下几个方面：一是完备性，即问题空间中的所有解均可以以GA空间中的染色体表现；二是健全性，即GA空间中的染色体均能对应到问题空间的某一可能解。

（三）适应度函数为了表明每个染色体的优劣，就需要一个适应度函数，来描述每个染色体的优劣，适应度就表现了每个个体的生存机会的大小。

因此，适应度函数的选取直接决定算法收敛的速度以及是否可以找到全局最优解，适应度函数直接影响到了遗传算法的效果。

那么合理选取适应度函数就变得相当重要了。

往往我们会对适应度函数进行尺度变换，常用的尺度变换有线性变换法、幂函数变换法、指数变换法等。

而一个问题具体采用什么变换才能达到最优的效果，vladik kreinovicha等人的《genetic algorithms: what fitness scaling is optimal?》[7]进行了比较详尽的阐述。

（四）选择策略在产生新一代个体过程中，很重要的一步就是在父代中进行选择。

不同的选择的策略对算法性能有不同的影响。

最常见的一个选择策略就是轮盘赌法，它依据父代每个个体的适应度数值大小，决定了每个个体被选择的几率，适应度数值越大，被选择存活的几率越大，但是这一种方法有着较大的抽样误差。

其它常用的一些选择策略还有非线性排名选择法，这时，种群将会进行基于排序的适应度分配，这样，适应度仅仅取决于个体在种群中的序位，不依赖于其具体目标值。

在一定程度上避免了轮盘赌法的弊端。

除此之外，还有随机遍历抽样法，局部选择法，锦标赛选择法等[8]。

面对不同的问题，应当采取合适的选择策略，以让算法性能尽可能的提高。

（五）遗传算子基本遗传算法中一般采用简单的单点交叉算子和简单的变异算子。

交叉与变异是产生新的个体的方式，因此交叉运算和变异运算对遗传算法的搜索能力有着明显的影响。

因此合理的选择交叉方法，变异方法可以有效的提高遗传算法的搜索能力。

在二进制编码或实数编码中，经常使用到的交叉算子有单点交叉，即随机设置一个交叉点，在该点相互交换两个配对个体的部分基因。

经常使用的还有双点交叉，即随机设置两个交叉点，对两个配对的个体交换两个交叉点之间的基因。

除此在外还有均匀交叉，算术交叉等[8]。

变异本身就是一种局部随机搜索，其使得群体具有多样性，防止出现非成熟收敛。

在二进制编码和实数编码中一般有基本位变异、均匀变异、高斯变异、二元变异[9]。

特别是二元变异，其变异需要两条染色体的参与，分别与另一条进行同或/异或运算，这有效的改善了早熟收敛问题，使得遗传算法得到了进一步优化。

（六）参数控制一般来说，参数包括群体大小，交叉概率，变异概率等。

参数的选取也是很重要的，比如群体大小，如果太小不利于进化，但如果太大的话程序运行时间过长，不能接受。

如果我们人为的去控制这些参数，具有很大的经验性，盲目性。

事实上，如果这些参数能够随着遗传进化而自适应变化，那将可靠的多，Davis 就提出自适应算子概率方法[10]。

许多学者也在该方向上努力，并取得了不少进展，相关算例也表明获得了较好的性能。

五、最新研究进展遗传算法的主要应用领域在于函数优化，机器人学，其在控制、规划、设计、组合优化、图像与信号的处理等方面也有着广泛的应用[8]。

而比较新的引人注目的有基于遗传算法的机器学习，而遗传算法与其它计算智能方法的相互渗透和结合也是一个热点。

遗传算法与神经网络、模糊推理以及混沌理论等的结合，可以取长补短，合理的应用将会显著提高系统性能。

而并行处理的遗传算法更是算法本身的发展，遗传算法与人工生命的渗透也逐渐成为一个热点。

六、结束语遗传算法以模拟自然界自然选择的过程，获得问题的最优解。

而在遗传算法当中，编码方式、适应度函数选择、选择策略、遗传算子处理、参数控制都决定着遗传算法的性能。

我们应当依据具体问题，采取具体的策略来让遗传算法的性能尽可能发挥到最好。

遗传算法也在很多领域有着广泛的应用价值，尽管其仍然有许多问题需要处理，但各国学者一直在寻求着遗传算法的改进，相信未来其会有更加广泛的应用前景。

参考文献[1][日]玄光男、程润传, 遗传算法与工程设计, 北京: 科学出版社，20001[2]Holland J H. Adaptation in Natural and Artificial Systems. Ann Arbor:University of Michigan press, 1975.[3]David E. Goldberg . Genetic Algorithms in Search, Optimization and MachineLearning.Addison-Wesley Educational Publishers Inc, 1989.[4]Z.Michalewicz. Genetic Algorithm + Data Structure = EvolutionaryProgramming Spinger Press,1992[5]周明、孙树栋, 遗传算法原理及应用, 北京: 国防工业出版社, 19991[6]唐飞滕弘飞刘峻娄汉文带有能力约束的二维装填布局问题宇航学报。

2000,21（2）：50-57[7]Vladik Kreinovich,Chris Quintana,Olac Fuentes. genetic algorithms: whatfitness scaling is optimal? Ctberm ans system.1993,24(1):9-26[8]王小平、曹立明遗传算法：理论、应用与软件实现。

西安交通大学出版社。

2002.1[9]杨启文, 蒋静坪, 张国宏, 遗传算法优化速度的改进软件学报 2000,12( 2) : 270~ 2751[10]Davis. L Adaptive Operator Probability in Genetic Algorithms. In Proc.3rd In tConf Genetic Algorithms,1989 18(6):590-595。

合集下载

几种仿生优化算法综述

几种仿生优化算法综述

几种仿生优化算法综述仿生优化算法是由自然界中的生物行为和现象而启发而来的一类算法。

这些算法通过模拟生物的行为和机制来解决各种优化问题，包括搜索、分类、调度、规划等诸多领域。

本文将介绍几种典型的仿生优化算法，并对它们的基本原理、应用领域和特点进行综述。

一、遗传算法遗传算法是一种模拟达尔文进化论的方法而产生的一种求解最佳问题的技术。

它是由美国密歇根大学的研究人员 John Holland 提出的，主要模拟自然选择和遗传的思想。

遗传算法的基本概念是模拟进化过程，利用自然选择机制和遗传机制，通过逐代选择和交叉变异操作寻找解决问题的最优解。

具体的工作过程是这样的：建立一个初始种群，通过适应度函数来评价每个个体的优劣。

然后，根据适应度值概率选择一些个体作为父代，采用交叉和变异操作产生下一代。

经过多次迭代操作，最终从种群中找到最优的解。

遗传算法的特点是它具有很强的全局寻优能力和较好的鲁棒性，能有效避免落入局部最优解。

遗传算法广泛应用于组合优化、函数优化、调度问题、神经网络设计等众多领域。

二、粒子群优化算法粒子群优化算法是由美国卡尔弗利技术学院的 James Kennedy 和 Russell Eberhart 在1995年提出来的。

它是一种模拟鸟群觅食行为的优化算法，通过模拟鸟群中鸟的行为和迁徙机制来寻找最优解。

粒子群优化算法的基本思想是通过不断调整搜索空间中各个解的位置和速度，来寻找最优解。

在每一代中，根据当前位置和速度，更新粒子的位置和速度，通过不断迁徙和调整，最终找到最优解。

粒子群优化算法的特点是具有较快的收敛速度和较好的局部搜索能力。

它通常用于解决连续优化、离散优化和多目标优化等问题，例如神经网络训练、模式识别、机器学习等领域。

三、人工蜂群算法人工蜂群算法是由意大利研究人员 Marco Dorigo 在2005年提出的一种模拟蜜蜂觅食行为的优化算法。

它是一种群智能算法，模拟蜜蜂在寻找食物和回巢过程中的行为和交流机制。

遗传算法文献综述

遗传算法文献综述

20世纪50年代末，国外就有人开始进行课程编排问题研究，Judit Csima & C.C. Gotlieb[16]曾形象化描述并提出一个求解课表问题的数学模型，上世纪70年代，Even和Cooper[17]等人证明了排课问题就是一个NP-Hard问题。

而NP 问题除了穷举法没有绝对的求解方法，这有效地回答了排课在应用中遇到困难的原因，同时认识到了课表编排的复杂性，从理论上证明了要解决大规模的排课问题单纯依靠数学方法是行不通的。

印度Vastapur 大学管理学院的Arabinda Tripathy 在1992年进行了课表编排研究，他在进行课表编制过程中，充分地考“人”的因素，并以“人”为单位进行课表编排，但是效果却差强人意[18]。

有学者指出，可以通过适当地减少变量的个数，从而使得在排课时，最大程度地减少计算量，但是，这种思想无疑是不可取的，因为排课属于一个多目标的优化问题，减少变量的个数，人为地造成课程之间的矛盾[19]。

有学者设计了多重课组进行排课，具体是根据学生自主选课的冲突情况，如果选课学生人数过多，教学与教室之间冲突情况严重，则可以在一周内开设一定数量的重复课程，来解决选课学生人数多的矛盾，但是这种方法的随机性较大，无法从根本上解决排课过程中多目标问题。

加拿大Montreal 大学的Jacques A．Ferland 等人通过研究，认为可以将排课问题分解成两个关联程度较高的子问题：即分成时间表和课程分组，并构造相应的启发函数和惩罚因子，来试图解决排课问题[20]。

在排课过程中，Jacques A．Ferland 等人将SAPHIR 课程调度决策支持系统分成多个功能模块，如数据处理、自动优化、交互优化等模块，利用多重课组来协调解决排课过程中出现的主要矛盾[21]。

Colomi 等人将具有自适应寻优能力的遗传算法用于课程编排问题求解，首先与高校教学过程相关的因素进行编码，然后采用遗传算法模拟自然界的选择、交叉、变异算子寻找最优排课方案，并应用到当前一所高中的排课系统中。

遗传算法与模型预测控制的结合研究综述

遗传算法与模型预测控制的结合研究综述

遗传算法与模型预测控制的结合研究综述引言在现代科学和工程领域中，模型预测控制（Model Predictive Control, MPC）作为一种强大的控制方法，已经得到了广泛的应用。

然而，MPC的设计和优化过程往往是复杂且耗时的。

为了解决这一问题，研究人员开始探索将遗传算法（Genetic Algorithm, GA）与MPC相结合的方法，以提高控制系统的性能。

本文将对遗传算法与模型预测控制的结合研究进行综述。

遗传算法的基本原理遗传算法是一种模拟自然遗传和进化过程的优化算法。

它通过模拟自然选择、交叉和变异等过程，来搜索问题的最优解。

遗传算法的基本原理包括个体编码、适应度评价、选择、交叉和变异等步骤。

个体编码是将问题的解表示为一个染色体，适应度评价是根据问题的目标函数来评估染色体的优劣，选择是根据适应度值选择优秀的个体，交叉是将两个个体的染色体进行交换，变异是对染色体进行随机改变。

遗传算法在模型预测控制中的应用遗传算法在模型预测控制中的应用主要包括参数优化和约束处理两个方面。

参数优化是指通过遗传算法来寻找最优的控制参数，以使系统的性能指标达到最佳。

约束处理是指通过遗传算法来处理系统约束条件，以确保控制系统的稳定性和安全性。

在参数优化方面，研究人员通常将MPC的控制参数作为染色体的编码，以目标函数的最小化为优化目标，通过遗传算法来搜索最优的控制参数。

例如，某些研究将MPC的预测模型参数和控制权重作为染色体的编码，通过遗传算法来优化这些参数，以使系统的性能指标如稳定性、响应速度等达到最佳。

在约束处理方面，遗传算法可以用于处理MPC中的约束条件，例如状态变量的上下限、输入变量的变化率限制等。

通过将约束条件转化为适应度函数，遗传算法可以搜索满足约束条件的最优解。

一些研究还将遗传算法与其他优化方法相结合，以提高约束处理的效果。

结合研究的案例分析为了更好地理解遗传算法与模型预测控制的结合，我们将对一些相关的案例进行分析。

遗传算法的综述

遗传算法的综述


１ 遗传算法 的基本原理
在自 然界 中 ．由于 同一个生物群体 中各个体之间也存在差异 ． 且 对所处环境有 的适应和生存能力也参差不齐 ． 遵照进化论所提 出的 自 然 界生物进化 的基本原则 ： 适者生存 、 优胜劣汰 ． 自然界将淘汰那些适 应能力较差 的个体 但是通过交配继承了父本优 秀的染 色体和遗传基 图１ 遗传算法 的运行过程示意图 因的 ． 或者通过 染色体核基 因的重新组合产生的生物的生命力往往会 更 强， 适 应能力 也更强 。在 自然界 中， 基 因会发生突变 ， 染 色体核基 因 ２ 遗传算法 的特点 的重组是无法控制 的， 但这种无法控制的 ． 小概率的变异 ， 也可能产生 新基 因和生命力更 强的新个体 。在此基础上 。 遗传算法真实 的模拟 自 遗传算法继 承了进化计算 的特征之外 ， 也有其 自 身 的特点 ： 然界生物进化机制进行对 问题 的最优化搜索 。 遗传算法是建立在 自 然 （ １ ） 遗传 算法不是直接 作用在参数变量集 上 ， 而是在求解 问题 的 选择 和种群遗传学基础上 的随机迭代和进化 ． 具有广泛适用性 的搜索 决定因素和控制参数 的编码（ 即染色体 的 ０ 、 １ 编码） 上进行操作 ， 从中 方法 ． 同时具有很强 的全局优化搜索能力。 对于某个 给定 的优化 问题 ， 找到适应值较高 的子 串。而且遗传算法不受 约束条件 的限制 。 目标 函数 为： （ ２ １ 遗传算 法并不是从 单个 点出发执行算法 ． 而是从一个点 的群 日＿ 厂 （ ｘ， Ｙ， ｚ ……） （ Ｘ， Ｙ， Ｚ ……） ∈ｎ Ｈ ∈Ｒ 体开始 ． 这样就可 以提高算 法的效率和程序 的运行速率 ． 也大 大减少 要求 （ Ｘ ｏ ， Ｙ 。 ， Ｚ 。 ） 使得 为极 大值和极小 值 ， 以适 应优化 的需要 。 了陷入局部最优解 的可能性 此外 ， ｎ是 （ ｘ ， Ｙ ， ｚ ……） 的定义域 ， 为实数 ， ， 为解空 间（ Ｘ ， Ｙ ， Ｚ ……） （ ３ ） 遗 传算法利用 了适 应值的信息 ． 适应值 是根据不 同问题 设计 ｅ Ｑ 到实数 域 Ｈ∈ Ｒ的一种映射 。 遗传算法要根据 目标 函数 日设定一 所 得， 针对 的是这个 问题 。 从而减少了其他辅 助信息 的导入 ， 即只需要 个适应性 函数 ｒ ’ 用 以判断某个样本的优劣程度 。 遗传算法 的基本 步骤 对象函数 和编码 串。因此 ， 遗传算法几乎可以处理任何 问题 。 如下 ： （ ４ ） 遗传算法利用概率转移规则 ， 而不是确定性 的规定 。 遗传算法 （ １ ） 编码 ： 定义 问题 的解空间到染色体编码空间的映射 ， 一般是用 采用 的概率仅仅是作为一种 工具来引导其搜索 过程朝着搜索空 间的 二进制将解 空间编码成 由 ０ 和 １ 组成的有限长度字符 串。 一般一个候 更优化 的解 区域移动 选解 （ 个 体） 用一 串符号表示 。 （ ５ ） 遗传 算法在搜索 过程中不容易 陷入局 部最优 ， 即使在所 定义 （ ２ ） 初始化种群 ： 在一定的 限制条件下初始化种群 ， 该种群 的解空 的适应 度函数是 不连续 的非规则的或有噪声的情 况下 ． 也能以很 大的 间的一个子空间 算法将从 初始化种 群开始模拟优胜 劣汰的选择过 概率找到全局最优解 程． 最后选择 出优 秀的群体和个体 。 （ ６ ） 遗 传算法采用 自 然 进化机制来表现 现实复杂 的现象 ， 能够快 （ ３ ） 设计适应度 函数 ： 将种群 中的每一个染色 体解 码成适 于计算 速可靠地解决非 常困难 的问题 机适应度 函数 的形式 ． 并计算其数值 。设计适应度 函数 的主要方 法是 （ ７ ） 遗传算法具有 固有 的并行性 ． 具有并行计算 的能力 。 将 问题 的 目 标 函数转换成合适 的适应度 函数 。 （ ８ ） 遗 传算法具有可扩展性 ． 易于同别的技术混合 、 结合使用 。 （ ４ ） 选择 ： 根据适应 度大小选 择优 秀个体繁 殖下 一代 ， 适 应度 越 高， 则被 选中的概率也越大 。 选择是遗传算法的关键 ， 它体现了 自然界 ３ 遗传 算法的应 用 中适者生存的思 想 遗传算法是 多学科结合与渗透 的产 物 ．已经发展成 为一种 自组 （ ５ ） 交叉 ： 随机选择两个用 于繁殖下一代 的个体 的相 同位置 ， 在选 织 、 自适应 的综合技术 其提供 了一种解决复杂系统优化问题的通用 中的位置进行交换 框架 ， 但不 是没用 固定 的方法 ． 它不依赖于问题的具体领域 。 所以广泛 （ ６ ） 变异 ： 对某个 串中的某一位进行取反操作。 变异模 拟了 自然界 应用于很 多学科 中偶然基 因突变现象 ３ ． １ 函数优化 从步骤 四开 始重复进行 ． 知道满足某一性能指标或者规定 的遗传 函数优化是 遗传算法 的一个经典应用领域 ． 也是对遗传算法进行 代数 。 性能评 价的常用算例 很多学者构造出了各种各样 的复杂形式的测试 步骤 １ 、 ２和 ３ 是实际应用 中关键 ， 步骤 ４ 、 ５ 和６ 进行 三种基 本基 函数 ， 有连续函数也有离散 函数 ． 有凸函数也有凹函数 。 有确定函数也 因操作 。对新生成一代群体进行重复评价 、 选择 、 交叉和变异 ， 如此循 有随机 函数， 有单峰值 函数也有多峰值函数等 用这些几 何性 质各具 环往 复 ．使得群体 中最优个 体的适应度 和群体的平均适 应度不断提 特 色的函数来评价遗传算法的性能 ， 更能反映算法 的本 质效果 而对 高． 直 到最优个体 的适应度达 到某个界限或者最优个体 的适应度 和平 于一些非线性 、 多模型 、 多 目标的函数优化问题 ， 用其他优 化方 法较难 均适应度不能再提高 求解 ． 而遗传算法却可以方便地得到较好 的结果 ３ ． ２ 组合优化 （ 下转第 ３ ６页 ）