Elsevier

Swarm and Evolutionary Computation
蜂群和进化计算

Volume 90, October 2024, 101683
第 90 卷,2024 年 10 月,101683
Swarm and Evolutionary Computation

Dynamic-multi-task-assisted evolutionary algorithm for constrained multi-objective optimization
约束多目标优化的动态多任务辅助进化算法

https://doi.org/10.1016/j.swevo.2024.101683 Get rights and content 获取权利和内容

Highlights 亮点

  • A dynamic task mechanism is designed to improve the generality of the algorithm.
    为提高算法的通用性,设计了一种动态任务机制。

  • The main task processes constraints with higher constraint priority in turn.
    主任务依次处理约束优先级较高的约束。

  • Auxiliary task P2 stops the evolution adaptively after converging to UPF.
    辅助任务 P2 在收敛到 UPF 后自适应地停止演化。

  • The entire solution process is divided into exploration and exploitation stages.
    整个解决方案过程分为探索和开发两个阶段。

Abstract https://linux.do/t/topic/111737

Compared with common multi-objective optimization problems, constrained multi-objective optimization problems demand additional consideration of the treatment of constraints. Recently, many constrained multi-objective evolutionary algorithms have been presented to reconcile the relationship between constraint satisfaction and objective optimization. Notably, evolutionary multi-task mechanisms have also been exploited in solving constrained multi-objective problems frequently with remarkable outcomes. However, previous methods are not fully applicable to solving problems possessing all types of constraint landscapes and are only superior for a certain type of problem. Thus, in this paper, a novel dynamic-multi-task-assisted constrained multi-objective optimization algorithm, termed DTCMO, is proposed, and three dynamic tasks are involved. The main task approaches the constrained Pareto front by adding new constraints dynamically. Two auxiliary tasks are devoted to exploring the unconstrained Pareto front and the constrained Pareto front with dynamically changing constraint boundaries, respectively. In addition, the first auxiliary task stops the evolution automatically after reaching the unconstrained Pareto front, avoiding the waste of subsequent computational resources. A series of experiments are conducted with eight mainstream algorithms on five benchmark problems, and the results confirm the generality and superiority of DTCMO.
与普通的多目标优化问题相比,约束多目标优化问题需要额外考虑约束的处理。最近,人们提出了许多约束多目标进化算法,以协调约束满足与目标优化之间的关系。值得注意的是,多任务进化机制也被用于解决约束多目标问题,并经常取得显著成果。然而,以往的方法并不完全适用于解决具有所有类型约束景观的问题,而只是对某一类问题具有优势。因此,本文提出了一种新颖的动态多任务辅助约束多目标优化算法,称为 DTCMO,涉及三个动态任务。主要任务通过动态添加新的约束条件来接近约束帕累托前沿。两个辅助任务分别用于探索无约束帕累托前沿和约束边界动态变化的约束帕累托前沿。此外,第一个辅助任务在到达无约束帕累托前沿后自动停止演化,避免了后续计算资源的浪费。我们在五个基准问题上用八种主流算法进行了一系列实验,结果证实了 DTCMO 的通用性和优越性。

Keywords https://linux.do/t/topic/111737

Constrained multi-objective optimization
Dynamic task
Evolutionary algorithm
Multi-task

受限多目标优化动态任务进化算法多任务

1. Introduction https://linux.do/t/topic/111737

When multiple conflicting objectives need to attain relative optimality while also satisfying a set of constraints, such issues are referred to as constrained multi-objective optimization problems (CMOPs) [1]. Many real-world challenges, such as low-carbon energy savings [2], flexible shop scheduling [3], and transport scheduling [4], contain constraints. These real-world issues are the region of CMOPs essentially. In general, CMOPs consist of the objective function, inequality constraints, and equality constraints, which are defined as follows:(1)MinimizeF(x)={f1(x),f2(x),,fM(x)}subjecttoxSgi(x)0,i=1,...,phj(x)=0,j=p+1,...,qwhere F(x) consists of M objective functions and x=(x1,x2,...,xD) is a D-dimensional decision vector. The following relationship exists between them: SRD and F(x)RM. g(x) and h(x) denote p inequality constraints and (qp) equality constraints, respectively.
当多个相互冲突的目标需要在满足一系列约束条件的同时达到相对最优时,这类问题被称为约束多目标优化问题(CMOPs)[1]。现实世界中的许多挑战,如低碳节能 [2]、灵活的车间调度 [3] 和运输调度 [4],都包含约束条件。这些现实问题本质上就是 CMOPs 的研究领域。一般来说,CMOPs 由目标函数、不等式约束和等式约束组成,其定义如下: (1)MinimizeF(x)={f1(x),f2(x),,fM(x)}subjecttoxSgi(x)0,i=1,...,phj(x)=0,j=p+1,...,q 其中 F(x)M 个目标函数组成, x=(x1,x2,...,xD)D 维决策向量。它们之间存在以下关系: SRDF(x)RMg(x)h(x) 分别表示 p 不等式约束和 (qp) 等式约束。

For a given CMOP, the degree of violation of each constraint can be noted as CVj(x) which is expressed mathematically as follows:(2)CVj(x)={max{0,gj(x)},j=1,...,pmax{0,|hj(x)|ϕ},j=p+1,...,qwhere ϕ is typically defined as a tiny positive number e.g. 10−4 to relax the constraints of the equation.
对于给定的 CMOP,每个约束条件的违反程度可记作 CVj(x) ,其数学表达式如下: (2)CVj(x)={max{0,gj(x)},j=1,...,pmax{0,|hj(x)|ϕ},j=p+1,...,q 其中 ϕ 通常定义为一个极小的正数,如 10 −4 以放松等式的约束。

After calculating the CVj(x) for each constraint, one can proceed to calculate the total constraint violation CV of x by using the following equation:(3)CV(x)=j=1qCVj(x)
在计算出每个约束条件的 CVj(x) 后,我们就可以利用下面的公式计算出 x 的总违反约束条件 CV(3)CV(x)=j=1qCVj(x)

For multi-objective optimization problems (MOPs), the Pareto optimal solution set is a set of non-dominated solutions obtained by optimizing multiple objectives with well-convergence and diversity. These solutions constitute the unconstrained Pareto front (UPF) in the objective space. Unlike multi-objective optimization problems, the feasible solutions in CMOPs are redefined as the undominated solutions that satisfy all equality constraints and inequality constraints at the same time, i.e., CV=0. Conversely, solutions are infeasible whenever one of the constraints is not satisfied. The mapping of the feasible Pareto optimal solution set in the objective space constitutes the constrained Pareto front (CPF). The ultimate goal of solving constrained problems is to obtain a well-distributed CPF.
对于多目标优化问题(MOPs)而言,帕累托最优解集是通过优化具有良好收敛性和多样性的多个目标而获得的一组非支配解。这些解构成目标空间中的无约束帕累托前沿(UPF)。与多目标优化问题不同,CMOPs 中的可行解被重新定义为同时满足所有相等约束和不等式约束的非支配解,即 CV=0 。反之,只要有一个约束条件不满足,解就是不可行的。可行的帕累托最优解集在目标空间的映射构成了约束帕累托前沿(CPF)。解决约束问题的最终目标是获得分布良好的 CPF。

Numerous multi-objective evolutionary algorithms (CMOEAs) have been devised by researchers to solve CMOPs. The goal of these algorithms is to find solutions with better feasibility by constraint handling techniques. Commonly used constraint handling techniques include the penalty function method [5], the constraint dominance principle [6] and the ε-constraint method [7]. Although these algorithms based on can cope with some simple problems, these approaches place too much emphasis on the feasibility of solutions. It may lead to the loss of population diversity and failure to provide a collection of well-distributed feasible solutions. To address this challenge, researchers discover that the sensible use of UPF information can aid in population evolution. Thus, multi-stage-based CMOEAs have been proposed. These algorithms gather relevant information from UPF, and assist the evolution of the late. However, this kind of algorithm also has some shortcomings, when the UPF and CPF are far away from each other or the overlap rate is low, the information of the UPF is of very little help to the solution, and may even cause some unnecessary waste of computational resources.
研究人员设计了许多多目标进化算法(CMOEAs)来解决 CMOP。这些算法的目标是通过约束处理技术找到可行性更好的解决方案。常用的约束处理技术包括惩罚函数法[5]、约束支配原理[6]和 ε - 约束法[7]。虽然这些基于的算法可以处理一些简单的问题,但这些方法过于强调解的可行性。这可能会导致种群多样性的丧失,无法提供分布良好的可行解决方案集合。为了应对这一挑战,研究人员发现,合理利用 UPF 信息有助于种群进化。因此,人们提出了基于多阶段的 CMOEA。这些算法从 UPF 中收集相关信息,帮助后期演化。然而,这种算法也存在一些缺陷,当 UPF 与 CPF 相距较远或重叠率较低时,UPF 的信息对求解的帮助很小,甚至会造成一些不必要的计算资源浪费。

To further optimize the solution process, the new idea of applying evolutionary multi-task (EMT) [8] optimization for solving CMOPs has attracted a lot of attention from the community. The primary principle of EMT, as the name implies, is to optimize multiple tasks in parallel and transfer certain useful knowledge between the tasks to increase the diversity of the population. Based on the benefits of EMT, the researchers find that it is possible to assist the solution of the main task by creating auxiliary tasks. Auxiliary tasks are created via the main task and are used for simple problems that do not contain constraints or slack constraints typically. The existence of auxiliary tasks can filter out some infeasible solutions that contain useful information, and then assist the main task in learning such useful information through inter-task knowledge transfer techniques. Based on this idea, many up-to-date CMOEAs facilitate the solution of CMOPs by creating auxiliary tasks. MTCMO [9] adopts the ε-constraint approach to relax the restrictions on constraints imposed by auxiliary tasks. CEMTFB [10], in turn, two auxiliary tasks are designed for infeasible solutions to provide more effective information for the main task.
为了进一步优化求解过程,应用进化多任务(EMT)[8] 优化法求解 CMOP 的新思路引起了社会各界的广泛关注。顾名思义,EMT 的主要原理是并行优化多个任务,并在任务之间转移某些有用的知识,以增加群体的多样性。基于 EMT 的优势,研究人员发现可以通过创建辅助任务来协助解决主要任务。辅助任务是通过主任务创建的,通常用于不包含约束或松弛约束的简单问题。辅助任务的存在可以筛选出一些包含有用信息的不可行解,然后通过任务间知识转移技术帮助主任务学习这些有用信息。基于这一思想,许多最新的 CMOEA 通过创建辅助任务来促进 CMOP 的求解。MTCMO [9]采用 ε - 约束方法来放宽辅助任务的约束限制。CEMTFB [10]则针对不可行解设计了两个辅助任务,为主要任务提供更有效的信息。

In the idealized EMT, suitable auxiliary tasks are first constructed according to the problem requirements, and the auxiliary tasks evolve in parallel with the main task, and the tasks promote each other and learn from one another, so as to help the main task to achieve the optimal solution. However, the actual situation is much more complicated. The performance of the algorithm will be degraded instead if auxiliary tasks are constructed arbitrarily or multiple tasks are simply stacked. Therefore, how to create auxiliary tasks, what evolutionary strategies are adopted by the main task and auxiliary tasks respectively, and how to communicate among multiple tasks effectively are the key issues we need to consider. Existing EMT-based algorithms do not fully address these issues and are unable to obtain high-quality solution sets for all problems with different constraint landscapes, motivating us to design more efficient algorithms to meet the needs of diverse problems. Thus, based on the EMT framework, a novel CMOEA with a dynamic task mechanism, namely DTCMO, is designed to address these critical issues efficiently. Furthermore, in optimization problems with different constraint landscapes, certain constraints are dominant while certain constraints are redundant. To spend more computational resources on the higher priority constraints, three dynamic tasks are constructed in DTCMO to rationally utilize the relationships between the constraints. The main contributions are as follows:
在理想化的 EMT 中,首先根据问题要求构建合适的辅助任务,辅助任务与主任务并行演进,任务之间相互促进、相互学习,从而帮助主任务实现最优解。然而,实际情况要复杂得多。如果任意构建辅助任务或简单堆叠多个任务,算法的性能反而会下降。因此,如何创建辅助任务,主任务和辅助任务分别采用何种进化策略,以及如何在多个任务之间进行有效通信,是我们需要考虑的关键问题。现有的基于 EMT 的算法并不能完全解决这些问题,无法为所有具有不同约束景观的问题获得高质量的解集,这促使我们设计更高效的算法来满足不同问题的需求。因此,在 EMT 框架的基础上,我们设计了一种具有动态任务机制的新型 CMOEA,即 DTCMO,以有效解决这些关键问题。此外,在具有不同约束条件的优化问题中,某些约束条件是主要的,而某些约束条件则是多余的。为了将更多计算资源用于优先级较高的约束上,DTCMO 构建了三个动态任务,以合理利用约束之间的关系。主要贡献如下:

  • Based on the idea of EMT, two auxiliary tasks are designed to assist the evolution of the main task. Three populations P1,P3 and P3 solve for these three tasks with constraint prioritization, constraint ignoring and ε-constraint techniques, respectively.
    根据 EMT 的思想,设计了两个辅助任务来协助主任务的演化。三个种群 P1P3P3 分别采用约束优先、约束忽略和 ε - 约束技术来解决这三个任务。

  • A novel dynamic task mechanism is designed to work on three populations. Specifically, P1 processes the constraints with higher priority first and dynamically adds the next constraint with the highest current priority when appropriate. P2 only optimizes the objective, it stops the evolution adaptively after converging to UPF, to save computational resources to a certain extent. For P3, retaining the promising infeasible solutions by shrinking the constraint boundaries dynamically.
    我们设计了一种新颖的动态任务机制,可在三个群体中发挥作用。具体来说, P1 首先处理优先级较高的约束条件,并在适当的时候动态添加当前优先级最高的下一个约束条件。 P2 只优化目标,在收敛到 UPF 后自适应地停止演化,以在一定程度上节省计算资源。对于 P3 ,通过动态收缩约束边界来保留有希望的不可行解。

  • DTCMO is divided into two stages: exploration and exploitation. In the exploration stage, three populations focus on the exploration of CPF, UPF and relaxed constraints CPF, respectively. Whereas, the exploitation stage favors the collection of solutions with higher feasibility. Only P1 and P3 are allowed to continue to evolve. Additionally, the superior performance of DTCMO is analyzed by experimental comparisons and tested on a real-world problem.
    DTCMO 分为两个阶段:探索和利用。在探索阶段,三个群体分别侧重于探索 CPF、UPF 和放松约束 CPF。而开发阶段则倾向于收集可行性较高的解决方案。只有 P1P3 被允许继续演化。此外,还通过实验对比分析了 DTCMO 的优越性能,并在实际问题上进行了测试。

The remainder of the paper consists of the following subsections. Section 2 lists some recent research results and discusses the motivation for this paper. A detailed description of the main parts of DTCMO is provided in Section 3. The relevant experimental settings are set in Section 4. To verify the DTCMO's generality and competitiveness, a series of experiments are devised in Section 5. Finally, Section 6 concludes and gives some potential future research directions.
本文的其余部分包括以下几个小节。第 2 节列举了近期的一些研究成果,并讨论了本文的写作动机。第 3 节详细介绍了 DTCMO 的主要部分。第 4 节介绍了相关的实验设置。为了验证 DTCMO 的通用性和竞争力,第 5 节设计了一系列实验。最后,第 6 节得出结论,并给出了一些潜在的未来研究方向。

2. Related work 2.相关工作

2.1. Existing CMOEAs 2.1.现有的 CMOEAs

The pre-existing CMOEAs can be classified into three categories depending on the strategy adopted.
根据所采取的战略,现有的 CMOEA 可分为三类。

1) Traditional CMOEAs: The constraint dominance principle, ε methods and muti-ranking are commonly adopted in traditional constraint handling techniques to solve CMOPs. To prioritize feasible solutions while ensuring the diversity of the populations, Fan et al. [11] combined the constraint dominance principle with the entrainment information of the populations. Thses methods are also applicable to the solution of constrained many-objective optimization problems (CMaOPs). Jain et al. [12] employed the constraint dominance principle as a constraint-handling technique to solve CMaOPs. Compared to it, the ε-method [7] relaxes the feasibility requirement. The pull stage of PPS [13] employed an improved ε method to help the population converge from UPF to CPF. Zhu et al. [14] incorporated the ε method into the detection-escape strategy to help the population jump out of this region by enhancing diversity. In addition, Chen et al. [15] combined the ε-method and the decomposition method. At the same time, the diversity of the population was ensured by the boundary point maintenance mechanism. Jiao et al. [16] extended the ε-method to the high-dimensional space. The proposed DCNSGA-III retained the solutions satisfying the ε-constraint to the next generation. But ε needs to be set artificially and its adaptivity still requires to be improved. Also for the high-dimensional problem, Zhou et al. [17] extended CMOEAs based on multiple rankings. The proposed tri-goal framework TiGE-2 measures the ordering of convergence, diversity and feasibility, respectively, to obtain solutions with better overall performance. It is demonstrated that TiGE-2 can be utilized to solve CMaOPs efficiently. Therefore, the approach of adopting three indicators as the three objectives is equally feasible. However, the multi-ranking-based approach may lead to a large number of infeasible solutions remaining at the final stage. This is due to the fact that multi-ranking-based methods require different weights based on convergence, diversity and feasibility, which allows some infeasible solutions with good convergence and diversity to be retained as well.
1) 传统的 CMOEAs:传统的约束处理技术通常采用约束支配原理、 ε 方法和多排序法来求解CMOEA。为了在保证种群多样性的前提下优先考虑可行解,Fan 等人[11]将约束支配原理与种群的诱导信息相结合。这些方法也适用于受约束多目标优化问题(CMaOPs)的求解。Jain 等人[12]采用约束支配原理作为约束处理技术来求解 CMaOPs。与之相比, ε 方法[7]放宽了可行性要求。PPS[13] 的拉动阶段采用了改进的 ε 方法,帮助群体从 UPF 收敛到 CPF。Zhu 等人[14] 将 ε 方法纳入检测-逃逸策略,通过增强多样性帮助种群跳出这一区域。此外,Chen 等人[15] 结合了 ε 方法和分解方法。同时,通过边界点维护机制确保种群的多样性。Jiao 等人[16] 将 ε 方法扩展到了高维空间。提出的 DCNSGA-III 将满足 ε 约束的解保留到下一代。但 ε 需要人为设置,其适应性仍有待提高。同样针对高维问题,Zhou 等人[17] 基于多重排序对 CMOEA 进行了扩展。提出的三目标框架 TiGE-2 分别衡量收敛性、多样性和可行性的排序,以获得整体性能更好的解决方案。研究表明,TiGE-2 可用于高效求解 CMaOPs。 因此,采用三个指标作为三个目标的方法同样可行。然而,基于多重排序的方法可能会导致大量不可行的解决方案留在最后阶段。这是由于基于多重排序的方法需要根据收敛性、多样性和可行性确定不同的权重,这使得一些具有良好收敛性和多样性的不可行方案也被保留下来。

