遗传算法的改进及其应用研究_图文

1、浙江工业大学硕士学位论文遗传算法的改进及其应用研究姓名：杨海清申请学位级别：硕士专业：计算机应用技术指导教师：黄德才20040501遗传算法的改进及其应用研究摘要遗传算法是模拟自然界生物进化过程与机制求解问题的一类自组织与自适应的人工智能技术，已广泛应用于计算机科学、人工智能、信息技术及工程实践，但在算法性能方面还有不足之处，因而对其进行改进研究具有理论意义和实用价值。国内外对遗传算法已经作过许多改进研究。目前，遗传算法的主要问题有两个：早熟收敛和开采能力差。相应的解决策略是：维持种群个体多样性和增强对局部领域的搜索开采能力。针对遗传算法存在的问题，在总体解决思路的指引下，本文在三个方面对遗传

2、算法进行改进研究。一、将自适应策略引入种间竞争遗传算法。该方法不仅运用交叉算子和变异算子的自适应调节技术协调种内进化过程，而且通过种问竞争频率的自适应调节促进最优个体的生成。二、将小生境技术和单纯形方法融入遗传算法中提出一种新的基于小生境的混合遗传算法。该方法一方面运用小生境技术增强遗传算法“探测”能力，另一方面通过使用单纯形搜索方法提高遗传算法的“开采”能力，从而有效消除遗传算法的两大弱点。三、针对多模态函数优化问题中的小生境半径变化差异悬殊的特点，给出一种小生境半径自动确定的设计方法。算例仿真表明了该方法的有效性。最后，应用改进的遗传算法求解供水泵站效率优化问题，验证了改进算法的有效性。关

3、键词：遗传算法，种间竞争，小生境技术，多模态函数优化，供水泵站，效率优化，：，：，浙讧业人学砸论立第一章绪论遗传算法（，）是模拟自然界生物进化过程与机制求解问题的一类自组织与自适应的人工智能技术，已广泛应用于计算机科学、人工智能、信息技术及工程实践。相对于其鲜明的生物学基础，它的理论基础公认是不完善的，这种不完善主要表现在没有完整的理论解释算法的机理，缺少广泛而完整的有关收敛性理论，在算法性能方面还有不足之处，这促使研究者对的理论和性能作进一步的研究。遗传算法理论研究的历史回顾遗传算法理论研究的内容主要有：分析的编码方法、适应值函数、微观遗传算子的改进等。当前，的理论研究正逐渐向宏观结构方面不

4、断深入，如并行计算、的局部改进及混合等。下面分别论述：编码方法中的编码在许多问题的求解中，对算法的性能有很重要的影响。简单二进制编码的采用得到了早期理论结果（模式定理、最小字母表原理）的支持，但它仍有许多不足之处。编码¨，”可用于克服二进制编码映射的不连续问题，即欧氏空间中临近点的二进制编码在距离下并不临近。动态参数编码的提出是为了克服搜索效率与表示精度问的矛盾，同时对克服过早收敛现蒙也有所帮助。），多值编码、实数编码、区间值编码、编码、对称编码以及将以往的合成编码分解成多个相对独立编码的编码策略等多种编码方法也都被证明各有优缺点。这些编码方法的提出是启发式的，缺乏一个理论基础来判断

5、各种编码方法的好坏并指导它们的设计。为了缓解二进制编码带来的“组合爆炸”和的早熟收敛问题，提出了十进制编码。浙江：业人学坝论文适应值函数在中，适应值是用来区分群体中个体的好坏。是基于适应值对个体进行选择，以保证适应值好的个体有机会在下一代中产生更多的予个体。在使用求解具体问题时，适应值函数的选择对算法的收敛性以及收敛速度的影响较大，针对不同的问题需根据经验来确定相应的参数。例如：考虑函数在搜索点的函数值及其变化率，并将浚信息加入适应值函数，使得按概率选择的染色体不但具有较小的函数值（对极小化问题而言），而且具有较大的函数变化率值。实验结果表明，这类方法的收敛速度明显高于标准。基于约束区域神经网

