基于小种群策略的并行遗传算法毕业论文

1、基于小种群策略的并行遗传算法 摘要：遗传算法作为一种基于生物进化机制的自适应算法，适用于各类复杂系统的优化计算。然而标准遗传算法所具有的易早熟、易陷入局部最优等问题，在一定程度上限制了遗传算法的推广和使用。本文在对遗传算子做出改进的基础上，提出了一种基于小种群策略的并行遗传算法，从而有效地提高了遗传算法的执行效率和性能。关键词：遗传算法；早熟；遗传算子；小种群并行0. 引言遗传算法1是最早由michigan大学的jholland教授于1975年提出的一种基于生物进化机制的自适应算法，适用于各类复杂系统的优化计算。遗传算法本身具有很多的优点，如简单易行，通用性强，鲁棒性高，全局搜索能力强等，这些

2、优点使其可以应用于大量复杂问题求解当中。然而遗传算法固有的一些缺陷如过早收敛，容易陷入局部最优，算法运行后期搜索效率较低等，也不可避免的的制约了遗传算法的使用与推广。对于全局范围的搜索算法而言，早熟现象的产生将是其失败的主要原因。种群的规模在很大程度上决定遗传算法应用的成功与否。种群数目过小会导致算法收敛速度过快，往往来不及找到全局最优解，种群数目过大会消耗过多的进化和处理时间，使得算法运行的异常缓慢。为了更好的使用遗传算法处理实际问题，长期以来人们在标准遗传算法（sga）的基础上已经做出了大量的研究和尝试，并且取得了巨大的成效。其改进方法包括对遗传算子的改进、增强算法的自适应性、与其他智能算

3、法搭配使用等，然而很多改进方法却使得算法变得较为复杂，从而失去了遗传算法简单易用的特点。本文在此提出一种新的基于小种群并行的改进型遗传算法：一方面针对实际应用中的一些问题对标准遗传算法的遗传算子加以改进，另一方面提出在个体总量相同的条件下，采用多个小种群并行运算，并在各种群间产生交互的方法，确保在尽可能的保持计算简单性的前提下，防止遗传算法中早熟现象的产生。1遗传算子的改进交叉算子是遗传算子中最为重要的组成部分，其不仅对遗传算子的收敛性起到了至关重要的作用，同时也对遗传算法的收敛速度有很大的影响。传统交叉算子的操作往往具有一定的盲目性，亲代染色体交叉互换后所形成的子代很可能将亲代个体中所具备的

4、优良基因模式丢弃或者破坏了4。本文提出一种改进的交叉算子方案，以便以较大的可能性保护亲代个体的优秀基因模式并使之得以传递至子代个体。在此使用相似程度的概念，通过相似程度的高低来决定是否进行交叉操作。首先给出相似度的定义，假设有两个二进制编码的编码的父代个体，分别记作个体x和个体y，则此二者的相似程度定义如下：定义1 相似程度： (1)其中表示个体x和个体y的相似程度，a表示两个体之间最大相同位串的数目，n表示个体染色体编码的长度。举例来说，例如个体x的染色体编码为1010110010，个体y的染色体编码为1000101001，则二者的最大相同位串数目a为5，而个体染色体编码长度n为10，则个体

5、x与个体y的相似程度为5/10，即0.5 。显然，同一种群中任意两个个体的相似程度为一个处于0,1之间的数。为了判别是否进行交叉操作，需要用到一个临界值作为参照对象，在此本文给出另一个概念标准交叉点，定义如下： (2)其中k为标准交叉点的值，g表示此种群预先设定的总进化代数，g表示算法到目前为止已运行的代数。由公式显然可知，标准交叉点k的值是动态变化的，其值随着当前种群进化代数的增长而不断增大，而预先设定的总进化代数对标准交叉点k的变化也有较大影响。当被选中参与交叉运算的两个个体的相似程度小于或等于k的值时，则进行染色体的交叉互换操作，而当相似程度大于k的值时，则不允许二者进行交叉互换操作，而

6、是克隆本身，复制产生与二者完全相同的子代个体。在遗传算法运行的初期，随即生成的种群个体之间的相似程度较低，为了控制交叉率以便在确保种群得到充分进化的前提下尽量不破坏个体中的优秀基因模式，标准交叉点的值k应当相对较小，反之在遗传算法运行的后期，种群进化了多代，此时个体间差异已经较小，相似程度较高，故而标准交叉点的值k也应当随之提高。根据上述公式，动态的控制父代染色体标准交叉点的移动，有助于提高遗传算法的收敛性能和收敛速度。为了简便以及更好的评价本文提出的改进方法，当一组亲代个体的染色体通过标准交叉点的比较判断后，本文使用传统的单点交叉方法来对它们进行交叉互换操作。2.基于小种群并行的算法方案种群

