最优权动态控制学习机制的多种群遗传算法

潘家文，钱 谦+，伏云发，冯 勇

1.昆明理工大学 信息工程与自动化学院，昆明 650500

2.昆明理工大学 云南省计算机技术应用重点实验室，昆明 650500

遗传算法（genetic algorithm，GA）[1]是20 世纪70年代初期由美国Michigan 大学Holland 提出来的借鉴生物界自然选择思想和自然遗传机制的一种全局随机搜索算法。它把问题的可能解看作个体，多个个体组成种群，算法运行时按照一定的进化策略使个体所代表的可能解不断进化，直到产生最优或近似最优解。该算法的优越性主要表现在：（1）使用时所需领域知识少，且优化过程不依赖于梯度信息，不要求目标函数的连续或可导；
（2）求解复杂函数时，只需要选择、交叉、变异三种操作就能获得最优解；
（3）能够同时搜索多个点，具有较好的并行寻优能力。目前GA 已广泛应用于机器学习、控制、优化等领域[2-4]。

传统遗传算法（standard GA，SGA）存在着“早熟”收敛和收敛速度慢等缺陷。目前已经提出了许多解决这一问题的方法，如引入并行机制[5]、学习机制[6]等，这些方法都取得了较好的效果。群体的多样性不足会使种群的搜索范围被限制，导致GA 易陷入“早熟”收敛，因此需要保证算法在计算过程中的种群多样性不能过快丧失。目前对种群初始化的研究较少，已有的GA 研究多数采用随机初始化方法产生种群，随机初始化方法会产生多样性差、染色体分布不均匀的种群[7]。文献[8]提出半初始化方法，该方法虽然丰富了种群多样性，但也增加了计算复杂度，还影响了种群的稳定性。文献[9]通过海明距离作为标准约束个体来产生初始种群，但该方法由于随机样本的影响仍会产生多样性较差的种群。引入并行机制是提高遗传算法性能的一个重要方向[10]，通过对不同种群配置不同的进化策略能够有效控制子种群的独立演化特性，同时还通过种群间的个体迁移来保证子种群间的融合，以此提升了算法的性能。郑明等[5]将改进的多种群并行遗传算法用于基因调控网络的构建。Zhou 等[11]将改进的多种群并行遗传算法用于列车组调度优化问题。但是上述方法仍存在一些问题，算法中的单个种群采用了具有固定数值的Pc和Pm的进化策略，在搜索空间的勘探和开采上出现了矛盾，无法有效地调整种群多样性和收敛速度之间的平衡。如果Pc和Pm的数值过高，虽然有利于跳出局部最优，增大找到全局最优的可能性，但是会破坏现有的优良个体，增加算法随机性；
如果Pc和Pm的数值过低，又不容易产生新的个体，容易导致进化停滞不前。文献[10]提出在多种群并行遗传算法的进化策略中采用自适应调整的进化参数，虽然在一定程度上改善了进化效果，但本质上仍然是在固定区间内对Pc和Pm取值，自适应能力有限。遗传操作在计算过程中是完全随机的，经过遗传操作进化的新染色体可能更加优秀或劣质，导致GA 在寻优过程中缺乏方向性。而且GA 不善于对局部区域进行细致搜索，导致该算法的局部搜索能力较差。Hinton 等[12]率先引入学习机制来引导GA 算法的进化方向，为个体提供更加优良的进化途径。在此基础上，不同的学习方法被引入GA以增强GA的性能。如单纯形法[13]、模拟退火算法[14]等。上述方法能够有效增强GA 的运行效率和求解质量，但增加了算法的计算复杂度。文献[15]将聚类思想与模式定理结合提出一种新的学习机制来引导种群的进化方向，该算法实际操作较为简单，其运行时间与SGA 近似为一种次线性的关系，即在不增加算法的基本运算频度的基础上增强了算法的局部寻优能力。但该算法采用线性的方式来控制学习机制的运行，在算法中后期会出现学习机制失效的现象。

为设计一种更加高效的遗传算法，本文在前人研究基础上做出改进，提出了最优权动态控制学习机制的多种群遗传算法（multi-population genetic algorithm based on optimal weight dynamic control learning mechanism，OWLMGA）。具体方法如下：

（1）采用一种均匀分区多种群初始化方法，该方法在避免扩大种群规模的基础上，能够产生多个种群较均匀分布在解空间的不同区域，保证了初始解的多样性，避免算法结果因多样性差陷入局部最优。

（2）采用一种改进的多种群并行机制，该机制首先对现有进化策略做出改进并提出一种新的保存策略，其次将不同种群分离承担不同的进化功能（详见1.2.1小节），减弱了传统并行机制在解空间勘探和开采的矛盾，使算法能够有效地保持种群多样性和收敛速度之间的平衡。

（3）采用了最优权动态控制的学习机制，该机制利用一种基于适应度的评价函数衡量基因模式的优劣程度，并能够根据进化中种群个体适应度的不同情况自适应调节基因模式的引导过程。

为改进GA 易“早熟”收敛的缺点，提出均匀分区多种群初始化方法和改进的多种群并行机制。为引导算法进化方向及加强局部搜索能力，提出了动态控制的学习机制，并将两种机制结合起来，形成一种能充分发挥两种机制优势的混合算法。

1.1 均匀分区多种群初始化方法

GA 从一组分布于解空间超平面的可能解开始寻优，理论上，算法希望这些可能解均匀分布在解空间，此时种群多样性较丰富，有助于算法摆脱“早熟”收敛，找到全局最优值。实际上，由于随机初始化方法的不确定性，会出现可能解聚集在解空间超平面局部一侧的情况，这样种群的多样性就会比较差。文献[10-11]所代表的多种群并行遗传算法都采用了随机初始化方法独立产生多个种群，虽然多个种群的存在一定程度上缓解了可能解局部聚集的情况，但多样性较差的可能性仍然存在。多样性差的种群通过遗传操作进化时，往往会收敛到可能解附近的局部最优值便停滞不前，若要打破这种不利局面，则需要数值比较大的Pc和Pm，但是，数值比较大的Pc和Pm在帮助种群探索全局最优解的同时，会不断破坏群体内个体的优良基因，使个体迟迟不能收敛到全局最优解，最终影响算法的性能。

