遗传算法基本理论实例

《遗传算法基本理论实例》由会员分享，可在线阅读，更多相关《遗传算法基本理论实例（28页珍藏版）》请在装配图网上搜索。

1、目录一、遗产算法的由来 . . 2二、遗传算法的国内外研究现状3三、遗传算法的特点 . . 5四、遗传算法的流程 . . 7五、遗传算法实例 12六、遗传算法编程 17七、总结 . 错误!未定义书签附录一：运行程序 19遗传算法基本理论与实例一、遗产算法的由来遗传算法（Gene tic Algori thm，简称GA）起源于对生物系统所进行 的计算机模拟研究。 20世纪40年代以来，科学家不断努力从生物学中寻求 用于计算科学和人工系统的新思想、新方法。很多学者对关于从生物进化和 遗传的激励中开发出适合于现实世界复杂适应系统研究的计算技术生物 进化系统的计算模型，以及模拟进 化过程的算法进行了长

2、期的开拓 性的探索和研究。John H.Holland教授及其学生首先提出的遗传算法就 是一个重要的发展方向。遗传算法借鉴了达尔文的进化论和孟德尔、摩根的遗传学说。按照达尔 文的 进化论，地球上的每一物种从诞生开始就进入了漫长的进化历程。生物 种群从低级、简单的类型逐渐发展成为高级复杂的类型。各种生物要生存下 去及必须进行生存斗争，包括同一种群内部的斗争、不同种群之间的斗 争， 以及生物与自然界无机环境之间的斗争。具有较强生存能力的生物个 体容易存活下来，并有较多的机会产生后代；具有较低生存能力的个体则 被淘汰，或者产生后代的机会越来越少。，直至消亡。达尔文把这一过程和 现象叫做“自然选择，适

3、者生存” 。按照孟德尔和摩根的遗传学理论，遗 传物质是作为一种指令密码封装在每个细胞中，并 以基因的形式排列在染色 体上，每个基因有特殊的位置并控制生物的某些特性。不同的基因组合产生 的个体对环境的适应性不一样，通过基因杂交和突变可以产生对环境适应性 强的后代。经过优胜劣汰的自然选择，适应度值高的基因结构就得以保存 下来，从而逐渐形成了经典的遗传学染色体理论，揭示了遗传和变异的基 本规律。遗传算法由美国的John H.Holland教授1975年首先提出，其主要特 点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内 在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获

4、 取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗 传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处 理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。二、遗传算法的国内外研究现状遗传算法的鼻祖是美国Michigan大学的Holland教授及其学生。他们受到 生物模拟技术的启发，创造了一种基于生物遗传和进化机制的适合于复 杂系统优化的自适应概率优化技术一一遗传算法。1967年，Holland的 学生 Bagley 在其博士论文中首次提出了“遗传算法”一词，他发展了复 制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用双倍体的编码 方法。Ho

5、lland教授用遗传算 法的思想对自然和人工自适应系统进行了研 究，提出了遗传算法的基本理论模式定理(Schema Theorem)并于1957 年出版了第一本系统论述遗传算法和人工自适应系统的专著 Adaptation in Natural and Artificial Systems。20世纪80年代，Holland教授实现了第一个基于遗传算法的机器学习系统， 开创了遗传算法的机器学习的新概念。1975年，De Jong基于遗传算法 的思想在计算机上进行了大量的纯数值函数优化计算实验，建立了遗传算法 的工作框架， 得到 了一些重要且具有指导意义的结论。 1989 年，Goldberg 出版

6、了 GeneticAlgorithm in Search ，Optimization and Machine Learning 一书， 系统地总 结了遗传算法的主要研究成果，全面完整的论述了遗传算法的基本 原理及其应 用。 1991年， David 出版了 Handbook of Genetic Algorithms 一书，介绍了 遗传算法在科学计算、工程技术和社会经济中 的大量实例。1992年，Koza将遗 传算法应用于计算机程序的优化设计及 自动生成，提出了遗传编程（Gene tic Programming，简称GP）的概念。在 控制系统的离线设计方面遗传算法被众多的使用者证明是有效的策略

