2.2　学习型智能优化中的知识

本节提出了精英个体知识、构件知识、算子知识和参数知识4种知识形式，为学习型智能优化方法嵌入知识奠定了重要基础；构建了用于实现学习型智能优化方法的8类典型知识，可辅助学习型智能优化方法高效地求解复杂优化问题。本书采用一维或多维数组来表示知识，知识的表示和存储就相对比较简单。由于仅采用统计方式来完成对不同类型知识的挖掘（学习），因此将不再详细阐述每种知识的表达、抽取和存储等技术。本节首先对每种知识的含义进行了简单界定，然后采用具体例子对部分知识进行直观说明。

2.2.1　精英个体知识

精英个体（elitist）是指种群从开始优化（进化）到目前为止搜索到的适应度值最高的个体，它具有最好的基因结构和优良特性。为了防止当前种群中的精英个体在后续优化过程中被破坏或丢失（可能会导致优化方法不能收敛到全局最优解），DeJong在其博士论文中提出了“精英保留”策略^[179]。该策略的主要思想是：把种群在进化过程中直到某一时刻出现的最好个体直接复制到下一代。

为了保持种群规模不变，如果将精英个体直接加入新一代种群，则可将新一代种群中适应度值最小的个体淘汰。采用“精英保留”策略的优点：智能优化方法在其进化过程中，直到某一时刻出现的精英个体不会被相关操作丢失或破坏。“精英保留”策略对改进智能优化方法的全局收敛能力产生了重大作用，Rudolph已从理论上证明具有“精英保留”的标准遗传算法是全局收敛的^[69]。

鉴于此，本书尝试从智能优化方法中抽取若干精英个体，然后采用精英个体来指导后续优化过程（如学习型协同进化算法中的良种迁移和良种交叉）。在每次迭代完成之后，智能优化方法都从当前可行方案集（种群）中选取若干最优秀个体加入到精英个体集中，本书将精英个体集中的所有个体称为精英个体知识。在精英个体集中，精英个体数目是确定的；在每次迭代之后，如果新获得的精英个体优于精英个体集中的最差个体，则用新获得的精英个体替换精英个体集中的最差个体；反之，不执行替换操作。

精英个体知识的结构可描述为

其中，EL_i={X|f（X）≥f（EL_num）}为第i个精英个体，X是种群中的个体，f（X）为X的适应值，num为精英个体知识的容量。精英个体集中的个体按适应值降序排列，即f（EL_i–1）≥f（EL_i），∀i≤num。精英个体知识是进化过程中具有优势引导作用的个体轨迹的反映。

精英个体知识的应用主要包括以下4种模式：

• 保留精英个体。将每次迭代获得的较优个体保留到精英个体集中，可保留从开始优化到目前为止搜索到的最优个体。从方法适用范围来讲，这种模式适用于各类智能优化方法；从问题适用范围来讲，这种模式适用于各类优化问题。
• 基于精英个体对普通个体进行改进。从精英个体集中随机选取一个精英个体，将该精英个体作为参考基准，对当前种群中的某普通个体执行调整操作，以期获得一个改进的优良个体。从方法适用范围来讲，这种模式适用于各类智能优化方法；从问题适用范围来讲，这种模式适用于各类优化问题。
• 良种迁移：从精英个体集中引进精英个体来替代当前种群中的最差个体。若采用遗传算法进行演化，则从精英个体集中引进精英个体来替代当前种群中的最差个体，然后再进行后续的选择、交叉和变异操作。若采用蚁群算法进行优化，则从精英个体集中引进精英个体来替代当前种群中的最差个体，然后再进行相关知识的更新操作。从方法适用范围来讲，这种模式适用于各类智能优化方法；从问题适用范围来讲，这种模式适用于各类优化问题。
• 良种交叉：从精英个体集中选取精英个体和当前种群中的个体进行交叉操作，用交叉操作产生的较优个体取代原种群中的最差个体。从方法适用范围来讲，这种模式适用于带有交叉操作的各类智能优化方法；从问题适用范围来讲，这种模式适用于各类优化问题。

从精英个体知识的应用模式中不难看出，每次只选择一个精英个体进行良种迁移、良种交叉和基于精英个体对普通个体进行改进操作，因此暂时还不涉及多个精英个体之间的冲突问题。在后续著作中，作者将进一步深入研究多个精英个体之间的冲突问题。

