Automated Design of State Transition Rules in Ant Colony Optimization by Genetic Programming: A Comprehensive Investigation DOI Creative Commons
Bo‐Cheng Lin, Yi Mei, Mengjie Zhang

et al.

Research Square (Research Square), Journal Year: 2024, Volume and Issue: unknown

Published: May 31, 2024

Abstract The automated design of Ant Colony Optimization (ACO) algorithms has become increasingly significant, particularly in addressing complex combinatorial optimization problems. Although existing methods have achieved some success, they still face limitations, the high dependency on expert knowledge, pre-solved data, and challenges interpretability. Genetic Programming (GP), as a proven technology, shown potential optimizing state transition rules ACO. However, research GP-ACO is insufficient, terms experimental validation systematic evaluation. To address these issues, this study conducts comprehensive experiments to explore several key questions: generality homogeneously distributed maps, impact different ACO variants learning capabilities GP-ACO, effect 2-opt local search enhancement through addition more global information, interpretability GP-ACO. findings indicate that exhibits robust generality; variations among minimal performance; can somewhat diminish performance Max-Min System (MMAS); additional information significantly enhance GP-ACO; good

Language: Английский

Neural combinatorial optimization: A tutorial DOI Creative Commons

Davide Angioni,

Claudia Archetti, M. Grazia Speranza

et al.

Computers & Operations Research, Journal Year: 2025, Volume and Issue: unknown, P. 107102 - 107102

Published: May 1, 2025

Citations

0
Regularity model based offspring generation in surrogate-assisted evolutionary algorithms for expensive multi-objective optimization DOI
Bingdong Li, Yongfan Lu, Hong Qian

et al.

Swarm and Evolutionary Computation, Journal Year: 2024, Volume and Issue: 86, P. 101506 - 101506

Published: Feb. 19, 2024

Language: Английский

Citations

3
NN-Steiner: A Mixed Neural-Algorithmic Approach for the Rectilinear Steiner Minimum Tree Problem DOI Open Access
Andrew B. Kahng, Robert R. Nerem, Yusu Wang

et al.

Proceedings of the AAAI Conference on Artificial Intelligence, Journal Year: 2024, Volume and Issue: 38(12), P. 13022 - 13030

Published: March 24, 2024

Recent years have witnessed rapid advances in the use of neural networks to solve combinatorial optimization problems. Nevertheless, designing "right" model that can effectively handle a given problem be challenging, and often there is no theoretical understanding or justification resulting model. In this paper, we focus on rectilinear Steiner minimum tree (RSMT) problem, which critical importance IC layout design as result has attracted numerous heuristic approaches VLSI literature. Our contributions are two-fold. On methodology front, propose NN-Steiner novel mixed neural-algorithmic framework for computing RSMTs leverages celebrated PTAS algorithmic Arora (and other geometric problems). replaces key components within Arora's by suitable components. particular, only needs four network (NN) called repeatedly an framework. Crucially, each NN bounded size independent input size, thus easy train. Furthermore, component learning generic step, once learned, generalizes much larger instances not seen training. NN-Steiner, our best knowledge, first architecture capacity approximately RSMT variants). empirical show how implemented demonstrate effectiveness approach, especially terms generalization, comparing with state-of-the-art methods (both non-neural based).

Language: Английский

Citations

3
Surrogate-assisted evolutionary algorithms for expensive combinatorial optimization: a survey DOI Creative Commons
Shulei Liu, Handing Wang, Wei Peng

et al.

Complex & Intelligent Systems, Journal Year: 2024, Volume and Issue: 10(4), P. 5933 - 5949

Published: May 18, 2024

Abstract As potent approaches for addressing computationally expensive optimization problems, surrogate-assisted evolutionary algorithms (SAEAs) have garnered increasing attention. Prevailing endeavors in computation predominantly concentrate on continuous with a notable scarcity of investigations directed toward combinatorial problems (ECOPs). Nevertheless, numerous ECOPs persist practical applications. The widespread prevalence such starkly contrasts the limited development relevant research. Motivated by this disparity, paper conducts comprehensive survey SAEAs tailored to address ECOPs. This comprises two primary segments. first segment synthesizes prevalent global, local, hybrid, and learning search strategies, elucidating their respective strengths weaknesses. Subsequently, second furnishes an overview surrogate-based evaluation technologies, delving into three pivotal facets: model selection, construction, management. also discusses several potential future directions focus towards optimization.

