TEC2025

Abstract:
Multiobjective evolutionary learning (MOEL) has demonstrated its advantages of training fairer machine learning models considering a predefined set of conflicting objectives, including accuracy and different fairness measures. Recent works propose to construct a representative subset of fairness measures as optimization objectives of MOEL throughout model training. However, the determination of a representative measure set relies on the dataset, prior knowledge, and requires substantial computational costs. What is more, those representative measures may differ across different model training processes. Instead of using a static predefined set determined before model training, this article proposes to dynamically and adaptively determine a representative measure set online during the model training. The dynamically determined representative set is then used as optimizing objectives of the MOEL framework and can vary with time. Extensive experimental results on 12 well-known benchmark datasets demonstrate that our proposed framework achieves outstanding performance compared to the state-of-the-art approaches for mitigating unfairness in terms of accuracy as well as 25 fairness measures although only a few of them were dynamically selected and used as optimization objectives. The results indicate the importance of setting optimization objectives dynamically during training.

Abstract:
Differential evolution (DE) is a widely recognized method to solve complex optimization problems as shown by many researchers. Yet, nonadaptive versions of DE suffer from insufficient exploration ability and uses no historical information for its performance enhancement. This work proposes fractional order DE (FODE) to enhance DE performance from two aspects. First, a bi-strategy co-deployment framework is proposed. The population-based and parameter-based strategies are combined to leverage their respective advantages. Second, the fractional order (FO) calculus is first applied to the differential vector to enhance DE’s exploration ability by using the historical information of populations, and ensures the diversity of population in an evolutionary process. We use the 2017 IEEE congress on evolutionary computation (CEC) test functions, and CEC2011 real-world problems to evaluate FODE’s performance. Its sensitivity to parameter changes is discussed and an ablation study of multistrategies is systematically performed. Furthermore, the variations of exploration and exploitation in FODE are visualized and analyzed. Experimental results show that FODE is superior to other state-of-the-art DE variants, the winners of CEC competitions, other FO calculus-based algorithms, and some powerful variants of classic algorithms.

Affiliations: Shanghai Frontiers Science Center of Molecule Intelligent Syntheses, Shanghai Institute of AI for Education, and the School of Computer Science and Technology, East China Normal University, Shanghai, China; Department of Computer Science and Engineering, and the Department of Statistics and Data Science, Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, Southern University of Science and Technology, Shenzhen, China; Department of Networked Intelligence, Peng Cheng Laboratory, Shenzhen, China

Abstract:
Large-scale multiobjective optimization problems (LSMOPs), characterized by a substantial number of decision variables, pose significant challenges for many existing evolutionary algorithms. However, the search efficiency of these algorithms is not yet satisfactory. This is mainly because that the search efficiency of these algorithms may deteriorate dramatically since the search space increases exponentially with the number of decision variables. Having this in mind, we proposed a large-Scale multiobjective optimization framework named causal inference-based competitive swarm optimizer (CI-CSO). Specifically, a causal-information-(CI)-based operator is designed for competitive swarm optimizers. First, a causal inference technique named information geometric causal inference (IGCI) is introduced to adequately explore the CI between decision variables and fitness values. To further distinguish the positive or negative impacts of these critical variables on solution quality, a CI processing module is designed, facilitating targeted optimization. To enhance search efficiency, CI-based offspring generator are employed, leveraging the variance of causal effects to dynamically adjust the search step size and sampling range. To evaluate its performance, the proposed CI-based operator is embedded into two multiobjective evolutionary algorithms (MOEAs) (LSTPA and LMOCSO). To demonstrate the effectiveness of the proposed framework, experimental results are presented using the LSMOP test suite and five real-world problems, each involving up to 10 000 decision variables. In addition, six classic algorithms are included for comparison.

Abstract:
Evolutionary computation (EC) is a kind of meta-heuristic algorithm that takes inspiration from natural evolution and swarm intelligence behaviors. In the EC algorithm, there is a huge amount of data generated during the evolutionary process. These data reflect the evolutionary behavior and therefore mining and utilizing these data can obtain promising knowledge for improving the effectiveness and efficiency of EC algorithms to better solve optimization problems. Considering this and inspired by the ability of human beings that acquire knowledge from the historical successful experiences of their predecessors, this article proposes a novel EC paradigm, named knowledge learning EC (KLEC). The KLEC aims to learn from historical successful experiences to obtain a knowledge library and to guide the evolutionary behaviors of individuals based on the knowledge library. The KLEC includes two main processes named learning from experiences to obtain knowledge and utilizing knowledge to guide evolution. First, KLEC maintains a knowledge library model (KLM) and updates this model by learning the successful experiences collected in every generation. Second, KLEC not only adopts the evolutionary operation but also utilizes the KLM to guide individuals for better evolution. The KLEC is a generic and effective framework, and we propose two algorithm instances of KLEC, which are knowledge learning (KL)-based differential evolution and KL-based particle swarm optimization. Also, we combine the KL framework with several state-of-the-art EC algorithms, showing that the performance of the state-of-the-art algorithms can be significantly enhanced by incorporating the KL framework.

Abstract:
Symbolic regression, a multifaceted optimization challenge involving the refinement of both structural components and coefficients, has gained significant research interest in recent years. The equation learner (EQL), a neural network designed to optimize both equation structure and coefficients through gradient-based optimization algorithms, has emerged as an important topic of concern within this field. Thus far, several variations of EQL have been introduced. Nevertheless, these existing EQL methodologies suffer from a fundamental constraint that they necessitate a predefined network structure. This limitation imposes constraints on the complexity of equations and makes them ill-suited for high-dimensional or high-order problem domains. To tackle the aforementioned shortcomings, we present a novel approach known as the evolving EQL (eEQL). eEQL introduces a unique network structure characterized by automatically defined functions (ADFs). This new architectural design allows for dynamic adaptations of the network structure. Moreover, by engaging in self-learning and self-evolution during the search process, eEQL facilitates the generation of intricate, high-order, and constructive subfunctions. This enhancement can improve the accuracy and efficiency of the algorithm. To evaluate its performance, the proposed eEQL method has been tested across various datasets, including benchmark datasets, physics datasets, and real-world datasets. The results have demonstrated that our approach outperforms several well-known methods.

Abstract:
Maximizing the influence of opinions is an emerging research topic in social networks. Although the community is a key structure of social networks, little effort has been made to investigate how to maximize the influence of opinions on all communities. This article proposes a systematic approach to address this issue. First, we construct a multifaceted opinion evolution (MFOE) model with three critical influence factors, namely, individuals, neighbors, and communities, to describe the opinion evolution process in social networks. The convergence analysis confirms its ability to reveal the influence of opinions. Then, we define the overall community opinion to measure the influence of opinions on all communities and employ it as the objective function to formulate an optimization problem called community opinion maximization (COM). We show that the COM problem is NP-hard. To optimize this problem, a memetic algorithm with three problem-specific schemes is developed and termed MACOM. Extensive experimental studies on real-world social networks demonstrate the plausibility of the MFOE model and the effectiveness of MACOM.

Abstract:
Inverted generational distance (IGD) is an important performance indicator in the field of multiobjective optimization (MOO). Although it has been widely used for decades, applying IGD for fair and accurate performance evaluation remains challenging, with the biggest obstacle being the selection of the reference set. IGD generally represents the distance between the solution set and the Pareto front (PF). Since the real PF is often an infinite set, even if it is known, it is difficult to apply it directly to the calculation of IGD. As a workaround, past research typically samples a finite set, i.e., the reference set, from the PF as an approximation, indirectly used in the IGD calculation. This inevitably introduces a systematic error, which we refer to as discretization error. In this article, we prove an upper bound for the discretization error, demonstrating that if the reference set is sufficiently dense and uniformly distributed on the entire PF, the discretization error will converge to zero. Additionally, we propose a numerical method for the exact calculation of IGD and IGD+. When the analytical expression of the PF is known, this method allows for the direct calculation of IGD and IGD+ using the real PF, thus avoiding discretization error.

Abstract:
When solving optimization problems with expensive or implicit objective functions, evolutionary algorithms (EAs) commonly utilize surrogate models as cost-effective substitutes for evaluation. This category of algorithms is referred to as data-driven EAs (DDEAs). However, when constructing surrogate models, existing studies rely on the hand-crafted model structure, requiring prior knowledge while leading to the suboptimal fitting ability of the model. To address the issue, this article proposes a novel symbolic regression (SR)-assisted EA, namely SR-DDEA. SR-DDEA employs SR to automatically construct the model structure without prior knowledge and obtain accurate surrogates. Specifically, we develop an efficient gene expression programming algorithm to enhance the expressive ability of surrogates, assisted by a queue-based decoding strategy to improve the efficiency of the model calculations. We also employ a clustering-based selective ensemble method to maximize data utilization and obtain diverse models. Experimental findings on commonly employed benchmarks demonstrate that our algorithm surpasses other cutting-edge offline DDEAs on test problems of different scales and a practical aerodynamic airfoil design challenge.

Abstract:
Generating agents that can achieve zero-shot coordination (ZSC) with unseen partners is a new challenge in cooperative multiagent reinforcement learning (MARL). Recently, some studies have made progress in ZSC by exposing the agents to diverse partners during the training process. They usually involve self-play when training the partners, implicitly assuming that the tasks are homogeneous. However, many real-world tasks are heterogeneous, and hence previous methods may be inefficient. In this article, we study the heterogeneous ZSC problem for the first time and propose a general method based on coevolution, which coevolves two populations of agents and partners through three subprocesses: 1) pairing; 2) updating; and 3) selection. Experimental results on various heterogeneous tasks highlight the necessity of considering the heterogeneous setting and demonstrate that our proposed method is a promising solution for heterogeneous ZSC tasks. To the best of our knowledge, we are the first to underscore the significance of the heterogeneous ZSC tasks and to introduce an effective framework for addressing it.

Abstract:
Exploratory landscape analysis (ELA) and fitness landscape analysis in general have given valuable insight into problem hardness understanding as well as facilitating algorithm design and endeavors, such as automated algorithm selection (AAS) and configuration. These techniques have largely been limited to search spaces of a single domain. In this work, we provide the means to compute exploratory landscape features for mixed-variable problems where the decision space is a mixture of continuous, binary, integer, and categorical variables. This is achieved by introducing a preprocessing scheme which needs to be incorporated into the process of ELA feature generation. To highlight the merit of our approach for practical applications, we design and conduct an AAS study based on a hyperparameter optimization benchmark suite and our preprocessing scheme. Our trained algorithm selector is able to close the gap between the single best and the virtual best solver by 57.5% over all benchmark problems.

Abstract:
As a challenging research topic in evolutionary multitask optimization (EMTO), evolutionary many-task optimization (EMaTO) aims at solving more than three tasks simultaneously. The design of the EMaTO algorithm generally needs to consider two major open issues, which are how to obtain useful knowledge from similar source tasks and how to effectively transfer knowledge to the target task. In this article, we discover that knowledge structure plays a significant role in dealing with these two issues and propose a novel knowledge structure preserving-based evolutionary algorithm (KSP-EA) to efficiently solve many-task optimization problems. KSP-EA aims to achieve two goals, which are first to obtain useful structure-preserved knowledge from similar source tasks and second to effectively transfer both direct and indirect knowledge to the target task. To achieve the first goal, we propose a local-structure-preserved knowledge acquisition strategy that projects the knowledge of similar source tasks into a unified subspace without loss of the knowledge structure, thus enhancing the quality of the obtained knowledge. To achieve the second goal, we propose a tree-based knowledge propagation strategy that constructs a knowledge propagating tree to connect all the tasks and propagates knowledge along the edges of this tree. This way, the target task can obtain both direct and indirect knowledge, improving the effectiveness of knowledge transfer. We conduct extensive experiments on CEC19 and WCCI22 many-task optimization test suites and a real-world application scenario to evaluate the performance of KSP-EA. The experimental results show that our KSP-EA generally outperforms state-of-the-art algorithms.

Abstract:
Many nature-inspired metaheuristics have been published, with claims of originality based on the metaphor that inspired the algorithm. Rarely is empirical evidence given to show algorithmic originality. In order to provide an easy and computationally cheap approach to characterize algorithm search behavior, a suite of 20 behavioral characteristics is proposed. This behavioral characteristic suite allows for the search behavior of an algorithm to be quantified without manual inspection. By doing so, behavioral novelty of any given algorithm may be determined by comparing the behavioral characteristics to those of well-known metaheuristics. To illustrate this use, and to evaluate whether metaheuristics are behaviorally distinct, a host of metaheuristics is run on various benchmark functions. To evaluate behavioral similarity across all problems, while acknowledging behavior to be problem dependant, a novel method is proposed. In addition to this method, new behavioral characteristics are also proposed. The behavioral vectors generated for each benchmark function are clustered. The relationships and trends present in the different clusters are summarized by creating a pair-wise matrix for every metaheuristic pair, which tallies the number of times that the pair are found within the same cluster. The tallies are then analyzed in order to make inference regarding the distinctness of any metaheuristic’s behaviors, across many different benchmark functions. The analysis finds that the range of unique search behaviors is small and that most metaheuristics share their behaviors with most other metaheuristics. The analysis also identifies both unique algorithms, as well as algorithms which have no unique behaviors.

Abstract:
Automated design of metaheuristic algorithms offers an attractive avenue to reduce human effort and gain enhanced performance beyond human intuition. Current automated methods design algorithms within a fixed structure and operate from scratch. This poses a clear gap toward fully discovering potentials over the metaheuristic family and fertilizing from prior design experience. To bridge the gap, this article proposes an autoregressive learning-based designer for automated design of metaheuristic algorithms. Our designer formulates metaheuristic algorithm design as a sequence generation task, and harnesses an autoregressive generative network to handle the task. This offers two advances. First, through autoregressive inference, the designer generates algorithms with diverse lengths and structures, enabling to fully discover potentials over the metaheuristic family. Second, prior design knowledge learned and accumulated in neurons of the designer can be retrieved for designing algorithms for future problems, paving the way to continual design of algorithms for open-ended problem solving. Extensive experiments on numeral benchmarks and real-world problems reveal that the proposed designer generates algorithms that outperform all human-created baselines on 24 out of 25 test problems. The generated algorithms display various structures and behaviors, reasonably fitting for different problem-solving contexts. Code is available at https://github.com/auto4opt/ALDes.

Abstract:
The (1+1) quantum evolutionary algorithm [ (1+1) QEA] uses quantum probability amplification to accelerate the classical (1+1) evolutionary algorithm [ (1+1) EA] for the optimization of pseudo-Boolean functions, which assign real-valued fitness to binary strings. However, determining the optimal mutation rate remains crucial to reducing the required number of function evaluations. To address this, we introduce a dynamic mutation rate strategy for the (1+1) QEA, leveraging the guarantees the fixed-point amplitude amplification algorithm gives to adjust the mutation rate dynamically [ (1+1) QEAdyn]. We derive upper bounds on the number of fitness evaluations the strategy requires to solve well-known benchmark functions. Notably, we close the performance gap of the (1+1) QEA on the NEEDLE problem, matching the optimal performance possible in the quantum setting. Nevertheless, our results on ONEMAX and LEADINGONES lag behind known classical results. So, we delve into quantum black-box complexity, exploring the difficulty of problem-solving on a quantum computer without explicit problem knowledge. We introduce a quantum algorithm that solves the n -dimensional LEADINGONES problem with at most n evaluations. Additionally, we develop a quantum algorithm for the ONEMAX problem, requiring only one function evaluation. Both of these quantum algorithms surpass the capabilities of classical algorithms. Finally, we devise a quantum algorithm for solving the ONEMAX problem using only fitness comparisons and provide computational evidence that it still does so faster than any classical algorithm.

Abstract:
Constrained multiobjective optimization problems often have complex feasible regions and constrained Pareto fronts. These factors bring great challenges to current constrained multiobjective optimization evolutionary algorithms (CMOEAs). To solve this problem and further balance the objective optimization and constraint satisfaction, we propose an indexes-based and partial restart-based constrained multiobjective optimization (IRCMO) algorithm. In IRCMO, a two-stage (i.e., development and enhancement) and tri-population framework is designed. IRCMO adopts the aggregative indexes-based evaluation and adaptive collaborative partial restart strategy to assist the evolution of the first and second populations. The third population is obtained by directed sampling, which is mostly located at the boundary of the feasible region and enhances the exploration ability of extreme solutions. At the end of each generation, a progressive dual-archive strategy is designed to screen the solutions distributed uniformly from three populations. Experimental results demonstrate that IRCMO is superior to the other six state-of-the-art CMOEAs on several constraint benchmark suites and real-world problems.

Abstract:
Dynamic multiobjective optimization problems (DMOPs) are often scaled to large-scale scenarios in real-world applications, which inevitably must face the triple challenges of massive search space, dynamic environmental changes and multiobjective conflicts simultaneously. This article proposes an adversarial autoencoder-based large-scale dynamic multiobjective evolutionary framework. It integrates deep generative modeling techniques and large-scale multiobjective evolutionary algorithms (LMOEAs) to solve large-scale DMOPs effectively and efficiently. Specifically, an adversarial autoencoder-based deep generative network training architecture is proposed for high-dimensional decision variables in large-scale DMOPs. It can transfer a generative model trained on Pareto-optimal solutions in the current environment to a new environment using only the auxiliary information exhibited through the movement trajectories of historical Pareto-optimal solutions, resulting in the generation of quality initial populations for the new environment. Meanwhile, any proven LMOEA can be integrated into the proposed framework without extensive modifications. Experimental results on a typical dynamic multiobjective test suite with problem settings from 30 to 1000 dimensions demonstrate that the optimization performance of the proposed framework outperforms existing state-of-the-art designs. Especially in large-scale scenarios, the proposed framework is considered superior in terms of solution quality and computational efficiency.

Abstract:
In the design of multiobjective particle swarm optimization (MOPSO) algorithms, swarm leaders, i.e., the personal best (pbest) and global best (gbest), are expected to guide the particles toward Pareto-optimal solutions. However, most existing MOPSO algorithms focus on selecting such leaders from the archive of candidate solutions to approximate the Pareto front (PF) that may not yield good approximations of the Pareto set (PS). To address this challenge, this work proposes to predict both pbest and gbest for each particle by explicitly approximating the manifold structure of the PS, following the regularity property of multiobjective optimization problems. Thus, we design a leader prediction-based MOPSO (PPSO) algorithm. In our algorithm, a self-organizing mapping (SOM) method is adopted at each iteration to capture the manifold structure from the current swarm to predict leaders. Specifically, pbest is pinpointed by mapping the particle onto the neuron of SOM, while gbest is estimated by randomly selecting from the neighborhood neurons. In this way, the particles of a swarm in PPSO are guided by the predicted pbest and gbest to approximate the Pareto-optimal solutions. The developed PPSO is empirically verified with several representative algorithms, on several benchmark test instances and real-world problems. Experimental results have demonstrated the advantages of leader prediction for MOPSO over other approaches.

Abstract:
This article discusses the challenge when evaluating multiobjective optimization algorithms under noise. It argues that it is important to take into account possible selection errors by a decision maker, due to inaccurate estimates of a solution’s true objective values. It demonstrates that commonly used performance metrics do not properly account for such errors, and proposes two alternative performance metrics that do account for such errors by adapting the popular R2 and \mathrm IGD^+ metrics.

Abstract:
Drug discovery is an expensive and risky process. To combat the challenges in drug discovery, an increasing number of researchers and pharmaceutical companies recognize the benefits of utilizing computational techniques. Evolutionary computation (EC) offers promise as most drug discovery problems are essentially complex optimization problems beyond conventional optimization algorithms. EC methods have been widely applied to solve these complex optimization problems especially in lead compound generation and molecular virtual evaluation, substantially speeding up the process of drug discovery and development. This article presents a comprehensive survey of EC-based drug discovery methods. Particularly, a new taxonomy of the methods is provided and the advantages and limitations of the methods are reviewed. In addition, the potential future directions of EC-based drug discovery are discussed and the publicly available resources, including databases and computational tools are compiled for the convenience of researchers seeking to pursue this field.

Abstract:
In surrogate-assisted evolutionary optimization, privacy-preservation and trusted data sharing has become an increasingly important concern, especially in scenarios involving distributed sensitive data. Existing privacy-preserving surrogate-assisted evolutionary optimization algorithms heavily rely on the basic federated learning framework. However, recent findings have revealed possible vulnerabilities within this framework, including susceptibility to adversarial threats like gradient leakage and inference attacks. To address the above challenges and enhance privacy protection, this article proposes to protect the raw data by applying a differentially private stochastic gradient descent method to train surrogate models. A differential evolution operator is designed to generate personalized new samples for multiple clients based on promising and additional auxiliary samples, avoiding the exposure of online newly generated data. Moreover, a similarity-based aggregation algorithm is integrated to effectively construct the global surrogate model. A rigorous security analysis is provided to further validate the effectiveness of the proposed method in privacy protection. Experimental results show that the proposed method exhibits remarkable optimization performance on a set of synthetic problems with federated settings while maintaining the data privacy.

Abstract:
Black-box optimization problems are commonly seen in the real world, ranging from experimental design to hyperparameter tuning of machine learning models. In numerous scenarios, addressing a collection of similar data-driven black-box optimization tasks distributed on multiple clients not only raises privacy concerns but also suffers from non-independent and identically distributed (non-IID) data, seriously deteriorating the optimization performance. To address the above challenges, this article focuses on handling non-IID data in federated data-driven many-task optimization. To construct a high-quality global surrogate by robustly aggregating the local models, the server first fits a Gaussian distribution for each model parameter upon receiving local parameters, from which an ensemble model can be sampled. To reduce the communication cost and provide a generalized global model, a student surrogate model is derived by means of knowledge distillation from the ensemble. In addition, each client is allowed to retain both local and global models, so that the mean and variance of the predictions can be used to guide the selection of new samples. Experimental results demonstrate the reliability and efficacy of our proposed method on both benchmark problems and a real machine learning problem in the presence of non-IID data.

Abstract:
3-D point cloud registration is a process of solving the geometric transformation between two point clouds. This process is an important issue in computer vision and pattern recognition. The registration methods based on geometric features are highly sensitive to the scale of feature extraction. Changes in scale can introduce inaccuracies in feature descriptions, thereby compromising the reliability of the registration results. To mitigate the impact of feature scale on the outcomes and the high-dimensional issue arising from features of different scales, we propose a method for multiscale point cloud feature selection (FS). We solve the high-dimensional problem of FS by designing a multitask framework. By designing a mutual information dimensionality reduction method, we decomposed the high-dimensional FS task of different descriptors with multiscale features into multiple related low-dimensional FS tasks. Then, by means of the knowledge transfer among these low-dimensional FS tasks, we sought the best feature subset to obtain more robust feature information. We evaluate the effectiveness of our method by conducting extensive experiments on various datasets. The experimental results show that the method outperforms other feature descriptors in terms of descriptive power and robustness and improves the effectiveness of point cloud registration.

Abstract:
dynamic multiobjective optimization (DMO) problems are prevalent in many practical applications and have garnered significant attention from both industry and academia, leading to the proposal of numerous DMO algorithms. Among these approaches, learning- and prediction-based evolutionary approaches have achieved remarkable success due to their fast learning and strong optimization capabilities when dynamic occurs. However, existing methods typically focus on learning and transferring knowledge within a single problem, often relying on historical knowledge to aid the optimization process. This could limit the data available for developing a more general prediction model for dynamic optimization. The potential for leveraging knowledge across different dynamic multiobjective problems (DMOPs) to enhance problem-solving efficiency and effectiveness remains largely unexplored. Building on this insight, this article explores the solution of DMOPs with learning not only within a single problem but also across different problems. In particular, by performing dynamic feature extraction and task-specific solution classification, we propose to construct a centralized learning model that captures the correlations across DMOPs and the corresponding optimized solutions. This approach allows optimization data from multiple problems to be effectively utilized, enabling the learning of dynamic knowledge to enhance evolutionary optimization when a change occurs. To assess the effectiveness of the proposed algorithm, extensive empirical studies have been conducted on the commonly used DMOP benchmarks with fixed and shifty dynamic settings. The numerical results demonstrate the effectiveness of the proposed algorithm in recognizing more general change patterns of DMOPs, showcasing its superiority compared to the existing state-of-the-art learning and prediction-based approaches.

Abstract:
Dynamic constrained multiobjective optimization problems (DCMOPs) involve complex changes in objective functions and constraints over time. These changes challenge most existing algorithms to quickly cross infeasible regions and accurately track the changing Pareto optimal set (POS) and Pareto optimal front (POF). To address this issue, this article presents a multicenters-based prediction strategy, termed FCP, for solving DCMOPs more effectively. First, we introduce a penalty function to cluster the historical optimal solutions, thereby obtaining multicenters of these solutions. These centers can roughly represent the distribution of different clusters in POS. Then, we predict cluster centers of the new environment’s POS by calculating the distance of centers from the preceding two environments. The prediction strategy can handle the change of POS caused by constraints thereby improving the accuracy of prediction. Finally, a proposed population generator calculates the distances between new centers and utilizes information from these centers to predict a well-distributed initial population. Comprehensive studies on widely used benchmark problems demonstrate that our proposed algorithm is very competitive in dealing with DCMOPs compared with seven state-of-the-art algorithms. Meanwhile, to validate the proposed prediction strategy, it is embedded into the static constraints handling techniques from other DCMOEAs to solving DCMOPs and the experimental results indicate that FCP is superior in generating initial population.

Abstract:
With the increasing requirement for computational efficiency in evolutionary algorithms (EAs) when tackling many optimization tasks concurrently, many-task optimization (MaTO) has gained much attention in recent years. It involves extracting and transferring the knowledge from successful search experiences across many tasks. As the number of tasks and variable scale grows in MaTO, the need for efficient knowledge transfer in EAs becomes indispensable. In this article, we present a task-averaged natural gradient-assisted natural evolution strategy (TNG-NES) to deal with MaTO efficiently. The task-averaged natural gradient (TNG) captures how a group of task distributions evolves, considering their overall trends of mean and covariance. This can accelerate the optimization process across all tasks by leveraging the evolutionary similarities among multiple task search distributions. Notably, TNG-NES exhibits linear computational complexity concerning the number of tasks for knowledge transfer. Additionally, to adaptively utilize TNG for distribution evolution and mitigate negative transfer, we introduce a transfer adaptive control mechanism for TNG-NES. We conducted extensive experiments on CEC19-MaTO, WCCI22-MaTO, our proposed large-scale MaTO benchmark suite, and real-world applications. The results validate the effectiveness of TNG-NES, outperforming state-of-the-art MaTO algorithms.

Affiliations: Department of Computing, The Hong Kong Polytechnic University, Hong Kong, SAR, China; Department of Artificial Intelligence, Key Laboratory of Multimedia Trusted Perception and Efficient Computing, Ministry of Education of China, Key Laboratory of Digital Protection and Intelligent Processing of Intangible Cultural Heritage of Fujian and Taiwan, Ministry of Culture and Tourism, School of Informatics, Xiamen University, Xiamen, Fujian, China; Department of Data Science and Artificial Intelligence, The Hong Kong Polytechnic University, Hong Kong, SAR, China

Abstract:
Dynamic constrained multiobjective optimization problems (DCMOPs) are characterized by multiple conflicting optimization objectives and constraints that vary over time. The presence of both dynamism and constraints underscores the importance of preserving population diversity. This diversity is essential not only to escape local optima following environmental changes but also to climb infeasible barriers to approach feasible regions. However, existing constraint-handling techniques for enhancing solution feasibility could steer infeasible solutions toward partially feasible regions, potentially resulting in the loss of diversity. To maintain both diversity and feasibility, this work establishes two synergistic tasks: one task concentrates on exploring the unconstrained search space to preserve diversity, while the other delves into searching the constrained search space to prioritize feasibility. Particularly, in light of evolutionary transfer optimization, two knowledge transfer modules, i.e., the spatial knowledge transfer module and temporal knowledge transfer module are designed. The spatial knowledge transfer module facilitates knowledge transfer between the constrained and unconstrained search spaces to accelerate the exploration of both spaces. On the other hand, the temporal transfer module leverages historical knowledge to enhance search efficiency within the new environment. To advance the test suite toward real-world cases, we designed fourteen test problems with various properties. Experiments conducted on the proposed test problems and a real-world problem have demonstrated the efficacy of our proposed algorithm.

Affiliations: Department of Computer Science, CINVESTAV-IPN, Ciudad de Mexico, Mexico; Big Data Analytics in Transportation, Technische Universitat Dresde, Dresden, Germany; Ciencias de la computación, Universidad Nacional Autonoma de Mexico Instituto de Investigaciones en Matematicas Aplicadas y Sistemas, Ciudad de Mexico, Mexico; Department of Machine Learning and Optimisation, University of Paderborn, Paderborn, Germany