7、。例 如， Krishnakumar 和 Goldberg 以及 Bramlette 和 Gusin 已证明使用遗 传优化方法在太空应用中导出优异的控制器结构比使用传 统方法如LQR和 Powell （鲍威尔）的增音机设计所用的时间要少（功能评估） 。 Porter 和Mohamed展示了使用本质结构分派任务的多变量飞行控制系统的遗传 设计 方案。与此同时，另一些人证明了遗传算法如何在控制器结构的选择中使用。从遗传算法的整个发展过程来看，20世纪 70年代是兴起阶段， 20世 纪 80 年代是发展阶段，20世纪 90 年代是高潮阶段。遗传算法作为一种实 用、高效、 鲁棒性强的优化技术，发展极为

8、迅速，已引起国内外学者的高度 重视。近些年来，国内外很多学者在遗传算法的编码表示、适应度函数、 遗传 算子、 参数选择、收敛性分析、欺骗问题和并行遗传算法上做出了大量的研 究和改进。 还有很多学者将遗传算法和其他只能算法结合，进一步提高局部 搜索能力。 在遗 传算法的应用上也有很多改进。由于遗传算法具有全局并 行搜索、 简单通用、 鲁 棒性强等优点，使得遗传算法广泛地应用于计算机 科学、自动控制、人工智能、工程设计、制造业、生物工程和社会科学等领 域。针对遗传算法的一些问题，还有一些问题需要进一步的探究，将大大促 进遗传算法理论和应用的发展，遗传算法必将在智能计算领域中展现出更加 光明的前景、

9、遗传算法的特点遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法。 它与 传统的算法不同，大多数古典的优化算法是基于一个单一的度量函数 （评估函数） 的梯度和较高次统计， 以产生一个确定性的试验解序列； 遗 传算法不依赖梯度信 息，而是通过模拟自然进化进程来搜索最优解， 它利用 某种编码技术， 作用于称 为染色体的数字串， 模拟由这些串组成的群体的 进化过程。 遗传算法通过有组织 的、随机的信息交换来重新组合那些适应性 好的串，生成新的串的群体。遗传算法有以下优点：（1）对可行解表示的广泛性。遗传算法的处理对象不是参数本身，而是 针 对那些通过参数集进行编码的基因个体， 此编码操作使

10、得遗传算法可以直 接对结 构对象进行操作。所谓结构对象，泛指集合、序列、矩阵、树、链、 表等各种一 维或二维甚至多维结构形式的对象。这一特点使得遗传算法具有 广泛的应用领 域。比如通过对连接矩阵的操作， 遗传算法可用来对神经网络 或自动机的结构或 参数加以优化； 通过对集合的操作， 遗传算法可实现对 规则集合和知识库的精炼 而达到高质量的机器学习目的； 通过对树结构的操 作， 用遗传算法可得到用于分 类的最佳决策树； 通过对任务序列的操作， 遗传算法可用于任务规划， 而通过对 操作序列的处理，可自动构造顺序控制 系统。（2）群体搜索特性。许多传统的搜索方法都是单点搜索，这种点对点的 搜 索方法

11、，对于多峰分布的搜索空间常常会陷于局部的某个单峰的极值点。相反， 遗传算法采用的是同时处理群体中多个个体的方法， 即同时对搜索空 间中的多个 解进行评估。 这一特点使遗传算法具有较好的全局搜索性能， 也使得算法本身易 于并行化3）不需要辅助信息。 遗传算法仅用适应度函数来的数值来评估基因个 体，并在此基础上尽心遗传操作。 更重要的是， 遗传算法的适应度函数不仅不受 连续 可微的约束， 而且其定义域可以任意设定。 对适应度函数的唯一要求 是， 编码必 须与可行解空间对应， 不能有死码。 由于限制条件的缩小， 使得遗传算法的应用 范围大大扩展。（4）内在启发式随机搜索特性。遗传算法不是采用确定性规