Language: Английский

Citations

3
Enhancing Multi-Objective Optimization with Automatic Construction of Parallel Algorithm Portfolios DOI Open Access

Xiasheng Ma,

Shengcai Liu, Wenjing Hong

et al.

Electronics, Journal Year: 2023, Volume and Issue: 12(22), P. 4639 - 4639

Published: Nov. 13, 2023

It has been widely observed that there exists no universal best Multi-Objective Evolutionary Algorithm (MOEA) dominating all other MOEAs on possible Optimization Problems (MOPs). In this work, we advocate using the Parallel Portfolio (PAP), which runs multiple independently in parallel and gets out of them, to combine advantages different MOEAs. Since manual construction PAPs is non-trivial tedious, propose automatically construct high-performance for solving MOPs. Specifically, first a variant PAPs, namely MOEAs/PAP, can better determine output solution set MOPs than conventional PAPs. Then, present an automatic approach MOEAs/PAP with novel performance metric evaluating across Finally, use proposed based training algorithm configuration space defined by several variants NSGA-II. Experimental results show constructed even rival state-of-the-art multi-operator-based designed human experts, demonstrating huge potential multi-objective optimization.

Language: Английский

Citations

2
A framework based on generational and environmental response strategies for dynamic multi-objective optimization DOI
Qingya Li, Xiangzhi Liu, Fuqiang Wang

et al.

Applied Soft Computing, Journal Year: 2023, Volume and Issue: 152, P. 111114 - 111114

Published: Dec. 4, 2023

Language: Английский

Citations

2
Learning Encodings for Constructive Neural Combinatorial Optimization Needs to Regret DOI Open Access
Rui Sun, Zhi Zheng, Zhenkun Wang

et al.

Proceedings of the AAAI Conference on Artificial Intelligence, Journal Year: 2024, Volume and Issue: 38(18), P. 20803 - 20811

Published: March 24, 2024

Deep-reinforcement-learning (DRL) based neural combinatorial optimization (NCO) methods have demonstrated efficiency without relying on the guidance of optimal solutions. As most mainstream among them, learning constructive heuristic (LCH) achieves high-quality solutions through a rapid autoregressive solution construction process. However, these LCH-based are deficient in convergency, and there is still performance gap compared to optimal. Intuitively, regret some steps process helpful training network representations. This article proposes novel regret-based mechanism for an advanced Our method can be applied as plug-in any existing DRL-NCO method. Experimental results demonstrate capability our work enhance various NCO models. Results also show that proposed LCH-Regret outperforms previous modification several typical problems. The code Supplementary File available at https://github.com/SunnyR7/LCH-Regret.

Language: Английский

Citations

0
A Novel Dual-Stage Algorithm for Capacitated Arc Routing Problems with Time-Dependent Service Costs DOI
Qingya Li, Shengcai Liu, Juan Zou

et al.

Published: Jan. 1, 2024

This paper focuses on solving the capacitated arc routing problem with time-dependent service costs (CARPTDSC), which is motivated by winter gritting applications. In current literature, exact algorithms designed for CARPTDSC can only handle small-scale instances, while heuristic fail to obtain high-quality solutions. To overcome these limitations, we propose a novel dual-stage algorithm, called MAENS-GN, that consists of stage and vehicle departure time optimization stage. The former obtains plan, latter determines time. Importantly, existing literature often ignores characteristic information contained in relationship between route cost most significant innovation this lies exploitation during Specifically, conduct detailed analysis under various scenarios employ tailored methods (approximately) optimal Furthermore, an improved initialization strategy considers characteristics achieve better solution quality. addition modified benchmark test sets, also experiment real-world set. Experimental results demonstrate MAENS-GN solutions both larger-scale instances CARPTDSC.

Language: Английский

Citations

0
A&I-ED-TSP: Association & Integration Encoder-Decoder for Traveling Shortest Path Planning DOI Creative Commons
Bin Hu, Renjun Zhang

IEEE Access, Journal Year: 2024, Volume and Issue: 12, P. 129601 - 129610

Published: Jan. 1, 2024

Language: Английский

Citations

0
A Requirements Optimization Method for Automotive Cyber Security Assurance DOI
Zhengshu Zhou,

Xinqi Yang,

Qian Long

et al.

Lecture notes in computer science, Journal Year: 2024, Volume and Issue: unknown, P. 506 - 513

Published: Jan. 1, 2024

Language: Английский

Citations

0