2) Multi-stage-based CMOEAs: PPS [13], as the most classical two-stage algorithm, considered no constraints in the push stage, and in the pull stage, the solutions found in the push stage distributed over the UPF are converged towards the CPF. To deal with the constraints in the objective space and decision space simultaneously, Liu et al. [18] re-modeled a CMOP as a multiple single-objective constrained optimization problem in the first stage and continued the solution in the second stage by a specific CMOEA. To preserve the feasible solutions found with good convergence and good diversity, Yu et al. [19] maintained an archive of the solutions found in both stages. Artificially setting the conditions for stage switching has some drawbacks, fixing the evolutionary time of each stage and making it impossible to adaptively move to the next stage based on the evolution of the population. To achieve automatic stage switching, Tian et al. [20] selected different evolution stages according to the characteristics of the population adaptively. Ma et al. [21] added a new constraint in each stage, which allows complex constraints to be handled one by one, greatly reducing the difficulty of solving CMOPs. Also placing importance on constraint prioritization is C3M [22]. As the name suggests, C3M consists of three stages. The second stage dealt with all the constraints in order of constraint priority while removing some unimportant constraints. Dong et al. [23] placed different preferences for solution performance at different stages of the evolution process. Similar to it, Yu et al. [24] placed different emphases on objective optimization and constraint satisfaction in different stages. When to perform stage transitions and how to utilize the useful information obtained in the previous stage are future research directions for researchers. To this end, the algorithm proposed in this paper fills this research gap. The algorithm automatically enters the next stage when the population remains largely stable and mostly viable, and the implementation details of the stage transitions are shown in Section 3.3.
2) 基于多阶段的 CMOEA:PPS [13] 作为最经典的两阶段算法,在推阶段不考虑任何约束条件,在拉阶段将推阶段找到的分布在 UPF 上的解向 CPF 收敛。为了同时处理目标空间和决策空间中的约束,Liu 等人[18]在第一阶段将 CMOP 重新建模为多个单目标约束优化问题,并在第二阶段通过特定的 CMOEA 继续求解。为了保留收敛性和多样性良好的可行解,Yu 等人[19]保留了两个阶段的解的档案。人为设定阶段切换条件有一些缺点,即固定了每个阶段的演化时间,无法根据种群的演化自适应地进入下一阶段。为了实现阶段的自动切换,Tian 等人[20]根据种群的特点自适应地选择了不同的进化阶段。Ma 等人[21]在每个阶段都增加了一个新的约束,这样就可以逐个处理复杂的约束,大大降低了 CMOP 的求解难度。同样重视约束优先级的还有 C3M [22]。顾名思义,C3M 包括三个阶段。第二阶段按照约束优先级的顺序处理所有约束,同时删除一些不重要的约束。Dong 等人[23]在演化过程的不同阶段对解决方案的性能有不同的偏好。与之类似,Yu 等人[24] 在不同阶段对目标优化和约束满足也有不同侧重。 何时进行阶段转换以及如何利用前一阶段获得的有用信息,是研究人员未来的研究方向。为此,本文提出的算法填补了这一研究空白。该算法在种群保持基本稳定和大部分存活时自动进入下一阶段,阶段转换的实现细节见第 3.3 节。

3) Multi-population-based CMOEAs: To produce higher quality solutions, information about various types of solutions can be collected by different populations. Li et al. [25] maintained both CA and DA archives, which preserve the solutions with superior convergence and diversity, respectively. The strong cooperation between CA and DA is adopted to share offspring in mating and environmental selection. Nevertheless, the strong cooperation interferes with their respective evolutionary directions and reduces the algorithm's performance. To solve this challenge, Tian et al. [26] suggested a novel co-evolutionary CMOEA, called CCMO. CCMO is designed with two populations for solving the original and auxiliary problems, and information sharing is achieved through the weak cooperation mechanism. Due to its weak cooperation mechanism, two populations share offspring only in environmental selection, which makes each population relatively independent and can get to the optimal solution of their respective optimization problems, and then share the offspring produced by all populations. c-DPEA based on dual populations was proposed by Ming et al. [27]. In this algorithm, one population retained high-quality infeasible solutions by the adaptive penalty function. While the other population preferred the solutions with better feasibility. BiCo [28] also maintained two populations at the same time, with the difference that two populations guided the convergence of the populations to the CPF from the feasible and infeasible regions, respectively. Peng et al. [29] created two populations for exploring the feasible region as well as the whole problem space, respectively. Ming et al. [30] created three populations, which were used for the solution of the original CMOP, MOP, and the relaxed CMOP, respectively. In addition, Sun et al. [31] divided the population into two sub-populations based on the CV values, which were dedicated to the solution of the relaxed CPF and original CPF, respectively.
3) 基于多人群的 CMOEA:为了生成更高质量的解,可以通过不同种群收集各类解的信息。Li等人[25]同时保留了CA和DA档案,它们分别保存了具有卓越收敛性和多样性的解。CA 和 DA 之间的强合作是为了在交配和环境选择中共享后代。然而,强合作会干扰各自的进化方向,降低算法的性能。为了解决这一难题,Tian 等人[26]提出了一种新的协同进化 CMOEA,称为 CCMO。CCMO 设计了两个种群分别解决原始问题和辅助问题,并通过弱合作机制实现信息共享。由于其弱合作机制,两个种群只在环境选择时共享后代,这使得每个种群都相对独立,可以达到各自优化问题的最优解,然后共享所有种群产生的后代。 Ming 等人[27]提出了基于双种群的 c-DPEA。在该算法中,一个种群通过自适应惩罚函数保留高质量的不可行解。而另一个种群则优先选择可行性更好的解。BiCo[28]也同时保留了两个种群,不同之处在于两个种群分别引导种群从可行区域和不可行区域向 CPF 收敛。Peng 等人[29] 创建了两个种群,分别用于探索可行区域和整个问题空间。Ming等人[30]创建了两个种群,分别用于探索可行区域和整个问题空间。 [30]创建了三个种群,分别用于原始 CMOP、MOP 和松弛 CMOP 的求解。此外,Sun 等人[31]根据 CV 值将种群分为两个子种群,分别用于松弛 CPF 和原始 CPF 的求解。

In general, multi-population-based methods usually obtain the final population by creating two populations to explore feasible and infeasible solutions separately. The infeasible solution obtained is used to assist in exploring all feasible solutions in the objective space. However, the infeasible solutions obtained do not provide valid information throughout the evolutionary process and their assistance to the main population will be greatly reduced. To solve this issue, the DTCMO proposed in this paper creates three dynamically changing tasks, which is described in detail in Section 3.
一般来说,基于多群体的方法通常通过创建两个群体来分别探索可行解和不可行解,从而获得最终群体。获得的不可行解用于帮助探索目标空间中的所有可行解。然而,所获得的不可行解在整个进化过程中并不能提供有效信息,其对主种群的帮助也会大大减少。为解决这一问题,本文提出的 DTCMO 创建了三个动态变化的任务,第 3 节将对此进行详细介绍。

2.2. Evolutionary muti-task
2.2.多任务进化

A new evolutionary search paradigm, EMT optimization, was first proposed by Gupta et al. [32] in 2015. For solving more complex CMOPs, compared to multi-stage and multi-population-based CMOEAs, the EMT technique demonstrates superior performance in terms of convergence speed and diversity. Thus, EMT-based CMOEAs have attracted much attention from the community in recent years and achieved remarkable results. In EMT, it is necessary to design one or more auxiliary tasks that are different from but related to the main task to achieve the auxiliary solution. Different tasks correspond to the search of different decision spaces. The primary goal of solving using EMT is to obtain information about various features by optimizing both the main task and auxiliary tasks. The useful information is transferred among tasks, so as to enhance the global search ability of the main task and improve the performance of the algorithm.
2015 年,Gupta 等人[32] 首次提出了一种新的进化搜索范式--EMT 优化。对于求解更复杂的 CMOP,与基于多阶段和多群体的 CMOEA 相比,EMT 技术在收敛速度和多样性方面表现出更优越的性能。因此,基于 EMT 的 CMOEA 近年来备受业界关注,并取得了令人瞩目的成果。在 EMT 中,需要设计一个或多个与主任务不同但相关的辅助任务来实现辅助解。不同的任务对应搜索不同的决策空间。使用 EMT 求解的主要目标是通过优化主任务和辅助任务来获取各种特征信息。有用信息在任务间传递,从而增强主任务的全局搜索能力,提高算法性能。

CMOEAs based on multi-population usually solve CMOPs by creating different populations, while the idea of solving them by employing the EMT mechanism is related to multiple tasks. EMT is employed to solve these problems by initially transforming the optimization of a given constrained problem into the optimal solution of two or more interrelated tasks. The ultimate goal of solving by EMT is to transfer potentially superior solutions between different tasks and solve multiple related tasks simultaneously. Nevertheless, the real application of EMT ideas to solve CMOPs is less researched and has only been proposed successively in the last two years. EMT was first employed by Qiao et al. [33] to design an evolutionary multi-task optimization framework, namely EMCMO. To enhance the design of the auxiliary task, in the same year, the team also proposed the MTCMO algorithm [9]. In MTCMO, the ε method was adopted to design auxiliary tasks. The constraint boundaries of the auxiliary tasks were reduced dynamically with the increase of iterations, which provides more diversified information to the main task. To share high-quality information among multiple tasks, Chen et al. [34] introduced the idea of deep learning in the process of optimizing the solution. High-quality solutions were selected for knowledge migration by transfer rank and KNN model. In addition, to reduce the possibility of negative migration occurring, Liang et al. [35] introduced the subspace alignment mechanism. To better assist the main task to approximate the CPF, Ming et al. [36] designed three tasks to solve CMOP, MOP and CMOP with relaxation constraints, respectively. Similarly, Qiao et al. [37] created two auxiliary tasks as well. The global diversity and local diversity of the main task were guaranteed by the global auxiliary tasks and local auxiliary tasks, respectively. To make full use of the information from different tasks, a new two-task-based optimization framework called DBEMTO [38] was designed by the team. The information was exchanged by selecting appropriate individuals between tasks by the adaptive strategy. Further, to apply the idea of EMT to large-scale CMOPs, Liu et al. [39] designed discriminative reconstruction network models. Simultaneous solution of multiple large-scale optimization problems was achieved by training the obtained model.
基于多群体的 CMOEA 通常通过创建不同的群体来解决 CMOP,而利用 EMT 机制解决 CMOP 的想法则与多任务有关。采用 EMT 解决这些问题时,首先要将给定约束问题的优化转化为两个或多个相互关联任务的最优解。利用 EMT 解决问题的最终目的是在不同任务之间转移潜在的最优解,并同时解决多个相关任务。然而,真正将 EMT 思想应用于解决 CMOP 的研究较少,近两年才陆续有人提出。Qiao 等人[33]首次采用 EMT 设计了进化多任务优化框架,即 EMCMO。为了加强辅助任务的设计,同年,该团队还提出了 MTCMO 算法[9]。在 MTCMO 中,采用了 ε 方法来设计辅助任务。辅助任务的约束边界随着迭代次数的增加而动态缩小,从而为主任务提供了更多样化的信息。为了在多个任务之间共享高质量信息,Chen 等人[34]在优化解决方案的过程中引入了深度学习的思想。通过转移等级和 KNN 模型选择高质量的解决方案进行知识迁移。此外,为了降低负迁移发生的可能性,Liang 等人[35]引入了子空间对齐机制。为了更好地帮助主任务逼近 CPF,Ming 等人[36]设计了三个任务,分别求解 CMOP、MOP 和带松弛约束的 CMOP。同样,Qiao 等人[37] 也创建了两个辅助任务。 全局辅助任务和局部辅助任务分别保证了主任务的全局多样性和局部多样性。为了充分利用来自不同任务的信息,研究小组设计了一种新的基于双任务的优化框架,称为 DBEMTO [38]。通过自适应策略在任务间选择合适的个体来交换信息。此外,为了将 EMT 的思想应用于大规模 CMOP,Liu 等人[39] 设计了判别重构网络模型。通过训练获得的模型,实现了多个大规模优化问题的同时求解。

EMT-based CMOEAs exhibit excellent performance when the CPF and UPF overlap is low or even completely disjoint. However, the application of EMT to solve complex CMOPs is still in its infancy, and there are still many research gaps in this area. Many issues need to be considered by researchers in future studies, such as how to create reasonable auxiliary tasks and how to reduce the effect of negative migration.
当 CPF 和 UPF 重叠较少甚至完全不相交时,基于 EMT 的 CMOEA 表现出卓越的性能。然而,应用 EMT 解决复杂 CMOP 仍处于起步阶段,该领域仍存在许多研究空白。在未来的研究中,研究人员需要考虑很多问题,例如如何创建合理的辅助任务,如何减少负迁移的影响等。

2.3. Motivation 2.3.动机

Existing CMOEAs usually use multi-stage or multi-population approaches to solve CMOPs and perform well on some simple test problems. Nevertheless, existing multi-stage and multi-population-based CMOEAs are not ideal when faced with problems with complex constraint landscapes, especially when the overlap between CPFs and UPFs is low. In addition, faced with optimization problems with different CPFs, the existing algorithms are not able to produce superior solutions for all tested problems and are poorly adaptive. For this end, two-stage-based PPS and two-population-based CCMO are chosen for experimental validation. To demonstrate the effects of CMOPs with different constraint landscapes on the existing CMOEAs, MW5 and MW13 are selected as test problems. The feasible region of MW5 is discrete and irregularly shaped, and its CPF consists of 16 discrete points. This requires a high level of population diversity. Whereas MW13 has two discrete bar-shaped feasible regions with a narrow feasible region area and a large infeasible region between them. It requires a strong ability of the population to cross infeasible regions. 2000 iterations are performed for PPS and CCMO, respectively. The population distributions obtained are shown in Fig. 1, Fig. 2.
现有的 CMOEA 通常采用多阶段或多群体方法来求解 CMOP,并在一些简单的测试问题上表现良好。然而,现有的基于多阶段和多群体的 CMOEA 在面对复杂约束景观的问题时并不理想,尤其是当 CPF 与 UPF 重叠较少时。此外,面对具有不同 CPF 的优化问题,现有算法无法为所有测试问题提供优越的解决方案,而且适应性较差。为此,我们选择了基于两阶段的 PPS 和基于双人口的 CCMO 进行实验验证。为了证明具有不同约束条件的 CMOP 对现有 CMOEA 的影响,我们选择了 MW5 和 MW13 作为测试问题。MW5 的可行区域离散且形状不规则,其 CPF 由 16 个离散点组成。这就需要高度的群体多样性。而 MW13 有两个离散的条形可行区域,可行区域面积较窄,两者之间的不可行区域面积较大。这就要求种群有很强的穿越不可行区域的能力。分别对 PPS 和 CCMO 进行 2000 次迭代。得到的种群分布如图 1 和图 2 所示。

Fig 1
  1. Download: Download high-res image (236KB)
    下载:下载高清图片 (236KB)
  2. Download: Download full-size image
    下载:下载全尺寸图片

