任务6.3 基于MOEAD算法的多目标柔性作业车间调度方法
1.任务引入
多目标优化问题广泛存在于科学研究与工程实践中，多目标进化算法以其高效的搜索能力，为传统精确方法难以求解的MOP提供新的思路。多个目标一般相互对立，这使优化的最终结果不再是单一解，而是一组解集，需要算法同时具有较好的收敛性与分布性。不少学者针对MOP设计不同的多目标进化算法。本书以提高算法的整体性能为出发点，综合考虑算法的收敛性与分布性，从种群进化结构、大规模优化的探索方向等角度出发，设计新的多目标进化算法。同时，以柔性作业车间调度为背景，结合多目标优化理论，将多目标进化算法应用于调度模型，提供优化方案。
2.任务目标
1）知识目标
（1）了解基于矢量角的竞争粒子群（VaCSO）算法。
（2）理解基于分解的大规模三粒子竞争算法。
（3）理解基于交叉融合的多目标迁徙鸟群优化算法。
2）技能目标
通过调度方法的学习能够进行优化调度。
3）素养目标
提升学生基于任务分析问题、解决问题的能力，培养快速学习专业知识的能力。
3.任务分析
本任务的主要研究工作如下。
（1）本任务所设计的基于角矢量的竞争粒子群算法从收敛性与分布性两个角度出发，通过分群聚类、竞争学习和辅助优化等操作，完成种群的寻优过程，在保证粒子收敛的基础 上增加粒子的空间分布。
（2）当决策变量大规模化时，传统的解决MOP的MOEA已不再适用，本任务设计的LTCSO/D可以解决大规模化所引起的局部最优点数量上升和粒子搜索方向一致所导致的多样性不足这两个问题。
（3）通过对多目标进化算法的研究，将其应用于柔性作业车间调度。
4.相关知识
1）基于矢量角的竞争粒子群算法
（1）竞争粒子群算法的概念。
竞争粒子群算法作为一种典型的元启发式算法，自问世以来已经得到学者的广泛关注，部分学者已经成功将其应用到多目标优化问题的求解，并取得了一定成果，但是该算法的性能在很大程度上取决于个体最佳粒子或全局最佳粒子，并且PSO在解决SOP上展现出的快速收敛性使得其在解决MOP时容易出现粒子分布不均、算法收敛性与分布性难以均衡等情况。为了解决以上问题，本书提出基于矢量角的竞争粒子群算法。
（2）算法改进动机。
竞争粒子群算法作为一种元启发式算法，其灵感来自自然界中鸟类的聚集行为。每一个粒子均有一个位置矢量与一个速度矢量，该速度矢量受个体最佳粒子和全局最佳粒子的影响。该粒子下一时刻的位置与速度根据当前粒子的速度信息与位置信息获得。可假设一个粒子群P（t）共包含N个粒子，每一个粒子i（i=1，2，…，N）有一个n维的位置矢量xi=（xi1，xi2，…，xin）和一个n维的速度矢量vi=（vi1，vi2，…，vin）。其速度更新公式与位置更新公式分别如式（6-10）与式（6-11）所示。
（3）算法原理及实现。
①算法整体结构。
基于角矢量的竞争粒子群算法的整体结构如图6-7所示，其主要包含以下步骤。
图6-7 基于角矢量的竞争粒子群算法的整体结构
首先，为了充分考虑多目标优化中的收敛性和多样性要求，采用基于指标的种群聚类。种群1更加关注算法的收敛性，种群2和种群1相比更加注重算法的分布性。其次，为了消除通用的多目标PSO参数的影响，使用竞争粒子群优化器CSO作为基本竞争机制。同时，考虑到CSO仅使用获胜粒子的信息，不能充分利用隐藏在失败粒子中的信息（此类信息在当前一代中表现可能很差，而在下一代中表现较佳），本书提出了一种三粒子竞争机制。最后，为一起优化两个种群，在三粒子竞争机制的基础上，添加辅助学习的思想，以优化种群之间的间隙。
②基于指标的分群聚类。
在多目标优化问题中，收敛性与分布性是算法的两个重要评价方向，为了使基于角矢量的竞争粒子群算法尽可能满足这两个评价指标，将种群依据指标进行分组。分组的最终结果是：种群1主要负责算法收敛性，种群2主要负责算法分布性。
聚合函数可以将多个目标映射到单个目标上，通过所获得的函数值可以对粒子的适应度值做出简单的判断。一般来说，数值越小的粒子其适应度越高，其越接近真实PF，收敛性能越好。针对种群1，为了使粒子更好地依据收敛性进行优化，这里提出了目前主要研究的聚合函数，并探讨其对算法性能的影响。
第一个聚合函数是目标和（the sum of all objectives，Sum），其计算公式如式（6-12）所示。
第二个聚合函数是到理想参考点的欧拉距离（the Euclidean distance to the Ideal reference point，EdI），其计算公式如（6-13）所示。
第三个聚合函数是到理想参考点的切比雪夫距离（the Chebyshev distance to the Ideal reference point，CdI），其计算公式如（6-14）所示。其针对离散问题优势更大，常用于基于分解的MOEA。
第四个聚合函数是到Nadir参考点的欧拉距离（the Euclidean distance based on Nadir point，EdN），其计算公式如（6-15）所示。
③基于精英集的竞争学习。
本算法的更新机制主要采用CSO框架，设计两个种群的目的是使种群1更注重算法收敛性，使种群2在考虑算法收敛性的基础上更注重算法分布性。为了保证算法的收敛性，首先采用了基于精英集的竞争学习方式，通过获得精英集，利用精英集指导待优化粒子。
精英种群的初始化采用NSGAII中非支配排序和拥挤距离的思想。值得注意的是，在种群进化后期，精英集中的粒子应是胜利粒子，在种群1中通过胜利粒子引导失败粒子，以此使失败粒子迫近真实PF。在种群1中，通过选择精英集中的粒子进行竞争，将胜利粒子作为待优化粒子的引导粒子，以此增加粒子的收敛性。
④三粒子竞争策略。
将基本CSO框架直接用于多目标优化时，存在以下问题：后代生成策略单一，只使用一种竞争机制，仅利用获胜粒子的信息，未能挖掘失败粒子隐藏的有用信息。在增加后代生成策略的多样性的基础上，还使用了失败粒子和中间粒子的隐藏有用信息。在三粒子竞争中，为了充分利用粒子之间的信息，设计两个速度更新公式，如式（6-16）和式（6-17）所示。(https://www.daowen.com)
⑤基于辅助学习的种群间隙优化。
值得注意的是，当算法根据指标对种群进行分组时，可能出现一个新的问题。由于指标不同，两个种群的分布范围可能有所不同，这使种群之间可能存在较大空间间隙。为了解决上述问题，该算法引入辅助学习的思想。在辅助学习中，该算法使用种群1中的获胜粒子作为辅助粒子，种群2中待优化粒子前进到种群1和种群2的折中空间。
2）基于分解的大规模三粒子竞争算法
（1）大规模三粒子竞争算法。
当MOP中决策变量的规模进一步增大时，便产生大规模多目标优化问题（Large-Scale Multi-objective Optimization Problems，LSMOP），其广泛存在于实际应用中。决策变量大规模化，使传统的MOEA的性能大幅度降低。LSMOP相比MOP计算难度更大。一方面，随着决策变量数量的大规模化，搜索空间呈指数级增长；另一方面，维数的增加可能导致算法中具有相似优化方向的解的数量增加，从而导致产生多个局部最优解。
（2）算法改进动机。
尽管现有方法对LSMOP表现出一定的优化效果，但仍然存在一些问题。针对大规模优化的三类算法（基于决策变量分析、协同进化、问题转移框架）主要是在决策变量空间上进行一定程度的操作运算，然而其整体搜索效率和搜索能力有待提高。
由于决策变量的大规模化，搜索空间呈指数级增长，局部最优点的数目爆炸性增加，现存的针对LSMOP的MOEA后代生成策略相对简单，其搜索功能不足，容易产生具有相似搜索方向的多个解决方案，并且不可能在有效时间内尽可能多地搜索有效空间。
（3）算法原理及实现。
①算法整体结构及框架。
LTCSO/D的整体结构如图6-8所示。决策变量空间的大规模化使搜索空间呈指数级增长，同时也导致在局部最优点的解的数量爆炸性上升。为解决以上两个问题，首先，对目标空间进行分解操作，将解的分布性提高，避免解过于集中导致算法“早熟”现象的发生；其次，搜索空间的变大使得传统的多目标PSO算法失效，这里提出三粒子竞争搜索策略，增加新的粒子速度更新方式，同时提出“邻接种群学习”的概念，使粒子的搜索更具方向性；最后，为了充分利用矢量角信息，使用基于矢量角的环境选择策略进行种群的更新。
图6-8 LTCSO/D的整体结构
LTCSO/D与当前大多数EOEA的框架相似，主要包括种群和参数初始化，后代生成策略和环境选择策略。在参数初始化中，为了解决由于决策变量规模较大而无法使解在真实Pareto前沿上完全均匀分布的问题，此处采用了目标空间分解策略，在每个小空间中进行竞争性学习。同时，为了充分利用邻近解的信息，设计了邻接种群学习策略。因此，该算法需要在初始化时设计权重矢量和邻接矩阵。在后代生成策略中，为了充分利用解决方案的潜在信息，LTCSO/D使用了三粒子竞争策略。在环境选择策略中，为了增加解决方案的多样性，该算法使用了基于最大矢量角的环境选择策略。
②基于空间分解的种群分组。
由于“维数诅咒”现象的存在，当前用于大规模MOEA的PSO算法的性能较差。由于决策变量维度的增加，存在大量具有相似搜索方向的粒子，进而使围绕局部最优的粒子个数增多，所获得的最优解集分布不均，无法在真实PF均匀分布。为了解决上述问题，该算法采用基于空间分解的种群分组策略。
为了能够将目标空间划分为不同组别，需要使用一组方向矢量作为划分依据，每个方向矢量位于每个子空间的中间区域。在此，可假设用户希望使解尽可能在真实PF上分布，不考虑用户的偏好信息。
③三粒子竞争搜索策略。
现有的多目标PSO和CSO算法在解决具有超过50个决策变量的MOP时，算法的性能显著下降。上述现象主要是由于以下两个方面。传统的PSO和CSO对后代具有单一生成策略，并且当问题规模较大时，所得解决方案的分布性能会下降。其次，CSO仅使用胜利粒子信息，而PSO仅使用当前种群中较好解的个体。问题维度的扩展要求算法使用尽可能多的有用信息。为了解决上述问题，LTCSO/D使用三粒子竞争搜索策略。在三粒子竞争搜索策略中，设计两个新的速度更新公式，如式（6-18）与式（6-19）所示，位置更新方式如式（6-20）所示。
在三粒子竞争搜索策略中，除当前种群粒子的速度和位置信息外，还需要邻接矩阵（B）和权重矢量（W）来获得竞争粒子。
为了确定粒子之间的邻接关系，该算法使用标志（flag）矩阵确定粒子与划分的子空间之间的归属关系。对于总体中的每个粒子pi，首先将值归一化，然后获得粒子pi所属的子区域，同时确定与粒子pi所属同一子空间Ri的粒子。为了解决传统CSO后代的单代策略问题，在通过传统竞争粒子学习获得后代粒子（off_vl，off_pl）之后，该算法使用速度更新[式（6-18）和式（6-19）]来生成两个额外的后代粒子。最后，该算法对获得的后代粒子执行常见的多项式变异，然后返回后代粒子。此时，后代粒子的数量大于当前种群中的粒子数量。
在传统的CSO中，仅使用胜利粒子来指导要优化的粒子，而失败粒子的潜在信息（当前代数性能较差，但仍然有一些信息对算法的收敛性或分布性有用）被忽略。这容易导致由胜利粒子的相似引导方向，使产生的后代粒子分布较差的问题。
④基于最大矢量角的环境选择。
当问题的维数增加或真实PF为离散情况时，很有可能使算法得到的解集中在局部区域，算法的总体性能下降。为了解决上述问题，算法应在确保收敛的同时尽可能地保留对算法分布性有贡献的粒子。在LTCSO/D的最后，使用基于最大矢量角的环境选择策略。
使用归一化操作，如式（6-21）所示。其目的是使每个粒子的目标空间的数值统一到[0，1]范围内，并消除某些粒子由于数值过大或过小而对其他解产生不利影响。式中f*k（pi）是归一化后的目标值，fkmax与fkmin分别为第k个目标的最大值与最小值。
考虑到种群的收敛性，此处使用Euclidean距离作为收敛指标，其计算方法如式（6-22）所示。该公式主要用于粒子排序。其数值越小，粒子的收敛性能越好，反之，粒子的收敛性能越差。
此处使用基于角度的信息作为分布性指标，角度值越大，两个目标矢量之间的距离越大，就越有开发潜在区域的可能。此时，问题的关键在于如何选择两个要比较的粒子，以及如何选择较大角度的粒子。针对以上两个问题，采用最大矢量角优先的策略。
3）基于交叉融合的多目标迁徙鸟群优化算法
（1）算法设计动机。
近年来，MOFJSP已经引起学者的广泛关注，目前用于解决MOFJSP的方法主要有先验法与后验法。先验法只能得到单一解，无法提供有指导意义的多目标优化方案，而在后验法中大多数算法采用种群迭代的全局优化方法，缺少有效的局部搜索策略。迁徙鸟群优化（MBO）的有效的局部搜索方式及其在离散问题上的优异性能为求解MOFJSP提供了新的思路。
MBO最初用于解决单目标离散问题，其参考了迁徙鸟群的队列结构，整个鸟群呈V形排列，在最前方的为领飞个体，后边的为跟飞个体。在传统MBO中，领飞个体个数为1，其消耗能量最多，信息通过领飞个体一层层向下传递，从而优化整个鸟群。MBO主要包含4个部分：初始化、领飞个体优化、跟飞个体优化、领飞个体更新。初始化需针对种群大小、邻域解规模N、共享解规模S、巡回次数G等参数设置，形成V形结构。在领飞个体优化中，通过产生N个邻域解，将最好的邻域解取代领飞个体，同时在剩下的N-1个邻域解中选择2S个个体放入共享解集，再让这2S个个体平均分配到V形结构两侧。跟飞个体通过自身产生的N个邻域解与上一个个体传下来的S个共享解来更新自身数值。在领飞个体替换过程中，将领飞个体随机移至种群后端，其余跟飞个体依次前移一个位置，领飞个体从原来离其最近的两个个体中选择。
当直接将MBO用于MOEA时，存在以下问题：目标之间的折中关系无法通过单一领飞个体传递，当共享解、非支配解数量过多时，算法出现“早熟”现象，提前结束进化，使算法的最终较优解是初始化中的较优解。为了解决以上问题，本书提出基于交叉融合的多目标迁徙鸟群优化算法（Multi-Objective Migrating Birds Optimization Algorithm based on Cross Fusion，MOMBO/CF），将其用于柔性作业车间调度问题求解及调度优化。
（2）算法。
MOMBO/CF其整体步骤与传统MBO相似，包含初始化、领飞鸟群优化、跟飞鸟群优化与领飞鸟群更新四个步骤。
其中在V形结构中，领飞个体更替为领飞鸟群，领飞鸟群的初始化取的是非支配解集，这样做的目的是尽可能使非支配解的信息得到保留，一方面通过非支配解集进行局部搜索可以探索更优的解，另一方面通过非支配排序得到的共享解保留较好的收敛信息，通过共享解来更新跟飞种群，以此保证算法的整体收敛性。
在领飞鸟群与跟飞鸟群进化之后，领飞鸟群每巡回一次时，均使用一次队间交叉融合，以提高整体的分布性，在巡回结束后，再进行队内交叉融合，以起到信息交互的作用。最后进行领飞鸟群更新。在此步骤中，考虑变异操作在提高种群多样性与帮助算法跳出局部最优解的优势，进行种群的依概率变异，而后通过变异的个体与整个种群混合，采用非支配排序与拥挤距离的思想进行个体的选择与更新。
（3）种群个体优化及局部搜索。
种群个体优化的过程主要包含两个方面：领飞鸟群的优化与跟飞鸟群的优化。无论是领飞鸟群的优化还是跟飞鸟群的优化，均需要产生邻域鸟群，领域鸟群的产生主要采用局部搜索策略。
在领飞鸟群的优化过程中，由于领飞鸟群中的个体均为非支配解，所以其与跟飞鸟群中的个体相比，能保留更多对算法收敛性有用的信息。领飞鸟群中的个体本身比跟飞鸟群中的个体包含更多的潜藏解，所以在对领飞种群优化时，需要采用局部搜索来探索有用信息。而跟飞鸟群中的个体，除了自身产生邻域解之外，还会融入共享解，共享解来自属于队列同一侧的前一个个体保留到该个体的解，即共享解与邻域解共同决定被优化粒子的更新数值。
（4）基于交叉融合的全局搜索。
①信息融合方式。
MOMBO/CF采用了两种新的信息融合方式：队间交叉融合与队内交叉融合。队间交叉融合在领飞鸟群每次巡回过程中均进行一次，而队内交叉融合是在当前鸟群巡回结束后，在当代鸟群中进行一次。两种信息融合的方式与目的不同。队间交叉融合主要利用面向工序的交叉操作与面向机器的交叉操作，主要是为了充分利用两个队列的信息，通过从每一个队列中选取父代来将两个队列中的优势基因遗传给下一代，一方面增加了算法的多样性，另一方面可探索更优的解空间。而队内交叉融合主要是防止鸟群规模不断扩大，通过去除劣解，保留优解来保证算法的收敛性，同时在后续的领飞鸟群更新步骤中需要提前对队列结构进行更新，其目的是保持MBO的V形结构，使适应度更好的个体在队列的前边，适应度较差的个体直接被淘汰或放在队列后边。
②染色体编码与解码。
在队间交叉融合中，需从两边队列中随机地各选择G个个体作为父代，然后通过面向工序码与面向机器码的交叉产生后代，同时需要判别后代的优劣，在此过程中需要实现染色体的编码与解码。
在柔性作业车间调度问题中，需要解决以下两个关键问题：为每一道工序都分配一台合适的可加工机器（机器选择问题）、对每一台机器上的被分配到的加工工序进行排列（工序排序问题）。针对以上两个问题，该算法将一个染色体分为两个关键部分：机器选择（Machine Selection，MS）部分与工序排序（Operation Sequence，OS）部分。
染色体解码的目的是指导算法的进化过程，MOMBO/CF不直接作用于优化的目标，也就是说为了使解收敛，需要从编码空间映射到问题空间，在问题空间评价染色体的适应度值进而指导进化。该算法的解码使用的规则是：使解码后的工序在所分配的加工机器上，满足该机器上一个工序已经完工与该工件的上一道工序完工两个约束，插入该机器。
③交叉算子。
MOMBO/CF中的交叉算子存在于队间交叉融合中，由外部输入参数G控制作为交叉所选择的父代个数。其中为了充分利用两个队列之间的信息，分别由两个队列选择G个个体。由于柔性作业车间调度问题属于离散问题，所以常规的用于连续优化理论的交叉算子不再适用。
针对柔性作业车间调度问题中的MS与OS两个子问题，在MS部分使用多点交叉（Multiple Point Crossover，MPX），在OS部分采用基于工件优先顺序的交叉（Precedence Preserving Order-based Crossover，POX）。
④变异算子。
为了增加种群的多样性，同时避免算法收敛于局部最优解，出现“早熟”现象，采用变异操作。
5.任务实施
（1）通过对现存的应用于多目标的PSO算法进行分析，为了去除全局最优粒子或个体最优粒子对算法的影响，采取竞争机制，针对PSO在多目标优化时分布性能不佳的情况设计新的种群进化结构。
（2）分别设计基于空间分解的种群分组和三粒子竞争搜索的策略。LTCSO/D通过挖掘粒子的潜在信息，发挥竞争学习在大规模优化上的探索优势，同时利用最大矢量角环境选择进行种群的更新。
（3）首先，以最大完工时间最短与机器总负荷最小为两个优化目标，建立柔性作业车间调度问题数学模型；其次，结合MOEA中的离散优化相关理论，设计MOMBO/CF；最后，将MOMBO/CF用于柔性作业车间调度问题进行求解与优化，通过与现有的MOEA进行对比，验证调度方案的有效性。
6.任务评价
任务评价见表6-3。
表6-3 任务评价