6、络的动态，将的全局搜索和约束区域神经网络模型的局部搜索结合起来。利用动态确定神经网络模型的初始点，同时使用神经网络确定动态的适应值函数。，微观遗传算子的改进的个遗传算子分别是选择、交叉和变异。选择体现“适者生存”的原则，通过适应值选择优质个体而抛弃劣质个体。杂交能使个体之间的遗传物质进行交换从而产生更好的个体。变异能恢复个体失去的或未开发的遗传物质，以防止个体在形成最优解过程中过早收敛。下面分别介绍选择、交叉和变异个算子的主要研究内容。一、选择算子选择策略的选取在的操作中是很重要的一个环节，它的一个重要特点是它几乎独立于算法的其它部分。出于选择策略对遗传搜索过程具有较大的影响，很多人早就意识到

7、它在中的重要性。所以，近年来不同的选择策略相继被提出。等人概括了种选择方法【。选择算子的收敛模型由首次引入，随后由和作了扩展，并提出了取代时问的概念，可以对各种选择策略之间选择压力进行定量比较。讨论了选择强度在收敛分析中的应用。对选择压力进行了推广，在特定条件下几个不同选择算子的收敛特性已经被成功建模，包括比例选择、锦标赛选择和截断选择。和分析了噪声对锦标赛选择收敛特性的影响。”针对问题，讨论了取代时间和基因漂移的相互作用。”提出了具有破坏性选择的，这个算法选择优秀和低劣个体，实验显示这个算法在解决模式里有许多大的变动或者斯江业人学坝论文欺骗问题时更有用。二、变叉算了交叉算子使不同个体问的基因

8、互换。在不同成员中进行基因互换是为了能够在下一代产生新的成员。等人概括了种杂交方法。吴少岩”等研究了交配箅子与其探索子空问的关系，提出设计良好算子的指导性原则，并构造出一种启发式交配算子。三、变异算子变异操作是为了在运算过程中能改变某些成员的值，以避免失去一些有用的基因，防某些成员的值处于不变状态，是一种防止算法早熟的措施。等人总结了种变异技术：管理变异、变化的变异概率和单值运算”。考虑将被优化函数的梯度或一阶差分引入到十进制实数编码的变异算子中，实现了定向变异”】。为克服传统变异算子不能有效地保持同一基因位上等位基因的多样性，提出用二元变异算子代替传统的变异算子忡。通过引入位改进子空间的概念

9、，对不同情形下突变概率的最优选取进行了分析】。此外，对于不同问题提出了不同的自适应算子，如从染色体个体个性化和染色体编码基因位个性化两个方面对标准变异算子进行改进：根据染色体的相似性，提出种群差异度的概念，并依据种群差异度自适应地调整遗传参数，交叉率与突变率两个参数随着串的适应值变化而变化。遗传算法的宏观结构改进在群体进化过程中，遗传算子并不完全具备将群体引导向编码空间的最佳静态适应值模式的能力，尽管这一能力是我们期望的。所以，从整体上讲，单纯地采用微观策略及实施遗传算子的参数控制，并不能保证求解优化问题的全局性和鲁棒性。因此提出遗传策略的另一个概念宏观遗传策略（），即通过对流程和结构的再设计

10、改变的宏观特征，或者以流程为基础，引入其它算法构成混合（，），以期提高求解优化问题全局最优解的能力。浙打业人学琐论义讯的宏观结构丰要在以方面进行改进研究。、的并行计算并行算法的基本思想是将一个复杂的任务分解为多个较简单的子任务，然后将各予任务分别分配给多个处理器并行执行求解。例如，把高性能并行应用到大型并行计算机，这种分而治之的思想可以用不同的方法和途径实现，直接导致了各种不同类型的并行。并行可以分为四大类¨】：全局并行、粗粒度并行、细粒度并行和混合并行。优于传统优化算法之一在于它固有的并行性。侯广坤等人讨论了并行的迁移现象及群体规模估算模型¨，分析了迁移的过程，揭示了迁移

11、的实质，并提出了在理想条件下的迁移计算模型。基于迁移计算模型导出了粗粒度并行进化质量估量模型。二、的局部改进由于涉及精度、可靠性、计算时间、探索与开采等诸多问题，通过改进本身在某种程度上可以提高求解问题的性能。针对各种情况有不同的改进，如：分层型：变区域多层：正交多目标最优化；具有空间平滑技术的：基于灾变的多群体；基于共生策略的多模式进化算法；将和神经网络有效结合起来，利用神经网络的学习功能，构造知识模型，用来引导群体中某些个体进化的；通过对个体基因不同年龄的不同操作，提出具有年龄结构的，可克服中存在的主要问题及过早收敛问题。三、混合混合的实质是通过将不同算法的优点有机结合，改善单纯的性能。如