海明距离（两条染色体间相同基因座上不同基因的数量）是衡量遗传算法种群多样性的传统方法之一。与其他度量方法相比，海明距离方法的主要优点是操作简单，仅需比较个体所代表的字符串，而不需要与目标函数相关的信息，不会增加计算复杂度。该方法的另一个优点是比较的是个体基因型的差距，而不是个体表现型之间的差距，能够更好地判断个体基因之间的亲属关系。

聚类分析是模式识别中非监督学习的一个重要的方法，聚类分析的目的是将若干实例按照“相似度”划分为不同的集合，每个集合中的实例按照规定的度量来说“相似”，而不同集合之间的实例按相同的度量来说“不相似”。本文借鉴聚类划分中常用的K-means 算法的基本思想提出一种均匀分区多种群初始化方法，首先选取海明距离作为实例（个体）之间的相似性度量，以最大海明距离为准则划分出不同集合（种群）的聚类中心点，然后每个聚类中心点将符合海明距离的实例收入集合中。均匀分区多种群初始化方法在解空间中聚类划分的问题可以描述为：对于给定的个体样本，按照最大海明距离划分为M个种群，种群染色体数目N，令P代表i个个体样本构成的集合，H1,H2,…,HM代表M个划分后的种群集合，则基本思想满足：

均匀分区多种群初始化方法能够使不同种群较均匀地分布在解空间的不同区域，每个种群随机地将适当距离的可能解放入种群中，该方法避免了随机初始化方法导致可能解聚集在局部区域的情况。通过这样的方式进行种群初始化，可以在避免扩大种群规模基础上保证种群多样性，有助于算法跳出局部最优值，寻找全局最优值。

均匀分区多种群初始化方法流程如下：

（1）初始化种群参数：种群总数目M，每个种群的染色体数目N，种群集合H，种群计数变量m=0，Hm表示第m个种群，Rm表示m种群染色体数目。

（2）P={x1,x2,…,xi}，代表一个含有i个染色体的可能解集合，其中i的规模为M×N的5～10倍左右。

（3）从P中选择第一个染色体x1放入种群Hm，m=m+1，x1→Hm，Hm→H。

（4）对于∀xi∈P，且xi∉H使得Distance(x1,xi)=max(Distance(x1,xi))，m=m+1，xi→Hm，Hm→H。

（5）若m＜M，转（6），否则转（7）。

（6）对 于∀xt∈H，若∃xk∈P，且xk∉H，使 得Distance(xt,xk)=max(Distance(xt,xk))(t=1,2,…,m;k=1,2,…,i)，则m=m+1，xk→Hm，Hm→H。转（5）。

（7）若存在Rm＜N，对于xk∈Hm，xk=Hm.head，Hm.head表示种群m的第一个染色体，对于∀xi∈P，且xi∉H，使得Distance(xk,xi)≤max(Distance(xk,xi))/M，则xi→Hm，Rm=Rm+1，转（5），否则结束。

上述初始化方法可以使种群均匀分布于解空间的不同区域，但同时也考虑了种群分布的整体质量，并不是盲目地追求均匀化。具体来说，由步骤（3）至步骤（6）可以看出，本文首先选出聚类中心点，该中心点与其选定的度量距离保证了种群分布的均匀度。由步骤（7）可以看出，任意个体与某个聚类中心点只要在选定的距离范围内就会被收入种群中，在种群所代表的集合之间的分布具有足够均匀度的前提下，这种随机收入个体的偏好随机方式能够较好地保证种群初始化后有足够丰富的解空间信息，又在一定程度上避免了盲目的随机性，有利于保持种群的整体质量。

1.2 改进的多种群并行机制

有效控制种群多样性是搜索到全局最优解的基本条件，单种群演化较难克服GA 收敛速度和种群多样性之间的矛盾，算法易出现早熟收敛或频繁在非有效区域进行搜索导致搜索效率较低[16]。OWLMGA在文献[17]所提出的进化策略基础上做出部分改进并提出一种改进的多种群并行机制，通过变换种群遗传操作的参数及种群分离承担不同的进化功能而有效地控制种群独立演化特性，保持种群多样性和收敛速度之间的平衡，进而提升算法的性能。

将数值较大的Pm和数值较小的Pc称为探索策略（exploration strategy），并且在遗传操作上选择先进行变异操作再进行交叉操作，最后执行选择复制操作。该进化策略有利于种群跳出局部最优，探索新的解空间。将数值较小的Pm和数值较大的Pc称为开发策略（development strategy），该策略首先执行交叉操作再进行变异操作，最后执行选择复制操作。该策略能够重组现有基因产生新的个体以期待获得更好的性状改变，使种群在当前解空间内充分进行探索。普通策略（normal strategy）采用介于开发策略和探索策略之间程度的Pc和Pm，在进化操作上采用SGA 的选择复制、交叉、变异操作，该策略兼具以上两者的功能。此外，还有一种与前述策略不同的策略称为保存策略（reorganization strategy），该策略不通过遗传操作在解空间进行寻优，而是作为一个容器不断接收其他种群通过数据共享传递过来的优秀个体进行处理，该策略能够充分发掘其他种群优秀个体的“进化潜能”，并使优秀基因能够有效遗传下去。

图1 描绘了OWLMGA 多种群并行机制的执行过程，首先算法初始化产生多个种群，算法开始时，种群复制自身并配置上述改进的进化策略。各种群独立进行演化，种群之间每代都进行个体迁移，即将当代自身的优秀个体传递给保存策略子群。保存策略子群对传递过来的优秀个体进行交叉来重组基因产生新染色体，选择最优N个染色体作为新子群进入下一代。每隔一定代数，各种群之间进行信息迁移，即与公共区域共享基因模式和最优个体（详见1.3.1小节定义9），探索策略与开发策略互换种群，然后再各自进化，如此反复，直到算法结束。

Fig.1 Processing structure of improved multi-population parallel mechanism图1 改进的多种群并行机制执行过程

1.2.1 改进的并行机制理论研究