12、则，而是采 用 概率的变迁规则来指导它的搜索方向。 概率不仅仅是作为一种工具来引导 其搜索 过程朝着搜索空间的更优化的解区域移动的。虽然看起来它是一种盲 目搜索方 法，实际上它有明确的搜索方向，具有内在的并行搜索机制。（5）遗传算法在搜索过程中不容易陷入局部最优，即时在所定义的适应 度 函数是不连续的、 非规则的或有噪声的情况下， 也能以很大的概率找到 全局最优 解。（6）遗传算法采用自然进化机制来表现复杂的现象，能够快速可靠地解 决 求解非常困难的问题。（7）遗传算法具有固有的并行性和并行计算的能力。（8）遗传算法具有可扩展性，易于同别的技术混合使用。 遗传算法作为 一种优化算法，也有它自身

13、的局限性：（1）编码不规范及编码存在表示的不准确性。（2）单一的遗传算法编码不能全面地将优化问题的约束表示出来。考虑 约 束的一个方法就是对不可行解采用阈值，这样，计算的时间必然增加。（3）遗传算法通常的效率比其他传统的优化方法低。（4）遗传算法容易出现过早收敛。（5）遗传算法对算法的精度、可信度、计算复杂性等方面，还没有有效 的 定量分析方法。遗传算法的基本内容如下：个体和种群。个体就是模拟生物个体而对问 题中的对象 （一般就是问题的解） 的一种称呼，一个个体也就是搜索空间中 的一个点。种群 （population） 就是模拟生物种群而由若干个体组成的群 体，它一般是整个搜索空间的一个很小的

14、子集。适应度与适应度函数。适应度（fitness）就是借鉴生物个体对环境的适 应程 度, 而对问题中的个体对象所设计的表征其优劣的一种测度。适应度函 数 （ fitness function ）就是问题中的全体个体与其适应度之间的一个对应 关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函 数。染色体与基因。染色体（chromosome）就是问题中个体的某种字符串形 式的编码表示。字符串中的字符也就称为基因（gene）。例如个体上9,染色 体的表示形式是1001，0 和1 是染色体上的基因。遗传操作。也称为遗传算子,就是关于染色体的运算。遗传算法中有 三种遗传操作：选择- 复制,

15、交叉和变异。四、遗传算法的流程遗传算法在整个进化过程中的遗传操作是随机的,但它所呈现出的特性 并不 是完全搜索，它能有效地利用历史信息来推测下一代期望性能有所提高 的寻优点 集。这样一代代的不断进化， 最后收敛到一个最适应环境的个体 上， 求得问题的 最优解。遗传算法所涉及的五大要素是：参数编码、初始种 群的设定、适应度函 数的设计、遗传操作的设计和控制参数的设定。流程如 图 1 所示*交义选择复制图1遗传算法基木流稈计算适应度变异牛成新一代种群简单遗传算法的运行过程为一个典型的迭代过程， 其必须完成的工作内 容和 基本步骤如下：1）选择编码策略，把参数集合 X 和域转换为位串结构空间 S。2

16、）定义适应度函数 。3）确定遗传策略，包括选择群体大小n选择、交叉、变异方法，以及 确定交叉概率、变异概率等遗传参数。4）随机初始化生成种群P。5）计算群体中个体位串解码后的适应度值。6）按照遗传策略，运用选择、交叉和变异算子作用与群体，形成下一代群 体。7）判断群体性能是否满足某一目标，或者已完成预定迭代次数，不满足 则 返回步骤6） ，或者修改遗传策略再返回步骤6） 。下面对基本步骤进行分解，进一步详细介绍流程中一些细节。编码表示。在许多问题求解中，编码是遗传算法中首要解决的问题， 对算法的性能有很重要的影响。 Holland 提出的二进制编码是遗传算法中 最常用的一种编码方法，它采用最小

17、字符编码原则，编/ 解码操作简单易 行，利于交叉、变异操作的实现，也可以采用模式定理对算法进行理论分 析。 但二进制编码用于多维、高精度数值问题优化时，不能很好地克服连 续函数离散化时的映射误差；不能直接反映问题的固有结构，精度不高，并 且个体长度大、占用内存多。针对二进制编码存在的不足，人们提出了多种 改进方法，比较典型的有以下几种：（1）格雷码编码。为了克服二进制编码在连续函数离散化时存在的不 足， 人们提出了用格雷码进行编码的方法，它是二进制编码的变形。格雷 码不仅具有二进制编码的一些优点，而且能够提高遗传算法的局部搜索能 力。假设有一个二进制编码为X xmxm1x2X,其对应的格雷码为