12、将模拟退火算法与结合；在简单中加入局部搜索机制贪心算法。将（）算法的理论移植到中来的统计。用来解决模糊寻优问题的模糊。结合可变多面体法和正交的混合算法”。遗传算法目前存在的主要问题从本质上来讲，无论是传统，还是实施特定遗传策略的，其基本搜索能力均来自于群体和选择、交叉、变异等三种遗传算子。采用合适的遗传策略对摊人革协！论群体实施交叉和变异操作，促使山低阶模！成高阶模式的址化过程中的突现行为（）的发生，从嘶克服模式的炊骗性，发现编码空问匕的全局撮优解位串。作为一种优化阃题求解的随机搜索过程，与任何基于解空闻上的个体或群体、单点或多点的搜索方法一样，当问题解空间存在多个局部极值点时，比如多峰函数优

13、化问题，搜索方法应当在求泛和求精的能力方面进行恰当平衡，以充分利用计算资源。一般来讲，探索解空间上的全局最优解需要较长的时间，具有较大的随机性；完善当前局部最优解则应当充分利用已获得的解信息快速逼近局部极值点，尽量减少资源消耗并提高解的质量。在对连续多模式函数求最优值时通常面临一定的不足，这主要是由于本身的大缺陷造成的，即早熟收敛和开采能力差。这些缺陷使得在大量问题中不具有实用价值。实际上，早熟收敛的发生常常使得只能获得个局部优化值，而得不封全局最优值。而丌采能力差叉常导致在获得一定精度结果时收敛速度缓慢。早熟收敛的主要原因是种群中缺乏个体多样性（）。因此克服这个问题的一种有效方法是维持种群的

14、多样性，从而在进化过程中有利于对搜索区域进行连续探测。本文的研究思路和主要工作生物是从低级、简单的类型逐渐进化为高级、复杂的类型。自然选择学说认为，生物要生存，就必须进行生存竞争，包括种内竞争、种问竞争以及生物跟无机环境之间的竞争等三个方面。在竞争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代：相反。产生后代的机会也少得多。目前，基本遗传算法所采用的遗传算子都是在同一组解群中产生的，即只模拟生存竞争中的釉内竞争。而忽略了种洲竞争，因而存在“封闭竞争”问题。我们对现有的基于种问竞争的遗传算法进千亍分析，提出了改进方案。小生境技术（）是一种能够维持种群多样牲的有效方法，它能

15、增强新搜索区域的探测能力。而混合能更高效、更精确和高可靠地解决连续多模式优化问题，被认为是提高解决复杂优化问题性能的一牵有效方法。在本研究巾，我们将小生境技术和一弛纯形方法融入遗传算法中提出种新的基于小“境技术的混合遗传算法。该方法方面运用小生境技术增强遗传算法全局“探测”能力，另一方面通过使用单纯形搜索方法提高遗传算法的局部“丌采”能力，因此能有效消除遗传算法的大弱点：早熟收敛和开采能力不足。由于小生境的性能易受小生境半径（）的影响。特别在多模态函数优化问题中，往往出现小生境半径变化差异非常悬殊的特征。一般在研究的改进算法时，小生境半径是预先设定的，或作离散值分析，对优化问题的求解带来不确定

16、性。因此，本研究也就小生境半径的自动确定问题给出一种设计方法。本论文的结构安排如下：第一章绪论，介绍遗传算法理论研究的现状、存在的主要问题以及研究思路；第二章遗传算法及其微观改进技术，介绍遗传算法的计算流程、参数选择以及基本数学性质，也介绍了单纯形方法：第三章基于种问竞争的遗传算法的改进，给出一种自适应算法的设计方法以及算例仿真结果：第四章小生境混合遗传算法，详细分析了将小生境技术和单纯形方法融入遗传算法的设计原理，仿真步骤以及与其它算法的比较结果；第五章多模态遗传算法小生境识别技术，详细分析了一种小生境半径的自动确定方法，算法设计以及与其它算法的比较结果；第六章改进遗传算法在供水泵站效率优化