模式定理（scheme theorem）与积木块假设（building block hypothesis）是由Holland 提出的构成GA 进化动力学的基本原理[18]，Holland 将种群中个体基因型相似样板称为遗传模式，其中“低阶、短距并高于种群平均适应度的遗传模式”被定义为积木块。模式定理说明了积木块有更大概率在进化过程中被遗传算子继承并重新联结成新的解，这个过程可以看作“搭积木”的过程[16]。GA 在遗传算子的作用下不断整合积木块产生适应度更高的个体，从而找到更优的解，这就是Holland 提出的积木块假设。以上两种理论共同阐述了GA 寻求最优解的可能性及能力，对遗传算法的理论和实践具有重要的引导意义。

Holland 早期的研究[18]指出，GA 中的遗传操作对基因的重组作用主要包含两方面：遗传模式保存能力和遗传模式重组能力。前者是指重新联结已有的低阶有效遗传模式组成高阶遗传模式；
后者是指打破已有的遗传模式并对其中的基因位进行重组产生新的低阶有效遗传模式。算法依靠着两种能力不断改进现有解朝着最优解的方向收敛，两种能力互为矛盾，算法难以同时具备强力的遗传模式保存能力和遗传模式重组能力[18]。而本文利用并行机制中多种群独立演化及优秀个体迁移的特性，赋予不同种群不同的进化功能（即模式重组和模式保存），进而使算法从整体上看同时具备较强的遗传模式重组能力和遗传模式保存能力。一方面，多数种群使用互不相同的进化策略进行搜索，主要负责勘探新的有效基因并对其进行重组产生新的低阶有效遗传模式。为了进一步增强算法的遗传模式重组能力，保持这些个体在解空间勘探与开采的有效平衡，本文首先对传统进化策略进行改进，当种群多样性低时，种群差异度小，种群包含的解空间信息不够丰富，此时按照传统遗传算法先进行选择与交叉操作，产生新个体的可能性较小，之后进行变异操作虽然能够产生新的有效基因，但其个体表现型的适应度普遍比较低，这些基因还没通过交叉操作重组成新的低阶有效遗传模式就随所在个体被执行顺序靠前的选择操作所淘汰；
当种群多样性高时，种群差异度大，种群包含足够丰富的信息，此时按照传统遗传算法先进行选择、交叉操作，虽然有机会重组有效基因产生新的低阶遗传模式提升个体表现型的适应度，但之后进行变异操作很可能使新产生的低阶遗传模式被破坏，削弱了交叉算子的作用。针对这一情况，本文提出的进化策略更符合种群进化状况，提高了搜索效率和收敛性；
其次对种群的进化策略进行了调整，具有较强勘探能力的种群经过一段时间的进化后，种群具有丰富的多样性，包含较多解空间的信息，此时应调整种群的进化策略，使种群专注于对信息的开发，产生更多的低阶遗传模式；
而具有较强开采能力的种群经过一段时间的进化后，对现有的基因挖掘出了足够的信息，此时应调整种群的进化策略，使种群探索更多的有效基因。另一方面，实行保存策略的种群通过个体迁移的方式接收其他种群传递来的优秀个体，该类个体往往包含较多的低阶有效遗传模式，通过对这些个体进行交叉处理，使低阶遗传模式有更大几率重新联结组成高阶遗传模式，产生新的最优解，增强了算法的遗传模式保存能力。

1.2.2 改进的并行机制的测试

本文使用函数F1和F2来测试改进的并行机制的性能。

F1是多峰函数，其函数表达式为：

F1的定义域空间为-100 ＜Xi＜100，当（Xi,Xi+1）取值为（0，0）时，F1取得全局最小值0。

F2是高维函数，其函数表达式为：

F2的定义域空间为-10 ＜Xi＜10，本文测试计算中，F2的维度设置为20，F2的全局最小值为0。

选取文献[5]提出算法中的并行机制（parallel mechanism，PM）与本文提出的改进并行机制（improved parallel mechanism，IPM）进行对比，PM 中进化策略与文献[5]保持一致，各种群独立进化，每代将全局最优个体传递给其他种群，大体定位后再采用爬山法进行细致搜索（详见该文）。主要参数设置为：PM 种群数目为6，IPM 种群数量为2（IPM 经复制后与PM种群数量一致），染色体数目50，pc1=0.70，pm1=0.10，pc2=0.50，pm2=0.30，pc3=0.85，pm3=0.05，在IPM 中每隔10 代进行一次策略调整。测试选取两个指标来评价并行机制的性能：（1）平均最优解（average optimum solution，AOS），该指标是算法多次运行的最优适应度的均值，反映求解质量的好坏。（2）收敛率（convergence rate，CR）函数收敛次数占实验总执行次数的百分比。当函数求解结果满足于指定的收敛精度时认为收敛成功，收敛精度应综合考量并行机制的性能来设定，以便更好地区分并行机制之间的优劣。

表1 表示两种并行机制各执行30 次后的实验结果，可以看出IPM 的性能要好于PM，这是由于PM 使用固定的进化策略，难以保持在搜索空间勘探和开采之间的平衡，使得大部分染色体进化效果较差。对于具有较大Pc和Pm数值的种群来说，虽然容易丰富群体多样性，扩大种群的搜索范围，但是其中有希望成为全局最优解的优秀个体的基因容易被破坏，使种群无法保持稳定，难以收敛。对于具有较小Pc和Pm数值的种群来说，虽然能够充分利用现有染色体的基因，但其跳出局部最优解探寻全局最优解的可能性较小，并且也缺少对迁移来的优秀个体进行进一步开发的能力。而IPM 通过种群分离控制不同功能进而有效地控制了勘探与开采的平衡，部分种群实施上述改进的策略负责在解空间勘探新基因并重组成新的低阶遗传模式，保存策略子群负责将低阶遗传模式重新联结为高阶遗传模式，通过这样的方式使算法同时具备良好的遗传模式重组能力和遗传模式保存能力。为进一步加强算法的遗传模式重组能力，OWLMGA 对进化策略进行了改进，并对种群的进化策略进行调整，通过这样的方式提高了搜索效率，改善了染色体的进化效果。

Table 1 Experimental results of parallel mechanism表1 并行机制测试实验结果