Abstract:
In this article, we address the problem of computing all locally optimal solutions of a given multiobjective problem whose images are sufficiently close to the Pareto front. Such \epsilon -locally optimal solutions are particularly interesting in the context of multiobjective multimodal optimization (MMO). To accomplish this task, we first define a new set of interest, L_Q,\epsilon , that is strongly related to the recently proposed set of \epsilon -acceptable solutions. Next, we propose a new unbounded archiver, ArchiveUpdateL_Q,\epsilon , aiming to capture L_Q,\epsilon in the limit. This archiver can in principle be used in combination with any multiobjective evolutionary algorithm (MOEA). Further, we equip numerous MOEAs with ArchiveUpdateL_Q,\epsilon , investigate their performances across several benchmark functions, and compare the enhanced MOEAs with their archive-free counterparts. For our experiments, we utilize the well-established metrics HV, IGDX, and \Delta _p . Additionally, we propose and use a new performance indicator, I_\mathrm EDR , which results in comparable performances but which is applicable to problems defined in higher dimensions (in particular in decision variable space).

Abstract:
Achieving a tradeoff between convergence, feasibility, and diversity is critical for solving constrained multiobjective optimization problems (CMOPs). Existing constrained multiobjective evolutionary algorithms (CMOEAs) primarily focus on constraint-handling techniques to balance constraint satisfaction and objective optimization. However, individual diversity is generally considered to be low. Owing to the insufficient enhancement of diversity, CMOEAs are unable to disperse well in the objective space to enhance the search for the constrained Pareto front (CPF) when handling CMOPs with complex constraints. To address this limitation, this study develops a diversity-enhanced tri-stage framework with three different evolutionary stages. First, sufficient convergence is enabled to move the population across the infeasible regions. Afterward, an angle-domination strategy is designed, aiming to spread the population evenly in the objective space while maintaining the achieved convergence. Third, we propose a minimum neighborhood-based domination strategy to ensure that the population searches the CPF by pursuing an even distribution in the objective space. Moreover, a weight vector preselection strategy is proposed to reduce computational overhead by avoiding ineffective searches in regions that do not include the CPF. Extensive experiments with 48 benchmark instances and 25 real-world instances validate the effectiveness of our approach over nine state-of-the-art methods.

Affiliations: School of Electronic Information Engineering, Taiyuan University of Science and Technology, Taiyuan, China; School of Computer Science and Electronic Engineering, University of Surrey, Surrey, U.K.; School of Computer Science and Technology, Taiyuan University of Science and Technology, Taiyuan, China; School of Engineering, Westlake University, Hangzhou, China; School of International Education, Taiyuan University of Science and Technology, Taiyuan, China

Abstract:
Traditional large-scale evolutionary algorithms are limited in their ability to solve certain real-world applications with high-dimensional, closed-box, and computationally expensive objectives due to their need for numerous objective evaluations. Surrogate-assisted evolutionary algorithms (SAEAs) have shown effective for expensive closed-box optimization by relying on inexpensive surrogate models. However, large-scale optimization remains challenging for SAEAs due to the exponentially growing search space and the presence of multiple local optima, resulting in difficulty in training a proper model due to the lack of samples. To address these challenges, we propose constructing an initial surrogate model on randomly selected dimensions and calculating a Gaussian distribution for each sampled dimension. The surrogate then provides predictions when perturbing each sampled dimension by sampling from the distribution, enabling the identification of the most important variables for constructing an active subproblem to reduce the search space. A secondary surrogate model, built for the active subproblem, guides the offspring generation and environmental selection for a modified particle swarm optimization algorithm to effectively explores the subspace while escaping local optima in large-scale problems. Experimental results on CEC’2013 and CEC’2010 benchmark problems show that the proposed method outperforms state-of-the-art algorithms in addressing large-scale expensive optimization problems. The efficiency of the proposed method is further verified on CEC’2010 benchmark problems extended to 2000 dimensions.

Abstract:
Unravelling the evolution of cooperation is essential for advancing natural and artificial intelligence (AI) systems. Previous studies have investigated the impact of additional incentives, such as reciprocity and reputation, on cooperative behavior. However, a fundamental question persists: under what conditions do moral preferences evolve and does this evolution subsequently promote cooperation in networked populations of agents? To address this question, we propose a comprehensive framework to systematically explore the co-evolution of moral preferences and cooperative behavior in a networked population. In our framework, the population structure is modeled as a network, with nodes corresponding to AI agents. Moral preferences are modeled through a learning algorithm that adheres to social norms. Prosocial and antisocial behaviors lead to rewards or punishments, and learning agents receive morality scores based on their rewarding behavior toward others. Simulation results demonstrate the effectiveness and robustness of the proposed algorithm in a networked population, showcasing faster convergence. We find that moral preferences enhance cooperation as long as the learning rate is moderate, even in the presence of dominant defectors. This surprising finding also holds for cooperation-inhibiting network structures, provided the critical benefit-cost ratio for cooperation is sufficiently high or below average. Interestingly, moral preferences also co-evolve with cooperation in the populations. Our work not only provides new design methodologies for network algorithms, but also highlights the insight that large-scale evolutionary computation can provide for evolutionary biology and emerging AI-agent populations.

Abstract:
In recent years, dynamic multiobjective evolutionary algorithms (DMOEAs) using the prediction strategy have shown promising performance for solving dynamic multiobjective optimization problems (DMOPs), as they can predict environmental changing trends in advance. However, most of them follow a regular change pattern and thus their performance is compromised when solving DMOPs with irregular change patterns (e.g., nonlinear correlations). To alleviate this challenge, this article proposes a DMOEA with a learnable prediction for tackling DMOPs. Specifically, a neural network is designed to effectively capture diverse change patterns of the environment. Based on the change patterns learned, a directional improvement prediction (DIP) is developed to guide the evolutionary search toward promising directions in the decision space. In this way, a superior initial population with good convergence and diversity is predicted by DIP, which can be more effective for solving various DMOPs. Comprehensive empirical studies show that the proposed DIP is effective and the proposed algorithm has some advantages over five competitive DMOEAs when solving three commonly used benchmarks and one real-world problem.

Abstract:
Many-task differential evolutionary (DE) algorithm is an effective way to optimize multiple tasks simultaneously. The optimization performance of the algorithm decreases due to the negative transfer when the number of tasks is large. To address this problem, a many-task DE algorithm based on bi-space similarity (MaTDE-BSS) is proposed to improve the positive transfer. First, the bi-space similarity metric is designed to characterize intertask similarity quantitatively. The decision space similarity and objective space similarity are considered simultaneously in the bi-space similarity metric. Second, a task selection strategy based on evolutionary state is proposed to select the optimal source task from the source task library accurately. The source task library based on bi-space similarity metric is built for storing source tasks. Finally, a dynamic knowledge transfer strategy is proposed to improve the efficiency of knowledge positive transfer in the many-task optimization. Parameters of the knowledge transfer strategy are adjusted according to bi-space similarity metric adaptively. In addition, the experimental results show that MaTDE-BSS is able to evaluate the intertask similarity more comprehensively. And MaTDE-BSS is more competitive compared to other many-task evolutionary algorithms.

Abstract:
Point cloud registration (PCR) is an important task for other point cloud tasks. Feature-based methods are widely adopted for their speed and efficiency in PCR. The descriptive capability of features extracted by a single geometric descriptor is limited. Descriptive capabilities can be improved by concatenating features extracted from multiple descriptors. However, due to the existence of redundant and irrelevant features, the correct corresponding points are difficult to match, which further affects the registration effect. We propose an evolutionary multitasking point cloud descriptor optimization method. Integrate existing descriptors to optimize descriptors with stronger description ability. Labeling features to calculate the feature importance for the registration and generating multitasks. In optimized processing, approximate evaluation which is calculated by prior correspondence saved in the database replaces the expensive searching correspondences process in the entire point cloud. Finally, a multiscale filter is developed to remove error correspondences by the geometric information from multiple scale descriptor features. Experimental demonstrate that the proposed approach can optimize a feature subset with higher-descriptive capability compared to other methods and show superior PCR performance on 14 point cloud models. This is the first paper on point cloud descriptor optimization, which provides a new idea for PCR research.

Affiliations: Shanghai Frontiers Science Center of Molecule Intelligent Syntheses, the Shanghai Institute of AI for Education, and the School of Computer Science and Technology, East China Normal University, Shanghai, China; National Engineering Laboratory for Big Data System Computing Technology, Shenzhen University, Shenzhen, China; Department of Computer Science and Engineering, and the Department of Statistics and Data Science, Guangdong Provincial Key Laboratory of Braininspired Intelligent Computation, Southern University of Science and Technology, Shenzhen, China

Abstract:
A series of surrogate-assisted evolutionary algorithms (SAEAs) have been proposed for the expensive multiobjective optimization problems (EMOPs), building cheap surrogate models to replace the expensive real function evaluations (FEs). However, the search efficiency of these SAEAs is not yet satisfactory. More efforts are needed to further exploit useful information from the real FEs in order to better guide the search process. Facing this challenge, this article proposes a hyperbolic neural network (HNN)-based preselection operator to accelerate the optimization process based on the limited evaluated solutions. First, the preselection task is modeled as a multilabel classification problem where solutions are classified into different layers (ordinal categories) through the \epsilon -relaxed objective aggregation. Second, in order to resemble the hierarchical structure of candidate solutions, a HNN is applied to tackle the multilabel classification problem. The reason for using HNN is that hyperbolic spaces more closely resemble hierarchical structures than the Euclidean spaces. Moreover, to alleviate the data deficiency issue, a data augmentation strategy is employed for training the HNN. In order to evaluate its performance, the proposed HNN-based preselection operator is embedded into two SAEAs. Experimental results on the two benchmark test suites and three real-world problems with up to 11 objectives and 150 decision variables involving seven state-of-the-art algorithms demonstrate the effectiveness of the proposed method.

Abstract:
Deep neural networks (DNNs) have achieved remarkable performance in various tasks, including image classification. However, recent research has revealed the susceptibility of trained DNNs to subtle perturbations introduced into input images. Addressing these vulnerabilities is pivotal, leading to a significant area of study focused on developing attack algorithms capable of generating potent adversarial images. In scenarios where access to gradient information is restricted (black-box scenario), many existing methods introduce optimized perturbations to each individual pixels of an image to cause trained DNNs to misclassify. However, due to the high-dimensional nature of this approach, current methods have inherent limitations. In contrast, our proposed approach involves the construction of perturbations by concatenating a series of overlapping semi-transparent shapes. Through the optimization of these shapes’ characteristics, we generate perturbations that result in the desired misclassification by the DNN. By conducting a series of attacks on state-of-the-art DNNs trained of CIFAR-10 and Imagenet datasets, our method consistently outperforms existing attack algorithms in terms of both query efficiency and success rate.

Abstract:
genetic programming (GP) is a widely recognized and powerful approach for symbolic regression (SR) problems. However, existing GP methods rely on a single form to solve the problem, which limits their search diversity and increases the likelihood of getting stuck in local optima, especially in complex scenarios. In this article, we propose a general multiform GP (MFGP) framework to improve the performance of GP on complicated SR problems. As far as we know, this articel is the first attempt to integrate the multiform optimization paradigm with GP to accelerate the search performance. The key idea of the proposed framework is to construct multiple forms to solve the same problem cooperatively at the same time. During the evolution process, knowledge gained from different forms is shared among the solvers to improve the search diversity and efficiency. A knowledge transfer mechanism is specifically designed to facilitate knowledge transfer among GP solvers with different modeling forms. In addition, an adaptive resource control mechanism is designed to reallocate computing resources according to the problem solving efficiency of different solvers to further improve search efficiency. To demonstrate the effectiveness of the proposed framework, a multiform gene expression programming algorithm is designed and tested on 20 problems, including physical datasets, synthetic datasets, and real-world datasets. The experimental results have demonstrated the effectiveness of the proposed framework.

Abstract:
The evolving unknown cyberattacks, compounded by the widespread emerging technologies (say 5G, Internet of Things, etc.), have rapidly expanded the cyber threat landscape. However, most existing intrusion detection systems (IDSs) are effective in detecting only known cyberattacks, because only known cyberattack samples are usually available for IDS training. Identifying unknown cyberattacks, therefore, remains a big challenging issue. To meet this gap, in this article, motivated by artificial immunity (AIm) and differential evolution (DE), we propose a bidirectional DE-based unknown cyberattack detection system, coined BDE-IDS. Specifically, we first design a bidirectional DE algorithm for known nonself antigens (abnormal data), where bidirectional evolutionary directions are considered for increasing or decreasing the differences between known nonself antigens and self antigens (normal data), to create new antigens possibly used for generating cyberattack detectors. Second, a novel tolerance training mechanism is developed to eliminate invalid newly evolved antigens falling into the coverage of either known self or nonself antigens. Third, the remaining antigens are employed to generate detectors for unknown cyberattacks. Extensive experiments demonstrate that the BDE-IDS achieves outperformance in detecting unknown cyberattacks (as well as known cyberattacks) compared to state-of-the-art studies, including those AIm-based, signature-based, and anomaly-based IDSs.

Abstract:
The use of an unbounded archive (UA) has attracted much attention in the filed of evolutionary multiobjective optimization (EMO) since a solution set selected from the UA is often better than the final population. The size of the UA is very large (e.g., 1 000 000) since it is unbounded and it stores all the examined nondominated solutions during the execution of an EMO algorithm. Thus, an algorithm which can efficiently select a high-quality subset from a large-scale candidate set (e.g., UA) is needed. In this article, we propose a gradient-guided local search hypervolume subset selection (GL-HSS) algorithm to efficiently select a high-quality subset from a large-scale candidate set. In each iteration of GL-HSS, the gradient of the hypervolume (HV) contribution of each selected solution is used to guide the local search. As a result, the proposed algorithm can quickly improve the HV of the selected subset. Experimental results show that, compared to the existing subset selection algorithms, the proposed GL-HSS algorithm can efficiently select high-quality subsets from various large-scale candidate sets.

Abstract:
Constraints may scatter the Pareto optimal solutions of a constrained multiobjective optimization problem (CMOP) into multiple feasible regions. To avoid getting trapped in local optimal feasible regions or a part of the global optimal feasible regions, a constrained multiobjective evolutionary algorithm (CMOEA) should consider both the escape force and the expansion force carefully during the search process. However, most CMOEAs fail to provide these two forces effectively. As a remedy for this limitation, this article proposes a method called three-population evolutionary algorithm (TPEA). TPEA maintains three populations, termed Pop1, Pop2, and Pop3. Pop1 is a regular population, updated with a constrained NSGA-II variant. Pop2 and Pop3 are two auxiliary populations, containing the innermost and outermost nondominated infeasible solutions, respectively. The analysis reveals that these two types of nondominated infeasible solutions can contribute to the generation of escape and expansion forces, respectively. Due to these two forces, TPEA is likely to identify more global optimal feasible regions, which is crucial for constrained multiobjective optimization. Also, a mating selection strategy is developed in TPEA to coordinate the interaction among these three populations. Extensive experiments on 58 benchmark CMOPs and 35 real-world ones demonstrate that TPEA is significantly superior or comparable to six state-of-the-art CMOEAs on most test instances.

Abstract:
Population-based evolutionary algorithms are often considered when approaching computationally expensive black-box optimization problems. They employ a selection mechanism to choose the best solutions from a given population after comparing their objective values, which are then used to generate the next population. This iterative process explores the solution space efficiently, leading to improved solutions over time. However, one of the challenges of these algorithms is that they require a large number of evaluations to provide a quality solution, which might be computationally expensive when the evaluation cost is high. In some cases, it is possible to replace the original objective function with a less accurate approximation of lower cost. This introduces a tradeoff between the evaluation cost and its accuracy. In this article, we propose a technique capable of choosing an appropriate approximate function cost during the execution of the optimization algorithm. The proposal finds the minimum evaluation cost at which the solutions are still properly ranked, and consequently, more evaluations can be computed in the same amount of time with minimal accuracy loss. An experimental section on four very different problems reveals that the proposed approach can reach the same objective value in less than half of the time in certain cases.

Abstract:
Large-scale overlapping problems (LSOPs) are prevalent in practical engineering applications, and the optimization challenge is significantly amplified due to the existence of shared variables. Decomposition-based cooperative coevolution (CC) algorithms have demonstrated promising performance in addressing LSOPs. However, current CC frameworks designed for overlapping problems rely on grouping methods for the identification of overlapping problem structures and the current grouping methods for LSOPs fail to consider both accuracy and efficiency simultaneously. In this article, we propose a two-stage enhanced grouping method for LSOPs, called overlapping enhanced differential grouping (OEDG), which achieves accurate grouping while significantly reducing computational resource consumption. In the first stage, OEDG employs a grouping method based on the finite differences principle to identify all subcomponents and shared variables. In the second stage, we propose two grouping refinement methods, called subcomponent union detection (SUD) and subcomponent detection (SD), to enhance and refine the grouping results. SUD examines the information of the subcomponents and shared variables obtained in the previous stage, and SD corrects inaccurate grouping results. To better verify the performance of the proposed OEDG, we propose a series of novel benchmarks that consider various properties of LSOPs, including the topology structure, overlapping degree, and separability. Extensive experimental results demonstrate that OEDG is capable of accurately grouping different types of LSOPs while consuming fewer computational resources. Finally, we empirically verify that the proposed OEDG can effectively improve the optimization performance of diverse LSOPs.

Abstract:
Expensive optimization problems (EOPs) have attracted increasing research attention over the decades due to their ubiquity in a variety of practical applications. Despite many sophisticated surrogate-assisted evolutionary algorithms (SAEAs) that have been developed for solving such problems, most of them lack the ability to transfer knowledge from previously-solved tasks and always start their search from scratch, making them troubled by the notorious cold-start issue. A few preliminary studies that integrate transfer learning into SAEAs still face some issues, such as defective similarity quantification that is prone to underestimate promising knowledge, surrogate-dependency that makes the transfer methods not coherent with the state-of-the-art in SAEAs, etc. In light of the above, a plug and play competitive knowledge transfer (CKT) method is proposed to boost various SAEAs in this article. Specifically, both the optimized solutions from the source tasks and the promising solutions acquired by the target surrogate are treated as task-solving knowledge, enabling them to compete with each other to elect the winner for expensive evaluation, thus boosting the search speed on the target task. Moreover, the lower bound of the convergence gain brought by the knowledge competition is mathematically analyzed, which is expected to strengthen the theoretical foundation of sequential transfer optimization. Experimental studies conducted on a series of benchmark problems and a practical application from the petroleum industry verify the efficacy of the proposed method. The source code of the CKT is available at https://github.com/XmingHsueh/SAS-CKT.

Abstract:
Production processes are inherently complex, often involving multiple production phases from raw materials to finished products, making joint scheduling problems a focal point of research. This article addresses the dynamic cascaded flowshop joint scheduling problem, which integrates a distributed permutation flowshop in Phase 1 and a hybrid flowshop in Phase 2. The challenge involves both initial scheduling and dynamic response mechanisms for new job insertions. We propose an evolutionary greedy algorithm (EGA) aimed at minimizing total flowtime. The EGA employs a multistart cooperative framework tailored to problem characteristics, alternating between a population-based EGA for Phase 1 and an elitist-based greedy algorithm for Phase 2 to generate a robust and complete schedule. Upon new job insertions, three heuristic-driven response strategies enhance solution stability and adaptability. In addition, phase-specific hybrid local search operators and an adaptive insertion strategy, leveraging knowledge-based problem properties, further improve solution quality and search efficiency. The experimental results indicate that the EGA outperforms five state-of-the-art algorithms, achieving an average improvement of 39% in RPI values across 480 instances. Moreover, the proposed local search mechanisms and dynamic response strategies significantly enhance its performance. Thus, the EGA is well-suited for addressing the studied problem.

Abstract:
Most existing dynamic multiobjective evolutionary algorithms (DMOEAs) have been designed to handle dynamic multiobjective optimization problems (DMOPs) with regular environmental changes. However, they often overlook scenarios where environmental changes are irregular and less predictable. Recently, knowledge transfer has been proposed as a novel paradigm for solving DMOPs. Despite this, most transfer strategies only consider transferring knowledge obtained from the previous environment while ignoring significant differences that may exist between adjacent environments due to irregular changes. To address these issues, this article proposes a novel knowledge transfer strategy based on a Gaussian mixture model (GMM denoted as KTMM) for solving DMOPs with irregular changes. In particular, an adaptive GMM is designed to capture the knowledge of historical environments, which is then transferred to generate an initial population for the new environment. Additionally, a new method for controlling irregular changes is introduced into widely used benchmarks to form the DMOP benchmark with irregular changes. Our proposed KTMM is compared with six state-of-the-art DMOEAs on several benchmark problems with irregular changes. Experimental results demonstrate the superiority of our proposed method in most test instances and in a real-world problem.

Abstract:
Inspired by natural evolutionary processes, evolutionary computation (EC) has established itself as a cornerstone of artificial intelligence. Recently, with the surge in data-intensive applications and large-scale complex systems, the demand for scalable EC solutions has grown significantly. However, most existing EC infrastructures fall short of catering to the heightened demands of large-scale problem solving. While the advent of some pioneering GPU-accelerated EC libraries is a step forward, they also grapple with some limitations, particularly in terms of flexibility and architectural robustness. In response, we introduce EvoX: a computing framework tailored for automated, distributed, and heterogeneous execution of EC algorithms. At the core of EvoX lies a unique programming model to streamline the development of parallelizable EC algorithms, complemented by a computation model specifically optimized for distributed GPU acceleration. Building upon this foundation, we have crafted an extensive library comprising a wide spectrum of 50+ EC algorithms for both single- and multi-objective optimization. Furthermore, the library offers comprehensive support for a diverse set of benchmark problems, ranging from dozens of numerical test functions to hundreds of reinforcement learning tasks. Through extensive experiments across a range of problem scenarios and hardware configurations, EvoX demonstrates robust system and model performances. EvoX is open source and accessible at: https://github.com/EMI-Group/EvoX.

Abstract:
Transfer evolutionary multiobjective optimization (MOO) leverages the relevant knowledge from other source problems (distinct but possibly related) to assist the optimization of the target problem of interest. Multiproblem surrogates (MPSs) stack multiple source surrogates to reduce the number of function evaluations of the target expensive problem. The current MPSs only considers several source problems and the source and target problems are assumed to be homogeneous. In order to address the above issues, this article proposes fast heterogeneous MPSs (HeMPSs) for transfer evolutionary MOO with a large number of surrogates. First, an iterative surrogate selection strategy is designed to select the highly relevant surrogates from the large-scale surrogate pool to avoid negative transfer. Second, HeMPSs are established to align the features of the source and target models. Finally, an adaptive k-fold cross-validation method is proposed to obtain the predicted values of the target model with low-computational costs. Experiments on the MOO benchmark problems and multiobjective neural architecture search problems have demonstrated that the proposed method is able to avoid negative transfer in the large-scale scenarios and reduce the computational costs.

Abstract:
Neural architecture search (NAS) is an effective approach for automating the design of deep neural networks. Evolutionary computation (EC) is commonly used in NAS due to its global optimization capability. However, the evaluation phase of architecture candidates in EC-based NAS is compute-intensive, limiting its application for many real-world problems. To overcome this challenge, we propose a novel progressive evaluation strategy for the evaluation phase in convolutional neural network architecture search, in which the number of training epochs of network individuals is progressively increased. In addition, a subpopulation preservation strategy is proposed to preserve medium-size and large-size architectures to avoid prematurely discarding networks that may not perform well in the early stages but have the potential to excel with further optimization. Our proposed algorithm reduces the computational cost of the evaluation phase and promotes population diversity and fairness by preserving promising networks based on their distribution. We evaluate the proposed progressive evaluation and subpopulation preservation of NAS (PEPNAS) algorithm on the CIFAR10, CIFAR100, and ImageNet benchmark datasets, and compare it with 36 state-of-the-art algorithms, including manually designed networks, reinforcement learning (RL) algorithms, gradient-based algorithms, and other EC-based ones. The experimental results demonstrate that PEPNAS effectively identifies networks with competitive accuracy while also markedly improving the efficiency of the search process. For instance, PEPNAS discovers the architecture on CIFAR10 with a low-error rate of 2.38% using only 0.7 GPU days. We directly adopt the searched architecture for the image classification on the CIFAR100 and ImageNet datasets, which achieves the top 1 error rates of 16.46% and 26.25%, respectively. The code is available at https://github.com/chajiajie/PEPNAS.

Abstract:
Constrained multimodal multiobjective optimization problems (CMMOPs) are challenging in the field of optimization, requiring to consider the balance between the constraints and objectives, the balance between exploration and exploitation in the decision space and the objective space, and the balance of diversity between the decision space and the objective space. In this work, we propose a multitask-assisted evolutionary algorithm (CMMO-MTA) to achieve these balances. In CMMO-MTA, a tri-task multitasking framework is proposed, which contains one main task and two assisting tasks. The main task aims to solve the original CMMOP, and two assisting tasks are designed to transfer desired knowledge to the main task to achieve the first two balances. Furthermore, a space balance-based selection mechanism is proposed to ensure a balanced representation of solutions in both the decision space and the objective space, thereby striking the third balance. Experimental studies are conducted on 31 test problems and a real-world application to compare the proposed algorithm with seven state-of-the-art algorithms. The results demonstrate the superiority of CMMO-MTA in solving CMMOPs.

Affiliations: School of Computer Science and the School of Cyberspace Security, Xiangtan University, Xiangtan, China; KINDI Computing Research, College of Engineering, Qatar University, Doha, Qatar; Department of Electrical and Computer Engineering, University of Alberta, Edmonton, AB, Canada; College of Systems Engineering, National University of Defense Technology, Changsha, China; Wuyi Intelligent Manufacturing Institute of Industrial Technology, Jinhua, China

Abstract:
In recent years, prediction-based algorithms have attracted much attention for solving dynamic multiobjective optimization (DMO) problems in the evolutionary computing community. However, this class of algorithms still has potential for further improvements by enhancing the historical information extraction approach to balance convergence and diversity. In this article, we propose a DMO algorithm based on a recurrent neural network (RNN) to balance the population’s convergence and diversity in dynamic environments. The RNN model in the proposed algorithm employs online learning in order to constantly improve according to the increasing evolutionary information. Meanwhile, differing from most existing prediction-based algorithms, the learning machine is not limited by assumptions, such as linear or nonlinear correlation, when it predicts new solutions for future evolutionary environments. Besides, an auxiliary strategy is performed, which adaptively introduces the random or mutated solutions according to the error losses between the prediction solutions and the optimal solutions in the whole optimization process. The experimental results show that the proposed algorithm is more effective for handling DMO problems than several recent algorithms.

Abstract:
Real-world problems often consist of multiple conflicting objectives to be optimized simultaneously, featuring a set of Pareto-optimal solutions. Estimating the entire Pareto front can be computationally expensive, and is not always necessary, as decision makers (DMs) will likely be interested only in specific regions of the Pareto front. In the absence of knowledge about the DM preferences, the so-called knees in the Pareto front are considered to be particularly attractive. In this article, we propose using Thompson sampling in the Bayesian optimization framework to estimate the location of the knee regions in a data-efficient manner. Our experimental results show that the proposed methods accurately locate the knee regions after a very small number of evaluations, providing a computationally efficient approach to single- and multiknee detection in multiobjective optimization.

Abstract:
Multiobjective multitasking evolutionary algorithms have shown promising performance for tackling a set of multiobjective optimization tasks simultaneously, as the optimization experience gained within one task can be transferred to accelerate the solving of others. However, most studies only select similar transfer tasks based on their designed metrics, which become less efficient when tackling a large number of optimization tasks, as their transferred knowledge may be insufficiently diversified. To alleviate this issue, this article proposes a multiobjective many-tasking evolutionary algorithm (MMaTEA) using Diversified Gaussian-based knowledge Transfer, named MMaTEA-DGT. In this algorithm, a diversified transfer selection strategy is presented to choose a number of similar and complementary source tasks for knowledge transfer. Then, based on the above diversified source tasks, a Gaussian-based transfer strategy is designed to transfer their various optimization knowledge. In this way, MMaTEA-DGT is more effective in transferring optimization knowledge to speed up the solving of many tasks. Experimental studies on both the benchmark suites and a real-world dynamic vaccine prioritization problem have indicated the superiority of MMaTEA-DGT over some recently proposed MMaTEAs.

Authors: Fabrício Olivetti de França, Marco Virgolin, Michael Kommenda, Maimuna S. Majumder, Miles D. Cranmer, Guilherme Espada, Leon Ingelse, Alcides Fonseca, Mikel Landajuela, Brenden K. Petersen, Ruben Glatt, T. Nathan Mundhenk, Chak Shing Lee, Jacob D. Hochhalter, David L. Randall, P. Kamienny, Hengzhe Zhang, Grant Dick, Alessandro Simon, Bogdan Burlacu, Jaan Kasak, Meera Vieira Machado, Casper Wilstrup, William G. La Cava

