遗传算法的分析

《遗传算法的分析》由会员分享，可在线阅读，更多相关《遗传算法的分析（11页珍藏版）》请在金锄头文库上搜索。

1、遗传算法遗传算法( Genetic Algorithm)目录隐藏 1遗传算法的概念 2遗传算法与自然选择 3遗传算法的基本原理4遗传算法的步骤和意义 5遗传算法的特点6遗传算法在神经网络中的应用7遗传算法案例分析o7.1案例一:遗传算法在装箱环节中的应用18参考文献编辑遗传算法的概念遗传算法是一类借鉴生物界的进化规律（ 适者生存，优胜劣汰遗传机制）演化而来的随机化 搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行 操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力； 采用概率 化的寻优方法，能自动获取和指导优化的搜索空间，自

2、适应地调整搜索方向，不需要确定的规则。 遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、 自适应控制和人 工生命等领域。它是现代有关智能计算中的关键技术之一。编辑遗传算法与自然选择达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。 这种学说认为，生物要生存 下去，就必须进行生存斗争。生存斗争包括种内斗争、 种间斗争以及生物跟无机环境之间的斗争 三个方面。在生存斗争中，具有有利变异的 个体容易存活下来，并且有更多的机会将有利变异传 给后代；具有不利变异的个体就容易被淘汰， 产生后代的机会也少的多。因此， 凡是在生存斗争 中获胜的个体都是对环境适应性比较强的。 达尔文把

3、这种在生存斗争中适者生存， 不适者淘汰的 过程叫做自然选择。它表明，遗传和变异是决定生物进化的内在因素。自然界中的多种生物之所 以能够适应环境而得以生存进化，是和遗传和变异生命现象分不开的。正是生物的这种遗传特性， 使生物界的物种能够保持相对的稳定； 而生物的变异特性，使生物个体产生新的性状，以致于形 成新的物种，推动了生物的进化和发展。遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。 它的思想源于生 物遗传学和适者生存的自然规律，是具有 “生存检测 ”的迭代过程的搜索算法。遗传算法以一种 群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。 其中

4、， 选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、 遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。 作为一种新的全局优化搜 索算法，遗传算法以其简单通用、鲁棒性强、适于并行处理以及高效、实用等显著特点，在各个 领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。编辑遗传算法的基本原理长度为L的n个二进制串bi(i= 1, 2,n)组成了遗传算法的初解群，也称为初始 群体。 在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：1 选择(Selection)这是从群体中选择出较适应环境的个体。 这些

5、选中的个体用于繁殖下一代。 故有时也称这一 操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度 而决定其繁殖量的,故而有时也称为非均匀再生 (differential reproduction) 。2 交叉(Crossover)这是在选中用于繁殖下一代的个体中， 对两个不同的个体的相同位置的基因进行交换， 从而 产生新的个体。3变异(Mutation)这是在选中的个体中，对个体中的某些基因执行异向转化。 在串 bi 中，如果某位基因为 1， 产生变异时就是把它变成 0；反亦反之。遗传算法的原理可以简要给出如下：choose an intial p

6、opulationdetermine the fitness of each individual perform selectionrepeat perform crossoverperform mutationdetermine the fitness of each individualperform selectionuntil some stopping criterion applies这里所指的某种结束准则一般是指个体的适应度达到给定的阀值； 或者个体的适应度的变化率为 零。编辑遗传算法的步骤和意义1初始化选择一个群体，即选择一个串或个体的集合bi, i=1 , 2, .n。这个

7、初始的群体也就是问题假设解的集合。一般取n = 30-160。通常以随机方法产生串或个体的集合bi,i= 1, 2, .n。问题 的最优解将通过这些初始假设解进化而求出。2选择根据适者生存原则选择下一代的个体。在选择时, 以适应度为选择原则。适应度准则体现了 适者生存,不适应者淘汰的自然法则。给出目标函数f,则f(bi)称为个体bi的适应度。以P选中bj = 沁)(3-86)为选中bi为下一代个体的次数。显然从式(386)可知：(1)适应度较高的个体,繁殖下一代的数目较多。(2)适应度较小的个体,繁殖下一代的数目较少；甚至被淘汰。 这样，就产生了对环境适应能力较强的后代。 对于问题求解角度来讲