Fig. 1. Solutions obtained by PPS at different stages on MW5 and MW13.
图 1.PPS 在 MW5 和 MW13 上不同阶段获得的溶液。

Fig 2
  1. Download: Download high-res image (317KB)
    下载:下载高清图片 (317KB)
  2. Download: Download full-size image
    下载:下载全尺寸图片

Fig. 2. Solutions obtained by CCMO at different stages on MW5 and MW13.
图 2.CCMO 在 MW5 和 MW13 上不同阶段获得的溶液。

Obviously, the multi-stage-based PPS fails to obtain a set of uniformly distributed non-dominated solutions to problems with both discrete feasible regions and large infeasible regions. The main reason for this phenomenon lies in the incorrect timing of the stage transitions. PPS enters the pull stage when the rate of change of the ideal and minimum points is less than a set threshold. However, it can be seen from Fig. 1(a) that the obtained solution is considered to satisfy the stage transition condition at a far distance from UPF. The unreasonable judgment prevents the PPS from converging to the desired UPF in the push stage, thereby reducing the performance of the algorithm greatly. In Fig. 1(b), PPS falls into a local optimum and fails to explore all feasible regions in MW5, with poor diversity performance. The same problem occurs on MW13. In this scenario, PPS cannot utilize the information from UPF effectively. Thus, the solutions obtained have poor convergence and diversity.
显然,对于既有离散可行区域又有较大不可行区域的问题,基于多阶段的 PPS 无法获得一组均匀分布的非支配解。造成这种现象的主要原因在于阶段转换的时机不正确。当理想点和最小点的变化率小于设定阈值时,PPS 就会进入拉动阶段。然而,从图 1(a)中可以看出,在距离 UPF 较远的地方,得到的解被认为满足阶段转换条件。这种不合理的判断使得 PPS 无法在推动阶段收敛到所需的 UPF,从而大大降低了算法的性能。在图 1(b) 中,PPS 在 MW5 中陷入局部最优,无法探索所有可行区域,分集性能较差。同样的问题也出现在 MW13 上。在这种情况下,PPS 无法有效利用 UPF 的信息。因此,得到的解的收敛性和多样性都很差。

For two-population-based CCMO, the auxiliary population P2 is dedicated to the solution of unconstrained MOPs, aiming to help the main population P1 to cross the infeasible region. To distinguish the roles played by different populations at different times of evolution easily, the main and auxiliary populations are denoted by red and green dots, respectively. From Fig. 2, it can be seen that P2 converges towards UPF over the evolution process and nearly matches UPF perfectly at the late stages of the iteration. For MW5, the CPF is a component of UPF. In this instance, the solution obtained by P2 which is uniformly distributed on the UPF can provide plenty of effective information for P1. On the contrary, for MW13 where the CPF and UPF overlap to a lesser extent, the solutions obtained by CCMO are not ideal. Although the presence of P2 can drive P1 to cross the larger infeasible region in MW13 and find two narrow feasible regions successfully, the information obtained by P2 fails to assist P1 further after it crosses CPF and continues to converge to the UPF. Additionally, P2 remains unchanged at the late stage, which may lead to the waste of resources.
对于基于双种群的 CCMO,辅助种群 P2 专门用于解决无约束澳门威尼斯人官网程,旨在帮助主种群 P1 穿越不可行区域。为了便于区分不同种群在不同演化时期所扮演的角色,主种群和辅助种群分别用红点和绿点表示。从图 2 可以看出, P2 在演化过程中逐渐向 UPF 靠拢,在迭代后期几乎与 UPF 完全吻合。对于 MW5,CPF 是 UPF 的一个组成部分。在这种情况下,在 UPF 上均匀分布的 P2 所得到的解可以为 P1 提供大量有效信息。相反,对于 CPF 和 UPF 重叠程度较低的 MW13,CCMO 得到的解并不理想。虽然 P2 的存在能促使 P1 穿过 MW13 中较大的不可行区域,并成功找到两个狭窄的可行区域,但 P2 所获得的信息在 P1 穿过 CPF 并继续向 UPF 收敛后,就无法进一步帮助 P1 了。此外, P2 在后期阶段保持不变,可能会造成资源浪费。

The above analyses demonstrate the ineffective of multi-stage and multi-population-based methods in solving CMOPs with non-overlapping CPF and UPF. These phenomena show that when the problem is complex and the correlation between CPF and UPF is small, it is impractical to adopt a simple strategy. Thus, EMT is required to be introduced to solve these CMOPs. The main idea of EMT is to tackle an issue by creating several auxiliary tasks and solving the problem from different perspectives. To better apply EMT to solve CMOPs, the following three core issues need to be addressed:
上述分析表明,基于多阶段和多群体的方法在求解 CPF 和 UPF 不重叠的 CMOP 时效果不佳。这些现象表明,当问题复杂且 CPF 和 UPF 的相关性较小时,采用简单的策略是不切实际的。因此,需要引入 EMT 来解决这些 CMOP。EMT 的主要思想是通过创建多个辅助任务,从不同角度解决问题。为了更好地应用 EMT 解决 CMOP,需要解决以下三个核心问题:

  • How to create different tasks?
    如何创建不同的任务?

  • What is the role of auxiliary tasks in the evolution process and how to assist the evolution of the main task?
    辅助任务在进化过程中的作用是什么,如何协助主要任务的进化?

  • How to achieve effective information exchange between different tasks?
    如何实现不同任务之间的有效信息交流?

To address these issues, existing EMT-based CMOEAs typically construct an auxiliary task that disregards any constraints and assists the main task to cross some infeasible regions through the evolution of the auxiliary task, and enable the exchange of information between tasks via offspring sharing. While these algorithms can perform well on partially constrained problems, they are not friendly to complex optimization problems where the feasible regions are narrower and more discrete. This is because constructing a single auxiliary task that does not consider any constraints cannot analyze the entire topology of the CPF and is prone to falling into local optima. In addition, considering that the existing EMT-based CMOEAs are not applicable to solving different types of CMOPs, the development of CMOEAs with improved generality is a worthwhile research topic.
为了解决这些问题,现有的基于 EMT 的 CMOEA 通常会构建一个辅助任务,不考虑任何约束条件,通过辅助任务的演化来协助主任务跨越一些不可行区域,并通过子任务共享来实现任务间的信息交换。虽然这些算法可以很好地处理部分约束问题,但对于可行区域较窄、离散性较强的复杂优化问题却并不友好。这是因为不考虑任何约束条件的单一辅助任务无法分析 CPF 的整个拓扑结构,容易陷入局部最优。此外,考虑到现有的基于 EMT 的 CMOEA 并不适用于求解不同类型的 CMOP,开发通用性更强的 CMOEA 是一个值得研究的课题。

Hence, to better address the above three issues, the multi-task algorithm with a novel dynamic task mechanism is designed, called DTCMO. The three tasks created by DTCMO are not fixed, and their respective strategies are adjusted during the evolution process adaptively. It means that for CMOPs with different constraint landscapes, to solve them, DTCMO adopts the most suitable strategy automatically. As a result, it shows more superiority and versatility over different types of problems than other EMT-based CMOEAs. The implementation details of the proposed algorithm will be elaborated in the next section.
因此,为了更好地解决上述三个问题,我们设计了具有新型动态任务机制的多任务算法,即 DTCMO。DTCMO 创建的三个任务并不是固定不变的,它们各自的策略会在演化过程中进行自适应调整。这意味着,对于具有不同约束景观的 CMOP,DTCMO 会自动采用最合适的策略进行求解。因此,与其他基于 EMT 的 CMOEA 相比,DTCMO 在解决不同类型的问题时表现出更大的优越性和通用性。下一节将详细介绍该算法的实现细节。

3. Proposed DTCMO 3.拟议的 DTCMO

3.1. The framework of DTCMO
3.1.DTCMO 的框架

To address the first major issue mentioned above, three distinct tasks are constructed and solved using constraint prioritization, constraint ignoring and constraint relaxation techniques respectively. Separate populations, i.e., P1,P2 and P3, are initialized for the three tasks, which are optimized in parallel during the evolution process. For the second problem, a novel dynamic task mechanism is designed to dynamize the constraint functions of the three tasks. Furthermore, to solve the final challenge, a knowledge transfer strategy is employed to achieve the transfer of outstanding individuals between different tasks. Consequently, the proposed dynamic task-based evolutionary multi-task algorithm DTCMO solves the above three problems perfectly. The overall framework of DTCMO is given in Fig. 3. To distinguish the different evolution processes of different populations, the main population P1, P2 without considering constraints, and P3 with changing constraint boundaries dynamically are denoted by red, green, and yellow, respectively. The blue color denotes the same steps of the three populations in the evolution.
为了解决上述第一个主要问题,我们构建了三个不同的任务,并分别使用约束优先、约束忽略和约束放松技术进行求解。三个任务的初始化种群分别为 P1P2P3 ,在演化过程中并行优化。对于第二个问题,设计了一种新颖的动态任务机制来动态调整三个任务的约束函数。此外,为了解决最后一个难题,还采用了知识转移策略,以实现优秀个体在不同任务之间的转移。因此,所提出的基于动态任务的多任务进化算法 DTCMO 完美地解决了上述三个问题。图 3 给出了 DTCMO 的整体框架。为了区分不同种群的不同进化过程,主种群 P1 、不考虑约束条件的 P2 和动态改变约束边界的 P3 分别用红色、绿色和黄色表示。蓝色表示三个种群在演化过程中的相同步骤。

Fig 3
  1. Download: Download high-res image (453KB)
    下载:下载高清图片 (453KB)
  2. Download: Download full-size image
    下载:下载全尺寸图片

Fig. 3. The general framework of DTCMO.
图 3.DTCMO 的总体框架。

The two major stages of DTCMO are demonstrated in Algorithm 1: the exploration stage and the exploitation stage. Firstly, three populations P1,P2 and P3 are initialized according to the three tasks (line 1). The constraint boundary of P3 is initialized as the maximum value of its constraint violation degree (line 3). During the iteration process, the constraint boundary of P3 is updated according to (5) (lines 5–7). Then, the populations enter the exploration stage. The constraint function of each population changes adaptively with the number of iterations (line 9). The population enters the exploitation stage once the stage transition condition is satisfied (line 11). Only the main population P1 and the auxiliary population P3 are involved in this stage, and their information is fully utilized in the environmental selection based on the knowledge transfer strategy. Finally, P1 is output as the final population (line 15).
算法 1 演示了 DTCMO 的两个主要阶段:探索阶段和利用阶段。首先,根据三个任务初始化三个种群 P1P2P3 (第 1 行)。 P3 的约束边界初始化为其约束违反度的最大值(第 3 行)。在迭代过程中,根据 (5) 更新 P3 的约束边界(第 5-7 行)。然后,种群进入探索阶段。每个种群的约束函数随着迭代次数的增加而自适应变化(第 9 行)。一旦满足阶段转换条件,种群即进入开发阶段(第 11 行)。该阶段只涉及主种群 P1 和辅助种群 P3 ,它们的信息将在基于知识转移策略的环境选择中得到充分利用。最后,输出 P1 作为最终种群(第 15 行)。

Algorithm 1. The framework of DTCMO.
算法 1.DTCMO 框架。

Input: N (population size), G (generation limits)
输入 N (种群数量), G (世代限制)
Output: P1 (final population)
输出: P1 (最终人口)
1: Initialize P1,P2,P3;
1: 初始化 P1 , P2 , P3

2: gen=1,state=0,currCons=[1];
2: gen=1 , state=0 , currCons=[1] ;

3: Initialize the parameter ε by P3;
3: 用 P3 初始化参数 ε
4: while genG do
5: if P3 is within the ε-constraint boundary then
5: 如果 P3ε 约束边界内,那么

6: εUpdate ε based on (5);
6: ε 根据 (5) 更新 ε

7: end if 7: 如果结束
8: if state==0 then
9: {P1,P2,P3,state,currCons}Exploration Stage (P1,P2,P3,N,currCons,ε);
9: { P1 , P2 , P3 , state , currCons } 探索阶段 ( P1 , P2 , P3 , N , currCons , ε );

10: else 10: 否则
11: {P1,P3}Exploitation Stage (P1,P3,N,ε);
11: { P1 , P3 } Exploitation Stage ( P1 , P3 , N , ε );

12: end if 12: 如果结束
13: gen=gen+1; 13: gen=gen+1 ;
14: end while 14: 同时结束
15: return P1 15: 返回 P1

3.2. Exploration stage 3.2.探索阶段

The distribution of constrained landscapes is unaware at the start, and a single mode of exploration can result in many feasible regions being unexplored. To solve this issue, exploration by different tasks under different conditions is required to get an overall view of the objective space. The pseudo-code for the exploration stage of DTCMO is given in Algorithm 2. P1,P2 and P3 explore the CPF with single or combined constraints, UPF with ignored constraints, and CPF with relaxation, respectively.
受限景观的分布在一开始是不可知的,单一的探索模式可能会导致许多可行区域未被探索。为了解决这个问题,需要不同任务在不同条件下进行探索,以获得目标空间的全貌。DTCMO 探索阶段的伪代码见算法 2。 P1P2P3 分别探索带有单一或组合约束条件的 CPF、带有忽略约束条件的 UPF 和带有松弛条件的 CPF。

Algorithm 2. Exploration Stage (P1,P2,P3,N,currCons,ε).
算法 2.探索阶段 ( P1 , P2 , P3 , N , currCons , ε ).

Input: P1 (main population), P2 (auxiliary population 1), P3 (auxiliary population 2), N (population size), currCons (the array of constraints currently under consideration), ε (constraint boundary)
输入 P1 (主种群)、 P2 (辅助种群 1)、 P3 (辅助种群 2)、 N (种群数量)、 currCons (当前考虑的约束条件阵列)、 ε (约束条件边界)
Output: P1 (main population), P2 (auxiliary population 1), P3 (auxiliary population 2), state (stage transition), currCons (the array of constraints currently under consideration)
输出: P1 (主种群)、 P2 (辅助种群 1)、 P3 (辅助种群 2)、 state (阶段转换)、 currCons (当前考虑的约束条件阵列)
1: NCCalculate the number of constraints;
1: NC 计算约束条件的数量;

2: CPGet constraint priority;
2: CP 获取约束优先级;

3: {state,addCons,isUPF}Judge the stage transition;
3: { state , addCons , isUPF } 判断阶段转换;

4: if addCons then
5: index=|currCons|+1; 5: index=|currCons|+1 ;
6: currCons=[currCons,CPindex];
6: currCons= [ currCons , CPindex ];

7: end if 7: 如果结束
8: if isUPF then
9: O2=; 9: O2= ;
10: end if 10: 如果结束
11: {O1,O2,O3}Generate offspring of {P1,P2,P3} based on GA and DE/rand-to-best/1/bin;
11: { O1 , O2 , O3 } 基于 GA 和 DE/rand-to-best/1/bin 生成 { P1 , P2 , P3 } 的后代;

12: P1Selection (P1O1O2O3,N,currCons);
12: P1 Selection ( P1O1O2O3 , N , currCons );

13: P2Selection (P2O2O1O3,N,0);
13: P2 Selection ( P2O2O1O3 , N ,0);

14: P3Selection (P3O3O1O2,N,ε);
14: P3 Selection ( P3O3O1O2 ,N, ε );
15: return P1,P2,P3,state,currCons
15: 返回 P1 , P2 , P3 , state , currCons

When the constraint landscape is relatively complex, it is necessary to sort out the impact of each constraint on the population distribution. The constraints that have a greater impact on the population distribution are prioritized, and the constraints that have less or no impact on the population distribution are dealt with last. This helps to reduce the difficulty of solving CMOPs. Inspired by this, DTCMO decomposes the multi-constraint optimization problem into multiple single-constraint optimization problems for solving. P1 considers the current highest priority constraints one by one, reducing the difficulty of exploring the space containing multiple constraints at once. In the exploration stage, the ranking of constraint priorities is performed first. Referring to C3M [22], the constraint priority CP is obtained by sorting them in descending order according to the minimum non-dominated level corresponding to each constraint (lines 1–2). A new constraint is added to P1 dynamically if the conditions for adding constraints are met (lines 4–7).
当制约因素相对复杂时,有必要对每个制约因素对人口分布的影响进行分类。优先处理对人口分布影响较大的约束条件,最后处理对人口分布影响较小或没有影响的约束条件。这有助于降低 CMOP 的求解难度。受此启发,DTCMO 将多约束条件优化问题分解为多个单约束条件优化问题进行求解。 P1 逐个考虑当前优先级最高的约束,降低了同时探索包含多个约束的空间的难度。在探索阶段,首先对约束优先级进行排序。参照 C3M [22],根据每个约束条件对应的最小非支配层级,按降序排序,得到约束条件优先级 CP (第 1-2 行)。如果满足添加约束的条件,则在 P1 中动态添加新约束(第 4-7 行)。