2.2.2　构件知识

构件是指构成优化问题可行方案的部件（component），如作业车间调度问题中的工序。构件知识是指有助于构建优化问题可行方案的特征信息，如两个工序是否在一台机器上加工。在学习型智能优化方法中，用到了5类构件知识：构件顺序知识、构件聚类知识、构件指派机器知识、构件指派顺序知识和变量灵敏度知识。

2.2.2.1　构件顺序知识

构件顺序知识（component priority knowledge，CPK）就是描述构件之间服务顺序的一种累积知识。在构建双层CARP优化问题（参见第5.1节）的可行方案时，经常要考虑相邻的或距离比较近的两条必需服务弧段之间的服务顺序。在实际操作中，只需学习每条弧段与距离它最近的若干弧段之间的服务顺序。鉴于此，本书将记录构件顺序知识的矩阵的列宽限定为一个固定数值。这样处理的优点在于：当问题规模比较大时，一方面可有效地节省存储空间；另一方面可极大地减少计算量。本书主要从演化过程中已得到的准最优解中学习（抽取）构件顺序知识。下面以简单例子来说明构件顺序知识是如何抽取的。

在求解双层CARP优化问题时，可采用N_R×Dim的矩阵CPK来表示构件顺序知识；这里，N_R表示必需服务弧段的数目，Dim表示矩阵CPK的列宽。构件顺序知识的简单实例如表2.1所示。在表2.1中，每行前三列（0.5Dim）表示距离当前弧段最近的三条弧段；每行后三列表示给定弧段序列在已获得准最优解中出现的次数。如第2行第1列中的1表示距离弧段2最近的弧段是弧段1；第2行第3列中的3表示距离弧段2第三近（third closest）的弧段是弧段3；第2行第4列中的6表示弧段序列（2，1）在已获得准最优解中共出现了6次；第2行第6列中的13表示弧段序列（2，3）在已获得准最优解中共出现了13次。弧段序列（2，1）表明弧段2和弧段1的服务顺序；即先执行对弧段2的服务，然后再执行对弧段1的服务。根据实验结果，在求解双层CARP优化问题时，构件顺序知识矩阵的列宽设置为20比较合理；可采用每次迭代所产生的前5%~20%个体来学习构件顺序知识。

假设采用方案C来更新构件顺序知识，且方案C中只有一条路径T₁，其必需服务弧段的服务顺序为3→4→2→1。方案C中出现了三个弧段序列（3，4）、（4，2）和（2，1），将弧段序列（3，4）、（4，2）和（2，1）在准最优解中的出现次数分别增加1次。更新后的构件顺序知识如表2.2所示。

为了防止当前个体中的优良子序列在交叉或变异操作中被破坏，使用构件顺序知识为交叉或变异操作选择断点位置。如果某弧段序列在已获得准最优解中出现的次数非常多，则应以较小概率在该弧段序列之间选择断点位置；反之，则应以较大概率在该弧段序列之间选择断点位置。以表2.2所示的构件顺序知识为基准，设当前个体为4→3→2→1，弧段序列（4，3）、（3，2）和（2，1）在准最优解中出现的次数分别为5次、11次和7次，在弧段序列（4，3）、（3，2）和（2，1）之间选择断点位置的概率（计算方式如下）分别为54%、8%和38%。

构件顺序知识的应用模式可概括为：从已获得准最优解中抽取不同构件之间的服务顺序知识，然后基于构件顺序知识来构造或改进后续个体。从方法适用范围来讲，该模式适用于各类智能优化方法；从问题适用范围来讲，该模式适用于需要考虑不同构件之间服务顺序的各类优化问题。

2.2.2.2　构件聚类知识

构件聚类知识（component cluster knowledge，CCK）就是描述构件之间聚类性质的一种累积知识。在求解双层CARP优化问题时，“聚类”可理解为：将所有必需服务弧段划分为不同群组，每个群组中的必需服务弧段将由同一台车辆来完成服务。在求解多星任务规划问题时，“聚类”可理解为：将所有观测任务划分为不同群组，每个群组中的观测任务将由同一个观测活动来进行观测。

