3.2　求解过程

求解函数优化问题的学习型遗传算法^[181]的优化流程如图3.1所示。学习型遗传算法的改进之处主要体现在：将多种不同操作算子集成到学习型遗传算法中；基于算子绩效知识动态地选择下一步操作中需要使用的操作算子。

3.2.1　种群初始化

本书采用浮点数方式对函数优化问题的解进行编码。在浮点数编码方式下，每个一维浮点数组（染色体）对应于函数优化问题的一个解；所有染色体的长度都等于优化问题的维度。在求解函数优化问题之前，通常很难知道全局最优点的分布区域，需要在种群初始化阶段就均匀地、离散地搜索整个可行空间。正交表在所有可能的组合中指定了均匀离散分布的数量规模比较小的组合群，能产生一组比较好的初始种群^[180]。因此本书采用正交设计方法来产生学习型遗传算法的初始种群。

（1）根据公式（3.5）将优化问题的可行空间[L，U]分割成B个子空间。

这里，L=[l₁，l₂，…，l_n]^T和U=[u₁，u₂，…，u_n]^T分别表示优化问题n个自变量的下边界和上边界；B为设计参数；I_k表示第k位为1，其他位为0的n维列向量；L_i和U_i分别表示类似于L和U的n维列向量。优化问题的可行空间[L，U]被分割成B个子空间，即[L₁，U₁]，[L₂，U₂]，…，[L_B，U_B]。

（2）按照公式（3.6）将每个子空间内的每个自变量进行离散化。假设自变量x_i的定义域为[l_i，u_i]，根据设计参数Q₁（奇数），将x_i量化成Q₁个水平a_i1，a_i2，…，，a_ij的计算方式如公式（3.6）所示。

（3）从每个子空间中选出M₁个染色体。构造正交表，n为优化问题的维数，，J₁是满足条件的正整数；从这个组合中选取M₁个组合，应用这些组合生成M₁个染色体。

（4）根据适应度值从M₁B个潜在染色体中选择最优秀的G个（种群规模）染色体作为初始种群。

3.2.2　选择操作

选择操作从当前种群中选出优良个体，将它们作为父代为下一代繁殖子孙，故被称为再生操作。选择操作的原则是向适应度较强的个体赋予较大的生存机会。选择操作根据个体对环境的适应度来决定其繁殖量，也称为非均匀再生（differential reproduction）。本书采用轮盘赌法来执行学习型遗传算法的选择操作。

3.2.3　交叉操作

求解函数优化问题的学习型遗传算法^[181]中用到了5种交叉算子：“取大”“取小”交叉算子^[213]、量化正交交叉算子^[180]、算术交叉算子^[214]、单点交叉算子和双点交叉算子。这5种交叉算子的基本信息如表3.1所示，这些交叉算子的操作方式描述如下。假设两个父代个体为

3.2.3.1　“取大”“取小”交叉算子

采用“取大”“取小”交叉算子执行交叉操作后，新产生的两个子代个体为

3.2.3.2　量化正交交叉算子

两个父代个体决定的求解空间[l_parent，u_parent]为

按照公式（3.6）将求解空间[l_parent，u_parent]离散化成Q₂份。随机生成F–1个整数1＜k₁＜k₂＜…＜k_F–1＜n；对于每个父代个体来讲，可产生F个因素

生成正交表，，J₂是满足条件的最小正整数；从个组合中选取M₂个组合；应用这些组合生成M₂个潜在子代。从潜在子代个体和父代个体中，选择适应度值最好的两个个体，作为本次交叉操作的结果。

3.2.3.3　算术交叉算子

产生一个位长为n的杂交模板s₁，s₂，…，s_n，其中0表示不杂交，1表示杂交。依据杂交模板对两个父代个体进行杂交，杂交方式为算术杂交，即生成n个在[0，1]区间上服从均匀分布的随机数t₁，t₂，…，t_n。按照杂交模板对这组随机数进行修改，即将模板与随机数组上相同位置的数字相乘，得到一组交叉系数r₁=s₁t₁，r₂=s₂t₂，…，r_n=s_nt_n。采用算术交叉算子执行交叉操作后，新产生的两个子代个体为