17、阃题中的应用，介绍了用改进的遗传算法求解具体实例的过程；第七章总结与展望。浙江人学坝论义第二章遗传算法与微观改进技术遗传算法抽象于尘物体的进化过程，通过全面模拟自然选择和遗传机制，形成一种具有“生成检验”的搜索算法。遗传算法以编码空间代替问题的参数空侧，以适应度函数为评价依掘，以编码群体为进化基础以对群体中个体位串的遗传操作实现选择和遗传机制，建立起一个迭代过程。在这一过程中，通过随机重组编码位串中重要的基因，使新一代的位串集合优于老一代的位串集合，群体的个体不断进化，逐渐接近最优解，最终达到求解问题的目的。整体优化问题整体优化问题的严格定义如下。定义给定非空集合作为搜索空间，：一尺为目标函数

18、，整体优化问题作为任务：（）（）给出，亦即在搜索空间中找到至少一个使目标函数最大化的点。函数值（）。称为一个整体极大值，当且仅当，（）（）（）成立时，被称为一个整体极大值。将所有整体极大值点的集合记为。显然，厂非空是求解优化问题（）适定的最基本要求。有时也把中的点称为可能解或候选解。假设在上给定了某个距离度量，如果对，使得对垤，（工）厂（）蔓（），则称（）极大点，）为一个局部极大值。显然，整体极大点定是局部极大点，但反之则未必。当目标函数厂有多个局部极大点时，它被称为多模念函数（）。刈，通常采用的度量是海明（）距离，办即两个二进制位串取值不相司的位的个数。而当几：，】时，一般使用的度量就是最普

19、通的欧氏距离。遗传算法的基本流程遗传算法在整个进化过程中的遗传操作是随机性的，但它所呈现出的特性并不是完全随机搜索，它能有效地利用历史信息来推测下一代期望性能有所提高的寻优点集。这样一代代地不断进化，最后收敛到一个最适应环境的个体上，求得问题的最优解。遗传算法所涉及的五个要素是：参数编码、初始群体的设定、适应度函数的设计、遗传操作的设计和控制参数的设定。简单遗传算法的基本流程结构”如图所示。¨计弹目标函数值）函数值向适应值唑）适应氆调整图简单遗传算法计算流程酗算绒懈蝌奴摒蝴三¨”眭浙江业人学！；论殳从【蛔巾可以看小，遗传算法的运行过程是一个典型的迭代过程，其必须完成的：作内

20、容和基本步骤如下：、选择编码策略，把参数集合的解域转换为位串结构空问；、定义适应值函数（）：、确定遗传策略，包括选择种群大小斤，选择、交叉、变异方法，以及确定交叉概率。、变异概率。，等遗传参数：、随机初始化生成群体；、计算群体中个体位串解码后的适应值（）；、按照遗传策赂，运用选择、交叉和变异算子作用于群体，形成下一代群体；、判断群体性能是否满足某一指标，或者己完成预定迭代次数，不满足则返回步骤，或者修改遗传策略再返回步骤。遗传编码按照遗传算法的工作流程，当用遗传算法求解问题时，必须在目标问题实际表示与遗传算法的染色体位串结构之间建立联系，即确定编码和解码运算。般来说，参数集及适应函数是与实际问

21、题密切相关的，往往由用户确定。由于遗传算法计算过程的鲁帮性，它对编码的要求并不苛刻。实际上，大多数问题都可以采用基因呈一维排列的定长染色体表现形式，尤其是基于，）符号集的二进制编码形式。然而，编码的策略或方法对于遗传算子，尤其是对于交叉和变异算子的功能和设计有很大的影响。按照遗传算法的模式定理州，往往采用二进制编码设计，使得相同的问题编码空间对应于最大的模式空间。二进制编码将问题空间的参数表示为基于字符集，）构成的染色体位串。设一维连续实函数，（），】采用长度为的二进制字符串进行定长编码，建立位串空间：盯，），日（口女，口，口“），口，）女：，；，；浙江业人学！论文其个体的量表示为。（吼：，。

22、），其字符串形式为。吼，（从右到左依次表示为从低位到高位），凡称为个体吒剥应的位串。表示精度为：三兰。一将位串个体从位串空间转化成问题参数空间的译码函数：，）斗的公式定义为，一，口“）“一、葛。）（）对于一维连续函数厂（），（扎，：，。），一，】。一，），各维变量的二进制编码位串的长度为，那么的编码从左到右依次构成总长度为圭，的二进制编码位串。相应的编码空间为该空间上的个体位串结构为。，（口；，口；，。，“，口】，口，口虬，。一，口：，口：，口，一，口，日；，。，口；。），），口：（。刖“口；日，口：口；“”！。对于给定的二进制编码位串“，译码函数：，叶的形式为轳州一。“，）”嚣（缸其中，：。