Affiliations: Center for Mathematics, Computation and Cognition, Heuristics, Analysis and Learning Laboratory, Federal University of ABC, Santo André, Brazil; Evolutionary Intelligence Group, Centrum Wiskunde and Informatica, Amsterdam, The Netherlands; Heuristic and Evolutionary Algorithms Laboratory, University of Applied Sciences Upper Austria, Hagenberg, Austria; Computational Health Informatics Program, Boston Children’s Hospital, Harvard Medical School, Boston, MA, USA; Center for Computational Astrophysics, Flatiron Institute, New York, NY, USA; LASIGE, Faculdade de CiÃªncias, Universidade de Lisboa, Lisbon, Portugal; Computational Engineering Division, Lawrence Livermore National Laboratory, Livermore, CA, USA; Department of Mechanical Engineering, University of Utah, Salt Lake City, UT, USA; Meta, FAIR, Paris, France; Victoria School of Engineering and Computer Science, University of Wellington, Wellington, New Zealand; Department of Information Science, University of Otago, Dunedin, New Zealand; Institut für Angewandte Physik, Universität Tübingen, Tübingen, Germany; Autonomous Learning, Abzu AI, Nordhavn, Denmark

Abstract:
Symbolic regression (SR) searches for analytic expressions that accurately describe studied phenomena. The main promise of this approach is that it may return an interpretable model that can be insightful to users, while maintaining high accuracy. The current standard for benchmarking these algorithms is SRBench, which evaluates methods on hundreds of datasets that are a mix of real-world and simulated processes spanning multiple domains. At present, the ability of SRBench to evaluate interpretability is limited to measuring the size of expressions on real-world data, and the exactness of model forms on synthetic data. In practice, model size is only one of many factors used by subject experts to determine how interpretable a model truly is. Furthermore, SRBench does not characterize algorithm performance on specific, challenging subtasks of regression, such as feature selection and evasion of local minima. In this work, we propose and evaluate an approach to benchmarking SR algorithms that addresses these limitations of SRBench by 1) incorporating expert evaluations of interpretability on a domain-specific task, and 2) evaluating algorithms over distinct properties of data science tasks. We evaluate 12 modern SR algorithms on these benchmarks and present an in-depth analysis of the results, discuss current challenges of SR algorithms and highlight possible improvements for the benchmark itself.

Affiliations: Civil Engineering School, Qingdao University of Technology, Qingdao, China; Department of Computer Science, City University of Hong Kong, Hong Kong, SAR, China; Department of Computing, The Hong Kong Polytechnic University, Hong Kong, SAR, China; College of Science, China University of Petroleum (East China), Qingdao, China; School of Petroleum Engineering, China University of Petroleum (East China), Qingdao, China

Abstract:
Evolutionary sequential transfer optimization (ESTO), which aims to better optimize a target task using the knowledge extracted from a number of previously solved source tasks, has been gaining continually increasing research attention over the years. Particularly, solution-based ESTO (S-ESTO) that transfers task solutions has been receiving much popularity due to its ease of implementation and optimizer independency. However, the existing S-ESTO algorithms put much emphasis on utilizing source optimized solutions standing for global search experience without being aware of the potential of intermediate solutions that represent local optimization experience. Besides, most of them cannot take full advantage of the solution data from evolutionary search. In the light of the above, this study aims to develop a global and local search experience-based solution transfer technique to maximally release the potential of optimization experience hidden in the source tasks. First, a novel transferability metric named landscape encoding-based rank correlation (LERC) is developed. Then, we propose to divide the optimization experience into two classes: 1) global and 2) local search experience. Accordingly, by instantiating LERC into global and local versions, we develop two distinct transfer methods to exploit the global and local search experience, respectively. Finally, by combining the two transfer methods, we propose an S-ESTO algorithm that can transfer the global and local search experience simultaneously for maximum performance enhancement for the target task. Experiments conducted on a set of benchmark problems and a practical case study verify the efficacy of the proposed methods. The source code of our algorithm is available athttps://github.com/ccm831143/GL-LERC.

Affiliations: College of Automation and Electronic Engineering, Qingdao University of Science and Technology, Qingdao, Shandong, China; School of Mechatronic Engineering and Automation, Shanghai University, Shanghai, China; School of Information and Control Engineering, China University of Mining and Technology, Xuzhou, China; Electrical and Computer Engineering Department, University of Alberta, Edmonton, AB, Canada; School of Computer Science and Informatics, De Montfort University, Leicester, U.K.

Abstract:
Dynamic multiobjective evolutionary algorithms (DMOEAs) have gained great popularity in dealing with the dynamic multiobjective optimization problems (DMOPs). However, the existing studies have difficulties in tackling DMOPs subject to (dynamic) constraints. In this article, we propose a prediction and weak coevolutionary multiobjective optimization algorithm (PWDCMO) to handle the dynamic constrained multiobjective optimization problems (DCMOPs), where a prediction strategy is employed to forecast potential optimal regions under the new environment, with a weak coevolutionary constrained multiobjective optimization (CCMO) as the optimizer aiming at balancing exploration and convergence. The proposed method is compared with the four popular dynamic constrained multiobjective evolutionary algorithms (DCMOEAs) on six test instances from two various test suites with their convergence and the overall performance being discussed. Furthermore, the performance of the proposed prediction strategy is also investigated to observe its impact on the final results. Additionally, the PWDCMO is employed in the optimization of an integrated coal mine energy system (ICMES) to validate the proficiency in addressing real world problems. Experimental results demonstrate the superiority of PWDCMO.

Abstract:
In the past few decades, many multiobjective evolutionary optimization algorithms (MOEAs) have been proposed to find a finite set of approximate Pareto solutions for a given problem in a single run. However, in many real-world applications, it could be desirable to have structure constraints on the entire optimal solution set, which define the patterns shared among all solutions. The current population-based MOEAs cannot properly handle such requirements. In this work, we make a first attempt to incorporate the structure constraints into the whole solution set. Specifically, we propose to model such a multiobjective optimization problem as a set optimization problem with structure constraints. The structure constraints define some patterns that all the solutions are required to share. Such patterns can be fixed components shared by all solutions, specific relations among decision variables, and the required shape of the Pareto set. In addition, we develop a simple yet efficient evolutionary stochastic optimization method to learn the set model, which only requires a low computational budget similar to classic MOEAs. With our proposed method, the decision-makers can easily tradeoff the Pareto optimality with preferred structures, which is not supported by other MOEAs. A set of experiments on benchmark test suites and real-world application problems demonstrates that our proposed method is effective.

Affiliations: Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, School of Computer Science and Technology, Anhui University, Hefei, China; Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, School of Artificial Intelligence, Anhui University, Hefei, China; Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, Institutes of Physical Science and Information Technology, Anhui University, Hefei, China; Information Materials and Intelligent Sensing Laboratory of Anhui Province, Anhui University, Hefei, Anhui, China; Faculty of Technology, Bielefeld University, Bielefeld, Germany

Abstract:
Despite that the surrogate-assisted evolutionary algorithms have achieved great success in addressing expensive optimization problems, they still suffer from stiff challenges when the number of dimensions of problems becomes large. The primary reason lies in that it is very hard to build an acceptable surrogate model in the high-dimensional search space with small amounts of evaluated historical data in evolution. To tackle this issue, we suggest an effective surrogate modeling method for large-scale expensive optimization in this article, where the models are built on a number of linear subspaces instead of the original search space. Specifically, a linear subspace is constructed by a pair of points/solutions which are generated based on the set of elite solutions. For each linear subspace, several historical solutions are first associated according to their distance to the linear subspace, and then a surrogate model is trained by the associated solutions and used to evaluate the offspring. To ensure the exploration and exploitation capacity of the proposed method, these linear subspaces and the surrogate models are updated after a few iterations. Experimental results on CEC’2010 and CEC’2013 single-objective optimization problems with up to 1500 decision variables show that the proposed algorithm is superior over six comparison algorithms. Moreover, we also extend the proposed algorithm to multiobjective optimization problems and verified its competitiveness on problems with up to 1500 decision variables.

Abstract:
Surrogate-assisted evolutionary algorithms (SAEAs) have achieved effective performance in solving complex data-driven optimization problems. In the Internet of Things environment, the data of many problems are collected and processed in distributed network nodes and cannot be transmitted. As each local node can only access and build surrogate models based on partial data, local models are usually not accurate and even conflicting. To address these challenges, this article proposes a classifier-ensemble-based surrogate-assisted evolutionary algorithm (CESAEA) with the following features. First, the local nodes in CESAEA train classifiers as surrogate models based on their own data to classify candidates into several levels according to their fitness quality. The classifiers are less sensitive to the partial and biased data than regression models in local nodes. Second, the central node in CESAEA ensembles the local surrogates to form a global classifier with a relaxation condition to guide the evolutionary optimizer to generate promising candidates. The relaxation condition helps to overcome the problem of local model inconsistency. Overall, CESAEA is composed of local classifier construction, global classifier ensemble, classifier-assisted evolutionary optimization and local regression-assisted selection. As only classifiers are allowed to transmit from local nodes to the central node, the mapping relationship between decision vector and objective is hidden and thus data privacy is protected. The experimental results on benchmark functions as well as distributed feature selection problems verify the effectiveness of CESAEA compared to several state-of-the-art approaches.

Abstract:
Dynamic flexible job-shop scheduling (DFJSS) aims to achieve the optimal efficiency for production planning in the face of dynamic events. In practice, deep Q -network (DQN) algorithms have been intensively studied for solving various DFJSS problems. However, these algorithms often cause moving targets for the given job-shop state. This will inevitably lead to unstable training and severe deterioration of the performance. In this article, we propose a training algorithm based on genetic algorithm to efficiently and effectively address this critical issue. Specifically, a state feature extraction method is first developed, which can effectively represent different job-shop scenarios. Furthermore, a genetic encoding strategy is designed, which can reduce the encoding length to enhance search ability. In addition, an evaluation strategy is proposed to calculate a fixed target for each job-shop state, which can avoid the parameter update of target networks. With the designs, the DQNs could be stably trained, thus their performance is greatly improved. Extensive experiments demonstrate that the proposed algorithm outperforms the state-of-the-art peer competitors in terms of both effectiveness and generalizability to multiple scheduling scenarios with different scales. In addition, the ablation study also reveals that the proposed algorithm can outperform the DQN algorithms with different updating frequencies of target networks.

Affiliations: School of Automation, Central South University, Changsha, China; State Key Laboratory of Advanced Design and Manufacturing Technology for Vehicle, Hunan University, Changsha, China; Department of Computer Science and Engineering, and the Research Institute of Trustworthy Autonomous Systems, Guangdong Key Laboratory of Brain-Inspired Intelligent Computation, Southern University of Science and Technology, Shenzhen, China

Abstract:
This article proposes a surrogate-assisted evolutionary framework (called SELF) to solve expensive multitask optimization problems (ExMTOPs). SELF consists of two main phases: 1) global knowledge transfer phase and 2) local knowledge transfer phase. In the former, a multitask Gaussian process model (MTGP) is established by fusing previously evaluated solutions of multiple optimization tasks. MTGP can capture task-relevant information and the knowledge of landscapes. Then, differential evolution assisted with MTGP is proposed to preselect high-quality candidates. During the preselection, the knowledge of landscapes is transferred among multiple optimization tasks for locating promising regions quickly. In the latter, for each optimization task, Bayesian optimization is adopted to improve the quality of the best individual in the population. Moreover, the improved best individuals in the populations of multiple optimization tasks are adaptively transferred based on a transfer probability, which is computed through the task-relevant information provided by MTGP. By combining these two phases, SELF not only achieves the tradeoff between exploration and exploitation, but also utilizes the global and local knowledge transfer to improve the efficiency for solving ExMTOPs. We test SELF on seven benchmark test problems in the IEEE CEC2017 evolutionary multitask optimization competition. The results demonstrate that the performance of SELF is better than that of other seven advanced methods. In addition, we also apply SELF to deal with two real-world ExMTOPs. The designs provided by SELF exhibit the best performance among all the compared methods, verifying the potential of SELF in practical engineering applications.

Abstract:
Many combinatorial multiobjective optimization problems involve very costly-to-evaluate objectives and constraints. It is very difficult, if not impossible, for traditional heuristics to solve these problems with an acceptable amount of computational time. In this article, we show that offline machine learning can be very useful to assist multiobjective evolutionary algorithms to tackle this kind of problem. We take a complicated real-life multiobjective routing-packing problem as the test bed. We propose to use offline machine learning methods to replace time-consuming packing heuristics for packing feasibility prediction. Experiments show that the machine learning models can be 1000 times faster than some commonly used packing heuristics and their accuracy can be as high as 98%. We adopt decomposition-based multiobjective evolutionary algorithmic to decompose the problem into a number of single objective subproblems and solve them in a collaborative manner. We propose an encoding strategy to represent each routing scheme and use genetic operators to generate new routes. Experimental studies have been conducted on 100 instances from HUAWEI’s real-world logistics application and two test suites from the literature. Our proposed method can solve each HUAWEI instance in around 1 min. Our solutions on the two test suites are comparable to other existing algorithms, and the overall computational cost of our method is significantly lower than others.

Abstract:
Evolutionary algorithms (EAs) have shown promise in solving sequential decision problems (SDPs) by simplifying them to static optimization problems and searching for the optimal policy parameters in a zeroth-order way. Despite their versatility, EAs often suffer from high sample complexity due to neglecting underlying temporal structures. In contrast, reinforcement learning (RL) methods typically formulate SDPs as Markov decision process (MDP). Although more sample efficient than EAs, RL methods are restricted to differentiable policies and prone to getting stuck in local optima. To address these issues, we propose a novel evolutionary framework zeroth-order actor-critic (ZOAC). We propose to use stepwise exploration in parameter space and theoretically derive the zeroth-order policy gradient. We further utilize the actor-critic architecture to effectively leverage the Markov property of SDPs and reduce the variance of gradient estimators. In each iteration, ZOAC collects trajectories with parameter space exploration, and alternates between first-order policy evaluation (PEV) and zeroth-order policy improvement (PIM). We evaluate the effectiveness of ZOAC on a challenging multilane driving task optimizing the parameters in a rule-based, nondifferentiable driving policy that consists of three submodules: 1) behavior selection; 2) path planning; and 3) trajectory tracking. We also compare it with gradient-based RL methods on three Gymnasium tasks, optimizing neural network policies with thousands of parameters. Experimental results demonstrate the strong capability of ZOAC in solving SDPs. ZOAC significantly outperforms EAs that treat the problem as static optimization and matches the performance of gradient-based RL methods even without first-order information, in terms of total average return across tasks.

Abstract:
This article studies an energy-efficient hybrid flow-shop scheduling problem (EHFSP) considering variable machine speed (EHFSP-VMS). To minimize the makespan and total energy consumption simultaneously, a tree-based multiobjective evolutionary algorithm (TMOEA) is proposed. It decomposes a multiobjective optimization problem into multiple scalar optimization subproblems and optimizes them simultaneously. Moreover, different from existing multiobjective evolutionary algorithms (MOEAs), TMOEA maintains Pareto archive using a tree structure instead of a linear structure, which reduces the time complexity of updating Pareto solutions from O(P) to O(logP), where P is the size of Pareto archive. In TMOEA, the population evolution is performed in three stages. Stage one is responsible for local search, in which five different operators are combined in the form of a roulette wheel to explore promising solutions in neighboring regions. Stage two is responsible for global search, which uses a technique for order preference by similarity to an ideal solution (TOPSIS) to select promising solutions for crossover to promote the population to evolve toward the Pareto front. Stage three is responsible for preventing local optimality, where a neighbor exchange method and opposition-based learning strategy are adopted to escape the local optimal. Computational experiments demonstrate that the tree structure is effective and TMOEA is superior to the existing algorithms in solving EHFSP-VMS.

Abstract:
Robust multiobjective optimization problems (RMOPs) widely exist in real-world applications, which introduce a variety of uncertainty in optimization models. While some evolutionary algorithms have been developed to find optimal solutions robust to uncertainty, they are ineffective to handle RMOPs in high-dimensional decision spaces. Focusing on the large-scale RMOPs with sparse optimal solutions, this article proposes an evolutionary algorithm with novel strategies for the selection, generation, and evaluation of robust solutions. In order to handle the uncertainty in the optimization models, we first introduce an archive to separately consider optimality and robustness, which can achieve the selection of robust solutions effectively at a low cost. Based on the robust knowledge extracted from the archive, a guiding vector is adaptively updated to facilitate the generation of robust solutions in high-dimensional decision spaces. With the assistance of the guiding vector, a robustness indicator is suggested to assist in the evaluation of robust solutions without additional perturbations. Besides, we design a test suite to evaluate the performance of the proposed algorithm on the large-scale RMOPs. Our experimental results demonstrate that the proposed algorithm has significant advantages over the state-of-the-art evolutionary algorithms in terms of optimality and robustness, on both the proposed test suite and practical applications.

Abstract:
Surrogate-assisted evolutionary algorithms (SAEAs) have shown promising performance in tackling expensive multiobjective optimization problems (EMOPs). However, existing SAEAs solve EMOPs separately, which ignore their optimization experiences earned before. Inspired by multitasking optimization paradigm for multitasking multiobjective optimization problems (MTMOPs), this article designs the first SAEA for tackling expensive MTMOPs (EMTMOPs) with adaptive knowledge transfer. First, a competitive surrogate selection is proposed to improve the generalization ability of approximating various EMOP tasks, where two types of surrogate models are trained and then compete for use to replace real expensive evaluations. Then, an adaptive solution selection is designed, which identifies promising transfer solutions to accelerate the solving of target task and selects promising infill solutions for real expensive evaluations to refine the surrogate models. The performance of our algorithm is validated on three commonly used benchmark suites and some real-world EMTMOPs. The experiments validate our superiority over several state-of-the-art SAEAs on most test cases.

Abstract:
Knowledge transfer (KT) has been regarded as an efficient method in evolutionary multitask optimization (EMTO) by utilizing the information of other tasks to promote the optimization of the current task. Most KT methods achieve information communication across index-aligned dimensions. However, the index-aligned dimensions are not always similar or related, which is not always suitable for communication and causes the low efficiency in KT. Moreover, when the KT occurs in the heterogeneous tasks with different dimensions, the task with lower dimensions often pads the extra dimensions to make their dimensions equal. However, the dimension-padding often involves the redundant or useless information, which may mislead the KT process. In this article, a novel multilevel and multisegment learning multitask optimization (MMLMTO) algorithm based on niching technique is proposed to achieve high-quality KT. First, a multilevel learning strategy is proposed to divide the population into three levels according to fitness values for better selecting the individuals for KT. Second, a multisegment learning strategy is proposed to split some top individuals in each level into several segments, and each segment will find its closest segment to form a niche, where the KT is executed. This ensures that KT occurs in the similar or related dimensions and avoids the dimension-padding to eliminate the influence of the redundant information. Experimental results on IEEE CEC2017 and IEEE CEC2022 multitask benchmarks fully demonstrate the effectiveness of MMLMTO, which can significantly outperform other state-of-the-art multitask algorithms. Finally, MMLMTO is applied to a real-world multitask rover navigation application problem to further demonstrate its applicability.

Abstract:
Competitive multiobjective multitask optimization (CMO-MTO) problems involve multiple tasks with comparable objectives but heterogeneous decision variables. The final Pareto front (PF) in CMO-MTO consists of multiple subsets corresponding to different tasks. Since the PF subset of one task may be dominated by that of another, competition arises among tasks. Additionally, there may be exploitable similarities among tasks that evolutionary multitasking methods can leverage. For a comprehensive study of CMO-MTO, we construct 12 benchmark CMO-MTO problems with varied competitive relationships and intertask similarities. To effectively solve CMO-MTO problems, we propose a reference vector contribution-based multitask evolutionary algorithm (RVC-MTEA). RVC-MTEA facilitates both global and local knowledge transfer based on vector contributions and integrates global archives to gather nondominated solutions across multiple competitive tasks. Comparative results with four popular single-task and six state-of-the-art multitask evolutionary algorithms demonstrate the efficacy of RVC-MTEA. Finally, we apply RVC-MTEA to several real-world applications, showcasing the potential of CMO-MTO in practical decision-making scenarios.

Abstract:
The existing constrained multiobjective evolutionary algorithms (CMOEAs) still have great room for improvement in balancing population’s convergence, diversity and feasibility on complex constrained multiobjective optimization problems (CMOPs). Besides, their effectiveness deteriorates dramatically when facing the CMOPs with scaling-up objective space or search space. We are thus motivated to design a learning-aided CMOEA with promising problem-solving ability and scalability for various CMOPs. In the proposed solver, two learning models are, respectively, trained online on constrained-ignored task and feasibility-first task, which are then used to learn the two improvement-based vectors for enhancing the search by differential evolution. In addition, the union population of parent and child solutions is divided into multiple subsets with a hierarchical clustering based on cosine similarity. A comprehensive indicator, considering objective-based performance and constraint violation degree of a solution, is developed to select the representative solution from each cluster. The effectiveness of the proposed optimizer is verified by solving the CMOPs with various irregular Pareto fronts, the number of objectives ranging from 2 to 15, and the dimensionality of search space scaling up to 1000.

Abstract:
Ribonucleic acid (RNA) design, also known as the RNA inverse folding problem, involves discovering a nucleotide sequence that folds into a target structure. This problem has been addressed from a wide number of approaches, improving the ability to solve it in a reasonable time over time. Despite all these efforts, today no method has completely solved the problem. We present GREED-RNA, a new RNA design algorithm, based on a simple greedy evolutionary strategy. The main feature is the use of several objective functions (base-pair distance, Hamming distance, probability over ensemble, partition function, ensemble defect, and GC-content) to select the best solution in each iteration, changing their weight according to the problem-solving conditions. The performance of GREED-RNA was tested using the Eterna100 benchmark, widely used in this area and never fully solved by any method. In addition, a comparative analysis against several published RNA design methods considering three metrics (solved structures, success rate, and execution time), allowed us to verify that GREED-RNA performs better than previously developed methods, thus successfully improving the current ability to solve this problem. This tool also allows users to select a range within which the GC-content of the solution sequences must fall. Source code and results are available at https://github.com/iARN-unex/GREED-RNA.

Affiliations: School of Automation, the Hubei Key Laboratory of Advanced Control and Intelligent Automation for Complex Systems, and the Engineering Research Center of Intelligent Technology for Geo-Exploration, Ministry of Education, China University of Geosciences, Wuhan, China; School of Artificial Intelligence, Anhui University of Sciences and Technology, Hefei, China; School of Mechanical Engineering and Electronic Information, China University of Geosciences, Wuhan, China; School of Computer Science and Informatics, De Montfort University, Leicester, U.K.; Department of Computer Science, CINVESTAV-IPN, Mexico, Ciudad de México, Mexico

Abstract:
Fitness landscape analysis (FLA) is quite important in evolutionary computation. In this article, we propose a novel FLA method, the nearest-better network (NBN), which uses the nearest-better relationship to simplify the original fitness landscape of continuous optimization problems. We introduce an efficient algorithm to calculate NBN for continuous problems. We also propose four numerical measurements and a 3-D visualization method based on NBN. Experiments show that compared to the other main FLA methods, the four numerical measurements proposed here can effectively measure the four intended features: 1) neutrality; 2) ruggedness; 3) modality; and 4) Basin of Attraction, respectively, and common features of the fitness landscape can be maintained in 3-D NBN visualization, regardless of the scale of the problem. NBN also provides a view of how algorithms search in high-dimensional problems with the help of the 3-D NBN visualization.

Abstract:
Fine-grained image classification (FGIC) is an important computer vision task with many real-world applications. However, FGIC is challenging due to intraclass variations and interclass similarities, especially when there is limited training data. To address these challenges, a new genetic programming approach with flexible region detection (GP-RD), is proposed for different FGIC tasks, i.e., flower and fish classification tasks. The proposed GP-RD approach can automatically highlight the object, detect regions of interest, extract effective features, and combine global, local, and/or color features for classification. The performance of GP-RD is evaluated on flower and fish classification tasks within the FGIC domain, utilizing datasets with varying classes. In comparison with seven benchmark methods, GP-RD achieves significantly better performance in most comparisons. Further analysis demonstrates the interpretability, effectiveness, and efficiency of the proposed approach.

Abstract:
Recent theoretical works have shown that the NSGA-II efficiently computes the full Pareto front when the population size is large enough. In this work, we study how well it approximates the Pareto front when the population size is smaller. For the OneMinMax benchmark, we point out situations in which the parents and offspring cover well the Pareto front, but the next population has large gaps on the Pareto front. Our mathematical proofs suggest as reason for this undesirable behavior that the NSGA-II in the selection stage computes the crowding distance once and then removes individuals with smallest crowding distance without considering that a removal increases the crowding distance of some individuals. We then analyse two variants not prone to this problem. For the NSGA-II that updates the crowding distance after each removal [Kukkonen and Deb (2006)] and the steady-state NSGA-II [Nebro and Durillo (2009)], we prove that the gaps in the Pareto front are never more than a small constant factor larger than the theoretical minimum. This is the first mathematical work on the approximation ability of the NSGA-II and the first runtime analysis for the steady-state NSGA-II. Experiments also show the superior approximation ability of the two NSGA-II variants.

Affiliations: Key Laboratory of Image Information Processing and Intelligent Control of Education Ministry of China, School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan, China; School of Artificial Intelligence, Xidian University, Xi’an, China; School of Electrical and Electronic Engineering, Huazhong University of Science and Technology, Wuhan, China; Department of Computing, The Hong Kong Polytechnic University, Hong Kong, SAR; Trustworth and General Artificial Intelligence Laboratory, School of Engineering, Westlake University, Hangzhou, China

Abstract:
In recent decades, various surrogate-assisted evolutionary algorithms (SAEAs) have been proposed to solve computationally expensive multiobjective optimization problems (EMOPs). Nevertheless, designing an SAEA to handle high-dimensional EMOPs and balance convergence, diversity, and computational complexity remains challenging. Here, we propose a two-phase SAEA (TP-SAEA), which follows the idea of convergence first and diversity second, for solving high-dimensional EMOPs. In Phase I, a surrogate-assisted problem reformulation method is proposed to fast-track the Pareto optimal set in association with some reference solutions. Specifically, the high-dimensional EMOP is reformulated into an expensive single-objective one with low-dimensional decision space. Then, the surrogate-assisted optimization is utilized to obtain well-converged solutions. In Phase II, the high-dimensional EMOP is decomposed into two subproblems to explore subregions of the decision space that can effectively promote the diversity of the solutions. The two subproblems are optimized independently via surrogate-assisted optimization, aiming to push the population toward different regions of the Pareto optimal front. Experiments are conducted on EMOPs with 100 to 500 decision variables compared with four state-of-the-art SAEAs. The proposed TP-SAEA obtains well-converged and diverse solutions with only 509 real function evaluations. Moreover, its superiority is examined in six real-world instances with up to 12 000 decision variables.

Abstract:
We analyze three permutation-based combinatorial optimization problems in Fourier space, namely, the quadratic assignment problem, the linear ordering problem (LOP), and the symmetric and nonsymmetric traveling salesperson problem (STSP). In previous studies, one can find a number of theorems with necessary conditions that the Fourier coefficients of the aforementioned problems must satisfy. In this manuscript, we prove the sufficiency of these conditions, which implies that they constitute the exact characterization of the problems in Fourier space. In addition, the Fourier coefficients of the LOP and the symmetric and non-STSP are completely characterized by showing certain proportionality patterns that they must follow. Taking the characterization in Fourier space of the problems as a basis, we study classes of equivalent instances of the LOP and the symmetric and non-STSP, considering that two instances are equivalent if they have the same objective function. Furthermore, we give canonical representations for each problem in such a way that the input matrices have the minimum number of nonzero parameters.

Affiliations: School of Automation, Central South University, Changsha, China; State Key Laboratory of Advanced Design and Manufacturing Technology for Vehicle, Hunan University, Changsha, China; Department of Computer Science and Engineering, Guangdong Key Laboratory of Brain-Inspired Intelligent Computation, Research Institute of Trustworthy Autonomous Systems, Southern University of Science and Technology, Shenzhen, China

Abstract:
This article proposes a new parameterless constraint-handling technique, named constrained probabilistic Pareto dominance (CPPD), for expensive constrained multiobjective optimization problems (CMOPs). In CPPD, when comparing two solutions, in terms of each original objective, we design a new objective for each solution, which is the negative product of two probabilities calculated based on the predicted fitness mean values and uncertainty information provided by Kriging models: 1) the probability that this solution satisfies all constraints, denoted as Probability of Feasibility (PoF) and 2) the probability that this solution is better than the other on the original objective, denoted as PoB. It is evident that for each solution, PoF and PoB indicate its feasibility and its optimality on the corresponding original objective, respectively. Then, Pareto dominance based on new objectives is executed. As a result, both competitive feasible solutions and promising infeasible solutions with good diversity can be preserved by CPPD. These two kinds of solutions can help the population to exploit the located feasible parts and to explore new feasible parts, respectively. Further, based on CPPD, we develop a Pareto-based Kriging-assisted constrained multiobjective evolutionary algorithm (called PEA) to deal with expensive CMOPs with two or three objectives. Finally, PEA is generalized to solve expensive constrained many-objective optimization problems, named \textrm PEA^+ . The effectiveness of CPPD, PEA, and \textrm PEA^+ is verified by comprehensive experiments.