3.2.3.4　单点交叉算子

在区间[0，1]上产生一个随机数r，采用单点交叉算子执行交叉操作，新产生的两个子代个体为

3.2.3.5　双点交叉算子

在区间[0，1]上产生两个随机数r₁和r₂，采用双点交叉算子执行交叉操作，新产生的两个子代个体为

在每次交叉操作之前，学习型遗传算法都基于交叉算子的绩效知识来动态地选择本次交叉操作中需要使用的交叉算子；在每次交叉操作之后，学习型遗传算法将基于当前交叉操作的结果（采用哪种算子执行了交叉操作，当前交叉操作是否得到改进解）来更新交叉算子的绩效知识。通过交叉算子绩效知识的更新与应用，学习型遗传算法尽可能地选择适合当前优化问题的交叉算子执行后续的演化过程。

在标准遗传算法中，通常给所有个体都赋予一个常数交叉概率，这种方式带有一定盲目性和随机性。依据每代个体的适应度值来调整交叉概率，使交叉沿着有利于算法收敛的方向进行。采用公式（3.7）来计算每个个体的交叉概率：

这里，Pc[i]代表第i个个体的交叉概率，f_i表示第i个个体的适应度值，f_min和f_avg分别表示当前种群中个体适应度值的最小值和平均值。假设个体i和个体j的交叉概率分别为Pc[i]和Pc[j]，如果个体i和个体j被选作父代个体来进行交叉操作，则以概率min{Pc[i]，Pc[j]}作为依据判断它们是否要进行交叉操作。

3.2.4　变异操作

求解函数优化问题的学习型遗传算法^[181]中用到了8种变异算子：随机数变异算子、随机一维变异算子^[215]、附加扰动变异算子^[215]、多位互换变异算子^[215]、逆序变异算子^[215]、i步循环移位变异算子^[215]、外抛变异算子^[216]和高斯变异算子^[180]。这8种变异算子的基本信息如表3.2所示。假设执行变异操作之前的个体为

P=（p₁，p₂，p₃，p₄，p₅，p₆，p₇，p₈）

对于当前优化问题，假设第i（1≤i≤8）个变量的可行区间为[l_i，u_i]。

3.2.4.1　随机数变异算子

在区间[1，8]上产生随机整数r，在区间[l_r，u_r]上产生随机数ε，采用随机数变异算子执行变异操作。假设随机数r=3，则子代个体为

P′=（p₁，p₂，ε，p₄，p₅，p₆，p₇，p₈）

3.2.4.2　随机一维变异算子

在区间[1，8]上产生随机整数r，在区间[0，1]上产生随机数ε，令ε′=max{l_r，min{u_r，p_r+ε}}，采用随机一维变异算子执行变异操作，假设随机数r=5，则子代个体为

P′=（p₁，p₂，p₃，p₄，ε′，p₆，p₇，p₈）

3.2.4.3　附加扰动变异算子

在区间[0，1]上产生8个随机数ε₁，ε₂，…，ε₈，令（1≤i≤8），采用附加扰动变异算子执行变异操作，新产生的子代个体为

3.2.4.4　多位互换变异算子

采用多位互换变异算子执行变异操作时，可能出现以下两种情况：

（1）在区间[1，8]上产生随机整数j，将第k（k=1，2，…，8–j）位的基因与第k+j位的基因进行互换。假设随机数j=3，则子代个体为

P′=（p₄，p₅，p₆，p₇，p₈，p₃，p₁，p₂）

假设随机数j=5，则子代个体为

P′=（p₆，p₇，p₈，p₄，p₅，p₁，p₂，p₃）

（2）在区间[1，8]上产生两个随机整数i和j，将第k（k=1，2，…，i）位的基因与第k+j（如果k+j＞8，则为k+j–8）位的基因进行互换，假设随机数为i=3和j=4，则子代个体为

P′=（p₅，p₆，p₇，p₄，p₁，p₂，p₃，p₈）

假设随机数为i=5和j=4，则子代个体为

P′=（p₁，p₆，p₇，p₈，p₅，p₂，p₃，p₄）

3.2.4.5　逆序变异算子