23、，口：！，口：，为个体位串的第段。采用二进制编码的遗传算法进行数值优化时，可以通过改变编码长度，协调搜索精度和效率之间的关系。和“。提出了参数动态编码（，）的策略，类似于搜索空间尺寸变换的方法。当稳定的基因位数超过某个值后，用变焦操作以提高编码精度。此外，二进制编码还有一些变种，如编码“、二倍体（）编码”】等，对某些问题类型的求解已有人做了大量试验，并提出了一些有针对性的参数编码原则。浙江业人学坝仑殳适应度函数遗传算法将问题空表示为染色体位串空问，为了执行“适者生存”的原则，必须刘个体位串的适应眺进行评价。冈此，适应函数（）就构成了对个体的生存能力评价。根据个体的适应值，就可决定它在此环境下的

24、生存能力。一般来说，好的染色体位串结构具有比较高的适应函数值，即可以获得较高的评价，具有较强的生存能力。由于适应值是群体中个体生存机会选择的唯一确定性指标，所以适应函数的形式直接决定着群体的进化行为。为了能够直接将适应函数与群体中的个体优劣度量相联系，在遗传算法中适应值规定为非负，并且在任何情况下总是希望越大越好。若用。表示位串空间，。上的适应值函数可表示为厂：斗，为实值函数，其中月表示非负实数集合。对于给定的优化问题（工）扛“，），目标函数有正有负，甚至可能是复数值，所以有必要通过建立适应函数与目标函数的映射关系，保证映射后的适应值是非负的，而且目标函数的优化方向应对应于适应值增大方向。针对

25、进化过程中关于遗传操作的控制的需要，选择函数变换：斗，使得对于最优解厂（）（）（阻，）。、对最小化问题，建立如下适应函数（）和目标函数（）的映射关系：、厂，；？“一九。括（。（）其中，可以是一个输入值或是理论上的最大值。或者是到目前所有进化代或最近代中（）的最大值，此时。随着进化代数会有变化。、对于最大化问题，一般采用下述方法：八加侄”黧。卜（）式中，。既可以是特定的输入值也可以是当前所有进化代或最近代中（）的最小值。若（）（为最大化问题，且（），】），仍然需要针对进化过程的控制日标选择某函数变换，以便于制定合适的选择策略，使得遗传算法获得最大的进化能力和最佳的搜索效果。遗传算子标准遗传算法的

26、操作算子一般包括选择（）、交叉（）和变异（）三种基本形式，它们构成了遗传算法具备强大搜索能力的核心，是模拟自然选择以及遗传过程中发生的繁殖、杂交和突变现象的主要载体。遗传算法利用遗传算子产生新一代群体来实现群体进化，算子的设计是遗传策略的主要组成部分，也是调整和控制进化过程的基本工具。一、选择算子选择即从当仃群体中选择适应值高的个体以生成交配池（）的过程。目前，主要有适应值比例选择（）、选择、排序选择（）、联赛选择（）等形式。为了防止由于选择误差，或者交叉和变异的破坏作用而导致当前群体的最佳个体在下一代丢失，提出了精英选择（）策略。另外，等还提出了稳态选择方法（）。、适应值比例选择适应值比例选

27、择是最基本的选择方法，其中每个个体被选择的期望数量与其适应值和群体平均适应值的比例有关，通常采用轮盘赌（）方式实现。这种方式首先计算每个个体的适应值，然后计算出此适应值在群体适应值总和中所占的比例，表示该个体在选择过程中被选中的概率。选择过程体现了生物进化过程中“适者生存，优胜劣汰”的思想，并且保证优良基因遗传给下一代个体。对于给定的规模为的群体娩，：，。，个体口，的适应值为（。），其选择概率为，（。，）：掣，：，。（）（）浙，业学删。论奠浚，决定后代利洋中个体的概率分布。经过选择搽作叫二成用于繁殖的交配池，在父代耳，群中每个个体生存的期望数目为：，）（，）”，（，），（）当群体中个体适应值的

