进化计算领域文章更新主要包括以下六大方向如下：
基础理论（包括遗传算法、进化策略、遗传编程、群智能等算法设计、理论研究、基准测试、进化思想、算法软件、综述等）
进化优化（包括黑盒优化、多目标优化、约束优化、噪声优化、多任务优化、多模态优化、迁移优化、大规模优化、昂贵优化、学习优化等）
组合优化（包括进化神经组合优化、进化机器人、路线规划、布局布线、工业控制、调度等）
神经进化（包含进化神经网络的参数、超参数、架构、规则等）
进化学习（包括进化特征选择、强化学习、多目标学习、公平性学习、联邦学习、进化计算机视觉、进化自然语言处理、进化数据挖掘等）
应用研究（工业、网络、安全、物理、生物、化学等）
文章来源主要包括：
1. IEEE CIS: CIM, TEVC, TNNLS, TFS, TAI, TETCI, CEC
2. IEEE CS/SMC: TPAMI, TKDE, TPDS, TCYB, TSMC, Proc. IEEE
3. ACM: TELO, GECCO, FOGA, ICML
4. MIT: ECJ, ARTL, JMLR, NIPS
5. Elsevier/Springer: AIJ, SWEVO, SCIS, PPSN
6. AAAI/MK/OR: AAAI, IJCAI, ICLR
7. Else: NMI, NC, PNAS, Nature, Science, ArXiv
基础理论
Optimal Linear Crossover for Mitigating Negative Transfer in Evolutionary Multitasking, IEEE TEVC
https://ieeexplore.ieee.org/document/10742196
Evolutionary multitasking algorithms use information exchange among individuals in a population to solve multiple optimization problems simultaneously. Negative transfer is a critical factor that affects the performance of evolutionary multitasking algorithms. In this study, we propose an innovative approach to mitigate negative transfer in evolutionary multitasking algorithms. The proposed approach is grounded in rigorous theoretical analysis, which provides valuable theoretical insights into the design of an optimal linear crossover operator for mitigating negative transfer. By identifying interpretable conditions, we establish a solid theoretical foundation to prevent negative transfer in diverse scenarios. Building upon these findings, we theoretically derive a closed-form expression for the optimal crossover operator and propose practical design methods based on approximations. Furthermore, we integrate the proposed optimal crossover operator into a fundamental evolutionary multitasking algorithm framework. The resultant algorithm is comparable or superior to other state-of-the-art methods. Empirical validation through comprehensive experiments confirms the effectiveness of our theoretical findings.
Real Relative Encoding Genetic Algorithm for Workflow Scheduling in Heterogeneous Distributed Computing Systems, IEEE TPDS
https://ieeexplore.ieee.org/document/10745772
This paper introduces a novel Real Relative encoding Genetic Algorithm (R 2 GA) to tackle the workflow scheduling problem in heterogeneous distributed computing systems (HDCS). R 2 GA employs a unique encoding mechanism, using real numbers to represent the relative positions of tasks in the schedulable task set. Decoding is performed by interpreting these real numbers in relation to the directed acyclic graph (DAG) of the workflow. This approach ensures that any sequence of randomly generated real numbers, produced by cross-over and mutation operations, can always be decoded into a valid solution, as the precedence constraints between tasks are explicitly defined by the DAG. The proposed encoding and decoding mechanism simplifies genetic operations and facilitates efficient exploration of the solution space. This inherent flexibility also allows R 2 GA to be easily adapted to various optimization scenarios in workflow scheduling within HDCS. Additionally, R 2 GA overcomes several issues associated with traditional genetic algorithms (GAs) and existing real-number encoding GAs, such as the generation of chromosomes that violate task precedence constraints and the strict limitations on gene value ranges. Experimental results show that R 2 GA consistently delivers superior performance in terms of solution quality and efficiency compared to existing techniques.
EVOTER: Evolution of Transparent Explainable Rule sets, ACM TELO
https://dl.acm.org/doi/10.1145/3702651
Most AI systems are black boxes generating reasonable outputs for given inputs. Some domains, however, have explainability and trustworthiness requirements that cannot be directly met by these approaches. Various methods have therefore been developed to interpret black-box models after training. This paper advocates an alternative approach where the models are transparent and explainable to begin with. This approach, EVOTER, evolves rule sets based on extended propositional logic expressions. The approach is evaluated in several prediction/classification and prescription/policy search domains with and without a surrogate. It is shown to discover meaningful rule sets that perform similarly to black-box models. The rules can provide insight into the domain and make hidden biases explicit. It may also be possible to edit the rules directly to remove biases and add constraints. EVOTER thus forms a promising foundation for building trustworthy AI systems for real-world applications in the future.
Toward Automated Algorithm Design: A Survey and Practical Guide to Meta-Black-Box-Optimization
https://arxiv.org/abs/2411.00625
In this survey, we introduce Meta-Black-Box-Optimization (MetaBBO) as an emerging avenue within the Evolutionary Computation (EC) community, which incorporates Meta-learning approaches to assist automated algorithm design. Despite the success of MetaBBO, the current literature provides insufficient summaries of its key aspects and lacks practical guidance for implementation. To bridge this gap, we offer a comprehensive review of recent advances in MetaBBO, providing an in-depth examination of its key developments. We begin with a unified definition of the MetaBBO paradigm, followed by a systematic taxonomy of various algorithm design tasks, including algorithm selection, algorithm configuration, solution manipulation, and algorithm generation. Further, we conceptually summarize different learning methodologies behind current MetaBBO works, including reinforcement learning, supervised learning, neuroevolution, and in-context learning with Large Language Models. A comprehensive evaluation of the latest representative MetaBBO methods is then carried out, alongside an experimental analysis of their optimization performance, computational efficiency, and generalization ability. Based on the evaluation results, we meticulously identify a set of core designs that enhance the generalization and learning effectiveness of MetaBBO. Finally, we outline the vision for the field by providing insight into the latest trends and potential future directions. Relevant literature will be continuously collected and updated at this https URL.
进化优化
Evolutionary Multitasking With Adaptive Knowledge Transfer for Expensive Multiobjective Optimization, IEEE TEVC
https://ieeexplore.ieee.org/document/10747213
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 vali-date our superiority over several state-of-the-art SAEAs on most test cases.
A Thompson Sampling-Based Sparse Evolutionary Operator for Sparse Large-Scale Multi-Objective Optimization, IEEE TEVC
https://ieeexplore.ieee.org/document/10742907
Traditional multi-objective evolutionary algorithms (MOEAs) face challenges when addressing sparse large-scale multi-objective 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 non-zero 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 10,041 decision variables, compared to algorithms designed explicitly for SLSMOPs.
DPP-HSS: Towards Fast and Scalable Hypervolume Subset Selection for Many-objective Optimization, IEEE TEVC
https://ieeexplore.ieee.org/document/10742945
Hypervolume subset selection (HSS) has received significant attention since it has a strong connection with evolutionary multi-objective 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 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 hypervolume contribution is very time-consuming. To efficiently solve HSS problems while maintaining a good solution quality, we propose a fast and scalable hypervolume subset selection method for many-objective optimization based on the determinantal point process (DPP), named DPP-HSS, which is fully free of hypervolume contribution calculation. Specifically, DPP-HSS constructs a hypervolume 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 hypervolume subset selection algorithm is implemented to solve this transformed problem. Extensive experiments show that the proposed DPP-HSS achieves significant speedup and good hypervolume 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.
Dynamic Detection of Relevant Objectives and Adaptation to Preference Drifts in Interactive Evolutionary Multi-Objective Optimization
https://arxiv.org/abs/2411.04547
Evolutionary Multi-Objective Optimization Algorithms (EMOAs) are widely employed to tackle problems with multiple conflicting objectives. Recent research indicates that not all objectives are equally important to the decision-maker (DM). In the context of interactive EMOAs, preference information elicited from the DM during the optimization process can be leveraged to identify and discard irrelevant objectives, a crucial step when objective evaluations are computationally expensive. However, much of the existing literature fails to account for the dynamic nature of DM preferences, which can evolve throughout the decision-making process and affect the relevance of objectives. This study addresses this limitation by simulating dynamic shifts in DM preferences within a ranking-based interactive algorithm. Additionally, we propose methods to discard outdated or conflicting preferences when such shifts occur. Building on prior research, we also introduce a mechanism to safeguard relevant objectives that may become trapped in local or global optima due to the diminished correlation with the DM-provided rankings. Our experimental results demonstrate that the proposed methods effectively manage evolving preferences and significantly enhance the quality and desirability of the solutions produced by the algorithm.
组合优化
A Surrogate Model for Quay Crane Scheduling Problem
https://arxiv.org/abs/2411.03324
In ports, a variety of tasks are carried out, and scheduling these tasks is crucial due to its significant impact on productivity, making the generation of precise plans essential. This study proposes a method to solve the Quay Crane Scheduling Problem (QCSP), a representative task scheduling problem in ports known to be NP-Hard, more quickly and accurately. First, the study suggests a method to create more accurate work plans for Quay Cranes (QCs) by learning from actual port data to accurately predict the working speed of QCs. Next, a Surrogate Model is proposed by combining a Machine Learning (ML) model with a Genetic Algorithm (GA), which is widely used to solve complex optimization problems, enabling faster and more precise exploration of solutions. Unlike methods that use fixed-dimensional chromosome encoding, the proposed methodology can provide solutions for encodings of various dimensions. To validate the performance of the newly proposed methodology, comparative experiments were conducted, demonstrating faster search speeds and improved fitness scores. The method proposed in this study can be applied not only to QCSP but also to various NP-Hard problems, and it opens up possibilities for the further development of advanced search algorithms by combining heuristic algorithms with ML models.
Metaheuristics for the Template Design Problem: Encoding, Symmetry and Hybridisation
https://arxiv.org/abs/2411.02842
The template design problem (TDP) is a hard combinatorial problem with a high number of symmetries which makes solving it more complicated. A number of techniques have been proposed in the literature to optimise its resolution, ranging from complete methods to stochastic ones. However, although metaheuristics are considered efficient methods that can find enough-quality solutions at a reasonable computational cost, these techniques have not proven to be truly efficient enough to deal with this problem. This paper explores and analyses a wide range of metaheuristics to tackle the problem with the aim of assessing their suitability for finding template designs. We tackle the problem using a wide set of metaheuristics whose implementation is guided by a number of issues such as problem formulation, solution encoding, the symmetrical nature of the problem, and distinct forms of hybridisation. For the TDP, we also propose a slot-based alternative problem formulation (distinct to other slot-based proposals), which represents another option other than the classical variation-based formulation of the problem. An empirical analysis, assessing the performance of all the metaheuristics (i.e., basic, integrative and collaborative algorithms working on different search spaces and with/without symmetry breaking) shows that some of our proposals can be considered the state-of-the-art when they are applied to specific problem instances.
Automated Placement of Analog Integrated Circuits using Priority-based Constructive Heuristic
https://arxiv.org/abs/2411.02406
This paper presents a heuristic approach for solving the placement of Analog and Mixed-Signal Integrated Circuits. Placement is a crucial step in the physical design of integrated circuits. During this step, designers choose the position and variant of each circuit device. We focus on the specific class of analog placement, which requires so-called pockets, their possible merging, and parametrizable minimum distances between devices, which are features mostly omitted in recent research and literature. We formulate the problem using Integer Linear Programming and propose a priority-based constructive heuristic inspired by algorithms for the Facility Layout Problem. Our solution minimizes the perimeter of the circuit's bounding box and the approximated wire length. Multiple variants of the devices with different dimensions are considered. Furthermore, we model constraints crucial for the placement problem, such as symmetry groups and blockage areas. Our outlined improvements make the heuristic suitable to handle complex rules of placement. With a search guided either by a Genetic Algorithm or a Covariance Matrix Adaptation Evolution Strategy, we show the quality of the proposed method on both synthetically generated and real-life industrial instances accompanied by manually created designs. Furthermore, we apply reinforcement learning to control the hyper-parameters of the genetic algorithm. Synthetic instances with more than 200 devices demonstrate that our method can tackle problems more complex than typical industry examples. We also compare our method with results achieved by contemporary state-of-the-art methods on the MCNC dataset, showing that our method is competitive and/or surpasses previous results.
Memetic collaborative approaches for finding balanced incomplete block designs
https://arxiv.org/abs/2411.02250
The balanced incomplete block design (BIBD) problem is a difficult combinatorial problem with a large number of symmetries, which add complexity to its resolution. In this paper, we propose a dual (integer) problem representation that serves as an alternative to the classical binary formulation of the problem. We attack this problem incrementally: firstly, we propose basic algorithms (i.e. local search techniques and genetic algorithms) intended to work separately on the two different search spaces (i.e. binary and integer); secondly, we propose two hybrid schemes: an integrative approach (i.e. a memetic algorithm) and a collaborative model in which the previous methods work in parallel, occasionally exchanging information. Three distinct two-dimensional structures are proposed as communication topology among the algorithms involved in the collaborative model, as well as a number of migration and acceptance criteria for sending and receiving data. An empirical analysis comparing a large number of instances of our schemes (with algorithms possibly working on different search spaces and with/without symmetry breaking methods) shows that some of these algorithms can be considered the state of the art of the metaheuristic methods applied to finding BIBDs. Moreover, our cooperative proposal is a general scheme from which distinct algorithmic variants can be instantiated to handle symmetrical optimisation problems. For this reason, we have also analysed its key parameters, thereby providing general guidelines for the design of efficient/robust cooperative algorithms devised from our proposal.
Deep memetic models for combinatorial optimization problems: application to the tool switching problem
https://arxiv.org/abs/2411.01922
Memetic algorithms are techniques that orchestrate the interplay between population-based and trajectory-based algorithmic components. In particular, some memetic models can be regarded under this broad interpretation as a group of autonomous basic optimization algorithms that interact among them in a cooperative way in order to deal with a specific optimization problem, aiming to obtain better results than the algorithms that constitute it separately. Going one step beyond this traditional view of cooperative optimization algorithms, this work tackles deep meta-cooperation, namely the use of cooperative optimization algorithms in which some components can in turn be cooperative methods themselves, thus exhibiting a deep algorithmic architecture. The objective of this paper is to demonstrate that such models can be considered as an efficient alternative to other traditional forms of cooperative algorithms. To validate this claim, different structural parameters, such as the communication topology between the agents, or the parameter that influences the depth of the cooperative effort (the depth of meta-cooperation), have been analyzed. To do this, a comparison with the state-of-the-art cooperative methods to solve a specific combinatorial problem, the Tool Switching Problem, has been performed. Results show that deep models are effective to solve this problem, outperforming metaheuristics proposed in the literature.
神经演化
Developing Convolutional Neural Networks using a Novel Lamarckian Co-Evolutionary Algorithm
https://arxiv.org/abs/2411.04658
According to the Strong Lottery Ticket Hypothesis, every sufficiently large neural network with randomly initialized weights contains a sub-network which - still with its random weights - already performs as well for a given task as the trained super-network. We present the first approach based on a genetic algorithm to find such strong lottery ticket sub-networks without training or otherwise computing any gradient. We show that, for smaller instances of binary classification tasks, our evolutionary approach even produces smaller and better-performing lottery ticket networks than the state-of-the-art approach using gradient information.
Harnessing the Power of Gradient-Based Simulations for Multi-Objective Optimization in Particle Accelerators
https://arxiv.org/abs/2411.04817
Particle accelerator operation requires simultaneous optimization of multiple objectives. Multi-Objective Optimization (MOO) is particularly challenging due to trade-offs between the objectives. Evolutionary algorithms, such as genetic algorithm (GA), have been leveraged for many optimization problems, however, they do not apply to complex control problems by design. This paper demonstrates the power of differentiability for solving MOO problems using a Deep Differentiable Reinforcement Learning (DDRL) algorithm in particle accelerators. We compare DDRL algorithm with Model Free Reinforcement Learning (MFRL), GA and Bayesian Optimization (BO) for simultaneous optimization of heat load and trip rates in the Continuous Electron Beam Accelerator Facility (CEBAF). The underlying problem enforces strict constraints on both individual states and actions as well as cumulative (global) constraint for energy requirements of the beam. A physics-based surrogate model based on real data is developed. This surrogate model is differentiable and allows back-propagation of gradients. The results are evaluated in the form of a Pareto-front for two objectives. We show that the DDRL outperforms MFRL, BO, and GA on high dimensional problems.
PropNEAT -- Efficient GPU-Compatible Backpropagation over NeuroEvolutionary Augmenting Topology Networks
https://arxiv.org/abs/2411.03726
We introduce PropNEAT, a fast backpropagation implementation of NEAT that uses a bidirectional mapping of the genome graph to a layer-based architecture that preserves the NEAT genomes whilst enabling efficient GPU backpropagation. We test PropNEAT on 58 binary classification datasets from the Penn Machine Learning Benchmarks database, comparing the performance against logistic regression, dense neural networks and random forests, as well as a densely retrained variant of the final PropNEAT model. PropNEAT had the second best overall performance, behind Random Forest, though the difference between the models was not statistically significant apart from between Random Forest in comparison with logistic regression and the PropNEAT retrain models. PropNEAT was substantially faster than a naive backpropagation method, and both were substantially faster and had better performance than the original NEAT implementation. We demonstrate that the per-epoch training time for PropNEAT scales linearly with network depth, and is efficient on GPU implementations for backpropagation. This implementation could be extended to support reinforcement learning or convolutional networks, and is able to find sparser and smaller networks with potential for applications in low-power contexts.
Machine Learning-Accelerated Multi-Objective Design of Fractured Geothermal Systems
https://arxiv.org/abs/2411.00504
Multi-objective optimization has burgeoned as a potent methodology for informed decision-making in enhanced geothermal systems, aiming to concurrently maximize economic yield, ensure enduring geothermal energy provision, and curtail carbon emissions. However, addressing a multitude of design parameters inherent in computationally intensive physics-driven simulations constitutes a formidable impediment for geothermal design optimization, as well as across a broad range of scientific and engineering domains. Here we report an Active Learning enhanced Evolutionary Multi-objective Optimization algorithm, integrated with hydrothermal simulations in fractured media, to enable efficient optimization of fractured geothermal systems using few model evaluations. We introduce probabilistic neural network as classifier to learns to predict the Pareto dominance relationship between candidate samples and reference samples, thereby facilitating the identification of promising but uncertain offspring solutions. We then use active learning strategy to conduct hypervolume based attention subspace search with surrogate model by iteratively infilling informative samples within local promising parameter subspace. We demonstrate its effectiveness by conducting extensive experimental tests of the integrated framework, including multi-objective benchmark functions, a fractured geothermal model and a large-scale enhanced geothermal system. Results demonstrate that the ALEMO approach achieves a remarkable reduction in required simulations, with a speed-up of 1-2 orders of magnitude (10-100 times faster) than traditional evolutionary methods, thereby enabling accelerated decision-making. Our method is poised to advance the state-of-the-art of renewable geothermal energy system and enable widespread application to accelerate the discovery of optimal designs for complex systems.
进化学习
Expanding Horizons of Level Diversity via Multi-objective Evolutionary Learning, IEEE TAI
https://ieeexplore.ieee.org/document/10742384
In recent years, the generation of diverse game levels has gained increasing interest, contributing to a richer and more engaging gaming experience. A number of level diversity metrics have been proposed in literature, which are naturally multi-dimensional, leading to conflicted, complementary, or both relationships among these dimensions. However, existing level generation approaches often fail to comprehensively assess diversity across those dimensions. This paper aims to expand horizons of level diversity by considering multi-dimensional diversity when training generative models. We formulate the model training as a multi-objective learning problem, where each diversity metric is treated as a distinct objective. Furthermore, a multi-objective evolutionary learning framework that optimises multiple diversity metrics simultaneously throughout the model training process is proposed. Our case study on the commonly used benchmark Super Mario Bros . demonstrates that our proposed framework can enhance multi-dimensional diversity and identify a Pareto front of generative models, which provides a range of tradeoffs among playability and two representative diversity metrics, including a content-based one and a player-centered one. Such capability enables decision-makers to make informed choices when selecting generators accommodating a variety of scenarios and the diverse needs of players and designers.
Evolved Hierarchical Masking for Self-Supervised Learning, IEEE TPAMI
https://ieeexplore.ieee.org/document/10742293
Existing Masked Image Modeling methods apply fixed mask patterns to guide the self-supervised training. As those mask patterns resort to different criteria to depict image contents, sticking to a fixed pattern leads to a limited vision cues modeling capability. This paper introduces an evolved hierarchical masking method to pursue general visual cues modeling in self-supervised learning. The proposed method leverages the vision model being trained to parse the input visual cues into a hierarchy structure, which is hence adopted to generate masks accordingly. The accuracy of hierarchy is on par with the capability of the model being trained, leading to evolved mask patterns at different training stages. Initially, generated masks focus on low-level visual cues to grasp basic textures, then gradually evolve to depict higher-level cues to reinforce the learning of more complicated object semantics and contexts. Our method does not require extra pre-trained models or annotations and ensures training efficiency by evolving the training difficulty. We conduct extensive experiments on seven downstream tasks including partial-duplicate image retrieval relying on low-level details, as well as image classification and semantic segmentation that require semantic parsing capability. Experimental results demonstrate that it substantially boosts performance across these tasks. For instance, it surpasses the recent MAE by 1.1% in imageNet-1K classification and 1.4% in ADE20K segmentation with the same training epochs. We also align the proposed method with the current research focus on LLMs. The proposed approach bridges the gap with large-scale pre-training on semantic demanding tasks and enhances intricate detail perception in tasks requiring low-level feature recognition.
应用研究
A Systematic Study on Solving Aerospace Problems Using Metaheuristics
https://arxiv.org/abs/2411.02574
Complex engineering problems can be modelled as optimisation problems. For instance, optimising engines, materials, components, structure, aerodynamics, navigation, control, logistics, and planning is essential in aerospace. Metaheuristics are applied to solve these optimisation problems. The present paper presents a systematic study on applying metaheuristics in aerospace based on the literature. Relevant scientific repositories were consulted, and a structured methodology was used to filter the papers. Articles published until March 2022 associating metaheuristics and aerospace applications were selected. The most used algorithms and the most relevant hybridizations were identified. This work also analyses the main types of problems addressed in the aerospace context and which classes of algorithms are most used in each problem.