The necessity of prioritizing the constraints is demonstrated visually in Fig. 4. The infeasible region of constraint 1 completely covers the solution obtained from constraint 2. Therefore, constraint 1 is unimportant. DTCMO processes the highest priority constraint 2 first. The determination of constraint priority can aid the population in finding CPF earlier, so it is effective to introduce the dynamic task mechanism into the CMOPs solution.
图 4 直观地说明了对约束条件进行优先排序的必要性。约束条件 1 的不可行区域完全覆盖了约束条件 2 得到的解决方案。因此,约束 1 并不重要。DTCMO 首先处理优先级最高的约束条件 2。约束优先级的确定可以帮助群体更早地找到 CPF,因此在 CMOPs 解决方案中引入动态任务机制是有效的。

Fig 4
  1. Download: Download high-res image (262KB)
    下载:下载高清图片 (262KB)
  2. Download: Download full-size image
    下载:下载全尺寸图片

Fig. 4. Population distribution of DTCMO on different constraints of MW12.
图 4.DTCMO 在 MW12 不同约束条件下的种群分布。

P2 ignores all constraints and focuses on the optimization of the objective. It is worth noting that when the UPF is fully explored, P2 will be less helpful to the subsequent evolution of other populations. Thus, to reduce unnecessary computation, P2 stops updating after reaching the UPF automatically, i.e., O2 is assigned to be the empty set (lines 8–10).
0#忽略了所有约束条件,专注于目标的优化。值得注意的是,当 UPF 被完全探索后, P2 对其他种群的后续演化帮助就会减少。因此,为了减少不必要的计算, P2 在达到 UPF 后自动停止更新,即 O2 被指定为空集(第 8-10 行)。

The ε-constraint strategy is introduced in P3, which re-models the original CMOPs into dynamic CMOPs via (4).(4)MinimizeF(x)={f1(x),f2(x),,fM(x)}subjecttoxSgi(x)εi,i=1,...,p|hj(x)|ε,j=p+1,...,q where εi,t denotes the relaxed constraint boundary of constraint i at the ith iteration. The simulated annealing approach [40] is adopted to update the constraint boundaries, which are computed by (5).(5)εt=(ε0+φ)×exp(t/T)σ×ln((ε0+φ)/φ)φ,t=1,...,Twhere t and T are the current iteration number and the maximum iteration number, respectively. ε0 indicates the initial value of the constraint boundary when the iteration number is 0, which is defined as the maximum CV value of P3 at initialization. The parameter φ is to ensure that ln((ε0+φ)/φ) is always valid and the denominator is not 0. The parameter σ is to control the rate of decrease of ε. In DTCMO, φ and σ are set to 10−8 and 5, respectively.
P3 中引入了 ε - 约束策略,通过 (4) 将原始 CMOPs 重塑为动态 CMOPs。 (4)MinimizeF(x)={f1(x),f2(x),,fM(x)}subjecttoxSgi(x)εi,i=1,...,p|hj(x)|ε,j=p+1,...,q 其中 εi,t 表示第 i 次迭代时约束条件 i 的松弛约束边界。采用模拟退火法[40]更新约束边界,其计算公式为 (5)。 (5)εt=(ε0+φ)×exp(t/T)σ×ln((ε0+φ)/φ)φ,t=1,...,T 其中 tT 分别为当前迭代次数和最大迭代次数。 ε0 表示迭代次数为 0 时约束边界的初始值,即初始化时 P3 的最大 CV 值。参数 φ 用于确保 ln((ε0+φ)/φ) 始终有效且分母不为 0。参数 σ 用于控制 ε 的下降率。 在 DTCMO 中, φσ 分别设置为 10 −8 和 5。

Inspired by MOEA/D-D-DQN [41], the choice of operators affects the quality of the resulting offspring tremendously. In DTCMO, offspring are generated by genetic algorithm (GA) and differential evolution (DE). On one hand, simulated binary crossover (SBX) [42] and polynomial mutation (PM) [6] are used to generate 2/N offspring. On the other hand, the DE operator DE/rand-to-best/1/bin is utilized to generate the remaining 2/N offspring by (6) (line 11).(6)x={y2r1+F×(y1besty2r1)+F×(y2r2y2r3),rand<CRy,randCRwhere y1best is the better individual in the first parent. y2r1,y2r2 and y2r3 are distinct individuals selected in the second parent randomly, i.e., r1,r2,r3[1,N] and r1r2r3. F denotes the scaling factor, and CR denotes the cross-control parameter.
受 MOEA/D-D-DQN [41]的启发,算子的选择会极大地影响子代的质量。在 DTCMO 中,子代是通过遗传算法(GA)和微分进化(DE)产生的。一方面,模拟二进制交叉(SBX)[42] 和多项式突变(PM)[6] 用于生成 2/N 后代。另一方面,利用 DE 算子 DE/rand-to-best/1/bin,通过 (6)(第 11 行)生成剩余的 2/N 后代。 (6)x={y2r1+F×(y1besty2r1)+F×(y2r2y2r3),rand<CRy,randCR 其中 y1best 是第一个父本中较好的个体。 y2r1y2r2y2r3 是在第二个父本中随机选出的不同个体,即 r1,r2,r3[1,N]r1r2r3F 表示比例因子, CR 表示交叉控制参数。

Finally, different strategies are employed to perform environment selection for P1,P2 and P3. P1requires only the currently added constraint to be considered (line 12). P2 is updated based on the environment selection without considering any constraints (line 13). The ε-constrained environment selection mechanism is adopted by P3 to select the more promising offspring (line 14). The truncation strategy in SPEA2 [43] is also adopted in DTCMO. When the number of feasible non-dominated solutions exceeds N, a truncation strategy needs to be adopted to sequentially delete the worst solutions, and the remaining N solutions can be selected into the next generation.
最后,对 P1P2P3 采用不同的策略进行环境选择。 P1 只需要考虑当前添加的约束条件(第 12 行)。 P2 根据环境选择进行更新,不考虑任何约束条件(第 13 行)。 P3 采用 ε 约束环境选择机制来选择更有前途的后代(第 14 行)。DTCMO 也采用了 SPEA2 [43] 中的截断策略。当可行的非主导解的数量超过 N 时,需要采用截断策略依次删除最差的解,剩余的 N 解可被选入下一代。

3.3. Stage transition 3.3.阶段过渡

Four conditions are required to be satisfied simultaneously to determine whether the proposed algorithm can enter the exploitation stage.
要确定所提出的算法能否进入开发阶段,需要同时满足四个条件。

  • Condition 1: Condition 1 is satisfied if the percentage of feasible solutions in P1 is greater than 0.9. The existence of condition 1 ensures the viability of the output population.
    条件 1:如果 P1 中可行解的百分比大于 0.9,则满足条件 1。条件 1 的存在确保了输出群体的可行性。

  • Condition 2: P2 is normalized by (7). Immediately after that, the average of the sum of changes in the objective value of P2 between every 100 generations is denoted as change. Its mathematical expression is shown in (8).(7)fi,nor(x)=(fi(x)fi,min)/(fi,maxfi,min)(8)change=(i=1Mfi,nor(x)i=1Nfi,nor(x))/N
    条件 2:根据 (7) 将 P2 归一化。紧接着,每 100 代之间 P2 目标值变化之和的平均值记为 change 。 其数学表达式如 (8) 所示。 (7)fi,nor(x)=(fi(x)fi,min)/(fi,maxfi,min) (8)change=(i=1Mfi,nor(x)i=1Nfi,nor(x))/N

where, fi,nor(x) and fi,nor(x) represent the normalized objective function value in the current iteration environment and the normalized objective function value before 100 generations, respectively. fi,min and fi,max represent the minimum and maximum objective function values at the ith objective, respectively.
其中, fi,nor(x)fi,nor(x) 分别代表当前迭代环境下的归一化目标函数值和 100 代之前的归一化目标函数值。 fi,minfi,max 分别代表第 i 个目标的最小和最大目标函数值。

If change<ζ, it can be understood that P2 remains stable basically. At this point, condition 2 is satisfied. In DTCMO, ζ is set to a smaller value of 10−2.
如果 change<ζ ,可以理解为 P2 基本保持稳定。此时,满足条件 2。在 DTCMO 中, ζ 被设置为一个较小的值,即 10 −2

  • Condition 3: Similarly, condition 3 holds if the mean change in the objective value of P1 on each objective is less than ζ. That is, condition 3 is satisfied when P1 remains stable.
    条件 3:同样,如果每个目标上 P1 目标值的平均变化小于 ζ ,则条件 3 成立。也就是说,当 P1 保持稳定时,就满足了条件 3。

  • Condition 4: If all constraints are added in P1, i.e., the number of constraints currently considered by P1 is equal to NC, condition 4 is satisfied.
    条件 4:如果 P1 中添加了所有约束条件,即 P1 当前考虑的约束条件数量等于 NC ,则满足条件 4。

When all the above four conditions are satisfied, P1 completes the processing of all constraints in CMOPs one by one, the whole objective space is explored comprehensively, and most of the feasible solutions satisfying these constraints are found. At the same time, P2 also finishes exploring the UPF and converges to UPF without considering feasibility. In this case, the algorithm enters the exploitation stage, favoring the search for feasible solutions with higher quality.
当上述四个条件全部满足时, P1 完成了对 CMOP 中所有约束条件的逐一处理,全面探索了整个目标空间,找到了满足这些约束条件的大部分可行解。同时, P2 也完成了对 UPF 的探索,并在不考虑可行性的情况下收敛到 UPF。在这种情况下,算法进入探索阶段,有利于寻找质量更高的可行解。

Condition 2 can also be utilized to measure the convergence of P2 to UPF. When condition 2 is satisfied, it can be assumed that P2 has evolved to UPF and the population distribution will no longer change significantly. At this point, the dynamic mechanism works, P2 will stop subsequent evolution, and isUPF=1. The reason for this setup is that P2 is an auxiliary task that disregards any constraints, and when P2 reaches UPF, its mission is complete. If it continues to participate in the subsequent evolution, the population distribution of P2 will not be changed in any way, instead, it will be a waste of computational resources. Therefore, stopping the update of P2 once condition 2 is satisfied is the best processing solution.
条件 2 也可以用来衡量 P2 是否趋同于 UPF。当条件 2 满足时,可以认为 P2 已经进化到 UPF,种群分布不再发生显著变化。此时,动态机制起作用, P2 将停止后续进化,而 isUPF=1 .之所以这样设置,是因为 P2 是一个无视任何约束条件的辅助任务,当 P2 达到 UPF 时,它的任务就完成了。如果它继续参与后续的进化, P2 的种群分布不会有任何改变,反而会浪费计算资源。因此,一旦满足条件 2,停止更新 P2 是最佳的处理方案。

Additionally, the timing of the addition of new constraints toP1 can be judged based on condition 1 and condition 3. When most of the solutions in P1 are feasible and the population remains stable, it means that the current constraints currCons are explored sufficiently. The next highest priority constraint can be considered to be added.
此外,还可以根据条件 1 和条件 3 判断向 P1 添加新约束条件的时机。当 P1 中的大部分解都是可行的,且群体保持稳定时,说明当前的约束条件 currCons 已被充分探索。可以考虑添加下一个优先级最高的约束条件。

3.4. Exploitation stage 3.4.开发阶段

The exploration stage is devoted to exploring the entire objective space, finding all feasible regions as much as possible, and avoiding falling into local optima. While the exploitation stage focuses more on the feasibility guarantee. It should be noted that P2 stops evolving before it enters the exploitation stage by the dynamic task mechanism, so P2 will not enter the exploitation stage. The input population in Algorithm 3 are P1, which considers all constraints, and P3, which adopts constraint relaxation techniques.
探索阶段致力于探索整个目标空间,尽可能找到所有可行区域,避免陷入局部最优。而利用阶段则更注重可行性保证。需要注意的是,在动态任务机制的作用下, P2 在进入开发阶段之前就停止了进化,因此 P2 不会进入开发阶段。算法 3 中的输入群体为 P1P3 ,前者考虑了所有约束条件,后者则采用了约束松弛技术。

Algorithm 3. Exploitation Stage (P1,P3,N,ε).
算法 3.开发阶段 ( P1 , P3 , N , ε ).

Input: P1 (main population), P3 (auxiliary population 2), N (population size), ε (constraint boundary)
输入 P1 (主要种群)、 P3 (辅助种群 2)、 N (种群数量)、 ε (约束边界)
Output: P1 (main population), P3 (auxiliary population 2)
输出: P1 (主要种群), P3 (辅助种群 2)
1: {O1,O3}Generate offspring of P1 and P3 based on GA and DE/rand-to-best/1/bin;
1: { O1 , O3 } 根据 GA 和 DE/rand-to-best/1/bin 生成 P1P3 的后代;

2: {P1,succ,O1,succ}Selection (P1O1,N,AllCons);
2: { P1,succ , O1,succ } Selection ( P1O1 , N , AllCons );

3: {P3,succ,O3,succ}Selection (P3O3,N,ε);
3: { P3,succ , O3,succ } Selection ( P3O3 , N , ε );

4: {TP1,TP3}Determine the transferred individual based on (9);
4: { TP1 , TP3 } 根据(9)确定被转移的个体;

5: P1Selection (P1O1TP3,N,AllCons);
5: P1 选择 ( P1O1TP3 , N , AllCons );

6: P3Selection (P3O3TP1,N,ε);
6: P3 选择 ( P3O3TP1 , N , ε );
7: return P1,P3
7: 返回 P1 , P3

In Algorithm 3, the strategy of the exploration stage is still employed for offspring generation (line 1). However, in the exploitation stage, the knowledge transfer strategy between the populations is not the same as in the exploration stage. Consider that not all offspring are of better quality (O1,O3) than their parents (P1,P3) in the late stages of evolution. Therefore, how to select useful knowledge among parents and offspring for information interaction between P1 and P3 is a problem to be considered in DTCMO. The DBEMTO [38] proposed by Qiao et al. addresses this challenge nicely. To determine the individuals that need to be transferred between tasks, the new individual transfer-based strategy is designed for judging inter-task relationships. The inter-task strategy of DBEMTO is introduced into our proposed algorithm. To judge the source of useful knowledge, the ratio rate of each parent and offspring among the selected individuals is calculated according to (9), and the superior population is identified as the transferred population TP (line 4).(9)rate=(|Psucc||Osucc|)/Nwhere |Psucc| and |Osucc| denote the number of N individuals selected as the most promising for the parent and offspring populations, respectively. If rate>0, it means that the parent has a higher chance of being selected, i.e., the knowledge possessed by the parent is more useful for subsequent evolution, thus, the parent should be selected as the TP. Conversely, the offspring is of higher quality and should be identified as the TP. Next, the TP, as a representative of one population, proceeds to participate in the selection of the environment of the other population and offspring (lines 5–6).
在算法 3 中,子代生成仍采用探索阶段的策略(第 1 行)。但是,在利用阶段,种群间的知识转移策略与探索阶段不同。考虑到在进化后期,并非所有子代的质量( O1 , O3 )都优于其亲代( P1 , P3 )。因此,如何在亲代和子代中选择有用的知识,实现 P1P3 之间的信息交互,是 DTCMO 需要考虑的问题。乔等人提出的 DBEMTO [38] 很好地解决了这一难题。为了确定需要在任务间转移的个体,设计了新的基于个体转移的策略来判断任务间的关系。我们提出的算法引入了 DBEMTO 的任务间策略。为了判断有用知识的来源,根据(9)计算出所选个体中每个亲代和子代的比率,并将优势种群确定为转移种群 TP (第 4 行)。 (9)rate=(|Psucc||Osucc|)/N 其中 |Psucc||Osucc| 分别表示亲代和子代种群中被选为最有前途的 N 个体的数量。若 rate>0 ,则表示亲代被选中的几率更高,即亲代所拥有的知识对后续进化更有用,因此亲代应被选中为 TP 。反之,子代的质量更高,应被确定为 TP 。接下来,作为一个种群代表的 TP 开始参与另一个种群和后代的环境选择(第 5-6 行)。

3.5. Analysis of DTCMO 3.5.DTCMO 分析

1) Analysis of the work process: In order to illustrate the work process of the proposed algorithm better, the exact process of 200,000 function evaluations performed by DTCMO on LIRCMOP7 is shown in Fig. 5. LIRCMOP7 consists of three constraints. Among them, constraint 2 and constraint 3 contain a large segment of infeasible regions, respectively. The feasible region accounts for a small proportion of the entire objective space. The three feasible regions are discontinuous, with a more complex constraint landscape. Thus, LIRCMOP7 can be used as a test problem for DTCMO work analysis.
1) 工作过程分析:为了更好地说明所提算法的工作过程,图 5 显示了 DTCMO 对 LIRCMOP7 进行 20 万次函数求值的具体过程。LIRCMOP7 包含三个约束条件。其中,约束 2 和约束 3 分别包含一大部分不可行区域。可行区域只占整个目标空间的一小部分。三个可行区域都是不连续的,约束景观较为复杂。因此,LIRCMOP7 可作为 DTCMO 工作分析的测试问题。

Fig 5
  1. Download: Download high-res image (524KB)
    下载:下载高清图片 (524KB)
  2. Download: Download full-size image
    下载:下载全尺寸图片

