进化计算领域文章更新主要包括以下六大方向如下：
基础理论（包括遗传算法、进化策略、遗传编程、群智能等算法设计、理论研究、基准测试、进化思想、算法软件、综述等）
进化优化（包括黑盒优化、多目标优化、约束优化、噪声优化、多任务优化、多模态优化、迁移优化、大规模优化、昂贵优化、学习优化等）
组合优化（包括进化神经组合优化、进化机器人、路线规划、布局布线、工业控制、调度等）
神经进化（包含进化神经网络的参数、超参数、架构、规则等）
进化学习（包括进化特征选择、强化学习、多目标学习、公平性学习、联邦学习、进化计算机视觉、进化自然语言处理、进化数据挖掘等）
应用研究（工业、网络、安全、物理、生物、化学等）
文章来源主要包括：
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
基础理论
Explainable Optimisation through Online and Offline Hyper-heuristics, ACM TELO
https://dl.acm.org/doi/10.1145/3701236
Research in the explainability of optimisation techniques has largely focused on metaheuristics and their movement of solutions around the search landscape. Hyper-heuristics create a different challenge for explainability as they make use of many more operators, or low-level heuristics and learning algorithms which modify their probability of selection online. This paper describes a set of methods for explaining hyper-heuristics decisions in both online and offline scenarios using selection hyper-heuristics as an example. These methods help to explain various aspects of the function of hyper-heuristics both at a particular juncture in the optimisation process and through time. Visualisations of each method acting on sequences provide an understanding of which operators are being utilised and when, and in which combinations to produce a greater understanding of the algorithm-problem nexus in hyper-heuristic search. These methods are demonstrated on a range of problems including those in operational research and water distribution network optimisation. They demonstrate the insight that can be generated from optimisation using selection hyper-heuristics, including building an understanding of heuristic usage, useful combinations of heuristics and heuristic parameterisations. Furthermore the dynamics of heuristic utility are explored throughout an optimisation run and we show that it is possible to cluster problem instances according to heuristic selection alone, providing insight into the perception of problems from a hyper-heuristic perspective.
Genetic Motifs as a Blueprint for Mismatch-Tolerant Neuromorphic Computing
https://arxiv.org/abs/2410.19403
Mixed-signal implementations of SNNs offer a promising solution to edge computing applications that require low-power and compact embedded processing systems. However, device mismatch in the analog circuits of these neuromorphic processors poses a significant challenge to the deployment of robust processing in these systems. Here we introduce a novel architectural solution inspired by biological development to address this issue. Specifically we propose to implement architectures that incorporate network motifs found in developed brains through a differentiable re-parameterization of weight matrices based on gene expression patterns and genetic rules. Thanks to the gradient descent optimization compatibility of the method proposed, we can apply the robustness of biological neural development to neuromorphic computing. To validate this approach we benchmark it using the Yin-Yang classification dataset, and compare its performance with that of standard multilayer perceptrons trained with state-of-the-art hardware-aware training method. Our results demonstrate that the proposed method mitigates mismatch-induced noise without requiring precise device mismatch measurements, effectively outperforming alternative hardware-aware techniques proposed in the literature, and providing a more general solution for improving the robustness of SNNs in neuromorphic hardware.
进化优化
An Efficient Dynamic Resource Allocation Framework for Evolutionary Bilevel Optimization
https://arxiv.org/abs/2410.24081
Bilevel optimization problems are characterized by an interactive hierarchical structure, where the upper level seeks to optimize its strategy while simultaneously considering the response of the lower level. Evolutionary algorithms are commonly used to solve complex bilevel problems in practical scenarios, but they face significant resource consumption challenges due to the nested structure imposed by the implicit lower-level optimality condition. This challenge becomes even more pronounced as problem dimensions increase. Although recent methods have enhanced bilevel convergence through task-level knowledge sharing, further efficiency improvements are still hindered by redundant lower-level iterations that consume excessive resources while generating unpromising solutions. To overcome this challenge, this paper proposes an efficient dynamic resource allocation framework for evolutionary bilevel optimization, named DRC-BLEA. Compared to existing approaches, DRC-BLEA introduces a novel competitive quasi-parallel paradigm, in which multiple lower-level optimization tasks, derived from different upper-level individuals, compete for resources. A continuously updated selection probability is used to prioritize execution opportunities to promising tasks. Additionally, a cooperation mechanism is integrated within the competitive framework to further enhance efficiency and prevent premature convergence. Experimental results compared with chosen state-of-the-art algorithms demonstrate the effectiveness of the proposed method. Specifically, DRC-BLEA achieves competitive accuracy across diverse problem sets and real-world scenarios, while significantly reducing the number of function evaluations and overall running time.
Non-Dominated Sorting Bidirectional Differential Coevolution
https://arxiv.org/abs/2410.19439
Constrained multiobjective optimization problems (CMOPs) are commonly found in real-world applications. CMOP is a complex problem that needs to satisfy a set of equality or inequality constraints. This paper proposes a variant of the bidirectional coevolution algorithm (BiCo) with differential evolution (DE). The novelties in the model include the DE differential mutation and crossover operators as the main search engine and a non-dominated sorting selection scheme. Experimental results on two benchmark test suites and eight real-world CMOPs suggested that the proposed model reached better overall performance than the original model.
An Inverse Modeling Constrained Multi-Objective Evolutionary Algorithm Based on Decomposition
https://arxiv.org/abs/2410.19203
This paper introduces the inverse modeling constrained multi-objective evolutionary algorithm based on decomposition (IM-C-MOEA/D) for addressing constrained real-world optimization problems. Our research builds upon the advancements made in evolutionary computing-based inverse modeling, and it strategically bridges the gaps in applying inverse models based on decomposition to problem domains with constraints. The proposed approach is experimentally evaluated on diverse real-world problems (RWMOP1-35), showing superior performance to state-of-the-art constrained multi-objective evolutionary algorithms (CMOEAs). The experimental results highlight the robustness of the algorithm and its applicability in real-world constrained optimization scenarios.
组合优化
Pareto Optimization for Fair Subset Selection: A Case Study on Personalized Recommendation, IEEE TEVC
https://ieeexplore.ieee.org/document/10737706
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. Firstly, 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 paper, 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{α/l(1-e-γ),γ/k,1-e-rk/k in polynomial time when l
Rethinking Supervised Learning based Neural Combinatorial Optimization for Routing Problem, ACM TELO
https://dl.acm.org/doi/10.1145/3694690
Neural combinatorial optimization (NCO) is a promising learning-based approach to solving complex combinatorial optimization problems such as the traveling salesman problem (TSP), the vehicle routing problem (VRP), and the orienteering problem (OP). However, how to efficiently train a powerful NCO solver for routing problems remains a crucial challenge. The widely used reinforcement learning method suffers from sparse rewards and low data efficiency, while the supervised learning approach requires a large number of high-quality solutions (i.e., labels) that could be costly to obtain. In this work, we find that simple data augmentation operations can drastically reduce the number of required high-quality solutions for supervised learning. Moreover, simple boosting strategies that leverage the property of multiple optima can significantly improve training efficiency. With only a small set of labeled instances, supervised learning can achieve a competitive in-distribution performance with the widely-used reinforcement learning counterpart. Furthermore, we also investigate the generalization ability for larger out-of-distribution problems. We believe the findings from this work may lead to a rethinking of the value of data-efficient supervised learning for NCO solver training.
A Flexible Job Shop Scheduling Problem Involving Reconfigurable Machine Tools Under Industry 5.0
https://arxiv.org/abs/2410.23302
The rise of Industry 5.0 has introduced new demands for manufacturing companies, requiring a shift in how production schedules are managed to address human centered, environmental, and economic goals comprehensively. The flexible job shop scheduling problem (FJSSP), which involves processing operations on various capable machines, accurately reflects the complexities of modern manufacturing settings. This paper investigates the FJSSP involving reconfigurable machine tools with configuration dependent setup times, while integrating human aspects like worker assignments, moving time, and rest periods, as well as minimizing total energy consumption. A mixed-integer programming (MIP) model is developed to simultaneously optimize these objectives. The model determines the assignment of operations to machines, workers, and configurations while sequencing operations, scheduling worker movements, and respecting rest periods, and minimizing overall energy consumption. Given the NPhard nature of the FJSSP with worker assignments and reconfigurable tools, a memetic algorithm (MA) is proposed. This metaheuristic evolutionary algorithm features a three layer chromosome encoding method, specialized crossover and mutation strategies, and neighborhood search mechanisms to enhance solution quality and diversity. Comparisons of MA with MIP and genetic algorithms (GA) on benchmark instances demonstrate the MA efficiency and effectiveness, particularly for larger problem instances where MIP becomes impractical. This research paves the way for sustainable and resilient production schedules tailored for the factory of the future under the Industry 5.0 paradigm. The work bridges a crucial gap in current literature by integrating worker and environmental impact into the FJSSP with reconfigurable machine models.
Automatic programming via large language models with population self-evolution for dynamic job shop scheduling problem
https://arxiv.org/abs/2410.22657
Heuristic dispatching rules (HDRs) are widely regarded as effective methods for solving dynamic job shop scheduling problems (DJSSP) in real-world production environments. However, their performance is highly scenario-dependent, often requiring expert customization. To address this, genetic programming (GP) and gene expression programming (GEP) have been extensively used for automatic algorithm design. Nevertheless, these approaches often face challenges due to high randomness in the search process and limited generalization ability, hindering the application of trained dispatching rules to new scenarios or dynamic environments. Recently, the integration of large language models (LLMs) with evolutionary algorithms has opened new avenues for prompt engineering and automatic algorithm design. To enhance the capabilities of LLMs in automatic HDRs design, this paper proposes a novel population self-evolutionary (SeEvo) method, a general search framework inspired by the self-reflective design strategies of human experts. The SeEvo method accelerates the search process and enhances exploration capabilities. Experimental results show that the proposed SeEvo method outperforms GP, GEP, end-to-end deep reinforcement learning methods, and more than 10 common HDRs from the literature, particularly in unseen and dynamic scenarios.
High-level hybridization of heuristics and metaheuristics to solve symmetric TSP: a comparative study
https://arxiv.org/abs/2410.21274
The Travelling Salesman Problem - TSP is one of the most explored problems in the scientific literature to solve real problems regarding the economy, transportation, and logistics, to cite a few cases. Adapting TSP to solve different problems has originated several variants of the optimization problem with more complex objectives and different restrictions. Metaheuristics have been used to solve the problem in polynomial time. Several studies have tried hybridising metaheuristics with specialised heuristics to improve the quality of the solutions. However, we have found no study to evaluate whether the searching mechanism of a particular metaheuristic is more adequate for exploring hybridization. This paper focuses on the solution of the classical TSP using high-level hybridisations, experimenting with eight metaheuristics and heuristics derived from k-OPT, SISR, and segment intersection search, resulting in twenty-four combinations. Some combinations allow more than one set of searching parameters. Problems with 50 to 280 cities are solved. Parameter tuning of the metaheuristics is not carried out, exploiting the different searching patterns of the eight metaheuristics instead. The solutions' quality is compared to those presented in the literature.
Hybrid Memetic Search for Electric Vehicle Routing with Time Windows, Simultaneous Pickup-Delivery, and Partial Recharges
https://arxiv.org/abs/2410.19580
With growing environmental concerns, electric vehicles for logistics have gained significant attention within the computational intelligence community in recent years. This work addresses an emerging and significant extension of the electric vehicle routing problem (EVRP), namely EVRP with time windows, simultaneous pickup-delivery, and partial recharges (EVRP-TW-SPD), which has wide real-world applications. We propose a hybrid memetic algorithm (HMA) for solving EVRP-TW-SPD. HMA incorporates two novel components: a parallel-sequential station insertion procedure for handling partial recharges that can better avoid local optima compared to purely sequential insertion, and a cross-domain neighborhood search that explores solution spaces of both electric and non-electric problem domains simultaneously. These components can also be easily applied to various EVRP variants. To bridge the gap between existing benchmarks and real-world scenarios, we introduce a new, large-scale EVRP-TW-SPD benchmark set derived from real-world applications, containing instances with many more customers and charging stations than existing benchmark instances. Extensive experiments demonstrate the significant performance advantages of HMA over existing algorithms across a wide range of problem instances. Both the benchmark set and HMA will be open-sourced to facilitate further research in this area.
神经演化
Developing Convolutional Neural Networks using a Novel Lamarckian Co-Evolutionary Algorithm
https://arxiv.org/abs/2410.22487
Neural Architecture Search (NAS) methods autonomously discover high-accuracy neural network architectures, outperforming manually crafted ones. However, The NAS methods require high computational costs due to the high dimension search space and the need to train multiple candidate solutions. This paper introduces LCoDeepNEAT, an instantiation of Lamarckian genetic algorithms, which extends the foundational principles of the CoDeepNEAT framework. LCoDeepNEAT co-evolves CNN architectures and their respective final layer weights. The evaluation process of LCoDeepNEAT entails a single epoch of SGD, followed by the transference of the acquired final layer weights to the genetic representation of the network. In addition, it expedites the process of evolving by imposing restrictions on the architecture search space, specifically targeting architectures comprising just two fully connected layers for classification. Our method yields a notable improvement in the classification accuracy of candidate solutions throughout the evolutionary process, ranging from 2% to 5.6%. This outcome underscores the efficacy and effectiveness of integrating gradient information and evolving the last layer of candidate solutions within LCoDeepNEAT. LCoDeepNEAT is assessed across six standard image classification datasets and benchmarked against eight leading NAS methods. Results demonstrate LCoDeepNEAT's ability to swiftly discover competitive CNN architectures with fewer parameters, conserving computational resources, and achieving superior classification accuracy compared to other approaches.
Survival of the Fittest: Evolutionary Adaptation of Policies for Environmental Shifts
https://arxiv.org/abs/2410.19852
Reinforcement learning (RL) has been successfully applied to solve the problem of finding obstacle-free paths for autonomous agents operating in stochastic and uncertain environments. However, when the underlying stochastic dynamics of the environment experiences drastic distribution shifts, the optimal policy obtained in the trained environment may be sub-optimal or may entirely fail in helping find goal-reaching paths for the agent. Approaches like domain randomization and robust RL can provide robust policies, but typically assume minor (bounded) distribution shifts. For substantial distribution shifts, retraining (either with a warm-start policy or from scratch) is an alternative approach. In this paper, we develop a novel approach called {\em Evolutionary Robust Policy Optimization} (ERPO), an adaptive re-training algorithm inspired by evolutionary game theory (EGT). ERPO learns an optimal policy for the shifted environment iteratively using a temperature parameter that controls the trade off between exploration and adherence to the old optimal policy. The policy update itself is an instantiation of the replicator dynamics used in EGT. We show that under fairly common sparsity assumptions on rewards in such environments, ERPO converges to the optimal policy in the shifted environment. We empirically demonstrate that for path finding tasks in a number of environments, ERPO outperforms several popular RL and deep RL algorithms (PPO, A3C, DQN) in many scenarios and popular environments. This includes scenarios where the RL algorithms are allowed to train from scratch in the new environment, when they are retrained on the new environment, or when they are used in conjunction with domain randomization. ERPO shows faster policy adaptation, higher average rewards, and reduced computational costs in policy adaptation.
Optimizing Hearthstone Agents using an Evolutionary Algorithm
https://arxiv.org/abs/2410.19681
Digital collectible card games are not only a growing part of the video game industry, but also an interesting research area for the field of computational intelligence. This game genre allows researchers to deal with hidden information, uncertainty and planning, among other aspects. This paper proposes the use of evolutionary algorithms (EAs) to develop agents who play a card game, Hearthstone, by optimizing a data-driven decision-making mechanism that takes into account all the elements currently in play. Agents feature self-learning by means of a competitive coevolutionary training approach, whereby no external sparring element defined by the user is required for the optimization process. One of the agents developed through the proposed approach was runner-up (best 6%) in an international Hearthstone Artificial Intelligence (AI) competition. Our proposal performed remarkably well, even when it faced state-of-the-art techniques that attempted to take into account future game states, such as Monte-Carlo Tree search. This outcome shows how evolutionary computation could represent a considerable advantage in developing AIs for collectible card games such as Hearthstone.
Evolving choice hysteresis in reinforcement learning: comparing the adaptive value of positivity bias and gradual perseveration
https://arxiv.org/abs/2410.19434
The tendency of repeating past choices more often than expected from the history of outcomes has been repeatedly empirically observed in reinforcement learning experiments. It can be explained by at least two computational processes: asymmetric update and (gradual) choice perseveration. A recent meta-analysis showed that both mechanisms are detectable in human reinforcement learning. However, while their descriptive value seems to be well established, they have not been compared regarding their possible adaptive value. In this study, we address this gap by simulating reinforcement learning agents in a variety of environments with a new variant of an evolutionary algorithm. Our results show that positivity bias (in the form of asymmetric update) is evolutionary stable in many situations, while the emergence of gradual perseveration is less systematic and robust. Overall, our results illustrate that biases can be adaptive and selected by evolution, in an environment-specific manner.
进化学习
Representation Learning Based on Co-Evolutionary Combined With Probability Distribution Optimization for Precise Defect Location, IEEE TNNLS
https://ieeexplore.ieee.org/document/10736981
Visual defect detection methods based on representation learning play an important role in industrial scenarios. Defect detection technology based on representation learning has made significant progress. However, existing defect detection methods still face three challenges: first, the extreme scarcity of industrial defect samples makes training difficult. Second, due to the characteristics of industrial defects, such as blur and background interference, it is challenging to obtain fuzzy defect separation edges and context information. Third, industrial defects cannot obtain accurate positioning information. This article proposes feature co-evolution interaction architecture (CIA) and glass container defect dataset to address the above challenges. Specifically, the contributions of this article are as follows: first, this article designs a glass container image acquisition system that combines RGB and polarization information to create a glass container defect dataset containing more than 60 000 samples to alleviate the sample scarcity problem in industrial scenarios. Subsequently, this article designs the CIA. CIA optimizes the probability distribution of features through the co-evolution of edge and context features, thereby improving detection accuracy in blurred defects and noisy environments. Finally, this article proposes a novel inforced IoU loss (IIoU loss), which can obtain more accurate position information by being aware of the scale changes of the predicted box. Defect detection experiments in three mainstream industrial manufacturing categories (Northeastern University (NEU)-Det, glass containers, wood) show that CIA only uses 22.5 GFLOPs, and mean average precision (mAP) (NEU-Det: 88.74%, glass containers: 95.38%, wood: 68.42%) outperforms state-of-the-art methods.
Large-scale Multi-objective Feature Selection: A Multi-phase Search Space Shrinking Approach
https://arxiv.org/abs/2410.21293
Feature selection is a crucial step in machine learning, especially for high-dimensional datasets, where irrelevant and redundant features can degrade model performance and increase computational costs. This paper proposes a novel large-scale multi-objective evolutionary algorithm based on the search space shrinking, termed LMSSS, to tackle the challenges of feature selection particularly as a sparse optimization problem. The method includes a shrinking scheme to reduce dimensionality of the search space by eliminating irrelevant features before the main evolutionary process. This is achieved through a ranking-based filtering method that evaluates features based on their correlation with class labels and frequency in an initial, cost-effective evolutionary process. Additionally, a smart crossover scheme based on voting between parent solutions is introduced, giving higher weight to the parent with better classification accuracy. An intelligent mutation process is also designed to target features prematurely excluded from the population, ensuring they are evaluated in combination with other features. These integrated techniques allow the evolutionary process to explore the search space more efficiently and effectively, addressing the sparse and high-dimensional nature of large-scale feature selection problems. The effectiveness of the proposed algorithm is demonstrated through comprehensive experiments on 15 large-scale datasets, showcasing its potential to identify more accurate feature subsets compared to state-of-the-art large-scale feature selection algorithms. These results highlight LMSSS's capability to improve model performance and computational efficiency, setting a new benchmark in the field.
Deep Insights into Automated Optimization with Large Language Models and Evolutionary Algorithms
https://arxiv.org/abs/2410.20848
Designing optimization approaches, whether heuristic or meta-heuristic, usually demands extensive manual intervention and has difficulty generalizing across diverse problem domains. The combination of Large Language Models (LLMs) and Evolutionary Algorithms (EAs) offers a promising new approach to overcome these limitations and make optimization more automated. In this setup, LLMs act as dynamic agents that can generate, refine, and interpret optimization strategies, while EAs efficiently explore complex solution spaces through evolutionary operators. Since this synergy enables a more efficient and creative search process, we first conduct an extensive review of recent research on the application of LLMs in optimization. We focus on LLMs' dual functionality as solution generators and algorithm designers. Then, we summarize the common and valuable designs in existing work and propose a novel LLM-EA paradigm for automated optimization. Furthermore, centered on this paradigm, we conduct an in-depth analysis of innovative methods for three key components: individual representation, variation operators, and fitness evaluation. We address challenges related to heuristic generation and solution exploration, especially from the LLM prompts' perspective. Our systematic review and thorough analysis of the paradigm can assist researchers in better understanding the current research and promoting the development of combining LLMs with EAs for automated optimization.
应用研究
A Large-Scale Multi-Objective Evolutionary Quantile Estimation Model for Wind Power Probabilistic Forecasting, IEEE TEVC
https://ieeexplore.ieee.org/document/10736509
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 paper proposes a novel model called large-scale multi-objective evolutionary quantile estimation (LMOEQE) to obtain high-quality wind power probabilistic estimations. Specifically, for avoiding quantile crossover, a multi-quantile regression monotone fuzzy neural network (MQRMFNN) is firstly 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 multi-objective problem (MOP) to achieve the trade-off 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 multi-objective 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.