28、差异非常大时，最佳个体与最差个体被选择的概率之比（选择压力）也将按指数增长。最佳个体在下一代的生存机会将显著增加，而最差个体的生存机会将被剥夺。当前群体中的最佳个体将快速充满整个群体，导致群体的多样性迅速降低，也就过早地丧失了进化能力。这是适应值比例选择容易出现的问题。、选择在群体进化过程中，不同阶段需要不周的选择压力。早期阶段选择压力较小，我们希望较差个体也有一定的生存机会，使得群体保持较高的多样性；后期阶段选择压力较大，我们希望缩小搜索领域，加快当前最优解改善的速度。为了动态调整群体进化过程中的选择压力，和设计了选择方法。个体选择概率为川：兰，川扣（圳，（）了，一，稚，（，”莒其中，是退火

29、温度。随着迭代的进行逐步缩小，选择压力将随之升高。和通过一组试验分析，认为该选择方法明显好于适应值比例选择”。是控制群体进化过程中选择压力的关键，一般的选择需要考虑预计最大进化代数。、排序选择排序选择方式是将群体中个体按其适应值由大到小的顺序摊成一个序列，然后将事先设计好的序列概率分配给每个个体。显然，排序选择与个体的适应值的绝对值无直接关系，仅仅与个体之间的适应值相对大小有关。排序选择不利用个体适应值绝对值的信息，可以避免群体进化过程的适应值标度变换。由于排序选择概率比较容易控制，所以在实际计算过程中经常采用，特别是适用于动态调整选择概率，根掘进化效果适时改变群体选择压力。最常用的排序选择方

30、法是采用线性函数将队列序号映射为期望的选择概率，即线性排序选择（）。浙门：业人学坝论史、联赛选择联赛选择九勺丛本思想是从当的群体中随机选择定数量的个体（放回或不放圈），将其中适应值最大的个体保存到下一代。反复执行该过程，直到下一代个体数量达到预定的群体规模。联赛规模用表示，也称为一联赛选择（日一）。联赛选择与个体的适应值有削接关系，注重适应值大小的比较。一般取。同样，联赛选择的选择概率也是比较容易控制的，实际计算中也经常采用，适用于在迭代过程中动态调整选择概率，将进化效果与群体选择压力联系起来。、精英选择从的整个选择策略来看，精英选择是群体收敛到优化问题最优解的一种基本保障。如果下一代群体的最

31、佳个体适应值小于当前群体最佳个体的适应值，则将当前群体最佳个体或者适应值大于下一代最佳个体适应值的多个个体直接复制到下一代，随机替代或替代晟差的下一代群体中的相应数量的个体。对于给定的第代规模为的群体（）溉（），：（），。（，），精英选择可用伪码描述如下：厂。）（），（：（），（。（，）、。）（，】）（，），一，（。）：）（，）。（，）。（，），口）（）（，）口，（，）尸）口：（，）（，），（，）（）日：（）浙江业人学坝】论业采这种策略的遗传算法，一般称为基于精英选抒模型的遗传算法（）。二、交叉算子交叉操作是进化算法中遗传算法具备的原始性的独有特征。交叉算子是模仿自然界有性繁殖的基因重组过程，

32、其作用在于将原有的优良基因遗传给下一代个体，并生成包含更复杂基因结构的新个体。交叉操作一般分为以下几个步骤：、从交配池中随机取出要交配的一对个体：、根据位串长度己，对要交配的一对个体，随机选取【，一中一个或多个的整数做为交叉位置：、根据交叉概率，（卫）实施交叉操作，配对个体在交叉位置处，相互交换各自的部分内容，从而形成新的对个体。通常使用的交叉算子包括一点交叉、两点交叉、多点交叉、一致交叉等形式。和认为一致交叉算子优于多点交算，并提出了一种带偏置概率参数的致交叉（），不存在多点交叉算子操作引起的位置偏差，任意基因位的重要基因在致交叉乍用下均可以重组，并遗传给下一代个体。三、变异算子变异操作模拟

33、自然界生物体进化中染色体上某位基因发生的突变现象，从而改变染色体的结构和物理性状。在遗传算法中，变异算子通过按变异概率。随机反转某位等位基因的二进制字符值来实现。对于给定的染色体位串，口：盘。，具体操作如下：。（。，）：口：口”。扫（。，茎，（，（）生成的新个体为疗扣口；。其中。工，是对应于每一个基因位产生的均匀随机变最，。浙业人学倾论艾为了保证个体变异后不会与其父代产生太大的差异，变异概率一般取值较小，以保旺种群发胜的稳定性。当交叉操作产生的后代个体的适应值不再比它们的前辈更好，但又未达到全局最优解时，就会发生成熟前收敛或早熟收敛（）。这时引入变异算子往往能产生很好的效果。一方面，变异算子可

