基于机器学习的多策略并行遗传算法

张 韵，钟慧超，张春江，李新宇+，丛建臣

(1.华中科技大学 数字制造装备与技术国家重点实验室，湖北 武汉 430074;2.山东理工大学 机械工程学院，山东 淄博 255000)

0 引言

在自然界生物遗传和进化中，适应自然环境的基因和形状大概率得以存留，使得生物朝着适应生存环境的方向不断进化。20世纪70年代，Holland教授受遗传学原理的启发，提出了遗传算法(Genetic Algorithm, GA)[1]。遗传算法是借鉴生物遗传机制和自然选择的随机经典启发式算法。算法中，使用染色体代表所需求解问题的一个解，通过对种群、染色体的操作(选择、交叉、变异)，模拟遗传和自然选择的整个过程[2]。

遗传算法具有较强的全局搜索能力和可拓展性，相关的研究和应用较多。但遗传算法也存在一些缺陷，如局部搜索能力不强、随机性较大等。针对这些不足，近年来有很多相关研究，以提升遗传算法的性能和应用价值[3-4]。WANG等[5]针对交叉操作和变异操作对遗失解影响较大的问题，设计了一种参数自适应方法，由此提出一种基于激素调节的自适应遗传算法;WANG等[6]针对遗传算法早熟、精度差等问题，将正交设计方法用于优化遗传算法参数，并将所改进的算法用于作业车间调度问题;OSABA等[7]提出一种自适应多策略交叉方法，交叉概率由前面几代的搜索经验和迭代次数确定;ISMKHAN等[8]提出一种变异概率控制方法，该方法是在遗传算法处于特定状态时调整变异概率，在多峰连续函数优化问题中表现较好;ZHANG等[9]提出一种基于聚类的自适应交叉概率和变异概率方法，使用K均值聚类算法分析解空间的分散状况，由此自适应改变交叉概率和变异概率，并用于多维函数优化问题;JEBARI等[10]提出一种动态优化算法，使用模糊聚类方法来寻找未被探索的解空间，引导部分个体向未被探索的空间进行探索，增强算法搜索能力;SUN等[11]针对算法早熟导致种群多样性减小的问题，对相邻代的种群多样性进行限定，根据种群多样性评估结果和个体适应度评估结果调整交叉概率和变异概率，该算法可以保持种群多样性，保证全局搜索能力的稳定性。

为提高遗传算法的鲁棒性，以上研究使用多种方法对其进行了改进。然而，上述方法虽然利用种群特征对参数进行了调整或实现自适应优化，但考虑不够全面，如并没有充分利用之前迭代过程中的信息，大多只考虑本代的特征，使得参数自适应过程与实际规律并不具有很强的相关性。而强化学习能对以往数据进行学习，利用过去的经验指导算法进行决策。此外，考虑并行计算可以减少算法运行时间，但一般的并行策略易忽略种群特征，受以上研究中使用K均值聚类算法获得种群分布的启发，可使用K均值聚类算法对种群进行聚类，使相似个体被分配到不同子种群，提高子种群多样性。

基于以上分析，本文提出一种基于机器学习的改进遗传算法，实现并行和多策略进化。一方面，使用强化学习对参数进行学习和调整，使参数随种群进化合理变化；另一方面，设计多种群并行搜索策略，使用K均值聚类算法提高子种群的种群多样性和均匀性，并设计了种群通信机制，充分挖掘多种群的优势。

1 基于机器学习的多策略并行遗传算法

1.1 基于强化学习的参数调整策略

在机器学习中，强化学习较为特殊，它通过与环境的反复交互和试错，根据获得的反馈不断对决策进行优化[12]。近年来，在围棋、工业自动化、数据科学等领域，强化学习得到了较多应用，取得了较好的效果，是实现智能系统的重要技术之一[13-15]。其原理是：智能体记录不同环境下做出不同决策的趋势，在作出某一决策后，如果得到环境奖励，则智能体会增加该状态下做出这一决策的趋势；相反地，如果得到环境的惩罚，则智能体会降低该状态下作出这一决策的趋势。经过反复学习，智能体能达到可以做出累积奖励最大决策的状态[16]。

Q-Learning算法是一种经典的强化学习算法，属于异步策略学习(off-policy learning)，其数据生成策略和评估策略不相同，数据生成策略是ε-greedy策略，评估策略是贪婪策略。Q-Learning算法值的更新使用Q函数实现，Q-Table用来存储Q值，式(1)为算法更新原理，式(2)用于计算决策的动作趋势值[17]。

Q(st+1,at)-Q(st,at)];

(1)