图2 表示某次实验中两种并行机制求解函数的最优值曲线，可以看出IPM 所代表的进化曲线出现了多次的波折提升，而PM 所代表的曲线每次波折后会出现一段时间的停滞，这是由于PM 采用固定的进化策略，使得探索能力较强的种群发现了新的有效基因却没有能力对其重组，反而不断破坏新基因和原有的遗传模式；
而开发能力较强的种群虽然能够重组有效基因产生新的遗传模式，但该种群对搜索空间的勘探能力较弱，种群若长时间未发现新的有效基因会陷入停滞状态；
PM 这种矛盾的进化方式较难控制种群多样性和收敛速度的有效平衡。而IPM中每个种群只需负责单一进化功能，不同种群之间相互协作，通过这样的方式减缓了PM 进化过程中出现的矛盾，增强了算法的寻优能力，有效控制了GA收敛速度和种群多样性之间的平衡。

1.3 最优权动态控制学习机制

1.3.1 学习机制基本概念

定义1设H={H1,H2,…,Hm} 为所有种群的集合，种群的个数设为M，每个种群内染色体数目为N。

定义2（年龄与超龄）对于任意种群Hm存在∀xi∈Hm，都有xig.age表示染色体xi在g代的年龄，对于任意染色体xi，其初始年龄为0，年龄更新公式（1）如下：

Fig.2 Comparison of performance of parallel mechanism图2 并行机制性能对比

其中，i=1～N，α表示控制参数（取值范围为0～1），Hmg.ave表示Hm在第g代的平均适应度，xi.fit表示染色体xi的适应度值。若染色体长期低于种群平均适应度，其年龄就较大，表明该染色体“进化潜能”较差，当染色体年龄超过规定年限life时，成为超龄个体，在后续进化中会被淘汰。Hm.old表示Hm中超龄个体的数目，即群体内年龄大于规定年限染色体的数目。

定义3（优秀率）对于任意种群Hm都有He表示Hm的优秀率（计算公式见1.3.4 小节），优秀个体的数目r=He×N，N为种群大小，即将Hm中适应度最大的r个个体称为优秀个体。

定义4（基因模式与模式抽取）对于任意种群Hm，设种群任意两个染色体分别为x={x1,x2,…,xj}，y={y1,y2,…,yj}，xj,yj∈{0,1}，两个染色体通过公式z=获得的染色体称为模式，其中zj∈{0,1,*}，“*”代表基因模式中非确定位，种群基于当代所有优秀个体进行抽取得到的模式称为基因模式，Hmg.scheme表示Hm在第g代的基因模式。

定义5（模式学习）对于任意种群Hm，设种群的任意一个染色体为x={x1,x2,…,xj}，该染色体和基因模式Hmg.scheme={z1,z2,…,zj} 通过公式x⊙Hmg.scheme=进行模式学习得到一个新的染色体x.new。设待学习的染色体基因为x=1010110，基因模式Hmg.scheme=1*0100*，则经过学习后的x.new=1001000。

定义6（基因模式的权）对于任意种群Hm都有Hmg.weight表示Hmg.scheme的权值，权值越高，表示Hmg.scheme越“优良”，权值越低，表示Hmg.scheme越“劣质”（计算公式见1.3.8 小节）。

定义7（最优基因模式）对于任意种群Hm，都有Hm.bscheme表示该种群截止到当前代次最“优良”（权最高）的基因模式。

定义8（全局最优模式）在算法进化过程中，截止到当前代次所有种群最优秀（权最高）的基因模式为全局最优模式，全局最优模式用H.bscheme表示。

定义9（公共区域）粗粒度模型[19]的多种群GA需要定期进行数据迁移和交换，本文利用公共区域来接收上述并行机制内各种群共享的基因模式和最优个体。之后，公共区域会比较不同基因模式的优劣程度选出H.bscheme，同时筛选出全局最优个体。此外，公共区域还持续监听各个种群，将H.bscheme分配给发出群间学习请求的种群。

1.3.2 学习机制操作过程

学习机制包括群内学习（learning within populations，LWP）和群间学习（learning between populations，LBP）两种学习方式，分别由群内学习算子Pi和群间学习算子Po进行控制。在群内学习方式中，以模式学习作为主要学习操作，在群间学习方式中，以模式学习结合局部搜索策略作为主要学习操作。

（1）群内学习操作过程如下：

①计算种群的He。

②按照个体适应度大小降序选择r个染色体作为种群优秀个体。

③对优秀个体进行模式抽取得到Hmg.scheme，将得到的Hmg.scheme与该种群的Hm.bscheme的权值进行比较，更新Hm.bscheme。

④Pi控制群内染色体对Hm.bscheme进行学习，并及时更新适应度值与年龄。

⑤若达到规定进行信息迁移的代次，将Hm.bscheme和最优染色体传递到公共区域。

⑥公共区域将各种群传递过来的Hm.bscheme和最优染色体与已有的H.bscheme和全局最优个体进行比较，并更新H.bscheme和全局最优个体。

（2）群间学习操作过程如下：

①Po判断种群是否进行群间学习，确定进行群间学习的种群向公共区域发送学习请求。

②公共区域将H.bscheme发送给该种群。

③种群首先淘汰超龄个体，剩存染色体通过结合局部搜索策略的模式学习方法对H.bscheme进行学习，通过局部搜索策略新产生的染色体按适应度大小填补被淘汰超龄个体的空缺，并及时更新适应度值和年龄。

群内学习能够引导个体的进化方向，个体通过对优秀个体共性基因的学习使自身性状在较少遗传代次得到改善。但是若只进行群内学习，种群之间没有共享信息，就无法避免因学习共性基因而引起的多样性的减弱，容易陷入局部收敛。群间学习引导种群的进化方向，具有较多超龄个体的种群进化程度较低，说明该种群“进化潜力”较差，仅仅通过群内学习很难追赶上其他种群。因此不但要通过模式学习对H.bscheme的确定位进行学习，还要通过局部搜索策略对H.bscheme的非确定位的邻域进行探索开发以产生新的染色体，并使用新染色体取代超龄个体，新染色体通过对种群多样性的提高来提高种群的“进化潜能”，以期待该种群在后续进化中有较大的进步。若只进行群间学习，个体之间缺乏信息传递和反馈，会影响算法的收敛速度。因此需要同时采用两种方式对种群进行共同引导。具体来说，每次迭代时某种群中的每个个体分别以概率Pi进行群内学习，之后种群本身以概率Po进行群间学习，如此，发挥两种学习方式优势，提升算法的性能。

