Dynamic-multi-task-assisted evolutionary algorithm for constrained multi-objective optimization
约束多目标优化的动态多任务辅助进化算法
Keywords https://linux.do/t/topic/111737
受限多目标优化动态任务进化算法多任务
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)where consists of objective functions and is a -dimensional decision vector. The following relationship exists between them: and . and denote inequality constraints and equality constraints, respectively.
当多个相互冲突的目标需要在满足一系列约束条件的同时达到相对最优时,这类问题被称为约束多目标优化问题(CMOPs)[1]。现实世界中的许多挑战,如低碳节能 [2]、灵活的车间调度 [3] 和运输调度 [4],都包含约束条件。这些现实问题本质上就是 CMOPs 的研究领域。一般来说,CMOPs 由目标函数、不等式约束和等式约束组成,其定义如下: (1) 其中 由 个目标函数组成, 是 维决策向量。它们之间存在以下关系: 和 。 和 分别表示 不等式约束和 等式约束。
For a given CMOP, the degree of violation of each constraint can be noted as which is expressed mathematically as follows:(2)where is typically defined as a tiny positive number e.g. 10−4 to relax the constraints of the equation.
对于给定的 CMOP,每个约束条件的违反程度可记作 ,其数学表达式如下: (2) 其中 通常定义为一个极小的正数,如 10 −4 以放松等式的约束。
After calculating the for each constraint, one can proceed to calculate the total constraint violation of by using the following equation:(3)
在计算出每个约束条件的 后,我们就可以利用下面的公式计算出 的总违反约束条件 : (3)
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., . 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 中的可行解被重新定义为同时满足所有相等约束和不等式约束的非支配解,即 。反之,只要有一个约束条件不满足,解就是不可行的。可行的帕累托最优解集在目标空间的映射构成了约束帕累托前沿(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 , and solve for these three tasks with constraint prioritization, constraint ignoring and -constraint techniques, respectively.
根据 EMT 的思想,设计了两个辅助任务来协助主任务的演化。三个种群 、 和 分别采用约束优先、约束忽略和 - 约束技术来解决这三个任务。 - •
A novel dynamic task mechanism is designed to work on three populations. Specifically, processes the constraints with higher priority first and dynamically adds the next constraint with the highest current priority when appropriate. only optimizes the objective, it stops the evolution adaptively after converging to UPF, to save computational resources to a certain extent. For , retaining the promising infeasible solutions by shrinking the constraint boundaries dynamically.
我们设计了一种新颖的动态任务机制,可在三个群体中发挥作用。具体来说, 首先处理优先级较高的约束条件,并在适当的时候动态添加当前优先级最高的下一个约束条件。 只优化目标,在收敛到 UPF 后自适应地停止演化,以在一定程度上节省计算资源。对于 ,通过动态收缩约束边界来保留有希望的不可行解。 - •
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 and 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。而开发阶段则倾向于收集可行性较高的解决方案。只有 和 被允许继续演化。此外,还通过实验对比分析了 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 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]根据 值将种群分为两个子种群,分别用于松弛 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 所示。
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 is dedicated to the solution of unconstrained MOPs, aiming to help the main population 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 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 which is uniformly distributed on the UPF can provide plenty of effective information for . 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 can drive to cross the larger infeasible region in MW13 and find two narrow feasible regions successfully, the information obtained by fails to assist further after it crosses CPF and continues to converge to the UPF. Additionally, remains unchanged at the late stage, which may lead to the waste of resources.
对于基于双种群的 CCMO,辅助种群 专门用于解决无约束澳门威尼斯人官网程,旨在帮助主种群 穿越不可行区域。为了便于区分不同种群在不同演化时期所扮演的角色,主种群和辅助种群分别用红点和绿点表示。从图 2 可以看出, 在演化过程中逐渐向 UPF 靠拢,在迭代后期几乎与 UPF 完全吻合。对于 MW5,CPF 是 UPF 的一个组成部分。在这种情况下,在 UPF 上均匀分布的 所得到的解可以为 提供大量有效信息。相反,对于 CPF 和 UPF 重叠程度较低的 MW13,CCMO 得到的解并不理想。虽然 的存在能促使 穿过 MW13 中较大的不可行区域,并成功找到两个狭窄的可行区域,但 所获得的信息在 穿过 CPF 并继续向 UPF 收敛后,就无法进一步帮助 了。此外, 在后期阶段保持不变,可能会造成资源浪费。
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., , and , 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 , without considering constraints, and 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.
为了解决上述第一个主要问题,我们构建了三个不同的任务,并分别使用约束优先、约束忽略和约束放松技术进行求解。三个任务的初始化种群分别为 、 和 ,在演化过程中并行优化。对于第二个问题,设计了一种新颖的动态任务机制来动态调整三个任务的约束函数。此外,为了解决最后一个难题,还采用了知识转移策略,以实现优秀个体在不同任务之间的转移。因此,所提出的基于动态任务的多任务进化算法 DTCMO 完美地解决了上述三个问题。图 3 给出了 DTCMO 的整体框架。为了区分不同种群的不同进化过程,主种群 、不考虑约束条件的 和动态改变约束边界的 分别用红色、绿色和黄色表示。蓝色表示三个种群在演化过程中的相同步骤。
The two major stages of DTCMO are demonstrated in Algorithm 1: the exploration stage and the exploitation stage. Firstly, three populations , and are initialized according to the three tasks (line 1). The constraint boundary of is initialized as the maximum value of its constraint violation degree (line 3). During the iteration process, the constraint boundary of 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 and the auxiliary population are involved in this stage, and their information is fully utilized in the environmental selection based on the knowledge transfer strategy. Finally, is output as the final population (line 15).
算法 1 演示了 DTCMO 的两个主要阶段:探索阶段和利用阶段。首先,根据三个任务初始化三个种群 、 和 (第 1 行)。 的约束边界初始化为其约束违反度的最大值(第 3 行)。在迭代过程中,根据 (5) 更新 的约束边界(第 5-7 行)。然后,种群进入探索阶段。每个种群的约束函数随着迭代次数的增加而自适应变化(第 9 行)。一旦满足阶段转换条件,种群即进入开发阶段(第 11 行)。该阶段只涉及主种群 和辅助种群 ,它们的信息将在基于知识转移策略的环境选择中得到充分利用。最后,输出 作为最终种群(第 15 行)。
Input: (population size), (generation limits) 输入 (种群数量), (世代限制) |
---|
Output: (final population) 输出: (最终人口) |
1: Initialize ,,; 1: 初始化 , , ; 2: ,,; 2: , , ; 3: Initialize the parameter by ; 3: 用 初始化参数 ; |
4: while do 5: if is within the -constraint boundary then 5: 如果 在 约束边界内,那么 6: Update based on (5); 6: 根据 (5) 更新 ; 7: end if 7: 如果结束 8: if then 9: {,,,,}Exploration Stage (,,,,,); 9: { , , , , } 探索阶段 ( , , , , , ); 10: else 10: 否则 11: {,}Exploitation Stage (,,,); 11: { , } Exploitation Stage ( , , , ); 12: end if 12: 如果结束 13: ; 13: ; |
14: end while 14: 同时结束 |
15: return 15: 返回 |
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. , and explore the CPF with single or combined constraints, UPF with ignored constraints, and CPF with relaxation, respectively.
受限景观的分布在一开始是不可知的,单一的探索模式可能会导致许多可行区域未被探索。为了解决这个问题,需要不同任务在不同条件下进行探索,以获得目标空间的全貌。DTCMO 探索阶段的伪代码见算法 2。 、 和 分别探索带有单一或组合约束条件的 CPF、带有忽略约束条件的 UPF 和带有松弛条件的 CPF。
Input: (main population), (auxiliary population 1), (auxiliary population 2), (population size), (the array of constraints currently under consideration), (constraint boundary) 输入 (主种群)、 (辅助种群 1)、 (辅助种群 2)、 (种群数量)、 (当前考虑的约束条件阵列)、 (约束条件边界) |
---|
Output: (main population), (auxiliary population 1), (auxiliary population 2), (stage transition), (the array of constraints currently under consideration) 输出: (主种群)、 (辅助种群 1)、 (辅助种群 2)、 (阶段转换)、 (当前考虑的约束条件阵列) |
1: Calculate the number of constraints; 1: 计算约束条件的数量; 2: Get constraint priority; 2: 获取约束优先级; 3: {,,}Judge the stage transition; 3: { , , } 判断阶段转换; 4: if then 5: ; 5: ; 6: [,]; 6: [ , ]; 7: end if 7: 如果结束 8: if then 9: ; 9: ; 10: end if 10: 如果结束 11: {,,}Generate offspring of {,,} based on GA and DE/rand-to-best/1/bin; 11: { , , } 基于 GA 和 DE/rand-to-best/1/bin 生成 { , , } 的后代; 12: Selection (∪∪∪,, |