34、以使群体进化过程中丢失的等位基因信息得以恢复，以保持群体中的个体差异性，防止发生成熟前收敛：另一方面，当种群规模较大时，在交叉操作基础上引入适度的变异，也能够提高遗传算法的局部搜索效率。在群体进化的整个过程中，交叉操作是主要的基因重组和群体更迭的手段，变异操作的作用是第二位的，变异算子仅仅充当背景性的角色（）。在很多组合优化问题中，往往存在着多个最优解或者最优解被环绕在大量的劣解之中，应用求解该类问题很容易形成模式欺骗问题，此时可以采用补算算子（）增加群体多样性或者克服模式欺骗性。基于，字符集表示的二进制染色体位串：，补算算子具体操作形式如下：（，）：口；一，一，三（一）对于位串上每一位基因位

35、，若等位基因为，则变为，否则变为，从而形成新的位串。例如：，补算运算结果为：。群体设定遗传算法与传统随机类搜索算法的最大区别之一，在于它的整个算法是在解的群体上进行的。证是这一特点使具有了搜索过程的并行性、全局性和鲁棒陛，可见群体的设定对整个的运行性能具有基础性的决定作用。根据模式定理，群体规模对遗传算法的性能影响很大。若群体规模为，则遗传算子可以从这个个体中生成和检测（）个模式”，并在此基础上不断形成和优化建筑模块，直到找到问题的最优解。群体规模越大，群体中个体的多样性越高，算法陷入局部解的危险就越小。但是随着群体规模增大，计算量也显著增加。若群体规模太小，使遗传算法的搜索空间受到限制，则可

36、能产生未成熟收敛的现象。浙业人学论文初始化群体初始化群体中的个体一般是随机产生的。在不具有关于问题解空问的先验知识的情况下，很难判定最优解的数景及其在可行解空、日中白，分布状况。因此，往往希望在问题解空间均匀采样随机生成一定数目的个体（为群体规模的倍，即），然后从中挑出较好的个体构成初始群体。对于二进制编码，染色体位串上的每一位基因在，上随机均匀选择，所以群体初始化至少需要×次随机取值（三为位串长度）。可以证明初始群体的位串译码到问题实空间中也是均匀分布的。另外，对于带约束域的问题，还需要判定随机初始化位串所对应的参数点是否在可行区域范田之内，所以一般必须借助于闷题领域知识。终止循环

37、的条件关于迭代过程如何终止，一般采用设定最大进化代数的方法。该方法简单易行但不准确。其次，可以根据群体的收敛程度来判断，通过计算种群中的基因多样性测度，即所有基因位的相似性程度来进行控制。第三，根据算法的离线性能和在线性能的变化进行判定。最后，在采用精英保留选择策略的情况下，按每代最佳个体的适应值的变化庸况确定。遗传算法的控制参数及其选择在遗传算法的运行过程中，存在着对其性能产生重大影响的一组参数。这组参数在初始阶段或群体进化过程中需要合理的选择和控制，以使以最佳的搜索轨迹达到最优解。主要参数包括染色体位串长度，群体规模，交叉概率，以及变异概率。许多学者进行了大量实验研究，给出了最优参数建议【

38、。”。、位串长度上：位串长度的选择取决于特定问题解的精度。要求的精度越高，位串越长，但需要更多的计算时间。为了提高运算效率，变长度位串或者在当前所达到的较小可行域内重新编码，是一种可行的方法，并显示了良好性能。、群体规模”：大群体含有较多模式，为遗传算法提供了足够的模式采样容量，可以改进搜索的质量，防止成熟前收敛。但大群体增加了个体适应性评价的计算量，从而使收敛速度降低。一般情况下厅。浙江业人学坝论文、交叉率交义概率控制着交叉算子的应用频率，在每代新的群体中，需要对，×胛个个体的染色体结构进行交叉操作。交叉概率越高，群体中新结构的引入愈快，已获得的优良基因结构的丢失速度也相应升高。而

