Knowledge-driven evolutionary algorithms for multiobjective optimization problems

Abstract

Multiobjective optimization is an indispensable task in a plethora of real-world applications such as logistics, manufacturing, and finance. In recent years, real-world applications with big data keep arising in various fields, leading to more complex multiobjective optimization problems of large-scale, dynamic, and multitasking nature. On the other hand, evolutionary algorithms, inspired by biological evolution mechanisms, have been widely used in many real-world applications to solve complex optimization problems, as they can find a set of approximately Pareto optimal solutions but without requiring domain-specific information such as continuous, differentiable, and unimodal functions. Despite the great success enjoyed by evolutionary algorithms, it is worth noting that traditional evolutionary algorithms often conduct the search at a "ground zero" knowledge state, leading to unnecessary computational costs and inefficient search. In fact, the optimization knowledge and search experience during the search process could be harnessed for effective problem-solving. Therefore, to effectively and efficiently cope with the more complex multiobjective optimization problems, creating knowledge-driven evolutionary algorithms is deemed desirable and much expected by learning useful traits of problem-solving experiences. Keeping these in mind, this thesis aims to conduct research on knowledge-driven evolutionary algorithms for solving multiobjective optimization problems such as large-scale multiobjective optimization problems, dynamic multiobjective optimization problems, dynamic constrained multiobjective optimization problems, and multitask multiobjective optimization problems. Firstly, to solve large-scale multiobjective optimization problems, traditional evolutionary algorithms fail to learn from high-quality solutions or useful traits, leading to inefficient exploration of the large-scale search space. The reproduced offspring are often near their parents, suffering from poor diversity and local optima. To address this issue, the thesis presents a knowledge-driven offspring generation operator that learns knowledge from non-dominated solutions. Specifically, the thesis points out that Pareto optimal solutions follow a low-dimensional manifold. By learning from the manifold, high-quality offspring solutions can be generated via a dedicated generative adversarial network, thereby improving the convergence and diversity of the offspring solutions. Experimental results demonstrate that significant improvements have been achieved by the proposed knowledge-driven offspring generation method. Secondly, to solve dynamic multiobjective optimization problems, existing evolutionary algorithms fall short of leveraging the environmental knowledge to adaptively adjust search strategies according to the changing environments, thus making the computational resources wasted on the suboptimal subpopulations and improper evolutionary operators. To exploit the computational resources, this thesis presents a knowledge-driven Monte Carlo tree-assisted multi-population algorithm. The Monte Carlo tree activates promising subpopulations to search for promising search regions. On the other hand, the evolutionary operator of the activated subpopulation can be adaptively switched according to the changing environments. Experimental results on test functions have demonstrated the efficacy of the proposed method in solving dynamic optimization problems. Furthermore, to solve dynamic constrained multiobjective optimization problems, existing techniques could force infeasible solutions toward partially feasible regions, leading to the loss of diversity. They did not utilize knowledge in constrained/unconstrained search space or dynamic environments to accelerate the search for feasible solutions. To address the issue, this thesis proposes a spatial-temporal knowledge-based dynamic response strategy. Specifically, two synergistic tasks are established: one task is focused on the unconstrained search space to maintain diversity, while the other involves searching the constrained search space to focus on feasibility. Particularly, two knowledge transfer modules, i.e., the spatial knowledge transfer module and temporal knowledge transfer module, are designed to leverage the knowledge of the historical dynamic environment and constrained/unconstrained search space. Additionally, to advance the test suite toward real-world cases, the thesis designs 14 dynamic constrained multiobjective optimization test problems with various properties. Experiments conducted on the proposed test problems and a real-world problem have demonstrated the efficacy of the proposed algorithm. Next, to solve multitask optimization problems, a plethora of evolutionary multitasking algorithms have been developed to enhance positive transfer among optimization tasks. Nevertheless, most of these methods conduct knowledge transfer by transferring the best solutions from a source task to the target task while ignoring the proper use of knowledge from the target task in solution selection. As a result, the transferred solutions could not adapt well to the target task, thus limiting the effectiveness of knowledge transfer across tasks. To address this issue, this thesis crafts a knowledge-driven solution selection method for evolutionary multitasking. By learning the solution distribution of both source and target tasks, a number of high-quality solutions can be selected and transferred to enhance positive transfer for the target task. Experimental results on multitasking benchmarks and a real-world application have demonstrated the effectiveness of the proposed method. Lastly, this thesis develops a dedicated knowledge-driven multiobjective optimization algorithm for fair graph learning. This work aims to generate diagnostic and actionable explanations to address the problem of "what subgraph patterns cause the biased behavior of graph neural networks and what actions practitioners could take to rectify the bias." By formulating the explanation generation problem as a multiobjective combinatorial optimization problem, a multiobjective evolutionary algorithm is presented to ensure classification performance, explainability, and fairness of graph neural networks in one go. In particular, an influenced nodes-based gradient approximation is developed to boost the computation efficiency of the evolutionary algorithm. Extensive experiments have been conducted to demonstrate the proposed method's superiority in classification performance, fairness, and explainability for fair graph learning.