Qπ(s,a)=Eπ{Rt|st=s,at=a}

(2)

基本遗传算法应用于具体问题时，参数往往需要多次试探或根据经验给定，因此参数设置与遗传算法的泛化能力关系密切。为了使参数变化符合种群进化需求，利用强化学习与种群环境进行交互，针对遗传算法中的交叉概率，设计了一种基于Q-learning算法参数调整策略。

Q-learning算法设置：

(1)状态空间

状态空间定义为两位小数表示的交叉概率数值，取值范围为[0.70,1.00)。

(2)动作空间

动作空间设置为交叉概率的减小、不变、增大3种，分别由{-1,0,1}表示，动作幅值设置为0.01。因此，Q-Table的规模为300×3。下一状态的交叉概率为：

st+1=st+0.01×action。

(3)

(3)奖励机制

奖励机制的主要依据是种群的平均适应度和最佳适应度两个指标，分为4种情况：①平均适应度增大;②最佳适应度增大;③两者都增大;④其他。每种情况的奖惩力度不同。

(4)贪婪策略

利用ε-greedy策略使算法具有探索现有经验之外的规律的能力，能在一定程度上避免算法陷入早熟。ε为接受现有经验最优解的概率。

(5)参数调整策略的流程

首先，初始化强化学习参数，包括学习率α、折扣率γ、探索率ε。然后，强化学习根据当前状态，选择动作空间中Q值最大的动作，或根据贪婪策略进行探索，对当前交叉概率进行调整。最后，完成本次种群迭代后，根据反馈信号和奖励机制更新Q-Table，即完成一次决策和自学习。通过不同环境下的反复训练，使模型不断学习经验，提高参数调整的准确程度。基于强化学习的参数调整策略的流程如图1所示。

1.2 基于K均值聚类的并行策略

引入并行优化能显著加快算法运行速度，减少运行时间，特别是在多核处理器上，并行计算能充分利用计算资源。然而，如果设计不合理，即使是在多核处理器上，并行算法也可能因为资源争夺等原因导致效果不如普通算法。遗传算法的并行策略中，子种群的划分至关重要，子种群中各个个体的分散程度影响算法的疏散性和全局搜索能力，会对收敛速度、解的质量均产生影响。以往研究中，子种群划分往往是随机的，难以保证算法整体的疏散性。

聚类是无监督学习的一种，K均值聚类算法是典型的分割聚类算法。K均值聚类算法基于数据之间的相似度，将数据划分到不同的簇[18]。K均值聚类算法的原理[19]是：首先将数据样本分为K组，并随机指定K个聚类中心，根据相似度计算方法，逐个计算每个点到各聚类中心的距离，将其分配到最近的聚类中心所在簇，簇中聚类中心会被重新指定。通过反复迭代更新聚类中心，直到其不再变化，距离误差平方和局部最小，即完成聚类。

为设计有效的并行策略、充分发挥并行算法同步优化的优势，本文使用K均值聚类算法来划分子种群。在初始化种群形成后，用K均值算法对所有个体进行聚类，再将同类个体均匀划分，形成多个内部个体具有较大差异性的子种群，以提高子种群在解空间内的分散程度，提升算法疏散性和全局搜索能力。

基于K均值聚类的并行策略流程如图2所示，具体过程如下：

(1)定义数据 种群初始化后的每条染色体都作为一条数据，数据集大小等于种群规模。

(2)聚类 起始随机确定K个聚类中心，计算数据与所有聚类中心的欧式距离，将该数据划分给最近的聚类中心所在簇。每次分配一条数据后重新计算聚类中心，直到满足终止条件，即可完成聚类。

(3)调整 按顺序排列所有簇，得到{C(1),C(2),…,C(k)}，记调整后的数据集为Pc。

(4)划分子种群 将Pc中的个体分为多个子种群，其中，第n个子种群由{Pc[1][n],Pc[2][n],Pc[3][n],…,Pc[k][n]}组成。

1.3 基于机器学习的多策略并行遗传算法

使用上述两种策略对遗传算法进行改进，提出一种基于机器学习的多策略并行遗传算法。首先，利用并行优化加速算法进化过程，引入K均值聚类对种群进行划分，保证子种群的种群多样性和均匀性；同时，在进化过程中，使子种群间相互通信，加快算法收敛。最后，使用基于强化学习的参数调整策略，实现遗传算法交叉概率的自学习，使交叉概率根据经验适应进化过程。算法流程如图3所示。

(4)

该段染色体的长度满足：

(5)

染色体过长会对计算速度造成影响，因此对该段染色体长度向上取整，如式(6)所示，ceil(x)表示大于x的最小整数。