在区间[1，8]上产生两个随机整数1≤i＜j≤8，采用逆序变异算子执行变异操作，假设随机数为i=3和j=6，则子代个体为

P′=（p₁，p₂，p₆，p₅，p₄，p₃，p₇，p₈）

3.2.4.6　i步循环移位变异算子

在区间[1，8]上产生随机整数i，采用i步循环移位变异算子执行变异操作，假设随机数为i=3，则子代个体为

P′=（p₆，p₇，p₈，p₁，p₂，p₃，p₄，p₅）

3.2.4.7　外抛变异算子

在区间[–1，1]上产生8个随机整数r_i（外抛方向），在区间上产生8个随机数s_i（外抛步长），令，采用外抛变异算子执行变异操作，则子代个体为

3.2.4.8　高斯变异算子

在区间上产生随机数δ，产生8个方差为δ均值为0的正态随机数r₁，r₂，…，r₈，令，采用高斯变异算子执行变异操作，则子代个体为

在每次变异操作之前，学习型遗传算法都基于变异算子的绩效知识来动态地选择本次变异操作中需要使用的变异算子；在每次变异操作之后，学习型遗传算法将基于当前变异操作的结果（采用哪种算子执行了变异操作，当前变异操作是否得到改进解）来更新变异算子的绩效知识。通过变异算子绩效知识的更新与应用，学习型遗传算法尽可能地选择适合当前优化问题的变异算子执行后续的演化过程。

在标准遗传算法中，通常给所有个体都赋予固定的变异概率，这种方式带有一定盲目性和随机性。本书依据每代个体的适应度值来调整变异概率，使变异沿着有利于算法收敛的方向进行。本书采用公式（3.8）来计算每个个体的变异概率：

这里，Pm[i]代表第i个个体的变异概率，f_i表示第i个个体的适应度值，f_min和f_avg分别表示当前种群中个体适应度值的最小值和平均值。

3.2.5　灾变操作

求解函数优化问题的学习型遗传算法^[181]中用到了5种灾变（局部优化）算子：动态更新灾变算子、免疫灾变算子^[217]、单纯形灾变算子^[218]、混沌搜索灾变算子^[219]和最速下降灾变算子^[220]。这5种灾变算子的基本信息如表3.3所示。

3.2.5.1　动态更新灾变算子

采用随机方法产生200个可行方案（优化问题的解），计算这200个可行方案的目标值，从这200个可行方案中选出最好的G/2（当前种群规模的一半，四舍五入使之为整数）个优秀个体，采用挑选出来的G/2个优秀个体替换当前种群中最差的G/2个个体。采用动态更新灾变算子进行局部优化操作，既可向当前种群中注入一些新的个体；也可有效保证当前种群的多样性。

3.2.5.2　免疫灾变算子

免疫灾变操作的核心在于如何抽取疫苗和利用疫苗。疫苗的实质就是对最优个体在某一分量上值的估计。免疫灾变包括疫苗提取、接种疫苗和免疫选择三个步骤。接种疫苗是为了提高个体的适应度，免疫选择则是为了防止群体的退化。

（1）疫苗提取。疫苗提取可通过利用所求问题的一些特征信息或对问题的先验知识来进行。先验知识可以是最优个体某些分量x_i的大概取值范围，也可以是一些分量之间的制约关系。为了提高算法的通用性与应用的便利性，同时为了避免在某些情况下，对所求解的问题一时很难形成较为成熟的先验知识，从而无法正确地提取疫苗或为了提取正确的疫苗而要做大量的工作，本书提出了一种自适应疫苗抽取算法。其过程是：将每个变量x_i的可行区间[l_i，u_i]平均分割成20个子区间，对每代的最优个体进行分析，统计这些最优个体中每个分量x_i的取值落入各个子区间的次数。本书将这些共同特点和有效信息看作疫苗库H。