1.3.3 学习机制的理论研究

学习机制对种群内优秀个体提取共性基因组成基因模式，控制种群内其他个体对基因模式进行学习来改变自身。这种机制是否有理论上的支持？

拉马克进化学说（Lamarckian learning）主张环境条件的改变能引起生物发生适应环境的变异，即生物体通过后天学习获得性状改变，这种改变可以通过基因遗传给后代。即“用进废退”和“获得性遗传”。把上述思想应用在遗传算法中，则染色体需要在“环境”影响下获得性状改变并直接编码到染色体基因上[20]。在本文中，“环境”即学习机制，学习机制在模式定理思想（详见1.2.1 小节）引导下对种群抽取基因模式，作用于染色体，使其对基因模式进行学习，通过这样的方式使染色体获得性状上的改变，基于拉马克学习的学习机制可以将这种变化按照表现型空间与基因型空间的映射关系直接编码到个体的基因型。但是拉马克学习无法对这种变化进行有效的区分，搜索到更好的表现型就改变原有基因型，在增大算法寻优性能的同时，陷入局部收敛的可能性也在增大。而学习机制通过对种群的优秀个体进行模式抽取，获得的基因模式包含多个优秀个体的共性基因，因此基因模式可以进一步地定义为“由多个低阶有效模式组成的定长基因串”。个体通过学习基因模式获得优秀个体的共性基因，由于各染色体的基因组合不同，有的染色体会直接学习到有效遗传模式，也有染色体的基因与学习到的基因组成新的有效遗传模式，两种形式都有助于个体产生有益的性状变化。基因模式抽取的不是单独染色体的基因，而是多个优秀个体共有的基因，降低了种群因学习陷入局部收敛的风险。搜索到更高表现型的个体在选择操作作用下有更大概率被选入下一代，通过这样的方式来引导进化方向并将有效遗传模式继承下去。

1.3.4 自适应改变优秀率He的值

优秀率He负责每次迭代时筛选种群内优秀个体，通过对优秀个体进行模式抽取得到的基因模式来引导种群进化方向。文献[15]采用线性的方式（详见该文）计算He，使得He的值在种群平均适应度随迭代次数而增加时将越来越高，高数值He意味着优秀个体的数目较多，在此基础上进行模式抽取获得的基因模式将充满非确定位，使基因模式失去作用。因此，为了更好地发挥优秀率在学习机制不同时期的作用，避免基因模式在算法进化中后期充满非确定位，本文提出了一种根据进化代数自适应控制优秀率值的选取计算式（2）：

式中，He1是最小优秀概率，He2是最大优秀概率，g是当前进化代数，G是总进化代数。

图3 中，虚线代表遵循线性变换的文献[15]中的He，实线表示遵循式（2）的He的变化规律。文献[15]所提出的优秀率计算式是基于线性的改变，本文引入sin 函数可以起到非线性地自适应改变优秀率的作用，使He的数值更加符合算法的进化现状，使种群能够更好地选取优秀个体。具体来说，算法开始时，实线相比同时期的虚线有更高的优秀率值，这是因为算法进化初期，种群平均适应度较低，优秀个体内包含较多劣质基因，为避免劣质基因混入基因模式，式（2）在进化前期自适应地提高He的值，旨在增加优秀个体数量，对较多优秀个体进行模式抽取会减小劣质基因混入基因模式的概率。随着算法进入中后期，优秀个体基因之间相似度比较高，为避免真正的优秀基因被较差优秀个体的劣质基因干扰，实线随着进化代数增加而提升的速度比同时期的虚线缓慢，这样能够保证只有真正优秀的基因才被抽取到基因模式中，还可以避免算法中后期基因模式充满非确定位的现象，使基因模式在算法中后期也能够引导进化方向。

Fig.3 Adaptive curve of excellent rate values图3 优秀率自适应曲线

1.3.5 自适应改变群内学习算子Pi的值

群内学习算子Pi控制种群内染色体对Hm.bscheme进行群内学习操作。文献[15]计算Pi时未充分考虑种群进化情况，随着种群平均适应度的增长，群内学习频率逐渐升高，种群极易陷入“早熟”收敛。在本文中，计算Pi不但要考虑进化的时期，还要考虑种群本身进化程度。算法前期，种群内个体质量普遍较差，应通过增大Pi加强对种群的引导进化，随着算法的进行，应逐渐降低Pi来保持种群多样性，以提升收敛到最优解的能力。此外，还要考虑种群本身进化情况，适应度较低的种群更应取较大数值的Pi来加强引导，适应度较高的种群为了保持种群多样性，避免发生“早熟”收敛的现象，加快收敛速度，应该适当减小Pi。综合以上几点，本文设计了一种自适应动态控制的群内学习算子：

式中，Pi1是最小群内学习概率；
Pi2是最大群内学习概率；
g是当前进化代数；
G是总进化代数；
Hm.ave为种群Hm平均适应度值；
Hm.best为种群Hm最优适应度值。

1.3.6 自适应改变群间学习算子Po的值

群间学习算子Po控制种群进行群间学习操作，由定义2 可知，如果染色体的适应度在进化过程中长期处于较低状态，则该染色体的年龄会比较大，说明该染色体“进化潜能”较差，此时需要淘汰超龄个体并以新染色体补充超龄个体的空缺，新染色体的加入能够提升种群多样性。文献[15]计算Po时未充分考虑超龄个体的影响，使得种群进行群间学习时可能出现淘汰超龄个体过多的情况而造成算法不稳定或出现无超龄个体的情况而使群间学习无效。计算Po应当首要考虑群内超龄个体的数目，种群内超龄个体较多时，说明该种群内染色体的“进化潜能”较差，应当加大Po淘汰超龄个体，种群内超龄个体少时，说明该种群内染色体有较大“进化潜能”，该种群应当以群内学习为主，因此要减少Po。此外，还要考虑种群相对于其他种群的进化情况，平均适应度较低的种群更应该进行群间学习，以便追赶其他种群。综合以上几点，本文提出了根据种群内超龄个体数目以及种群进化情况自适应调节群间学习概率的计算式（4）：