39、交叉概率太低则可能导致搜索阻滞。一般，。、变异概率变异操作是保持群体多样性的有效手段，交叉结束后，交配池中的全部个体位串上的每位等位基因按变异率。随机改变，因此每代中大约发生。，××次变异。变异概率太小，可能使某些基因位过早丢失的信息无法恢复：而变异概率过高，则遗传搜索将变成随机搜索。般取。实际上，上述参数与问题的类型有着直接的关系。问题的目标函数越复杂，参数选择就越困难。从理论上讲，不存在一组适用于所有问题的最佳参数值，随着问题特征的变化，有效参数的差异往往非常显著。因此，如何设定遗传算法的控制参数以使遗传算法的性能得到改善，还需要结合实际问题深入研究，以及有赖于遗传算法

40、理论研究的新进展。遗传算法数学性质模式定理在遗传算子选择、交叉、变异的作用下，那些低阶、长度短的、超过群体平均适应值的模式的生存数量，将随着迭代次数的增加以指数级增长。建筑模块假设定义长度短的、低阶的、适应值高的模式（建筑模块），在遗传算子的作用下被采样、重组，从而形成高阶、长距、高于群体平均适应值的模式。定理当采用精英保留策略变异概率。固定不变时，求解优化问题（）的基于二进制编码的是以概率收敛的，且收敛性与初始群体无关。浙扭：业人学坝单纯形法简介和提出的单纯形是一乖求解多变量无约束优化问题的直接搜索法。币纯形是指”维空州中一】个顶点构成的凸多面体。给定维空间中的一个单纯形，个项点分别记为，：

41、，。，。单纯形的基本思想是计算胛个顶点的函数值并确定其中的最差点。次差点爿。，最优点瓦，以及单纯形中除最差点外其余各点的形心“，（。一。），（）然后，过。求。的反射点，。（彳。一。），（）反射点有三种可能的情况：、如果，优于。，沿反射方向求扩展点。，！。（。一。），（）这里，称为扩展系数。若。优于。，则以。取代。形成一新的单纯形，否则以，取代。形成一新的单纯形。、如果，次子。但不次于，则以，取代盖。形成一新的单纯形。、如果肖，次于。，说明，取得太远，应当沿彳，以方向压缩。令以为石，和。两点中的较优点、求压缩点。，。（瓦一。），（）这卑，称为压缩系数。若爿。不次子。，则以。取代。形成一新的单纯形

42、，否则进行单纯形缩边，即以乙为基点，将初始单纯形缩小一半。上述情况，无论属于哪一种，所得到新的单纯形，必有一个顶点优于初始单纯形的某个顶点。单纯形法通过循环进行反射、扩展和压缩操作，可馊搜索过程收敛到某个局部最优解或直到满足停止条件，是一种高效的局部搜索策略印。引言第三章基于种间竞争的遗传算法的改进生物是从低级、简单的类型逐渐进化为高级、复杂的类型。自然选择学说认为，生物要生存，就必须进行生存竞争，包括种内竞争、种问竞争以及生物跟无机环境之间的竞争三个方面。在竞争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；相反，产生后代的机会也少得多。遗传算法是一类模拟自然选择和自

43、然遗传机制的随机搜索算法，其主要特点是通过群体搜索策略和群体中个体之问的信息交换，搜索不依赖于梯度的信息”，”。目前，基本遗传算法所采用的遗传算子都是在同一组解群中产生的，即只模拟生存竞争中的种内竞争，而忽略了种间竞争以及生物和无机环境之间的竞争，因而存在“封闭竞争”问题。由于生物与无机环境之间的竞争难以用数学来描述，故本章只对基于种间竞争的遗传算法进行改进。基本遗传算法存在的问题遗传算法的核心问题是寻找求解优化问题的效率与稳定性之问的有机协调性，即所谓的鲁棒性”】。虽然从理论上说，基本遗传算法有很强的鲁棒性，但是就任何一个特殊的领域而言，它却存在一些问题。为此，不少学者对遗传算法作了改进，以解决相应领域的问题。基本遗传算法和上述的改进遗传算法都只产生个群体，即只模拟自然选择生存竞争中的一种竞争方式种内竞争，而不考虑种问竞争和生物与无机环境之间的竞争。图一】是基本遗传运算过程的一个简明计算流程图。浙江。业人学倾论艾图基本遗传算法计算流程图基于种问竞争的基本遗传算法基于种间竞争的基本遗传算法的计算步骤大部分与单种群基本遗传算法一致，不同的是在产生初始群体时，不是产生个群体，而是个群体；基本遗传操作保持不变：在遗传操作后插入群体之间的信息交换，即种阳竞争，该步骤是个群体问个体