8、，就是选择出和最优解较接 近的中间解。3交叉对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中 的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合， 也即产生新的个 体。交叉时，可实行单点交叉或多点交叉。例如有个体S1=100101S2=010111选择它们的左边 3 位进行交叉操作，则有S1=010101S2=100111一般而言，交叉幌宰P。取值为0.25 0.75。4变异根据生物遗传中基因变异的原理，以变异概率 Pm 对某些个体的某些位执行变异。在变异时， 对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情

9、 况一致，所以， Pm 的取值较小，一般取 0.01-0.2。例如有个体S = 101011 o对其的第 1， 4位置的基因进行变异，则有S=001111单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。 因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是 说，变异增加了全局优化的特质。5全局最优收敛(Convergence to the global optimum)当最优个体的适应度达到给定的阀值， 或者最优个体的适应度和群体适应度不再上升时， 则 算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取

10、代上一 代群体，并返回到第2步即选择操作处继续循环执行。1变异为9用作下一代2】交叉 产生6,7图 3 7 中表示了遗传算法的执行过程编辑遗传算法的特点1遗传算法从问题解的中集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的； 容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。2遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。 遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。3遗传算法有极强的容错能力遗传算法的初始

11、串集本身就带有大量与最优解甚远的信息；通过选择、 交叉、变异操作能迅 速排除与最优解相差极大的串；这是一个强烈的滤波过程； 并且是一个并行滤波机制。故而， 遗 传算法有很高的容错能力。4遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。这说明遗传算法是采用随机方法进行最优解搜索， 选择体现了向最优解迫近，交叉体现了最 优解的产生，变异体现了全局最优解的复盖。5遗传算法具有隐含的并行性 编辑遗传算法在神经网络中的应用遗传算法在神经网络中的应用主要反映在 3 个方面：网络的学习，网络的结构设计，网络 的分析。1. 遗传算法在网络学习中的应用在神经网络中，遗传算法可用于网络的学习。这时

12、，它在两个方面起作用(1)学习规则的优化用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。(2)网络权系数的优化用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。2. 遗传算法在网络设计中的应用用遗传算法设计一个优秀的神经网络结构， 首先是要解决网络结构的编码问题； 然后才能以 选择、交叉、变异操作得出最优结构。编码方法主要有下列 3 种：(1)直接编码法这是把神经网络结构直接用二进制串表示，在遗传算法中， “染色体 ”实质上和神经网络是一 种映射关系。通过对 “染色体”的优化就实现了对网络的优化。(2)参数化编码法参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数

13、、各层互连方式等信息。 一般对进化后的优化 “染色体”进行分析，然后产生网络的结构。(3)繁衍生长法这种方法不是在 “染色体”中直接编码神经网络的结构， 而是把一些简单的生长语法规则编码 入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题 的神经网络。这种方法与自然界生物地生长进化相一致。3. 遗传算法在网络分析中的应用遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直 接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传 算法还有大

14、量的问题需要研究，目前也还有各种不足。 首先，在变量多，取值范围大或无给定范 围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法 的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上 证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和 形式等。编辑遗传算法案例分析编辑案例一:遗传算法在装箱环节中的应用1一、一维装箱问题的描述一维装箱问题2引可描述如下：要将11个物品装入许多箱子(最多n个箱子)。每个物品有重量(W 0)。每个箱子有重量限 制(c O)。问题是寻找最好的将物品分配到箱子的方案，使得

15、在每个箱子中物品的总重量不超i过其限制，并且使用的箱子数量最少。该问题可表示 2为：重量及限制表物品12ldotsn重量w_1w_2ldotsw_n重量限制c_1c_2ldotsc_n其中重量W和重量限制c是正实数“装箱问题的数学表示如下:jiamin恳)=工側-jt-iy =0 或 1i-、x =0 或 1ij其中y = l表示箱子i被放入物品，反之则表示箱子i空着；X = 1表示物品j放入箱子i，反 i ij之表示物品 j 未放入箱子 i 。基于基本遗传算法的求解方案。由于近似算法有时并不能产生出一个优秀的装箱方案，在这里采用遗传算法进行优化。(一) 染色体表示对于一维装箱问题，由于其装箱费用依赖于箱子中物体的群体， 故在此问题中染色体的表示 需要包含两个部分，其一应该提供哪个物品属于哪个箱子 (群体)的信息，另外对使用的箱子进行 编码。故采用基于群体的表示方法 2，其中一个基因表示一个箱子。设有六个物品，从 1