式中,Po1是最小群间学习概率；
Po2是最大群间学习概率；
g是当前进化代数；
G是总进化代数；
Hm.old表示种群内超龄个体数目；
N表示种群内染色体总数目；
max(Hm.ave) 为所有种群中最大平均适应度值；
Hm.ave为当前种群平均适应度值；
min(Hm.ave)为所有种群中最小平均适应度值。

从式（4）中可以看出种群内超龄个体的数量决定了Po的大小，当超龄个体的数目较少时，Po值也较小，随着迭代的进行，种群内超龄个体的数目不断增多，Po值也逐渐增大，超龄个体被淘汰的几率也逐渐增大。这样，每次进行群间学习时，种群内的超龄个体能够保持在一定的数目，避免了种群进行学习时群内没有超龄个体或者超龄个体过多的情况，保证了种群进化的稳定性。最后，引入余弦函数非线性控制不同种群的学习概率，能够使种群的学习更加平滑，保持种群进化时的稳定性。具体来说，对于种群平均适应度值处于[min(Hm.ave),(max(Hm.ave)-min(Hm.ave))/2]的种群，该种群更应该追赶其他种群，因此有较大的Po值；
对于种群平均适应度值处于[(max(Hm.ave)-min(Hm.ave))/2,(max(Hm.ave)+min(Hm.ave))/2]的种群，该种群本身基因质量比较好，产生更好结果的可能性更大，因此小幅度增加该类种群的Po值；
其余种群与上述区间的种群相比有更大的平均适应度，说明这类种群有较好的“进化潜能”，应当以群内学习为主，因此取较小的Po。通过非线性地改变不同质量的种群学习比重，使群间学习能更好地发挥引导种群进化方向和加强局部搜索能力的作用。

超龄个体经历过多代的进化，虽然适应度较低，但也代表着解空间内与其相邻的可能解所在区域的信息。文献[15]采用随机产生新染色体的方法取代超龄个体，该方法的缺点一方面是由于新产生的个体往往表现比较劣质，在一定程度上会减缓算法的收敛速度；
另一方面是超龄个体所代表的解空间信息会直接消失。本文采用1.3.7 小节所表述的局部搜索策略对超龄个体进行信息挖掘，并以适应度作为质量准则来评价这些信息的价值，具有高价值的个体往往也具有更高的质量。从另一角度来说，这类个体也具有一定的“进化潜能”。局部搜索策略对这类个体进行了保留，对没有价值的个体进行了淘汰，通过这样的方式避免了超龄个体所代表的有效信息的缺失，同时还对这一有效信息进行了进一步的挖掘，有希望得到更优秀的个体。

1.3.7 一种新型局部搜索策略——分裂爬山法

GA 在迭代进化过程中，总是贪心选择适应度大的个体，导致GA 容易陷入局部最优，无法收敛到全局最优解。为此，有国内外学者引入梯度法[21]、爬山法[5]、列表寻优法[22]等优化方法作为局部搜索策略，加强GA 的局部搜索能力。本文在前人研究基础上，提出一种新的局部搜索策略，在染色体对基因模式的确定位进行学习时，该策略能够对其非确定位进行局部细搜，通过这种局部搜索策略，染色体能够在允许的邻域内搜索到适应度更高的个体。

设H.bscheme=10*10*011，待学习的个体为x1=011001011，首先是x1的第一个和第二个基因对H.bscheme的相应位置基因进行学习，x1的第一个和第二个基因位置变为1 和0，当在第三个基因位置碰到H.bscheme的非确定位的时候，通过分裂算子来判定是否进行分裂，确定进行分裂后，以该非确定位基因为核心进行分裂，非确定位基因同时取0、1 两个基因，并结合之前学习过的基因进行分裂产生两个新的染色体，分裂后的第一个染色体x2=100001011，第二个染色体x3=101001011，分裂后对父染色体x1的第三个基因位进行取反操作（将0 基因置为1，1 基因置为0），然后父染色体x1继续进行学习和分裂操作，直至学习到H.bscheme的最后一个基因位。

图4 描绘了分裂爬山法作用于染色体在基因型空间和表现型空间的影响。由图中基因型空间可以看出x1在第三个基因位进行分裂产生了x2和x3两个染色体，在表现型空间可以看到x2和x3在x1的基础上进行适应度的攀爬，通过这样的方式实现了对x1邻域空间的探索，弥补GA 局部搜索能力弱的缺陷，实现了探索新适应度的目的。而在群间学习中，该局部搜索策略分裂产生的新染色体按适应度值排列后用于补充被淘汰超龄个体的空缺，新染色体比“进化潜能”普遍较差的超龄个体更有机会进化为优良个体。此外，通过学习遍历H.bscheme后，第一个非确定位和最后一个非确定位之间有多种组合，因此新染色体之间基因相似程度并不高，新染色体补足超龄个体的空缺后，能够丰富种群的多样性。

1.3.8 基因模式的权

学习机制通过群内学习和群间学习共同引导种群进化，因此会有概率出现下一代基因模式不如上一代基因模式“优秀”的情况。

本文提出一种评价函数，通过该函数对基因模式进行赋权操作，算法以权值来比较不同基因模式的优劣程度，选出群内最优基因模式Hm.bscheme和全局最优模式H.bscheme。基因模式的权计算公式如下：

Fig.4 Effect of split mountain climbing method on new chromosomes图4 分裂爬山法对新染色体的影响

式中，Hm.best为种群最优秀个体适应度值；
fˉ是种群内除Hm.best剩余优秀个体平均适应度值；
g是当前进化代数；
G是总进化代数。

进化前期，种群平均适应度较低，群内大部分染色体“劣质”基因较多，应当加强群体内最优秀个体引导种群进化方向的力度，减弱其他较差优秀个体的影响，因此在进化前期提高Hm.best的权重，降低fˉ的权重。随着迭代的进行，种群平均适应度逐渐升高，群体内最优秀个体和其他优秀个体相似度也逐渐变大，考虑到最优秀个体有可能是局部最优解，为了避免种群进化方向被局部最优解错误引导，应逐渐降低Hm.best的权重，提高fˉ的权重。