Fig. 5. The work process of DTCMO.
图 5.DTCMO 的工作流程。

In Fig. 5, the evolution processes of the main population and the two auxiliary populations are represented by red, green and yellow progress bars, respectively. Progress bars with different color depths are used to represent the evolution process of P1 under the consideration of different constraints. Several representative time points throughout the optimization process are labeled, and the corresponding schematic diagrams of the distribution of the various populations are attached. It is clear that the number of function evaluations between 0 and 90,900 belongs to the exploration stage, and after 90,900 the exploitation stage is entered. In the exploration stage, firstly, the priority ranking of the three constraints is obtained by P1.
在图 5 中,主种群和两个辅助种群的演化过程分别用红色、绿色和黄色进度条表示。不同颜色深度的进度条用于表示 P1 在不同约束条件下的演化过程。图中标注了整个优化过程中几个具有代表性的时间点,并附有相应的不同种群分布示意图。很明显,函数求值次数在 0 到 90,900 之间属于探索阶段,90,900 之后进入开发阶段。在探索阶段,首先通过 P1 得到三个约束条件的优先级排序。

From the picture of 9000 iterations, it can be seen that the minimum non-dominated level of constraint 1 is the largest. Thus, constraint 1 has the highest priority. The priority of all constraints is obtained by Algorithm 2: constraint 1 > constraint 3 > constraint 2. Next, P1 considers constraint 1 with the highest priority, P2 ignore all constraints, and P3 adopts the dynamic constraint mechanism. Taking the case when the number of evaluations is 60,000 as an example, the distributions of the solutions obtained by the three populations are similar, and all of them converge in the direction of CPF in the whole objective space. When the number of function evaluations reaches 79,800, the solutions obtained by P2 have fully converged to the UPF. At this point, the dynamic task mechanism works, P2 stops evolving, and its progress bar for subsequent stages is blank. P1 and P3 continue to evolve. When the number of function evaluations reaches 80,300, P1 satisfies the condition of adding a new constraint and adds the next highest priority constraint 3 dynamically. In this case, constraint 1 and constraint 3 form the existing constraint landscape. P1 continues to evolve in the environment of constraint 1 and constraint 3. While P3 continues to evolve by shrinking the boundaries of the constraints dynamically. Similarly, when the number of evaluations reaches 86,900, constraint 2 is added. By this time, all constraints are considered. Immediately after that, DTCMO enters the exploitation stage when the constraint transition condition is satisfied, i.e., when the number of evaluations is 90,900. Only P1 and P3 are contained in the exploitation stage. Finally, output P1 when the function evaluations reach the maximum.
从 9000 次迭代的图片中可以看出,约束 1 的最小非支配水平最大。因此,约束条件 1 的优先级最高。所有约束条件的优先级由算法 2 得出:约束条件 1 > 约束条件 3 > 约束条件 2。接下来, P1 考虑优先级最高的约束 1, P2 忽略所有约束, P3 采用动态约束机制。以函数求值次数为 60,000 次时为例,三个群体得到的解的分布相似,在整个目标空间都向 CPF 方向收敛。当函数评估次数达到 79 800 次时, P2 得到的解已完全收敛到 UPF。此时,动态任务机制开始工作, P2 停止演化,其后续阶段的进度条为空。 P1P3 继续演化。当函数评估次数达到 80,300 次时, P1 满足添加新约束条件,并动态添加下一个最高优先级的约束条件 3。在这种情况下,约束条件 1 和约束条件 3 构成了现有的约束条件格局。 P1 在约束 1 和约束 3 的环境中继续演化。而 P3 则通过动态收缩约束边界继续演化。同样,当评估次数达到 86,900 次时,就会添加约束 2。此时,所有约束条件都已考虑完毕。紧接着,当约束条件转换条件得到满足时,即评估次数达到 90,900 时,DTCMO 进入利用阶段。开发阶段只包含 P1P3 。最后,当函数求值达到最大值时,输出 P1

2) Superiority in handling complex CMOPs: To verify the superiority of the proposed evolutionary multi-task algorithm with dynamic tasks in dealing with problems with discrete CPFs, the populations obtained at different stages of DTCMO are plotted on MW5 and MW13 in Figs. 6 and 7, respectively. For the MW5 test problem, constraint 3 possesses the highest priority. Therefore, P1 only considers constraint 3 at the beginning. It can be seen from Fig. 6(a) that the solution obtained by P1 covers all feasible regions. The population coverage obtained is large at this time. However, the CPF of MW5 is composed of several discrete points, to converge closer to the CPF, it is necessary to narrow down the feasible regions by adding constraint 2 and constraint 1 later gradually. At this point, P2 has already reached the UPF and is no longer involved in the evolution subsequently. Therefore, only P1 and P3 are needed to consider in Fig. 6(b) to Fig. 6(d). P1 and P3 are optimized in parallel and the information interaction is achieved by the individual transfer strategy. Since all the solutions on the CPF are found by DTCMO in the exploration stage, the population distribution obtained in the exploitation stage remains unchanged essentially.
2) 处理复杂 CMOP 的优势:为了验证所提出的动态任务进化多任务算法在处理离散 CPF 问题时的优越性,图 6 和图 7 分别绘制了 DTCMO 不同阶段在 MW5 和 MW13 上得到的种群。对于 MW5 测试问题,约束 3 具有最高优先级。因此, P1 在开始时只考虑约束条件 3。从图 6(a)可以看出, P1 得到的解决方案覆盖了所有可行区域。此时得到的人口覆盖率很大。但是,MW5 的 CPF 是由多个离散点组成的,为了更接近 CPF,需要通过以后逐渐增加约束 2 和约束 1 来缩小可行区域。此时, P2 已达到 UPF,不再参与后续演化。因此,图 6(b)至图 6(d)中只需考虑 P1P3P1P3 是并行优化的,信息交互是通过单独的传输策略实现的。由于 CPF 上的所有解都是由 DTCMO 在探索阶段找到的,因此开发阶段得到的种群分布基本保持不变。

Fig 6
  1. Download: Download high-res image (323KB)
    下载:下载高清图片 (323KB)
  2. Download: Download full-size image
    下载:下载全尺寸图片

Fig. 6. Solutions obtained by DTCMO in exploration and exploitation stages on MW5.
图 6.DTCMO 在 MW5 勘探和开发阶段获得的解决方案。

Fig 7
  1. Download: Download high-res image (336KB)
    下载:下载高清图片 (336KB)
  2. Download: Download full-size image
    下载:下载全尺寸图片

Fig. 7. Solutions obtained by DTCMO in exploration and exploitation stages on MW13.
图 7.DTCMO 在 MW13 勘探和开发阶段获得的解决方案。

MW13 places a high demand on the ability of the population to span the larger infeasible region. In the exploration stage, P1 prioritizes constraint 2 and obtains CPF with five-segment discontinuous. Similarly, P2 is no longer considered after reaching the UPF. When the condition of adding constraints is satisfied, constraint 1 is added in P1 based on considering only constraint 2. As shown in Fig. 7(b), most of the solutions located around the CPF are obtained at the end of the exploration stage. The population enters the exploitation stage with the principle of feasibility priority. In Fig. 7(c), the final solutions obtained by P3 have a larger range than those obtained by P1. This is due to the fact that the P3 is allowed to preserve some infeasible solutions with smaller constraint violations by the ε-constraint technique at a late stage. These infeasible solutions can reduce the possibility of the population falling into a local optimum.
MW13 对人口跨越较大不可行区域的能力提出了很高的要求。在探索阶段, P1 优先考虑约束 2,并获得了五段不连续的 CPF。同样, P2 在达到 UPF 后不再考虑。当满足添加约束条件时,在只考虑约束 2 的基础上,在 P1 中添加约束 1。如图 7(b) 所示,大多数位于 CPF 周围的解都是在探索阶段结束时获得的。根据可行性优先原则,群体进入开发阶段。在图 7(c)中, P3 得到的最终解比 P1 得到的解范围更大。这是由于 P3 在后期允许 ε - 约束技术保留一些违反约束条件较小的不可行解。这些不可行解可以降低群体陷入局部最优的可能性。

The above analyses reveal that DTCMO achieves excellent performance on both MW5 and MW13. The population distributions obtained by DTCMO are significantly better than those in Figs. 1 and 2. That is, DTCMO performs better than multi-stage-based PPS and multi-population-based CCMO. The reason for this superiority is mainly because the dynamic task mechanism of DTCMO allows the algorithm to map out the basic topology of the CPF in the exploration stage.
上述分析表明,DTCMO 在 MW5 和 MW13 上都取得了优异的性能。DTCMO 得到的种群分布明显优于图 1 和图 2。也就是说,DTCMO 的性能优于基于多阶段的 PPS 和基于多种群的 CCMO。其优越性主要是因为 DTCMO 的动态任务机制允许算法在探索阶段就绘制出 CPF 的基本拓扑图。

3.6. Computational complexity
3.6.计算复杂度

The computational time complexity of DTCMO is mainly determined by four operators, which are: the binary tournament selection operator, genetic operator, difference operator and environment selection operator. The computational complexity of the first three operators are O(N), O(ND) and O(ND), respectively. The non-dominated sorting strategy with a computational complexity of O(MN2) and the truncation strategy with a complexity of O(N3) in SPEA2 are adopted in DTCMO. Due to the dynamic task mechanism, the time complexity of the environment selection operators in the exploration and exploitation stages are written as 3×O(N3)=O(N3) and 2×O(N3)=O(N3), respectively. Overall, the maximum computational complexity of DTCMO is determined by the environment selection operator and is O(N3).
DTCMO 的计算时间复杂度主要由四个算子决定,它们是:二元锦标赛选择算子、遗传算子、差分算子和环境选择算子。前三个算子的计算复杂度分别为 O(N)O(ND)O(ND) 。DTCMO 采用了 SPEA2 中计算复杂度为 O(MN2) 的非支配排序策略和复杂度为 O(N3) 的截断策略。由于采用了动态任务机制,探索和开发阶段环境选择算子的时间复杂度分别写为 3×O(N3)=O(N3)2×O(N3)=O(N3) 。总的来说,DTCMO 的最大计算复杂度由环境选择算子决定,为 O(N3)

4. Experimental settings 4.实验设置

4.1. Benchmark problems and performance indicators
4.1.基准问题和绩效指标

To verify the generality of DTCMO in solving different types of CMOPs, five commonly used benchmark problems are selected, which are MW [44], C_DTLZ [45], DC_DTLZ [25], CF [46] and LIRCMOP [47]. The constraint landscapes vary in terms of the different dimensions of the problem, the range of the constraints, and the continuity of the constraints.
为了验证 DTCMO 在求解不同类型 CMOP 时的通用性,我们选择了五个常用的基准问题,分别是 MW [44]、C_DTLZ [45]、DC_DTLZ [25]、CF [46] 和 LIRCMOP [47]。这些约束景观在问题的不同维度、约束范围和约束连续性方面各不相同。

In order to evaluate the performance of different algorithms for solving CMOPs quantitatively, three general indicators are utilized as performance indicators for the algorithms: the average Hausdorff distance (Δp) [48], the inverse generation distance based on the improved distance (IGD+) [49] and the hypervolume (HV) [50]. The reason for sampling IGD+ instead of IGD is that IGD is Pareto non-compliant. Δp, IGD+ and HV are all comprehensive evaluation indicators. Details of the performance indicators are given in Section S-1 of the supplementary material.
为了定量评估不同算法求解 CMOP 的性能,我们采用了三个通用指标作为算法的性能指标:平均 Hausdorff 距离 ( Δp ) [48]、基于改进距离的逆生成距离(IGD+)[49]和超体积(HV)[50]。取样 IGD+ 而不是 IGD 的原因是 IGD 不符合帕累托标准。 Δp 、IGD+ 和 HV 都是综合评价指标。性能指标详见补充材料第 S-1 节。

4.2. Algorithms for comparison and parameter settings
4.2.比较算法和参数设置

Eight state-of-the-art CMOEAs are selected as comparison algorithms to evaluate the performance of DTCMO and to verify its superiority. They are ToP [18], PPS [13], DCNSGA-III [16], TiGE-2 [17], POCEA [51], TSTI [23], C3M [22], and MTCMO [9]. To assist in the solution of the CMOPs, the auxiliary problems are introduced in many comparison algorithms, but the choice of auxiliary problems is different for each of them. Several single-objective optimization problems with constraints are defined as auxiliary problems in ToP. In PPS, the problems without considering constraints are treated as auxiliary problems. TSTI redesigns a two-objective optimization problem as an auxiliary problem. While MTCMO solves the auxiliary problem by the constraint relaxation technique. Comparison with ToP, PPS, TSTI and MTCMO can test the performance of the two auxiliary tasks we designed.
我们选择了八种最先进的 CMOEA 作为比较算法,以评估 DTCMO 的性能并验证其优越性。它们是 ToP [18]、PPS [13]、DCNSGA-III [16]、TiGE-2 [17]、POCEA [51]、TSTI [23]、C3M [22] 和 MTCMO [9]。为了帮助解决 CMOPs,许多比较算法都引入了辅助问题,但辅助问题的选择各不相同。在 ToP 中,几个带约束条件的单目标优化问题被定义为辅助问题。在 PPS 中,不考虑约束条件的问题被视为辅助问题。TSTI 将一个双目标优化问题重新设计为辅助问题。而 MTCMO 则通过约束松弛技术来解决辅助问题。通过与 ToP、PPS、TSTI 和 MTCMO 的比较,可以检验我们设计的两个辅助任务的性能。

Multi-stage and multi-population strategies are also widely implemented in CMOEAs. ToP constructs multiple single-objective constrained problems in the first stage and obtains the final solution in the second stage. The whole evolution process is divided into push and pull stages in PPS. Similarly, in the two-stage-based TSTI, the adaptive evaluation strategy is employed in different stages. C3M, which divides the evolution process into three stages, deals with constraints of different priorities in different stages. The dynamic multi-task approach is employed in MTCMO to assist in the evolution of the main population. Comparison of DTCMO with these algorithms verifies the advantages of the evolutionary multi-task framework, as well as of the exploration and exploitation stages. Moreover, to realize the dynamic solution of CMOPs, the ε-constraint technique is employed in the DCNSGA-III. Comparisons with it can validate the superiority of the dynamic task mechanism in DTCMO.
多阶段和多人口策略也在 CMOEAs 中广泛实施。ToP 在第一阶段构建多个单目标约束问题,并在第二阶段获得最终解决方案。在 PPS 中,整个演化过程分为推和拉两个阶段。同样,在基于两阶段的 TSTI 中,自适应评估策略也被应用于不同阶段。C3M 将演化过程分为三个阶段,在不同阶段处理不同优先级的约束条件。MTCMO 采用了动态多任务方法来协助主群体的进化。DTCMO 与这些算法的比较验证了多任务进化框架以及探索和利用阶段的优势。此外,为了实现 CMOP 的动态求解,DCNSGA-III 采用了 ε 约束技术。与之比较,可以验证 DTCMO 中动态任务机制的优越性。

The above analysis reveals that the eight CMOEAs with various optimization strategies are useful for evaluating the solution performance of DTCMO comprehensively. The parameter settings of the comparison algorithms are taken from the original literature. The exact parameter settings are given in Table S-1. The population size N is set to 106 for C_DTLZ and DC_DTLZ and 100 for the rest of the benchmark problems. Also, MaxFEs is given to be 300,000 for CF and LIRCMOP and 200,000 for the rest of the benchmark problems. The special settings are provided in Table S-2.
上述分析表明,采用不同优化策略的八种 CMOEA 可以全面评估 DTCMO 的求解性能。比较算法的参数设置来自原始文献。具体参数设置见表 S-1。C_DTLZ 和 DC_DTLZ 的种群规模 N 设置为 106,其余基准问题的种群规模 N 设置为 100。另外,CF 和 LIRCMOP 的 MaxFEs 为 300,000 个,其余基准问题为 200,000 个。特殊设置见表 S-2。

All comparison experiments are performed on the PlatEMO4.4 [52] platform. To reduce the contingency of the experiments, all algorithms are run 30 times on the 48 test problems independently. At a significance level of 0.05, the symbols “+”, “-” and “=” in the Wilcoxon rank sum test indicate the performance of the current comparison algorithm is significantly better, worse and similar to the proposed DTCMO, respectively.
所有对比实验均在 PlatEMO4.4 [52] 平台上进行。为了减少实验的偶然性,所有算法都在 48 个测试问题上独立运行了 30 次。在显著性水平为 0.05 时,Wilcoxon 秩和检验中的符号 "+"、"-"和"="分别表示当前比较算法的性能明显优于、劣于和类似于提议的 DTCMO。

5. Experimental results and analysis
5.实验结果和分析

5.1. Experimental results on benchmark problems
5.1.基准问题的实验结果