(6)

一条染色体的总长度len=Σleni。

(2)解码。解码是由染色体得到所表示的各自变量的值的过程。染色体中对应vi取值的一段二进制序列为Bvi，将二进制数转换为十进制数Dvi，则vi取值的计算如下：

(7)

例如，对于函数f(v1,v2)，其中v1∈[0,2]，v2∈[2,6]，设精度ε=0.01。编码时，先作对称调整，mean_v1=1，mean_v2=4，range_vi=1，range_v2=2，对称调整后的区间分别为v1∈[-1,1],v2∈[-2,2]。由式(6)可得，len1=8，len2=9。对于v1=1.26，v2=3.48，Dv1=33，Dv2=-66.3按照二进制编码，v1的二进制编码表示为Bv1=00 011 010，v2的二进制编码表示为Bv2=100 110 100。解码时，按式(7)即可反解得v1和v2的真实取值。

(3)种群初始化。采用随机初始化，种群规模为N。

(4)子种群划分。采用前述的基于K均值聚类的并行策略进行子种群划分。其中，距离计算采用欧氏距离，如式(8)所示。

d(x,y)=

(8)

(5)适应度评估与选择。由所有自变量和函数方程可以计算出函数值，适应度设置为函数值的倒数。个体i表示为pi，染色体解码出的函数值为obj(·)，则适应度函数为：

(9)

选择操作采用“轮盘赌法”与精英保留策略结合。个体i被选择的概率如式(10)所示。

(10)

适应能力越强的个体，存留的机会越大。为加速种群进化，并保证较优个体不在其他过程中丧失，使用精英保留策略，用本代适应度最高的个体替换子代中适应度最差的个体。

(6)交叉。交叉父代的选择规则为：对1～N的有序序列进行随机排序，表示N个个体的随机排列，记为序列A；然后生成长度为N、大小在区间[0,1]内的随机数序列，记为序列B。序列A与序列B位置一一对应，若序列B某一位置的值比当前交叉率小，则序列A中该位置的个体与相邻的下一个位置的个体交叉。

采用高效的PMX(partial-mapped crossover)作为交叉算子，如图4所示。二进制编码的染色体的交叉过程为：首先随机确定两个基因作为交叉起止位置；然后将两个父代染色体所选片段互换，完成交叉。

(7)基于强化学习的交叉概率自学习。使用前述基于强化学习的参数调整策略对交叉概率进行学习和决策。

(8)变异。采用随机单点变异，按照变异概率，选择随机点位，对基因值进行反转，即01或10。

(9)子种群通信机制。为了充分发挥并行优势，加快收敛速度，设计了子种群通信机制。按一定步数，将全局最优个体替换其他子种群中的最差个体。

2 数值实验结果与分析

2.1 测试函数

本文选择了9个常用的测试函数，如式(11)～式(19)所示。前3个函数的目标是求解函数的最大值，后6个以最小值为目标。

xi∈[-5.12,5.12],i=1,2;

(11)

f(X)=1+x1sin(4πx1)-x2sin(4πx2+π),

xi∈[-1,1],i=1,2;

(12)

xi∈[-2.048,2.048],i=1,2;

(13)

x1∈[-15,5],x2∈[-3,3]

f*=0⟺X*=[-10,1]T;

(14)

(15)

f(X)=(x1+2x2-7)2+(2x1+x2-5)2,

xi∈[-10,10],i=1,2

f*=0⟺X*=[1,3]T;

(16)

f(X)=sin(x1+x2)+(x1-x2)2-1.5x1+

2.5x2+1,x1∈[-1.5,4],x2∈[-3,4]

f*=-1.913 3⟺X*

=[-0.547 19,-1.547 19]T;

(17)

f(X)=(x1-1)2+(x2-1)2-x1x2,

xi∈[-4,4]f*=-2⟺X*=[2,2]T;

(18)

f(X)=-cos(x1)cos(x2)exp(-(x1-π)2-

(x2-π)2),xi∈[-5,5],i=1,2

f*=-1⟺X*=[π,π]T。

(19)

2.2 参数设置

遗传算法的基本参数设置为：种群规模为100，最大进化代数为200，起始交叉概率为0.85，变异概率为0.05。基于强化学习的参数调整策略的参数设置为：学习率α=0.05，折扣率γ=0.9，ε-greedy中的选中概率ε=0.85，Q-Table更新周期为20步。基于K均值聚类的并行策略为：聚类中心数K=5，种群通讯机制更新周期为20步。解的精度设置为0.000 001。

2.3 实验结果与分析