1.4 OWLMGA 算法流程

算法流程如图5 所示。

算法执行流程如下：

（1）初始化控制参数和公共区域。

（2）多样本均匀分区种群初始化产生父种群，父种群自我复制生成子种群，子种群部署不同进化策略。

（3）各子种群按自身进化策略独立计算演化，进行遗传操作，更新个体适应度和年龄。

Fig.5 Flow chart of OWLMGA algorithm图5 OWLMGA 算法流程图

（4）各子种群将群体内优秀个体传递给同父种群实施保存策略的子种群。保存策略子种群对优秀个体进行发掘，保留优秀基因。

（5）对种群进行模式抽取获得基因模式，同时将基因模式和全局最优个体上传到公共区域。

（6）种群内个体通过Pi判定是否进行群内学习，否则转（7）。

（7）各子种群通过Po判定是否进行群间学习，否则转（8）。

（8）检查终止条件，满足转（9），否则转（4）。

（9）算法结束。

算法实施时可利用Matlab 的并行计算工具箱(parallel computing toolbox，PCT)进行并行运算，通过并行处理不同种群的进化，提升了算法的收敛速度，大幅度减少了算法解决问题的时间。

2.1 测试函数及对比算法

为验证本文提出的OWLMGA 算法性能，本节以12 个基准函数为对象进行仿真测试。f1～f6所代表的多峰值函数能够测验算法的开采能力及跳出局部最优的能力，f7～f12所代表的高维函数用于测试算法的勘探能力及收敛能力。本文选取标准多种群遗传算法（standard multi-population genetic algorithm，SMGA）、文献[5]提出的HGA（hybrid genetic algorithm）及文献[15]提出的PGABL（parallel genetic algorithm based on learning mechanism）作为对比算法，其中以SMGA验证OWLMGA 所改进的多种群并行机制的性能；
HGA 将多种群遗传算法与局部搜索策略混合增强了多种群遗传算法的局部搜索能力，以该算法验证OWLMGA 改进的局部搜索策略的有效性；
PGABL虽然使用了多种群并行机制，但各种群均使用了相同的交叉及变异参数，未能发挥多种群的优势，因此以该算法印证OWLMGA 的学习机制。测试函数如表2 所示，其中D是变量的维数。

2.2 仿真实验设置

为公平起见，SMGA、HGA、OWLMGA 均采用相同的参数，PGABL与原文保持一致。以上算法均采用二进制编码，适应度比例选择，单点交叉和多基因位变异。算法的控制参数如下：种群数目为4，每个种群染色体规模N均为50，染色体长度为40，算法迭代次数G为400。在SMGA中，pc1=0.70，pm1=0.10，pc2=0.50，pm2=0.30，pc3=0.85，pm3=0.05。在HGA 中，pc1=0.70，pm1=0.10，pc2=0.50，pm2=0.30，pc3=0.85，pm3=0.05。PGABL 中α=1，life=15，Pc=0.80，Pm=0.06。在OWLMGA 中，α=1，life=15，pc1=0.70，pm1=0.10，pc2=0.50，pm2=0.30，pc3=0.85，pm3=0.05，Pe1=0.10，Pe2=0.20，Pi1=0.30，Pi2=0.50，Po1=0.10，Po2=0.15，种群之间每隔15 代进行一次信息迁移和策略调整。

实验选取4 个指标评价算法的性能：（1）最优值，该指标反映了算法求解质量的好坏；
（2）最优收敛代数，该指标反映了算法求解最优值的速度，收敛代数越少，说明算法求解速度越快；
（3）平均收敛代数，该指标是算法多次运行的最优收敛代数的平均值，反映了算法求解最优值的稳定性；
（4）收敛次数及收敛率，收敛结果满足指定收敛精度时则认为收敛成功，收敛次数反映了算法求解最优值的成功率。收敛精度应综合考量函数维度及不同算法之间的性能来设定，以便更好区分算法之间的优劣。

2.3 仿真实验结果分析

表3 与表4 表示4 种算法各执行30 次后的优化测试结果。由测试结果可以看出，与SMGA、HGA、PGABL相比，OWLMGA 求解的函数最优值更接近函数的理论最优值，说明该算法求解精度高。OWLMGA的收敛次数接近实验总次数，其中对函数f1和f2求解的收敛次数与实验总次数一致，说明该算法的稳定性较好。由PGABL 求解f1结果可知，虽然收敛次数较低，但发生收敛的平均代数也较低，说明学习机制赋予了该算法较好的寻优能力，而PGABL 求解f2未发生满足收敛精度的收敛，这是因为f2的全局最优值被局部最优值包围，算法寻优过程中极易陷入局部极值点，说明该算法跳出局部最优能力较差。f3的数学特性类似于聚集的多个山峰，其每个顶峰都有一个局部最大值，会对算法造成干扰，该函数能够体现算法跳出局部极值及收敛能力，由最优迭代次数和收敛次数上可以看出，HGA 虽然收敛次数比SMGA 低，但最优迭代次数表现较好，这是因为HGA所使用的局部搜索策略提升了该算法的局部搜索能力，但也更易陷入局部最优。而OWLMGA 求解f3收敛次数较高，且收敛的平均迭代次数较低，说明该算法具有更好的跳出局部最优的能力和开发能力。在求解f7、f8高维函数时出现了两个极端，在本文30次实验中，PGABL 求解f7、f8未发生收敛，而SMGA和HGA 有较少收敛次数，说明并行机制提升了算法的全局寻优能力，OWLMGA 求解f7、f8具有较高的收敛率，说明OWLMGA 有更好的全局寻优能力和收敛能力。

Table 2 Test function表2 测试函数

图6 描绘了某次实验中SMGA、HGA、PGABL 与OWLMGA 对12 个测试函数求解的每代最优值的比较。由图6 中的（c）和（e）可以看出，相对于其他算法，OWLMGA 有更好的初始解，这是由于均匀分区初始化方法产生的种群，其群体内的个体能够较好地分布在解空间，该方法使得新产生的个体有几率位于函数峰值附近，因此算法有较好的初始解。

Table 3 Experimental results of function f1 to f6表3 f1～f6 函数实验结果