1) Comparisons on MW, C_DTLZ and DC_DTLZ: The Δp results of the proposed algorithm and the eight comparison algorithms on MW, C_DTLZ and DC_DTLZ are presented in Table 1. The best average values obtained by all algorithms on each test problem are shown in bold. It can be observed that the proposed DTCMO obtains the best Δp values on 14 test problems, followed by MTCMO which obtains the best 7 values. Based on the results of the rank sum test, DTCMO outperforms ToP, PPS, DCNSGA-III, TiGE-2, POCEA, TSTI, C3M, and MTSOM on 22, 23, 16, 23, 21, 14, 24, and 10 test problems, respectively. Specifically, ToP and PPS perform worst on MW5 with the complex constraint landscape. The two-stage-based ToP and PPS deal with single-objective and unconstrained problems separately in the first stage, and deal with all constraints simultaneously in the second stage. Due to the complexity of the constraint landscape of MW5, ToP and PPS cannot handle all the constraints simultaneously. It is difficult to find all the discrete feasible regions. In the worst case, many infeasible solutions are generated. On the contrary, MTCMO and DTCMO perform better on the same test problems. This is because the dynamic auxiliary tasks are created in MTCMO and DTCMO. The constraint boundary of the auxiliary task is shrunk by the ε-constraint relaxation technique adaptively. Some high-quality infeasible solutions are retained to assist the main task of exploring further unexplored feasible regions. Unlike MTCMO, the dynamic mechanism is also adopted by the main task of DTCMO. The algorithm can adjust the constraint priority according to the difference in constraint landscapes adaptively. The introduction of the novel adaptive task mechanism renders DTCMO more competitive than MTCMO.
1) 在 MW、C_DTLZ 和 DC_DTLZ 上的比较:表 1 列出了拟议算法和八种比较算法在 MW、C_DTLZ 和 DC_DTLZ 上的 Δp 结果。所有算法在每个测试问题上获得的最佳平均值以粗体显示。可以看出,拟议的 DTCMO 在 14 个测试问题上获得了最佳 Δp 值,其次是 MTCMO,获得了最佳的 7 个值。根据秩和测试结果,DTCMO 分别在 22、23、16、23、21、14、24 和 10 个测试问题上优于 ToP、PPS、DCNSGA-III、TiGE-2、POCEA、TSTI、C3M 和 MTSOM。具体来说,ToP 和 PPS 在具有复杂约束条件的 MW5 上表现最差。基于两阶段的 ToP 和 PPS 在第一阶段分别处理单目标问题和无约束问题,在第二阶段同时处理所有约束。由于 MW5 的约束条件非常复杂,ToP 和 PPS 无法同时处理所有约束条件。很难找到所有离散可行区域。在最坏的情况下,会产生许多不可行的解。相反,MTCMO 和 DTCMO 在相同的测试问题上表现更好。这是因为在 MTCMO 和 DTCMO 中创建了动态辅助任务。辅助任务的约束边界通过 ε - 约束松弛技术自适应地缩小。保留一些高质量的不可行解,以协助主任务进一步探索未开发的可行区域。与 MTCMO 不同,DTCMO 的主任务也采用了动态机制。该算法可以根据约束景观的差异自适应地调整约束优先级。新颖的自适应任务机制的引入使 DTCMO 比 MTCMO 更具竞争力。

Table 1. Δp values of DTCMO and eight comparison algorithms on MW, C_DTLZ and DC_DTLZ.
表 1.DTCMO 和八种比较算法在 MW、C_DTLZ 和 DC_DTLZ 上的 Δp 值。

Problem https://linux.do/t/topic/111737ToPPPSDCNSGA-IIITiGE-2POCEATSTIC3MMTCMODTCMO
MW11.4122e−2 (0.00e+0)= 1.4122e-2 (0.00e+0)=2.6893e−3 (1.08e−4) - 2.6893e-3 (1.08e-4) -2.3400e−3 (8.02e−5) - 2.3400e-3 (8.02e-5) -1.6701e−2 (2.64e−2) - 1.6701e-2 (2.64e-2) -8.1965e−3 (2.72e−3) - 8.1965e-3 (2.72e-3) -1.7925e−3 (9.91e−4) = 1.7925e-3 (9.91e-4) =1.8735e−3 (7.79e−5) - 1.8735e-3 (7.79e-5) -1.6139e−3 (1.13e−5) = 1.6139e-3 (1.13e-5) =1.6095e3 (9.20e6)
MW21.2342e−1 (9.56e-2) - 1.2342e-1 (9.56e-2) -1.2765e−1 (8.40e-2) - 1.2765e-1 (8.40e-2) -1.6335e−2 (8.14e−3) = 1.6335e-2 (8.14e-3) =6.4982e−1 (6.75e−2) - 6.4982e-1 (6.75e-2) -1.0670e−1 (8.53e−2) - 1.0670e-1 (8.53e-2) -1.7917e−2 (6.88e−3) - 1.7917e-2 (6.88e-3) -7.5838e−2 (3.03e−2) - 7.5838e-2 (3.03e-2) -2.0168e−2 (8.76e−3) - 2.0168e-2 (8.76e-3) -1.4580e2 (6.92e3)
MW35.1507e−1 (4.47e−1) - 5.1507e-1 (4.47e-1) -6.3310e−3 (5.84e−4) - 6.3310e-3 (5.84e-4) -5.6020e−3 (5.16e−4) - 5.6020e-3 (5.16e-4) -2.2623e−2 (3.80e−3) - 2.2623e-2 (3.80e-3) -1.0742e−2 (1.84e−3) - 1.0742e-2 (1.84e-3) -8.2961e−3 (1.95e−2) - 8.2961e-3 (1.95e-2) -4.9529e−3 (1.52e−4) - 4.9529e-3 (1.52e-4) -4.6765e−3 (1.65e−4) - 4.6765e-3 (1.65e-4) -4.3011e-3 (1.02e-4)
MW4NaN (NaN) NaN (无)5.4432e−2 (1.45e−3) - 5.4432e-2 (1.45e-3) -4.1258e-2 (1.01e−4) - 4.1258e-2 (1.01e-4) -1.1738e−1 (4.06e−2) - 1.1738e-1 (4.06e-2) -5.0853e−2 (1.87e−3) - 5.0853e-2 (1.87e-3) -4.2751e−2 (3.85e−4) - 4.2751e-2 (3.85e-4) -4.9028e−2 (1.27e−3) - 4.9028e-2 (1.27e-3) -4.0720e2 (5.01e4) + 4.0720e-2 (5.01e-4) +4.1076e−2 (3.06e−4)
MW55.7571e−1 (2.93e−1) - 5.7571e-1 (2.93e-1) -4.4957e−1 (3.64e−1) - 4.4957e-1 (3.64e-1) -1.8200e−2 (8.00e−3) - 1.8200e-2 (8.00e-3) -3.4857e−2 (5.33e−3) - 3.4857e-2 (5.33e-3) -6.7419e−2 (1.30e−2) - 6.7419e-2 (1.30e-2) -1.3770e−2 (8.73e−3) - 1.3770e-2 (8.73e-3) -3.2678e−2 (1.34e−1) - 3.2678e-2 (1.34e-1) -5.4056e−3 (3.61e−4) - 5.4056e-3 (3.61e-4) -4.8804e3 (3.22e4)
MW65.4228e-1 (4.48e-1) -5.5898e-1 (3.61e-1) -1.5138e-2 (9.21e-3) =2.0299e-1 (3.26e-1) -4.1900e-1 (2.78e-1) -6.7221e-2 (1.31e-1) -3.8012e-1 (1.90e-1) -2.4663e-2 (1.65e-2) -1.4715e-2 (9.41e-3)
MW72.8391e-2 (8.01e-2) -5.4610e-3 (4.98e-4) -5.2325e-3 (4.04e-4) -4.4490e-2 (2.28e-2) -1.2924e-2 (1.72e-3) -4.0532e-3 (2.32e-4) =4.6980e-3 (2.73e-4) -3.9692e-3 (1.40e-4) =3.9417e-3 (1.34e-4)
MW83.9498e-1 (3.89e-1) -1.5086e-1 (5.84e-2) -5.1054e-2 (4.24e-3) -7.0632e-1 (1.15e-1) -9.8255e-2 (4.06e-2) -5.2072e-2 (6.40e-3) -1.0939e-1 (4.23e-2) -4.8769e-2 (1.40e-2) -4.4244e-2 (1.36e-3)
MW93.4608e-1 (3.45e-1) -6.7086e-2 (1.11e-1) -2.3805e-2 (7.90e-3) -1.2272e-1 (1.65e-1) -7.5280e-2 (1.54e-2) -1.8863e-2 (3.59e-3) =6.1754e-2 (1.20e-1) -1.3691e-2 (3.68e-3) +1.7210e-2 (3.79e-3)
MW102.8863e-1 (0.00e+0)=4.4539e-1 (2.21e-1) -2.7826e-2 (2.21e-2) =5.4478e-2 (3.15e-2) -3.2661e-1 (2.56e-1) -4.6231e-2 (2.24e-2) -4.1415e-1 (2.28e-1) -3.7494e-2 (3.03e-2) =2.4690e-2 (1.41e-2)
MW114.0128e-1 (2.84e-1) -7.3507e-2 (6.59e-3) =6.2102e-2 (2.07e-2) +4.3843e-2 (1.19e-2) +5.1713e-2 (1.43e-2) +7.6443e-2 (4.06e-3) =7.6838e-2 (4.36e-3) -7.5702e-2 (3.34e-3) =7.5252e-2 (3.06e-3)
MW125.8683e-1 (2.91e-1) -1.8324e-2 (1.74e-2) -6.2772e-3 (1.72e-3) -1.1440e-1 (2.30e-1) -2.0104e-2 (5.69e-3) -4.6627e-3 (8.99e-5) -7.9774e-2 (2.17e-1) -4.7454e-3 (6.85e-4) =4.6116e-3 (9.95e-5)
MW136.0838e-1 (5.88e-1) -7.2352e-1 (6.85e-1) -7.4276e-2 (3.20e-2) -1.2489e+0 (5.89e-1) -2.8817e-1 (2.94e-1) -8.7495e-2 (4.79e-2) -2.0655e-1 (1.00e-1) -8.0362e-2 (5.10e-2) -4.7812e-2 (2.84e-2)
MW142.6113e-1 (1.77e-1) -1.3199e-1 (7.67e-3) -1.3693e-1 (2.91e-2) -1.6122e-1 (1.34e-2) -1.4316e-1 (2.27e-3) -1.0135e-1 (1.76e-3) -1.0762e-1 (1.79e-3) -9.7615e-2 (1.81e-3) =9.7734e-2 (1.85e-3)
C1_DTLZ15.9490e-2 (7.44e-2) -2.2707e-2 (6.60e-4) -1.8991e-2 (2.83e-4) +3.4950e-1 (1.09e-1) -3.2640e-2 (2.10e-2) =1.9539e-2 (1.27e-4) +2.0942e-2 (3.36e-4) -1.9463e-2 (1.08e-4) +2.0561e-2 (5.14e-4)
C1_DTLZ36.2870e-1 (2.08e+0) -1.3372e+0 (2.86e+0) -3.7684e+0 (4.04e+0) =1.8507e+1 (8.61e+0) -8.0463e+0 (3.91e-2) -4.9791e+0 (4.04e+0) -6.9947e-1 (2.17e+0) -6.6720e+0 (3.30e+0) -9.5671e-2 (1.13e-1)
C2_DTLZ25.6368e-2 (2.18e-3) -4.8226e-2 (1.85e-3) -4.4402e-2 (2.82e-4) -8.8617e-2 (6.01e-3) -4.7169e-2 (4.90e-4) -4.1379e-2 (5.80e-4) =4.7691e-2 (9.56e-4) -4.1089e-2 (4.75e-4) +4.1555e-2 (4.94e-4)
C3_DTLZ41.3877e-1 (5.11e-3) -1.1213e-1 (5.95e-3) -1.6126e-1 (2.31e-1) -1.7383e-1 (6.90e-3) -1.5359e-1 (2.03e-1) -9.3408e-2 (1.53e-3) +1.1115e-1 (2.85e-3) -9.2397e-2 (9.37e-4) +9.5265e-2 (1.64e-3)
DC1_DTLZ11.6727e-2 (2.11e-3) -2.2705e-2 (1.51e-2) -1.2534e-2 (1.49e-4) -3.7153e-1 (9.64e-2) -6.3357e-1 (7.92e-1) -3.3332e-2 (8.48e-2) -1.3253e-2 (4.03e-4) -1.1037e-2 (8.13e-5) +1.1285e-2 (3.13e-4)
DC1_DTLZ31.3001e-1 (1.48e-1) -1.5753e-1 (1.68e-1) -4.3155e-2 (7.12e-4) -1.5706e+1 (7.84e+0) -9.0680e-1 (1.07e+0) -5.3833e-2 (4.46e-2) =1.2305e-1 (1.68e-1) -6.8081e-2 (1.11e-1) -3.2926e-2 (3.05e-4)
DC2_DTLZ1NaN (NaN) NaN (无)4.7623e-2 (5.65e-2) -8.5640e-2 (8.62e-2) =3.7780e-1 (4.28e-2) -7.1888e-2 (6.20e-2) -1.9554e-2 (1.32e-4) +2.4253e-2 (6.12e-4) -1.9549e-2 (1.74e-4) +2.2722e-2 (1.09e-3)
DC2_DTLZ3NaN (NaN) NaN (无)3.5649e-1 (2.54e-1) -4.8088e-1 (2.38e-1) -7.8546e-1 (1.08e-1) -5.8351e-1 (0.00e+0)=3.8987e-1 (2.65e-1) =2.5125e-1 (2.58e-1) -5.3742e-1 (1.09e-1) -1.4099e-1 (1.96e-1)
DC3_DTLZ17.3012e-1 (1.75e+0) -1.0848e+0 (1.74e+0) -8.5643e-3 (2.14e-4) -8.8833e-1 (6.90e-1) -4.2273e+0 (4.41e+0) -1.5558e-1 (1.44e-1) -8.5087e+0 (2.21e+1) -1.2365e-2 (3.13e-2) =6.6207e-3 (4.95e-5)
DC3_DTLZ34.9135e+0 (3.20e+0) -2.8017e+0 (1.78e+0) -1.8526e-1 (2.48e-1) =8.4881e+0 (9.06e+0) -4.5113e+0 (3.98e+0) -1.5808e+0 (4.86e-1) -3.2845e+0 (4.58e+0) -8.3284e-1 (3.72e-1) -2.0180e-1 (2.46e-1)
+/-/=0/22/20/23/12/16/61/23/01/21/23/14/70/24/07/10/7

It is worth noting that the proposed algorithm does not perform as well as other problem classes on C_DTLZ and DC_DTLZ. This is because the overlap between CPF and UPF is high for this type of problem and the proposed algorithm's advantages cannot be fully revealed. On the contrary, some simpler constraint-handling methods can obtain well-distributed feasible solutions more easily. Take the C1_DTLZ1 problem as an example, the CPF and UPF of this problem are completely overlapped. In this case, the ordinary treatment of ignoring the constraints achieves superior solutions. As a result, DCNSGA-III, TSTI, C3M and MTCMO all obtain better non-dominated solutions. DTCMO, which has a more complex treatment of constraints, is disadvantaged. For the C2_DTLZ2 and DC2_DTLZ1 problems, their CPF is part of the UPF. For this type of problem, the solution performance of DTCMO is second only to that of MTCMO. This is because MTCMO creates only one auxiliary task with dynamically varying constraint boundaries. Whereas the proposed DTCMO creates two auxiliary tasks and processes each constraint, which is redundant for these simple problems. Additionally, the average values of IGD+ and HV for all algorithms on MW, C_DTLZ and DC_DTLZ are counted in Tables S-3 and S-4, respectively. Specific analyses are provided in Section S-3 of the supplementary material.
值得注意的是,拟议算法在 C_DTLZ 和 DC_DTLZ 上的表现不如其他问题类别。这是因为在这类问题中,CPF 和 UPF 的重叠率很高,拟议算法的优势无法充分显现。相反,一些更简单的约束处理方法可以更容易地得到分布良好的可行解。以 C1_DTLZ1 问题为例,该问题的 CPF 和 UPF 完全重叠。在这种情况下,忽略约束条件的普通处理方法能获得较好的解。因此,DCNSGA-III、TSTI、C3M 和 MTCMO 都获得了较好的非支配解。而对约束条件处理更复杂的 DTCMO 则处于劣势。对于 C2_DTLZ2 和 DC2_DTLZ1 问题,其 CPF 是 UPF 的一部分。对于这类问题,DTCMO 的求解性能仅次于 MTCMO。这是因为 MTCMO 只创建了一个具有动态变化约束边界的辅助任务。而提议的 DTCMO 会创建两个辅助任务并处理每个约束,这对于这些简单问题来说是多余的。此外,表 S-3 和 S-4 分别统计了所有算法在 MW、C_DTLZ 和 DC_DTLZ 上的 IGD+ 和 HV 平均值。具体分析见补充材料第 S-3 节。