7、的规模是决定遗传算法能否成功使用的一个重要原因，显然无论种群的规模过大或是过小均不可能令算法最终得到一个令人满意的全局最优解。种群规模过小会导致所得到解的准确性和可信性难以得到保证，而种群规模过大则会使得遗传算法的收敛速度过低，且在运行代数不足的前提下仍然不能确保得到准确的全局最优解，这更加降低了遗传算法的运行效率，据此，本文提出一种基于小种群并行的改进型遗传算法。区别于传统的遗传算法，新方案将在初始化的过程中同时建立多个个体数量完全相同而染色体编码彼此之间完全不同的相对规模较小的种群，以此实现在不影响算法运行的总体效率的前提下，提高算法的全局搜索能力。算法流程描述如下：1) 依据实际问题的需

8、要建立一个由n个种群组成的集合，每个种群中包含由染色体编码组成完全不同的m个个体；2) 根据上文中已经给出的对于遗传算子的改进方案，在每个小规模的种群内部进行一次独立的遗传运算。即从种群1开始，每个种群均进行一次使用上文中改进遗传算子的遗传运算过程，得到下一代种群个体，直到n个种群均完成了上述运算；3) 对种群中各个个体的相对适应度进行计算，并选择出每个种群中相对适应度最高的个体，得到的n个个体按照来源的种群编号为1至n，称为优秀个体；4) 使用得到的每一个优秀个体与剩余的所有优秀个体分别进行杂交，即杂交（n-1）次。对n个优秀个体分别进行此项杂交操作，根据下文中的杂交规则，在杂交完成后即产生

9、新一代的种群； 5) 判断算法此时的运行结果是否满足终止条件，如满足则终止算法，如不满足则转向步骤2。关于上述算法，说明如下：1.步骤1中初始化的方式可以为先随机生成个完全不同的个体，然后在随机将它们分配进入n个种群当中，每个种群分配m个个体即可。分配完成后，此n个种群随机编号为从1至n号，并记为种群1至种群n，此时种群内的个体即为第一代个体。2.步骤4中的杂交规则举例说明如下：编号1的优秀个体与编号2至n的优秀个体分别杂交，当其与优秀个体2进行杂交时，得到两个新的子代个体，此时计算两个新个体与优秀个体1和优秀个体2的相似程度。其中与优秀个体1相似程度高的子代个体记为个体1(2),与优秀个体2

10、相似程度高的子代得体记为个体2(1)。如果两个子代个体均与某一优秀个体的相似程度高或与两个优秀个体的相似程度相同，则随机将子代个体中的某一个记作1(2)，另一个记作2(1)。以上面方法依次进行杂交，则可分别得到新的子代个体1(2)至1(n)。同理，在经过相互间的杂交后，还可以得到新的子代个体2(1)、2(3)2(n)直至n(1) n(n-1)。计算个体1(2)至1(n)的相对适应程度，在得到的结果中选择相对适应度最大的一个子代，并将其作为新的优秀个体1，并根据上述方法逐步得到新的优秀个体2至优秀个体n。最后，将此时得到的新优秀个体1至n根据编号带入相应的原先下一代种群1至n，从而得到新的下一代

11、种群。3.由于新算法中选取的每个小种群中的个体数量较少，故而算法的全局搜索能力由优秀个体之间的杂交来保证，而收敛速度和收敛性能则主要由算法中针对遗传算子的改进来保证。3.算法测试：为了验证新算法的性能，本文将选用两个常见的优化函数对其进行测试，并使用标准遗传算法与之同时测试以作为参照。测试函数1：；有2个局部最大点，即，；其中后者为该函数的全局最大点；测试函数2：待添加的隐藏文字内容3；有6个局部最小点，其中和为该函数的全局最小点。算法测试过程中，标准遗传算法记为sga，本文提出的基于小种群并行的改进遗传算法记为iga。算法运行过程中，sga分别使用轮盘赌选择和单点交叉进行选择和交叉操作，其中

12、交叉概率取0.7。iga则根据本文提出的新算法进行运算。其中sga设定初始种群数为100， iga则初始化为5个小种群，每个小种群包含20个个体。算法运行的最大进化代数为200，变异概率为0.05，当搜索到的最优解的与理想极值的误差小于e-3，则可认为算法已经成功收敛并停止进化。下表为两种算法各运行50次后的统计结果： 表二 sga、iga仿真结果 算法函数收敛次数成功收敛比例平均收敛代数sga 330.6663370.74141iga390.7851410.82122根据对比结果可以看出，本文提出的基于小种群并行的改进遗传算法可以有效的抑制早熟现象的发生，并可以减少收敛时间，以相对较少的遗传

13、代数得到最优解，从而提高算法的执行效率。4.结论：本文针对标准遗传算法易早熟，算法运行后期搜索效率较低等问题，提出了一种基于小种群策略的并行遗传算法。通过对交叉算子的修正，以及多个小规模种群并行优化求解的方案，使得算法的执行效率得到了提高，并且在一定程度上解决了标准遗产算法运行的过程中收敛速度与易得到局部最优解之间的矛盾。在对两种算法进行测试后，仿真结果显示本文提出的改进算法相较于标准遗传算法具有更好的性能。参考文献： holland j h. adaptation in nature and artificial systemm. masscchusetts:masscchusetts insititute of technology,1992 m srinivas ,l patnaik.adap