基于多样性保持的遗传算法性能研究【开题报告+文献综述+毕业论文】

《基于多样性保持的遗传算法性能研究【开题报告+文献综述+毕业论文】》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、毕业论文本科毕业论文开题报告计算机科学与技术基于多样性保持的遗传算法性能研究一、综述本课题国内外研究动态，说明选题的依据和意义遗传算法(geneticalgorithm)是由密切根大学的Holland等人提出的，是从进化论和群体遗传学中启发出，最初是用于模拟自然系统的自适应现象的，直到后来才被应用到工程问题。遗传算法之所以能够发展成一种自适应启发式概率性迭代式全局搜索算法，是因为它的解决不同非线性问题的鲁棒眭、全局最优性、不依赖于问题模型的特性、可并行性及高效率，具有独特的吸引力，正掀起越来越广泛的研究及应用热潮。从八十年代以

2、来，遗传算法在许多方面得到了应用，如自动控制、计算机科学、机器人学、模式识别、工程设计和神经网络等领域。保持种群多样性问题作为生物学中一个重要问题，在生物坏境中的应用无疑是占有很重要的位置，应用遗传算法是否成功在于能否避免GA的早熟收敛[1]。传统的遗传算法有其通用的算法框架。即从问题空间向遗传空间进行转化，也就是编码，并形成“染色体”。首先产生初始种群，然后根据适应度进行选择操作，两两配对后开始交叉和变异操作，形成新的种群，这样经过若干代的进化，最后求得最优解。遗传操作中有三个重要的算子：选择，交叉，变异。选择不同的方法来实

3、现这三个操作对算法的性能有较大的影响。最常用的选择算子有轮盘赌，最优保持策略。最常用和最基本交叉方式为单点交叉，双点交叉等。最常用和最基本变异方式为单点变异和多点变异。当然根据具体的问题有不同的处理。在三个重要算子在前，遗传算法首先要解决的是编码问题，常用的编码方法有二值编码，格雷编码，浮点数编码，符号编码等。编码设计的好坏，直接影响后面算子的实现效果。因此在用遗传算法求解具体问题中，都会有一定的改进，使算法的性能更优。传统的遗传算法有着其鲜明的特点：1.遗传算法的操作对象是一组可行解，而非单个可行解，搜索轨道有多条，而非单条

4、，因而具有良好的可行性。2.遗传算法只需利用目标的取值信息，而无须梯度等高价值信息，因而适用任何大规模、高度非线性的不连续多峰函数的优化以及无解析表达式的目标函数的优化，具有很强的通用性。3.遗传算法择优机制是一种“软”选择，加上其良好的并行性，使它具有良好的全局优化性和稳健性[2]。38毕业论文但传统GA的寻优效率不高，易出现早熟收敛，我们举例有这样一个二进制的编码的种群[3]1010100110Q=0011010100该种群的每一行代表了一个二进制编码的个体，那么在第二位和第三位的基因位置上分别是0和1，所以无论我们通过怎

5、么样的交叉操作，产生的新的个体，在第二位和第三位的基因座上的基因始终不会变，如果先不要考虑基因多样性的影响，我们对该种群进行变异操作，让第二位和第三位的基因多样性有较大增加的概率就会很小，但是假如第二位和第三位基因是有效的效的基因，那么遗传算法就会很难找到该空间区域，那么这样就一定会陷入局部最优而导致早熟现象产生。针对传统GA的早熟收敛的主要缺点，所以从维持种群的多样性出发，首先引入了一种基于适应度方差的个体多样性度量指标，并利用指标对交叉概率进行自适应调整，以维持种群中的个体多样性。其次，通过计算各基因座上等位基因的基因多样

6、性，自适应调整相应基因座上等位基因的变异概率，以增强基因多样性、抑制种群中的有效基因缺失，从而提出了一种新的基于多样性保持的自适应遗传算法(Di2versityMaintainingAdaptiveGeneticAlgorithm，DMAGA)。保持种群多样性问题作为生物学中一个重要问题，在生物坏境中的应用无疑是占有很重要的位置，应用遗传算法是否成功在于能否避免GA的早熟收敛，其关键是如何保持群体的多样性。这也是DMAGA要解决的核心问题[4]。种群的多样性是遗传算法进化的前提。传统的遗传算法由于变异点选择的无指导性，以及变异

7、的无方向性从而不能有效地维持种群多样性。而DMAGA不仅能非常有效地维持群体的多样性和优良性，更保证了算法主要参数的自适应性。当然，片面地强调多样性有时会对算法的稳定性、种群的整体收敛性造成很大影响。因此种群多样性的保持策略必须具有一定的指导性，使算法在寻优过程中保持的多样性有利于全局收敛。需要指出的是，在种群进化中，对多样性的测定已经比较多了，但是如何在进化中利用多样性测度来影响种群的进化，保证种群的多样性和高选择压力，仍然是个需要不断加以研究的问题；同时，由于多样性的测定过程会影响进化速度，尤其是在多维、多目标函数问题中，

8、基因型多样性的测度会在一定程度上影响进化速度。所以如何以一定尺度有效地控制多样性及以及进化速度，也需要加以进一步分析和研究。在本设计中，将遗传算法应用与单背包问题。单背包问题是一个典型的组合优化问题，并且背包问题是组合优化学科中一个经典而著名的问题，它实际上是一个0-1规划问