混合遗传算法自适应策略研究

陈雄峰，曾霞霞，徐 戈1,

(1.福建省信息处理与智能控制重点实验室(闽江学院)， 福建 福州 350108；2.闽江学院计算机与控制工程学院， 福建 福州 350108)

0 引言

混合遗传算法因其结合了全局探索与局部搜索，可折中平衡二者的搜索能力，非常利于搜索复杂的解空间，能有效处理大规模NP难组合优化问题[1]。然而，混合遗传算法必须进行大量的适应值估算，且种群容易失去多样性，影响进化效率，所需的计算时间较长[1-2]。问题针对性设计和自适应策略是改进混合遗传算法性能的两个主要措施。它是利用问题领域先验知识增强算法的整体性能，然而人们对NP难问题内部结构的先验领域知识总是有限的，通过人工实验设置的参数往往无法使混合遗传算法达到满意的搜索效率，因此需要自适应策略。自适应策略利用搜索过程中获得的信息，通过自适应的机制和参数来控制算法的多个方面，如搜索强度、种群多样性等，使得搜索过程可动态适应问题解空间的适应值地貌特征，从而提高算法搜索效率。近十来年，自适应策略逐渐成为了混合遗传等启发式算法研究的最新趋势，其中参数和算子自适应策略是具有很好前景的重要研究方向[3]。

自适应策略主要包括局部搜索概率、局部搜索个体选择与强度和模因(meme)选择与搜索过程等方面[1-3]。局部搜索概率自适应旨在更好地分配基于种群的全局探索与基于个体的局部搜索的计算时间。局部搜索个体选择自适应则可增强获得高质量问题解的整体效率[1,4]。许多相关研究证实了局部搜索强度对搜索过程的性能有重大影响，很大程度上决定了搜索过程所需的计算时间，其主要自适应策略是将搜索强度与个体适应值或某种爬山启发式相关联[1,5]。模因(meme)是指体现个体特性的含有多个基因的基因片段。许多不同问题的研究阐述了模因作为混合遗传等启发式算法处理问题时计算表示的基本信息单元，被用作搜索过程的指南、规则、策略和先验知识等，会有效提升算法的问题求解能力[1,5-7]。其主要的自适应机制是基于超启发式策略[1-2,7]，即首先依据问题领域知识采用针对性策略确定一个模因集，然后在搜索过程的某个时刻，依据当前个体、搜索区域和模因的不同特点，自适应地选择不同形式的模因组合，最后应用模因组合逐步进行启发式搜索操作，如模因中两个符号交换位置、几个符号重新排序等，每一步获得的候选解采用不同的接受准则。

本文将自适应策略应用于全局探索与局部搜索过程、局部搜索个体选择与强度以及种群多样性等方面，并提出了单个交叉模因构造过程和候选解接受准则的自适应策略，使得混合遗传算法搜索过程可动态适应问题解空间的适应值地貌特征，协调分配全局探索和局部搜索的计算时间，提高搜索效率，在保证可获得同样高质量解的前提下，大幅减少运行时间。以超大规模集成电路(VLSI, very large scale integration)标准单元布局问题为测试实例，实验结果表明了这些自适应策略的有效性。

1 自适应策略

1.1 候选解搜索与接受

候选解的接受准则包括“全部” “好于” “好于或等于” “指数蒙特卡洛(Exponential Monte Carlo)”等[7]。不同的接受准则适用于不同特征的搜索区域。“全部”接受准则利于扩大搜索区域，但不能保证寻获更好的候选解，应与其他接受准则结合使用。“好于”和“好于或等于”接受准则寻找更好候选解的效率高，但仅在可行解总是连续的搜索区域才能体现其优势。“指数蒙特卡洛”接受准则可以小概率接受不好的候选解，适用于可行解不总是连续的搜索区域[2,4-7]。

本文算法全局探索和局部搜索过程所使用的候选解自适应接受策略包括以下两个方面。

1.1.1 候选解搜索

应用模因集逐步搜索，以 “当前步及其之前所有逐步搜索的结果” 为候选解即“全部”接受准则。如此可动态自适应解空间的适应值地貌特征。

1.1.2 候选解接受

当“解空间可行解不总是连续的”时，以“指数蒙特卡洛”准则接受候选解为当前解，否则以“好于”准则接受候选解为当前解。如此可自适应解空间的可行解特征。

1.2 交叉全局探索

