进化计算领域文章更新主要包括以下六大方向如下：
基础理论（包括遗传算法、进化策略、遗传编程、群智能等算法设计、理论研究、基准测试、进化思想、算法软件、综述等）
进化优化（包括黑盒优化、多目标优化、约束优化、噪声优化、多任务优化、多模态优化、迁移优化、大规模优化、昂贵优化、学习优化等）
组合优化（包括进化神经组合优化、进化机器人、路线规划、布局布线、工业控制、调度等）
神经进化（包含进化神经网络的参数、超参数、架构、规则等）
进化学习（包括进化特征选择、强化学习、多目标学习、公平性学习、联邦学习、进化计算机视觉、进化自然语言处理、进化数据挖掘等）
应用研究（工业、网络、安全、物理、生物、化学等）
文章来源主要包括：
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
基础理论
Self-Reproduction and Evolution in Cellular Automata: 25 Years After Evoloops, Artificial Life
https://direct.mit.edu/artl/article-abstract/doi/10.1162/artl_a_00451/124368/Self-Reproduction-and-Evolution-in-Cellular?redirectedFrom=fulltext
The year 2024 marks the 25th anniversary of the publication of evoloops, an evolutionary variant of Chris Langton’s self-reproducing loops, which proved constructively that Darwinian evolution of self-reproducing organisms by variation and natural selection is possible within deterministic cellular automata. Over the last few decades, this line of Artificial Life research has since undergone several important developments. Although it experienced a relative dormancy of activity for a while, the recent rise of interest in open-ended evolution and the success of continuous cellular automata models have brought researchers’ attention back to how to make spatiotemporal patterns self-reproduce and evolve within spatially distributed computational media. This article provides a review of the relevant literature on this topic over the past 25 years and highlights the major accomplishments made so far, the challenges being faced, and promising future research directions.
Runtime analysis of a coevolutionary algorithm on impartial combinatorial games
https://arxiv.org/abs/2409.04177
Due to their complex dynamics, combinatorial games are a key test case and application for algorithms that train game playing agents. Among those algorithms that train using self-play are coevolutionary algorithms (CoEAs). CoEAs evolve a population of individuals by iteratively selecting the strongest based on their interactions against contemporaries, and using those selected as parents for the following generation (via randomised mutation and crossover). However, the successful application of CoEAs for game playing is difficult due to pathological behaviours such as cycling, an issue especially critical for games with intransitive payoff landscapes. Insight into how to design CoEAs to avoid such behaviours can be provided by runtime analysis. In this paper, we push the scope of runtime analysis to combinatorial games, proving a general upper bound for the number of simulated games needed for UMDA (a type of CoEA) to discover (with high probability) an optimal strategy for an impartial combinatorial game. This result applies to any impartial combinatorial game, and for many games the implied bound is polynomial or quasipolynomial as a function of the number of game positions. After proving the main result, we provide several applications to simple well-known games: Nim, Chomp, Silver Dollar, and Turning Turtles. As the first runtime analysis for CoEAs on combinatorial games, this result is a critical step towards a comprehensive theoretical framework for coevolution.
进化优化
A Diversity-Enhanced Tri-Stage Framework for Constrained Multi-objective Optimization, IEEE TEVC
https://ieeexplore.ieee.org/document/10680148
Achieving a trade-off 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 pre-selection 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.
Transfer Task-Averaged Natural Gradient for Efficient Many-Task Optimization, IEEE TEVC
https://ieeexplore.ieee.org/document/10680050
With the increasing requirement for computational efficiency in evolutionary algorithms 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 evolutionary algorithms becomes indispensable. In this paper, we present a task-averaged natural gradient-assisted natural evolution strategy (TNG-NES) to deal with MaTO efficiently. The task-averaged natural gradient 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 task-averaged natural gradient 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.
Finding ϵ-Locally Optimal Solutions for Multi-Objective Multimodal Optimization, IEEE TEVC
https://ieeexplore.ieee.org/document/10677365
In this paper, we address the problem of computing all locally optimal solutions of a given multi-objective problem whose images are sufficiently close to the Pareto front. Such -locally optimal solutions are particularly interesting in the context of multi-objective multimodal optimization (MMO). To accomplish this task, we first define a new set of interest, LQ, that is strongly related to the recently proposed set of -acceptable solutions. Next, we propose a new unbounded archiver, ArchiveUpdateLQ, aiming to capture LQ,in the limit. This archiver can in principle be used in combination with any multi-objective evolutionary algorithm (MOEA). Further, we equip numerous MOEAs with ArchiveUpdateLQ, 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 p. Additionally, we propose and use a new performance indicator, IEDR, which results in comparable performances but which is applicable to problems defined in higher dimensions (in particular in decision variable space).
Micro Many-Objective Evolutionary Algorithm With Knowledge Transfer, IEEE TETCI
https://ieeexplore.ieee.org/document/10670082
Computational effectiveness and limited resources in evolutionary algorithms are interdependently handled during the working of low-power microprocessors for real-world problems, particularly in many-objective evolutionary algorithms (MaOEAs). In this respect, the balance between them will be broken by evolutionary algorithms with a normal-sized population, but which doesn't include a micro population. To tackle this issue, this paper proposes a micro many-objective evolutionary algorithm with knowledge transfer ( μ MaOEA). To address the oversight that knowledge is often not considered enough between niches, the knowledge-transfer strategy is proposed to bolster each unoptimized niche through optimizing adjacent niches, which enables niches to generate better individuals. Meanwhile, a two-stage mechanism based on fuzzy logic is designed to settle the conflict between convergence and diversity in many-objective optimization problems. Through efficient fuzzy logic decision-making, the mechanism maintains different properties of the population at different stages. Different MaOEAs and micro multi-objective evolutionary algorithms were compared on benchmark test problems DTLZ, MaF, and WFG, and the results showed that μ MaOEA has an excellent performance. In addition, it also conducted simulation on two real-world problems, MPDMP and MLDMP, based on a low-power microprocessor. The results indicated the applicability of μ MaOEA for low-power microprocessor optimization.
Multiselection-Based Differential Evolution, IEEE TSMC
https://ieeexplore.ieee.org/document/10677453
Differential evolution (DE) has been developed as a state-of-the-art population-based stochastic optimizer for continuous nonconvex search space in recent decades. It uses difference vectors among individuals to adaptively control the balance between exploration and exploitation for achieving an excellent search performance. Specifically, one-to-one selection in DE guarantees that difference vectors vary from large for exploration to small for exploitation. However, the selection may generate inappropriate scale of difference vectors, which causes insufficient exploitation when facing complex problems with, e.g., multimodal with a huge number of local optima or plain regions. In this article, we propose a multiselection-based DE (MSDE) to address such limitation. Specifically, three different types of selection strategies are adopted to deal with the different situation during a search process. The proposed MSDE is evaluated on the 2013, 2014, and 2017 IEEE congress on evolutionary computation real parameter optimization competitions. Experimental results demonstrate that the proposed MSDE significantly outperforms the winners of those competitions. We further show that, when integrating the proposed multiselection-based strategy with the original DE or other advanced DE variants, it can also improve their search performance on most of test cases. This work makes a significant contribution to advance the state of the art in the area of population-based stochastic optimizers.
组合优化
A Memetic Algorithm for Vehicle Routing with Simultaneous Pickup and Delivery and Time Windows, IEEE TEVC
https://ieeexplore.ieee.org/document/10669598
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.
Transforming Combinatorial Optimization Problems in Fourier Space: Consequences and Uses, IEEE TEVC
https://ieeexplore.ieee.org/document/10673981
We analyze three permutation-based combinatorial optimization problems in Fourier space, namely, the Quadratic Assignment Problem, the Linear Ordering Problem and the symmetric and non-symmetric Traveling Salesperson Problem. 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 Linear Ordering Problem and the symmetric and non-symmetric Traveling Salesperson Problem 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 Linear Ordering Problem and the symmetric and non-symmetric Traveling Salesperson Problem, 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 non-zero parameters.
Multi-objective Dynamic Flexible Job Shop Scheduling with Biased Objectives via Multitask Genetic Programming, IEEE TAI
https://ieeexplore.ieee.org/document/10669769
Dynamic flexible job shop scheduling is an important combinatorial optimisation problem which has rich real-world applications such as product processing in manufacturing. Genetic programming has been successfully used to learn scheduling heuristics for dynamic flexible job shop scheduling. Intuitively, users prefer small and effective scheduling heuristics that can not only generate promising schedules but also are computationally efficient and easy to be understood. However, a scheduling heuristic with better effectiveness tends to have a larger size, and the effectiveness of rules and rule size are potentially conflicting objectives. With the traditional dominance relation based multi-objective algorithms, there is a search bias towards rule size, since rule size is much easier to be optimised than effectiveness and larger rules are easily abandoned, resulting in the loss of effectiveness. To address this issue, this paper develops a novel multi-objective genetic programming algorithm that takes size and effectiveness of scheduling heuristics for optimisation via multitask learning mechanism. Specifically, we construct two tasks for the multi-objective optimisation with biased objectives using different search mechanisms for each task. The focus of the proposed algorithm is to improve the effectiveness of learned small rules by knowledge sharing between constructed tasks which is implemented with the crossover operator. The results show that our proposed algorithm performs significantly better, i.e., with smaller and more effective scheduling heuristics, than the state-of-the-art algorithms in the examined scenarios. By analysing the population diversity, we find that the proposed algorithm has a good balance between exploration and exploitation during the evolutionary process.
Adaptive Ant Colony Optimization Algorithm Based on Real-Time Logistics Features for Instant Delivery, IEEE TCYB
https://ieeexplore.ieee.org/document/10679189
Ant colony optimization (ACO) algorithm is widely used in the instant delivery order scheduling because of its distributed computing capability. However, the order delivery efficiency decreases when different logistics statuses are faced. In order to improve the performance of ACO, an adaptive ACO algorithm based on real-time logistics features (AACO-RTLFs) is proposed. First, features are extracted from the event dimension, spatial dimension, and time dimension of the instant delivery to describe the real-time logistics status. Five key factors are further selected from the above three features to assist in problem modeling and ACO designing. Second, an adaptive instant delivery model is built considering the customer’s acceptable delivery time. The acceptable time is calculated by emergency order mark and weather conditions in the event dimension feature. Third, an adaptive ACO algorithm is proposed to obtain the instant delivery order schedules. The parameters of the probability equation in ACO are adjusted according to the extracted key factors. Finally, the Gurobi solver in Python is used to perform numerical experiments on the classical datasets to verify the effectiveness of the instant delivery model. The proposed AACO-RTLF algorithm shows its advantages in instant delivery order scheduling when compared to the other state-of-the-art algorithms.
进化学习
Automatically Evolving Interpretable Feature Vectors Using Genetic Programming for an Ensemble Classifier in Skin Cancer Detection, IEEE CIM
https://ieeexplore.ieee.org/document/10595537
Early skin cancer diagnosis saves lives as the disease can be successfully treated through complete excision. Computer-aided diagnosis methods are developed using artificial intelligence techniques to help earlier detection and identify hidden causes leading to cancers in skin lesion images. In skin cancer image classification problems, an ensemble of classifiers has demonstrated better classification ability than a single classification algorithm. Traditionally, training an ensemble uses the complete set of original features, where some of these features can be redundant or irrelevant and hence, may not provide useful information in generating good models for ensemble classification. Moreover, newly created features may help improve classification performance. To address this issue, the existing methods have used feature construction for building an ensemble classifier, which usually creates a fixed number of features that may fit the training data too well, resulting in poor test performance. This study develops a novel classification approach that combines ensemble learning, feature selection, and feature construction utilizing genetic programming (GP) to handle the above limitations. The proposed method automatically evolves variable-length feature vectors consisting of GP-selected and GP-constructed features suitable for training an ensemble classifier. This study evaluates the effectiveness of the proposed method on two benchmark real-world skin image datasets that include dermoscopy and standard camera images. The experimental results reveal that the proposed algorithm significantly outperforms four state-of-the-art convolutional neural network methods, the existing GP approaches, and 11 commonly used machine learning methods. Furthermore, this study also includes interpreting evolved individuals that highlight important skin cancer characteristics playing a vital role in discriminating images of different cancer classes. This study shows that high classification performance can be achieved at a low cost of computational resources and inference time, and accordingly, this method is potentially suitable to be implemented in mobile devices for the automated screening of skin lesions and many other malignancies in low-resource settings.
An Automated and Interpretable Computer-Aided Approach for Skin Cancer Diagnosis Using Genetic Programming, IEEE TEVC
https://ieeexplore.ieee.org/document/10679181
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 paper, 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.
SENGraph: A Self-Learning Evolutionary and Node-Aware Graph Network for Soft Sensing in Industrial Processes, IEEE TNNLS
https://ieeexplore.ieee.org/document/10680054
The last decade has witnessed the growing prevalence of deep models on soft sensing in industrial processes. However, most of the existing soft sensing models are developed to learn from regular data in the Euclidean space, ignoring the complex coupling relations among process variables. On the other hand, graph networks are gaining attraction in handling non-Euclidean relations in industrial data. However, the existing graph networks on soft sensing models still suffer from two major issues: 1) how to capture the intervariable structural relations and intravariable temporal dependencies from dynamic and strongly coupled industrial data and 2) how to learn from nodes with distinctive importance for the soft sensing task. To address these problems, we propose a self-learning evolutionary and node-aware graph network (SENGraph) for industrial soft sensing. We first develop a self-learning graph generation (SLG) module to combine the coarse-and fine-grained graphs to capture the global trend and local dynamics from process data. Then, we build a self-evolutionary graph module (EGM) to obtain diversified node features from the entire graph using mutation and crossover strategies. Finally, we design a node-aware module (NAM) to highlight the informative nodes and suppress the less significant ones to further improve the discriminative ability of the downstream soft sensing. Extensive experimental results and analysis on four real-world industrial datasets demonstrate that our proposed SENGraph model outperforms the existing state-of-the-art (SOTA) soft sensing methods.
A Space Transformation-Based Multiform Approach for Multiobjective Feature Selection in High-Dimensional Classification, IEEE TSMC
https://ieeexplore.ieee.org/document/10672540
Improving classification performance and reducing the number of selected features are two conflicting objectives of feature selection, which can be well solved by multiobjective algorithms. However, as the dimensionality of the data increases, the search space for feature selection will grow exponentially, which leads to high-computational costs. Additionally, the complex interaction among features makes the population prone to falling into local optimal. To address these issues, feature grouping can treat one dimension as a group of features instead of one feature, effectively transforming the high-dimensional search space into a lower-dimensional one. Since different grouping forms can be converted into different feature combination spaces, the search directions of the population also vary. Inspired by this, a multiform optimization approach based on space transformation (MOFS-MST) is proposed in this article. Specifically, two different grouping forms are set based on the ranking of features in different evaluation criteria to construct a multiform framework, thereby increasing the diversity of the population. During the evolutionary process, a knowledge transfer strategy based on feature groups is executed between the two forms of grouping in order to help each other escape local optima. Moreover, it can dynamically adjust the state of feature grouping to enhance the potential for feature interaction. Experimental results demonstrate that this method outperforms six other state-of-the-art multiobjective high-dimensional feature selection methods on 12 high-dimensional datasets.
Advancing Automated Knowledge Transfer in Evolutionary Multitasking via Large Language Models
https://arxiv.org/abs/2409.04270
Evolutionary Multi-task Optimization (EMTO) is a paradigm that leverages knowledge transfer across simultaneously optimized tasks for enhanced search performance. To facilitate EMTO's performance, various knowledge transfer models have been developed for specific optimization tasks. However, designing these models often requires substantial expert knowledge. Recently, large language models (LLMs) have achieved remarkable success in autonomous programming, aiming to produce effective solvers for specific problems. In this work, a LLM-based optimization paradigm is introduced to establish an autonomous model factory for generating knowledge transfer models, ensuring effective and efficient knowledge transfer across various optimization tasks. To evaluate the performance of the proposed method, we conducted comprehensive empirical studies comparing the knowledge transfer model generated by the LLM with existing state-of-the-art knowledge transfer methods. The results demonstrate that the generated model is able to achieve superior or competitive performance against hand-crafted knowledge transfer models in terms of both efficiency and effectiveness.
应用研究
Evolutionary Retrosynthetic Route Planning [Research Frontier], IEEE CIM
https://ieeexplore.ieee.org/document/10595522
Molecular retrosynthesis is a significant and complex problem in the field of chemistry, however, traditional manual synthesis methods not only need well-trained experts but also are time-consuming. With the development of Big Data and machine learning, artificial intelligence (AI) based retrosynthesis is attracting more attention and has become a valuable tool for molecular retrosynthesis. At present, Monte Carlo tree search is a mainstream search framework employed to address this problem. Nevertheless, its search efficiency is compromised by its large search space. Therefore, this paper proposes a novel approach for retrosynthetic route planning based on evolutionary optimization, marking the first use of Evolutionary Algorithm (EA) in the field of multi-step retrosynthesis. The proposed method involves modeling the retrosynthetic problem into an optimization problem, defining the search space and operators. Additionally, to improve the search efficiency, a parallel strategy is implemented. The new approach is applied to four case products and compared with Monte Carlo tree search. The experimental results show that, in comparison to the Monte Carlo tree search algorithm, EA significantly reduces the number of calling single-step model by an average of 53.9%. The time required to search three solutions decreases by an average of 83.9%, and the number of feasible search routes increases by 1.38 times. The source code is available at https://github.com/ilog-ecnu/EvoRRP.
Surrogate-Assisted Differential Evolution for Wave Energy Converters Optimization, IEEE TETCI
https://ieeexplore.ieee.org/document/10670088
In the aftermath of the successes in wind and solar energy, wave energy has emerged as an exceptionally promising renewable resource. A pivotal aspect of wave energy development involves optimizing the placement of energy converters in constrained sea areas to achieve maximum output. However, the hydrodynamic interactions among buoys in wave energy arrays pose a formidable challenge, making power assessment modeling both expensive and intricate. This study introduces a surrogate-assisted chaotic differential evolution (SDE) algorithm to address this challenge. The proposed methodology replaces computationally demanding evaluations with trained neural network models. Significantly, in contrast to prior surrogate models, we employ a selection of elite individuals to guide the evolutionary algorithm's search direction through confidence ranking. We curated eight datasets from four real wave scenarios (Perth, Adelaide, Tasmania, and Sydney) with two buoy configurations (4 and 16 buoys). Subsequently, we trained five state-of-the-art deep network models and two numerical regression models to identify the optimal model. Experimental results demonstrate that SDE exhibits superior energy output and computational efficiency compared to the other four intelligent algorithms when optimizing the locations of a highly challenging 16-buoy wave energy converter array in authentic wave environments.
Learning the Graph Structure of Regular Vine-Copulas from Dependence Lists, ACM TELO
https://dl.acm.org/doi/10.1145/3695467
Regular vine copulas (R-vines) provide a comprehensive framework for modeling high-dimensional dependencies using a hierarchy of trees and conditional pair-copulas. While the graphical structure of R-vines is traditionally derived from data, this work introduces a novel approach by utilizing a (conditional) pairwise dependence list. Our primary goal is to construct R-vine graphs that include the maximum possible number of dependence relationships specified in such lists. To tackle this optimization challenge, characterized by exponential growth in the search space and the structural constraints of R-vines, we propose two distinct methodologies: A 0-1 linear programming formulation and a Genetic Algorithm (GA). Additionally, the Randomized Constructive Technique (RCT) is employed to generate the initial population of the GA, serving as a baseline for our comparison. Experimental results reveal the superior performance of the GA over the RCT in terms of success rate, incorporating more relationships than RCT into the constructed R-vine graphs and achieving near-optimal or optimal graph structures.