Abstract:
Measuring the diversity of a Pareto front approximation (PFA) is critical when comparing the performance of multiobjective evolutionary algorithms (MOEAs). In the literature, some quality indicators (QIs) measure diversity according to their specific preferences. However, just a few QIs have mathematical properties proven. In this article, we propose the Riesz s-energy (E_s) as a QI to evaluate the diversity and spread of PFAs. Theoretical results show that E_s holds 1) some of the Weitzman properties of a desirable diversity QI; 2) monotonicity; 3) the submodularity property (for -E_s ); and 4) that it is invariant under rotations. We provide numerical evidence on the behavior of E_s in both artificial PFAs and PFAs generated by state-of-the-art MOEAs. The mathematical properties that E_s satisfies show its usefulness when it is utilized as a diversity QI in evolutionary multiobjective optimization.

Abstract:
Quality indicators play an essential role in evolutionary multiobjective optimization (EMO). Most likely the most often used quality indicator in EMO is hypervolume, due to its strict monotonicity with respect to the dominance relation. However, hypervolume is not free of some weak points. For example, a number of recent papers pointed out its high sensitivity to the specification of the reference point. Furthermore, hypervolume is based on fully geometric reasoning which may lead to some undesired results. Thus, it is worth to consider also other quality indicators. In this article, we prove that another well-known R2 quality indicator is also strictly monotonic with respect to the dominance relation when calculated exactly and the reference point strongly dominates any solution in the evaluated set. Furthermore, we adapt the improved quick hypervolume algorithm to the exact calculation of R2 indicator. To our knowledge, this is the first exact algorithm for R2 calculation with publicly available implementation. In addition, through both theoretical analysis and computational experiments, we show that R2 performs consistently for Pareto fronts with different shapes. We discuss also differences of Pareto fronts representations generated by an indicator-based EMO with hypervolume and R2 , where the latter tends to generate solutions having a high chance to be preferred by the decision maker, not necessarily uniformly distributed in geometric sense. All of these results make R2 a sound alternative or a complement to hypervolume in EMO.

Abstract:
In the realm of evolutionary multiobjective optimization, the hypervolume (HV) indicator serves as a crucial metric for assessing the quality of solution sets. Due to the high costs in HV computation, HV-based optimization algorithms always meet the challenge of finding a certain number of points in a given point set to maximize the HV indicator, especially when there are many objectives. In response, the greedy decremental algorithm for HV subset selection problem (gHSSD) has emerged as a noteworthy alternative. This article introduces a general algorithm for gHSSD, applicable in any dimensionality above two. The proposed algorithm leverages a space partition tree and incorporates a once-build-multiple-use strategy, effectively reducing time complexity. We prove that the proposed algorithm has a time complexity of O((n-k+\sqrt n)n^(d-1/2)\log n) where n is the number of points, k is the number of points to be reserved, and d the dimensionality. Theoretically, this complexity is competitive with the current best algorithms for d=3, 4 and better than them for all 5\le d\le 7 . To validate our algorithm, we have conducted extensive tests on various random point sets and multiobjective optimization benchmarks. Experimental results suggest that our implementation is more efficient than or competitive with state-of-the-art algorithms on many instances as n increases for d=3,4 .

Abstract:
This article attempts to derive a mathematical formulation for real-practice clinical laboratory scheduling, and to present a syntactic problem solver by leveraging instances’ landscape structures to infer the most suitable search strategy. After formulating scheduling of medical tests as a distributed scheduling problem in heterogeneous, flexible job shop environment, we establish a mixed integer programming model to minimize mean test turnaround time. Preliminary landscape analysis sustains that these clinics-orientated scheduling instances are difficult to solve under the same search strategy. The search difficulty motivates the search for a syntactic problem solver where relatedness between domain’s syntactic features and search strategies help identify effective strategies. The challenge in designing a syntactic problem solver—which landscape features to choose as domain’s syntactic features to accurately reflect instance hardness under different search strategies—are addressed. Under various local search move operators, we investigate the changes in instance landscape structures and find that the single-move size for local search operators, local-global optima connectivity, landscape ruggedness, and plateau size fairly predict the efficacy of the local searches. The above relationship is refined into a deterministic association between instance size and local search, thereby forming the syntactic problem solver. When faced with new instances, the solver automatically instantiates the best local search algorithm for various scenarios. Extensive experiments demonstrate that the proposed syntactic solver excels not only in clinical laboratory scheduling problems but also in publicly available benchmark.

Abstract:
Hypervolume is most likely the most often used quality indicator in evolutionary multiobjective optimization (EMO) due to its monotonicity with respect to the dominance relation. Since, however, exact calculation of hypervolume is computationally demanding, many researchers have proposed methods for hypervolume estimation. Many of such methods use numerical integration of the distance from the reference point to the upper boundary of the dominated region along uniformly sampled directions. To find this distance for a given direction, the maximum value of the inverse weighted Chebycheff function needs to be found. For small solution sets this could be done by the exhaustive search which, however, may be very inefficient for large solution sets, e.g., for unbounded external archives of the EMO algorithms. In this article, we adapt the ND-Tree-based algorithm for finding the minimum of the standard weighted Chebycheff function to finding the maximum of the inverse function. Through a computational experiment we show that this ND-Tree-based algorithm may be used either for reduction of the running time of hypervolume estimation by up to two orders of magnitude or for improving the estimation accuracy with the same time budget up to an order of magnitude for data sets with up to 12 objectives and 50 000 points.

Abstract:
Constrained multiobjective optimization problems (CMOPs) have multiple objective functions that need to be optimized and constraints need to be satisfied, making them difficult to solve. Based on the multitasking optimization, the optimization of the original CMOP can be transformed into multiple related subtasks. Existing multitasking-based constrained multiobjective optimization evolutionary algorithms assist the evolution of the original problem by adopting auxiliary tasks. However, this approach may waste computational resources on tasks that are unsuitable for evolutionary states and dynamics. In this article, a new competitive multitasking-based framework is proposed for CMOPs. We maintain an archive for the constrained Pareto front (CPF) and multiple subtasks as auxiliaries. In each iteration, one of the subtasks is selected as the main task, and offspring are generated from its evolution. The offspring are viewed as knowledge and fed back to auxiliary tasks. The reward is mapped to a selection probability to control the main task selection in each iteration. Computational resources are saved by allocating only to the main task that is better suited for different evolutionary stages of different problems. The effectiveness of our approach is validated through experiments on four CMOP benchmark suites compared to 11 state-of-the-art methods.

Abstract:
Quality diversity (QD) algorithms, such as the multidimensional archive of phenotypic elites (MAP-Elites), are a class of optimization techniques that attempt to find many high-performing points that all behave differently according to a user-defined behavioral metric. In this article we propose the Bayesian optimization of elites (BOP-Elites) algorithm. Designed for problems with expensive fitness functions and coupled behavior descriptors, it is able to return a QD solution-set with excellent performance already after a relatively small number of samples. BOP-Elites models both fitness and behavioral descriptors with Gaussian Process surrogate models and uses Bayesian optimization strategies for choosing points to evaluate in order to solve the quality-diversity problem. In addition, BOP-Elites produces high-quality surrogate models which can be used after convergence to predict solutions with any behavior in a continuous range. An empirical comparison shows that BOP-Elites significantly outperforms other state-of-the-art algorithms without the need for problem-specific parameter tuning.

Abstract:
The coupling of multiple constraints can pose difficulties in solving constrained multiobjective optimization problems (CMOPs). Existing constrained multiobjective evolutionary algorithms (CMOEAs) often overlook this issue by considering all constraints together. This article proposes MTOTC, a novel multitasking optimization algorithm that addresses this challenge through a task clone technique. MTOTC clones the target CMOP with q constraints into q+1 copies, resulting in a total of q+2 tasks. Each cloned task is handled using an independent population that considers a unique constraint-handling sequence, effectively decoupling the constraints in q+1 different ways. Additionally, the algorithm incorporates online information sharing between the target task and cloned tasks, enabling the utilization of valuable search history as much as possible. Experimental results on four recently developed complex CMOP benchmark suites and a series of real-world CMOPs demonstrate the superior performance of MTOTC compared to seven state-of-the-art CMOEAs.

Abstract:
Directed evolution, a strategy for protein engineering, optimizes protein properties (i.e., fitness) by a rigorous and resource-intensive process of screening or selecting among a vast range of mutations. By conducting an in-silico screening of sequence properties, machine learning-guided directed evolution (MLDE) can expedite the optimization process and alleviate the experimental workload. In this work, we propose a general MLDE framework in which we apply recent advancements of deep learning in protein representation learning and protein property prediction to accelerate the searching and optimization processes. In particular, we introduce an optimization pipeline that utilizes the large language models (LLMs) to pinpoint the mutation hotspots in the sequence and then suggest replacements to improve the overall fitness. Our experiments have shown the superior efficiency and efficacy of our proposed framework in the conditional protein generation, in comparison with the other state-of-the-art baseline algorithms. We expect this work will shed a new light on not only protein engineering but also on solving the combinatorial problems using the data-driven methods.

Abstract:
Evolutionary algorithms (EAs) for optimization have received wide attention due to their robustness and practicality. However, the traditional way of asynchronously handling bilevel optimization problems (BLOPs) ignores the benefits brought by effective upper- and lower-level collaboration. To address this issue, this article proposes a collaborative multiobjective transformation (MOT)-based EA (MOTEA-II). In MOTEA-II, the BLOP is handled within a decomposition-based multiobjective optimization paradigm using a two-stage collaborative MOT strategy. The stage-1 MOT focuses on multiple lower-level optimizations and collaboration, while stage-2 collaborates the upper-level optimization with lower-level optimization, which makes simultaneously horizontal and vertical optimization information sharing in bilevel optimization possible. In addition, a dynamic decomposition strategy is further proposed to reconstruct the hierarchy relationship in collaborative multiobjective optimization, facilitating the adaptive and flexible importance control of the upper-level objective optimization and lower-level optimality satisfaction for better-bilevel search efficiency. Empirical studies are conducted on two groups of commonly used BLOP benchmark suites and four practical applications. Experimental results show that the proposed collaborative MOTEA-II can achieve performance comparable to that of the previous MOTEA and three other representative EA-based bilevel optimization approaches, but using much fewer computational resources.

Abstract:
Transfer multiobjective optimization promises sample-efficient discovery of near Pareto-optimal solutions to a target task by utilizing experiential priors from related source tasks. In this article, we show that in domains where evaluation data is at a premium, e.g., in scientific and engineering disciplines involving time-consuming computer simulations or complex real-world experimentation, knowledge transfer through surrogate models can be pivotal in saving sample evaluation costs. While state-of-the-art algorithms (without transfer) typically assume budgets in the order of only a few hundred evaluations, we seek to explore how far we can get on even tighter budgets. The uniqueness of our proposed expensive transfer evolutionary multiobjective optimizer (ExTrEMO) is that it can maximally utilize external information from hundreds of source datasets, including those that may be negatively correlated with the target task. This is achieved by melding evolutionary search with factorized transfer Gaussian process surrogates, capturing varied source-target correlations in potentially decentralized computation environments. We provide a regret bound analysis for ExTrEMO that translates to a theoretical proof of increasingly faster convergence as a result of multisource transfers. The theory is experimentally verified on benchmark functions and toward accelerated design of biomedical microdevices. We release our code at https://github.com/LiuJ-2023/ExTrEMO.

Affiliations: Department of Computing, The Hong Kong Polytechnic University, Hong Kong, SAR, China; Department of Artificial Intelligence, Key Laboratory of Digital Protection and Intelligent Processing of Intangible Cultural Heritage of Fujian and Taiwan, Ministry of Culture and Tourism, School of Informatics, and the Key Laboratory of Multimedia Trusted Perception and Efficient Computing, Ministry of Education of China, Xiamen University, Xiamen, Fujian, China; College of Computer Science, Chongqing University, Chongqing, China

Abstract:
Evolutionary multitasking (EMT) is an emerging research direction within the evolutionary computation community, attempting to concurrently solve multiple optimization tasks by exploiting the underlying synergies between the tasks. Recently, numerous explicit transfer strategies have been developed for enhancing 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 information from the target task in solution selection. As a result, the transferred solutions could not well adapt to the target task, thus limiting the effectiveness of knowledge transfer across tasks. To address this issue, this article proposes a solution selection method based on the lower confidence bound (LCB) for EMT, which is designed by leveraging task-specific information of both source and target tasks. With the proposed LCB metric, a number of high-quality solutions that could be more helpful for the target task can be selected and transferred to enhance positive transfer in EMT. To verify the effectiveness of the proposed approach, the solution selection method is embedded into several existing EMT algorithms and then evaluated on the single-objective multitasking benchmarks, the multiobjective multitasking benchmark, and a real-world application. The obtained results confirmed the generality and efficacy of the proposed solution selection approach.

Abstract:
Evolutionary multitasking (EMT) exploits the correlation among different tasks to help handle them through knowledge transfer (KT) techniques in evolutionary algorithms. In this area, multiobjective multitask optimization (MO-MTO) utilizes EMT to solve multiple multiobjective optimization tasks simultaneously. The key to addressing MO-MTO problems (MO-MTOPs) is to transfer appropriate knowledge among optimization tasks to assist the multiobjective evolutionary process. Both the type and the amount of knowledge can significantly affect the KT process. To achieve better KT behavior, we propose a multiple knowledge types and transfer adaptation (MKTA) framework for handling MO-MTOPs. The MKTA framework incorporates multiple types of knowledge in order to obtain comprehensive KT performance. It also provides transfer adaptation strategies to control: 1) the type of knowledge and 2) the amount of knowledge for KT via parameter adaptation approaches, thereby mitigating negative KT. Furthermore, we propose an evolution-path-model-based knowledge type and incorporate the existing unified-search-space-based knowledge type to form the knowledge pool for MKTA. Finally, the MKTA framework is coupled with a ranking-based differential evolution operator to constitute the complete algorithm MTDE-MKTA. In the experimental study, MTDE-MKTA outperformed ten advanced algorithms on 39 benchmark MO-MTOPs and six groups of realworld application problems.

Abstract:
Dynamic constrained multiobjective optimization problems (DCMOPs) are widely encountered in real-world applications and have attracted increasing attention in the evolutionary computation community. Existing studies primarily focus on the population initialization, but disregard to improve the evolution process. In DCMOPs, the knowledge is undoubtedly more abundant as the existence of historical environments. Therefore, extracting and utilizing useful knowledge from historical environments can further improve the evolution process. In this article, a history-assisted two-state auxiliary task collaboration approach is proposed to solve DCMOPs by conducting a more effective auxiliary task. Specifically, the algorithm indicates that constrained Pareto-optimal front (CPF) in similar historical environments is more suitable as an auxiliary task for current evolution, as it is closer to the current CPF. To identify the most suitable environment from extensive historical environments, a novel prediction-based similar environment identification method is proposed for the auxiliary task. To fully utilize the novel auxiliary task, an experience-driven two-state environmental selection strategy is proposed, which conditionally considers both historical and current information. In this strategy, individuals in state A are inclined to promote toward the historical CPF while disregarding the dominance relationship or constraints, to help cross infeasible region and approach CPF rapidly. For those individuals in state B, dominance relationship is taken into consideration, further bringing auxiliary task closer to the main task. The superiority of the proposed algorithm has been comprehensively demonstrated by experimental comparison results on a variety of benchmark test problems and a real-world problem with raw ore allocation in mineral processing.

Abstract:
Hypervolume subset selection (HSS) has received significant attention since it has a strong connection with evolutionary multiobjective optimization (EMO), such as environment selection and post-processing to identify representative solutions for decision-makers. The goal of HSS is to find the optimal subset that maximizes the hypervolume (HV) indicator subject to a given cardinality constraint. However, existing HSS algorithms or related methods are not efficient in achieving good performance in high-dimensional objective spaces. This is primarily because HSS problems become NP-hard when the number of objectives exceeds two, and the calculation of HV contribution (HVC) is very time-consuming. To efficiently solve HSS problems while maintaining a good solution quality, we propose a fast and scalable HSS method for many-objective optimization based on the determinantal point process (DPP), named DPP-HSS, which is fully free of HVC calculation. Specifically, DPP-HSS constructs an HV kernel matrix by extracting the convergence and diversity representations of each solution for a given HSS problem. This matrix is then used to build a DPP model. Subsequently, the original HSS problem is reformulated as a new maximization optimization problem based on the constructed model. A greedy DPP-based HSS algorithm is implemented to solve this transformed problem. Extensive experiments show that the proposed DPP-HSS achieves significant speedup and good HV performance in comparison with state-of-the-art HSS algorithms on benchmark problems. Furthermore, DPP-HSS demonstrates very good scalability with respect to the number of objectives.

Abstract:
Traditional multiobjective evolutionary algorithms (MOEAs) face challenges when addressing sparse large-scale multiobjective optimization problems (SLSMOPs) with many zero decision variables. The “large-scale” refers to the high dimensionality of the decision space, making it difficult for traditional MOEAs to traverse vast expanses efficiently with limited computational resources. Furthermore, In sparse contexts, most variables in Pareto optimal solutions are zero. It is difficult for traditional MOEAs to identify nonzero variables’ positions efficiently. In reinforcement learning, Thompson sampling employs a probability distribution to estimate each item’s value or success probability. Drawing inspiration from this concept, we propose a Thompson sampling-based sparse evolutionary operator (TSSEO). TSSEO maintains a probability distribution for each variable and utilizes this distribution to recommend for the variable, assisting MOEAs in transitioning from high-dimensionality dense to sparse spaces. Experimental results show that when integrated with representative MOEAs, TSSEO performs competitively in three real-world problems and eight benchmark problems involving up to 10041 decision variables, compared to algorithms designed explicitly for SLSMOPs.

Abstract:
Customized bus (CB), as an emerging urban shared transportation mode, can provide residents with flexible, high-quality, economical, and efficient transportation services. Most studies assumed that CBs transport passengers directly from their origin to destination without transfer, leading to potential inefficiencies and underutilization of capacity. This article establishes a mixed-integer nonlinear programming model for the CB network design problem that comprehensively considers passenger transfer, heterogeneous fleet, and holding control strategies. The model jointly optimizes routes, timetables (including arrival time and holding time for each vehicle at each station), and passenger-route assignment schemes to meet all the travel demands while simultaneously reducing operational costs. To solve the model, a linearization technique and an improved particle swarm optimization (IPSO) algorithm are, respectively, proposed for exact and near-optimal solutions. To validate the effectiveness and applicability of the proposed method, numerical experiments are conducted on the Sioux Falls network and a large-scale dataset from Beijing, China. The results demonstrate that the IPSO algorithm can effectively provide high-quality solutions compared to the GUROBI solver and benchmark algorithms. Furthermore, incorporating passenger transfers, heterogeneous fleets, and holding control strategies can effectively reduce operational costs and optimize the utilization of transportation resources.

Affiliations: Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education and the School of Artificial Intelligence, Anhui University, Hefei, China; Information Materials and Intelligent Sensing Laboratory of Anhui Province, Anhui University, Hefei, Anhui, China; Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education and the Institutes of Physical Science and Information Technology, Anhui University, Hefei, China; Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education and the School of Computer Science and Technology, Anhui University, Hefei, China

Abstract:
Multitasking multiobjective evolutionary algorithms (MMEAs) have been extensively studied in the past decade, which mainly concentrate on multitasking multiobjective optimization problems (MMOPs) with dozens of decision variables. Nevertheless, many real-world MMOPs have thousands of decision variables and are of sparse nature, which are regarded as large-scale MMOPs (LSMMOPs) in this study. To address LSMMOPs, a sparsity knowledge transfer-based evolutionary multiobjective algorithm, termed EMO-SKT, is proposed for efficiently finding high-quality sparse solutions of LSMMOPs. For each target optimization task, a sparsity knowledge transfer strategy extracts sparse distribution information from a source task and incorporates the information into the target task for two types of sparsity knowledge: 1) variable importance and 2) sparse degree. The variable importance is utilized to produce high-quality sparse solutions during the evolutionary search for EMO-SKT, while the sparse degree facilitates the reduction of search space and thus speeds up the convergence of the evolutionary search. Experimental results on eight benchmark problems and six practical LSMMOPs demonstrate the effectiveness of the sparsity knowledge transfer strategy. Furthermore, the proposed EMO-SKT is capable of efficiently finding high-quality sparse solutions on an LSMMOP with over 1000 decision variables. In comparison with five state-of-the-art multitasking or sparse optimization algorithms, the proposed EMO-SKT exhibits superior performance in terms of both solution quality and search efficiency.

Abstract:
This article proposes a distribution information-based Kriging-assisted evolutionary algorithm (named DISK) to tackle expensive many-objective optimization problems (EMaOPs). In DISK, we design a new Pareto dominance relationship (called DIPD) to guide the evolutionary search and candidate selection. DIPD works based on the Kriging models and incorporates the decision-space distribution information of the nondominated solutions in the database. Such distribution information can be used to assess the possibility of an unknown solution being located in/close to the decision-space promising region. Thanks to this property, DIPD is capable of preserving the predicted elitist solutions located in/close to the decision-space promising region. These solutions are very likely to possess good original Pareto optimality and are beneficial for improving the convergence of the nondominated-solution set in the database. In addition, to further ensure the diversity of the nondominated-solution set in the database, we also design an adaptive exploration strategy, which explores the objective-space unknown region farthest away from the nondominated solutions in the database once the optimization process stagnates. Furthermore, through a feasibility-first mechanism, we extend DISK to deal with constrained EMaOPs, obtaining \textrm DISK^+ . Finally, we verify the competitiveness of DISK and \textrm DISK^+ via extensive experiments.

Abstract:
The rooted max tree coverage (MTC) problem has wide applications in areas, such as network design and vehicle routing. Given a graph with non-negative costs defined on edges, a vertex used as the root, and a budget, the rooted MTC problem asks to find a tree containing the root and having total cost at most the budget, so that the number of vertices spanned by the tree is maximized. Rooted MTC is NP-hard and has constant factor approximation algorithms. However, the existing approximation algorithms for rooted MTC are very complicated and hard to be implemented practically. In this article, we formulate a polynomial size mixed integer linear program (MILP) for rooted MTC for the first time. Based on this, we develop a simple evolutionary algorithm for rooted MTC (called CMSA-MTC) using the CMSA meta-heuristic, where construct, merge, solve, and adapt (CMSA) is a meta-heuristic proposed recently. Experimental results show that CMSA-MTC has very good practical performance. For the small size instances of the problem, CMSA-MTC almost always finds the optimal solutions. For the large size instances, CMSA-MTC finds solutions better than that of CPLEX within the same running time and two additional greedy algorithms.

Abstract:
Multilabel classification (MLC) deals with instances associated with multiple labels simultaneously and often includes high dimensional data with noisy, irrelevant, and redundant features. Feature selection for MLC is crucial for achieving successful classification performance. However, no unified metric exists for evaluating learning performance in MLC tasks. Instead, multiple metrics exist, each assessing a different aspect of the classification process, and these metrics are often inconsistent with one another. Consequently, multilabel feature selection (MLFS) becomes a many-objective optimization problem (MaOP) when optimizing three or more classification metrics and the number of selected features simultaneously. Evolutionary computation (EC) techniques have shown great promise in addressing many-objective tasks due to their ability to effectively explore large and complex search spaces. EC techniques can handle multiple objectives concurrently, making them well-suited for the challenges posed by MLFS. Despite this potential, research on EC-based MLFS methods remains limited, with few studies treating it as an MaOP. To address this gap, this article proposes a new many-objective evolutionary algorithm within a multiform framework. The proposed algorithm leverages distinct subpopulations to address specific MLFS tasks, incorporates a strategy to exchange information between MLFS tasks, employs a local density-based selection mechanism to maintain diverse high-quality solutions, and uses an adaptive parameter scheme inspired by stochastic gradient descent to guide the search toward new regions in the objective space. Experimental results demonstrate the superiority of the proposed algorithm across a diverse range of high-dimensional datasets, outperforming both recently introduced many-objective and conventional MLFS algorithms.

Abstract:
Searching for symbolic models plays an important role in a wide range of domains, such as neural architecture search and automatic program synthesis. Genetic programming is a promising stochastic method for searching effective symbolic models within an acceptable time. The genetic programming (GP) performance is closely related to the hardness of the fitness landscape (FL). A better FL with less local optima normally implies that it is easier to search for better solutions. In recent years, there have been many studies enhancing GP performance by forming better FLs. However, the better design of the FL highly relies on specific domain knowledge and consumes a lot of expert effort. This article proposes a FL optimization method to automatically design better FLs for GP search than the manually designed ones. We optimize the landscapes by optimizing the neighborhood structures of symbolic solutions. We verify the effectiveness of the proposed method in both supervised learning and combinatorial optimization problems. The results show that the proposed method significantly reduces the hardness of FLs. By simply searching against the automatically optimized FLs, a GP method can have a very competitive performance with state-of-the-art methods.

Abstract:
In multiobjective feature selection, different feature subsets with the same number of selected features can achieve identical classification accuracy, meaning that it is a multimodal optimization problem. To effectively search for multimodal feature subsets within the vast search spaces of high-dimensional datasets, it is crucial to adopt reasonable encoding and search methods. Generally, applying a uniform evolutionary operator based on a single encoding method across the entire feature space is inefficient and prone to falling into local optima. To address the above issues, this article proposes a multimodal multiobjective feature selection method based on a joint encoding mechanism that combines discrete encoding and continuous encoding. It provides new perspectives to solve the high-dimensional feature selection problem from encoding methods to search operators. First, the search space is divided into a discrete encoding region and a continuous encoding region based on the knee points of feature importance ranking curve. A tailored initialization strategy is used to obtain the initial population for joint encoding. Second, an adaptive niche strategy based on three priorities is proposed, which ensures the similarity of individuals within a niche and the difference between niches. In addition, different search operators are cooperated with the two encoding strategies, respectively, to achieve effective and efficient search. The experimental results on 24 datasets show that the proposed algorithm achieves a better-classification performance than the state-of-the-art feature selection methods.

Abstract:
To solve dynamic multiobjective optimization problems (DMOPs), the optimization algorithms are required to track the movement of the Pareto set after the environmental changes effectively. Many prediction-based dynamic multiobjective evolutionary algorithms (DMOEAs) have been proposed to address this challenge by utilizing environmental information for population reinitialization. However, when environmental changes are complex, irregular, and severe, the solutions and information during the evolution process often contain noise, making it difficult for prediction-based DMOEAs to accurately predict and reinitialize the population. To address this issue, we propose a novel dynamic multiobjective evolutionary algorithm (DM-DMOEA) which uses a diffusion model-based prediction strategy. In DM-DMOEA, to improve the prediction accuracy, the diffusion model is introduced to extract the relationships of high-quality solutions and reinitialize the population, and a PS estimation method is employed to integrate both historical and new environmental information, providing a set of high-quality solutions for diffusion model training. To speed up the response time, a variational autoencoder (VAE) is used to map the decision space to a latent space, which can reduce the diffusion model size and accelerate the diffusion process. To evaluate the effectiveness of the proposed DM-DMOEA on DMOPs, comprehensive experiments are conducted on several benchmarks and a practical problem. The results show that the DM-DMOEA outperforms other four state-of-the-art DMOEAs in most cases.

Affiliations: School of Artificial Intelligence, Anhui University of Science and Technology, Hefei, China; State Key Laboratory of Intelligent Coal Mining and Strata Control, Beijing, China; School of Computer Science, Wuhan University, Wuhan, China; School of Information Science and Technology, Qingdao University of Science and Technology, Qingdao, China; School of Safety Science and Engineering, Anhui University of Science and Technology, Huainan, China

Abstract:
Dynamic constrained multiobjective optimization problems (DCMOPs) require algorithms to quickly track the feasible Pareto optima under dynamic environments. The existing dynamic constrained multiobjective evolutionary algorithms (DCMOEAs) normally focus on the convergence speed, but cannot well guarantee distribution. To address this issue, a subspace sparsity-driven knowledge transfer strategy-based DCMOEA is developed in this article, called SSDKT. First, reference points are introduced to partition objective space into multiple subspaces. Subsequently, the feasibility of each subspace is determined by the distribution of all historical feasible optimal solutions in it, and defined as the sparsity of subspace. A predictor based on the gated recurrent unit (GRU) network is further constructed to estimate the sparsity under the future environment. Once a new environment appears, a subspace transfer strategy is designed to generate an initial population. In each feasible subspace, the GRU-based prediction method is developed and competed with Kalman filter to generate the initial solution under the new environment. Based on the predicted solution of the nearest feasible neighbor, a potential initial individual in each infeasible subspace is produced by transferring the corresponding knowledge. The experimental results on various benchmarks verify that, compared with several state-of-the-art DCMOEAs, the proposed algorithm achieves the most competitive performance in solving DCMOPs.