在构建双层CARP优化问题的可行方案时，经常要考虑相邻的或距离比较近的两条必需服务弧段之间的聚类关系。在构建多星任务规划问题的可行方案时，对于卫星单个轨道圈次内的多个观测任务，也经常需要考虑时序上相邻的两个观测活动之间的聚类关系。类似于构件顺序知识，本书将记录构件聚类知识的矩阵的列宽限定为一个固定数值，从演化过程中已得到的准最优解中学习构件聚类知识。

在求解双层CARP优化问题时，可采用N_R×Dim的矩阵CCK来表示构件聚类知识；其中，N_R表示必需服务弧段的数目，Dim表示矩阵CCK的列宽。在求解多星任务规划问题时，可采用N_T×Dim的矩阵CCK来表示构件聚类知识；其中，N_T表示观测任务数目，Dim表示矩阵CCK的列宽。

在求解柔性作业车间调度问题时，构件聚类知识的简单实例如表2.3所示。在表2.3中，每行前三列（0.5Dim）表示距离当前弧段最近的三条弧段；每行后三列表示给定弧段序列在已获得准最优解中被划分到同一个群组中的次数。如第2行第4列中的6表示弧段序列（2，1）在已获得准最优解中有6次被划分到同一个群组中；第2行第6列中的2表示弧段序列（2，3）在已获得准最优解中有2次被划分到同一个群组中。弧段序列（2，1）表示弧段2和弧段1被划分到同一个群组中。

根据表2.3中的构件聚类知识，在构建双层CARP优化问题的可行方案时，假设只有弧段2已被执行服务操作，接下来需要从以下三种可能情况中选择一种结果：

• 以的概率选择弧段1并对其进行服务；
• 以的概率选择弧段3并对其进行服务；
• 以的概率选择弧段4并对其进行服务。

这步操作可通过轮盘赌法来实现。在已获得的准最优解中，弧段2和弧段1被多次划分到同一个群组中，在构件聚类知识的指导下，弧段2和弧段1将以一个较高概率被划分到同一个群组。根据实验结果，构件聚类知识矩阵的列宽设置为20比较合理；可采用每次迭代所产生的前5%~20%个体来学习构件聚类知识。

构件聚类知识的应用模式可概括为：从已获得准最优解中抽取不同构件之间的聚类知识，然后基于构件聚类知识来构造或改进后续个体。从方法适用范围来讲，该模式适用于各类智能优化方法；从问题适用范围来讲，该模式适用于需要考虑不同构件之间聚类处理的各类优化问题。

2.2.2.3　构件指派机器知识

构件指派机器知识（component assignment machine knowledge，CAMK）是指将给定构件安排到比较合理的机器上进行加工的一种累积知识。这里的机器可理解为资源，如柔性作业车间调度问题（参见6.1节）中的车床、多星任务规划问题（参见9.1节）中的卫星遥感器。

在求解柔性作业车间调度问题时，可采用大小为n×num×m的三维数组CAMK来表示构件指派机器知识；n表示工件数目，表示所有工件工序数目的最大值，m表示机器数目；CAMK（i，j，k）可理解为将工序O_ij安排到机器M_k上进行加工的累积知识。在求解多星任务规划问题时，可采用大小为N_T×N_S×num的三维数组CAMK来表示构件指派机器知识；N_T表示观测任务数目，N_S表示卫星遥感器数目，num表示所有卫星对不同任务的可见时间窗数目的最大值；CAMK（i，j，k）可理解为将任务t_i安排到卫星s_j的第k个可见时间窗的累积知识。

在求解柔性作业车间调度问题时，构件指派机器知识的简单实例如表2.4所示。在表2.4中，CAMK（1，2，1）=0表示工序O₁₂不能被安排到机器M₁上进行加工；CAMK（1，2，2）=0.6表示工序O₁₂能以概率安排到机器M₂上进行加工；CAMK（1，2，3）=0.3表示工序O₁₂能以概率安排到机器M₃上进行加工。在初始化阶段，如果工序O_ij不能被安排到机器M_k上进行加工，则将CAMK（i，j，k）初始化为0；如果工序O_ij可被安排到机器M_k上进行加工，且加工时间为p_ijk，则将CAMK（i，j，k）初始化为。

构件指派机器知识的应用模式可概括为：从已获得准最优解中抽取将构件安排到比较合理的机器上进行加工的知识，然后基于构件指派机器知识来构造或改进后续个体。从方法适用范围来讲，该模式适用于各类智能优化方法；从问题适用范围来讲，该模式适用于涉及资源指派的各类优化问题。

