浙江工业大学
硕士学位论文
遗传算法的改进及其应用研究
姓名：杨海清
申请学位级别：硕士
专业：计算机应用技术
指导教师：黄德才
20040501
遗传算法的改进及其应用研究
摘要
遗传算法是模拟自然界生物进化过程与机制求解问题的一类自组织与自适应的人工智能技术，已广泛应用于计算机科学、人工智能、信息技术及工程实践，但在算法性能方面还有不足之处，因而对其进行改进研究具有理论意义和实用价值。
国内外对遗传算法已经作过许多改进研究。目前，遗传算法的主要问题有两个：早熟收敛和开采能力差。相应的解决策略是：维持种群个体多样性和增强对局部领域的搜索开采能力。
针对遗传算法存在的问题，在总体解决思路的指引下，本文在三个方面对遗传算法进行改进研究。
一、将自适应策略引入种间竞争遗传算法。该方法不仅运用交叉算子和变异算子的自适应调节技术协调种内进化过程，而且通过种问竞争频率的自适应调节促进最优个体的生成。
二、将小生境技术和单纯形方法融入遗传算法中提出一种新的基于小生境的混合遗传算法。该方法一方面运用小生境技术增强遗传算法“探测”能力，另一方面通过使用单纯形搜索方法提高遗传算法的“开采”能力，从而有效消除遗传算法的两大弱点。
三、针对多模态函数优化问题中的小生境半径变化差异悬殊的特点，给出一种小生境半径自动确定的设计方法。‘算例仿真表明了该方法的有效性。
最后，应用改进的遗传算法求解供水泵站效率优化问题，验证了改进算法的有效性。
关键词：遗传算法，种间竞争，小生境技术，多模态函数优化，供水泵站，效率优化
ＡＳＴＵＤＹＯＮＴＥＣＨＮＩＱＵＥＳＯＦＩＭＰＲＯＶＩＮＧ
ＧＥＮＥＴＩＣＡＬＧＯＲＩＴＨＭＡＮＤＩＴＳＡＰＰＬｔＣＡＴＩＯＮ
ＡＢＳＴＲＡＣＴ
Ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｉｓａｎａｒｔｉｆｉｃｉａｌｉｎｔｅｌｌｉｇｅｎｃｅｔｅｃｈｎｏｌｏｇｙｏｆｓｅｌｆ－ｏｒｇａｎｉｚａｔｉｏｎａｎｄａｄａｐｔａｔｉｏｎ，ｗｈｉｃｈｉｍｉｔａｔｅｓｎａｔｕｒａｌｏｒｇａｎｉｓｍｓ’
ｅｖｏｌｕｔｉｏｎａｒｙｐｒｏｃｅｓｓａｎｄｍｅｃｈａｎｉｓｍｔｏｓｏｌｖｅｐｒｏｂｌｅｍｓ．Ａｌｔｈｏｕｇｈｔｈｅａｌｇｏｒｉｔｈｍｈａｓｂｅｅｎｗｉｄｅｌｙａｐｐｌｉｅｄｔｏｔｈｅｃｏｍｐｕｔｅｒｓｃｉｅｎｃｅ，ａｒｔｉｆｉｃｉａｌ
ｉｎｔｅｌｌｉｇｅｎｃｅ，ｉｎｆｏｒｍａｔｉｏｎｔｅｃｈｎｏｌｏｇｙａｎｄｅｎｇｉｎｅｅｒｉｎｇｐｒｏｊｅｃｔｓ，ｂｕｔｉｔｓｔｉｌｌｓｕｆｆｅｒｓｆｒｏｍｐｅｒｆｏｒｍａｎｃｅｄｅｆｉｃｉｅｎｃｙ．Ｓｏｍｏｒｅｓｔｕｄｉｅｓｓｈｏｕｌｄｂｅｃａｒｒｉｅｄｏｕｔ
ｔｏｉｍｐｒｏｖｅｉｔｓｐｅｒｆｏｒｍａｎｃｅｂｅｃａｕｓｅｏｆｉｔｓｌａｒｇｅｖａｌｕｅｉｎｔｈｅｏｒｙｒｅｓｅａｒｃｈａｎｄｐｒａｃｔｉｃａｌａｐｐｌｉｃａｔｉｏｎ．
Ｐｒｅｓｅｎｔｌｙ，ｔｈｅａｌｇｏｒｉｔｈｍｓｔｉｌｌｓｕｆｆｅｒｓｆｒｏｍｔｗｏｄｒａｗｂａｃｋｓ，ｐｒｅｍａｔｕｒｅｃｏｎｖｅｒｇｅｎｃｅａｎｄｗｅａｋｅｘｐｌｏｉｔａｔｉｏｎｃａｐａｂｉｌｉｔｉｅｓ．Ｔｈｅｅｆｆｅｃｔｉｖｅｗａｙｓｔｏｏｖｅｒｃｏｍｅｓｕｃｈｐｒｏｂｌｅｍｓａｒｅｔｏｍａｉｎｔａｉｎｔｈｅｐｏｐｕｌａｔｉｏｎｄｉｖｅｒｓｉｔｙａｎｄｅｎｈａｎｃｅｅｘｐｌｏｉｔａｔｉｏｎｏｆｌｏｃａｌｓｅａｒｃｈｄｏｍａｉｎｓ．
Ｂｙｕｓｉｎｇｔｈｅｉｄｅａｍｅｎｔｉｏｎｅｄａｂｏｖｅｔｏｓｏｌｖｅｓｕｃｈｐｒｏｂｌｅｍｓ，ｔｈｒｅｅｍｏｄｉｆｉｅｄｓｃｈｅｍｅｓｏｆｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍａｒｅｐｒｏｐｏｓｅｄｉｎｔｈｉｓｐａｐｅｒｆｒｏｍｆｏｌｌｏｗｉｎｇａｓｐｅｃｔｓ：
１．Ａｎｅｗｍｅｔｈｏｄｏｆｃｏｎｎｅｃｔｉｎｇａｄａｐｔｉｖｅｔｅｃｈｎｉｑｕｅｓｗｉｔｈｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｂａｓｅｄ０１＂１ｔｈｅｃｏｍｐｅｔｉｔｉｏｎｂｅｔｗｅｅｎｐｏｐｕｌａｔｉｏｎｓｉｓｐｒｏｐｏｓｅｄ．Ｔｈｅｍｅｔｈｏｄｎｏｔｏｎｌｙｃａｎｃｏｏｒｄｉｎａｔｅｅｖｏｌｕｔｉｏｎａｒｙｐｒｏｃｅｓｓｉｎｓｉｄｅｅａｃｈ
ｐｏｐｕｌａｔｉｏｎｂｙｕｓｉｎｇａｎａｄａｐｔｉｖｅｒｅｇｕｌａｔｉｏｎｏｆｃｒｏｓｓｏｖｅｒａｎｄｍｕｔａｔｉｏｎ
ｆｏｒｍａｔｉｏｎｏｆｂｅｓｔｄｅｓｉｇｎｂｙｕｓｉｎｇｏｐｅｒａｔｏｒｓ，ｂｕｔａｌｓｏｃａｎａｄｖａｎｃｅｔｈｅ
ａｄａｐｔｉｖｅａｄｊｕｓｔｍｅｎｔｏｆｔｈｅｃｏｍｐｅｔｉｔｉｏｎｆｒｅｑｕｅｎｃｙｂｅｔｗｅｅｎｐｏｐｕｌａｔｉｏｎｓ．２．Ａｎｅｗｎｉｃｈｅｈｙｂｒｉｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄ，ｗｈｉｃｈｏｒｇａｎｉｃａｌｌｙｍｅｒｇｅｓｔｈｅｎｉｃｈｅｔｅｃｈｎｉｑｕｅａｎｄｓｉｍｐｌｅｘｍｅｔｈｏｄｉｎｔｏｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ．Ｔｈｅｐｒｏｐｏｓｅｄｍｅｔｈｏｄｎｏｔｏｎｌｙｍａｋｅｓｔｈｅｅｘｐｌｏｒａｔｉｏｎｃａｐａｂｉｌｉｔｉｅｓｏｆｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓｔｒｏｎｇｅｒｔｈｒｏｕｇｈｎｉｃｈｅｔｅｃｈｎｉｑｕｅｓ，ｂｕｔａｌｓｏｈａｓｍｏｒｅｐｏｗｅｒｆｕｌｅｘｐｌｏｉｔａｔｉｏｎｃａｐａｂｉｌｉｔｉｅｓｂｙｕｓｉｎｇｓｉｍｐｌｅｘｍｅｔｈｏｄ．
Ｓｏｉｔｅｆｆｅｃｔｉｖｅｌｙａｌｌｅｖｉａｔｅｓｔｈｅｔｗｏｍａｊｏｒｄｒａｗｂａｃｋｓｏｆｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ．３．ＡｎｅｗｔｅｃｈｎｉｑｕｅｆｏｒｃａｌｃｕｌａｔｉｎｇｎｉｃｈｅｒａｄｉｕｓａｕｔｏｍａｔｉｃａｌｌｙｉＳｐｒｏｐｏｓｅｄ，ａｃｃｏｒｄｉｎｇｔｏｔｈｅｃｈａｒａｃｔｅｒｏｆｔｈｅｌａｒｇｅｄｉｆｆｅｒｅｎｃｅｏｆｔｈｅｎｉｃｈｅｆ．ａｄｉｉｉｎｍｕｌｔｉ—ｍｏｄａｌｆｕｎｃｔｉｏｎｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓ，ＡｓｅｔｏｆｂｅｎｃｈｍａｒｋｆｕｎｃｔｉｏｎｓｉｓｕｓｅｄｔＯｄｅｍｏｎｓｔｒａｔｅｔｈｅｖａｌｉｄｉｔｙｏｆｔｈｅｍｅｔｈｏｄ．
Ｆｉｎａｌｌｙ，ｔｈｅｆｉｒｓｔｍｅｔｈｏｄｍｅｎｔｉｏｎｅｄａｂｏｖｅｉｓａｐｐｌｉｅｄｔｏｔｈｅｅｆｆｉｃｉｅｎｃｙｏｐｔｉｍｉｚａｔｉｏｎｏｆａｗａｔｅｒ－ｓｕｐｐｌｙｂｕｍｐｉｎｇｓｔａｔｉｏｎ，ａｎｄｔｈｅｓｉｍｕｌａｔｉｏｎｒｅｖｅａｌｓｉｔＳｒｅｌｉａｂｉｌｉｔｙ．
ＫＥＹＷＯＲＤＳ：ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ，ｔｅｃｈｎｉｑｕｅ，ｍｕｌｔｉ—ｍｏｄａｌｆｕｎｃｔｉｏｎｓｔｏｌｏｎ，ｅｆｆｉｃｉｅｎｃｙｏｐｔｉｍｉｚａｔｉｏｎｃｏｍｐｅｔｉｔｉｏｎｂｅｔｗｅｅｎｐｏｐｕｌａｔｉｏｎｓ，ｎｉｃｈｅｏｐｔｉｍｉｚａｔｉｏｎ，ｗａｔｅｒ－ｓｕｐｐｌｙｂｕｍｐｉｎｇ
３
浙讧１‘业人学砸１’论立
第一章绪论
遗传算法（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ，ＧＡ）是模拟自然界生物进化过程与机制求解问题的一类自组织与自适应的人工智能技术，已广泛应用于计算机科学、人工智能、信息技术及工程实践。相对于其鲜明的生物学基础，它的理论基础公认是不完善的，这种不完善主要表现在没有完整的理论解释算法的机理，缺少广泛而完整的有关ＧＡ收敛性理论，在算法性能方面还有不足之处，这促使研究者对ＧＡ的理论和性能作进一步的研究。
１．１遗传算法理论研究的历史回顾
遗传算法理论研究的内容主要有：分析ＧＡ的编码方法、适应值函数、微观遗传算子的改进等。当前，ＧＡ的理论研究正逐渐向宏观结构方面不断深入，如并行计算、ＧＡ的局部改进及混合ＧＡ等。下面分别论述：
１．１１编码方法
ＧＡ中的编码在许多问题的求解中，对算法的性能有很重要的影响。简单二进制编码的采用得到了Ｈｏｌｌａｎｄ早期理论结果（模式定理、最小字母表原理）的支持，但它仍有许多不足之处。Ｇｒａｙ编码¨，”’２１１可用于克服二进制编码映射的不连续问题，即欧氏空间中临近点的二进制编码在Ｈａｍｍｉｎｇ距离下并不临近。动态参数编码的提出是为了克服搜索效率与表示精度问的矛盾，同时对克服过早收敛现蒙也有所帮助。）ｔ＃ｌ－，多值编码、实数编码、区间值编码、Ｄｅｌｔａ编码、对称编码以及将以往的合成编码分解成多个相对独立编码的编码策略等多种编码方法也都被证明各有优缺点。这些编码方法的提出是启发式的，缺乏一个理论基础来判断各种编码方法的好坏并指导它们的设计。为了缓解二进制编码带来的“组合爆炸”和ＧＡ的早熟收敛问题，提出了十进制编码Ⅲ。
１１２适应值函数
在ＧＡ中，适应值是用来区分群体中个体的好坏。ＧＡｉＥ是基于适应值对个体进行选择，以保证适应值好的个体有机会在下一代中产生更多的予个体。在使用ＧＡ求解具体问题时，适应值函数的选择对算法的收敛性以及收敛速度的影响较大，针对不同的问题需根据经验来确定相应的参数。例如：
考虑函数在搜索点的函数值及其变化率，并将浚信息加入适应值函数，使得按概率选择的染色体不但具有较小的函数值（对极小化问题而言），而且具有较大的函数变化率值。实验结果表明，这类方法的收敛速度明显高于标准ＧＡｌ３］。
基于约束区域神经网络的动态ＧＡ，将ＧＡ的全局搜索和约束区域神经网络模型的局部搜索结合起来。利用动态ＧＡ确定神经网络模型的初始点，同时使用神经网络确定动态ＧＡ的适应值函数１４．５］。
１，１．３微观遗传算子的改进
ＧＡ的３个遗传算子分别是选择、交叉和变异。选择体现“适者生存”的原则，通过适应值选择优质个体而抛弃劣质个体。杂交能使个体之间的遗传物质进行交换从而产生更好的个体。变异能恢复个体失去的或未开发的遗传物质，以防止个体在形成最优解过程中过早收敛。下面分别介绍选择、交叉和变异３个算子的主要研究内容。
一、选择算子
选择策略的选取在ＧＡ的操作中是很重要的一个环节，它的一个重要特点是它几乎独立于算法的其它部分。出于选择策略对遗传搜索过程具有较大的影响，很多人早就意识到它在ＧＡ中的重要性。所以，近年来不同的选择策略相继被提出。Ｐｏｒｔｓ等人概括了２３种选择方法【６Ｉ。选择算子的收敛模型由Ｇｏｌｄｂｅｒｇ首次引入，随后由Ｇｏｌｄｂｅｒｇ和Ｄｅｂ作了扩展，并提出了取代时问的概念，可以对各种选择策略之间选择压力进行定量比较。Ｍｕｈｌｅｎｂｅｉｎｌ７１讨论了选择强度在收敛分析中的应用。Ｂａｃｋｌ８１对选择压力进行了推广，在特定条件下几个不同选择算子的收敛特性已经被成功建模，包括比例选择、锦标赛选择和截断选择。Ｍｉｌｌｅｒ和Ｇｏｌｄｂｅｒ９９１分析了噪声对锦标赛选择收敛特性的影响。ＴｈｉｅｒｅｎｓＩ”１针对ＢｉｎＩｎｔ问题，讨论了取代时间和基因漂移的相互作用。ＫｕｏＩ”１提出了具有破坏性选择的ＧＡ，这个算法选择优秀和低劣个体，实验显示这个算法在解决模式里有许多大的变动或者ＧＡ
欺骗问题时更有用。
二、变叉算了．
交叉算子使不同个体问的基因互换。在不同成员中进行基因互换是为了能够在下一代产生新的成员。Ｐｏｔｔｓ等人概括了１７种杂交方法１６１。吴少岩Ｉ”１等研究了交配箅子与其探索子空问的关系，提出设计良好算子的指导性原则，并构造出一种启发式交配算子。
三、变异算子
变异操作是为了在运算过程中能改变某些成员的值，以避免失去一些有用的基因，防ｌＥ某些成员的值处于不变状态，是一种防止算法早熟的措施。Ｐｏｔｔｓ等人总结了３种变异技术：管理变异、变化的变异概率和单值运算”１。考虑将被优化函数的梯度或一阶差分引入到十进制实数编码的ＧＡ变异算子中，实现了定向变异ｆ”】。
为克服传统变异算子不能有效地保持同一基因位上等位基因的多样性，提出用二元变异算子代替传统的变异算子忡｝。
通过引入ｉ位改进子空间的概念，对不同情形下突变概率的最优选取进行了分析ｆ１５】。
此外，对于不同问题提出了不同的自适应算子，如从染色体个体个性化和染色体编码基因位个性化两个方面对标准变异算子进行改进：根据染色体的相似性，提出种群差异度的概念，并依据种群差异度自适应地调整遗传参数，交叉率与突变率两个参数随着串的适应值变化而变化。
１．１．４遗传算法的宏观结构改进
在ＧＡ群体进化过程中，遗传算子并不完全具备将群体引导向编码空间的最佳静态适应值模式的能力，尽管这一能力是我们期望的。所以，从整体上讲，单纯地采用ＧＡ微观策略及实施遗传算子的参数控制，并不能保证ＧＡ求解优化问题的全局性和鲁棒性。因此提出ＧＡ遗传策略的另一个概念——宏观遗传策略（ｍａｃｒｏｇｅｎｅｔｉｃｓｔｒａｔｅｇｙ），即通过对ＧＡ流程和结构的再设计改变ＧＡ的宏观特征，或者以ＧＡ流程为基础，引入其它算法构成混合ＧＡ（ｈｙｂｒｉｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓ，ＨＧＡ），以期提高ＧＡ求解优化问题全局最优解的能力。
ｍ讯ＧＡ的宏观结构丰要在以ＶＪＬ方面进行改进研究。
１、ＧＡ的并行计算
并行算法的基本思想是将一个复杂的任务分解为多个较简单的子任务，然后将各予任务分别分配给多个处理器并行执行求解。例如，Ｚｅｉｇｌｅｒ把高性能并行ＧＡ应用到大型并行计算机，这种分而治之的思想可以用不同的方法和途径实现，直接导致了各种不同类型的并行ＧＡ。并行ＧＡ可以分为四大类¨９】：全局并行ＧＡ、粗粒度并行ＧＡ、细粒度并行ＧＡ和混合并行ＧＡ。
ＧＡ优于传统优化算法之一在于它固有的并行性。侯广坤等人讨论了并行ＧＡ的迁移现象及群体规模估算模型¨６Ｊ，分析了迁移的过程，揭示了迁移的实质，并提出了在理想条件下的迁移计算模型。基于迁移计算模型导出了粗粒度并行ＧＡ进化质量估量模型。
二、ＧＡ的局部改进
由于ＧＡ涉及精度、可靠性、计算时间、探索与开采等诸多问题，通过改进ＧＡ本身在某种程度上可以提高ＧＡ求解问题的性能。针对各种情况有不同的改进ＧＡ，如：分层型ＧＡ：变区域多层ＧＡ：正交多目标最优化ＧＡ；具有空间平滑技术的ＧＡ：基于灾变的多群体ＧＡ；基于共生策略的多模式进化算法；将ＧＡ和神经网络有效结合起来，利用神经网络的学习功能，构造知识模型，用来引导群体中某些个体进化的ＧＡ；通过对个体基因不同年龄的不同操作，提出具有年龄结构的ＧＡ，可克服ＧＡ中存在的主要问题及过早收敛问题。
三、混合ＧＡ
混合ＧＡ的实质是通过将不同算法的优点有机结合，改善单纯ＧＡ的性能。如将模拟退火算法与ＧＡ结合；在简单ＧＡ中加入局部搜索机制——贪心算法。将ＳＡ（ｓｔａｔｉｓｔｉｃａｌｈｅｕｒｉｓｔｉｃｓｅａｒｃｈ）算法的理论移植到ＧＡ中来的统计ＧＡ。用来解决模糊寻优问题的模糊ＧＡ。结合可变多面体法和正交ＧＡ的混合算法”’。
１．２遗传算法目前存在的主要问题
从本质上来讲，无论是传统ＧＡ，还是实施特定遗传策略的ＧＡ，其基本搜索能力均来自于群体和选择、交叉、变异等三种遗传算子。采用合适的遗传策略对
摊ｆ｝ｆ．１ＨＥ人‘革协！｝ｊ论ｋ
群体实施交叉和变异操作，促使山低阶模！｝Ｌ＇ｄ－成高阶模式的ｉ址化过程中的突现行为（ｅｍｅｒｇｃｎｔｂｅｈａｖｉｏｒ）的发生，从嘶克服模式的炊骗性，发现编码空问匕的全局撮优解位串。
ＧＡ作为一种优化阃题求解的随机搜索过程，与任何基于解空闻上的个体或群体、单点或多点的搜索方法一样，当问题解空间存在多个局部极值点时，比如多峰函数优化问题，搜索方法应当在求泛和求精的能力方面进行恰当平衡，以充分利用计算资源。一般来讲，探索解空间上的全局最优解需要较长的时间，具有较大的随机性；完善当前局部最优解则应当充分利用已获得的解信息快速逼近局部极值点，尽量减少资源消耗并提高解的质量。
ＧＡ在对连续多模式函数求最优值时通常面临一定的不足，这主要是由于ＧＡ本身的２大缺陷造成的，即早熟收敛和开采能力差。这些缺陷使得ＧＡ在大量问题中不具有实用价值。实际上，早熟收敛的发生常常使得ＯＡ只能获得～个局部优化值，而得不封全局最优值。而丌采能力差叉常导致ＧＡ在获得一定精度结果时收敛速度缓慢。早熟收敛的主要原因是种群中缺乏个体多样性（ｄｉｖｅｒｓｉｔｙ）。因此克服这个问题的一种有效方法是维持种群的多样性，从而在进化过程中有利于对搜索区域进行连续探测。
１．３本文的研究思路和主要工作
生物是从低级、简单的类型逐渐进化为高级、复杂的类型。自然选择学说认为，生物要生存，就必须进行生存竞争，包括种内竞争、种问竞争以及生物跟无机环境之间的竞争等三个方面。在竞争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代：相反。产生后代的机会也少得多。目前，基本遗传算法所采用的遗传算子都是在同一组解群中产生的，即只模拟生存竞争中的釉内竞争。而忽略了种洲竞争，因而存在“封闭竞争”问题。我们对现有的基于种问竞争的遗传算法进千亍分析，提出了改进方案。
小生境技术（ｎｉｃｈｉｎｇｔｅｃｈｎｉｑｕｅ）是一种能够维持种群多样牲的有效方法，它能增强新搜索区域的探测能力。而混合ＧＡ能更高效、更精确和高可靠地解决连续多模式优化问题，被认为是提高ＧＡ解决复杂优化问题性能的一牵ｔ’有效方法。
在本研究巾，我们将小生境技术和Ｎｅｌｄｅｒ—Ｍｅａｄ一弛纯形方法融入遗传算法中提出…种新的基于小“ｉ境技术的混合遗传算法。该方法～方面运用小生境技术增强遗传算法全局“探测”能力，另一方面通过使用单纯形搜索方法提高遗传算法的局部“丌采”能力，因此能有效消除遗传算法的２大弱点：早熟收敛和开采能力不足。
由于小生境ＧＡ的性能易受小生境半径（ｎｉｃｈｅｒａｄｉｕｓ）的影响。特别在多模态函数优化问题中，往往出现小生境半径变化差异非常悬殊的特征。一般在研究ＧＡ的改进算法时，小生境半径是预先设定的，或作离散值分析，对优化问题的求解带来不确定性。因此，本研究也就小生境半径的自动确定问题给出一种设计方法。
本论文的结构安排如下：第一章绪论，介绍遗传算法理论研究的现状、存在的主要问题以及研究思路；第二章遗传算法及其微观改进技术，介绍遗传算法的计算流程、参数选择以及基本数学性质，也介绍了单纯形方法：第三章基于种问竞争的遗传算法的改进，给出一种自适应算法的设计方法以及算例仿真结果：第四章小生境混合遗传算法，详细分析了将小生境技术和Ｎｅｌｄｅｒ—Ｍｅａｄ单纯形方法融入遗传算法的设计原理，仿真步骤以及与其它算法的比较结果；第五章多模态遗传算法小生境识别技术，详细分析了一种小生境半径的自动确定方法，算法设计以及与其它算法的比较结果；第六章改进遗传算法在供水泵站效率优化阃题中的应用，介绍了用改进的遗传算法求解具体实例的过程；第七章总结与展望。
浙江Ｔｑｋ人学坝Ｉｊ论义
第二章遗传算法与微观改进技术
遗传算法抽象于尘物体的进化过程，通过全面模拟自然选择和遗传机制，形成一种具有“生成＋检验”的搜索算法。遗传算法以编码空间代替问题的参数空侧，以适应度函数为评价依掘，以编码群体为进化基础．以对群体中个体位串的遗传操作实现选择和遗传机制，建立起一个迭代过程。在这一过程中，通过随机重组编码位串中重要的基因，使新一代的位串集合优于老一代的位串集合，群体的个体不断进化，逐渐接近最优解，最终达到求解问题的目的。
２．１整体优化问题
整体优化问题的严格定义如下。
定义２．１给定非空集合Ｓ作为搜索空间，ｆ：Ｓ一尺为目标函数，整体优化问题作为任务：
ｍａｘｆ（ｘ）（２－－１）给出，亦即在搜索空间Ｓ中找到至少一个使目标函数最大化的点。
函数值／＋＝ｆ（ｘ’）ｃ＋。。称为一个整体极大值，当且仅当
ｖｚ∈Ｓｊ，（ｚ）ｓｆ（ｘ’）（２－－２）成立时，ｘ’∈Ｓ被称为一个整体极大值。将所有整体极大值点的集合记为ａｒｇｆ’。显然，ａｒｇ厂’非空是求解优化问题（２－－１）适定的最基本要求。有时也把Ｓ中的点称为可能解或候选解。
假设在Ｓ上给定了某个距离度量Ｐ，如果对ｘ’∈Ｓ，ｊ￡＞０，使得对垤∈Ｓ，ｐ（ｘ．工’）＜ｓｊ厂（ｘ）蔓ｆ（ｘ’），则称ｚ’Ｙ０－－＋ＮＮ（１０ｃａｌ）极大点，．ｆｉｘ’）为一个局部极大值。显然，整体极大点～定是局部极大点，但反之则未必。当目标函数厂有多个局部极大点时，它被称为多模念函数（ｍｕｌｔｉ－ｍｏｄａｌｆｕｎｃｔｉｏｎ）。
Ｉ３
刈ｓ＝８‘＝ｆＯ．∥，通常采用的度量是海明（Ｈａｍｍｉｎｇ）距离，办即两个二进制位串取值不相『司的位的个数。而当ｓ＝几：，ｈ，＾】时，一般使用的度量就是最普通的欧氏距离。
２．２遗传算法的基本流程
遗传算法在整个进化过程中的遗传操作是随机性的，但它所呈现出的特性并不是完全随机搜索，它能有效地利用历史信息来推测下一代期望性能有所提高的寻优点集。这样一代代地不断进化，最后收敛到一个最适应环境的个体上，求得问题的最优解。遗传算法所涉及的五个要素是：参数编码、初始群体的设定、适应度函数的设计、遗传操作的设计和控制参数的设定。
简单遗传算法的基本流程结构｛”１如图２—１所示。
¨计弹目标函数值
２）函数值向适应值唑
３）适应氆调整
图２—１简单遗传算法计算流程酗
算
绒
懈蝌奴摒蝴三¨＂”眭
从【蛔２—１巾可以看小，遗传算法的运行过程是一个典型的迭代过程，其必须完成的ｌ：作内容和基本步骤如下：
ｌ、选择编码策略，把参数集合ｘ的解域转换为位串结构空问Ｓ；
２、定义适应值函数ｆ（Ｙ）：
３、确定遗传策略，包括选择种群大小斤，选择、交叉、变异方法，以及确定交叉概率Ｐ。、变异概率Ｐ。，等遗传参数：
４、随机初始化生成群体Ｐ；
５、计算群体中个体位串解码后的适应值ｆ（ｘ）；
６、按照遗传策赂，运用选择、交叉和变异算子作用于群体，形成下一代群体；
７、判断群体性能是否满足某一指标，或者己完成预定迭代次数，不满足则返回步骤６，或者修改遗传策略再返回步骤６。
２２．１遗传编码
按照遗传算法的工作流程，当用遗传算法求解问题时，必须在目标问题实际表示与遗传算法的染色体位串结构之间建立联系，即确定编码和解码运算。～般来说，参数集及适应函数是与实际问题密切相关的，往往由用户确定。
由于遗传算法计算过程的鲁帮性，它对编码的要求并不苛刻。实际上，大多数问题都可以采用基因呈一维排列的定长染色体表现形式，尤其是基于｛Ｏ，１）符号集的二进制编码形式。然而，编码的策略或方法对于遗传算子，尤其是对于交叉和变异算子的功能和设计有很大的影响。
按照遗传算法的模式定理Ｉ州，往往采用二进制编码设计，使得相同的问题编码空间对应于最大的模式空间。
二＋进制编码将问题空间的参数表示为基于字符集｛０，１）构成的染色体位串。
设一维连续实函数，（ｘ），ｘ∈‰ｖ】采用长度为Ｌ的二进制字符串进行定长编码，建立位串空间：
Ｓ‘＝｛盯１，ｎ２，??，ｄＫ），日ｔ＝（口女ｌ，口１２，…，口“），口Ｉｆ∈｛０，１）
女：１，２，．．．，Ｋ；，＝１，２，…，￡；Ｋ＝２‘
其ｌｕ｛Ｊ＇个体的ｌｈ］量表示为ｄ。＝（ⅡⅢ吼：，…，ａ。），其字符串形式为０＝Ｈ。。吼，…％（从右到左依次表示为从低位到高位），凡称为个体吒剥应的位串。表示精度为：Ａｘ：三兰。
２。一１
将位串个体从位串空间转化成问题参数空间的译码函数ｒ：｛Ｏ，１）７斗ｈｖ］的公式定义为
ｘｔ＝№，，ｄ一…，口“）＝“＋ｊｖ．－一ｕｌ、葛Ｌ。２Ｌ－Ｉ）（２—３）对于一维连续函数厂（ｚ），ｚ＝（扎，ｚ：，…，ｚ。），一∈ｈ，ｖ，】０＝１。２一，Ｈ），各维变量的二进制编码位串的长度为‘，那么ｘ的编码从左到右依次构成总长度为￡＝圭，，的
ｉ＝１
二进制编码位串。相应的ＧＡ编码空间为
ＳＬ《。ｊ．ｄ２，…，ｎ０．Ｘ＝２ｔ
该空间上的个体位串结构为
ａ々＝（口；ｌ，口；２，‘。’，Ｏ“１，口々２】，口＾２２，?．．，口虬２，。一，口：Ｉ，口：２，…，口＾，?一，口★ｎＩ，日；２，。‘’，口；。）
ｎ＾∈｛ｏ，１），ｓ＾＝口：ｌ（１。Ｉ２???。刖Ｉ．“＾２１口；２?－?日★２，ｉ…口：ｌ口；２…ａ“ｉ－?－ｄｋ”ｌａｋ”２???ａｋ”！。
对于给定的二进制编码位串“，译码函数Ｆ’：㈣｝‘＿ｈ，叶］的形式为
轳州一。…“，Ｉ）＝”嚣（缸２７
其中，ｄ：。，口：！，…，口：，为个体位串Ｓ＾的第ｉ段。
采用二进制编码的遗传算法进行数值优化时，可以通过改变编码长度，协调搜索精度和效率之间的关系。Ｓｃｈｒａｕｄｏｌｐｈ和Ｂｅｌｅ“２。１提出了参数动态编码（ｄｙｎａｍｉｃｐａｒａｍｅｔｅｒｅｎｃｏｄｉｎｇ，ＤＰＥ）的策略，类似于搜索空间尺寸变换的方法。当稳定的基因位数超过某个值后，用变焦操作以提高编码精度。
此外，二进制编码还有一些变种，如Ｇｒａｙ编码‘２“、二倍体（ｄｉｐｌｏｉｄ）编码１”】等，对某些问题类型的ＧＡ求解已有人做了大量试验，并提出了一些有针对性的参数编码原则。
２．２２适应度函数
遗传算法将问题空｜１＝ｌＪ表示为染色体位串空问，为了执行“适者生存”的原则，必须刘个体位串的适应‘眺进行评价。冈此，适应函数（ｆｉｔｎｅｓｓｆｕｎｃｔｉｏｎ）就构成了对个体的生存能力评价。根据个体的适应值，就可决定它在此环境下的生存能力。一般来说，好的染色体位串结构具有比较高的适应函数值，即可以获得较高的评价，具有较强的生存能力。
由于适应值是群体中个体生存机会选择的唯一确定性指标，所以适应函数的形式直接决定着群体的进化行为。为了能够直接将适应函数与群体中的个体优劣度量相联系，在遗传算法中适应值规定为非负，并且在任何情况下总是希望越大越好。
若用Ｓ。表示位串空间，Ｓ。上的适应值函数可表示为厂：Ｓ‘斗Ｒ＋，为实值函数，其中月＋表示非负实数集合。
对于给定的优化问题ｏｐｔｇ（工）扛∈［“，ｖ］），目标函数有正有负，甚至可能是复数值，所以有必要通过建立适应函数与目标函数的映射关系，保证映射后的适应值是非负的，而且目标函数的优化方向应对应于适应值增大方向。
针对进化过程中关于遗传操作的控制的需要，选择函数变换Ｔ：ｇ斗．ｆ，使得对于最优解ｚ＋ｍａｘ．厂（ｘ＋）＝ｏｐｔｇ（ｘ’）（ｘ’∈阻，ｖ］）。
１、对最小化问题，建立如下适应函数ｆ（ｘ）和目标函数ｇ（ｘ）的映射关系：
、厂ｃｘ，＝｛；？“一ｇ‘ｘ九。ｉｆ括（。ｇ‘ｘ’＜ｃ…’（２－－５）其中，ｃ…可以是一个输入值或是理论上的最大值。或者是到目前所有进化代或最近Ｋ代中ｇ（ｘ）的最大值，此时Ｃ。。随着进化代数会有变化。
２、对于最大化问题，一般采用下述方法：
八加侄∽‰”黧。卜％ｍ’（２－－６）式中，ｃ。。既可以是特定的输入值＋也可以是当前所有进化代或最近Ｋ代中ｇ（ｘ）的最小值。
若ｏｐｔｇ（ｘ）（ｘ∈ｋ’ｍ为最大化问题，且ｍｉｎ（ｇ（ｘ））≥０＠∈ｍ，１，】），仍然需要针对进化过程的控制日标选择某｛ｑｔ函数变换，以便于制定合适的选择策略，使得遗传算法获得最大的进化能力和最佳的搜索效果。
２．２．３遗传算子
标准遗传算法的操作算子一般包括选择（ｓｅｌｅｃｔｉｏｎ）、交叉（ｃｒｏｓｓｏｖｅｒ）和变异（ｍｕｔａｔｉｏｎ）三种基本形式，它们构成了遗传算法具备强大搜索能力的核心，是模拟自然选择以及遗传过程中发生的繁殖、杂交和突变现象的主要载体。
遗传算法利用遗传算子产生新一代群体来实现群体进化，算子的设计是遗传策略的主要组成部分，也是调整和控制进化过程的基本工具。
一、选择算子
选择即从当ｆｉ仃群体中选择适应值高的个体以生成交配池（ｍａｔｉｎｇｐ００１）的过程。目前，主要有适应值比例选择（ｆｉｔｎｅｓｓ—ｐｒｏｐｏｒｔｉｏｎａｔｅｓｅｌｅｃｔｉｏｎ）、Ｂｏｌｔｚｍａｎｎ选择、排序选择（ｒａｎｋｓｅｌｅｃｔｉｏｎ）、联赛选择（ｔｏｕｒｎａｍｅｎｔｓｅｌｅｃｔｉｏｎ）等形式。为了防止由于选择误差，或者交叉和变异的破坏作用而导致当前群体的最佳个体在下一代丢失，ＤｅＪｏｎｇ提出了精英选择（ｅｌｉｔｉｓｔｓｅｌｅｃｔｉｏｎ）策略。另外，Ｈｏｌｌａｎｄ等还提出了稳态选择方法（ｓｔｅａｄｙ－ｓｔａｔｅｓｅｌｅｃｔｉｏｎ）。
ｌ、适应值比例选择
适应值比例选择是最基本的选择方法，其中每个个体被选择的期望数量与其适应值和群体平均适应值的比例有关，通常采用轮盘赌（ｒｏｕｌｅｔｔｅｗｈｅｅｌ）方式实现。这种方式首先计算每个个体的适应值，然后计算出此适应值在群体适应值总和中所占的比例，表示该个体在选择过程中被选中的概率。选择过程体现了生物进化过程中“适者生存，优胜劣汰”的思想，并且保证优良基因遗传给下一代个体。
对于给定的规模为ｎ的群体Ｐ＝娩，ａ：，…，ａ。｝，个体口，的适应值为ｆ（ａ。），其选择概率为
ｐ，（。，）：掣，，：ｌ，２，…，。
（２～７）
∑ｆ（ａ．）
浙ｒ』，１＋业ｋ学删１。论奠
浚，℃决定后代利１｛洋中个体的概率分布。经过选择搽作叫二成用于繁殖的交配池，在父代耳１，群中每个个体生存的期望数目为：
，）（Ⅱ，）＝”Ｐ，（Ⅱ，），Ｊ＝１，２．?－．，＂（２－－８）当群体中个体适应值的差异非常大时，最佳个体与最差个体被选择的概率之比（选择压力）也将按指数增长。最佳个体在下一代的生存机会将显著增加，而最差个体的生存机会将被剥夺。当前群体中的最佳个体将快速充满整个群体，导致群体的多样性迅速降低，ＧＡ也就过早地丧失了进化能力。这是适应值比例选择容易出现的问题。
２、Ｂｏｌｔｚｍａｎｎ选择
在群体进化过程中，不同阶段需要不周的选择压力。早期阶段选择压力较小，我们希望较差个体也有一定的生存机会，使得群体保持较高的多样性；后期阶段选择压力较大，我们希望ＧＡ缩小搜索领域，加快当前最优解改善的速度。为了动态调整群体进化过程中的选择压力，Ｍｉｌｌｅｒ和Ｇｏｌｄｂｅｒｇ设计了Ｂｏｌｔｚｍａｒｍ选择方法。个体选择概率为
Ｐ川ａｊ：＃兰，川扣＂（２圳
，（）＝—了—————～，，＝ｌ，２，’一，稚Ｌ２～ｙ，
ｙｅｌ（ａ，’”
莒
其中，Ｔ＞０是退火温度。ｒ随着迭代的进行逐步缩小，选择压力将随之升高。Ｍｉｌｌｅｒ和Ｇｏｌｄｂｅｒｇ通过一组试验分析，认为该选择方法明显好于适应值比例选择‘２”。ｒ是控制群体进化过程中选择压力的关键，一般７’的选择需要考虑预计最大进化代数。
３、排序选择
排序选择方式是将群体中个体按其适应值由大到小的顺序摊成一个序列，然后将事先设计好的序列概率分配给每个个体。显然，排序选择与个体的适应值的绝对值无直接关系，仅仅与个体之间的适应值相对大小有关。排序选择不利用个体适应值绝对值的信息，可以避免群体进化过程的适应值标度变换。由于排序选择概率比较容易控制，所以在实际计算过程中经常采用，特别是适用于动态调整选择概率，根掘进化效果适时改变群体选择压力。
最常用的排序选择方法是采用线性函数将队列序号映射为期望的选择概率，即线性排序选择（１ｉｎｅａｒｒａｎｋｉｎｇｓｅｌｅｃｔｉｏｎ）。
浙门：ｌｉ业人学坝１’论史
４、联赛选择
联赛选择九勺丛本思想是从当的群体中随机选择?定数量的个体（放回或不放圈），将其中适应值最大的个体保存到下一代。反复执行该过程，直到下一代个体数量达到预定的群体规模。联赛规模用ｑ表示，也称为ｇ一联赛选择（日一ｔｏｕｒｎａｍｅｎｔｓｅｌｅｃｔｉｏｎ）ｍＪ。联赛选择与个体的适应值有削接关系，注重适应值大小的比较。一般取ｑ＝２。
同样，联赛选择的选择概率也是比较容易控制的，实际计算中也经常采用，适用于在ＧＡ迭代过程中动态调整选择概率，将进化效果与群体选择压力联系起来。
５、精英选择
从ＧＡ的整个选择策略来看，精英选择是群体收敛到优化问题最优解的一种基本保障。如果下一代群体的最佳个体适应值小于当前群体最佳个体的适应值，则将当前群体最佳个体或者适应值大于下一代最佳个体适应值的多个个体直接复制到下一代，随机替代或替代晟差的下一代群体中的相应数量的个体。
对于给定的第ｒ代规模为Ｈ的群体Ｐ（ｆ）＝溉（ｆ），ａ：（ｆ），…，ｄ。（，）），精英选择可用伪码描述如下：
厂ｍ。。０）＝ｍａｘ｛ｆ（ａ．（ｆ）），ｆ（ａ：（ｒ）），…，ｆ（ａ。（，）））
、‘。。ｐ＋１）＝ｍａｘ｛ｆ（ａｌ（，＋】））’ｆ（ａ２（，＋１）），’一，ｆ（ａ。０＋１））｝
ｒｅｐｌｉｃａｔｅ｛ｄ：ｐ）｝＝｛ａ★（，）Ｉ。ｆ（ａ￡（，））＞／ｊ。（，＋１），口￡Ｏ）∈Ｊｐ（ｆ）｝
（ｋ＝１，ｏｒｋ＝１，２，…，Ｋ）
ｒｅｐｌａｃｅｒａｎｄｏｍｌｙ｛口，（，＋１）∈尸Ｏ＋１））ｗｉｔｈ｛口：（，）｝
（，＝１，ｏｒＪ＝１，２，…，Ｋ）
ｏｒｒｅｐｌａｃｅｔｈｅｗｏｒｓｔｏｎｅｓｏｆ｛ｄ，（，＋１）∈Ｐ（ｔ＋１））ｗｉｔｈ｛日：（ｆ））
ｅｎｄｉｆ
采＿｜｛Ｊ这种策略的遗传算法，一般称为基于精英选抒模型的遗传算法（ｅｌｉｔｉｓｔｍｏｄｅｌｂａｓｅｄＧＡ）１２４１。
二、交叉算子
交叉操作是进化算法中遗传算法具备的原始性的独有特征。ＧＡ交叉算子是模仿自然界有性繁殖的基因重组过程，其作用在于将原有的优良基因遗传给下一代个体，并生成包含更复杂基因结构的新个体。交叉操作一般分为以下几个步骤：１、从交配池中随机取出要交配的一对个体：
２、根据位串长度己，对要交配的一对个体，随机选取【ｌ，￡一１］中一个或多个的整数ｋ做为交叉位置：
３、根据交叉概率Ｐ，（Ｏ＜卫ｓ１）实施交叉操作，配对个体在交叉位置处，相互交换各自的部分内容，从而形成新的～对个体。
通常使用的交叉算子包括一点交叉、两点交叉、多点交叉、一致交叉等形式。ＤｅＪｏｎｇ和Ｓｐｅａｒｓ认为一致交叉算子优于多点交ｙ．算ｙ－∞１，并提出了一种带偏置概率参数的～致交叉（０．５ｓｘ≤Ｏ．８），不存在多点交叉算子操作引起的位置偏差，任意基因位的重要基因在～致交叉｛乍用下均可以重组，并遗传给下一代个体。
三、变异算子
变异操作模拟自然界生物体进化中染色体上某位基因发生的突变现象，从而改变染色体的结构和物理性状。在遗传算法中，变异算子通过按变异概率ｐ。随机反转某位等位基因的二进制字符值来实现。对于给定的染色体位串Ｓ＝ｄ，口：??盘。，具体操作如下：
。（ｐ。，，ｘ．）：口ｊ＝｛：ｉ口”。ｉｆ扫（。ｘ，茎ｐｍ’，ｒｅ（１，２，?．．，￡｝（２－－１０）生成的新个体为ｓ’＝疗扣≯．口；。其中。工，是对应于每一个基因位产生的均匀随机变最，ｘ，∈［０，ｔ］。
为了保证个体变异后不会与其父代产生太大的差异，变异概率一般取值较小，以保旺种群发胜的稳定性。
当交叉操作产生的后代个体的适应值不再比它们的前辈更好，但又未达到全局最优解时，就会发生成熟前收敛或早熟收敛（ｐｒｅｍａｌｕｒｅｃｏｎｖｅｒｇｅｎｃｅ）。这时引入变异算子往往能产生很好的效果。一方面，变异算子可以使群体进化过程中丢失的等位基因信息得以恢复，以保持群体中的个体差异性，防止发生成熟前收敛：另一方面，当种群规模较大时，在交叉操作基础上引入适度的变异，也能够提高遗传算法的局部搜索效率。
在群体进化的整个过程中，交叉操作是主要的基因重组和群体更迭的手段，变异操作的作用是第二位的，变异算子仅仅充当背景性的角色（ｂａｃｋｇｒｏｕｎｄｒｏｌｅ）。
在很多组合优化问题中，往往存在着多个最优解或者最优解被环绕在大量的劣解之中，应用ＧＡ求解该类问题很容易形成模式欺骗问题，此时可以采用补算算子（ｃｏｍｐｌｅｍｅｎｔａｒｙｏｐｅｒａｔｏｒ）增加群体多样性或者克服模式欺骗性。
基于｛Ｏ，１｝字符集表示的二进制染色体位串ｓ＝ｑａ：…ａ．，补算算子具体操作形式如下：
Ｏ（ｃｏｍ，Ｓ）：口；＝１一ａ．，ｉ＝１，２，?一，三（２一１１）对于位串上每一位基因位，若等位基因为０，则变为ｌ，否则变为０，从而形成新的位串。例如：Ｓ＝１０１１１０１１，补算运算结果为：Ｊ’＝０１０００１００。
２．２．４群体设定
遗传算法与传统随机类搜索算法的最大区别之一，在于它的整个算法是在解的群体上进行的。证是这一特点使ＧＡ具有了搜索过程的并行性、全局性和鲁棒’陛，可见群体的设定对整个ＧＡ的运行性能具有基础性的决定作用。
根据模式定理，群体规模对遗传算法的性能影响很大。若群体规模为ｒｔ，则遗传算子可以从这Ｈ个个体中生成和检测Ｏ（ｎ３）个模式１”’，并在此基础上不断形成和优化建筑模块，直到找到问题的最优解。群体规模越大，群体中个体的多样性越高，算法陷入局部解的危险就越小。但是随着群体规模增大，计算量也显著增加。若群体规模太小，使遗传算法的搜索空间受到限制，则可能产生未成熟收敛的现象。
第17卷第3期 辽阳石油化工高等专科学校学报Vol.17No.3 2001年9月 Journal of Liaoyang Petrochemical College September2001 一种改进的遗传算法 王亮申 王文友 吴克勤 江远鹏 谢 荣 (辽阳石油化工高等专科学校机械系,辽阳111003) 摘 要 给出的适应值标定公式能够解决对个体选择压力和标定后适应值非负问题. 对多极值函数的遗传算法所提出的改进措施可以增加群体的多样性,避免算法“早熟”,过早 陷入局部最优. 关键词 遗传算法;适应值标定;早熟 中图分类号 O224 由美国密执安(Michrgan)大学的Holland教授等人在1975年创立的遗传算法(G enetic Algo2 rithms简称G A),是建立在达尔文(Darwin)的生物进化论和孟德尔(Mendel)的遗传学说基础上的算法.经过后人的不断改进使得遗传算法更加完善.由于遗传算法求解复杂优化问题的巨大潜力及其在各个领域(如布局优化问题、交通问题、图像处理与识别、结构设计、电力系统设计、可靠性计算等)的成功应用,这种算法越来越被人们所接受. 遗传算法是一种基于生物进化原理构想出来的搜索最优解的仿生算法,它模拟基因重组与进化的自然过程,把待解决问题的参数编成二进制码或十进制码(也可编成其它进制码)即基因(gene),若干基因组成一个染色体(个体),许多染色体进行类似于自然选择、配对交叉和变异运算,经过多次重复迭代(即世代遗传)直至得到最后的优化结果.习惯上,适应度值越大,表示解的质量越好.对于求解最小值问题可通过变换转为求解最大值问题.遗传算法是一种高度并行、随机、自适应搜索算法. 尽管遗传算法有许多优点,也有许多专家学者对遗传算法进行不断研究,但目前存在的问题依然很多.如(1)适应值标定方式多种多样,没有一个简洁、通用方法,不利于对遗传算法的使用; (2)遗传算法的“早熟”现象即很快收敛到局部最 收稿日期:2001-06-27优解而不是全局最优解是迄今为止最难处理的关键问题;(3)快要接近最优解时在最优解附近左右摆动,收敛较慢. 1 改进方法 1.1 适应值标定 初始种群中可能存在特殊个体的适应值超常(如很大).为了防止其统治整个群体并误导群体的发展方向而使算法收敛于局部最优解需限制其繁殖;在计算临近结束,遗传算法逐渐收敛,由于群体中个体适应值比较接近,继续优化选择困难,造成在最优解附近左右摇摆,此时应将个体适应值适当加以放大,以提高选择能力,这就是适应值的标定.文献[1]提出的标定方法有两个计算公式,不利于使用;文献[2]的标定方式虽然限制了适应值范围但将最大最小值颠倒.此外象幂律标定、对数标定等亦有应用.本文针对适应值标定问题提出以下计算公式. f’= 1 f max-f min+δ (f+|f min|) f′—为标定后的适应值;f—为原适应值;δ—为在(0,1)内的一个正实数,目的是防止分母为零和增加遗传算法的随机性;|f min|—是为了保证定标后的适应值不出现负值。
遗传算法基本原理及改进 编码方法： 1、二进制编码方法 2、格雷码编码方法 3、浮点数编码方法。个体长度等于决策变量长度 4、多参数级联编码。一般常见的优化问题中往往含有多个决策变量，对这种还有多个变量的个体进行编码的方法就成为多参数编码方法。多参数编码的一种最常用和最基本的方法是：将各个参数分别以某种方式进行编码，然后再将它们的编码按照一定顺序连接在一起就组成了标识全部参数的个体编码。 5、多参数交叉编码：思想是将各个参数中起主要作用的码位集中在一起，这样他们就不易于被遗传算子破坏掉。在进行多参数交叉编码时，可先对各个参数进行编码；然后去各个参数编码串的最高位连接在一起，以他们作为个体编码串前N位编码，同上依次排列之。
改进遗传算法的方法： （1）改进遗传算法的组成成分或实用技术，如选用优化控制参数、适合问题的编码技术等。 （2）采用动态自适应技术，在进化过程中调整算法控制参数和编码精度。 （3）采用混合遗传算法 （4）采用并行算法 （5）采用非标准的遗传操作算子 改进的遗传算法： （1）分层遗传算法 （2）CHC算法 （3）messy遗传算法； （4）自实用遗传算法（Adaptive Genetic Algorithm） （5）基于小生境技术的遗传算法（Niched Genetic Algorithm，简称NGA）。 （6）并行遗传算法（Parallel Genetic Algorithm） （7）混合遗传算法：遗传算法与最速下降法相结合的混合遗传算法；遗传算法与模拟退火算法相结合的混合遗传算法。 解决标准遗传算法早熟收敛和后期搜索迟钝的方案 （1）变异和交叉算子的改进和协调采用 将进化过程划分为渐进和突变两个不同阶段 采用动态变异 运用正交设计或均匀设计方法设计新的交叉和变异算子 （2）采用局部搜索算法解决局部搜索能力差的问题 （3）采用有条件的替代父代的方法，解决单一的群体更新方式难以兼顾多样性和收敛性的问题 （4）收敛速度慢的解决方法； 产生好的初始群体 利用小生境技术 使用移民技术 采用自适应算子 采用与局部搜索算法相结合的混合遗传算法 对算法的参数编码采用动态模糊控制 进行未成熟收敛判断
遗传算法的基本理论 一、起源： 早在20世纪50年代和60年代，就有少数人几个计算机科学家独立地进行了所谓的“人工进化系统”研究，其出发点是进化的思想可以发展成为许多工程问题的优化工具。早期的研究形成了遗传算法的雏形，如大多数系统都遵循“适者生存”的仿自然法则，有些系统采用了基于群体（population）的设计方案，并且加入了自然选择与变异操作，还有一些系统对生物染色体编码进行了抽象处理，应用二进制编码。由于缺乏一种通用的编码方案，人们只能依赖变异而非交叉来产生新的基因结构，早期的算法收敛甚微。20世纪60年代中期，美国Michigan大学的John Holland在A.S.Fraser和H.J.Bremermann等人工作的基础上提出了位串编码技术。这种编码既适用于变异操作，又适用于交叉（即杂交）操作。并且强调将交叉作为主要的遗传操作。随后，Holland将该算法用于自然和人工系统的自适应行为的研究中，并于1975年出版了其开创性著作“Adaption in Natural and Artificial System”。以后，Holland等人将该算法加以推广，应用到优化及机器学习等问题中，并正式定名为遗传算法。遗传算法的通用编码技术和简单有效的遗传操作作为其广泛、成功地应用奠定了基础。Holland早期有关遗传算法的许多概念一直沿用至今，可见Holland对遗传算法的贡献之大。他认为遗传算法本质上是适应算法，应用最多的是系统最优化的研究。 二、发展： 年份贡献者内容 1962Holland程序漫游元胞计算机自适应系统框架 1968Holland模式定理的建立 1971Hollstein具有交配和选择规则的二维函数优化 1972Bosworth、Foo、Zeigler提出具有复杂变异、类似于遗传算法的基因操作1972Frantz位置非线性和倒位操作研究 1973Holland遗传算法中试验的最优配置和双臂强盗问题 1973Martin类似遗传真法的概率算法理论 1975De Jong用于5个测试函数的研究基本遗传算法基准参数 1975Holland 出版了开创性著作《Adaptation in Natural and Artificial System》 1981Bethke应用Walsh函数分析模式 1981Brindle研究遗传算法中的选择和支配问题 1983Pettit、Swigger遗传算法应用于非稳定问题的粗略研究1983Wetzel用遗传算法解决旅行商问题(TSP) 1984Mauldin基本遗传算法小用启发知识维持遗传多样性1985Baker试验基于排序的选择方法 1985Booker建议采用部分匹配计分、分享操作和交配限制法1985Goldberg、Lingle TSP问题个采用部分匹配交叉 1985Grefenstette、Fitzpattrick对含噪声的函数进行测试 1985Schaffer多种群遗传算法解决多目标优化问题1986Goldberg最优种群大小估计 1986Grefenstette元级遗传算法控制的遗传算法 1987Baker选择中随机误差的减少方法 1987Goldberg复制和交叉时最小欺骗问题(MDP) 1987Goldberg、Richardson借助分享函数的小生境和物种归纳法
2016年第17期 科技创新科技创新与应用 遗传算法的应用研究 赵夫群 （咸阳师范学院，陕西咸阳712000） 1概述 遗传算法（Genetic Algorithms，GA）一词源于人们对自然进化系统所进行的计算机仿生模拟研究，是以达尔文的“进化论”和孟德尔的“遗传学原理”为基础的，是最早开发出来的模拟遗传系统的算法模型。遗传算法最早是由Fraser提出来的，后来Holland对其进行了推广，故认为遗传算法的奠基人是Holland。 随着遗传算法的不断完善和成熟，其应用范围也在不断扩大，应用领域非常广泛，主要包括工业控制、网络通讯、故障诊断、路径规划、最优控制等。近几年，出现了很多改进的遗传算法，改进方法主要包括：应用不同的交叉和变异算子；引入特殊算子；改进选择和复制方法等。但是，万变不离其宗，都是基于自然界生物进化，提出的这些改进方法。 2遗传算法的原理 遗传算法是从某一个初始种群开始，首先计算个体的适应度，然后通过选择、交叉、变异等基本操作，产生新一代的种群，重复这个过程，直到得到满足条件的种群或达到迭代次数后终止。通过这个过程，后代种群会更加适应环境，而末代种群中的最优个体，在经过解码之后，就可以作为问题的近似最优解了。 2.1遗传算法的四个组成部分 遗传算法主要由四个部分组成[1]：参数编码和初始群体、适应度函数、遗传操作和控制参数。编码方法中，最常用的是二进制编码，该方法操作简单、便于用模式定理分析。适应度函数是由目标函数变换而成的，主要用于评价个体适应环境的能力，是选择操作的依据。遗传操作主要包括了选择、交叉、变异等三种基本操作。控制参数主要有：串长Z，群体大小size，交叉概率Pc，变异概率Pm等。目前对遗传算法的研究主要集中在参数的调整中，很多文献建议的参数取值范围一般是：size取20~200之间，Pc取0.5~1.0之间，Pm取0~0.05之间。 2.2遗传算法的基本操作步骤 遗传算法的基本操作步骤为： （1）首先，对种群进行初始化；（2）对种群里的每个个体计算其适应度值；（3）根据（2）计算的适应度，按照规则，选择进入下一代的个体；（4）根据交叉概率Pc，进行交叉操作；（5）以Pm为概率，进行变异操作；（6）判断是否满足停止条件，若没有，则转第（2）步，否则进入（7）；（7）得到适应度值最优的染色体，并将其作为问题的满意解或最优解输出。 3遗传算法的应用 遗传算法的应用领域非常广泛，下面主要就遗传算法在优化问题、生产调度、自动控制、机器学习、图像处理、人工生命和数据挖掘等方面的应用进行介绍。 3.1优化问题 优化问题包括函数优化和组合优化两种。很多情况下，组合优化的搜索空间受问题规模的制约，因此很难寻找满意解。但是，遗传算法对于组合优化中的NP完全问题非常有效。朱莹等[2]提出了一种结合启发式算法和遗传算法的混合遗传算法来解决杂货船装载的优化问题中。潘欣等[3]在化工多目标优化问题中应用了并行遗传算法，实验结果表明该方法效果良好。王大东等[4]将遗传算法应用到了清运车辆路径的优化问题求解中，而且仿真结果表明算法可行有效。 3.2生产调度 在复杂生产调度方面，遗传算法也发挥了很大的作用。韦勇福等[5]将遗传算法应用到了车间生产调度系统的开发中，并建立了最小化完工时间目标模型，成功开发了车间生产调度系统模块，并用实例和仿真验证了该方法的可行性。张美凤等[6]将遗传算法和模拟退火算法相结合，提出了解决车间调度问题的混合遗传算法，并给出了一种编码方法以及建立了相应的解码规则。 3.3自动控制 在自动控制领域中，遗传算法主要用于求解的大多也是与优化相关的问题。其应用主要分为为两类，即离线设计分析和在线自适应调节。GA可为传统的综合设计方法提供优化参数。 3.4机器学习 目前，遗传算法已经在机器学习领域得到了较为广泛的应用。邢晓敏等[7]提出了将遗传算子与Michigan方法和基于Pitt法的两个机器学习方法相结合的机器学习方法。蒋培等[8]提出了一种基于共同进化遗传算法的机器学习方法，该方法克服了学习系统过分依赖于问题的背景知识的缺陷，使得学习者逐步探索新的知识。 3.5图像处理 图像处理是一个重要的研究领域。在图像处理过程中产生的误差会影响图像的效果，因此我们要尽可能地减小误差。目前，遗传算法已经在图像增强、图像恢复、图像重建、图像分形压缩、图像分割、图像匹配等方面应用广泛，详见参考文献[9]。 4结束语 遗传算法作为一种模拟自然演化的学习过程，原理简单，应用广泛，已经在许多领域解决了很多问题。但是，它在数学基础方面相对不够完善，还有待进一步研究和探讨。目前，针对遗传算法的众多缺点，也相继出现了许多改进的算法，并取得了一定的成果。可以预期，未来伴随着生物技术和计算机技术的进一步发展，遗传算法会在操作技术等方面更加有效，其发展前景一片光明。 参考文献 [1]周明，孙树栋.遗传算法原理及应用[M].国防工业出版社，1999，6. [2]朱莹，向先波，杨运桃.基于混合遗传算法的杂货船装载优化问题[J].中国船舰研究，2015：10（6）：126-132. [3]潘欣，等.种群分布式并行遗传算法解化工多目标优化问题[J].化工进展，2015：34（5）：1236-1240. [4]王大东，刘竞遥，王洪军.遗传算法求解清运车辆路径优化问题[J].吉林师范大学学报（自然科学版），2015（3）：132-134. [5]韦勇福，曾盛绰.基于遗传算法的车间生产调度系统研究[J].装备制造技术，2014（11）：205-207. [6]黄巍，张美凤.基于混合遗传算法的车间生产调度问题研究[J].计算机仿真，2009，26（10）：307-310. [7]邢晓敏.基于遗传算法的机器学习方法赋值理论研究[J].软件导刊[J].2009，8（11）：80-81. [8]蒋培.基于共同进化遗传算法的机器学习[J].湖南师范大学自然科学学报，2004，27（3）：33-38. [9]田莹，苑玮琦.遗传算法在图像处理中的应用[J].中国图象图形学报，2007，12（3）：389-396. [10]周剑利，马壮，陈贵清.基于遗传算法的人工生命演示系统的研究与实现[J].制造业自动化，2009，31（9）：38-40. [11]刘晓莉，戎海武.基于遗传算法与神经网络混合算法的数据挖掘技术综述[J].软件导刊，2013，12（12）：129-130. 作者简介：赵夫群（1982，8-），女，汉族，籍贯：山东临沂，咸阳师范学院讲师，西北大学在读博士，工作单位：咸阳师范学院教育科学学院，研究方向：三维模型安全技术。 摘要：遗传算法是一种非常重要的搜索算法，特别是在解决优化问题上，效果非常好。文章首先介绍了遗传算法的四个组成部分，以及算法的基本操作步骤，接着探讨了遗传算法的几个主要应用领域，包括优化、生产调度、机器学习、图像处理、人工生命和数据挖掘等。目前遗传算法以及在很多方面的应用中取得了较大的成功，但是它在数学基础方面相对还不够完善，因而需要进一步研究和完善。 关键词：遗传算法；优化问题；数据挖掘 67 --
遗传算法及其在TSP问题中的应用 摘要：本文首先介绍了遗传算法的基本理论与方法，从应用的角度对遗传算法做了认真的分析和研究，总结了用遗传算法提出求解组合优化问题中的典型问题——TSP问题的最优近似解的算法。其次，本文在深入分析和研究了遗传算法基本理论与方法的基础上，针对旅行商问题的具体问题，设计了基于TSP的遗传算法的选择、交叉和变异算子等遗传算子，提出了求解旅行商问题的一种遗传算法，并用Matlab语言编程实现其算法，最后绘出算法的仿真结果，并对不同结果作出相应的分析。然后，本文还针对遗传算法求解TSP时存在的一些问题对该算法进行了适当的改进。如针对初始群体、遗传算子作出适当改进，或者将遗传算法与其他方法相结合，以及在编程过程中对算法流程的改进。本人在用计算机模拟遗传算法求解TSP问题时，首先分析了用Matlab语言设计遗传算法程序的优越性，接着以遗传算法求解TSP问题为例，深入讨论了各个遗传算子的程序实现，并通过分析实验数据，得到各个遗传算子在搜索寻优过程中所起的作用，最后指出了用Matlab语言编程同用其它高级程序语言编程的差异所在，以及运用Matlab编写遗传算法程序的一些注意事项。最后，本文提出将遗传算法与其它算法相结合来求解一般问题的想法；并将遗传算法的应用范围扩展，提出可以运用遗传算法求解由TSP衍生出的各类TSP扩展问题，如求解配送/收集旅行商问题的遗传算法（TSPD）、遗传算法在货物配送问题中的应用（ST－TSP）、多旅行商问题（MTSP）等。 引言：优化问题可以自然地分为两类：一类是连续变量的优化问题；另一类是离散变量的优化问题，即所谓组合优化问题。对于连续变量的优化问题，一般是求一组实数或一个函数；而在组合优化问题中，一般是从一个无限集或有限的几个无限集中寻找一个对象——它可以是一个整数，一个集合，一个排列或者一个图，也即是从可行解中求出最优解的问题。TSP问题就是其中的典型例子，就本质上而言它可抽象为数学上的组合优化，它描述的是旅行商经N个城市的最短路径问题，因而对TSP问题的求解是数学上，同时也是优化问题中普遍关注的。旅行商问题（Traveling Salesman Problem，简称TSP）也称为货担郎问题，是一个较古的问题，最早可以追溯到1759年Euler提出的骑士旅行问题[9]。旅行商问题可以解释为，一位推销员从自己所在城市出发，必须邀访所有城市且每个城市只能访问一次之后又返回到原来的城市，求使其旅行费用最小（和旅行距离最短）的路径。 TSP是一个典型的组合优化问题，并且是一个NP难题，所以一般很难精确地求出其最优解，因而寻找出其有效的近似求解算法就具有重要的理论意义。另一方面，很多实际应用问题，如公安执勤人员的最优巡回路线、流水作业生产线的顺序问题、车辆调度问题、网络问题、切割问题以至机组人员的轮班安排、教师任课班级负荷分配等问题，经过简化处理后，都可建模为TSP问题，因而对旅行商问题求解方法的研究也具有重要的应用价值。再者，在各种遗传算法应用实例中，其个体编码方法大多都是采用二进制编码方法或浮点数编码方法，而TSP问题是一种典型的需要使用符号编码方法的实际问题，所以，研究求解TSP问题的遗传算法，对促进遗传算法本身的发展也具有重要意义。在过去的20年里，在求解旅行商问题的最优解方面取得了极大的进展。尽管有这些成就，但旅行商问题还远未解决，问题的许多方面还要研究，很多问题还在期待满意的回答。 另外，遗传算法就其本质来说，主要是解决复杂问题的一种鲁棒性强的启发式随机
改进的混沌遗传算法 李辉 (计算机学院2004级研究生 04720746) 摘要：混沌遗传算法(chaos genetic algorithm, CGA)是基于混沌优化的遗传操作,将使子代个体均匀地分布于定义空间,从而可避免早熟,以较大的概率实现全局最优搜索.与传统的遗传算法相比较, CGA 的在线和离线性能都有较大的改进。而遗传算法作为一种智能算法，是解决非线性复杂优化问题的有利工具，但它在搜索过程中易陷入局部最优，收敛速度慢的缺陷又限制了它的寻优效能。混沌遗传算法具有两者的优点，大大提高了优化的效率。 关键词：遗传算法混沌混沌优化 Abstract：Chaos genetic algorithm (CGA)is a genetic operation,which based on chaos optimization,makes the individuals of subgeneration distribute uniformly in the defined space and avoids the premature of subgeneration.To compare the performances of the CGA with those of the traditional GA,The results demonstrated that the CGA’s on-line and off–line performance was all superior to that of the traditional GA.As an inteliengence algorithm,GA is a effectual toos to resolve the problem of the liner-optimization,but the slower convergence and the premature restrict its efficiency.And CGA which has the two strongpoint has promoted is efficiency in optimization. Key words: genetic algorithm chaos chaos optimization 1 引言： 遗传算法(GA)最早由美国Michigan大学的John Holland教授提出，通过模拟自然界中的生命进化过程，有指导地而不是盲目地进行随机搜索，适用于在人工系统中解决复杂特定目标的非线性反演问题。De Jong首先将遗传算法应用于函数优化问题的研究，他的工作表明在求解数学规划时，GA是一种有效的方法。但对于大型复杂系统，尤其是非线性系统优化问题的求解，GA仍有许多缺陷，如无法保证收敛到全局最优解，群体中最好的染色体的丢失，进化过程的过早收敛等。 混沌是自然界中一种较为普遍的现象，具有“随机性”、“遍历性”及“规律性”等特点，在一定范围内能按其自身的“规律”不重复地遍历所有状态的。在搜索空间小时混沌优化方法效果显著，但搜索空间大时几乎无能为力。 混沌遗传算法(CGA)的基本思想是将混沌状态引入到优化变量中，并把混沌运动的遍历范围“放大”到优化变量的取值范围，然后把得到的混沌变量进行编码，进行遗传算子操作。再给混沌变量附加—混沌小扰动，通过一代代地不断进化，最后收敛到一个最适合环境的个体上，求得问题的最优解。 2 传统遗传算法 传统遗传算法： population old_pop,new_pop;/*current and next population*/ int pop_size,generation; float p_cross,p_mutation; /*prob. Of crossover & mutation*/ 1 old_pop=initial random population={ind1,ind2,….indpopsize} 2 while(generation 遗传算法论文：浅谈遗传算法的研究与改进【摘要】遗传算法是模拟自然界生物进化机制的概率性搜索算法，可以处理传统搜索方法难以解决的非线性问题。但是经典遗传算法存在局部收敛、收敛速度慢等缺点，这使得经典遗传算法有时很难找到全局最优解。本文针对经典遗传算法中所存在的缺点，采用阶段式的适应度函数、基于竞争机制的交叉方式和仿粒子群变异操作，使遗传算法的收敛速率、全局收敛概率都得到了较大的提高。 【关键词】遗传算法适应度交叉操作仿粒子群变异 一遗传算法 遗传算法（genetic algorithm，简称ga）是holland 在研究自然遗传现象与人工系统的自适应行为时，模拟生物进化现象，并采用自然进化机制来表现复杂现象的一种全局群体搜索算法。遗传算法的基本思想起源于darwin进化论和mendel的遗传学说。作为一类智能计算工具和学习算法，由于其实现简单、对目标函数要求不高等特性，遗传算法已广泛应用于如人工智能、组合优化等研究领域。 1．遗传算法的优越性 遗传算法（genetic algorithm）利用某种编码技术作用在称为染色体的二进制串上，模拟由这些串组成的个体的进化过程。通过有组织的、随机的信息交换来重新结合那些 适应性好的串，在每一代中，利用上一代串结构中适应性好的位和段来形成一个新的串的群体，同时在串结构中尝试用新的位和段来代替原来的部分以形成新的个体，以增加种群的多样性。遗传算法的最大优点是能够通过群体间的相互作用，保存已经搜索到的信息，这是基于单次搜索过程的优化方法所无法比拟的。但是，遗传算法也存在着计算速度较慢，并且容易陷入局部最优解的问题中。 遗传算法的优越性归功于它与传统搜索方法不同的特 定结构。 第一，遗传算法的操作对象是编码，对问题的限制极少，对函数的一些约束条件如连续性、可导性等不做要求，减少了要解决问题的复杂性。 第二，遗传算法同时搜索解空间内的许多点，因而可以有效地防止搜索过程中收敛到局部最优解，并获得全局最优解，与其他单点搜索的方法相比，在计算时间上也有较大的优势。 第三，遗传算法使用遗传操作时是按概率在解空间进行搜索，因而既不同于随机搜索，也不同于枚举法那样盲目地举例，而是一种有目标、有方向的启发式搜索。 2．遗传算法的基本步骤 遗传算法的实现中包括复制、交叉、变异三个算子，需 第七章 遗传算法应用举例 遗传算法提供了一种求解非线性、多模型、多目标等复杂系统优化问题的通用框架，它不依赖于问题具体的领域。随着对遗传算法技术的不断研究，人们对遗传算法的实际应用越来越重视，它已经广泛地应用于函数优化、组合优化、自动控制、机器人学、图象处理、人工生命、遗传编码、机器学习等科技领域。遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等多方面的应用取得了成功。本章通过一些例子，介绍如何利用第五章提供的遗传算法通用函数，编写MATLAB 程序，解决实际问题。 7.1 简单一元函数优化实例 利用遗传算法计算下面函数的最大值： ()sin(10) 2.0[1,2]f x x x x π=?+∈-， 选择二进制编码，种群中个体数目为40，每个种群的长度为20，使用代沟为0.9，最大遗传代数为25。 下面为一元函数优化问题的MA TLAB 代码。 figure(1); fplot ('variable.*sin(10*pi*variable)+2.0',[-1,2]); %画出函数曲线 % 定义遗传算法参数 NIND= 40; % 个体数目(Number of individuals) MAXGEN = 25; % 最大遗传代数(Maximum number of generations) PRECI = 20; % 变量的二进制位数(Precision of variables) GGAP = 0.9; % 代沟(Generation gap) trace=zeros (2, MAXGEN); % 寻优结果的初始值 FieldD = [20;-1;2;1;0;1;1]; % 区域描述器(Build field descriptor) Chrom = crtbp(NIND, PRECI); % 初始种群 gen = 0; % 代计数器 variable=bs2rv(Chrom,FieldD); % 计算初始种群的十进制转换 ObjV = variable.*sin (10*pi*variable)+2.0; % 计算目标函数值 while gen < MAXGEN, FitnV = ranking (-ObjV); % 分配适应度值(Assign fitness values) SelCh = select ('sus', Chrom, FitnV , GGAP); % 选择 SelCh = recombin ('xovsp',SelCh,0.7); % 重组 SelCh = mut(SelCh); % 变异 variable=bs2rv(SelCh,FieldD); % 子代个体的十进制转换 ObjVSel =variable.*sin(10*pi*variable)+2.0; % 计算子代的目标函数值 [Chrom ObjV]=reins(Chrom,SelCh,1,1,ObjV ,ObjVSel); % 重插入子代的新种群 gen = gen+1; % 代计数器增加 % 输出最优解及其序号，并在目标函数图象中标出，Y 为最优解，I 为种群的序号 [Y,I]=max(ObjV),hold on; plot (variable (I),Y , 'bo'); trace (1,gen)=max (ObjV); %遗传算法性能跟踪 关于遗传算法的文献综述 班级：13级机械(4)班学号：913101140439 姓名：元志斌 关键词：遗传算法，编码，搜索，优化，交叉，遗传 摘要：遗传算法是一种基于生物进化自然选择和群体遗传机理的，适合于复杂系统优化的自适应概率优化技术，近年来，因为遗传算法求解复杂优化问题的巨大潜力和在工业工程领域的成功应用，这种算法受到了国内外学者的广泛关注，本文介绍了遗传算法研究现状和发展的前景，概述了它的理论和技术，并对遗传算法的发展情况发表了自己的看法。Abstract:Genetic algorithm is a kind of natural selection and based on biological evolution of gen etic mechanism, group suitable for complex system optimization adaptive probability optimizatio n technique, in recent years, because genetic algorithm for solving complex optimization problem in the huge potential and the successful application of industrial engineering, this algorithm was wide attention of scholars at home and abroad, this paper introduces the current research status and development of genetic algorithm, summarizes the prospect of its theory and technology of genetic algorithm and the development of published opinions of his own. 1.引言 遗传算法Genetic Algorithm（GA）是由美国密歇根大学的John H. Holland教授及其学生于20世纪60年代末到70年代初提出的。它是以达尔文的自然进化论“适者生存、优胜劣汰”和孟德尔遗传变异理论为基础，模拟生物进化过程。它具有大范围快速全局搜索能力，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求的最优解。正是遗传算法的诸多特点，使得它在求解组合优化、机器学习、并行处理等问题上得到了广泛的应用。普通遗传算法是通过模拟染色体群的选择、交叉和变异等操作，不断迭代，最终收敛到高适应度值的染色体，从而求得问题的最优解。但是随着问题规模的扩大，组合优化问题的搜索空间急剧扩大，普通遗传算法的收敛速度慢、易陷入局部最优的缺点就暴露了。而佳点集遗传算法正是通过佳点集的方法改进交叉算子，加快算法收敛到全局最优解的速度，降低发生早熟的概率，提高整个算法的计算效率。 2.国内外相关研究现状 遗传算法的鼻祖是美国Michigan大学的Holland教授及其学生。他们受到生物模拟技术的启发，创造了一种基于生物遗传和进化机制的适合于复杂系统优化的自适应概率优化技术 遗传算法的应用研究 遗传算法是一种非常重要的搜索算法，特别是在解决优化问题上，效果非常好。文章首先介绍了遗传算法的四个组成部分，以及算法的基本操作步骤，接着探讨了遗传算法的几个主要应用领域，包括优化、生产调度、机器学习、图像处理、人工生命和数据挖掘等。目前遗传算法以及在很多方面的应用中取得了较大的成功，但是它在数学基础方面相对还不够完善，因而需要进一步研究和完善。 标签：遗传算法；优化问题；数据挖掘 1 概述 遗传算法（Genetic Algorithms，GA）一词源于人们对自然进化系统所进行的计算机仿生模拟研究，是以达尔文的“进化论”和孟德尔的“遗传学原理”为基础的，是最早开发出来的模拟遗传系统的算法模型。遗传算法最早是由Fraser提出来的，后来Holland对其进行了推广，故认为遗传算法的奠基人是Holland。 随着遗传算法的不断完善和成熟，其应用范围也在不断扩大，应用领域非常广泛，主要包括工业控制、网络通讯、故障诊断、路径规划、最优控制等。近几年，出现了很多改进的遗传算法，改进方法主要包括：应用不同的交叉和变异算子；引入特殊算子；改进选择和复制方法等。但是，万变不离其宗，都是基于自然界生物进化，提出的这些改进方法。 2 遗传算法的原理 遗传算法是从某一个初始种群开始，首先计算个体的适应度，然后通过选择、交叉、变异等基本操作，产生新一代的种群，重复这个过程，直到得到满足条件的种群或达到迭代次数后终止。通过这个过程，后代种群会更加适应环境，而末代种群中的最优个体，在经过解码之后，就可以作为问题的近似最优解了。 2.1 遗传算法的四个组成部分 遗传算法主要由四个部分组成[1]：参数编码和初始群体、适应度函数、遗传操作和控制参数。编码方法中，最常用的是二进制编码，该方法操作简单、便于用模式定理分析。适应度函数是由目标函数变换而成的，主要用于评价个体适应环境的能力，是选择操作的依据。遗传操作主要包括了选择、交叉、变异等三种基本操作。控制参数主要有：串长Z，群体大小size，交叉概率Pc，变异概率Pm等。目前对遗传算法的研究主要集中在参数的调整中，很多文献建议的参数取值范围一般是：size取20～200之间，Pc取0.5～1.0之间，Pm取0～0.05之间。 2.2 遗传算法的基本操作步骤 课程：新技术讲座 题目：遗传算法在图像处理中的应用姓名： 学号： 目录 摘要 (2) 1.引言 (3) 2.遗传算法的基本原理和基本性质 (3) 3.遗传算法在图像处理中的应用 (5) 3.1在图像增强中的应用 (5) 3.2在图像恢复中的应用 (6) 3.3在图像分割中的应用 (7) 3.4在图像压缩中的应用 (8) 3.5在图像匹配中的应用 (9) 4.遗传算法在图像处理中的问题及发展方向 (10) 参考文献 (10) 遗传算法在图像处理中的应用 摘要 遗传算法是一种模拟生命进化机制，基于生物自然选择与遗传机理的随机搜索与优化方法。近几年来，遗传算法广泛应用在生物信息学、系统发生学、计算科学、工程学、经济学、化学、制造、数学、物理、药物测量学和其他领域之中，这种算法得到快速发展，尤其是在计算机科学人工智能领域中。本文将在系统并且深入的介绍遗传算法基本理论的基础上，重点综述遗传算法在数字图像处理中的主要应用，深入研究目前遗传算法在图像处理领域中存在的问题，并对这些问题作出了一些个人的见解，阐述了遗传算法在图像处理应用的发展方向。 关键词：遗传算法，数字图像处理 Abstract Genetic Algorithm is a simulation of the life evolution mechanism, random search and optimization method which is based on the natural selection and genetic mechanism.In recent years,due to the enormous potential of solving complex optimization problems and the successful applications in the industrial field,the Genetic Algorithm developed rapidly,Especially in the field of artificial intelligence in computer science.This article not only describes the basic theoretical foundation of genetic algorithms,but also focus on Genetic Algorithm in digital image processing.Moreover,it studies the problems of the Genetic Algorithm in the field of image processing and the direction of development in the future，Moreover,the author elaborates the personal opinion in the end. keyword ：Genetic Algorithm,Digital image processing遗传算法论文：浅谈遗传算法的研究与改进
第七章 遗传算法应用举例
遗传算法及其发展状况研究
遗传算法的应用研究
遗传算法在图像处理中的应用
相关主题
文本预览