Abstract:
A widely accepted way to assess the performance of iterative black-box optimizers is to analyze their empirical cumulative distribution function (ECDF) of predefined quality targets achieved not later than a given runtime. In this work, we consider an alternative approach, based on the empirical attainment function (EAF) and we show that the target-based ECDF is an approximation of the EAF. We argue that the EAF has several advantages over the target-based ECDF. In particular, it does not require defining a priori quality targets per function, captures performance differences more precisely, and enables the use of additional summary statistics that enrich the analysis. We also show that the average area over the convergence curves is a simpler-to-calculate, but equivalent, measure of anytime performance. To facilitate the accessibility of the EAF, we integrate a module to compute it into the IOHanalyzer platform. Finally, we illustrate the use of the EAF via synthetic examples and via the data available for the black-box optimization benchmark suite.

Abstract:
This article derives a population sizing model for standard evolution strategies (ES) in highly multimodal fitness landscapes with exponentially many local optima. The Rastrigin, Bohachevsky, and Ackley test functions are considered. Due to the highly nonconvex structure of these functions a detailed analytical description of the behavior of the ES is a challenge. Therefore, a model is derived that simplifies the complex structure of the functions under consideration. The main idea of this model is the interpretation of local landscape oscillations as frozen noise. This allows for an estimation of the success probability of the ES converging to the global optimum and in turn an estimation of the population size required. It is shown that the population size scales usually sublinearly with the search space dimension N. For the Rastrigin and Bohachevsky function, the population size scales with \mathcal O(\sqrt N \ln (N)) . As for Ackley, the scaling behavior depends strongly on the initial values. If the algorithm starts in a certain vicinity of the global optimizer, the dependence on the dimension N is rather weak. However, if the initial value exceeds a certain distance R to the optimizer, the population size scales exponentially with R.

Abstract:
Many search strategies have been designed to generate a promising offspring population for efficiently solving large-scale multiobjective optimization problems (LSMOPs). The effectiveness of existing search strategies relies on the quality of good parent solutions. However, especially in early generations, the current population does not always include high-quality solutions. This article proposes a generative adversarial network (GAN)-guided search (G2S) strategy for learning to evolve with guiding solutions. Its main idea is to employ GAN for mapping a set of guiding points in the objective space with good convergence and diversity back to the decision space to guide evolution. Specifically, the current population is used as real data, and the guiding points consisting of nondominated solutions and reference vectors are used as virtual data. The trained GAN generates guiding solutions in the decision space to guide the population to evolve efficiently. A large-scale multiobjective evolutionary framework using G2S is also proposed which can be embedded into multiobjective evolutionary algorithms (MOEAs) to improve their ability to handle LSMOPs. Experimental studies on several benchmark problems with the highest-5000-D decision space show that the proposed G2S is competitive compared with the state-of-the-art algorithms and has impressive efficiency as the component to improve the performance of MOEAs for solving LSMOPs.

Abstract:
In their recent work, Doerr and Krejca (IEEE Transactions on Evolutionary Computation, 2023) proved upper bounds on the expected runtime of the randomized local search (RLS) heuristic on generalized Needle functions. Based on these upper bounds, they deduce in a not fully rigorous manner a drastic influence of the needle radius k on the runtime. In this short article, we add the missing lower bound necessary to determine the influence of parameter k on the runtime. To this aim, we derive an exact description of the expected runtime, which also significantly improves the upper bound given by Doerr and Krejca. We also describe asymptotic estimates of the expected runtime.

Abstract:
In multiobjective optimization, the R2 indicator is widely used for designing the indicator-based algorithms, and the Tchebycheff approach is commonly employed in the decomposition-based algorithms. Despite their wide use, the connection between these two different paradigms is still not well understood, particularly in the field of multiobjective efficient global optimization (MOEGO). Considering that expected improvement (EI) is a cornerstone in efficient global optimization (EGO), this article first studies the relationship between R2-based EI and Tchebycheff-based EI. Then, we introduce a many-to-few (M2F) decomposition framework, offering a new perspective for linking the R2-based method and the Tchebycheff decomposition approach. By incorporating M2F decomposition into MOEGO, a new algorithm called R2/D-EGO is proposed. At each iteration, R2/D-EGO utilizes the Tchebycheff decomposition paradigm to generate a set of candidate solutions, each one corresponding to a different weight vector. Subsequently, a subset of query points is selected from the candidates based on the lower bound of R2-based EI. Empirical results indicate that the proposed R2/D-EGO is highly competitive in comparison with both the R2-based and decomposition-based MOEGO algorithms in the parallel (or batch) setting.

Abstract:
Although knowledge transfer methods are developed for many-task optimization problems, they tend to utilize solutions from a single task for knowledge transfer. Indeed, there are usually multiple relevant source tasks with commonality. Multisource data fusion can capture complementary knowledge of distinct source tasks to better assist the optimization of target tasks. However, biases potentially flow with the interaction between tasks during multisource fusion, resulting in performance degeneration. Thus, how to select multiple relevant source tasks and perform multisource knowledge transfer is challenging. To address these issues, this article proposes a multisource knowledge fusion (MKF) method based on graph attention networks. In MKF, tasks are structured using a relational graph, in which each vertex represents a task and each directed edge from vertex u to v represents that u is a source task of v. Particularly, for each task, multiple source tasks are selected based on the distribution similarity and evolutionary performance. In the graph, local message is passed from source tasks to target tasks using graph attention networks, which automatically learn the adjacency weight of each directed edge and aggregate solutions from multiple source tasks to obtain fused representations for target tasks. These fused representations are adopted to generate new solutions through mutation. In this way, multisource knowledge is fused and transferred according to their importance to the target task. Integrating MKF into differential evolution, a new algorithm named MKF-DE is put forward. Experimental results on GECCO2020MaTOP and CEC2022MaTOP show that MKF-DE outperforms state-of-the-art algorithms on most instances.

Affiliations: School of Computing, Queen’s University, Kingston, ON, Canada; School of Computing Science, Newcastle University, Newcastle upon Tyne, U.K.; Department of Computing Science and Mathematics, University of Stirling, Stirling, U.K.; Dipartimento di Ingegneria e Architettura, University of Parma, Parma, Italy; National Subsea Centre, Robert Gordon University, Aberdeen, U.K.; Department of Information Engineering and Computer Science, Universita degli Studi di Trento, Trento, Italy; IDEAS Research Institute, Robert Gordon University, Aberdeen, U.K.; Leiden Institute of Advanced Computer Science, Universiteit Leiden, Leiden, The Netherlands; Department of Computer Science, University of Exeter, Exeter, U.K.

Abstract:
Artificial intelligence methods are being increasingly applied across various domains, but their often opaque nature has raised concerns about accountability and trust. In response, the field of explainable AI (XAI) has emerged to address the need for human-understandable AI systems. Evolutionary computation (EC), a family of powerful optimization and learning algorithms, offers significant potential to contribute to XAI, and vice versa. This article provides an introduction to XAI and reviews current techniques for explaining machine learning (ML) models. We then explore how EC can be leveraged in XAI and examine existing XAI approaches that incorporate EC techniques. Furthermore, we discuss the application of XAI principles within EC itself, investigating how these principles can illuminate the behavior and outcomes of EC algorithms, their (automatic) configuration, and the underlying problem landscapes they optimize. Finally, we discuss open challenges in XAI and highlight opportunities for future research at the intersection of XAI and EC. Our goal is to demonstrate EC’s suitability for addressing current explainability challenges and to encourage further exploration of these methods, ultimately contributing to the development of more understandable and trustworthy ML models and EC algorithms.

Abstract:
Spiking neural networks (SNNs) have been widely applied not only for their advantages in energy efficiency with discrete signal processing but also for their natural suitability to integrate multiscale biological plasticity. However, most SNNs still adopt the structure of the well-established deep neural networks (DNNs), with few attempts at implementing automatic neural architecture search (NAS) for SNNs. The neural motifs topology, modular regional structures, and global cross-brain region connections in the human brain are the product of natural evolution, serving as a perfect reference for designing brain-inspired SNN architecture. Here, we propose an efficient multiscale evolutionary NAS (MSE-NAS) for SNN, simultaneously considering micro-, meso-, and macro-scale brain topologies as the evolutionary search space and is supplemented with customized brain-inspired indirect evaluation (BIE) function, encoding scheme and genetic operations. This is the first instance that the evolutionary characteristics of microconnections and electrophysiological patterns have been incorporated into one single evolutionary framework. The proposal of MSE-NAS proves that the evolutionary structure and mechanism of the human brain can essentially help better handle artificial intelligence tasks, revealing the important value and key role of integrating evolutionary computation (EC) principles in optimizing biologically realistic neural models. Extensive experiments demonstrate that MSE-NAS achieves superior performance with shorter simulation steps on static datasets (CIFAR10 and CIFAR100) and neuromorphic datasets (CIFAR10-DVS and DVS128-Gesture). More importantly, the emergence of general capabilities, such as transferability and robustness brought about by evolution confirms the innovative progress and important value of EC in the field of brain-inspired intelligence.

Abstract:
The self-adaptive, multirecombinative (\mu /\mu _I,\lambda) -Evolution strategy (ES) is investigated on the highly multimodal Rastrigin test function by theoretical and experimental means. The analysis is based on the established dynamical systems approach. To this end, the self-adaptation response (SAR) function is derived in the limit of large populations, which are necessary to achieve high success rates. Furthermore, steady-state conditions on Rastrigin are discussed and compared to the sphere function. Then, a relation for the learning parameter \tau is derived to tune the sampling process of the self-adaptive ES, improving its efficiency on Rastrigin. The obtained result is compared to default \tau -values. Furthermore, expected runtime experiments are conducted varying \tau and population parameters of the ES. Theoretical and experimental results regarding \tau are compared in terms of efficiency and robustness showing good agreement.

Abstract:
Feature selection (FS) is a very important technique for hyperspectral image (HSI) classification, as successfully selecting informative features can significantly increase the learning performance while reducing the computational cost. However, most of the existing FS methods tend to treat the HSI as a whole for FS, which does not fully consider the unique characteristics of HSIs and disregards the fact that different feature classes possess varying preferences for features. Thus, this article proposes a superpixel segmentation-based evolutionary multitasking (EMT) algorithm for FS of HSIs, called SS-EMT. First, the superpixel segmentation method is used to partition the original HSI into several superpixel blocks, which can preserve well the information of different classes of the original image. Second, in order to explore each superpixel block efficiently, an EMT algorithm using particle swarm optimization is designed, which treats each superpixel block as a subtask and then optimizes these subtasks collaboratively by transferring useful knowledge among related subtasks. In addition, a new individual evaluation mechanism is devised to obtain multiple high-quality feature subsets with different numbers of features simultaneously in a single run, thus reducing the computational cost. Finally, extensive experimental results on four common HSI datasets under three classifiers validate that our proposed method outperforms several state-of-the-art FS methods.

Abstract:
black-box global optimization aims at minimizing an objective function whose analytical form is not known. To do so, many state-of-the-art methods rely on sampling-based strategies, where sampling distributions are built in an iterative fashion, so that their mass concentrate where the objective function is low. Despite empirical success, the theoretical study of these methods remains difficult. In this work, we introduce a new framework, based on divergence-decrease conditions, to study and design black-box global optimization algorithms. Our approach allows to establish and quantify the improvement of sampling distributions at each iteration, in terms of expected value or quantile of the objective. We show that the information-geometric optimization approach fits within our framework, yielding a new approach for its analysis. We also establish sampling distribution improvement results for two novel algorithms, one related with the cross-entropy approach with mixture models, and another one using heavy-tailed sampling distributions.

Abstract:
Plenty of decision variable grouping-based algorithms have shown satisfactory performance in solving high-dimensional optimization problems. However, most of them are tailored for inexpensive optimization problems. Extending variable grouping method to expensive optimization problems poses many challenges. One of the greatest challenges is that most grouping approaches require additional function evaluations (FEs) to discover interactions among decision variables, which is intolerable for expensive optimization problems as it incurs prohibitive computational costs. To address this issue, an adaptive variable grouping method is proposed in this article, which can achieve relatively accurate grouping results without additional FE consumption. Specifically, variables are grouped based on the contrasts between well-converged solutions and poorly converged solutions. Furthermore, the grouping scheme is adjusted dynamically during the optimization process to improve the grouping accuracy. Besides, an adaptive environmental selection-based sampling strategy is suggested, which attempts to provide the currently required solutions for reevaluation according to the demands of different optimization stages. The proposed algorithm is compared with the other five state-of-the-art multiobjective optimization evolutionary algorithms on both benchmark and real-world problems. The experimental results demonstrate the promising performance and the superior computational efficiency of the proposed algorithm in tackling high-dimensional expensive multiobjective optimization problems.

Abstract:
Biological markers (i.e., biomarkers) are the key to predicting disease states and revealing the molecular mechanisms in precision medicine of complex diseases (e.g., cancer). With the advancement of high-throughput sequencing technology, there has been a significant increase in the volume and diversity of known disease omics data, where many methods have been developed to identify potential disease biomarkers (DBs) for mining the complex dynamics. As emerging artificial intelligence techniques, evolutionary computation (EC) has found extensive application in the identification of DBs, making significant achievements in mining disease omics data. However, there is currently no survey or analysis available of the existing EC methods to identify DBs on the disease omics data, resulting in missed opportunities to enhance performance and achieve successful applications in precision medicine. This article aims to present a comprehensive overview of the latest EC methods for mining the dynamics of DBs, including the summary of biomolecular omics datasets, the classification of the EC methods for DB discovery, and performance comparisons of the typical EC methods. Additionally, this article discusses challenges and potential future directions of the EC methods in the identification of DBs, providing directions and prospects for future research.

Affiliations: National Frontiers Science Center for Industrial Intelligence and Systems Optimization, Key Laboratory of Data Analytics and Optimization for Smart Industry, Ministry of Education, Northeastern University, Shenyang, China; Liaoning Engineering Laboratory of Data Analytics and Optimization for Smart Industry and the Liaoning Key Laboratory of Manufacturing System and Logistics Optimization, Northeastern University, Shenyang, China; National Frontiers Science Center for Industrial Intelligence and Systems Optimization, Northeastern University, Shenyang, China; Department of Computing and Decision Sciences, Lingnan University, Hong Kong, China

Abstract:
When solving dynamic multiobjective optimization problems, most evolutionary algorithms (EAs) attempt to predict the initial population in a new environment by mining the relationships between solutions during historical environment changes. However, the complex relationships between solutions and the limited amount of available data often make it difficult to extract useful information efficiently, which may deteriorate the prediction accuracy. To address this problem, this article proposes a spatial–temporal topological tensor-based prediction method to generate the initial population in a new environment under the decomposition framework of MOEA/D. The method relies on the idea that the population distribution in each environment has topological similarity along the time dimension in the objective space, which makes it efficient to represent the population distribution in terms of a tensor and predict new solutions along each decomposition axis in a new environment by an improved tensor-based multishort time series prediction method. Experimental results on various benchmark problems and a real-world problem show that the proposed method is competitive or even superior to state-of-the-art dynamic multiobjective EAs based on prediction strategies.

Abstract:
Task similarity is a major requisite to trigger knowledge sharing in evolutionary multitasking optimization (EMTO). Unfortunately, most of the existing EMTO algorithms only focus on the similarity between population distributions of tasks, but ignore the search behavior of populations, which may degrade the performance of cross-task knowledge sharing. Motivated by this, an improved EMTO algorithm with similarity evaluation of search behavior (SESB-IEMTO), employing the particle swarm optimization (PSO) algorithm as a task solver for each task, is proposed. It comprises three key elements: 1) a dynamic similarity-based evaluation strategy; 2) a cross-task knowledge adaptation method; and 3) a search direction-sharing mechanism. Primarily, the source tasks with similar search behavior are discriminated with the dynamic similarity-based evaluation strategy, where individuals can be fully exploited for cross-task evolution. Then, the knowledge derived from these source tasks is regulated by the cross-task knowledge adaption method for alleviating the risk of negative transfer caused by the heterogeneity between tasks. Moreover, to further promote knowledge sharing between tasks, the search direction-sharing mechanism is developed to navigate tasks efficiently searching for promising regions. Finally, the convergence of SESB-IEMTO is analyzed, and the effectiveness and superiority are also verified with the experiments on several benchmark tests and a real-world application study.

Abstract:
Large language models (LLMs), such as GPT-4 have demonstrated their ability to understand natural language and generate complex code snippets. This article introduces a novel LLM evolutionary algorithm (LLaMEA) framework, leveraging GPT models for the automated generation and refinement of algorithms. Given a set of criteria and a task definition (the search space), LLaMEA iteratively generates, mutates, and selects algorithms based on performance metrics and feedback from runtime evaluations. This framework offers a unique approach to generating optimized algorithms without requiring extensive prior expertise. We show how this framework can be used to generate novel closed box metaheuristic optimization algorithms for box-constrained, continuous optimization problems automatically. LLaMEA generates multiple algorithms that outperform state-of-the-art optimization algorithms (covariance matrix adaptation evolution strategy and differential evolution) on the 5-D closed box optimization benchmark (BBOB). The algorithms also show competitive performance on the 10- and 20-D instances of the test functions, although they have not seen such instances during the automated generation process. The results demonstrate the feasibility of the framework and identify future directions for automated generation and optimization of algorithms via LLMs.

Abstract:
Many real-world problems are inherently stochastic, complicating, or even precluding the use of analytical methods. These problems are often characterized by high dimensionality, large solution spaces, and numerous local optima, which make finding optimal solutions challenging. Therefore, simulation optimization is frequently employed. This article specifically focuses on the discrete case, also known as discrete optimization via simulation. Despite their adaptions for stochastic problems, previous evolutionary algorithms face a major limitation in these problems. They discard all information about solutions that are not involved in the most recent population. However, this is ineffective, as each simulation observation gathered over the course of iterations provides valuable information that should guide the selection of subsequent solutions. Inspired by the domain of reinforcement learning (RL), we propose a novel memory concept for evolutionary algorithms that ensures global convergence and significantly improves their finite time performance. Unlike previous evolutionary algorithms, our approach permanently preserves simulation observations to progressively improve the accuracy of sample means when revisiting solutions in later iterations. Moreover, the selection of new solutions is based on the entire memory rather than just the last population. The numerical experiments demonstrate that this novel approach, which combines a genetic algorithm (GA) with such memory, consistently outperforms popular convergent state-of-the-art benchmark algorithms in a large variety of established test problems while requiring considerably less computational effort. This marks the so-called genetic multi-armed bandit (MAB) as one of the currently most powerful algorithms for solving stochastic problems.

Abstract:
Domain adaptation reuses the knowledge learned from an existing (source) domain to classify unlabeled data from another related (target) domain. However, the two domains have different data distributions. Common approaches to bridge the two distributions are selecting/reweighting instances, building domain-invariant feature subspaces, or directly building adaptive classifiers. Recent domain adaptation work has shown that combining the above first two approaches before applying the third approach achieves better performance than performing each approach individually. However, most existing instance selection approaches are based on a ranking mechanism, ignore interdependences between instances, and require a predefined number of selected instances. Furthermore, adaptive classifiers are sensitive to their parameters which are challenging to optimize due to the lack of target labeled instances. This article introduces a novel evolutionary instance selection approach for domain adaptation. We propose a compacted representation and an efficient fitness function for particle swarm optimization to automatically determine the number of selected instances while considering the interdependencies among instances. This article also proposes to use multiple partial classifiers to build a more reliable and robust adaptive classifier. The results show that evolutionary instance selection selects better instances than the ranking approach. In cooperation with multiple partial classifiers, the proposed algorithm achieves better performance than nine state-of-the-art and well-known domain adaptation approaches.

Abstract:
Truck-drone delivery systems have been proposed for sustainable and economical last-mile distribution, especially in urban environments. To widen the service range, some works have recommended adding facilities, such as drone stations, considering the problem in discrete space by choosing from a predefined set. In this article, an evolutionary optimization approach to the design decision of where to locate drone stations in the continuous plane is introduced, modeled, and solved. Drone stations serve as facilities for storage, charging, and launching. A truck (or other land transport means) transports parcels to the drone stations from a depot and the drones launch from the stations and deliver the parcels to each customer. The objective is to determine the positions of the drone stations in 2-D space and establish the shortest fixed truck route from the depot through all the stations and returning to the depot. The problem is constrained by the radius of service for each drone and all customers must be served, if possible. We formulate the problem as a constrained nonlinear optimization problem and present two versions of an algorithm using particle swarm optimization (PSO) with a subordinate dynamic program. Computational results show that our approach achieves much better results than a standard commercial nonlinear solver in a similar amount of computational time for both maximizing coverage of customers and minimizing distance of the truck delivery route. A design case study concerning healthcare delivery throughout the Birmingham, Alabama (USA) metropolitan area is provided.

Abstract:
With the rise of globalization and environmental concerns, distributed scheduling and energy-efficient scheduling have become crucial topics in the informational manufacturing system. Additionally, the growing consideration about realistic constraints, such as transportation time and finite transportation resources, has made the scheduling problem increasingly complex. Facing these challenges, special mechanisms are required to improve the efficiency of solving algorithms. In this article, a bi-learning evolutionary algorithm (BLEA) is proposed to solve the distributed energy-efficient flexible job shop problem with transportation constraints (DEFJSP-T). First, we integrate statistical learning (SL) and evolutionary learning (EL) in the framework, while decomposition and Pareto dominance methods are employed in different stages to handle conflicting objectives. During the SL stage, probability models are established to statistically search for advantageous substructures on each weight vector, and an update mechanism is devised to improve the exploration. In the EL stage, the genetic operators are introduced and an improved local search that takes into account the problem properties is proposed to realize sufficient exploitation. Finally, according to the performance of the SL, a novel switching mechanism between SL and EL is designed to ensure the rational allocation of computing resources. Extensive experiments are conducted to test the performances of the BLEA. The statistical comparison shows that the BLEA is superior in solving the DEFJSP-T in terms of efficiency and effectiveness.

Abstract:
Due to the curse of dimensionality, the search efficiency of existing operators in large-scale decision space deteriorates dramatically. The competitive swarm optimizer (CSO)-based framework has great potential in tackling large-scale single-objective optimization problems. However, the existing CSOs only focus on the loser to winner learning paradigm and neglect the significance of the winner determination mechanism for large-scale search, which makes the algorithm difficult to escape from local optima. To remedy this issue, a flexible ranking-based CSO has been tailored for handling large-scale multiobjective optimization problems (MOPs). Concretely, a novel winner determination strategy is introduced to broadly identify high-quality individuals in the population to enhance diversity maintenance. In addition, a special competitive mechanism is adopted to guide the search direction, which is capable of efficiently increasing search space utilization. The simulation results validate that the proposed algorithm can significantly enhance the exploration and exploitation ability of the conventional CSO, and outperforms several state-of-the-art large-scale multiobjective optimization algorithms on both large-scale benchmark MOPs and application examples.

Abstract:
Constrained multiobjective optimization has gained much interest in the past few years. However, constrained multiobjective optimization problems (CMOPs) are still unsatisfactorily understood. Consequently, the choice of adequate CMOPs for benchmarking is difficult and lacks a formal background. This article takes a step toward addressing this issue by exploring CMOPs from a performance space perspective. First, it presents a novel performance assessment approach designed explicitly for constrained multiobjective optimization. This methodology offers a first attempt at simultaneously measuring the performance in approximating the Pareto front and constraint satisfaction. Second, it proposes an approach to measure the capability of the given optimization problem to differentiate among algorithm performances. Finally, this approach is used to compare eight frequently used artificial test suites of CMOPs. The experimental results reveal which suites are more efficient in discerning between four well-known multiobjective optimization algorithms.

Affiliations: Information Materials and Intelligent Sensing Laboratory of Anhui Province, School of Computer Science and Technology, Anhui University, Hefei, China; Institutes of Physical Science and Information Technology, Anhui University, Hefei, China; School of Artificial Intelligence, Anhui University, Hefei, China; State Key Laboratory of Synthetical Automation for Process Industries, Northeastern University, Shenyang, China; School of Engineering, Westlake University, Hangzhou, China

Abstract:
Binary optimization assumes a pervasive significance in the context of practical applications, such as knapsack problems, maximum cut problems, and critical node detection problems. Existing techniques, including mathematical programming, heuristics, evolutionary computation, and neural networks have been employed to tackle the binary optimization problems (BOPs). However, they grapple with the challenge of optimizing a large number of binary variables. In this article, we propose a dimensionality reduction method to assist the evolutionary algorithms in solving large-scale BOPs, which is achieved based on the neural networks. The proposed method converts the optimization of a large number of binary variables into the optimization of a small number of network weights, resulting in a significant reduction in search space dimensionality. Crucially, the proposed method obviates the necessity for a training process, which eliminates the requirement for a priori knowledge and enhances the search efficiency. On six types of single- and multiobjective BOPs with up to 10000000 variables, the proposed method demonstrates superiority over the top-tier evolutionary algorithms and neural network-based methods.

Abstract:
Balancing objectives and constraints is challenging in addressing constrained multiobjective optimization problems (CMOPs). Existing methods may have limitations in handling various CMOPs due to the complex geometries of the Pareto front (PF). And the complexity arises from the constraints that narrow the feasible region. Categorizing problems based on their geometric characteristics facilitates facing this challenge. For this purpose, this article proposes a novel constrained multiobjective optimization framework with detection and supervision phases, called COEA-DAS. The framework categorizes the problems into four types based on the overlap between the obtained approximate unconstrained PF (UPF) and constrained PF (CPF) to guide the coevolution of the two populations. In the detection phase, the detection population approaches the UPF ignoring the constraints. The main population is guided by the detection population to cross infeasible barriers and approximate the CPF. In the supervision phase, specialized evolutionary mechanisms are designed for each possible problem type. The detection population maintains evolution to assist the main population in spreading along the CPF. Meanwhile, the supervision strategy is conducted to reevaluate the problem types based on the evolutionary state of the populations. This idea of balancing constraints and objectives based on the type of problem provides a novel approach for more effectively addressing the CMOPs. Experimental results indicate that the proposed algorithm performs better or more competitively on 57 benchmark problems and 12 real-world CMOPs compared with eight state-of-the-art algorithms.

Abstract:
Surrogate-assisted evolutionary algorithms (SAEAs) rely on the infill criterion to select candidate solutions for expensive evaluations. However, in the context of expensive constrained multiobjective optimization problems (ECMOPs) with complex feasible regions, guiding the optimization algorithm toward the constrained Pareto optimal front and achieving a balance between feasibility, convergence, diversity, exploration, and exploitation using a single infill criterion pose significant challenges. We propose an ensemble infill criterion-based multistage SAEA (EIC-MSSAEA) to tackle these challenges. Specifically, EIC-MSSAEA comprises three stages. In the first stage, we ignore constraints to facilitate the rapid traversal of infeasible obstacles. In the second stage, only one constraint is activated at a time to increase algorithm diversity. Finally, in the last stage, we activate all constraints to improve overall feasibility. In each stage, EIC-MSSAEA first employs NSGA-III as the underlying baseline solver to explore the search space, in which promising solutions are then selected by an ensemble infill criterion that incorporates multiple base-infill criteria to measure the feasibility, convergence, diversity, and uncertainty of candidate solutions. Experimental results demonstrate the competitiveness of EIC-MSSAEA against state-of-the-art SAEAs for ECMOPs.

Abstract:
The search for multiple optimal solutions in the traveling salesman problem (TSP), as a challenging multimodal optimization problem in the combinatorial domain, has received increasing attention in recent years. Nevertheless, the multisolution TSP (MSTSP) still remains extremely difficult for larger-scale TSP instances. In this article, we propose a niching Lin-Kernighan–Helsgaun (LKH)-based ant colony system (ACS), named nLKH-ACS, taking advantage of LKH’s ability to solve large-scale TSPs, ACS’s search efficiency, and the niching technique for diversity preservation. Specifically, first, to address multisolution problems, we design a niching LKH (nLKH) strategy to generate diverse cost-efficient spanning trees, and adopt the \alpha -nearness on each tree to obtain a diverse candidate edge set. The nLKH strategy enhances the ACS by improving pheromone initialization, solution construction, and local search operation using spanning trees and candidate edge sets, thereby strengthening the search capability and diversity. Then, to balance convergence and diversity, an adaptive Gaussian strategy is utilized to update the pheromone matrix. Furthermore, we design an indicator to measure the geometric diversity between pairs of solutions in the MSTSP solution set. The comprehensive experiments on MSTSPs and TSPLIB are conducted to validate the performance of the proposed nLKH-ACS. The experimental results demonstrate the powerful solving capability and excellent diversity of the proposed nLKH-ACS, particularly in finding various optimal solutions in larger-scale TSP instances.