2.2.2.4　构件指派顺序知识

构件指派顺序知识（component assignment priority knowledge，CAPK）是指将给定构件以比较合理的优先级进行加工的一种累积知识。

在求解柔性作业车间调度问题时，可采用大小为n×num×rank的三维数组CAPK来表示构件指派机器知识；n表示工件数目，表示所有工件工序数目的最大值，rank表示优先级数目；CAPK（i，j，k）表示采用第k个优先级加工工序O_ij的累积知识。

在求解柔性作业车间调度问题时，构件指派顺序知识的简单实例如表2.5所示。在表2.5中，CAPK（1，2，1）=0.4表示工序O₁₂能以概率以第1优先级进行加工；CAPK（1，2，2）=0.8表示工序O₁₂能以概率以第2优先级进行加工；CAPK（1，2，3）=0.4表示工序O₁₂能以概率以第3优先级进行加工。在初始化阶段，构件指派顺序知识三维数组CAPK中的所有元素都被初始化为τ₀。

构件指派顺序知识的应用模式可概括为：从已获得的准最优解中抽取将构件以比较合理的优先级进行加工的知识，然后基于构件指派顺序知识来构造或改进后续个体。从方法适用范围来讲，该模式适用于各类智能优化方法；从问题适用范围来讲，该模式适用于涉及资源指派的各类优化问题。

2.2.2.5　变量灵敏度知识

变量灵敏度知识是指各个变量在给定区域内对目标值（输出结果）的敏感程度。对于拥有多变量的优化问题来讲，每个变量对目标值的敏感程度都是不同的；有些变量对目标值非常敏感，即变量数值的微小调整会导致输出结果的较大波动；有些变量对于目标值不太敏感，即变量数值的微小调整不会导致输出结果的较大波动。变量对目标值的敏感程度随着变量所处区域的不同而有所差异，如某个变量在区域A内对目标值是敏感的，而在区域B内对目标值却是不敏感的。

通常情况下，可采用灵敏度分析方法来计算每个变量对目标值的敏感程度。灵敏度分析包括局部灵敏度分析和全局灵敏度分析：局部灵敏度分析只检验某个参数的调整对模型结果的影响程度；全局灵敏度分析则检验多个参数的调整对模型结果的影响程度，并分析每个参数及参数之间的相互作用对模型结果的影响程度。

在求解复杂优化问题时，变量灵敏度知识可辅助智能优化方法来提高其优化绩效。在优化问题可行空间的某个区域内，如果某变量对目标值是比较敏感的，则设法调整该变量的输入值，来最大限度地改善目标值；如果某变量对目标值是不敏感的，则对该变量的任何微调基本上都是徒劳的。从提高智能优化方法效率的角度来讲，应尽可能对灵敏度较高的变量进行微调，以最大限度地改善目标值；同时应尽可能避免对灵敏度较低的变量进行微调，以最大限度地节约计算工作量。

变量灵敏度知识的结构可描述为

其中，SEN（i）表示第i维变量在当前最优解附近的灵敏度，N为优化问题的维度。

变量灵敏度知识主要应用于遗传算法的变异操作中。在应用变量灵敏度知识时，首先按照公式（2.10）计算每个自变量被选择操作的概率。

这里，P_i表示第i个自变量被选择操作的概率，从N个自变量中随机选择1个需要进行变异操作的自变量。然后按照微摄动方法，得到变异后的子代染色体。微摄动方法是指，将父代染色体中已选自变量的数值分别微调为原来的1–2σ，1–σ，1+σ和1+2σ倍，这样就得到4个子代染色体，σ为设计参数。从父代染色体和子代染色体中选择一个最优个体作为此次变异的结果。

变量灵敏度知识的应用模式可概括为：从已获得准最优解中抽取各变量在给定区域内对目标值的敏感程度，然后基于变量灵敏度知识来构造或改进后续个体。从方法适用范围来讲，该模式适用于各类智能优化方法；从问题适用范围来讲，该模式适用于各类连续优化问题。

2.2.3　算子知识