To visualize the results of the population distributions, the solutions obtained by DTCMO and the eight state-of-the-art algorithms on the MW14 are visualized in Fig. S-1. The comparison reveals that TiGE-2 and POCE still have a large number of infeasible solutions with poor feasibility. The reason for this phenomenon is the over-emphasis on promising infeasible solutions. Although ToP and PPS maintain the convergence and diversity of the populations well in the first stage, all constraints are processed simultaneously in the second stage, which makes it hard to strike a balance between feasibility, convergence and diversity. The distribution of populations in feasible regions is extremely non-uniform. DCNSGA-III suffers from a lack of diversity as well. The solutions obtained by DTCMO are distributed in the four feasible regions uniformly while ensuring feasibility.
为了直观显示群体分布结果,图 S-1 展示了 DTCMO 和八种最先进算法在 MW14 上得到的解。对比结果显示,TiGE-2 和 POCE 仍有大量不可行解,可行性较差。造成这种现象的原因是过分强调有希望的不可行解。虽然 ToP 和 PPS 在第一阶段很好地保持了种群的收敛性和多样性,但在第二阶段要同时处理所有约束条件,因此很难在可行性、收敛性和多样性之间取得平衡。种群在可行区域的分布极不均匀。DCNSGA-III 也缺乏多样性。而 DTCMO 在确保可行性的前提下,得到的解均匀分布在四个可行区域。

2) Comparisons on CF and LIRCMOP: To further explore the performance of the algorithms in handling complex CMOPs, all the algorithms are tested on CF and LIRCMOP. The experimental results for the Δp, IGD+ and HV indicators are shown in Table S-5 to S-7 in Section S-3 of the supplementary material. Based on the experimental results, we can conclude that the proposed DTCMO performs best.
2) CF 和 LIRCMOP 的比较:为了进一步探索算法在处理复杂 CMOP 时的性能,所有算法都在 CF 和 LIRCMOP 上进行了测试。 Δp 、IGD+ 和 HV 指标的实验结果见补充材料 S-3 部分的表 S-5 至 S-7。根据实验结果,我们可以得出结论,提议的 DTCMO 性能最佳。

Combining the above analyses, it can be concluded that DTCMO is more competitive in dealing with complex CMOPs. To analyze the ability of each algorithm to handle problems with narrow feasible regions visually, the results of the population distributions obtained by all the algorithms for 3000 iterations on CF7 are plotted in Fig. 8. As can be seen from the figure, ToP, PPS, DCNSGA-III and POCEA perform poorly on CF7, with very few solutions converging to the CPF. Most of the solutions are infeasible and concentrated in a certain region, and have poor convergence and diversity. In comparison, good diversity is maintained in TiGE-2 but the convergence performance is the worst of all the algorithms. Only one solution is distributed on the CPF, and the rest are infeasible and dispersed in different regions of the objective space. The two and three solutions are found on the CPF by the two-stage TSTI and the multi-task MTCMO, respectively. Their results are slightly better than TiGE-2, but the overall performance is still poor. This is because TSTI maintains only one population and cannot focus on the convergence, diversity and feasibility of the population at the same time during evolution. In C3M and DTCMO, multiple constraints are decomposed for processing, which reduces the difficulty of solving problems. As a result, more solutions near CPF can be found. DTCMO provides better performance with stronger convergence ability than C3M. Overall, although the populations obtained by DTCMO do not exactly match the CPF on the narrow feasible region, it is still the most competitive in terms of convergence, diversity and feasibility.
综合上述分析,可以得出结论:DTCMO 在处理复杂的 CMOP 时更具竞争力。为了直观地分析各算法处理可行区域狭窄问题的能力,图 8 中绘制了所有算法在 CF7 上迭代 3000 次所得到的种群分布结果。从图中可以看出,ToP、PPS、DCNSGA-III 和 POCEA 在 CF7 上的表现很差,只有极少数解收敛到 CPF。大多数解都不可行,且集中在某个区域,收敛性和多样性都很差。相比之下,TiGE-2 保持了良好的多样性,但收敛性是所有算法中最差的。只有一个解分布在 CPF 上,其余解均不可行,且分散在目标空间的不同区域。两阶段 TSTI 和多任务 MTCMO 分别在 CPF 上找到了两个和三个解。它们的结果略好于 TiGE-2,但总体性能仍然较差。这是因为 TSTI 只维持一个种群,在进化过程中无法同时关注种群的收敛性、多样性和可行性。在 C3M 和 DTCMO 中,多个约束被分解处理,从而降低了解决问题的难度。因此,可以找到更多接近 CPF 的解决方案。与 C3M 相比,DTCMO 的性能更好,收敛能力更强。总体而言,虽然 DTCMO 所得到的种群在狭窄的可行区域内与 CPF 并不完全匹配,但它在收敛性、多样性和可行性方面仍然是最有竞争力的。

Fig 8
  1. Download: Download high-res image (452KB)
    下载:下载高清图片 (452KB)
  2. Download: Download full-size image
    下载:下载全尺寸图片

Fig. 8. Solutions obtained by DTCMO and eight comparison algorithms on CF7.
图 8.DTCMO 和八种比较算法在 CF7 上获得的解决方案。

5.2. Statistical analysis
5.2.统计分析

For a comprehensive comparison between DTCMO and eight comparison algorithms, the multi-problem Wilcoxon test results are given in Table 2. All the values of R+ are much larger than R, which further validates the advantages of DTCMO. Fig. 9 presents the average rankings of DTCMO and eight comparison algorithms by Wilcoxon test on Δp and IGD+. TiGE-2 obtained the worst overall ranking on 48 test problems. It may be because some infeasible solutions are still present in TiGE-2 at the late stage. On the contrary, the proposed DTCMO obtained the best average ranking, i.e., second place, on both Δp and IGD+. This indicates that the solutions obtained by DTCMO perform well in terms of convergence, diversity and feasibility.
表 2 列出了 DTCMO 与八种对比算法的多问题 Wilcoxon 检验结果,以进行综合比较。所有 R+ 的值都远远大于 R ,这进一步验证了 DTCMO 的优势。图 9 显示了 DTCMO 和八种对比算法在 Δp 和 IGD+ 上的 Wilcoxon 检验平均排名。在 48 个测试问题中,TiGE-2 的总排名最差。这可能是因为 TiGE-2 在后期仍存在一些不可行解。相反,建议的 DTCMO 在 Δp 和 IGD+ 上都获得了最好的平均排名,即第二名。这表明,DTCMO 得到的解在收敛性、多样性和可行性方面表现良好。

Table 2. Multi-problem Wilcoxon test results
表 2.多问题 Wilcoxon 检验结果
.

Δp
DTCOM VS.Δp(-/+/=)R+RP-value
ToP1/43/41078.098.02.02e-08
PPS9/33/6811.0365.02.05e-04
DCNSGA-III6/32/10911.0265.05.47e-04
TiGE-22/44/21066.0110.03.63e-07
POCEA4/39/51063.0113.06.21e-07
TSTI4/34/101045.0131.02.92e-07
C3M3/32/13792.0384.03.72e-04
MTCMO8/29/11973.0203.01.57e-05
IGD+
DTCOM VS.IGD+ (-/+/=)R+RP-value
ToP1/42/51104.072.01.59e-08
PPS8/37/3829.0347.01.67e-04
DCNSGA-III6/32/101018.0158.01.29e-06
TiGE-20/48/01176.00.01.63e-09
POCEA1/43/41141.035.05.35e-09
TSTI5/37/61041.0135.06.85e-08
C3M6/32/10753.0423.06.90e-05
MTCMO10/33/51012.0164.08.08e-07
HV
DTCOM VS.HV (-/+/=) 高压 (-/+/=)R+RP-value
ToP1/43/41151.025.01.74e-09
PPS9/34/5762.0414.01.42e-04
DCNSGA-III4/34/10999.0177.01.11e-06
TiGE-20/48/01176.00.01.63e-09
POCEA1/43/41141.035.02.88e-09
TSTI3/37/81046.0130.04.08e-08
C3M8/34/6784.0392.06.71e-06
MTCMO10/32/6937.0239.01.13e-05
Fig 9
  1. Download: Download high-res image (161KB)
    下载:下载高清图片 (161KB)
  2. Download: Download full-size image
    下载:下载全尺寸图片

Fig. 9. Average Wilcoxon ranking for all algorithms on Δp and IGD+.
图 9.所有算法在 Δp 和 IGD+ 上的平均 Wilcoxon 排名。

Additionally, all the obtained P-values are less than 0.05. Thus, DTCMO possesses significant superiority. The average rankings of DTCMO and the eight comparison algorithms on the 48 test functions are plotted in Fig. 10. It is clear that the smallest mean ranked on Δp and IGD+ and the largest mean ranked on HV are obtained by DTCMO. DTCMO is different from all comparison algorithms on the IGD+ indicator significantly. This shows the strong superiority and generality of adopting DTCMO to solve CMOPs with different landscapes. It can also be observed that the average rankings of DCNSGA-III and MTCMO are not much different and follow the DTCMO ranking. This indicates that DCNSGA-III and MTCMO have similar and weaker performance than the proposed DTCMO in handling these problems.
此外,所有得到的 P 值都小于 0.05。因此,DTCMO 具有明显的优越性。图 10 列出了 DTCMO 和八种比较算法在 48 个测试函数上的平均排名。很明显,DTCMO 在 Δp 和 IGD+ 上的平均排名最小,在 HV 上的平均排名最大。在 IGD+ 指标上,DTCMO 与所有比较算法都有显著差异。这表明采用 DTCMO 解决不同地貌的 CMOP 具有很强的优越性和通用性。还可以看出,DCNSGA-III 和 MTCMO 的平均排名相差不大,且紧跟 DTCMO 的排名。这表明,在处理这些问题时,DCNSGA-III 和 MTCMO 的性能相似,弱于所提出的 DTCMO。

Fig 10
  1. Download: Download high-res image (178KB)
    下载:下载高清图片 (178KB)
  2. Download: Download full-size image
    下载:下载全尺寸图片

Fig. 10. Friedman ranking test for all algorithms on Δp, IGD+ and HV.
图 10.所有算法在 Δp 、IGD+ 和 HV 上的弗里德曼排名测试。

To test the performance of DTCMO on problems with complex variable linkages, experiments on the proposed algorithm and eight other comparative algorithms on the SDC benchmark problem [53] are conducted in Section S-4 of the supplementary material.
为了测试 DTCMO 在复杂变量联系问题上的性能,在补充材料第 S-4 节中,对 SDC 基准问题[53]上的拟议算法和其他八种比较算法进行了实验。

5.3. Parameter analysis 5.3.参数分析

The only parameter that requires manual setting in the proposed algorithm is σ. It is utilized in the ε-constraint mechanism of P3 to control the shrinkage rate of the constraint boundary. To discuss the effect of different values of σ on the performance of DTCMO, the values of σ are set to be 1, 3, 5, 7, and 9, respectively. The trajectories of Δp, IGD+, and HV of DTCMO with different parameter settings on the MW and LIRCMOP are plotted in Fig. S-2 and Fig. S-3, respectively. From Fig. S-2(b), it can be seen that the effect of different σ on the algorithm performance is insignificant on MW3, MW4, and MW7, where the feasible region is simple. However, when the feasible region is complicated, DTCMO with σ=1 and σ=5 perform better on MW2 and MW6, which contain multiple feasible regions. Whereas DTCMO with σ=7 and σ=9 performs poorly on IGD+. Four feasible regions are contained on the three-objective MW8, and the DTCMO with σ=1 performs worse on MW8. On the contrary, the DTCMO with σ=3 and σ=5 perform better. However, the DTCMO with σ=3 performs extremely poorly on MW10 and MW13 with two discrete feasible regions. It follows that only the DTCMO with σ=5 is able to maintain a better level of performance on all test problems.
建议算法中唯一需要手动设置的参数是 σ ,它被用于 ε - 约束机制中的 P3 来控制约束边界的收缩率。为了讨论不同的 σ 值对 DTCMO 性能的影响,将 σ 的值分别设置为 1、3、5、7 和 9。图 S-2 和图 S-3 分别绘制了不同参数设置下 DTCMO 的 Δp 、IGD+ 和 HV 在 MW 和 LIRCMOP 上的轨迹。从图 S-2(b)可以看出,在可行区域简单的 MW3、MW4 和 MW7 上,不同 σ 对算法性能的影响不大。然而,当可行区域比较复杂时,使用 σ=1σ=5 的 DTCMO 在包含多个可行区域的 MW2 和 MW6 上表现较好。而使用 σ=7σ=9 的 DTCMO 在 IGD+ 上表现较差。三目标 MW8 上包含四个可行区域,使用 σ=1 的 DTCMO 在 MW8 上表现较差。相反,带有 σ=3σ=5 的 DTCMO 表现较好。然而,带 σ=3 的 DTCMO 在 MW10 和 MW13 两个离散可行区域上的表现极差。由此可见,只有带有 σ=5 的 DTCMO 才能在所有测试问题上保持较好的性能水平。

To test the performance of DTCMO with different values of σ in more complex constraint environments, tests are performed on LIRCMOP with much smaller feasible regions. Fig. S-3 reveals that DTCMO with σ=7 performs particularly poorly on LIRCMOP5 and LIRCMOP9 with larger infeasible regions. It is likely due to the inability of the populations to span infeasible regions. Similarly, DTCMO with σ=3 faces the same challenge when dealing with LIRCMOP6, LIRCMOP11, and LIRCMOP12, which also contain large infeasible regions. The Δp, IGD+ and HV results obtained on LIRCMOP8 are zoomed. LIRCMOP8 contains three narrow feasible regions and two large infeasible regions. It can be observed that the population's ability to search feasible regions is not as strong when σ takes a smaller value as when σ takes a larger value. This is because the larger σ is, the slower the constraint boundary shrinks, which facilitates the search of the whole objective space to find all the narrow discrete feasible regions. However, larger values of σ get the opposite effect when the feasible regions are large and continuous. Therefore, it is feasible for DTCMO to take a compromise value between the two, i.e., σ=5.
为了测试不同 σ 值的 DTCMO 在更复杂的约束环境中的性能,我们在可行区域更小的 LIRCMOP 上进行了测试。图 S-3 显示,使用 σ=7 的 DTCMO 在不可行区域较大的 LIRCMOP5 和 LIRCMOP9 上表现特别差。这可能是由于种群无法跨越不可行区域。同样,使用 σ=3 的 DTCMO 在处理 LIRCMOP6、LIRCMOP11 和 LIRCMOP12 时也面临同样的挑战,因为这些区域也包含较大的不可行区域。在 LIRCMOP8 上获得的 Δp 、IGD+ 和 HV 结果被放大。LIRCMOP8 包含三个狭窄的可行区域和两个较大的不可行区域。可以看出,当 σ 取值较小时,群体搜索可行区域的能力不如 σ 取值较大时强。这是因为 σ 越大,约束边界的收缩速度越慢,有利于在整个目标空间中寻找所有狭窄的离散可行区域。然而,当可行区域较大且连续时, σ 值越大,效果越相反。因此,DTCMO 在两者之间取一个折中值,即 σ=5 是可行的。

5.4. Validation of strategies of DTCMO
5.4.验证 DTCMO 的战略

1) Effectiveness of multi-task: Unlike existing EMTs, three dynamic tasks are created in DTCMO. To validate the necessity of creating dynamic tasks, three tasks are permutated and combined to obtain six variants. DTCMO-T1, DTCMO-T2, and DTCMO-T3 only optimized P1,P2 and P3, respectively. Only two tasks are created by DTCMO-T4, DTCMO-T5, and DTCMO-T6, which optimize P1 and P2, P1 and P3, and P2 and P3 in parallel, respectively. IGD+ is adopted to test the performance of DTCMO and its six variants. To visualize the results of the algorithm for 30 iterations on all test problems, the boxplots of DTCMO based on different task strategies on 24 test problems with different constraint landscapes on IGD+ are shown in Fig. S-4. For LIRCMOP9, which consists of many discrete and narrow feasible regions, the worst IGD+ value is obtained by DTCMO-T3. This is probably because the solutions obtained only by the constrained relaxation method still exist many infeasible solutions. Secondly, DTCMO-T2 with the unconstrained task strategy also performs poorly. This is because only the optimization of the objective is considered by DTCMO-T2, and the viability of the population is poor. Two-task-based DTCMO-T4, DTCMO-T5, and DTCMO-T6 obtain a distribution of values that are not centralized and contain many outliers. Whereas, DTCMO not only obtains the smallest IGD+ value but also a more concentrated distribution of results with no outliers. This implies that DTCMO obtains solutions of higher quality and is suitable for solving different problems compared to other variants.
1) 多任务的有效性:与现有的 EMT 不同,DTCMO 中创建了三个动态任务。为了验证创建动态任务的必要性,对三个任务进行了排列组合,得到了六个变体。DTCMO-T1、DTCMO-T2 和 DTCMO-T3 只分别优化了 P1P2P3 。DTCMO-T4、DTCMO-T5 和 DTCMO-T6 只创建了两个任务,分别并行优化了 P1P2P1P3 以及 P2P3 。采用 IGD+ 测试 DTCMO 及其六个变体的性能。为了直观地显示算法在所有测试问题上迭代 30 次的结果,图 S-4 显示了基于不同任务策略的 DTCMO 在 24 个测试问题上的方框图,这些测试问题在 IGD+ 上具有不同的约束景观。对于由许多离散和狭窄可行区域组成的 LIRCMOP9,DTCMO-T3 得到的 IGD+ 值最差。这可能是因为仅用约束松弛法得到的解仍存在许多不可行解。其次,采用无约束任务策略的 DTCMO-T2 也表现不佳。这是因为 DTCMO-T2 只考虑了目标的优化,群体的生存能力较差。基于双任务的 DTCMO-T4、DTCMO-T5 和 DTCMO-T6 所得到的数值分布不集中,包含许多离群值。而 DTCMO 不仅获得了最小的 IGD+ 值,而且结果分布更加集中,没有异常值。这意味着,与其他变体相比,DTCMO 得到的解决方案质量更高,适合解决不同的问题。