18、Y ymym 1y2y1，贝9ymx myixi 1 x ii m 1, m 2, ,1（2）实数编码。该方法适合于遗传算法中表示范围较大的数，使遗传算 法 更接近问题空间，避免了编码和解码的过程。它便于较大空间的遗传搜 索， 提高了遗传算法的精度要求；便于设计专门问题的遗传算子；便于算 法与经典优化方法的混合作用，改善了遗传算法的计算复杂性，提高了运算 效率。（3）十进制编码。该方法利用十进制编码控制参数，缓解了“组合爆炸” 和遗传算法的早熟收敛问题（4）非数值编码。染色体编码串中的基因值取一个仅有代码含义而无数 值 含义的符号集，这些符号可以是数字也可以是字符。非数值编码的优点 是在遗传算

19、法中可以利用所求问题的专门知识及相关算法。对于非数值编 码， 问题的解和染色体的编码要注意染色体的可行性、染色体的合法性和映 射的惟一性。适应度函数。在遗传算法中，适应度是描述个体性能的主要指标，根据 适应 度的大小对个体进行优胜劣汰。对于求解有约束的优化问题时，一般 采用罚函数方法将目标函数和约束条件建立成一个无约束的优化目标函数； 然后再将目标函数作适当处理，建立适合遗传算法的适应度函数。将目标 函数转换成适应度函数一般应遵循两个原则：适应度必须非负；优化过程 中目标函数的变化方向应与群体进化过程中适应度函数变化方向一致。在使 用遗传算法求解具体问题时，适应度函数的选择对算法的收敛性以及收

20、敛速 度的影响较大，针对不同的问题需根据经验或算法来确定相应的参数。遗传算子。 在遗传算法中通过一系列算子来决定后代， 算子对当前群体中选 定的成员进行重组和变异。（1）选择算子 选择操作通过适应度选择优质个体而抛弃劣质个体，体现 了“适者生存”的原理。常见的选择操作主要有以下几种：a）轮盘赌选择。选择某假设的概率是通 过这个假设的适应度与当前群体中其他成员的适应度的比值而得到。 此方 法是基 于概率选择的， 存在统计误差， 因此可以结合最优保存策略以保证 当前适应度最 优的个体能够进化到下一代而不被遗传操作的随机性破坏，保证算法的收敛性。b）排序选择。对个体适应度取正值或负值以及个体适应度之

21、间的数值差异程度无特殊要求， 对群体中的所有个体按其适应度大小进行排序， 根据排序来分 配各个体被选中的概率。c）最优个体保存。父代群体中的最优个体直接进 入子代群 体中。该方法可保证在遗传过程中所得到的个体不会被交叉和变异 操作所破坏， 它是遗传算法收敛性的一个重要保证条件； 它也容易使得局部 最优个体不易被淘汰，从而使算法的全局搜索能力变强。d）随机联赛选 择。每次选取 N 个个体中 适应度最高的个体遗传到下一代群体中。具体操作 如下：从群体中随机选取 N 个个体进行适应度大小比较， 将其中适应度最高 的个体遗传到下一代群体中；将 上述过程重复执行M （为群体大小）次，则 可得到下一代群体

22、。（2）交叉算子 交叉是指对两个相互交叉的染色体按某种方式相互交换其部分基因， 从而形成两个新的个体。 它是产生新个体的主要方法， 决定了 遗传算 法的全局搜索能力， 在遗传算法中起关键作用。 几种常用的适用于 二进制编码或实数编码方式的交叉算子如下：a）单点交叉。在个体编码串 中随机设置一个交叉点后在该点相互交换两个配对个体的部分基因。b）两 点交叉。在相互配对的 两个个体编码串中随机设置两个交叉点， 并交换两个 交叉点之间的部分基因。 c） 均匀交叉。 两个相互配对个体的每一位基因都 以相同的概率进行交换，从而形成两个新个体。d）算术交叉。由两个个体 的线性组合而产生出新的个体。（3）变异