通常情况下，每种算子都有不同的适用范围。单个算子在求解有些实例时效果会比较明显，在求解其他实例时效果可能会很差，很难找到能有效求解各种实例的通用算子。为了提高智能优化方法的绩效，可采用多种算子来执行智能优化方法的各种操作，尝试挖掘出能有效求解当前实例的一些算子。

当采用某种算子执行单次操作时，假设参与操作的原个体集合为C_B，操作后产生的新个体集合为C_A，若C_A中的最优个体好于C_B中的最优个体，则认为采用该算子完成的此次操作是成功的。算子的优化绩效可理解为：在求解当前实例的过程中，采用某算子所获得的成功操作次数。算子知识主要是指各个算子优化绩效的一种累积知识，也被称为算子绩效知识（performance knowledge of operators，PKO）。

算子知识抽取和应用的简单实例如表2.6所示。假设在某遗传算法中，共有3种不同算子被用来执行变异操作。若采用第k种算子执行的当前变异操作是成功的，那么第k种算子的优化绩效N（k）将增加1次。在执行下次变异操作时，将根据公式（2.11）来计算每种算子的被选概率。

这里，P（i）表示第i种算子的被选概率。如表2.6所示，在算子知识初始化操作时，每种算子的优化绩效都被初始化为1，根据公式（2.11）计算得到每种算子的被选概率为33%。假设在第1次变异时选择了第二种算子来执行变异操作，第1次变异后得到的新个体优于变异前的原个体（此次变异操作是成功的），则第二种变异算子的优化绩效被更新为2，每种算子的被选概率分别被更新为25%，50%和25%。假设在第2次变异时选择了第一种算子来执行变异操作，第2次变异操作也是成功的，则第一种变异算子的优化绩效被更新为2，每种算子的被选概率分别被更新为40%，40%和20%。假设在第3次变异时选择了第三种算子来执行变异操作，第3次变异操作没能得到改进的个体（此次变异操作是不成功的）；这样所有算子的优化绩效和被选概率均保持不变。

算子知识的应用模式可概括为：采用多种算子执行智能优化方法的各种操作，在优化过程中抽取各个算子的优化绩效，然后基于算子知识优先选取优化绩效高的算子执行后续优化操作。从方法适用范围来讲，该模式适用于各类智能优化方法；从问题适用范围来讲，该模式适用于各类优化问题。

2.2.4　参数知识

在优化过程中动态合理地调整参数取值，是提高智能优化方法优化绩效的简单易行的方法。为了降低参数对实验结果的敏感性，本书采用多个不同参数组合来实施演化过程，同时根据当前参数组合的优化绩效来确定下次迭代所使用的参数组合。在单次迭代完成后，如果全局最优解得到改进，那么当前迭代被称为一次成功的迭代。在求解当前实例的过程中，采用给定参数组合获得的成功迭代次数可看作是该参数组合的优化绩效。参数知识主要指各个参数组合优化绩效的一种累积知识，又被称为参数组合绩效知识（performance knowledge of parameter combinations）。

在初始化阶段，可采用正交设计方法^[180]来产生多个不同参数组合，同时每个参数组合的优化绩效都被初始化为1。在智能优化方法每次迭代之前，采用轮盘赌法（基于参数组合的优化绩效）随机地从多个参数组合中选择一个参数组合作为本次迭代的参数；如果全局最优解在本次迭代中得到改进，则增加本次迭代所使用参数组合的优化绩效值。

参数知识抽取和应用的简单实例如表2.7所示。在第一次迭代前，每个参数组合的优化绩效和被选概率分别被初始化为1和25%。假设采用轮盘赌法选中了参数组合2为第一次迭代的参数，且当前最优解在本次迭代中得到改进，则参数组合2的优化绩效增加为2。在第二次迭代前，每个参数组合的被选概率分别为20%，40%，20%和20%。参数知识抽取和应用既保证了以较高概率使用那些拥有较高优化绩效（多次成功改进全局最优解）的参数组合，又保证了参数组合的多样性，可有效地提高学习型智能优化方法的优化绩效。

参数知识的应用模式可概括为：采用多个不同参数组合来实施优化过程，在优化过程中抽取各参数组合的优化绩效，然后基于参数知识优先选取优化绩效高的参数组合作为下次迭代的参数。从方法适用范围来讲，该模式适用于各类智能优化方法；从问题适用范围来讲，该模式适用于各类优化问题。

各类知识的应用模式和适用范围如表2.8所示。