进化计算领域文章更新主要包括以下六大方向如下：
基础理论（包括遗传算法、进化策略、遗传编程、群智能等算法设计、理论研究、基准测试、进化思想、算法软件、综述等）
进化优化（包括黑盒优化、多目标优化、约束优化、噪声优化、多任务优化、多模态优化、迁移优化、大规模优化、昂贵优化、学习优化等）
组合优化（包括进化神经组合优化、进化机器人、路线规划、布局布线、工业控制、调度等）
神经进化（包含进化神经网络的参数、超参数、架构、规则等）
进化学习（包括进化特征选择、强化学习、多目标学习、公平性学习、联邦学习、进化计算机视觉、进化自然语言处理、进化数据挖掘等）
应用研究（工业、网络、安全、物理、生物、化学等）
文章来源主要包括：
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
基础理论
Tail Bounds on the Runtime of Categorical Compact Genetic Algorithm, ECJ
https://direct.mit.edu/evco/article-abstract/doi/10.1162/evco_a_00361/124684/Tail-Bounds-on-the-Runtime-of-Categorical-Compact?redirectedFrom=fulltext
The majority of theoretical analyses of evolutionary algorithms in the discrete domain focus on binary optimization algorithms, even though black-box optimization on the categorical domain has a lot of practical applications. In this paper, we consider a probabilistic model-based algorithm using the family of categorical distributions as its underlying distribution and set the sample size as two. We term this specific algorithm the categorical compact genetic algorithm (ccGA). The ccGA can be considered as an extension of the compact genetic algorithm (cGA), which is an efficient binary optimization algorithm. We theoretically analyze the dependency of the number of possible categories K, the number of dimensions D, and the learning rate on the runtime. We investigate the tail bound of the runtime on two typical linear functions on the categorical domain: categorical OneMax (COM) and KVAL. We derive that the runtimes on COM and KVAL are and with high probability, respectively. Our analysis is a generalization for that of the cGA on the binary domain.
Intelligence at the Edge of Chaos
https://arxiv.org/abs/2410.02536
We explore the emergence of intelligent behavior in artificial systems by investigating how the complexity of rule-based systems influences the capabilities of models trained to predict these rules. Our study focuses on elementary cellular automata (ECA), simple yet powerful one-dimensional systems that generate behaviors ranging from trivial to highly complex. By training distinct Large Language Models (LLMs) on different ECAs, we evaluated the relationship between the complexity of the rules' behavior and the intelligence exhibited by the LLMs, as reflected in their performance on downstream tasks. Our findings reveal that rules with higher complexity lead to models exhibiting greater intelligence, as demonstrated by their performance on reasoning and chess move prediction tasks. Both uniform and periodic systems, and often also highly chaotic systems, resulted in poorer downstream performance, highlighting a sweet spot of complexity conducive to intelligence. We conjecture that intelligence arises from the ability to predict complexity and that creating intelligence may require only exposure to complexity.
On the Interaction of Adaptive Population Control with Cumulative Step-Size Adaptation
https://arxiv.org/abs/2410.00595
Three state-of-the-art adaptive population control strategies (PCS) are theoretically and empirically investigated for a multi-recombinative, cumulative step-size adaptation Evolution Strategy (μ/μI,λ)-CSA-ES. First, scaling properties for the generation number and mutation strength rescaling are derived on the sphere in the limit of large population sizes. Then, the adaptation properties of three standard CSA-variants are studied as a function of the population size and dimensionality, and compared to the predicted scaling results. Thereafter, three PCS are implemented along the CSA-ES and studied on a test bed of sphere, random, and Rastrigin functions. The CSA-adaptation properties significantly influence the performance of the PCS, which is shown in more detail. Given the test bed, well-performing parameter sets (in terms of scaling, efficiency, and success rate) for both the CSA- and PCS-subroutines are identified.
进化优化
Surrogate-Based Decision Boundary Evolutionary Sampling Method for Autonomous Systems, IEEE TEVC
https://ieeexplore.ieee.org/document/10700818
Searching the decision boundary of an autonomous system is essential for understanding its behavioral characteristics. In this paper, the decision boundary search problem is mathematically modeled as an optimization problem with continuous inputs and discrete outputs, which aims at searching continuous regions. A surrogate-based decision boundary evolutionary sampling method for autonomous systems (SDBES) is proposed. SDBES combines the evolutionary algorithms with adaptive sampling methods, enabling the samples to adaptively search and cover decision boundaries in iterative evolution. The subject of evolutionary iteration shifts from individual to community. The adaptive grouping strategy is designed to increase the diversity of sample points. The elite-pool strategy and elimination strategy are used to improve convergence. To fully compare the performance of algorithms with uniform standards and low cost, we design a series of test cases and two new metrics that consider repeatedly covered true boundary points and the number of queries of actual systems. The ablation experiments are conducted to verify the effectiveness of the strategy. SDBES is compared with two state-of-the-art adaptive sampling algorithms under the proposed 17 types of benchmarks and various sample numbers. Experimental results show that the sample points generated by SDBES could be concentrated in decision boundary regions with high precision and efficiency. The test of eight path planning scenarios illustrates that SDBES can effectively find the decision boundary of real-world autonomous systems and provide a new method for their robustness test.
Comparative study of regression vs pairwise models for surrogate-based heuristic optimisation
https://arxiv.org/abs/2410.03409
Heuristic optimisation algorithms explore the search space by sampling solutions, evaluating their fitness, and biasing the search in the direction of promising solutions. However, in many cases, this fitness function involves executing expensive computational calculations, drastically reducing the reasonable number of evaluations. In this context, surrogate models have emerged as an excellent alternative to alleviate these computational problems. This paper addresses the formulation of surrogate problems as both regression models that approximate fitness (surface surrogate models) and a novel way to connect classification models (pairwise surrogate models). The pairwise approach can be directly exploited by some algorithms, such as Differential Evolution, in which the fitness value is not actually needed to drive the search, and it is sufficient to know whether a solution is better than another one or not. Based on these modelling approaches, we have conducted a multidimensional analysis of surrogate models under different configurations: different machine learning algorithms (regularised regression, neural networks, decision trees, boosting methods, and random forests), different surrogate strategies (encouraging diversity or relaxing prediction thresholds), and compare them for both surface and pairwise surrogate models. The experimental part of the article includes the benchmark problems already proposed for the SOCO2011 competition in continuous optimisation and a simulation problem included in the recent GECCO2021 Industrial Challenge. This paper shows that the performance of the overall search, when using online machine learning-based surrogate models, depends not only on the accuracy of the predictive model but also on both the kind of bias towards positive or negative cases and how the optimisation uses those predictions to decide whether to execute the actual fitness function.
A Tutorial on the Design, Experimentation and Application of Metaheuristic Algorithms to Real-World Optimization Problems
https://arxiv.org/abs/2410.03205
In the last few years, the formulation of real-world optimization problems and their efficient solution via metaheuristic algorithms has been a catalyst for a myriad of research studies. In spite of decades of historical advancements on the design and use of metaheuristics, large difficulties still remain in regards to the understandability, algorithmic design uprightness, and performance verifiability of new technical achievements. A clear example stems from the scarce replicability of works dealing with metaheuristics used for optimization, which is often infeasible due to ambiguity and lack of detail in the presentation of the methods to be reproduced. Additionally, in many cases, there is a questionable statistical significance of their reported results. This work aims at providing the audience with a proposal of good practices which should be embraced when conducting studies about metaheuristics methods used for optimization in order to provide scientific rigor, value and transparency. To this end, we introduce a step by step methodology covering every research phase that should be followed when addressing this scientific field. Specifically, frequently overlooked yet crucial aspects and useful recommendations will be discussed in regards to the formulation of the problem, solution encoding, implementation of search operators, evaluation metrics, design of experiments, and considerations for real-world performance, among others. Finally, we will outline important considerations, challenges, and research directions for the success of newly developed optimization metaheuristics in their deployment and operation over real-world application environments.
An evolutionary approach for discovering non-Gaussian stochastic dynamical systems based on nonlocal Kramers-Moyal formulas
https://arxiv.org/abs/2409.19534
Discovering explicit governing equations of stochastic dynamical systems with both (Gaussian) Brownian noise and (non-Gaussian) Lévy noise from data is chanllenging due to possible intricate functional forms and the inherent complexity of Lévy motion. This present research endeavors to develop an evolutionary symbol sparse regression (ESSR) approach to extract non-Gaussian stochastic dynamical systems from sample path data, based on nonlocal Kramers-Moyal formulas, genetic programming, and sparse regression. More specifically, the genetic programming is employed to generate a diverse array of candidate functions, the sparse regression technique aims at learning the coefficients associated with these candidates, and the nonlocal Kramers-Moyal formulas serve as the foundation for constructing the fitness measure in genetic programming and the loss function in sparse regression. The efficacy and capabilities of this approach are showcased through its application to several illustrative models. This approach stands out as a potent instrument for deciphering non-Gaussian stochastic dynamics from available datasets, indicating a wide range of applications across different fields.
Analysing the Influence of Reorder Strategies for Cartesian Genetic Programming
https://arxiv.org/abs/2410.00518
Cartesian Genetic Programming (CGP) suffers from a specific limitation: Positional bias, a phenomenon in which mostly genes at the start of the genome contribute to a program output, while genes at the end rarely do. This can lead to an overall worse performance of CGP. One solution to overcome positional bias is to introduce reordering methods, which shuffle the current genotype without changing its corresponding phenotype. There are currently two different reorder operators that extend the classic CGP formula and improve its fitness value. In this work, we discuss possible shortcomings of these two existing operators. Afterwards, we introduce three novel operators which reorder the genotype of a graph defined by CGP. We show empirically on four Boolean and four symbolic regression benchmarks that the number of iterations until a solution is found and/or the fitness value improves by using CGP with a reorder method. However, there is no consistently best performing reorder operator. Furthermore, their behaviour is analysed by investigating their convergence plots and we show that all behave the same in terms of convergence type.
组合优化
A Multi-Objective Memetic Algorithm for Workflow Scheduling in Clouds, IEEE TETCI
https://ieeexplore.ieee.org/document/10705420
Simultaneously optimizing monetary cost and makespan of workflow execution is substantial to enhance the competitiveness of cloud services, but it still imposes challenges. Heuristics-based algorithms are often problem-dependent and well-suitable for special cases, but the complexity of workflow structures seriously challenges their generalization. Metaheuristics-based algorithms pose good generalization, but the elasticity and heterogeneity of cloud resources seriously impact their search efficiency. Inspired by previous works, we tailor a memetic workflow scheduling algorithm (KDMA for short) that embeds a heuristic local search operator into the multi-objective metaheuristic algorithm to combine their strengths and complement each other's shortcomings. Specifically, the proposed local search operator searches for a set of solutions with good convergence and diversity by accumulating tasks one by one. This operator is good at gathering workflow tasks into a limited range of candidate resources, thereby guiding the metaheuristic algorithm to focus on exploring potential solution regions. Moreover, KDMA includes an adaptive strategy to determine the number of solutions reproduced by the problem-special local search operator based on its past overall contribution. We compare KDMA to five representative algorithms over 25 real-world workflow instances to corroborate its superior all-around performance by performing the best on 21 workflow instances. Meanwhile, we conduct an ablation analysis to verify the performance contributions of two proposed mechanisms.
Optimal Solving of a Scheduling Problem Using Quantum Annealing Metaheuristics on the D-Wave Quantum Solver, IEEE TSMC
https://ieeexplore.ieee.org/document/10703120
Accurately solving discrete optimization problems is still a serious challenge for classical computing systems. Despite significant progress, it is still impossible to optimally solve examples of the size found in real-world applications. This article examines the problem of scheduling tasks on one machine. Each task has an associated execution time, desired completion date, and a late penalty feature weight. The order of executing tasks should be determined in a manner that minimizes the sum of delay costs. Despite the simplicity of the formulation, this problem is NP-hard and is representative of optimization challenges encountered in the practice of production control, management, and logistics.In this work, we propose using a quantum computing environment to solve it. The main disadvantage of calculations on quantum computers is their nondeterminism. Therefore, there is no guarantee of optimality of solutions to discrete optimization problems determined on a quantum computer.We propose a novel approach to constructing hybrid algorithms that guarantee the optimality of the solution. The algorithm for solving the task scheduling problem considered here is based on the branch and bound method. Calculations are performed alternately on a classical computer and a quantum computer. The lower and upper bounds of the criterion function are determined on a quantum computer. Computational experiments were performed on the D-Wave quantum computer. In small examples, the algorithm runs faster and generates significantly fewer solution tree vertices than its counterpart running on a classic computer. For larger examples, the proposed runtime-constrained method, acting as a heuristic, is an interesting alternative to using quantum computing hardware in relation to classical approaches based on silicon computers.
A System for Critical Facility and Resource Optimization in Disaster Management and Planning
https://arxiv.org/abs/2410.02956
Disruptions to medical infrastructure during disasters pose significant risks to critically ill patients with advanced chronic kidney disease or end-stage renal disease. To enhance patient access to dialysis treatment under such conditions, it is crucial to assess the vulnerabilities of critical care facilities to hazardous events. This study proposes optimization models for patient reallocation and the strategic placement of temporary medical facilities to bolster the resilience of the critical care system, with a focus on equitable outcomes. Utilizing human mobility data from Texas, we evaluate patient access to critical care and dialysis centers under simulated hazard scenarios. The proposed bio-inspired optimization model, based on the Ant Colony optimization method, efficiently reallocates patients to mitigate disrupted access to dialysis facilities. The model outputs offer valuable insights into patient and hospital preparedness for disasters. Overall, the study presents a data-driven, analytics-based decision support tool designed to proactively mitigate potential disruptions in access to critical care facilities during disasters, tailored to the needs of health officials, emergency managers, and hospital system administrators in both the private and public sectors.
神经演化
Cartesian Genetic Programming Approach for Designing Convolutional Neural Networks
https://arxiv.org/abs/2410.00129
The present study covers an approach to neural architecture search (NAS) using Cartesian genetic programming (CGP) for the design and optimization of Convolutional Neural Networks (CNNs). In designing artificial neural networks, one crucial aspect of the innovative approach is suggesting a novel neural architecture. Currently used architectures have mostly been developed manually by human experts, which is a time-consuming and error-prone process. In this work, we use pure Genetic Programming Approach to design CNNs, which employs only one genetic operation, i.e., mutation. In the course of preliminary experiments, our methodology yields promising results.
Life, uh, Finds a Way: Systematic Neural Search
https://arxiv.org/abs/2410.01349
We tackle the challenge of rapidly adapting an agent's behavior to solve spatiotemporally continuous problems in novel settings. Animals exhibit extraordinary abilities to adapt to new contexts, a capacity unmatched by artificial systems. Instead of focusing on generalization through deep reinforcement learning, we propose viewing behavior as the physical manifestation of a search procedure, where robust problem-solving emerges from an exhaustive search across all possible behaviors. Surprisingly, this can be done efficiently using online modification of a cognitive graph that guides action, challenging the predominant view that exhaustive search in continuous spaces is impractical. We describe an algorithm that implicitly enumerates behaviors by regulating the tight feedback loop between execution of behaviors and mutation of the graph, and provide a neural implementation based on Hebbian learning and a novel high-dimensional harmonic representation inspired by entorhinal cortex. By framing behavior as search, we provide a mathematically simple and biologically plausible model for real-time behavioral adaptation, successfully solving a variety of continuous state-space navigation problems. This framework not only offers a flexible neural substrate for other applications but also presents a powerful paradigm for understanding adaptive behavior. Our results suggest potential advancements in developmental learning and unsupervised skill acquisition, paving the way for autonomous robots to master complex skills in data-sparse environments demanding flexibility.
进化学习
Active Learning in Genetic Programming: Guiding Efficient Data Collection for Symbolic Regression, IEEE TEVC
https://ieeexplore.ieee.org/document/10700803
This paper 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.
Diffusion Models are Evolutionary Algorithms
https://arxiv.org/abs/2410.02543
In a convergence of machine learning and biology, we reveal that diffusion models are evolutionary algorithms. By considering evolution as a denoising process and reversed evolution as diffusion, we mathematically demonstrate that diffusion models inherently perform evolutionary algorithms, naturally encompassing selection, mutation, and reproductive isolation. Building on this equivalence, we propose the Diffusion Evolution method: an evolutionary algorithm utilizing iterative denoising -- as originally introduced in the context of diffusion models -- to heuristically refine solutions in parameter spaces. Unlike traditional approaches, Diffusion Evolution efficiently identifies multiple optimal solutions and outperforms prominent mainstream evolutionary algorithms. Furthermore, leveraging advanced concepts from diffusion models, namely latent space diffusion and accelerated sampling, we introduce Latent Space Diffusion Evolution, which finds solutions for evolutionary tasks in high-dimensional complex parameter space while significantly reducing computational steps. This parallel between diffusion and evolution not only bridges two different fields but also opens new avenues for mutual enhancement, raising questions about open-ended evolution and potentially utilizing non-Gaussian or discrete diffusion models in the context of Diffusion Evolution.
Large Language Model Aided Multi-objective Evolutionary Algorithm: a Low-cost Adaptive Approach
https://arxiv.org/abs/2410.02301
Multi-objective optimization is a common problem in practical applications, and multi-objective evolutionary algorithm (MOEA) is considered as one of the effective methods to solve these problems. However, their randomness sometimes prevents algorithms from rapidly converging to global optimization, and the design of their genetic operators often requires complicated manual tuning. To overcome this challenge, this study proposes a new framework that combines a large language model (LLM) with traditional evolutionary algorithms to enhance the algorithm's search capability and generalization this http URL our framework, we employ adaptive and hybrid mechanisms to integrate the LLM with the MOEA, thereby accelerating algorithmic convergence. Specifically, we leverage an auxiliary evaluation function and automated prompt construction within the adaptive mechanism to flexibly adjust the utilization of the LLM, generating high-quality solutions that are further refined and optimized through genetic this http URL, the hybrid mechanism aims to minimize interaction costs with the LLM as much as possible.
应用研究
Decentralized Event-Triggered Tracking Control for Unmatched Interconnected Systems via Particle Swarm Optimization-Based Adaptive Dynamic Programming, IEEE TCYB
https://ieeexplore.ieee.org/document/10701474
The problem of the large-scale interconnected system (LSIS) control is prevalent in practical engineering and is becoming increasingly complex. In this article, we propose a novel decentralized event-triggered tracking control (ETTC) strategy for a class of continuous-time nonlinear LSIS with unmatched interconnected terms and asymmetric input constraints. First, auxiliary subsystems are established to address the unmatched cross-linking terms. Next, the dynamics states of the tracking error and the exosystem are combined to construct a nominal augmented subsystem. By employing a nonquadratic performance function, the input-constrained decentralized tracking control problem is transformed into an optimal control problem for the nominal augmented subsystem. A group of independent parameters and event-triggered conditions are designed to save communication bandwidth and computational resources. Subsequently, the critic-only adaptive dynamic programming (ADP) method is used to solve the Hamilton–Jacobi–Bellman equation (HJBE) associated with the optimal control problem. To improve training success rate, the weights of the critic neural network (NN) are updated by introducing a particle swarm optimization algorithm (PSOA). The tracking error and the NN weights are proved to be uniformly ultimately bounded (UUB) under the proposed ETTC by using the Lyapunov extension theorem. Finally, the simulation example of an unmatched interconnected system is provided to verify the validity of the proposed decentralized method.
A Census-Based Genetic Algorithm for Target Set Selection Problem in Social Networks
https://arxiv.org/abs/2410.02011
This paper considers the Target Set Selection (TSS) Problem in social networks, a fundamental problem in viral marketing. In the TSS problem, a graph and a threshold value for each vertex of the graph are given. We need to find a minimum size vertex subset to "activate" such that all graph vertices are activated at the end of the propagation process. Specifically, we propose a novel approach called "a census-based genetic algorithm" for the TSS problem. In our algorithm, we use the idea of a census to gather and store information about each individual in a population and collect census data from the individuals constructed during the algorithm's execution so that we can achieve greater diversity and avoid premature convergence at locally optimal solutions. We use two distinct census information: (a) for each individual, the algorithm stores how many times it has been identified during the execution (b) for each network node, the algorithm counts how many times it has been included in a solution. The proposed algorithm can also self-adjust by using a parameter specifying the aggressiveness employed in each reproduction method. Additionally, the algorithm is designed to run in a parallelized environment to minimize the computational cost and check each individual's feasibility. Moreover, our algorithm finds the optimal solution in all cases while experimenting on random graphs. Furthermore, we execute the proposed algorithm on 14 large graphs of real-life social network instances from the literature, improving around 9.57 solution size (on average) and 134 vertices (in total) compared to the best solutions obtained in previous studies.
ADEPT-Z: Zero-Shot Automated Circuit Topology Search for Pareto-Optimal Photonic Tensor Cores
https://arxiv.org/abs/2410.01313
Photonic tensor cores (PTCs) are essential building blocks for optical artificial intelligence (AI) accelerators based on programmable photonic integrated circuits. Most PTC designs today are manually constructed, with low design efficiency and unsatisfying solution quality. This makes it challenging to meet various hardware specifications and keep up with rapidly evolving AI applications. Prior work has explored gradient-based methods to learn a good PTC structure differentiably. However, it suffers from slow training speed and optimization difficulty when handling multiple non-differentiable objectives and constraints. Therefore, in this work, we propose a more flexible and efficient zero-shot multi-objective evolutionary topology search framework ADEPT-Z that explores Pareto-optimal PTC designs with advanced devices in a larger search space. Multiple objectives can be co-optimized while honoring complicated hardware constraints. With only <3 hours of search, we can obtain tens of diverse Pareto-optimal solutions, 100x faster than the prior gradient-based method, outperforming prior manual designs with 2x higher accuracy weighted area-energy efficiency. The code of ADEPT-Z is available at this https URL.