2) Effectiveness of two stages: In DTCMO, the whole evolution process is divided into the exploration stage and the exploitation stage. To explore the impact of the stage division on the performance of the algorithm, two variants are designed: DTCMO-S1 and DTCMO-S2. DTCMO-S1 contains only the exploration stage, where the three populations evolve in parallel, and the transferred populations are all derived from the generated offspring. DTCMO-S2 contains only the exploitation stage. DTCMO-S2 contains only the evolution stage, where the sources of the transfer populations are determined based on the quality of the parents and the offspring. The constraint priorities are not considered, all constraints are handled simultaneously by P1 during iteration. DTCMO is compared with these two variants on different test functions, and the experimental results are shown in Fig. 11 and Fig. S-5. DTCMO-S1 performs significantly worse than DTCMO on MW4, MW8, MW9, MW10, LIRCMOP3, LIRCMOP4, LIRCMOP7, and LIRCMOP9. DTCMO-S2 performs even worse than DTCMO-S1. In particular, the performance on the three-objective LIRCMOP13 and LIRCMOP14 is significantly worse than the other comparison algorithms. The reason for this phenomenon may be that too much emphasis is placed on the collection of feasible solutions in DTCMO-S2, neglecting the search of the entire objective space, with inferior diversity. The comprehensive analysis demonstrates that DTCMO-S1 and DTCMO-S2 obtain inferior values of Δp, IGD+ and HV on most of the test problems. This suggests that it is reasonable and effective to divide the whole evolution process into two stages.
2) 两个阶段的有效性:在 DTCMO 中,整个演化过程分为探索阶段和利用阶段。为了探索阶段划分对算法性能的影响,设计了两个变体:DTCMO-S1 和 DTCMO-S2。DTCMO-S1 只包含探索阶段,其中三个种群并行进化,转移的种群均来自生成的后代。DTCMO-S2 只包含开发阶段。DTCMO-S2 只包含进化阶段,其中转移种群的来源是根据亲代和子代的质量决定的。不考虑约束条件的优先级,所有约束条件都由 P1 在迭代过程中同时处理。DTCMO 与这两个变体在不同的测试函数上进行了比较,实验结果如图 11 和图 S-5 所示。在 MW4、MW8、MW9、MW10、LIRCMOP3、LIRCMOP4、LIRCMOP7 和 LIRCMOP9 上,DTCMO-S1 的表现明显不如 DTCMO。DTCMO-S2 的性能甚至不如 DTCMO-S1。特别是在三目标 LIRCMOP13 和 LIRCMOP14 上的表现明显不如其他比较算法。造成这种现象的原因可能是 DTCMO-S2 过于重视可行解的收集,忽视了对整个目标空间的搜索,多样性较差。综合分析表明,在大多数测试问题上,DTCMO-S1 和 DTCMO-S2 获得的 Δp 、IGD+ 和 HV 值都较差。这表明,将整个演化过程分为两个阶段是合理而有效的。

Fig 11
  1. Download: Download high-res image (155KB)
    下载:下载高清图片 (155KB)
  2. Download: Download full-size image
    下载:下载全尺寸图片

Fig. 11. The performance of the Δp, IGD+ and HV indicators of DTCMO with different stage strategies on 6 test problems. The values on the horizontal axis denote: 1=MW3, 2=MW4, 3=MW6, 4=MW8, 5=MW9, 6=MW10.
图 11.采用不同阶段策略的 DTCMO 的 Δp 、IGD+ 和 HV 指标在 6 个测试问题上的表现。横轴上的数值分别表示:1=MW3、2=MW4、3=MW6、4=MW8、5=MW9、6=MW10。

3) Effectiveness of adding constraints dynamically in P1: The novelty of DTCMO is the proposed dynamic task mechanism. For P1, new constraints need to be added one by one during the exploration stage. Before that, all the constraints are prioritized, and constraints with higher priority are processed first. To verify the effectiveness of the dynamic task mechanism in P1, three variants of DTCMO are designed with different dynamic constraint mechanisms. All constraints in the exploration stage are considered in DTCMO-C1. The constraint priorities are obtained by sorting constraints randomly in DTCMO-C2. DTCMO-C3 treats only one constraint in the exploration stage without considering combinations of multiple constraints. The Δp, IGD+, and HV statistics of DTCMO and its three variants based on different dynamic constraint strategies are shown in Fig. 12. DTCMO-C1 performs poorly on most problems. The next poor performer is DTCMO-C2. Especially on LIRCMOP3, DTCMO-C1 and DTCMO-C2 perform poorly in terms of Δp and IGD+. It is difficult for DTCMO-C1 to process all the constraints simultaneously. DTCMO-C2′s random ordering of constraints may bias the algorithm towards some unimportant constraints. The dynamic mechanism of DTCMO enables P1 to continue to deal with new constraints while satisfying the constraints of maximum priority, which reduces the problem difficulty. Although constraints are decomposed by DTCMO-C3, it is difficult to merge information from all constraints. The results demonstrate that dynamically adding constraints can reduce the difficulty of solving complex CMOPs and enhance the algorithm's performance.
3) 在 P1 中动态添加约束条件的效果:DTCMO 的新颖之处在于提出了动态任务机制。对于 P1 ,需要在探索阶段逐个添加新的约束条件。在此之前,会对所有约束条件进行优先级排序,优先级较高的约束条件会优先处理。为了验证 P1 中动态任务机制的有效性,我们设计了三种具有不同动态约束机制的 DTCMO 变体。DTCMO-C1 考虑了探索阶段的所有约束条件。在 DTCMO-C2 中,通过对约束进行随机排序获得约束优先级。DTCMO-C3 在探索阶段只处理一个约束条件,不考虑多个约束条件的组合。图 12 显示了基于不同动态约束策略的 DTCMO 及其三个变体的 Δp 、IGD+ 和 HV 统计量。DTCMO-C1 在大多数问题上的表现都很差。其次是 DTCMO-C2。特别是在 LIRCMOP3 上,DTCMO-C1 和 DTCMO-C2 在 Δp 和 IGD+ 方面表现不佳。DTCMO-C1 很难同时处理所有约束条件。DTCMO-C2 对约束条件的随机排序可能会使算法偏向一些不重要的约束条件。DTCMO 的动态机制使 P1 可以在满足最高优先级的约束条件的同时,继续处理新的约束条件,从而降低了问题的难度。虽然 DTCMO-C3 对约束条件进行了分解,但很难合并所有约束条件的信息。结果表明,动态添加约束可以降低复杂 CMOP 的求解难度,提高算法性能。

Fig 12
  1. Download: Download high-res image (208KB)
    下载:下载高清图片 (208KB)
  2. Download: Download full-size image
    下载:下载全尺寸图片

Fig. 12. The trajectories of Δp, IGD+ and HV values of DTCMO with different dynamic constraint strategies on 10 problems. The values on the horizontal axis denote: 1=MW3, 2=MW4, 3=MW8, 4=MW9, 5=DC1_DTLZ3, 6=CF4, 7=CF5, 8=LIRCMOP1, 9=LIRCMOP3, 10=LIRCMOP10.
图 12.在 10 个问题上采用不同动态约束策略的 DTCMO 的 Δp 、IGD+ 和 HV 值的变化轨迹。横轴上的值分别表示:1=MW3、2=MW4、3=MW8、4=MW9、5=DC1_DTLZ3、6=CF4、7=CF5、8=LIRCMOP1、9=LIRCMOP3、10=LIRCMOP10。

5.5. Further discussion 5.5.进一步讨论

Due to space restrictions, the effectiveness of stopping evolution in P2, the effectiveness of the ε-constraint relaxation technique in P3, the effectiveness of GA and DE operators, and adaptive selection for transferred populations are presented in Section S-5 of the supplementary material.
由于篇幅限制, P2 中停止进化的有效性、 P3ε -约束松弛技术的有效性、GA和DE算子的有效性以及转移种群的自适应选择将在补充材料的第S-5节中介绍。

5.6. Real-world application
5.6.实际应用

To verify that the proposed algorithm is equally effective in the real-world optimization problem, the experiment is carried out on the example of a real car side impact problem. This problem is a three-objective constrained optimization problem. The specific function definitions for this real-world problem are given in detail in Section S-6 of the supplementary material. Set the population size to 100 and the maximum number of iterations to 500. Each algorithm is run 10 times independently to average the values. The trajectory of HV values of DTCMO on the car side impact problem is shown in Fig. 13. Larger values of HV indicate better performance of the algorithm. As the number of iterations increases, the quality of the solutions obtained by DTCMO on the real problem improves and stabilizes. The mean HV values obtained by all algorithms on the car side impact problem are statistically presented in Table 3. It can be seen that the proposed DTCMO algorithm has greater advantages and achieves the best HV value in solving the real-world problems of the real car side impact problem. This means that the solution obtained by DTCMO can make multiple objectives to be optimized relatively optimal while satisfying all the constraints. It is feasible to employ DTCMO for the solution of real-world problems.
为了验证所提出的算法在实际优化问题中同样有效,我们以真实的汽车侧面碰撞问题为例进行了实验。该问题是一个三目标约束优化问题。该实际问题的具体函数定义详见补充材料第 S-6 节。将群体大小设为 100,最大迭代次数设为 500。每种算法独立运行 10 次,取平均值。图 13 显示了 DTCMO 在汽车侧面碰撞问题上的 HV 值轨迹。HV 值越大,说明算法性能越好。随着迭代次数的增加,DTCMO 在实际问题上获得的解的质量得到改善并趋于稳定。表 3 统计了所有算法在汽车侧面碰撞问题上获得的平均 HV 值。可以看出,所提出的 DTCMO 算法在解决汽车侧面碰撞实际问题时具有更大的优势,并取得了最佳的 HV 值。这说明 DTCMO 算法得到的解可以在满足所有约束条件的前提下,使多个待优化目标相对最优。采用 DTCMO 解决实际问题是可行的。

Fig 13
  1. Download: Download high-res image (133KB)
    下载:下载高清图片 (133KB)
  2. Download: Download full-size image
    下载:下载全尺寸图片

Fig. 13. The trajectory of HV values of DTCMO on the car side impact problem.
图 13.DTCMO 在汽车侧面碰撞问题上的 HV 值轨迹。

Table 3. The mean HV values of nine algorithms on the car side impact problem
表 3.九种算法在汽车侧面碰撞问题上的平均 HV 值
.

Problem https://linux.do/t/topic/111737ToPPPSDCNSGA-IIITiGE-2POCEATSTIC3MMTCMODTCMO
Car side impact 汽车侧面撞击2.0052e-2-1.5123e-2-2.0547e-2-9.8312e-3-9.8023e-3-2.1229e-2-2.3317e-2=2.1335e-2=2.3326e-2
+/-/=0/1/00/1/00/1/00/1/00/1/00/1/00/0/10/1/0

6. Conclusion 6.结论

To improve the generality of the algorithm to solve CMOPs with different constraint landscapes, an evolutionary multi-task algorithm DTCMO based on the novel dynamic task mechanism is proposed in this paper. Three different tasks are constructed based on the CMOPs, MOPs and relaxed CMOPs, respectively, and are optimized in parallel by different strategies during the evolution process. To solve the different CMOPs adaptively, the novel dynamic task mechanism is introduced in DTCMO, which acts on the populations corresponding to the three tasks respectively. In contrast to existing EMT-based CMOEAs, in the exploration stage, only the current constraints in the constraint list are processed by the main population P1, and new constraints are added to the list sequentially according to the constraint priority. P2 stops the evolution once it reaches a steady state, avoiding the waste of resources. In P3, the constraint boundaries are narrowed dynamically during the evolution process, which contributes to the useful information of some high-quality infeasible solutions.
为了提高算法的通用性,以解决具有不同约束地貌的 CMOPs,本文提出了一种基于新型动态任务机制的进化多任务算法 DTCMO。基于 CMOPs、MOPs 和松弛 CMOPs 分别构建了三种不同的任务,并在进化过程中通过不同的策略并行优化。为了自适应地解决不同的 CMOPs,DTCMO 引入了新颖的动态任务机制,该机制分别作用于三个任务对应的种群。与现有的基于 EMT 的 CMOEA 相比,在探索阶段,主种群 P1 只处理约束列表中的当前约束,新的约束会根据约束优先级依次添加到列表中。一旦达到稳定状态, P2 就会停止演化,避免资源浪费。在 P3 中,约束边界在演化过程中被动态缩小,这有助于获得一些高质量不可行解的有用信息。

A series of experiments are conducted with DTCMO and eight popular CMOEAs on five benchmark problems. The experimental analyses verified the generality and effectiveness of DTCMO in handling test problems with different characteristics. In addition, the parameter involved in P3 is analyzed for sensitivity. The main strategies of DTCMO are analyzed and validated by designing different variants of DTCMO.
DTCMO 和八种常用的 CMOEA 在五个基准问题上进行了一系列实验。实验分析验证了 DTCMO 在处理具有不同特征的测试问题时的通用性和有效性。此外,还对 P3 所涉及的参数进行了敏感性分析。通过设计不同变体的 DTCMO,分析并验证了 DTCMO 的主要策略。

However, the experimental results obtained by DTCMO on DTLZ and LIRCMOP1-6 still require improvement. To better enhance the algorithm's performance, the dynamic task mechanism can be further improved, and the distribution of populations in the decision space can also be taken into account. Additionally, some research gaps still exist in the application of adaptive for solving complex problems. In this regard, the dynamic task mechanism is considered to be introduced in high-dimensional expensive optimization problems [54], dynamic multi-objective optimization problems [55] and multimodal optimization problems [56], aiming to further improve the generality of DTCMO.
然而,DTCMO 在 DTLZ 和 LIRCMOP1-6 上获得的实验结果仍有待改进。为了更好地提高算法性能,可以进一步改进动态任务机制,还可以考虑种群在决策空间中的分布情况。此外,在应用自适应解决复杂问题方面还存在一些研究空白。为此,考虑在高维昂贵优化问题[54]、动态多目标优化问题[55]和多模式优化问题[56]中引入动态任务机制,旨在进一步提高 DTCMO 的通用性。

CRediT authorship contribution statement
CRediT 作者贡献声明

Qianlin Ye: Methodology, Conceptualization, Writing – original draft, Writing – review & editing, Validation. Wanliang Wang: Supervision, Writing – review & editing, Funding acquisition. Guoqing Li: Supervision, Writing – review & editing, Funding acquisition. Zheng Wang: Writing – review & editing, Funding acquisition.
叶倩琳方法论、概念化、写作 - 原稿、写作 - 审阅与编辑、验证。王万良督导、写作--审阅和编辑、资金获取。李国庆:指导、写作--审阅和编辑、经费获取。王铮撰写--审阅和编辑、资金获取。

Declaration of competing interest
利益冲突声明

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
作者声明,他们没有任何可能会影响本文所报告工作的已知经济利益或个人关系。

Acknowledgments 致谢

This study was supported by the National Natural Science Foundation of China (grant number 61873240), the Foundation of State Key Laboratory of Digital Manufacturing Equipment and Technology (grant number DMETKF2022024), the Key Research and Development Program of Zhejiang Province (grant number 2023C01168), the National Natural Science Foundation of China (grant number 51875524), the Open Project Program of the State Key Lab of CAD&CG (grant number A2210), Zhejiang University, the Zhejiang Provincial Natural Science Foundation of China (grant number LQ23F030007), and the Fundamental Research Funds for the Provincial Universities of Zhejiang (grant number SJLY2023010).
本研究得到了国家自然科学基金(批准号:61873240)、数字化制造装备与技术国家重点实验室基金(批准号:DMETKF2022024)、浙江省重点研发计划(批准号:2023C01168)的资助、国家自然科学基金(批准号:51875524)、浙江大学 CAD&CG 国家重点实验室开放项目(批准号:A2210)、浙江省自然科学基金(批准号:LQ23F030007)和浙江省省属高校基本科研基金(批准号:SJLY2023010)。

Appendix. Supplementary materials
附录。补充材料

Download: Download Word document (2MB)

Data availability 数据可用性

  • Data will be made available on request.
    数据将应要求提供。

References

Cited by (0)

View Abstract