由图6 的（d）和（g）可以看出，SMGA、HGA 与OWLMGA 在求解高维函数的表现要优于PGABL，这是因为多种群并行机制使算法能够保持较好的多样性及全局寻优能力。而由图6中的（b）可知，SMGA虽然能够收敛到全局最优值，但是该算法的进化曲线出现了长时间水平停滞状态，这是由于该算法使用固定的进化策略导致群体内个体的进化效果较差，但是由于种群间个体迁移的作用使得该算法总能产生新的最优值，使得该算法在大部分情况下总是能够收敛。而OWLMGA 所对应的进化曲线更加“陡峭”，这是由于算法为每个种群部署不同的进化策略并定期调整进化策略，使得种群不必等待个体迁移，而是通过策略的调整便能进行自我开发产生新的最优解，保存策略保证了算法不会因更换策略而导致群体内优秀个体的基因被破坏，优秀个体之间重组产生更优秀解的可能性更大。由图6 中（e）和（h）可以看出，PGABL 算法对应的曲线在进化前期有比较“陡峭”的变化趋势，表明该算法在进化前期有较强的寻优能力，而在进化后期，该曲线出现了长时间的水平停滞状态，直到算法结束也没有接近全局最优值。这是由于PGABL 算法通过学习机制引导种群进化方向，该机制能够使算法在进化前期很快接近全局最优值，但是进化一段时间后，该算法的基因模式充满了不确定位，使基因模式失去了引导作用，从而使PGABL 算法沦落为SGA 算法，导致该算法在进化中后期经常陷入局部最优值，难以收敛到全局最优值。而从OWLMGA 算法的进化曲线可以看出，算法在整体进化的过程中能够保持较快的收敛速度，在较短的进化代数内就能够收敛到全局最优解。进化前期，进化曲线呈上升趋势快速接近全局最优解，表明该算法能够不断寻得新的最优值，而在算法后期，该算法出现多次短暂停滞并继续上升，表明该算法的学习机制在算法中后期不会出现学习机制失效的现象，仍能够发挥良好的作用。

Table 4 Experimental results of function f7 to f12表4 f7～f12 函数实验结果

2.4 计算复杂度分析

设种群数目为M，种群大小为N，染色体长度为L，采用随机初始化方法（random initialization method）产生多个种群，种群中任意个体的各基因位取1 或0的概率相等，即p=q=0.5，且各基因位之间是独立的。采用随机初始化方法的时间复杂度与种群规模有关。其中，M、N、L的数值越大，其计算的时间复杂度O(MNL)也就越大。而本文提出的初始化方法，虽然在大规模样本下以海明距离为标准选取个体，理论上计算的时间复杂度为O(iMNL)，其中，i为样本比例的系数。但各种群的大小未变，即初始化过程中不会用到超过种群大小或接近样本规模数量的个体，因此本文初始化方法的实际时间复杂度为O(MNL|iMNL)，涉及上述参数的计算对Matlab 软件来说计算量较小，且初始化行为只会发生一次，不存在多次迭代，因此不会较明显地影响运算速度。

数学模型的参数拟合决定了算法的时间复杂度[5]，OWLMGA 和对比算法（SMGA、HGA）采用了相同种群规模，OWLMGA 提出的并行机制通过种群分离控制不同进化功能，并且采用了改进的进化策略及调整种群的进化策略，但是上述行为不会使并行机制发生更深层的循环。而本文选取的另外两种对比算法（HGA、PGABL）分别采用了爬山法和线性的学习机制。前者对遗传算法的每代寻优结果使用爬山法进行局部搜索，在遗传算法的计算复杂度基础上多了爬山法的内层循环，使得该算法的时间复杂度较高。后者所使用的学习机制由于其参数设置的不合理使得学习机制在算法中后期的操作频率越来越高，增加了算法的时间复杂度。相比之下，OWLMGA 中的学习机制是作为并行机制的附加模块参与计算，与遗传操作处于同一迭代次数，近似为一种线性的关系，使得OWLMGA 基本运算的频度与SMGA 相同，没有过多地增加算法的时间复杂度。此外，学习机制中的局部搜索策略虽然对淘汰个体及其非确定位进行了循环搜索，但由于自适应的He与Po的存在，使得每代参与计算的非确定位基因的数目l和被淘汰个体的数目n小于染色体长度L和种群大小N，增加的计算量有限。

Fig.6 Comparison of optimum curves of algorithms图6 算法寻优曲线对比

通过介绍相关研究并结合分析遗传算法易“早熟”收敛及收敛速度慢等缺点产生的原因，指出现有方法的不足之处及缺陷。本文在前人研究基础上，秉着充分发挥遗传算法优点，克服遗传算法的不足的思路，提出了均匀分区的多种群初始化方法，改进的多种群并行机制及动态控制的学习机制，并融合上述改进形成一种新的混合遗传算法。

最后实验结果证明，改进的多种群并行机制和最优权动态控制学习机制天然具有良好的沟通能力，两种机制结合起来充分发挥了每个机制的优势，增强了算法的全局搜索能力和局部搜索能力。

猜你喜欢 适应度染色体种群 改进的自适应复制、交叉和突变遗传算法计算机仿真(2022年8期)2022-09-28山西省发现刺五加种群分布今日农业(2022年15期)2022-09-20多一条X染色体，寿命会更长科学之谜(2019年3期)2019-03-28为什么男性要有一条X染色体？科学之谜(2018年8期)2018-09-29由种群增长率反向分析种群数量的变化中学生物学(2018年8期)2018-03-01启发式搜索算法进行乐曲编辑的基本原理分析当代旅游(2016年10期)2017-04-17真假三体的遗传题题型探析中学生理科应试(2016年4期)2016-11-19能忍的人寿命长恋爱婚姻家庭·养生版(2016年9期)2016-09-07基于人群搜索算法的上市公司的Z—Score模型财务预警研究财经理论与实践(2015年2期)2015-04-16种群增长率与增长速率的区别中学生物学(2008年6期)2008-08-29 相关关键词： 2017年快手上面最优美的古风歌曲推荐 2017年yy上最优美的古风歌曲推荐 最优美的句子都有哪些 学生最优发展教学模式的研究与实践 理财最优模式