Abstract:
Many real-world applications often generate unbalanced data. Learning from such data may lead to biased classifiers that perform poorly on the class of interest. Oversampling methods have been shown to be effective in rebalancing unbalanced data to help classifiers avoid performance bias. However, many existing oversampling methods rely on a predesigned linear model structure and the neighborhood information of an original instance. This may lead to the generation of noisy instances when the original data has noise. In this study, we develop a novel oversampling method in which genetic programming is introduced to automatically select good-quality instances and evolve a model structure that combines the selected instances to create a new instance. In the proposed oversampling method, an individual is used to represent a generated instance, which is evaluated by the fitness function designed based on the Euclidean distance and the cosine theorem. In the experiments, we examine the effectiveness of the proposed oversampling method in assisting different types of classifiers to solve the issue of class imbalance, and compare it with popular sampling methods in unbalanced classification. The results have been analyzed comprehensively, indicating that the new method successfully addressed the class imbalance issue by generating a group of good-quality instances for the minority class and outperformed the compared sampling methods in almost all cases.

Abstract:
Dynamic air traffic flow management (DATFM) aims at flexibly balancing air traffic demand with limited airspace by scheduling aircraft, particularly during unforeseen events, to maintain efficiency in aviation operations. Genetic programming (GP) has shown success in evolving effective heuristics across various domains. However, directly adopting GP to DATFM may be less effective due to the computationally intense simulations required for large-scale aircraft decision-making over broad airspace. To address the issue, we develop a novel multifidelity surrogate-assisted GP. The core idea is that if a computationally efficient low-fidelity surrogate provides enough information to guide the population toward promising areas effectively, then employing more accurate but resource-intensive evaluations would only increase computational effort without enhancing the direction of evolution. A key innovation in our method is a surrogate management strategy that automatically determines when and which surrogate model to use, based on collective information from the evolving population. This approach allows for more effective management of computational resources during the evolutionary process, enabling exploration of a broader range of the heuristic space and increasing the likelihood of identifying promising solutions. The proposed method has been tested on various benchmark instances derived from actual air traffic data. Extensive experimental results demonstrate that the proposed algorithm significantly outperforms current state-of-the-art methods in both effectiveness and efficiency.

Abstract:
Traveling salesman problem (TSP) is a combinatorial optimization problem, serving as basis for many real-world applications (e.g., transportation planning, circuit board design, and DNA sequencing). In TSP, it is common to encounter some dynamic events, for example, traffic jam, and roadworks in transportation planning. To deal with such dynamic TSP (DTSP) scenarios, numerous techniques have been designed over decades. In this article, we take a different perspective to study DTSP. Instead of focusing only on algorithm design for DTSP, we investigate how dynamic events in DTSP affect its fitness landscape (e.g., the location of local optimal solutions and the ruggedness level of search space). We consider three dynamic events, including node addition, node deletion and weight changes, and analyze how they affect the TSP with respect to the overall landscape structure and solution optimality. Experimental results show that the weight change event has great effect on the problem’s fitness landscape, introducing more local optima and reducing the basin of attraction for the global optimum. This may suggest that search algorithms need to have stronger exploration capability when handling weight change dynamic events. Furthermore, our experimental studies also demonstrate that the dynamic solution adaptation strategy on the original global optimum is effective for tracking the new optimum after dynamic changes.

Abstract:
In dynamic multiobjective optimization problems (DMOPs) where the number of objectives (NObj) changes, the Pareto-optimal set (PS) manifold may expand or contract over time. Knowledge transfer has been utilized to solve DMOPs because it can transfer valuable information from one problem-solving instance (i.e., source) to solving another related problem instance. However, existing transfer approaches suffer from poor diversity and convergence after a severe increase and decrease in the NObjs, respectively. The reason is that most transfer approaches simply transfer knowledge from the solutions before the change, which causes degeneration in quality of transferred solutions due to dissimilarity between the problem instances before and after the severe change. In this article, we propose a simple-yet-effective transfer approach, called similarity transfer approach (STA) to tackling a severely changing NObjs. It selects the historically most similar environment to the current one as the source problem instance and transfers knowledge from that environment. Furthermore, a novel strategy of randomization enhancing transfer diversity is proposed in STA if the transfer from the most similar environment still lacks sufficient diversity when increasing the NObjs. Comprehensive studies using 13 DMOP benchmarks with a severely changing NObjs demonstrate that our proposed STA is effective in improving solution quality not only immediately after changes but also after optimization, in comparison to state-of-the-art algorithms.

Abstract:
Recently, transfer-learning-based dynamic multiobjective optimization algorithms (TL-DMOAs) have been shown to be very promising in solving dynamic multiobjective optimization problems (DMOPs). However, it is difficult for them to model knowledge capable of delineating the Pareto optimal solutions (POSs) found in each historical environment, because the POSs’ distribution cannot be adequately reflected. Besides, existing TL-DMOAs normally focus on acquiring knowledge from historical environments, but neglect correlations behind them for excavating potential knowledge, restricting the performance in generating high-quality initial populations (HIPs). To address these issues, herein a DMOA with multisource and hidden source-based knowledge transfer (DMOA-MHKT) is proposed. First, we design a knowledge extraction strategy by introducing mean shift, a nonparametric clustering method, to cluster the historical POSs. As clusters’ representatives, the cluster centers are considered to represent environmental knowledge, because they can adequately reflect the POSs’ distribution. Second, the most similar historical environment through environmental match and the last one are selected as two explicit sources. In the former source the POSs’ cluster centers are treated as its knowledge. By contrast, based on the POSs’ cluster centers and knee points in the latter source, a scoring method is designed to generate environmental knowledge by depicting the dynamics between two continuous environments. Third, after aligning knowledge of the explicit sources, a hidden source is learned by excavating correlations and potential knowledge behind them, facilitating the generalization enhancement in generating HIPs. The experimental results especially performance comparisons with seven state-of-the-art DMOAs demonstrate that DMOA-MHKT brings significant improvements in solving DMOPs.

Abstract:
Evolutionary reinforcement learning (ERL), which integrates the evolutionary algorithms (EAs) and reinforcement learning (RL) for optimization, has demonstrated remarkable performance advancements. By fusing both the approaches, ERL has emerged as a promising research direction. This survey offers a comprehensive overview of the diverse research branches in ERL. Specifically, we systematically summarize the recent advancements in related algorithms and identify three primary research directions: 1) EA-assisted optimization of RL; 2) RL-assisted optimization of EA; and 3) synergistic optimization of EA and RL. Following that, we conduct an in-depth analysis of each research direction, organizing multiple research branches. We elucidate the problems that each branch aims to tackle and how the integration of EAs and RL addresses these challenges. In conclusion, we discuss potential challenges and prospective future research directions across various research directions. To facilitate researchers in delving into ERL, we organize the algorithms and codes involved on https://github.com/yeshenpy/Awesome-Evolutionary-Reinforcement-Learning.

Abstract:
Feature selection can be treated as a bi-objective optimization problem, if aimed at minimizing both classification error and number of selected features, suitable for multiobjective evolutionary algorithms (MOEAs) to solve. However, traditional MOEAs would encounter setbacks when the number of features explodes to high dimensionality, causing difficulties for searching optimal solutions in large-scale decision space. In this article, we propose two general methods applicable to integrate with the existing MOEA frameworks in addressing bi-objective feature selection, especially for the high-dimensional datasets. One based on probe populations for improving initialization is called probe population-based initialization (PPI), and the other based on genetic pools for improving reproduction is called genetic pool-based reproduction (GPR), both aimed at boosting the search ability of MOEAs. Tested on 20 datasets, in terms of four performance metrics (including the computational time), the experimental section can be divided into three parts. First, five state-of-the-art MOEAs are used as baseline algorithms to integrate with PPI and GPR, while the integrated versions are then compared with their own baselines. Second, the PPI method is additionally compared with the three representative feature selection initialization methods to further identify its advantages. Third, a complete PPI and GPR-based MOEA (termed PGMOEA) is proposed to compare with the three cutting-edge evolutionary feature selection algorithms to further position its search ability. In general, it is suggested from the empirical results that either PPI or GPR can significantly improve the overall performance of each integrated MOEA, while adopting both of them takes the most complementary effect.

Abstract:
In black-box optimization, noise in the objective function is often inevitable. Noise disrupts the ranking of candidate solutions in comparison-based optimization, possibly deteriorating the search performance compared with a noiseless scenario. Explicit averaging takes the sample average of noisy objective function values and is widely used as a simple and versatile noise-handling technique. Although it is suitable for various applications, it is ineffective if the mean is not finite. We theoretically reveal that explicit averaging has a negative effect on the estimation of ground-truth rankings when assuming stably distributed noise without a finite mean. Alternatively, sign averaging (SA) is proposed as a simple but robust noise-handling technique. We theoretically prove that SA estimates the order of the medians of the noisy objective function values for a pair of points with arbitrarily high probability as the number of samples increases. Its advantages over explicit averaging and its robustness are also confirmed through numerical experiments.

Abstract:
Subset selection is a fundamental problem across a wide range of applications. In this study, we explore scenarios where the variables within the original dataset are divided into distinct groups. Subsequently, we investigate an optimization problem that includes extra fairness constraints (i.e., partition matroid constraints), restricting the selection of a specified number of variables from each group, which is known as the fair subset selection (FSS) problem. First, for the case where the existing Pareto optimization algorithms do not have the ability to well handle the fairness constraints, due to they do not consider fairness constraints in the process of solutions generation. In this article, a Pareto Optimization algorithm named POFSS is proposed for FSS, by introducing a designed fairness balance flip operator. Also, we prove that POFSS has the approximation ability of \max \ [\alpha /l](1-e^-\gamma ), (\gamma /k), 1-e^-r\overline k/k \ in polynomial time when l \lt \log _2n and the probability of mutation is constant c/n~(c\lt 2) and this approximation ratio is no worse than the previous theoretical result ( \alpha , \gamma represent two submodular ratios, and l is the number of disjoint groups). In addition, we apply POFSS to one typical FSS task named personalized recommendation (PR), where an acceleration strategy is designed and the acceleration ratio is strictly proved. Finally, the experimental results on the PR task show the proposed POFSS outperforms the state-of-the-art methods in addressing the FSS.

Abstract:
Short-term wind power probabilistic forecasting can furnish decision-makers with comprehensive information to enhance management capabilities. Most wind power probabilistic predictions are modeled by multiple training of the pinball loss at a single quantile. However, this modeling leads to two underlying limitations, i.e., traditional probabilistic forecasting models fail to achieve a balance between the accuracy and width and are prone to quantile crossover. This article proposes a novel model called large-scale multiobjective evolutionary quantile estimation (LMOEQE) to obtain high-quality wind power probabilistic estimations. Specifically, for avoiding quantile crossover, a multiquantile regression monotone fuzzy neural network (MQRMFNN) is first proposed to simultaneously output monotonically increasing probability distributions. Then, a multiple loss function framework involving the accuracy, reliability and width is designed. Based on this framework, we regard the training of MQRMFNN as a large-scale multiobjective problem (MOP) to achieve the tradeoff on each metric of the probability distribution. But optimizing large-scale MOP for probabilistic neural network is extremely demanding in terms of efficiency and performance. A large-scale distributed multiobjective competitive swarm optimizer (LDMOCSO) is proposed for solving the constructed large-scale MOP. It implements a distributed competitive update strategy of different states to leverage global information from the decision space, effectively enhancing the convergence speed and diversity. All the methods show the superiority in real-world datasets.

Abstract:
Data-efficient image classification, which focuses on achieving accurate classification performance with limited labeled data, has garnered significant attention. Genetic programming (GP) has achieved impressive progress in image classification, particularly in scenarios involving small amounts of labeled data. GP research typically focuses on designing tree-based model representations to learn useful image features for classification. However, most GP methods are proposed for gray-scale images and ignore the color features. Furthermore, the existing GP methods typically learn features on a single scale/resolution, restricting potential accuracy enhancements. To address these issues, this article proposes a new multitree GP representation for image feature learning and classification. In each individual, three trees are included to extract discriminative features from the red, green, and blue channels of the image. With the new image resizing layer in the tree representation, the proposed approach can achieve multiscale feature extraction, i.e., flexibly learning fine-grained details and coarse-grained structures in the image, improving the classification performance. In addition, since a limitation of GP is premature convergence due to a decline in population diversity, this article develops a hybrid parent selection method consisting of tournament and lexicase selection to increase population diversity, find the best individual, and improve classification accuracy. The experiments on six image classification datasets indicate that the proposed approach outperforms state-of-the-art neural network-based and GP-based methods in almost all comparisons. Further analyses demonstrate the effectiveness of each component and the potentially high interpretability of the proposed approach.

Abstract:
The hardly dominated boundary (HDB) is commonly observed in multiobjective optimization problems (HDB-MOPs). However, there are only a few benchmark problems related to HDB-MOPs in the evolutionary computation community, which is insufficient to validate the performance of the multiobjective evolutionary algorithms (MOEAs). In this article, we first introduce a new set of HDB-MOPs characterized by various shapes of Pareto fronts and scalable HDB sizes. We then systematically analyze the capabilities of several representative existing MOEAs in handling HDB-MOPs and reveal their strengths and weaknesses in solving this type of problem. Finally, based on this insightful analysis, we propose an indicator-based MOEA with an adaptive reference point (denoted as IMOEA-ARP) to effectively address HDB-MOPs. The source codes of the proposed benchmark problems and the IMOEA-ARP algorithm are available from https://github.com/CIAM-Group/EvolutionaryAlgorithm_Codes/tree/main/IMOEA-ARP.

Abstract:
This article examines various methods of computing uncertainty and diversity for active learning in genetic programming. We found that the model population in genetic programming can be exploited to select informative training data points by using a model ensemble combined with an uncertainty metric. We explored several uncertainty metrics and found that differential entropy performed the best. We also compared two data diversity metrics and found that correlation as a diversity metric performs better than minimum Euclidean distance, although there are some drawbacks that prevent correlation from being used on all problems. Finally, we combined uncertainty and diversity using a Pareto optimization approach to allow both to be considered in a balanced way to guide the selection of informative and unique data points for training.

Affiliations: College of Information Science and Engineering, and the National Frontiers Science Center for Industrial Intelligence and Systems Optimization, Northeastern University, Shenyang, China; National Frontiers Science Center for Industrial Intelligence and Systems Optimization, and the Key Laboratory of Data Analytics and Optimization for Smart Industry, Ministry of Education, Northeastern University, Shenyang, China; State Key Laboratory of Synthetical Automation for Process Industries, Northeastern University, Shenyang, China

Abstract:
Most of the current research on dynamic multiobjective optimization problems (DMOPs) assumes that environmental changes can be detectable. However, undetectable changes are frequently encountered in real-world applications, which pose a serious challenge for the existing methods. Because undetectable changes can lead to the failure of change detection techniques, thereby making it difficult to adapt to environmental changes for most algorithms. Therefore, to effectively deal with DMOPs with undetectable changes, this work proposes a dual mutation-based dynamic multiobjective evolutionary algorithm (DM-DMOEA). The proposed DM-DMOEA incorporates the following two main components. First, based on the exploration level of the population, an adaptive selection strategy is proposed, which enables the adaptive identification of individuals for mutation. Second, a dual mutation scheme is developed, utilizing both the polynomial mutation and the Gaussian mutation. These mutation operations are applied on the selected individuals to generate the mutated individuals, allowing for diverse exploration in the search space. After conducting the above two strategies, the population will evolve by the evolutionary criterion of multiobjective optimization. As a result, the algorithm can effectively adapt to undetectable changes in the environment. Comprehensive empirical studies are conducted on different benchmark functions and a real-world application to evaluate the performance of DM-DMOEA. Experimental results have demonstrated that DM-DMOEA is competitive in tracking the Pareto front over time when facing undetectable changes.

Abstract:
Large language models have recently become known for their ability to generate computer programs, especially through tools, such as GitHub Copilot, a domain where genetic programming (GP) has been very successful so far. Although they require different inputs (free-text versus input/output examples) their goal is the same—program synthesis. Therefore, in this work, we compare how well GitHub Copilot and GP perform on common program synthesis benchmark problems. We study the structure and diversity of the generated programs by using well-known software metrics. We find that GitHub Copilot and GP solve a similar number of benchmark problems (85.2% versus 77.8%, respectively). We find that GitHub Copilot generated smaller and less complex programs as GP, while GP is able to find new and unique problem solving strategies. This increase in diversity of solutions comes at a cost. When analyzing the success rates for 100 runs per problem, GitHub Copilot outperforms GP on over 50% of the problems.

Abstract:
Within the current literature on multiobjective optimization, there is a scarcity of comparisons between equation-based white-box solvers to evolutionary black-box solvers. It is commonly held that when dealing with linear and quadratic models, equation-based deterministic solvers are generally the preferred choice. The present study aims at challenging this hypothesis, and we show that particularly in box-constrained mixed-integer (MI) problems it is worth employing evolutionary methods when the goal is to achieve a good approximation of a Pareto frontier. To do so, this article compares a mathematical programming approach with an evolutionary method for set-oriented Pareto front approximation of bi-objective quadratic MI optimization problems. The focus is on convex quadratic under-constrained models wherein the decision variables are either tightly or loosely bounded by box-constraints. Through an empirical assessment of families of quadratic models across varying Hessian forms, variable ranges, and condition numbers, the study compares the performance of the CPLEX-based diversity maximization approach to a state-of-the-art evolutionary multiobjective optimization meta-heuristic with MI mutation and crossover operators. We identify and explain strengths and weaknesses of both approaches when dealing with loosely bounded box-constraints, and prove a theorem regarding the potential undecidability of such multiobjective problems featuring unbounded integer decision variables. The empirical results systematically confirm that black-box and white-box solvers can be competitive, especially in the case of loose box-constraints.

Abstract:
This article presents a novel knowledge-based genetic algorithm (GA) to generate a collision-free path in complex environments. The proposed algorithm infuses specific domain knowledge into robot path planning through the development of five problem-specific operators that integrate a local search technique to improve efficiency. In addition, the proposed algorithm introduces a unique and straightforward representation of the robot path and an effective method for evaluating the path quality and accurately detecting collisions. The proposed algorithm is capable of finding optimal or suboptimal robot paths in both static and dynamic environments. Simulation and experimental studies are conducted to showcase the effectiveness and efficiency of the proposed algorithm. Furthermore, a comparative study is performed to highlight the indispensable role of specialized genetic operators within the proposed algorithm in solving the path planning problem.

Abstract:
Large language models (LLMs) have not only revolutionized natural language processing but also extended their prowess to various domains, marking a significant stride toward artificial general intelligence. The interplay between LLMs and evolutionary algorithms (EAs), despite differing in objectives and methodologies, share a common pursuit of applicability in complex problems. Meanwhile, EA can provide an optimization framework for LLM’s further enhancement under closed box settings, empowering LLM with flexible global search capacities. On the other hand, the abundant domain knowledge inherent in LLMs could enable EA to conduct more intelligent searches. Furthermore, the text processing and generative capabilities of LLMs would aid in deploying EAs across a wide range of tasks. Based on these complementary advantages, this article provides a thorough review and a forward-looking roadmap, categorizing the reciprocal inspiration into two main avenues: 1) LLM-enhanced EA and 2) EA-enhanced LLM. Some integrated synergy methods are further introduced to exemplify the complementarity between LLMs and EAs in diverse scenarios, including code generation, software engineering, neural architecture search, and various generation tasks. As the first comprehensive review focused on the EA research in the era of LLMs, this article provides a foundational stepping stone for understanding the collaborative potential of LLMs and EAs. The identified challenges and future directions offer guidance for researchers and practitioners to unlock the full potential of this innovative collaboration in propelling advancements in optimization and artificial intelligence. We have created a GitHub repository to index the relevant papers: https://github.com/wuxingyu-ai/LLM4EC.

Abstract:
Both dual-population and two-phase strategies are effective for utilizing infeasible solution information and significantly enhancing the ability of algorithms to solve constrained multiobjective optimization problems. However, most existing algorithms tend to underperform when facing problems with complex constraints. To address these issues, a constrained multiobjective evolutionary algorithm named DPTPEA, which combines dual-population and two-phase strategies, is proposed in this article. DPTPEA employs two collaborative populations [the exploitive population (expPop) and the tractive population (tracPop)] and divides the evolutionary process of the tracPop into two phases (Phase 1 and Phase 2). In Phase 1, the tracPop ignores constraints and drags the expPop across the infeasible region by sharing offspring information. In Phase 2, the tracPop adopts the epsilon-constrained method to converge toward the constrained Pareto front and to guide the expPop exploiting different feasible regions. Moreover, a dynamic cooperation strategy, a boundary point direction sampling strategy, and a dynamic environmental selection are proposed to improve the exploration ability of tracPop for solving complex problems. Comprehensive experiments on three popular test suites demonstrate that DPTPEA outperforms seven state-of-the-art algorithms on most test problems.

Abstract:
Evolutionary multiobjective optimization (EMO) is a highly active research field that has attracted many researchers and practitioners over the past three decades. Surprisingly, until now, the goal of almost all EMO algorithms is to compute a suitable finite size representation of the Pareto set/front of a given multiobjective optimization problem or at least a part of it. In other words, the quest is restricted to optimal solutions. In this work, we argue that the entire set of nearly optimal solutions—which includes all optimal ones—is of potential interest for the decision maker as they contain in addition to the optimal solutions alternative realizations or backup solutions. We further make a first effort to reliably compute the set of nearly optimal solutions via EMO algorithms. To this end, we first propose a new set of interest, N_Q,\epsilon , and analyze its topology. In a next step, we propose an unbounded archiver that aims to capture N_Q,\epsilon and analyze it with respect to monotonicity and limit behavior. After this, we discuss the related subset selection problem which comes with unbounded archivers leading to four different algorithms. Finally, we numerically investigate the behavior of the archiver and the selection strategies, and present some results when using the archiver as external archiver to three widely used multiobjective evolutionary algorithms indicating the benefit of the new approach.

Abstract:
This article addresses the challenge of selecting the most suitable optimization algorithm by presenting a comprehensive computational comparison between stochastic and deterministic methods. The complexity of algorithm selection arises from the absence of a universal algorithm and the abundance of available options. Manual selection without comprehensive studies can lead to suboptimal or incorrect results. In order to address this issue, we carefully selected 25 promising and representative state-of-the-art algorithms from both aforementioned classes. The evaluation with up to the 20 dimensions and large evaluation budgets (10^5× n) was carried out in a significantly expanded and improved version of the DIRECTGOLib v2.0 library, which included ten distinct collections of primarily continuous test functions. The evaluation covered various aspects, such as solution quality, time complexity, and function evaluation usage. The rankings were determined using statistical tests and performance profiles. When it comes to the problems and algorithms examined in this study, EA4eig, EBOwithCMAR, APGSK-IMODE, 1-DTC-GL, OQNLP, and DIRMIN stand out as superior to other derivative-free solvers in terms of solution quality. While deterministic algorithms can locate reasonable solutions with comparatively fewer function evaluations, most stochastic algorithms require more extensive evaluation budgets to deliver comparable results. However, the performance of stochastic algorithms tends to excel in more complex and higher-dimensional problems. These research findings offer valuable insights for practitioners and researchers, enabling them to tackle diverse optimization problems effectively.

Abstract:
The decomposable feature of operations in the welding shop scheduling scenario results in a vast search space, posing challenges for the design of traditional optimization algorithms. Addressing the multiobjective distributed heterogeneous welding shop scheduling problem (DHWSP), this work introduces a generalized multitasking framework. It establishes an auxiliary task by employing knowledge-and-learning-synergy neighborhood search, thereby enhancing the convergence and diversity of the original task. In this framework, an enhanced competitive swarm optimizer is adopted as the original task for DHWSP. Additionally, knowledge expression and transfer strategies are designed to expedite the comprehensive performance of each task by leveraging knowledge gained from search results. Finally, a memetic algorithm based on the multitasking framework is proposed for DHWSP. The effectiveness of the algorithm is validated through extensive experiments on 20 DHWSP instances. Numerical experimental results indicate that the proposed multitasking framework can significantly improve algorithmic comprehensive performance, demonstrating its efficacy in addressing the multiobjective DHWSP within a complex search space.

Abstract:
Bilevel multiobjective optimization problem (BLMOP) can be seen as a special constrained multiobjective optimization problem (CMOP), where the optimality constraint of the lower-level (LL) problem cannot be easily and quickly checked, but must be verified by solving the LL problem. If there was a relatively simple alternative formulation for effectively identifying LL optimal solutions, the abovementioned special constraint could become as simple as the usual constraints and the nested optimization structure of BLMOP would be altered, which can greatly improve efficiency and effectively find LL optimal solutions with excellent upper-level (UL) performance. In this article, we improve the training mechanism for conditional generative adversarial network (cGAN) by introducing multiple generators to construct a reasonable reference distribution, so as to prevent the discriminator from performance degradation. With a discriminator identifying LL optimal solutions effectively, the nested optimization structure of BLMOP is altered by adding the objective that maximizing the discriminator output score into the UL objectives and removing the LL optimality constraint, realizing synchronous optimization of UL and LL vectors. The cooperation of generators and discriminator greatly reduces the computational overhead for solving BLMOPs. The proposed algorithm has achieved the best or competitive results in comparison with 6 state-of-the-art algorithms and a nested method on benchmark problems and a real-world problem, whose effectiveness has been demonstrated.

Abstract:
In recent years, black-box distributed optimization (DBO) has been widely studied to solve complex optimization problems in multiagent systems (MASs), such as hyperparameter optimization of distributed machine learning. However, most existing methods use a fixed or diminishing step size to sample and search in the black box optimization space, which makes it challenging to maintain optimization efficiency on different optimization problems. In this work, we propose a multiagent evolution strategy with cooperative and cumulative step adaptation (CCSA-DES). In CCSA-DES, each agent executes the algorithm to sample and explores its local objective function, and communicates with other agents to optimize the global objective function cooperatively, which is the sum of local objective functions. To improve the sampling adaptability, we design a cooperative and cumulative step adaptation method (CCSA) consisting of inner adaptation and outer adaptation. By detecting the evolution path of the MAS, CCSA decreases the step size when the evolution directions of agents are conflicting and increases the step size when consistent. In terms of theoretical analysis, we first discuss the working principle of CCSA, and then discuss the system consensus of CCSA-DES. In terms of experimental verification, CCSA-DES achieves better-consensus performance and competitive solution quality compared with state-of-the-art algorithms for DBO.

Abstract:
Dynamic multimodal optimization problems (DMMOPs) represent the multimodal optimization problems that the optimal solution changes over time. Due to the wide application of DMMOPs in reality, some related algorithms have been proposed in recent years. Most existing algorithms employ a single dynamic response mechanism and embed it in existing multimodal evolutionary algorithms. However, these algorithms often perform limited when environmental change involves multiple types, and they fail to consider utilizing historical information to assist static multimodal optimizers. To solve these issues, this article proposes historical information-assisted dynamic response integration and adaptive niche methods (HIA-DRI-AN) for dynamic multimodal optimization. In HIA-DRI-AN, an dynamic response integration method with adaptive adjustment mechanism is proposed for generating the initial population when the change happens. This method considers the change types of DMMOPs, and integrates targeted dynamic response mechanisms to respond to the different change types. Also, this method can adaptively self-adjust to balance the convergence and diversity of the initial population depending on the integrated response mechanism’s performance in historical environments. Furthermore, a niching adaptive division strategy is proposed to enhance the performance of the static optimizer. The strategy dynamically divides niches based on the integrated response mechanism’s performance and the current evolutionary stage, which can adjust the preference for diversity and convergence during evolution. The comprehensive experimental results on 24 test functions show that HIA-DRI-AN is superior compared to some state-of-the-art dynamic multimodal algorithms.

Affiliations: College of Automation and Electronic Engineering, Qingdao University of Science and Technology, Qingdao, Shandong, China; School of Data Science, Qingdao University of Science and Technology, Qingdao, Shandong, China; School of Automation, Central South University, Changsha, Hunan, China; Department of Computer Science and Technology, Ocean University of China, Qingdao, Shandong, China; Faculty of Data Science, City University of Macau, Macau, SAR, China

Abstract:
Dynamic interval multiobjective optimization problems, such as those encountered in wireless sensor network scheduling and portfolio selection, are increasingly prevalent. However, they present significant challenges due to the inherent uncertainty and variability of their parameters. This article proposes a dynamic interval multiobjective evolutionary algorithm in terms of multitask learning and inverse mapping. The algorithm employs an interval-based MOEA/D as its foundational framework. Upon encountering environmental changes, prediction models for the midpoints and widths of intervals are developed using multitask learning combined with a self-evolving fuzzy system. These models generate a predicted Pareto front (PF) in the objective space. Subsequently, inverse mappings of the objective functions at the new time are established to identify solutions that correspond to the predicted PF in the decision space. Finally, these solutions are expanded to form an initial population at the new time. Testing on 18 benchmark optimization problems and an uncertain scheduling of underwater wireless sensor networks, the proposed algorithm demonstrates both competitiveness and superiority when compared to five state-of-the-art algorithms.