实验结果如表1所示，其中GA是基本遗传算法，RLGA(reinforcement learning based genetic algorithm)是基于强化学习的参数调整策略的改进遗传算法，KPGA(K-mearns based parallel genetic algorithm)是基于K均值聚类的并行策略的改进遗传算法，MLGA(machine learning based genetic algorithm)是本文所提算法。4种算法中遗传算法的基本参数设置都相同，RLGA与MLGA中基于强化学习的参数调整策略的参数设置相同，KPGA与MLGA中基于K均值聚类的并行策略的参数设置相同。4种算法分别对每个测试函数运行10次。

表1 实验结果

表1中AVG表示10次结果的平均值，σ表示10次结果的总体标准差。由表1可见，对于9个测试函数，MLGA能获得全部的最好平均值，对大多数问题MLGA的标准差也是最小的，说明改进算法运行的稳定性较好。同时，RLGA与KPGA求解效果均远超GA，验证了两种改进策略是有效的。

为进一步展示算法的优越性，选取函数f1和函数f7的10次实验结果如图5所示。由图5可知，对于最大化问题f1，MLGA、RLGA、KPGA在大多数实验中能获得优于基本GA的解，且求解稳定性均在GA基础上有很大提升；对于最小化问题f7，MLGA每次运行都能获得接近最优值的解，RLGA、KPGA所求得的解略差于MLGA，但两者相对于基本GA都具有很大优势。由此验证了所提出的基于强化学习的参数调整策略、基于K均值聚类的并行策略的合理性，使用这些策略的MLGA具有更强的寻优能力和稳定性。

通过表1和图5的实验结果进一步对比分析两种策略，在9个测试函数中，KPGA在其中8个的表现优于RLGA，在函数f1和函数f7的10次测试中可看出，无论在解的优劣方面还是稳定性方面，KPGA都表现得比RLGA更好。因此，在这些问题上，基于K均值聚类的并行策略比基于强化学习的参数调整策略对遗传算法的改进效果更好。但是，基于强化学习的参数调整策略的强化学习模型会随着种群规模与迭代次数的增加而不断稳健，效果会进一步提升，因此该策略有较大的潜力应对更复杂的问题。MLGA结合两种策略的优势，求解效果和稳定性都比RLGA和KPGA好，具有较大的潜力。

在计算复杂度方面，基于强化学习的参数调整策略中使用的Q-Learning算法计算过程和Q-Table更新过程都比较简单，且每一步均只需要重新计算一次交叉率，每20步才更新一次Q-Table，并不会显著增大遗传算法的计算复杂度，且由上述实验结果中的RLGA相对于GA的求解效果可知该策略的有效性，该策略使用了较小的计算代价获得了较大的性能提升。而基于K均值聚类的并行策略每一步都需要多次对n个个体计算其与K个聚类中心的距离，因此具有一定的计算复杂度，但由于该策略是建立在并行计算的基础上的，有效减小了K均值聚类带来的计算负担。从以上实验结果中KPGA的表现可得出，该策略的应用较大地提升了遗传算法的性能，由此增加了一定的计算复杂度是值得的。

在算法参数方面，本文中遗传算法其他参数是根据实验效果和经验选定的，强化学习用来自适应调整交叉率，并证明了该思路的可行性，强化学习也可以用来调整算法中的其他参数，实现自适应，可进一步提升算法性能。强化学习的学习率α、折扣率γ、探索率ε以及K均值聚类的参数K是通过多次实验选定的，对算法的收敛有较大影响，但参数适应性较高，通过少量试验即可获得较好的参数。

3 结束语

本文提出一种基于机器学习的多策略并行遗传算法。一方面，利用并行计算思想提高算法效率，使用K均值聚类算法按照相似程度将种群划分为多个簇，然后将每个簇中的个体均匀分配到不同的子种群中，以保证子种群多样性和均匀性；同时，设计子种群通信机制，使用优秀个体替换其他种群中的较差个体，加快进化速度。另一方面，使用强化学习实现遗传算法交叉概率的调整，通过对历史数据规律的学习作出合理的决策，使参数更适应进化过程，提高遗传算法的鲁棒性。使用提出的算法对9个函数进行测试求解，并对比了基本GA、RLGA、KPGA，证明了本文所提算法具有较强的寻优能力和稳定性。

对机器学习结合启发式算法的研究有待更加深入，未来可从以下两方面展开工作：①引入深度学习结合启发式算法,如使用神经网络拟合Q-learning中离散且数量有限的Q-Table，实现状态的连续和数量无限;②扩展应用领域,如将所提算法用于车间调度问题、车辆路径调度问题等。