23、算子 变异是指将个体染色体编码串中的某些基因座上的基因值 用该基因座的其他等位基因来替换， 从而形成一个新的个体。 它是产生新个 体的 辅助方法， 决定了遗传算法的局部搜索能力。 变异算子与交叉算子相 互配合， 可 以共同完成对搜索空间的全局搜索和局部搜索， 从而使得遗传 算法以良好的搜索 性能完成最优化问题的寻优过程。 在遗传算法中使用变异 算子主要有以下两个目 的 : 改善遗传算法的局部搜索能力； 维持群体的多 样性，防止出现早熟现象。下面是几种常用的变异操作：a）基本位变 异。对个体编码串以变异概率 P 随机指 定某一位或某几位基因进行变异操 作。b）均匀变异（一致变异）。分别用符合某

24、一范围内均匀分布的随机数， 以某一较小的概率来替换个体编码串中各个基 因座 上的原有基因值。 均匀变异操作特别适合应用于遗传算法的初期运行阶 段， 它使 得搜索点可以在整个搜索空间内自由地移动， 从而可以增加群体 的多样性，使算法能够处理更多的模式。c）二元变异。需要两条染色体参 与，通过二元变异操 作后生成两条新个体中的各个基因分别取原染色体对应 基因值的同或异或。 它改 变了传统的变异方式， 有效地克服了早熟收敛， 提高了遗传算法的优化速度。 d） 高斯变异。在进行变异时用一个均值为L、方差为R2的正态分布的一个随机数 来替换原有基因值。其操作过程与均 匀变异类似。五、遗传算法实例例：利用

25、遗传算法，求解区间0 , 31上的二次函数y X2的最大 值。分析：原问题可转化为在区间0，31中搜索能使y取最小值的点x 的问题。那么，0, 31中的点x就是个体，函数值f (x)恰好就可 以作为x的适应度，区间0, 31就是一个(解)空间。这样，只要能给 出个体x的适当染色 体编码，该问题就可以用遗传算法来解决。二次函数的 图像如图2 所示叵310203CInsert TookW ndov hi&p图 2 二次函数 y x 2 的图像Edit/lewm P3 | b1000900L800卜700600600r-40C30C?00100一2（1）设定种群规模，编码染色体，产生初始种群。将种群

26、规模设定为4；用 5 位二进制数编码染色体；取下列个体组成初始种群S1：s1= 13（01101）， s2= 24 （ 11000）丄L-is3= 8 （01000）， s4= 19 （ 10011） （2）定义适应度函数取适应度函数： f （x） = x2。（3）计算各代种群中的各个体的适应度，并对其染色体进行遗传操作，直到适 应度最高的个体（即31（11111）出现为止。首先计算种群S中各个体的适应度f S。容易求得，再计算种群S12 (s)1(s)2(s)3(s)4f(13) =13 f(24 =)24f(8)二二8= f（19）；91692576=642361中各个体的选择概率。选择概