Abstract:
Dynamic workflow scheduling (DWS) is a challenging and important optimization problem in cloud computing, aiming to execute multiple heterogeneous workflows on dynamically leased virtual machine resources to satisfy user-defined Quality of Service requirements. For the popular deadline-constrained DWS in cloud problem, a virtual machine selection rule (VMSR) and a task selection rule (TSR) need to be designed simultaneously to minimize the rental fee and deadline violation penalty. For this purpose, Dual-Tree Genetic Programming (DTGP) has been previously developed to automatically evolve effective VMSRs and TSRs. However, existing DTGP approaches assume that VMSR and TSR, as well as terminals used by VMSRs and TSRs are equally important and evolve both VMSRs and TSRs in a opaque manner, i.e., without using any knowledge about different impacts of trees and terminals. Several recent studies clearly indicate that different trees or terminals have varied performance impacts, making it critical to develop adaptive mutation mechanisms for effective DTGP. Driven by this motivation, this article proposes two new levels of adaptive mutation mechanisms, contributing to the development of a new DTGP algorithm, which features the use of three new probability vectors for adaptive tree selection of VMSR and TSR at the first level and adaptive terminal selection at the second level while mutating any existing dual-tree individuals. Extensive experimental results demonstrate that the proposed two adaptive mechanisms can improve the effectiveness of DTGP compared to four baseline algorithms.

Abstract:
In the post-pandemic era, more manufacturers have expedited the shift from centralized to distributed manufacturing to enhance supply chain resilience. Along with this, the distributed shop floor scheduling problem has attracted much attention from academia, one of which is the distributed flexible job-shop scheduling problem (DFJSP). Nonetheless, the majority of research on DFJSPs overlooks crucial real-world necessities, such as multiobjective decision making and preventive maintenance (PM). Thus, this article suggests a multiobjective DFJSP with PM (DFJSP/PM) as a new variant of the DFJSP. The aim is to achieve a tradeoff between production and maintenance to minimize the makespan, maintenance cost, and energy consumption. To this end, we establish a mathematical model and then customize a learning-assisted bi-population evolutionary algorithm (LBPEA) to solve it. In LBPEA, a novel encoding mechanism is proposed to initialize the population randomly. Then, a neighborhood search heuristic is designed to enhance the population’s quality. To balance the convergence and diversity of the population, a bi-population evolution idea is introduced during the environmental selection. Besides, a two-stage local search (LS) process is adaptively triggered to balance the allocation of computational resources between exploration and exploitation. At the first stage, a reinforcement learning mechanism is employed to intelligently select LS operators to adjust either the operations’ sequence or assignment to different factories and machines, while the second stage is to adjust the number and placement of maintenance decisions. Experimental results show that LBPEA has excellent performance in terms of convergence and diversity when solving the proposed multiobjective DFJSP/PM.

Abstract:
Malignant melanoma is a very deadly form of skin cancer and early diagnosis can significantly reduce the mortality rate. Many computer-aided diagnosis (CAD) systems have been developed as second opinion diagnostic aids to assist dermatologists in diagnosing malignant melanoma. However, traditional CAD systems often require domain knowledge for feature extraction, while neural network-based CAD systems require specialized knowledge for designing network structures and often have poor interpretability. In this article, we propose a new skin cancer CAD system based on genetic programming (GP) to automatically learn effective features for classification with strong interpretability. The approach can automatically evolve variable-length models to extract informative features for describing skin cancer images based on a relatively simple program structure, a new function set, and a terminal set. In addition, compared with other GP methods, this approach employs a newly proposed duplicate subtree removing mechanism, which can effectively prevent the duplication of features, thereby simplifying the model and enhancing its interpretability. The proposed approach has been examined on five real-world skin cancer classification tasks. The results suggest that the proposed approach achieves better performance than GP-based, neural network-based feature learning comparison methods and traditional comparison methods in most cases. Further analysis shows that the proposed approach has employed a smaller tree structure and can automatically evolve/learn models with potentially high interpretability.

Abstract:
Detecting infeasible solutions is an important challenge in closed-box multiobjective bilevel optimization (MOBO) due to a lower-level (LL) optimization problem used as a constraint (along with equality and inequality constraints) in an upper-level optimization. In this context, a feasible solution is an optimal solution to the LL problem, typically addressed using evolutionary algorithms (EAs) (or other metaheuristics) for complex scenarios. Since metaheuristics do not guarantee optimality, then infeasible solutions are inherently reported. This article introduces a novel data-driven framework to automatically identify infeasible solutions reported by bilevel EAs (BEA) when addressing any MOBO problem. This framework operates without imposing strong assumptions on objectives or constraints, making it versatile and easy to implement. Besides, our approach uses solutions reported by one or multiple BEAs to detect and eliminate possible infeasible solutions. This approach helps to enhance algorithm comparison by eliminating infeasible solutions before applying existing performance indicators. The framework is successfully applied to several MOBO problems, including two real-world instances from specialized literature, solved by four different BEAs. Results suggest that the proposed framework advances the field of bilevel evolutionary optimization, offering a tool for promoting fair algorithmic comparisons and ensuring solution feasibility without requiring a deep understanding of the problem context.

Abstract:
Multisource location is a significant application in the field of robot swarm and is required to find all sources whose number and distribution are unknown in advance. With few parameters and fast search, particle swarm optimizer (PSO) variants that have certain grouping capability have been applied to address multisource location problems (MSLPs) by dividing a swarm such that every source has robots to locate. However, they are difficult to predetermine the exact number of groups, require a big number of robots, and are easily trapped in the no-signal areas when the proportion of no-signal areas is high. This work proposes a virtual-source and virtual-swarm-based PSO (VVPSO) to divide a search area into multiple cells equally, each of which has a virtual source in its center. Then, instead of robots grouping, only one group of robots is employed to traverse all virtual sources, and search their corresponding cells to locate real sources by a new PSO called real-virtual mapping PSO (RMPSO). RMPSO asymmetrically maps a robot into a particle swarm with multiple virtual particles to perform PSO, which greatly reduces the requirements for the number of robots. Experimental results show that VVPSO has great search scalability and can solve large-scale MSLPs than two state-of-the-art grouping methods and three representative multimodal PSO variants, even with only one robot. Hence, this work greatly advances the field of multisource location by using mobile robot swarm.

Abstract:
There are many real-world applications with uncertainties that can be modeled as the dynamic interval multiobjective optimization problems (DI-MOPs). However, it is challenging for the traditional algorithms to converge rapidly before time-varying parameters change to obtain optimal solutions under interval objectives. So far, there is a lack of studies on the evaluation methods for interval optimal solutions in dynamic problems. Therefore, a fast evaluation framework is proposed in this article to tackle these issues. In this framework, we first derive a new hash function based on the Canberra distance and provide a theoretical proof of the validity and local sensitivity of the hash function, from which a Canberra locality sensitive hashing (CLSH) is constructed. The CLSH accelerates the search for interval evaluation objects in uncertain environments. Further, we propose an adaptive interval crowding distance (AICD) with relaxed constraints to obtain a global improvement in the quality of the solutions. The candidate solutions in the above framework are generated by the environment awareness and directed migration of the mutiobjective bacteria colony chemotaxis (MOBCC) algorithm. This complete algorithm is called the dynamic interval MOBCC (DI-MOBCC). In addition, the theoretical proofs of the validity and local sensitivity of hash functions are also provided. Computational results on the eight benchmark optimization problems and a path planning of the mobile robots in uncertain environments validate that the DI-MOBCC is more competitive than the other state of the art algorithms in tackling DI-MOPs.

Abstract:
Subset selection, a fundamental problem in various domains, is to choose a subset of elements from a large candidate set under a given objective or multiple objectives. Pareto optimization for subset selection (POSS) has emerged as a powerful paradigm for addressing subset selection problems. Recently, some POSS variants have been proposed to further improve its performance. In this article, we propose a new POSS variant, named targeted POSS (TPOSS). TPOSS differs from POSS in four aspects: 1) problem formulation; 2) population initialization; 3) mutation; and 4) environmental selection. The main idea of TPOSS is to focus the search on the target region of subset selection with respect to the subset cardinality in order to improve the search efficiency. We conduct comprehensive experiments to compare TPOSS with six state-of-the-art algorithms on three subset selection tasks (i.e., sparse regression, unsupervised feature selection, and hypervolume subset selection) where the size of the candidate sets ranges from 20 to 400. Experimental results show that with respect to the objective value of the best feasible subset, TPOSS outperforms the other algorithms on all the three tasks, which suggests the potential of TPOSS to enhance subset selection in various domains.

Abstract:
Constrained multiobjective optimization problems (CMOPs) pervade real-world applications in science, engineering, and design. Constraint violation (CV) has been a building block in designing evolutionary multiobjective optimization (EMO) algorithms for solving CMOPs. However, in certain scenarios, constraint functions might be unknown or inadequately defined, making CV unattainable and potentially misleading for the conventional constrained EMO algorithms. To address this issue, we present the first of its kind evolutionary optimization framework, inspired by the principles of the alternating direction method of multipliers that decouples objective and constraint functions. This framework tackles CMOPs with unknown constraints by reformulating the original problem into an additive form of two subproblems, each of which is allotted a dedicated evolutionary population. Notably, these two populations operate toward complementary evolutionary directions during their optimization processes. In order to minimize discrepancy, their evolutionary directions alternate, aiding the discovery of feasible solutions. Comparative experiments conducted against the five state-of-the-art constrained EMO algorithms on 120 benchmark test problem instances with varying properties as well as two real-world engineering optimization problems demonstrate the effectiveness and superiority of our proposed framework. Its salient features include faster convergence and enhanced resilience to various Pareto front shapes.

Abstract:
Multirobot task allocation (MRTA) is a challenging bi-level problem in the multirobot cooperative systems (MRCSs) and offers an effective method for addressing complex tasks. However, dynamic /uncertain environments can easily invalidate original schemes in practical MRTA decision-makings. Further, a nested structure in MRTA problems makes computational expensive. Therefore, the two main tasks are 1) finding a sufficient number of equivalent schemes for MRTA problems to adapt to task environments and 2) improving algorithm search efficiency in bi-level optimization problems. In this study, a multimodal multiobjective evolutionary algorithm (MMOEA) based on deep reinforcement learning (DRL) and large neighborhood search (LNS), called MMOEA-DL, is proposed to solve MRTA problems. In the MMOEA-DL, the task allocation problem, which is considered as the upper-level optimization problem, is solved using an improved MMOEA. The traveling salesman problem (TSP) regarded as the lower-level optimization problem is addressed via end-to-end method (i.e., DRL) and LNS. By leveraging the end-to-end method to obtain the results of the lower-level optimization, the bi-level optimization problem is effectively transformed into a single-level optimization problem. To demonstrate the performance of the proposed algorithm, 16 MRTA simulation scenarios and two actual MRTA scenarios with evenly and unevenly distributed task points are introduced in the present study. The simulation results verify that the MMOEA-DL not only provides decision-makers with expanded equivalent optimal schemes to address dynamic environments or unforeseen circumstances, but also offers a novel approach to solve the multimodal multiobjective bi-level optimization problem while saving computational costs.

Affiliations: Key Laboratory of Image Information Processing and Intelligent Control of Education Ministry of China, School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan, China; State Key Laboratory of Advanced Electromagnetic Technology, School of Electrical and Electronic Engineering, Huazhong University of Science and Technology, Wuhan, China; Department of Pathology, Renmin Hospital of Wuhan University, Wuhan, China; Trustworth and General Artificial Intelligence Laboratory, School of Engineering, Westlake University, Hangzhou, China

Abstract:
Accurate cell classification is crucial but expensive for large-scale single-cell RNA sequencing (scRNA-seq) analysis. Gene selection (GS) emerges as a pivotal technique in identifying gene subsets of scRNA-seq for classification accuracy improvement and gene scale reduction. Nevertheless, the rising scale of scRNA-seq data presents challenges to existing GS methods regarding performance and computational time. Thus, we propose a surrogate-assisted evolutionary algorithm for multiobjective GS to address these deficiencies. An innovative two-phase initialization method is proposed to select sparse solutions to provide preliminary insights into gene contributions. Then, a binary competitive swarm optimizer is proposed for effective global search, where a local search method is embedded to eliminate irrelevant genes for efficiency consideration. Additionally, a surrogate model is adopted to forecast classification accuracy efficiently and substitutes part of the computationally expensive classification process. Experiments are conducted on eight large-scale scRNA-seq datasets with more than 20 000 genes. The effectiveness of the proposed GS method for scRNA-seq cell classification compared with eight state-of-the-art methods is validated. Gene expression analysis results of selected genes further validated the significance of the genes selected by the proposed method in the classification of scRNA-seq data.

Abstract:
Protein structure prediction (PSP) is an important scientific problem because it helps humans to understand how proteins perform their biological functions. This article models the PSP problem as a multiobjective optimization problem with three fast and accurate knowledge-based energy functions. This way, using evolutionary computation (EC)-based artificial intelligence (AI) approach to solve this multiobjective PSP problem to find the optimal structure is explainable. Considering that the multiple populations for multiple objectives (MPMO) framework shows efficient performance in solving lots of multiobjective benchmarks and real-world problems, this article proposes a new AI approach named improved MPMO-based differential evolution (IMPMO-DE) to solve the multiobjective PSP problem. To our best knowledge, this is the first time that MPMO is applied to PSP, with three novel strategies. First, an adaptive archive-based mutation strategy is proposed to better balance the exploration and exploitation abilities by adaptively using different archive-based mutation operators in different evolutionary stages. Second, a mixed individual transfer strategy is proposed to share search information among the multiple populations to accelerate the convergence speed. Third, an evolvable archive update strategy is proposed to generate more promising solutions through evolving the archived solutions. IMPMO-DE is tested on 28 representative proteins and all the available template-free modeling proteins up to 404 residues in the famous critical assessment of protein structure prediction (CASP14) competition. Experimental results show that IMPMO-DE performs better than the compared state-of-the-art EC-based PSP methods and ranks above average compared with all the CASP14 competitors. More importantly, IMPMO-DE is a new efficient AI approach that opens a promising optimization-based evolutionary and explainable way for efficient PSP rather than deep learning approaches like AlphaFold2, especially for newly discovered proteins without similar known protein structures.

Abstract:
In many real-world scenarios (e.g., product manufacturing), multiple heterogeneous robots cooperate to complete complex tasks with precedence constraints. In these heterogeneous multirobot systems, the multirobot task allocation problem is important and has attracted increasing attention. The problem usually involves multiple optimization objectives for decision making. However, existing approaches meet challenges on multiobjective problems with large-scale tasks and precedence constraints in terms of solution diversity and convergence. Therefore, this article formulates a tri-objective model and proposes a cooperative ant colony system (CACS) to optimize three objectives, i.e., minimizing the makespan, average robot traveling time, and average task waiting time. In CACS, three ant colonies are created to simultaneously optimize the three objectives. To coordinate with the precedence constraints of the problem, solutions are encoded as a task-alliance sequence. A new solution construction method is developed to generate feasible solutions using dynamic heuristic information and two pheromone matrices. Particularly, one matrix deposits pheromone between tasks for task selection and the other between tasks and robots for alliance building. To further improve solution diversity and convergence, a fusion-based local search is adopted to generate high-quality solutions by combining information from multiple colonies. Thirty instances are constructed with different numbers of tasks and robots under complex precedence constrains. Experimental results show that CACS outperforms state-of-the-art methods in terms of the inverted generational distance and hypervolume metrics.

Abstract:
The knowledge about variable interactions is frequently employed in state-of-the-art research concerning genetic algorithms (GAs). Whether these interactions are known a priori (gray-box optimization) or are discovered by the optimizer (black-box optimization), they are used for many purposes, including proposing more effective mixing operators. Frequently, the quality of the problem structure decomposition is decisive to the optimizers’ effectiveness. However, in gray- and black-box optimization, the dependency between the variables is assumed to be symmetric. This work identifies and defines the nonsymmetrical (directional) variable dependencies. We show that these dependencies may exist (together with symmetrical) in the considered real-world problem, in which we must optimize subsequent variable groups (one after the other) in the appropriate optimization order that is not known by the optimizer. To improve GA’s effectiveness in solving the problem of such features, we propose a new linkage learning (LL) technique that can discover symmetrical and nonsymmetrical dependencies (in binary and nonbinary discrete domains) and distinguish them from each other. We show that telling these two types of dependencies from each other may significantly increase the optimizer’s effectiveness in solving real-world and theoretical problems with nonsymmetrical dependencies. Finally, we show that using the proposed LL technique does not deteriorate the effectiveness of the state-of-the-art optimizer in solving typical benchmarks containing only symmetrical dependencies.

Abstract:
With the advent of Big Data, managing large-scale portfolios of thousands of securities is one of the most challenging tasks in the asset management industry. This study uses an evolutionary multiobjective technique to solve large-scale portfolio optimization problems with both long-term listed and newly listed securities. The future returns of long-term listed securities are defined as random variables whose probability distributions are estimated based on sufficient historical data, while the returns of newly listed securities are defined as uncertain variables whose uncertainty distributions are estimated based on experts’ knowledge. Our approach defines security returns as theoretically uncertain random variables and proposes a three-moment optimization model with practical trading constraints. In this study, a framework for applying arbitrary multiobjective evolutionary algorithms to portfolio optimization is established, and a novel evolutionary algorithm based on large-scale optimization techniques is developed to solve the proposed model. The experimental results show that the proposed algorithm outperforms state-of-the-art evolutionary algorithms in large-scale portfolio optimization.

Abstract:
Handling conflicting objectives and finding multiple Pareto optimal solutions are two challenging issues in solving multiobjective optimization problems (MOPs). Inspired by the efficiency of multitask optimization (MTO) in finding multiple optimal solutions of MTO problem (MTOP), we propose to treat MOP as a MTOP and solve it by using MTO. By transforming the MOP into a MTOP, not only that the difficulty in handling conflicting objectives can be avoided, but also that MTO can help efficiently find well-distributed multiple optimal solutions for MOP. With the above idea, this article proposes a new multiobjective optimization method via MTO, with the following three contributions: 1) a theorem is proposed to theoretically show the relationship between MOP and MTOP and how MOP can be transformed into a MTOP; 2) based on the theoretical analysis, a multiple tasks for multiple objectives (MTMOs) framework is proposed for solving MOP efficiently; and 3) a MTMO-based evolutionary algorithm is developed to solve MOP, together with two novel strategies. One is a target point estimation strategy for transforming the MOP into a MTOP automatically and accurately. The other is an archive-based implicit knowledge transfer strategy for efficiently transferring knowledge across multiple tasks to enhance the optimization results of multiple tasks together. The superiority of the proposed algorithm is validated in extensive experiments on 15 MOPs with objective numbers varying from 3 to 20 and with six state-of-the-art algorithms as competitors. Therefore, solving MOP and even many-objective optimization problem via MTO is a new, promising, and efficient method.

Abstract:
LGP has been successfully applied to dynamic job shop scheduling (DJSS) to automatically evolve dispatching rules. Flow control operations are crucial in concisely describing complex knowledge of dispatching rules, such as different dispatching rules in different conditions. However, existing linear genetic programming (LGP) methods for DJSS have not fully considered the use of flow control operations. They simply included flow control operations in their primitive set, which inevitably leads to a huge number of redundant and obscure solutions in LGP search spaces. To move one step toward evolving effective and interpretable dispatching rules, this article explicitly considers the characteristics of flow control operations via grammar-guided LGP and focuses on IF operations as a starting point. Specifically, this article designs a new set of normalized terminals to improve the interpretability of IF operations and proposes three restrictions by grammar rules on the usage of IF operations: 1) specifying the available inputs; 2) the maximum number; and 3) the possible locations of IF operations. The experiment results verify that the proposed method can achieve significantly better-test performance than state-of-the-art LGP methods and improves interpretability by IF-included dispatching rules. Further investigation confirms that the explicit introduction of IF operations helps effectively evolve different dispatching rules according to their decision situations.

Affiliations: School of Artificial Intelligence, Anhui University, Hefei, China; Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, Institutes of Physical Science and Information Technology, Anhui University, Hefei, China; Computational Intelligence Laboratory, School of Electrical and Information Engineering, Zhengzhou University, Zhengzhou, China; Information Materials and Intelligent Sensing Laboratory of Anhui Province, School of Computer Science and Technology, Anhui University, Hefei, China; Information Materials and Intelligent Sensing Laboratory of Anhui Province, Anhui University, Hefei, Anhui, China; School of Engineering, Westlake University, Hangzhou, China

Abstract:
As a pivotal technique in intelligent education systems, cognitive diagnosis (CD) serves to reveal students’ knowledge proficiency for better tackling subsequent tasks. Unfortunately, due to pursuing high model interpretability, existing manually designed models for CD often hold simplistic architectures, which cannot cope with intricate data in modern education platforms. Furthermore, the bias of human design limits the emergence of novel and effective CD models (CDMs). To develop interpretable and more effective models, thus this article proposes an evolutionary multiobjective neural architecture search (NAS) approach for CD. Specifically, we first adopt a comprehensive search space for the NAS task of CD: all candidate models can be encompassed by a general model that deals with three distinct types of inputs. Then, an innovative model interpretability objective is devised to formulate the architecture search task as a bi-objective optimization problem (BOP). To solve the BOP, we employ a multiobjective genetic programming (MOGP) as the search strategy to explore the search space. To make the employed MOGP search well, all architectures are first encoded by trees for easy optimization, and we devise a genetic operation and a population initialization strategy to expedite its convergence. Finally, the proposed approach is actually an MOGP-based NAS approach for CD. Extensive experiments show that CDMs searched by the proposed approach exhibit significantly better performance than existing models and hold as good interpretability as handcrafted models. Besides, the effectiveness of the proposed MOGP search strategy, the devised objective, and tailored strategies are validated.

Abstract:
Distributed manufacturing and fine-manufacturing are two typical scenarios of modern manufacturing industries in the context of globalization and customization. The distributed differentiation flowshop integrated scheduling problem (DDFISP) is a novel model that deals with the integrated scheduling problem of these two manufacturing scenarios. In the DDFISP, jobs have multiple customized types and are manufactured in a number of distributed factories. Each factory includes three fine-processing stages: 1) parallel machine fabrication; 2) single machine assembly; and 3) dedicated machine differentiation. In this article, a new distributed memetic evolutionary architecture is first built, which consists of four modules with distinct functions, including global exploration, local exploitation, knowledge transfer, and search restart. The exploration and exploitation are coevolved in the distributed way and communicated by knowledge transfer. This architecture can be used as a universal model to construct evolutionary algorithms. Following this architecture and devising each module innovatively, a novel knowledge transfer-driven distributed memetic algorithm (KTDMA) is constructed to solve the DDFISP. Specifically, global exploration is performed on multiple populations by dynamically selecting global exploration optimizers from predefined external repository. Local exploitation is executed on an independent elite archive by a destruction-construction local search and a key block local search. Knowledge transfer is conducted to communicate the superior information between exploration and exploitation based on a point-ring topology. Search restart is adaptively carried out to alleviate the search homogeneity. Computational results show the effectiveness of the proposed evolutionary architecture and special designs, and demonstrate that the KTDMA performs more competitive than the compared state-of-the-art algorithms.

Abstract:
The Kriging model has been widely used in regression-based surrogate-assisted evolutionary algorithms (SAEAs) for expensive multiobjective optimization by using one model to approximate one objective, and the fusion of all the models forms the fitness surrogate. However, when tackling expensive many-objective optimization problems, too many models are required to construct such a fitness surrogate, which incurs cumulative prediction uncertainty and higher computational cost. Considering that the fitness surrogate works to predict different objective values to help select promising solutions with good convergence and diversity, this article proposes a novel model reduction idea to change the many-models-based fitness surrogate to a two-models-based indicator surrogate (TIS) that directly approximates convergence and diversity indicators. Based on TIS, a hierarchical and ensemble SAEA (HES-EA) is proposed with three stages. First, the HES-EA transforms the many objectives of the real-evaluated solutions into two indicators (i.e., the convergence and diversity indicators) and divides these solutions into different clusters. Second, an HES consisting of a cluster surrogate and different TISs is trained through these clustered solutions and their indicators. Third, during the optimization process, the HES can predict the candidate solutions’ cluster information via the cluster surrogate and indicator information via the TISs. Promising solutions can thus be selected based on the predicted information via a clustering-based sequential selection strategy without real fitness evaluation consumption. Compared with state-of-the-art SAEAs on three widely used benchmark suites up to 184 instances and one real-world application, HES-EA shows its superiority in both optimization performance and computational cost.

Affiliations: School of Information Science and Technology, Hebei Agricultural University, Baoding, China; School of Mechanical and Electrical Engineering and the Intelligent Agricultural Equipment Technology Innovation Center of Hebei, Hebei Agricultural University, Baoding, China; College of Science, Northwest A & F University, Yangling, China; Department of Automation, Tsinghua University, Beijing, China; State Key Laboratory for Manufacturing System Engineering, Xi’an Jiaotong University, Xi’an, China

Abstract:
Compared to existing distributed flowshop scheduling problems (DFSPs), this article addresses a more realistic DFSP, which further integrates intermachine blocking constraints and two customized processing stages of assembly and differentiation. The manufacturing process includes job fabrication in distributed blocking flowshops, job-to-product assembly on an assembling machine, and product fine-processing on differentiation machines. A novel evolutionary framework is proposed, including continuous space exploration, discrete space exploitation, and dual-space knowledge migration. This framework has advanced features of distribution, memetic evolution, and dual-space coevolution, and can serve as a unified model to construct algorithms for different optimization problems. Based on this evolutionary framework, a matrix and learning assisted distributed dual-space memetic algorithm (DDMA) is proposed to address the studied problem. In DDMA, exploratory population is represented as a real-valued matrix, where individuals are defined as different identities that will dynamically adjust with evolution. In accordance with identity differences, exploratory population is heterogeneously evolved in the continuous search space by a matrix-assisted evolutionary optimizer. The exploitative population consists of elite individuals, which are represented as discrete permutations. It is evolved in parallel with exploratory population and in the discrete search space by a learning-assisted evolutionary optimizer, including a reinforcement learning-based multineighborhood local search and a statistical learning-based enhanced local search. To communicate the superior evolutionary information obtained by exploration and exploitation, an adaptive knowledge migration across continuous and discrete search spaces is proposed based on the impact of migration on the population diversity. The computational results demonstrate the superiority of DDMA over state-of-the-art algorithms.

Affiliations: School of Computer Science and Communication Engineering, Jiangsu University, Zhenjiang, China; School of Computer Science and Communication Engineering and the Jiangsu Key Laboratory of Security Technology for Industrial Cyberspace, Jiangsu University, Zhenjiang, China; School of Computer Science, Jiangsu University of Science and Technology, Zhenjiang, China; School of Engineering and Computer Science, Baylor University, Waco, TX, USA; School of Computer and Information, Anqing Normal University, Anqing, China

Abstract:
The utilization of both constrained and unconstrained-based optimization for solving constrained multiobjective optimization problems (CMOPs) has become prevalent among recently proposed constrained multiobjective evolutionary algorithms (CMOEAs). However, the constrained-based optimization which adopted by many CMOEAs typically gives priority to feasible solutions over infeasible ones regardless of their objective values, potentially leading to degraded performance due to the elimination of promising infeasible solutions with strong convergence and diversity. Furthermore, many existing CMOEAs have difficulty in maintaining diversity while focusing on feasibility, thereby hindering their ability to effectively address CMOPs characterized by complex feasible regions. To tackle these challenges, a constraint-Pareto dominance relationship is proposed in this article to evaluate solutions based on both objectives and feasibility, to improve the optimization potential by reduce the elimination probability of promising infeasible solutions. A diversity enhancement strategy is also designed to enable simultaneously focus on both diversity and feasibility, thus effectively ensuring the diversity of the feasible solutions obtained. Empirical results from benchmark suites and real-world problems demonstrate that our proposed algorithm surpasses state-of-the-art CMOEAs.

Abstract:
In this review article, we provide a comprehensive guide to the endeavor of problem decomposition (PD) within the field of genetic programming (GP), specifically tree-based GP for supervised learning tasks. We analyzed in detail 70 manuscripts that deal with motifs, such as “PD,” “modular GP,” “subroutine evolution,” “hierarchical GP,” “cooperative coevolution,” among others. As a result of this study, we propose a unifying taxonomy that categorizes efforts on PD in GP along three major axes: 1) the architecture of evolved composite solutions; 2) PD strategy; and 3) credit assignment approach. This classification system sheds light on how the diverse proposed methodologies for PD relate to each other and where most of the research efforts have focused to this day. Rather than discussing in detail any particular set of works, we see this overview as a map that may help researchers in obtaining a wider view of existing efforts for PD in GP, as well as provide a cohesive framework that allows the disclosure of future developments in clearly differentiated niches. We close this article with a brief analysis that compares the current state of PD methodologies in GP with that of another exemplar of PD in machine learning: deep learning.

Affiliations: School of Information and Control Engineering, China University of Mining and Technology, Xuzhou, China; College of Automation and Electronic Engineering, Qingdao University of Science and Technology, Qingdao, China; School of Mechanical and Electrical Engineering, China University of Mining and Technology (Beijing), Beijing, China; School of Computer and Information, Anhui Normal University, Wuhu, China