基于进化视角，模因是体现个体特性的含有多个基因的基因片段。基于算法视角，模因是问题求解时用于表示特定领域知识的信息单元[2]。在混合遗传等启发式算法中将模因用作搜索过程操作对象的指南，将具有良好的启发效果。模因选择与构造是针对性和自适应策略的基础之一[1,6]。为使得交叉探索过程动态自适应解空间的地貌特征，本文算法在针对性选择基因的基础上，让单个模因的构成动态自适应于其当时所影响的基因集合，让单个模因所包含基因的个数(下文称为模因大小)动态自适应于其当时所影响基因集合的变化情况和一个问题的基因总个数。交叉全局探索过程动态自适应策略包括以下3个方面。

1.2.1 单个模因大小

单个模因大小与问题基因总个数|的成比例关系。

1.2.2 单个模因构造

在双亲交叉过程中动态构造模因，在双亲个体交叉时所能影响的范围内选择其构成基因。

1.2.3 交叉全局探索过程

第一阶段为模因集组成，依据“1.单个模因大小”和“2.单个模因构成”自适应策略构造交叉的单个模因，而后采用简单随机方法组成模因集，模因集大小可通过简单实验确定；第二阶段为候选解搜索与接受，即对第一阶段已组成的模因集，双亲交叉时使用“1.1.2候选解搜索与接受”自适应策略获得当前解。

1.3 局部搜索

局部搜索个体选择与强度方面使用自适应策略，可更好分配全局探索与局部搜索的计算时间。交替使用不同类型的局部搜索，适当控制每一步局部搜索的邻域范围，都是利于跳出局部优解区域的有效措施。本文算法交替使用单个基因局部搜索和染色体窗口局部搜索。局部搜索过程动态自适应策略包括以下4个方面。

1.3.1 个体选择

问题解个体质量越高，局部搜索寻获高质量候选解的可能性越大，计算时间的价值体现得越充分，因此局部搜索个体选择范围和搜索强度通常自适应于体现个体质量水平的适应值[1]。对于超大规模问题，通常采用小规模种群(5～10个)，局部搜索个体选择自适应策略可相对简约。本文算法将局部搜索个体选择范围简单地划分为“没有”、“当前最好个体”和“全部个体”3种情况，而后与当前最好个体的适应值(记为fitness(sbest))动态自适应，具体为：1) 当fitness(sbest)

1.3.2 单个模因选择

遗传算法中一条染色体编码对应一个问题解个体，染色色编码上基因符号位置变化会直接或间接影响问题解个体质量。让一个基因所包含的符号在染色体编码上聚拢，或对染色体编码上窗口(若干连续基因符号)进行最佳排列，以优化问题解个体质量为目的调整这些基因符号的位置，对局部搜索过程具有良好的启发引导作用。同时考虑限制个体邻域范围的需要，本文算法将“染色体编码上符号不连续单个基因”和“染色体编码上4～5个连续符号窗口”作为局部搜索的一个模因。

1.3.3 局部搜索过程

第一阶段，如上“1.3.1个体选择”选择局部搜索个体，如上“1.3.2单个模因选择”选择单个模因，随机选择多个模因组成模因集，模因集大小可通过简单实验确定；第二阶段为候选解搜索与接受，即对第一阶段已组成的模因集，局部搜索时使用“1.1候选解搜索与接受”自适应策略获得当前解。

1.3.4 局部搜索强度

分别使用两种策略：1)自适应于当时获得更好邻域解个体的可能性，即重复进行上述局部搜索，直到3次未能获得更好的邻域解个体。2)自适应于当前解个体si的适应值fitness (si)大小。

1.4 种群多样性保持

为了避免陷入不好的局部优解区域，更恰当地跳出局部优解区域，在全局探索过程保持种群个体具有适当的多样性是设计基于种群寻优算法必须考虑的一个重要因素。多样性的度量方法主要包括基于适应值和基于距离两种[1]。实验观察，由于计算时间过长，基于距离的度量方法并不适用于大规模组合优化问题。本文算法使用基于适应值，以动态替换种群个体作为保持种群多样性的主要自适应策略，具体描述为：当所有“个体适应值fitness(si)/ 当前最好个体适应值fitness(sbest)>99.5%”时，用新的初始个体替换除当前最好个体之外的其他所有个体。

2 算法基本框架

使用自适应策略的混合遗传算法基本框架如算法1所述，其中：自适应策略如上第1节所述，Np、PGS、PLS、PGENorWIN和“算法终止条件”的可通过简单实验确定，具体设定值见“3、实验结果与分析”。

算法1:使用自适应策略的混合遗传算法基本框架

输入:求解问题所需信息Problem(info).

输出:近优解s*.

begin

生成初始种群{s[0], s[1], …, s[Np-1]};

repeat

随机生成0, 1, …, Np-1的一个排列φ;

for ( i = 0 to Np-1)

选择双亲s[φi], s[φ( i + 1 ) % Np];