27、率的计算公式为由此求得，P(s)i=(s)2(s)3(s)4f (xi )P ( x ) iif ( x j) j1 Nj j1P(13) 0.14_P(24) 0.49P(8)=0.06=P( 0.31用赌轮选择法可得图3，图 3 赌轮选择法示意图设从区间 0，1中产生4个随机数如下：r= 0.450126 ， r = 0.110347r1 2= 0.572496 ， r = 0.985033 4表 1 第一代选中次数表染色体适应 度选择概率枳累概 率选中次 数s1=011011690.140. 141s2=110005760.490.632s3=01000640.060.690s4=100

28、113610.3111于是，经复制得群体：s =11000(24)， s =01101(13)12s =11000 s =10011设交叉率p =配00%24即卩，中的全体染色体)参加交叉运算。设s 与c 1 1 2对，s与s 配对。分别交换后两位基因，得新染色体：34s =11001(25卩， s =01100(12卩12s =11011(27卩， s =10000(16卩34设变异率 变异;000。这样，群体S中共有5X4X0.001=0.02位基因可以m1 位显然不足 1位，所以本轮遗传操作不做变异。于是，得到第二代种群S:2=11001 (25), s =01100 (12)s =11

29、011(27)， s =10000(16)染色体适应 度选择概率枳累概 率估计的选中次数sl=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.1511假设这一轮选择-复制操作中，种群s2中的4个染色体都被选中，则得到s =1100125），s = 011001（12）s =1101127），s = 100003（16）做交叉运算，让 s s ，s分别交换后三位基因，得与237 s=11100 28），s= 01001（9）1s3=11000224），s4= 1001119）群体这一轮仍然不会发生变异。于

30、是，得第三代种群S3：s =11100（28）， s=01001（9） 12s =11000（24）， s =10011（19） 34表3 第三代选中次数染色体适应度选择嘅率枳累概率估计的选中次数s1=111007840.440.442s2=01001810.040.480s3=110005760.320.81s4=100113610.211设这一轮的选择-复制结果为:s =11100（28）， s =11100（28）s =11000（24）， s =10011（19）做交叉运算，让S 与S ， s与S 分别交换后两位基因，得S =11111 （31），1S =11000 （24），1 4

31、2 3S =11100（ 28）2S =1000016这一轮仍然不会发生变异。S2=11100于是，得第四代种群S：(28)4S1=11111 ( 31) ，显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染 色体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。六、遗传算法编程MATLAB程序需要解决的问题是利用遗传算法，求解区间0，31上的 二次函数y x 2的最大值。使用的是matlabR2010A，在WIN7环境下运 行。鉴于

32、此版本的软件不含有遗传算法工具箱，自行安装至路径“ D:MAT LABR 2 0 1 0 a t oo l b oxgene t icga t b x ”，并在操作界面上添加 路径。程序见附录一，程序界面如图3 所示。帕1hl1nIfF=a中L.KFieLdLC AUmrar9ro gDeopgerekiCiiT:-d-p itntza：_zr： 2 Kzl-1lCrrzu* -SeLLh1. = - t 1 ； ： r iZ-. rri h 1L Ji.crChv 心=二灯邛 LHLH1A PM Li iSalCrrrcciirir图 3程序图运行结果如图 4 所 示。图 4运行结果图由图可

33、知，经过10 代之后，遗传算法找个了二次函数的最 优值。附录一：运行程序addpathD:MATLABR2010atoolboxgeneticgatbxgen=gen+1; % 代计数器fpl ot (variable * variable,0,31);NIND=4; %种群个体数目MAXGEN=10; %最大遗传代数PRECI=5; %变量的二进制位数GGAP=1; %代沟trace二zeros(2,MAXGEN); %寻优结果的初始值FieldD=5;0;31;1;0;1;1; %区域描述器Chrom=cr tbp(NIND,PRECI); %初始种群gen=0; %计数器variable

34、=bs2rv(Chrom,FieldD); %计算初始种群的十进制转换计算目标函数ObjV二variable*variable; % 值while genMAXGENFitnV=ranking(-ObjV);%分配适应度函数值SelCh二selec t( sus,Chrom, %Fit nV,GGAP);选择SelCh二recombin(xovsp,SelCh,1); %重组，100%SelCh=mut(SelCh);%变异variable二bs2rv(SelCh,Fie子代个体的十进制转ldD);%换ObjVSel二variable*variab%计算子代的目标函数le;值Chrom Obj

35、V=reins(Chrom,SelCh,1,1,ObjV,ObjVSel); %重插入子代的新种群子代个体variable=bs2rv(Chrom,FieldD);的十进制转换加1%输出最优解及其序号，并在目标函数图像中标出，Y为最优解，1 为 种群的序号Y， I=max(ObjV);hold on;plot(variable(I)， Y， bo);trace(1， gen)=max(ObjV); % 遗传算法性能跟踪trace(2， gen)=sum(ObjV)/length(ObjV);endvariable=bs2rv(Chrom， FieldD); %最优个体的十进制转换hold on， grid;plot(variable，ObjV，b*);figure(2); plot(trace(1，:);hold on;plot(trace(2，:)，-.);grid legend（ 解的变化， 种群均值的变化）