Abstract:
Feature selection (FS) is an effective data preprocessing technique. In some practical applications, features may continuously arrive one by one or by groups, and we cannot know the exact number of features before learning. Streaming FS (SFS) aims to remove redundant and irrelevant features from the continuously arriving features. This article proposes a three-stage SFS method based on dynamic feature clustering and particle swarm optimization (SFS-DPSO). In the first stage, an online relevance analysis is utilized to quickly remove irrelevant features, reducing the size of newly arrived feature groups. In the second stage, a dynamic feature clustering technique is employed to divide redundant features into different groups, thereby reducing the search space for subsequent evolutionary algorithms. In the third stage, a historical information-driven integer particle swarm optimization algorithm is exploited to search for optimal feature subset in the clustered feature space. The proposed algorithm is applied in 12 typical datasets with different difficulty levels and a real-word case, experimental results show that it can achieve better-classification results in a reasonable time and is superior to most existing algorithms.

Abstract:
The vehicle routing problem with simultaneous pickup and delivery and time windows (VRPSPDTW) has a number of real-world applications, especially in reverse logistics. In this work, we propose an effective memetic algorithm that integrates a lightweight feasible and infeasible route descent search and a learning-based adaptive route-inheritance crossover to solve this complex problem. We evaluate the effectiveness of the proposed algorithm on the set of 65 popular benchmark instances as well as 20 real-world large-scale benchmark instances. We provide a comprehensive analysis to better understand the design and performance of the proposed algorithm.

Abstract:
The most obvious characteristic of dynamic multiobjective optimization problems (DMOPs) is the time-varying Pareto-optimal set (POS) or/and Pareto-optimal front (POF). This kind of problem poses a higher challenge to the evolutionary algorithms, as it requires populations to rapidly track and converge the updated POF in new environments. Differing from the superposition of several strategies in the literatures, we propose an adaptive multistrategy algorithm based on the extent of environmental change, called AMEEC to effectively handle various dynamic changes. AMEEC chooses the corresponding strategies for different environmental changes adaptively. When the environment changes moderately or similarly, the prediction based on the clustered center points, POS manifold prediction, and generation of random solutions based on the ideal points are employed to relocate the population individuals in the new environment. Otherwise, the trend prediction model is employed to predict the knee points of each part and the center points of each cluster, and to adaptively adjust the area of random solutions based on the ideal and nadir points focuses on enhancing the diversity of population members. The proposed AMEEC is tested comprehensively on 19 benchmark problems compared with the six state-of-the-art algorithms. All algorithms use RM-MEDA (a regularity model-based multiobjective estimation of distribution algorithm) as a static optimizer. The experimental results demonstrate that AMEEC can achieve good convergence, diversity, and distribution, and is more competitive in dealing with the dynamic problems.

Abstract:
A common goal in evolutionary multiobjective optimization is to find suitable finite-size approximations of the Pareto front of a given multiobjective optimization problem. While many multiobjective evolutionary algorithms (MOEAs) have proven to be very efficient in finding good Pareto front approximations, they may need quite a few resources or may even fail to obtain optimal or nearly optimal approximations. Hereby, optimality is implicitly defined by the chosen performance indicator. In this work, we propose a set-based Newton method for the Hausdorff approximations of the Pareto front to be used within MOEAs. To this end, we first generalize the previously proposed Newton step for the performance indicator to treat constrained problems for general reference sets. To approximate the target Pareto front, we propose a particular strategy for generating the reference set that utilizes the data gathered by the evolutionary algorithm during its run. Finally, we show the benefit of the Newton method as a postprocessing step on several benchmark test functions and different base evolutionary algorithms.

Abstract:
Feature discretization can improve the processing efficiency of remote sensing big data. However, the distribution of target attribute values is often difficult to ascertain, and there are complex correlations between features, making it extremely difficult to obtain an optimal discretization scheme for remote sensing data. Although feature discretization methods based on evolutionary models can achieve some considerable results, it is difficult to formulate appropriate strategies without prior knowledge as guidance, which makes searching in multidimensional space inefficient and prone to falling into local optima. Therefore, we propose a Genetic algorithm based on deep Q-learning (DQLGA) to optimize the discretization scheme of remote sensing data. First, we design a state set in the crossover and mutation stages by balancing the global and local search capabilities of genetic operators to obtain an accurate mapping of states in high-dimensional feature space. Then, we simulate the variation pattern of the optimal discretization scheme by analyzing the distribution of all individuals in the population during the evolution process to construct a reasonable adaptive reward function in reinforcement learning model. Finally, we introduce a pair of deep Q-networks with the same structure by treating the calculation of Q-values as a function fitting problem to fulfil an efficient updating of massive Q-values in state transition. We compare DQLGA with state-of-the-art feature discretization methods on remote sensing data. The experimental results indicate that DQLGA significantly improves the search efficiency of feature discretization methods based on evolutionary models, achieving higher-classification accuracy while further reducing the number of breakpoints.

Abstract:
Distributed optimization has attracted lots of attention in recent years. Thanks to the intrinsic parallelism and great search capacity, evolutionary computation (EC) has the potential for black-box and nonconvex distributed optimization. However, due to the decentralization of local objective functions, it is challenging to optimize the global objective function with efficient communication and guaranteed system consensus. To tackle this challenge, we propose a multiagent swarm optimization method with adaptive internal and external learning (MASOIE). In MASOIE, each agent evolves a swarm of particles by internal learning and external learning. Internal learning enables agents to optimize their local objectives, while external learning enables agents to cooperate to achieve a consensus toward the global objective. To improve the consensus ability, we design a special velocity setting of external learning for particle evolution. We provide the theoretical analysis of the system consensus of deterministic MASOIE. To improve communication efficiency, we design an adaptive communication mechanism to adjust the communication interval, enabling agents to explore at the early stage and reach system consensus at the later stage. Empirical studies show that the proposed algorithm achieves stable consensus performance, competitive solution quality and lower communication cost on benchmark functions compared with existing black-box distributed algorithms.

Abstract:
With increasing energy concerns and development of globalization, energy-aware scheduling and distributed scheduling have become significant topics in modern manufacturing. However, realistic manufacturing scenarios, such as collaborative scheduling of distributed shops and limited transportation resources, are rarely taken into account. To bridge the gap, this article addresses the energy-aware distributed flexible job-shop with transportation constraints (EDFJSP-T) and proposes a feedback learning-based memetic algorithm (FLMA) to minimize makespan and total energy consumption simultaneously. First, a mathematical model is formulated to represent the relationship between different subproblems. Additionally, an encoding and decoding method based on forward insertion is designed to reduce the search space and obtain high-quality schedules. Second, various problem-specific operators are designed to focus on different subproblems and objectives to enrich search patterns. Third, memetic search with feedback learning is proposed via introducing observer indexes for both population state and individual state to adaptively match appropriate operators for individuals. Besides, local intensification search with multiple operators is incorporated for low-density regions to further improve exploitation ability. The parameter setting is investigated and experimental tests are carried out using different types of instances. The comparisons demonstrate the effectiveness of the feedback learning mechanism and the superiority of the FLMA over existing algorithms for solving the EDFJSP-T.

Affiliations: School of Computer Science, Shaanxi Normal University, Xi’an, China; School of Computer and Electronic Information/School of Artificial Intelligence, the Information Security and Privacy Protection Technology, and the Key Laboratory of Numerical Simulation for Large Scale Complex Systems, Ministry of Education, Nanjing Normal University, Nanjing, China; College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China

Abstract:
Since severe environmental problem in manufacturing industries is becoming increasingly prominent, energy-efficient production scheduling has gained more and more attentions. This article studies an energy-efficient distributed fuzzy hybrid blocking flow-shop scheduling problem (EEDFHBFSP), where processing time and setup time are uncertain. The objective is to minimize fuzzy makespan and total fuzzy energy consumption simultaneously. To solve such problem, a mixed-integer linear programming model is first presented to format it. Then, a meta-Q-learning-based multiobjective metaheuristic (MQL-MM) is proposed. In MQL-MM, a machine-position-based dispatch rule is designed as the decoding scheme. A decomposition-based constructive heuristic (DCH) is employed to generate the initial population with high quality and diversity. Several problem-specific search operators are developed to explore and exploit the solution space. A meta-Q-learning-based multiobjective search framework is presented to guide the using of search operators, which includes a meta-training phase and an adaptive search phase. The meta-training phase is employed to train the search operators to construct the Q-learning model. The adaptation search phase utilizes such model to conduct the automatic selection of the search operators. Moreover, an energy-saving strategy is designed to improve the candidate solutions. Finally, we conduct extensive experiments. The experimental results show that the designs of MQL-MM are effective, and MQL-MM performs better than several well-performing methods on solving EEDFHBFSP.

Abstract:
Design change is an important issue in complex product development projects. In a complex product with numerous parts (also known as components), the change of one key part may spread to other parts associated with it, generating a chain reaction throughout the entire project. Therefore, it is necessary to select a suitable change plan involving only fewer crucial parts in order to enhance the product’s performance, minimize change cost, and reduce change duration/time. Focusing on the case where the correlation strength between parts cannot be accurately obtained, in this article we study an interval multiobjective evolutionary algorithm for finding excellent design change plans. First, on the basis of the established multilayer product network with interval correlation weights, an interval multiobjective optimization model of the product design change planning problem is established, where three new objective functions regarding product performance, carbon trading cost and supply risk are defined. Then, a constraint multiobjective evolutionary algorithm based on interval Pareto dominance is proposed to search for optimal change plans. Several novel operators, including the problem characteristic-guided population update strategy, the probability-based interval Pareto dominance, and the interval constraint handling strategy, are developed to enhance the algorithm’s performance. Finally, the proposed algorithm is compared with eight existing algorithms on the two design change cases, experimental results revealed its effectiveness.

Abstract:
This article considers the longest common square subsequence (LCSqS) problem, a variant of the longest common subsequence (LCS) problem in which solutions must be square strings. A square string can be expressed as the concatenation of a string with itself. The LCSqS problem has applications in bioinformatics, for discovering internal similarities between molecular structures. We propose a metaheuristic approach, a biased random key genetic algorithm (BRKGA) hybridized with a beam search (BS) from the literature. Our approach is based on reducing the LCSqS problem to a set of promising LCS problems. This is achieved by cutting each input string into two parts first and then evaluating such a transformed instance by solving the LCS problem for the obtained overall set of strings. The task of the BRKGA is, hereby, to find a set of good cut points for the input strings. For this purpose, the search is carefully biased by problem-specific greedy information. For each cut point vector, the resulting LCS problem is approximately solved by the existing BS approach. The proposed algorithm is evaluated against a previously proposed state-of-the-art variable neighborhood search (VNS) on random uniform instances from the literature, new nonuniform instances, and a real-world instance set consisting of DNA strings. The results underscore the importance of our work, as our novel approach outperforms former state-of-the-art with statistical significance. Particularly, they evidence the limitations of the VNS when solving nonuniform instances, for which our method shows superior performance.

Abstract:
The cumulative capacitated vehicle routing problem (CCVRP) with single or multiple depots (MDCCVRP) is a variant of the popular capacitated vehicle routing problem. Instead of minimizing the total travel time, the objective here is to minimize the sum of all customers’ waiting times. This problem has a variety of real-world applications, especially in post-disaster humanitarian relief. To solve the challenging CCVRP and MDCCVRP, we propose a unified two-individual evolutionary algorithm that follows the memetic search framework. The algorithm integrates several key features: a two-individual population mechanism to accelerate convergence while maintaining population diversity, a dedicated edge assembly crossover to generate high-quality offspring, and an adaptive feasible and infeasible local search to achieve a balanced exploration between feasible and infeasible solutions. The algorithm is evaluated on 39 CCVRP instances and 78 MDCCVRP instances commonly used in the literature. Computational results show that for the CCVRP, the algorithm outperforms the leading algorithms by achieving improved best results (new upper bound) for 13 instances and matching the best results for 23 other instances. For the MDCCVRP, the algorithm achieves nine improved best results and matches the best results for the remaining instances. The critical components of the algorithm are investigated to understand their contributions.

Abstract:
The dispatch optimization of coal mine integrated energy system is challenging due to high dimensionality, strong coupling constraints, and multiobjective. Existing constrained multiobjective evolutionary algorithms struggle with locating multiple small and irregular feasible regions when solving the dispatch problem. To address this issue, we here develop a multiform EA framework that incorporates the dispatch-correlated domain knowledge to effectively deal with strong constraints and multiobjective optimization. Possible evolutionary multiform construction strategy based on complex constraint relationship analysis and handling, i.e., constraint-coupled spatial decomposition, constraint strength classification, and constraint handling technique, is first explored. Within the multiform evolutionary optimization framework, two strategies, i.e., an elite-guided knowledge transfer by designing a special crowding distance mechanism to select dominant individuals from each task and a neighborhood-driven dual mutation to effectively balance the diversity and convergence of each optimized task for the differential evolution algorithm, are further developed. The performance of the proposed algorithm in feasibility, convergence, and diversity is demonstrated in a case study of a coal mine integrated energy system (IES) by comparing with CPLEX solver and eight state-of-the-art constrained multiobjective EAs.

Abstract:
Large-scale multiobjective binary optimization problems (MBOPs) often occur in real-world applications, where the function evaluation can only be performed through computationally expensive simulations, which renders standard exact and heuristic methods ineffective. Aggregation-based surrogate-assisted multiobjective evolutionary algorithms have been developed and shown to be promising for solving such problems. They define a set of uniformly distributed weight vectors as search directions, on which all search resources are placed to perform the evolution. However, the Pareto fronts of large-scale MBOPs are discrete and nonuniform. As a result, many weight vectors are useless, thus a lot of search resources are wasted. To address this challenge, we propose a surrogate-assisted neighborhood search (SANS) for expensive large-scale multiobjective binary optimization. SANS uses only a few weight vectors to save search resources while maintaining an adequate diversity. To further utilize the limited search resources, a Q-learning-based method is designed to dynamically allocate search resources to weight vectors. Furthermore, a surrogate-assisted variable neighborhood search is developed to speed up the search without getting trapped in a local optimum prematurely. To robustly and reliably predict the quality of the found solutions, global and local surrogate models are trained by different training samples and then work collaboratively. The experimental results have demonstrated the superiority of SANS over seven state-of-the-art algorithms on the MBOPs with up to 1000 decision variables using only 500 real solution evaluations.

Abstract:
The flexible job shop scheduling, as the most typical production mode in industrial manufacturing, aims to improve production efficiency. However, the proposal of energy-saving and emission-reduction policy implies that it is impossible to increase the processing speed to improve productivity, and energy consumption is also becoming another important optimization objective. For the multiobjective flexible job shop scheduling problem, the optimization process tends to converge faster in some regions. This is because different scheduling sequences obtain the same objective values, i.e., there is a multimodal characteristic, which is still hardly investigated. Therefore, optimizing the decision space and the objective space simultaneously has become an urgent challenge that needs to be solved. To overcome the above challenges, we model the multimodal multiobjective flexible job shop scheduling problem with variable speed (MMFJSP-S) and propose an affinity propagation hierarchical memetic algorithm (APHMA) to minimize makespan and total energy consumption. First, four problem-specific neighborhood structures are employed to enhance the convergence. Then, an affinity propagation clustering combined with the random forests strategy is proposed to classify the global and local Pareto sets. Finally, a hierarchical environmental selection strategy is designed to ensure the convergence and diversity in the decision and objective spaces. Evaluations against seven advanced algorithms on MK and DP benchmarks demonstrate the competitive performance of APHMA in solving MMFJSP-S.

Affiliations: Department of Mathematics, Yunnan Normal University, Kunming, Yunnan, China; School of Information Science and Engineering, Shandong Normal University, Jinan, Shandong, China; School of Electronic Information Engineering, Inner Mongolia University, Hohhot, China; Department of Engineering Science, Macau University of Science and Technology, Macau, SAR, China; School of Mechatronic Engineering and Automation, Shanghai University, Shanghai, China

Abstract:
Driven by the evolution of smart and sustainable manufacturing paradigms under Industry 5.0, which emphasize adaptability, connectivity, and data-driven decision-making, the dynamic flexible job shop scheduling problem (DFJSSP) has emerged as a critical area of research. The DFJSSP involves scheduling jobs in a highly dynamic and uncertain manufacturing environment where new tasks are continually introduced, further complicating the scheduling process. In this study, the DFJSSP is extended to incorporate single crane transportation and sequence-dependent setup times, reflecting real-world manufacturing constraints. To tackle this multifaceted problem, we introduce a novel approach, i.e., a multipopulation-based evolutionary multitask optimization (EMTO) framework. In addition, the genetic programming algorithm is employed as a generative hyperheuristic to deal with the dynamic uncertainties in the shop floor. Two components are collaborated to optimize two objectives, i.e., minimizing the maximum completion time and the total tardiness. Furthermore, a dynamic transfer ratio is proposed, allowing the proportion of knowledge transfer to adapt throughout the iteration process, balancing convergence speed with population diversity. The results demonstrate that both the EMTO framework and the dynamic transfer ratio significantly enhance the performance of the algorithm. Compared to well-known constructive heuristics and reinforcement learning algorithm, the proposed approach enables parallel resolution of multiple optimization objectives, leading to enhanced scheduling efficiency and adaptability in dynamic manufacturing environments.

Abstract:
In complex navigational environments, effective unmanned surface vehicle (USV) scheduling is critical. However, the obstacle avoidance problems are often ignored in the literature. This study addresses the multiobjective heterogeneous USV scheduling problems with obstacle avoidance. The objective is to minimize the maximum completion time and total carbon emissions. First, a mathematical model is developed to describe the concerned problems. Second, an A algorithm is employed to obtain a path between task points with avoiding obstacles. Third, to obtain a high-quality scheduling scheme, an improved artificial bee colony (ABC) algorithm with deep Q-network (DQN) is designed. According to the problem nature, six novel rules are designed for finding high-quality solutions in initialized population. Five local search strategies are designed based on the structure of solution space. The scales of the instances and different objectives are utilized to designed a DQN, which recommends suitable local search strategies during iterations for improving convergence speed. Then, the Gurobi solver is employed to verify the proposed model. The effectiveness of the proposed strategies is verified by 13 instances with different scales. Finally, the experimental results and discussions show that the designed ABC with DQN has the strongest competitiveness among all compared algorithms.

Abstract:
Dynamic multiobjective optimization problems (DMOPs) with a changing number of objectives (NObjs) may have Pareto-optimal set (PS) manifold expanding or contracting over time. Knowledge transfer has been used for solving DMOPs, since it can transfer useful information from solving one problem instance to solve another related problem instance. However, we show that the state-of-the-art transfer approach based on heuristic lacks diversity on problem with extremely strong bias and loses convergence on problems with multimodality and variable correlation, after the NObjs increases and decreases, respectively. Therefore, we propose a novel transfer strategy based on learning, called learning to expand and contract PS (denoted as LEC) for enhancing diversity and convergence after NObj increases and decreases, respectively. It first learns potentially good directions for expansion and contraction separately via principal component analysis. Then, the most promising expansion and contraction directions are selected from their candidates according to whether they help diversity and convergence, respectively. Finally, PS is learned to be expanded and contracted based on these most promising directions. Comprehensive studies using 13 DMOP benchmarks with a changing NObjs demonstrate that our proposed LEC is effective on improving solution quality, not only right after changes but also after optimization of different generations, compared to state-of-the-art algorithms.

Abstract:
For fault detection (FD) in manufacturing, various machine learning (ML) models have been widely applied to minimize human intervention and improve detection performance. Even though ML models, such as neural networks (NNs), have been shown to identify faults effectively, root cause identification (RCI) is becoming more difficult due to their black-box structures and the tradeoff between accuracy and interpretability. In order to improve performance while maintaining interpretability, we propose a new framework named Feature Extraction for finding Root causes for Manufacturing Applications with Tree-based algorithms (FERMAT), which enhances the performance of height-limited decision trees (DTs) (C4.5) through dimensionally aware genetic programming for feature extraction. Especially in FERMAT, only interpretable features are extracted to prevent DTs from delivering uninterpretable expressions to practitioners. In the present study, FERMAT’s applicability to RCI was verified with both manufacturing and nonmanufacturing datasets with different imbalance ratios. The experimental results showed that FERMAT outperformed the other single-tree-based models by extracting good features and delivered performance comparable to the black-box models.

Abstract:
The hybrid seru manufacturing mode widely exists in many real-world production enterprises, where workers are usually partially cross-trained due to high-training costs and employee turnover. However, the hybrid seru system scheduling problem considering worker heterogeneity (HSSWH) has rarely been studied in academia. To fill the gap, this article introduces a branch-and-bound enhanced cooperative evolutionary algorithm (BBCEA) to solve the HSSWH. Three core search components and an evaluation component are proposed in BBCEA, which are crafted to be problem-specific. In the exploration search component, a probability model sampling method and crossover collaborate to generate offspring with high quality and diversity. In the exploitation search component, five knowledge-based operators collaborate with a knowledge-guided operator selection strategy, which is designed by fully utilizing the problem properties and feedback information. In the exact search component, a branch-and-bound method is designed to solve the bottom layer subproblem precisely, which can greatly improve the effectiveness of the algorithm. In the evaluation component, a look-up table method is proposed to reduce computation effort by avoiding duplicate calculations. Numerical experimental results validate the superiority of the BBCEA in addressing the HSSWH, which can obtain the best solution on 95% of the instances compared with the state-of-the-art algorithms.

Affiliations: International Business School Suzhou, Xi’an Jiaotong-Liverpool University, Suzhou, China; Digital Port Technologies Lab, School of Computer Science, University of Nottingham Ningbo China, Ningbo, China; School of Computer Science, University of Nottingham, Nottingham, U.K.; Department of Engineering, University of Cambridge, Cambridge, U.K.; School of Engineering, Westlake University, Hangzhou, China

Abstract:
Efficient truck dispatching is crucial for optimizing container terminal operations within dynamic and complex scenarios. Despite good progress being made recently with more advanced uncertainty-handling techniques, existing approaches still have generalization issues and require considerable expertise and manual interventions in algorithm design. In this work, we present deep reinforcement learning-assisted genetic programming hyper-heuristics (DRL-GPHHs) and their ensemble variant (DRL-GPEHH). These frameworks utilize a reinforcement learning (RL) agent to orchestrate a set of auto-generated genetic programming (GP) low-level heuristics, leveraging the collective intelligence, ensuring advanced robustness and an increased level of automation of the algorithm development. DRL-GPEHH, notably, excels through its concurrent integration of a GP heuristic ensemble, achieving enhanced adaptability and performance in complex, dynamic optimization tasks. This method effectively navigates traditional convergence issues of deep RL (DRL) in sparse reward and vast action spaces, while avoiding the reliance on expert-designed heuristics. It also addresses the inadequate performance of the single GP individual in varying and complex environments and preserves the inherent interpretability of the GP approach. Evaluations across various real port operational instances highlight the adaptability and efficacy of our frameworks. Essentially, innovations in DRL-GPHH and DRL-GPEHH reveal the synergistic potential of RL and GP in dynamic truck dispatching, yielding transformative impacts on algorithm design and significantly advancing solutions to complex real-world optimization problems.

Abstract:
The distributed hybrid flowshop scheduling problems (DHFSPs) widely exist in various industrial production processes, and thus have received widespread attention. However, the existing research mainly focuses on interfactory and intermachine collaboration, but ignores collaborative processing between jobs. Therefore, this article considers rescheduling DHFSP with job merging and reworking (DHFRPJM) and establishes a mixed-integer linear programming model. The objective is to minimize the makespan. Based on problem-specific knowledge, a decoding heuristic and initialization strategy considering job merging are designed. An acceleration strategy based on critical path is adopted to save the computational effort of the iterated greedy algorithm. A local search strategy based on a deep reinforcement learning algorithm further improves the performance of the algorithm. Experimental results based on actual production data show that the proposed algorithm outperforms other algorithms in closely related literature.

Affiliations: Shanghai Institute of AI for Education and the School of Computer Science and Technology, East China Normal University, Shanghai, China; Department of Computer Science and Engineering, and the Department of Statistics and Data Science, Research Institute of Trustworthy Autonomous Systems, the Guangdong Key Laboratory of Brain-Inspired Intelligent Computation, Southern University of Science and Technology, Shenzhen, China; Department of Computer Science and Engineering, Research Institute of Trustworthy Autonomous Systems, the Guangdong Key Laboratory of Brain-Inspired Intelligent Computation, Southern University of Science and Technology, Shenzhen, China

Abstract:
Multiobjective optimization problems (MOPs) containing a large number of decision variables, which are also known as large-scale MOPs (LSMOPs), pose great challenges to most existing evolutionary algorithms. This is mainly because that a high dimensional decision space degrades the effectiveness of search operators notably, and balancing convergence and diversity becomes a challenging task. In this article, we propose a two-population-based algorithm for large-scale multiobjective optimization named large-scale two population algorithm. In the proposed algorithm, solutions are classified in to two subpopulations: 1) a convergence subpopulation (CP) and 2) a diversity subpopulation (DP), aiming at convergence and diversity, respectively. In order to improve convergence speed, a fitness-aware variation operator (FAVO) is applied to drive DP solutions toward CP. Besides, an adaptive penalty-based boundary intersection (APBI) strategy is adopted for environmental selection in order to balance convergence and diversity temporally during different stages of evolution process. Experimental results on benchmark test problems with 100-2000 decision variables demonstrate that the proposed algorithm can achieve the best overall performance compared with several state-of-the-art large-scale multiobjective evolutionary algorithms.

Abstract:
Integrated order batching and picker routing (IOBPR) is a complex combinatorial optimization problem in real-world intelligent manufacturing systems. Heuristics are often used for solving such complex scheduling problems. Manually designing scheduling heuristics suffer from two limitations: 1) few problem features can be taken into account and 2) the design process is time consuming. Genetic programming hyper heuristic (GPHH) approaches have been proposed on many scheduling problems to automatically evolve effective heuristics. However, existing GPHH approaches are often problem specific and requires careful design of problem specific terminal sets and evolution operators. The aim of this work is to develop a GPHH approach to evolve heuristics for the IOBPR problem. In particular, we propose a novel terminal set (NT) with three types of terminals, and a GPHH with elitist mutation (GPHH-EM) algorithm. Extensive experiments demonstrate that the heuristics evolved by GPHH-EM can significantly outperform other state-of-the-art competing algorithms designed by human experts. Further analysis indicates that the three types of terminals effectively complement to improve evolved heuristics for decision making. Furthermore, the newly developed elitist mutation operator expedites the evolutionary process for GPHH to find high-quality heuristics.

Abstract:
This article proposes a surrogate-assisted evolutionary algorithm to tackle expensive inequality-constrained optimization problems through global exploration and local exploitation. The algorithm begins with an exploration stage that involves sampling in three kinds of global regions: 1) the feasible region; 2) the better-objective region; and 3) the converging region. Specifically, sampling in the uncertain feasible region mitigates issues caused by inaccurate objective surrogates. In addition, sampling in the uncertain region containing better-objective values than the current best-feasible solution reduces the risk of missing the global optimum due to inaccurate constraint surrogates. Moreover, sampling in the converging region facilitates quick convergence to the global feasible optimum. Following the exploration stage, promising feasible and infeasible solutions are further refined using local surrogate-based search strategies. To address the risk of missing the global optimum resulting from limited local region scope, the regions are adaptively extended if predicted infill points lie on the boundary. If an infill point is determined to showcase a better-objective value after accurate evaluation, a rewarding local search is performed within the local region. This exploration-exploitation process iterates until the computation budget is exhausted. Experimental results demonstrate that the proposed algorithm outperforms the selected state-of-the-art algorithms on the majority of tested problems.

Abstract:
The growing ubiquity of machine learning (ML) has led it to enter various areas of computer science, including black-box optimization (BBO). Recent research is particularly concerned with Bayesian optimization (BO). BO-based algorithms are popular in the ML community, as they are used for hyperparameter optimization and more generally for algorithm configuration. However, their efficiency decreases as the dimensionality of the problem and the budget of evaluations increase. Meanwhile, derivative-free optimization methods have evolved independently in the optimization community. Therefore, we urge to understand whether cross-fertilization is possible between the two communities, ML and BBO, i.e., whether algorithms that are heavily used in ML also work well in BBO and vice versa. Comparative experiments often involve rather small benchmarks and show visible problems in the experimental setup, such as poor initialization of baselines, overfitting due to problem-specific setting of hyperparameters, and low statistical significance. With this article, we update and extend a comparative study presented by Hutter et al. in 2013. We compare BBO tools for ML with more classical heuristics, first on the well-known Black-Box Optimization Benchmarking test suite from the COCO environment and then on Direct Policy Search for OpenAI Gym, a reinforcement learning benchmark. Our results confirm that BO-based optimizers perform well on both benchmarks when budgets are limited, albeit with a higher computational cost, while they are often outperformed by algorithms from other families when the evaluation budget becomes larger. We also show that some algorithms from the BBO community perform surprisingly well on ML tasks.