以概率PGS进行自适应“交叉全局搜索”，生成孩子个体sc，记为sc=Adaptive Crosser_GS(s[φ( i + 1 ) % Np], s[φi]);

以“好于”准则接受s[φi]=sc或s[φi];

if(个体 s[φi]同时满足局部搜索概率PLS和“个体选择”自适应策略)

以概率PGENorWIN交替进行自适应“局部搜索”，生成邻域个体sn，记为sn=AdaptiveGen_LS (s[φi])或AdaptiveWin _LS (s[φi]);

以“候选解搜索与接受”自适应策略接受s[φi]= sn或s[φi];

end if

end for

使用“种群多样性保持”自适应策略;

until 满足“算法终止条件”;

输出近优解s*=种群中当前最好个体;

end

3 实验结果与分析

算法以超大规模集成电路标准单元布局问题作为测试实例，其问题描述、解表示、优化目标如文[8]所述。算法优化目标是一个布局的半周长HPWL(Half-Perimeter WireLength)， HPWL越小表示其布局质量越高[8-12]。阵列布局可行解总是连续的，非阵列布局可行解不总是连续的，二者分别使用标准测试电路实例Peko suite3[13]、 ISPD04 ibm[14]，ISPD04与Peko suite3规模完全相同。

算法基本框架中种群规模Np=5，交叉全局搜索概率PGS=0.6，局部搜索概率PLS=0.6，单个基因和染色体窗口交替局部搜索概率PGENorWIN=0.15，动态替换种群个体的自适应判断条件为“所有fitness(si)/ fitness(sbest)>99.5%”，算法结束条件为“20 min(阵列布局)或40 min(非阵列布局)时间间隔HPWL进化减小量小于0.01×106”。

3.1 自适应策略整体有效性

所有测试电路实例均可获得有效实验结果，实验结果为5次运行算法获得结果的平均值，限于篇幅仅列出不同规模代表电路实例的测试结果，如表1所列。其中，“运行时间减少”是指获得相同HPWL平均值情况下，与全部不用第1节所述主要自适应策略而其他要素相同的算法相比的结果。全部不用第1节所述主要自适应策略时，相应替代方法为： 1)1.1小节所述接受准则都使用“好于”；2)1.2小节所述单个模因固定为交叉前随机选定的平均大小的线网即基因；3)1.3小节所述个体选择策略保持不变，局部搜索强度分别固定为1次或6个窗口；4)1.4小节所述种群替换条件固定为“每隔3 000代”。测试结果表明，对可行解是否总是连续的解空间，算法所使用的自适应策略都是有效的。

表1 自适应策略整体有效性Tab.1 The overall effectiveness of the adaptive strategies

3.2 主要自适应策略各自作用

为验证各个主要自适应策略的有效性和作用大小，分别单独不用第1节所述主要自适应策略，下文分别简称不用“接受”、 不用“模因”、 不用“强度”、不用“替换”，与此同时其他自适应策略、参数保持不变，执行算法直到获得与表1“本文算法HPWL”相同的布局结果。选用不同规模代表电路实例Peko/ibm01、05、10、15、18进行测试，相应运行时间减少程度的计算方法与表1“运行时间减少”相同，简称相应“运行时间减少”。测试结果如表2所列，其中“⊿RRT”是相应“运行时间减少”与表1“运行时间减少”之间的差距，即“⊿RRT”=(表1“运行时间减少”)-(相应“运行时间减少”)，“⊿RRT”大小体现了相应自适应策略作用的大小。因为不用“接受”的替代方法与对阵列布局的接受准则相同，此时“⊿RRT”为0，所以表2的“阵列”部分没有列举不用“接受”的情况。

测试结果表明，候选解接受自适应策略仅对可行解不总是连续的解空间有作用；对可行解是否总是连续的解空间，单个模因构造自适应策略都有较大作用；对可行解总是连续的解空间，局部搜索强度和种群多样性保持自适应策略的作用相对更大。

表2 主要自适应策略各自作用Tab.2 The respective effect of the major adaptive strategies

4 结语

针对性设计使得混合遗传算法可处理超大规模组合优化问题，在此基础上使用适应性策略可大幅减少运行时间，是提高混合遗传算法整体性能的有效途径。实验结果证实了本文提出和采用自适应策略的有效性，其中，本文提出的交叉全局探索单个模因构造和候选解接受自适应策略具有显著的作用，采用的局部搜索个体选择与强度自适应策略也具有重要作用。后续研究的重点将是交叉全局探索和局部搜索的自适应交互策略，进一步协调全局探索和局部搜索的能力，从而进一步提高算法的整体性能。