博士论文粗粒度并行遗传算法的计算性能研究华中科技大学控制科学与工程系系统工程研究所 博士生：岳嵚 导 师：冯珊 教授 二零零八年四月1论文结构论文结构一、绪论一、绪论二、遗传算法特性分析二、遗传算法特性分析三、遗传算法的运行过程和效率分析三、遗传算法的运行过程和效率分析四、粗粒度并行遗传算法的机理分析四、粗粒度并行遗传算法的机理分析五、迁移操作对粗粒度并行遗传算法的影响五、迁移操作对粗粒度并行遗传算法的影响六、改进型遗传算法的计算性能分析六、改进型遗传算法的计算性能分析七、总结与展望七、总结与展望2遗传算法遗传算法是一类借鉴生物界自然选择和遗传机制的启发式搜索算法，它是将生物学中的遗传进化原理和优化理论相结合的产物。其基本思想是通过模拟生物界“物竞天择，适者生存，优胜劣汰”的策略，获取种群的全局最优解。遗传算法的核心思想是利用进化历史中获得的信息指导搜索，在本质上是一类不依赖具体问题的随机搜索算法。遗传算法对所求解的优化问题没有太多数学上的要求， 它可以处理任意形式的目标函数和约束，在搜索解的过程中不需要了解问题的内在性质。遗传算法的主要优点是简单、通用、鲁棒性强和适于并行处理。3遗传算法的运行过程分析研究使用的软件是matlab7.1仿真平台。对遗传算法的运行过程进行分析，并提供跟踪和评价遗传算法运行过程的方法。 456遗传算法的实验方法分析计算量较小的优化问题使用遗传算法并无实际意义，遗传算法一般只应用于解决复杂的大型优化问题。遗传算法作为一种启发式算法，本身具有不可重现性和随机性，其计算结果会受到各种随机因素的影响，如随机产生的初始种群和随机进行的变异操作等，尤其初是始种群对计算结果影响较大，但是遗传算法有一定的稳定性，可以利用基于仿真的优化的思想通过对同一参数组合进行多次计算的方法提高实验的准确性和可信度。用产生最优解的平均代数分析算法的收敛性和种群的多样性：产生最优解的平均代数越大越好。最优适应度的平均值用于评价遗传算法的计算结果，越小越好。最优解方差的平均值用于判断遗传算法的计算稳定性，也是越小越好。 7遗传算法的计算效率分析 随机遍历搜索算法随着精度的提高，结果会越好，计算量也越大。本研究以随机遍历搜索算法效率作为标准来评价遗传算法的计算效率。具体方法是：用遗传算法计算得到结果后，再用不同精度的随机遍历搜索算法进行计算，必然有某个精度下的随机遍历搜索算法所得到的结果与遗传算法基本相同，用这个精度下的随机遍历搜索算法对函数的计算次数除以遗传算法对函数的计算次数，就可以看作是遗传算法的计算效率。 8粗粒度并行遗传算法的机理分析（1）粗粒度并行遗传算法是将随机生成的初始群体依处理器个数分割成若干个较大的子种群。各个子种群在不同的处理器上相互独立的并发执行进化操作，每经过一定的进化代数，各子种群间再交换若干的个体。粗粒度并行遗传算法的通信开销小。由于计算量很大，在遗传算法并行化实现的过程中会产生大量的通信开销，成为提高运算速度的瓶颈。群体分组的并行性从根本上减少了信息交换，从而减小了通信开销、任务分割的难度和信息交换的逻辑顺序判断的工作量。粗粒度并行遗传算法的通信开销很小，可获得接近线性的加速比。9粗粒度并行遗传算法的机理分析（2）经典遗传算法容易产生早熟现象而使计算结果陷于局部最优解。粗粒度并行遗传算法改变了经典遗传算法的运行结构，由于子种群之间允许交换个体，通过新个体的加入增加个体的差异性，加强了全局搜索能力，有利于避免未成熟收敛现象。实际运算时可以在单台计算机上串行地实现粗粒度并行遗传算法。虽然在串行计算机上实现的粗粒度并行遗传算法不具有并行计算的速度优势，但仍具有避免未成熟收敛的性质。10粗粒度并行遗传算法的运行步骤确定初始参数随机产生初始种群（二进制）将初始种群平均分为n个子种群主循环开始当（子种群编号为1至n）时，执行解码计算适应度函数值选择复制杂交变异从每个子种群中提取要迁移的个体精英保留策略结束子循环迁移进化结束判断：若满足，则结束主循环进化代数加1主循环返回输出结果11粗粒度并行遗传算法的实证分析（1）由于本研究所使用的是一个复杂的测试函数，实验所采用的计算量无法使计算收敛到最优解。如果计算过早收敛，遗传算法就容易陷入局部最优解而无法得到好的计算结果；而且过早的收敛也会使收敛后的进化难以向前发展，浪费大量的计算量。收敛后进化的向前发展主要是靠变异操作实现的，而大的变异率会增加遗传算法的不稳定性，所以提高种群的多样性是降低遗传算法的收敛性的有效途径。为了得到好的计算结果，就需要使进化过程尽可能的延长，因此可以用产生最优解的平均代数分析算法的收敛性和种群的多样性：产生最优解的平均代数越大越好。最优适应度的平均值用于评价粗粒度并行遗传算法的计算结果，越小越好。最优解方差的平均值用于判断遗传算法的计算稳定性，也是越小越好。12粗粒度并行遗传算法的实证分析（2）由于本研究所使用的是一个复杂的测试函数，实验所采用的计算量无法使计算收敛到最优解。如果计算过早收敛，遗传算法就容易陷入局部最优解而无法得到好的计算结果；而且过早的收敛也会使收敛后的进化难以向前发展，浪费大量的计算量。收敛后进化的向前发展主要是靠变异操作实现的，而大的变异率会增加遗传算法的不稳定性，所以提高种群的多样性是降低遗传算法的收敛性的有效途径。为了得到好的计算结果，就需要使进化过程尽可能的延长，因此可以用产生最优解的平均代数分析算法的收敛性和种群的多样性：产生最优解的平均代数越大越好。最优适应度的平均值用于评价粗粒度并行遗传算法的计算结果，越小越好。最优解方差的平均值用于判断遗传算法的计算稳定性，也是越小越好。13粗粒度并行遗传算法的实证分析（3）通过对测试函数的多次求解计算和分析，可以得出以下结论： 粗粒度并行遗传算法的运行结果比较理想。和相同规模初始种群的经典遗传算法相比，在绝大多数情况下粗粒度并行遗传算法都能得到更好的结果。 粗粒度并行遗传算法的子种群的个数较多为宜。子种群的个数的最佳值随着种群规模的增加而增加。 粗粒度并行遗传算法的运行过程也比较理想。粗粒度并行遗传算法的收敛性比经典遗传算法要弱，得到最优解的代数相对于经典遗传算法要大；粗粒度并行遗传算法最优解的方差小，说明其计算的稳定性较经典遗传算法强。 14迁移操作对粗粒度并行遗传算法的影响（1）没有迁移操作的多种群遗传算法可以看作是多次重复运行的种群规模较小的经典遗传算法，它和经典遗传算法拥有完全相同的计算性能。所以可以说，粗粒度并行遗传算法相对于经典遗传算法的计算性能的优势主要来自于迁移操作，而迁移方式和迁移间隔描述了粗粒度并行遗传算法的主要特征，是改变粗粒度并行遗传算法计算性能的主要因素。粗粒度并行遗传算法的各个子种群之间通过迁移算子进行信息交流，迁移算子有两种不同的迁移方式：同步迁移同步迁移即确定迁移间隔的迁移。异步迁移异步迁移即非确定性迁移间隔的迁移。15迁移操作对粗粒度并行遗传算法的影响（2）同步迁移可以看作是迁移概率为1、基础迁移间隔等于平均迁移间隔的异步迁移。的异步迁移。对同步迁移和异步迁移的具体计算性能进行了实证分析。通过计算和分析得出了一下结论： 同步迁移作为异步迁移的一种特例，即不是异步迁移中最优的形式，也不是最差的形式。所以如果想要使异步迁移达到比同步迁移更好的计算效果，或者说要想达到最优的计算效果，关键看如何设定基础迁移间隔和迁移概率：平均迁移间隔大时，基础迁移间隔和迁移概率都应该相应地增大。16迁移操作对粗粒度并行遗传算法的影响（3） 迁移间隔要视具体问题而设定一个合适的值；迁移操作的性能特征类似于变异操作，但是不能用改变变异率的大小来替代迁移操作；迁移间隔和变异率的设定应该遵循互补的原则。 单峰问题相对于多峰问题来说更适合采用同步迁移方式。17遗传算法的变异算子改型及其性能分析（1） 变异操作是指将个体编码串中的某些基因值用其他基因值来替换，从而形成一个新的个体。遗传算法中的变异运算决定了遗传算法的局部搜索性能。变异操作的主要作用是引入新的个体，防止计算过快地陷入局部最优解。但是变异操作带有很强的随机性，采用大的变异率在提高种群多样性的同时会降低计算的稳定性；而且变异操作的作用相当于使部分个体被其邻近的个体替代，对提高种群多样性的作用不大。 18遗传算法的变异算子改型及其性能分析（2） 研究提出三种改进变异算子的方法：（1）变异率随进化状态改变 具体来说就是根据进化状态改变变异率的大小。进化程度越深，变异率越大。有以下2种方法可以判定进化的程度：进化的代数 代数越大，变异率越大。这种方法称为方法1.1。最大无进化代数 最大无进化代数越大，变异率越大。这种方法称为方法1.2。19遗传算法的变异算子改型及其性能分析（3）（2）变异操作只在部分个体中发生 具体来说就是变异操作只发生在部分个体中，特别是离局部最优解近的个体中，这些个体会进行加倍的变异，而其他个体不进行变异操作。 划分出部分个体的方法就有3种：按一定比例随机划分出部分个体（方法2.1）根据个体的二进制编码划分部分个体（方法2.2）根据个体的适应度值划分部分个体（方法2.3）（3）进化过程中产生新的个体每隔一定进化代数再随机产生新个体（方法3）20遗传算法的变异算子改型及其性能分析（4） 通过计算和分析得出以下结论：方法1.1优于方法1.2。方法2.2优于方法2.1和方法2.3。方法3优于方法2.2，方法2.2优于方法1.1。 以上任何一种改进方法的计算结果都明显优于不采用任何改进的经典遗传算法。21改进型粗粒度并行遗传算法（1）改进粗粒度并行遗传算法的基本思路是：利用粗粒度并行进化的框架结构，对不同的种群赋予不同的遗传操作参数组合（主要是杂交率和变异率），使粗粒度并行遗传算法能真正达到不同种群搜索不同的局部最优解的目的。如果各个子种群使用不同的参数组合，则各个子种群将可能会收敛到不同的局部最优解，这样就可以集合各种参数组合的优点于一身，有利于种群多样性的提高。改进进意义义：以往提高遗传算法对求解实际工程优化问题的计算性能的方式主要三种，它们都需要了解待求解问题的特性后才能找到最优的参数组合 ，这又恰恰与遗传算法的优点相矛盾，也就是说遗传算法的优点不具有普适性，而这种改进方法可以克服以往所采取的方法的这种局限性，为求解实际实际 工程优优化问题带问题带 来了方便。 22改进型粗粒度并行遗传算法（2）方法杂杂交率变变异率平均最优优解与理论论的差 最优优解方差的平均值值 产产生最优优解的平均代数 原方法0.60.10.00230.00021129.3原方法0.80.10.00220.00022131.2原方法0.60.150.00200.00017150.5原方法0.80.150.00200.00015149.6原方法0.60.20.00190.00015155.2原方法0.80.20.00180.00012153.8改进进型 0.60.8 0.10.20.00170.00009156.923改进型粗粒度并行遗传算法（3） 通过计算和分析得出以下结论：（1）对于多峰问题，改进型粗粒度并行遗传算法的运行结果比采用任何参数组合的粗粒度并行遗传算法的运行结果都要好。（2） 对于单峰问题，改进型粗粒度并行遗传算法的运行结果并不是最优的，但是优于大部分参数组合的粗粒度并行遗传算法。（3） 改进型粗粒度并行遗传算法相对于原先的算法的运行过程比较理想，计算的稳定性比较强。2425欢迎各位老师和同学提出宝贵意见！谢 谢 ！26