（2）接种疫苗。对第k代种群P^（k）接种疫苗，就是按照比例α（0≤α≤1）（将α设置为0.6）从种群P^（k）中随机抽取G_a=α·G个个体来接种疫苗。给个体X=（x₁，x₂，…，x_n）接种疫苗，就是按照先验知识（疫苗库H）强制性修改个体X中某些分量x_i的取值。在对个体接种疫苗时，首先需要判断对哪些基因位进行接种，然后从疫苗库H中抽取有用疫苗对这些基因位接种疫苗。在判断哪些基因位需要进行接种操作时，可随机生成一个长度为n的布尔数组R（对于数组R的每个分量，以20%的概率取1，80%的概率取0），如果R（i）=1，则第i个基因位需要执行接种操作；反之，第i个基因位不需要执行接种操作。在从疫苗库H中选取分量x_k的疫苗时，首先按照概率选取一个合适的子区间，这里a（i）表示在前期演化过程中已经获得的准最优解中分量x_k的取值落入到第i个子区间内的次数；然后在所选子区间上产生随机数R_p，R_p就是从疫苗库H中选取出来的分量x_k的疫苗。

（3）免疫选择。对接种疫苗的个体进行检测，若其适应度比原来退化了，这时该个体将被接种前的个体所替代；反之，接种后的个体将进入下一代种群。免疫选择对算法的收敛性将起到决定性作用，对加强免疫灾变算子的功能有着积极的作用，具有较强的鲁棒性。

3.2.5.3　单纯形灾变算子

单纯形方法针对n维向量给出n+1个点，将选取的n+1个点作为n维单纯形的n+1个顶点；求取n+1个顶点上的函数值，找出其中带有最大函数值的顶点（最高点）、最小函数值的顶点（最低点），仅低于最高点的顶点（次高点）。通过反射、扩展和压缩求取一个新的较好的顶点代替最高点，形成一个新的单纯形；或通过向最低点收缩形成一个新的单纯形，以逐步逼近函数的极小值点。采用单纯形灾变算子执行局部优化操作的具体步骤如图3.2所示。单纯形灾变算子中的参数设置为a_m=1.2，a_c=0.5，a_e=2，ε=10^–6。

3.2.5.4　混沌搜索灾变算子

混沌是非线性系统中的普遍现象，具有一些特异性质：如混沌运动能在一定范围内按其自身规律不重复地遍历所有状态（遍历性）；初值条件极其微弱的变化会引起系统行为的巨大变化，即对初值变化强烈的敏感性。混沌优化算法容易跳出局部解，计算效率高。假设某系统的运动状态为

这里，0≤t₀＜1，k=0，1，2，…，u为控制变量，u=4时公式（3.9）刻画的系统完全处于混沌状态。混沌搜索灾变算子的基本步骤如图3.3所示。混沌搜索灾变算子中的参数设置如下：c_i和d_i均为区间[0，10]上的随机数，每次混沌搜索的最大迭代次数为200次。

3.2.5.5　最速下降灾变算子

采用最速下降灾变算子执行局部优化操作的具体步骤如图3.4所示。最速下降灾变算子中的参数设置为δ=0.1，ε=10^–6，β=0.5，α=2。

在每次灾变操作之前，学习型遗传算法都基于灾变算子的绩效知识来动态地选择本次灾变操作中需要使用的灾变算子；在每次灾变操作之后，学习型遗传算法将基于当前灾变操作的结果（采用哪种算子执行了灾变操作，当前灾变操作有没有得到改进解）来更新灾变算子的绩效知识。通过灾变算子绩效知识的更新与应用，学习型遗传算法尽可能地选择适合当前优化问题的灾变算子来执行后续的演化过程。

在每次迭代之后，学习型遗传算法都执行一次灾变操作，从而尽可能地提高当前种群的质量。局部优化操作对于初始解是比较敏感的：如果初始解选的比较合适，局部优化操作就能快速地得到最优解。鉴于此，在每次灾变操作之前，都从当前种群中选择一些比较优秀（通常从适应度较高的前30%的个体中随机选择）的个体作为局部优化操作的初始解。如果在局部操作中得到了改进解，则用这些改进解来替换当前种群中适应度最差的一些个体。

3.2.6　终止条件

当下列条件之一满足时，求解函数优化问题的学习型遗传算法^[181]立即终止：如果优化过程中得到的全局最优解与实际最优解的相对误差小于0.001%；如果优化过程中得到的全局最优解在连续SI次迭代内没有被改进；如果预先设置的MI次（最大迭代次数）迭代已经完成。