1、毕业论文文献综述 计算机科学与技术 基于多样性保持的遗传算法性能研究 引言： 遗传算法 (genetic algorithm)是由密切根大学的 Holland 等人提出的，是从进化论和群体遗传学中启发出，最初是用于模拟自然系统的自适应现象的，直到后来才被应用到工程问题。遗传算法之所以能够发展成一种自适应启发式概率性迭代式全局搜索算法，是因为它的解决不同非线性问题的鲁棒眭、全局最优性、不依赖于问题模型的特性、可并行性及高效率，具有独特的吸引力，正掀起越来越广泛的研究及应用热潮。从八十年代以来，遗传算法在许多方面得到 了应用，如自动控制、计算机科学、机器人学、模式识别、工程设计和神经网络等领域。保
2、持种群多样性问题作为生物学中一个重要问题，在生物坏境中的应用无疑是占有很重要的位置，应用遗传算法是否成功在于能否避免 GA的早熟收敛，其关键是如何保持群体的多样性。 因此基于多样性保持的遗传算法性能研究有着重要的意义。 1 研究动态 关于 保持种群多样性一直以来是国内外研究的热点。 如五十年代的 Dijkstra 算法，六十年代的Floyd 算法，关于该问题的研究在七十年代和八十年代发展很缓慢，但是进入九十年代后，随着信息科学，现代通讯，智能 网络的发展， 还有完善 的图 片论述以及计算机的数据结构，算法之间的并行运用， 使得新的 多样性保持的 算法不断涌现。它们在空间复杂度、时间复杂度、易实
3、现性及应用范围等方面各具特色 1。 遗传算法 (Genetic Algorithms, GA)是美国密歇根大学 Holland 教授借鉴生物进化中的 “ 生存竞争 ” 和 “ 优胜劣汰 ” 现象提出来的全局优化 的 算法。从 最开始的 可行解 开始 ，在不需要 其他的 函数之外 （除了适应度函数） 的 前提 下， 开始 对 有 可能解 区域 的 进行 全局 有效的 搜索。 GA 是一 个有多 个的 参数 ，并且也有着 多 个 个体 的 同时优化的 一种 算法 。 该 算法 为我们 提供了一种 对 系统优化问题 求解 的通用 方法 ，它不 会依赖 于问题的具体 空间 ， 并且 对 不同的问题有着
4、 很强的鲁棒性， 根据 特性使它在组合优化领域获得 到 了成功的应用，并成为计算智能领域研究的热点。被广泛应用于生产调度、图象处理、函数优化、机器人学习、自动控制等领域。 随着科学技术的发展，问题的规模不断扩大，复杂度不断增加，对 GA 求解质量和运行速度都提出了更高的要求， GA 在处理这些问题时往往都显得 “ 力不从心 ”。 但传统 GA 的寻优效率不高，易出现早熟收敛，也不便于局部微调，针对传统 GA 的早熟收敛的主要缺点，所以提出 了群体多样1 性的几种策略，形成了一种改进新的基于多样性保持的自适应遗传算法 (Diversity Maintaining Adap tive Geneti
5、c Algorithm， DMAGA) 2。 2 遗传算法简介 2.1 遗传算法的特点 传统的遗传算法有着其鲜明的特点： 1.GA 的操作的对象是一组可行的解，而不是只有一个可行的解，搜索的方法有多种，而非一种，所以具有非常好好的可行性。 2.GA 只要根据目标的取值的信息，不需要梯度等更多的信息，所以是适用所有的大规模、高度非线性的不连续多峰函数的优化以及没有确 定表达式的目标函数的优化，具有非常强的通用性 3.遗传算法择优机制是一种可变化选择，加上它的良好的并行性，使它具有良好的全局优化性和稳定性 3。 遗传算法（ DMAGA)具有如下特点： 1.强调了保持群体的多样性，给出了度量群体多样
6、的方法；2.采用了二进制编码，简化了计算过程； 3.不易早熟收敛，比传统 GA更为有效和稳健。然而 DMAGA仍不便与局部微调，当需要更高精度解时，它需进一步与有效的局部搜索方法有机结合，以形成既能持续全局优化，又能进行局部微调的稳健而有效的方法 4 。 2.2 遗传算法原理 遗传算法 先对问题的可行解 (近似解 ) 进行编码，表示成“染色体”，接着再用随机的方法产生一群“染色体”的个体，组成初始种群，它们对应的的目标函数值大小，就可以视为生物种群的好坏，通过适应度这种方法，就形成了一种优胜劣汰、适者生存的“自然环境”，然后种群再通过杂交、交换、变异等不断演化，产生新的更加优异的种群。这样经过
7、几代的进化后，最后求得适合问题的全局最优解 5。 3 基于多样性保持的遗传算法性能研究 遗传算法从提出到现在 ，虽然 就只有几十年 ，也 尽管还没有非常正规和严格的理论基础 ， 但是它研究方向已经得到了非常大的应 用 ，已经 由一维静态优化问题发展到了多维动态优化问题 ，由离散空间问题拓展到了连续域范围内的研究。 对于保持种群多样性问题， DMAGA基本操作可分为六个步骤： 步骤 1，随机产生初始种群；第一步就是对程序中的变量和常量进行初始化设置。 步骤 2，根据公式 p o p s iz efftDtp o p sizeiitp /)()( 2_1 （ 2.1） 2 公式 11 1)( p
8、o p sizei p o p sizeij kijkg dtD （ 2.2） 计 算种群中的个体多样性和各基因座的基因多样性； 步骤 3，执行选择操作，采用最优保存策略及均匀排序方式； 选择的目的是为了让群体中适应度高的个体尽最大的可能出现在在下一代新群体中，然后繁殖，从中就可以体现出了“适者生存”的自然选择原则，同时还要让新产生的一代群体中的个体数量要与原来群体的个体数量一样 7。 可是，只是按照适应度大小来实行选择也是不可行的，虽然说保存了当下的优良个体，却不一定有益于找到更好的个体，因为还是存在这种情况，最优的解也许就在某差解的附近。去掉了某以个差解却也不利于去发现最优的解。所以 ，在
9、这里并不仅仅只是利用适应度的大小来选择被选择的个体，而是运用一种既能表现出“适者生存”的原则，又能照顾到“个体多样性”的随机抽样的方法来选择对象。 步骤 4，执行交叉操作，交叉概率根据公式 )e x p (1 15.1 1 yDkPc (2.7） 计算出。 选择操作每次在群体中仅作用在一个个体上，而这里的交叉操作每次作用在从群体中随机选取的两个个体上。交叉的目的是寻找父代双亲巳有的但未能合理利用的基因信息，以 保证个体的多样性 8 步骤 5，执行变异操作，变异概率为一个行向量，各元素由式 NDGgkP kgkm2e x p115.0 （ 2.8） 产生； 遗传算法不仅仅只有选择和交叉操作，如果
10、遗传算法没有变异，那么遗传算法就与生物界中的近亲繁殖影响进程是相似了，因为种群中的个体有限，在通过几代的交叉操作，一个较好的父代的个体便会慢慢的充斥整个种群，使问题过早的收敛而导致早熟得不到最优解，为了阻止这种情况出现，就要模仿自然界生物的变异，对个 体进行小概率的翻转、替换，在采用二进制编码方案的遗传算法中，变异就是把个体的某一位基因码按变异概率 Pm 随机的改变即把 1 变成 0 或反之，3 根据生物遗传中基因变异的原理，以变异概率 Pm 对某些个体的某些位执行变异 14。在变异时，对执行变异的串的对应位求反，即把 1 变为 0，把 0 变为 1。变异概率 Pm 与生物变异极小的情况一致，
11、所以， Pm 的取值较小，一般取 0.01-0.2。 选择操作每次在群体中仅作用在一个个体上，而这里的交叉操作每次作用在从群体中随机选取的两个个体上。交叉的目的是寻找父代双亲巳有的但未能合理利用的基因信息 ，以保证个体的多样性。 步骤 6，执行重插入操作，得到新一代种群，返回步骤 2，循环直至满足条件为止。 DMAGA 的上述步骤在一定程度上体现了生物进化和群体遗传的特点。任何动物 DNA 的都是其父母 DNA 链的混合。优良的父母有较大的概率产生优良的后代，强壮的个体有更多的机会进行交配和产仔。一旦出现优秀的个体，它便在群体中起主导作用，直到被新的更优的个体所取代为止。动物界就是这样不断地繁
12、衍和进化的。显然，在保持群体多样性方面， DMGA 与传统 GA存在明显的差异 10。 4 总结 遗传算法是一种来自大自然的自适应 全局搜索寻优方法，是生物界的群体启发式行为，现已陆续应用到组合优化、人工智能、通讯等多个领域。 目前该算法还有许多值得研究的地方 ， 主要是 : (1)进一步提高算法的收敛速度。算法的收敛速度一直是人们关心的问题 ， 虽然 DM-GA经过改进后 ， 收敛速度有了很大的提高 ， 但对于解决大规模组合优化问题 ， 还不是很理想 （ 当然 ， 这一点也是其它启发式算法中也存在的 )； (2)对算法的收敛性进行理论研究 ； (3)利用 DMAGA的思想来解决更广泛的复杂问
13、题 ， 其关键是怎样将问题转化为网络图的形式 ； (4)系统的分析方法和数学基础 ， 参数选取标准等 10。 尽管遗传算法的严格理论基础尚未奠定，有关研究仍停留在实验探索阶段，但从当前的应用效果来看这种模仿自然生物的新型系统寻优思想无疑具有十分光明的前景。 4 参考文献 1 恽为民 ， 席裕庚 . 遗传算法的运行机理分析 . 控制理论与应用 ， 1996. 2 邢小军，闫建国 . 一种基于多样性保持的遗传算法及其仿真 . 计算机仿真 ， 2010.4. 3 张文修 ， 梁怡 . 遗传算法的数学基础 . 西安交通大学出版社 ， 2001. 4 巩敦卫 . 一 种 新 的 基 于 混 沌 变 异
14、解 决 早 熟 收 敛 的 遗 传 算 法 . 控 制 与 决 策 ，2003.18(6).pp686-689 5 吴浩扬 . 基于种群过早收敛程度定量分析的改进自适应遗传算法 . 西安交通大学学报， 1999. 6 周明 , 孙树栋 . 遗传算法原理及应用 . 国防科技图书出版 ， 1999.6 7 曲中水，王丽萍 . 基本遗传算法的收敛性分析方法 ， 哈尔滨理工大学学报 ， 2003.9 8 从明煜 ， 杜文 . 智能化遗传算法 . 高科技通讯 ， 2003.4.pp43-47 9 武永刚， Murphy Ho. 智能化遗传算法群体模式多样性与生长方程 . 水电能源科学，1999.12(4
15、).pp1-5 10 张晓馈 ， 戴冠中 . 遗传算法种群多样性的分析研究 . 控制理论与应用 ,1998.15(1).pp17-23 11 陈丽燕，刘陈，吴新东 . 遗传算法过早收敛现象的特征分析及其预防 . 南京邮电学报， 1997.9 12 吴斌，吴坚 . 快速遗传算法研究电子科技大学学报 .电子科技大学学报， 1999.28(2).pp49-53 13 李逍波 ， 林争辉 . 标准遗传算法选择操作的递归实现 . 上海交通大学学报 ，1998.32(4).pp89-93 14 何琳 . 遗传算法种群多样性的分析研究 . 哈尔滨工程大学 学报， 1999.9 15 程润伟 . 遗传算法与工程设计 .科学出版社 ， 2000
