Neural and Evolutionary Computing
See recent articles
Showing new listings for Thursday, 25 September 2025
- [1] arXiv:2509.19339 [cn-pdf, pdf, html, other]
-
Title: Multi-population Ensemble Genetic Programming via Cooperative Coevolution and Multi-view Learning for ClassificationTitle: 基于协作进化和多视角学习的多种群集成遗传编程用于分类Mohammad Sadegh Khorshidi, Navid Yazdanjue, Hassan Gharoun, Mohammad Reza Nikoo, Fang Chen, Amir H. GandomiComments: 59 Pages, 68 Figures, 27 TablesSubjects: Neural and Evolutionary Computing (cs.NE) ; Artificial Intelligence (cs.AI)
This paper introduces Multi-population Ensemble Genetic Programming (MEGP), a computational intelligence framework that integrates cooperative coevolution and the multiview learning paradigm to address classification challenges in high-dimensional and heterogeneous feature spaces. MEGP decomposes the input space into conditionally independent feature subsets, enabling multiple subpopulations to evolve in parallel while interacting through a dynamic ensemble-based fitness mechanism. Each individual encodes multiple genes whose outputs are aggregated via a differentiable softmax-based weighting layer, enhancing both model interpretability and adaptive decision fusion. A hybrid selection mechanism incorporating both isolated and ensemble-level fitness promotes inter-population cooperation while preserving intra-population diversity. This dual-level evolutionary dynamic facilitates structured search exploration and reduces premature convergence. Experimental evaluations across eight benchmark datasets demonstrate that MEGP consistently outperforms a baseline GP model in terms of convergence behavior and generalization performance. Comprehensive statistical analyses validate significant improvements in Log-Loss, Precision, Recall, F1 score, and AUC. MEGP also exhibits robust diversity retention and accelerated fitness gains throughout evolution, highlighting its effectiveness for scalable, ensemble-driven evolutionary learning. By unifying population-based optimization, multi-view representation learning, and cooperative coevolution, MEGP contributes a structurally adaptive and interpretable framework that advances emerging directions in evolutionary machine learning.
本文介绍了多种群集成遗传编程（MEGP），这是一种计算智能框架，结合了协同进化和多视角学习范式，以解决高维和异构特征空间中的分类挑战。 MEGP将输入空间分解为条件独立的特征子集，使多个子种群能够并行进化，同时通过动态集成的适应度机制进行交互。 每个个体编码多个基因，其输出通过可微的基于softmax的加权层进行聚合，从而提高模型的可解释性和自适应决策融合。 一种结合孤立和集成级适应度的混合选择机制促进了种群间的合作，同时保持种群内的多样性。 这种双层次的进化动态促进了结构化的搜索探索并减少了过早收敛。 在八个基准数据集上的实验评估表明，MEGP在收敛行为和泛化性能方面始终优于基线GP模型。 全面的统计分析验证了Log-Loss、精确率、召回率、F1分数和AUC的显著改进。 MEGP在整个进化过程中表现出强大的多样性保留和加速的适应度增长，突显了其在可扩展的、基于集成的进化学习中的有效性。 通过统一基于种群的优化、多视角表示学习和协同进化，MEGP贡献了一个结构自适应且可解释的框架，推动了进化机器学习中的新兴方向。
- [2] arXiv:2509.19821 [cn-pdf, pdf, html, other]
-
Title: Fully Tensorized GPU-accelerated Multi-population Evolutionary Algorithm for Constrained Multiobjective Optimization ProblemsTitle: 针对约束多目标优化问题的全张量化GPU加速多种群进化算法Subjects: Neural and Evolutionary Computing (cs.NE)
Real world constrained multiobjective optimization problems (CMOPs) are prevalent and often come with stringent time-sensitive requirements. However, most contemporary constrained multiobjective evolutionary algorithms (CMOEAs) suffer from a number of drawbacks, including complex designs, low computational efficiency, and long convergence times, which are particularly pronounced when addressing time-sensitive CMOPs. Although research on accelerating evolutionary algorithms using GPU parallelism has advanced, existing CMOEAs still face significant limitations within GPU frameworks. To overcome these challenges, this paper proposes a GPU-accelerated multi-population evolutionary algorithm, termed GMPEA. We first systematically analyze the performance bottlenecks of representative CMOEAs when implemented in a GPU environment. To address the trade-off between computational speed and solution performance, GMPEA introduces a decomposition-based multi-population approach that is fully parallelized across its entire workflow. We conducted comparative experiments on various benchmark tests and real world applications: the Weapon Target Assignment Problems. The results demonstrate that GMPEA achieves competitive performance even without time constraints, while its computational speed significantly surpasses that of the compared algorithms. More critically, under a strict time limit, the performance of GMPEA drastically outperforms its counterparts. This work provides compelling evidence of GMPEA's superiority in solving time-sensitive CMOPs.
现实世界中的约束多目标优化问题（CMOPs）普遍存在，并且通常具有严格的时间敏感性要求。 然而，大多数当代约束多目标进化算法（CMOEAs）存在诸多缺点，包括设计复杂、计算效率低和收敛时间长，这些缺点在处理时间敏感的CMOPs时尤为明显。 尽管利用GPU并行性加速进化算法的研究已经取得进展，但现有的CMOEA在GPU框架内仍然面临显著的限制。 为克服这些挑战，本文提出了一种基于GPU加速的多群体进化算法，称为GMPEA。 我们首先系统分析了代表性CMOEA在GPU环境中的性能瓶颈。 为解决计算速度与解性能之间的权衡，GMPEA引入了一种基于分解的多群体方法，该方法在其整个工作流程中完全并行化。 我们在各种基准测试和现实世界应用上进行了比较实验：武器目标分配问题。 结果表明，即使在没有时间限制的情况下，GMPEA也表现出具有竞争力的性能，而其计算速度显著优于比较算法。 更重要的是，在严格的时限下，GMPEA的性能远远优于其竞争对手。 这项工作提供了GMPEA在解决时间敏感的CMOPs方面的优越性的有力证据。
- [3] arXiv:2509.20049 [cn-pdf, pdf, html, other]
-
Title: Projective Kolmogorov Arnold Neural Networks (P-KANs): Entropy-Driven Functional Space Discovery for Interpretable Machine LearningTitle: 投影柯尔莫哥洛夫阿诺尔德神经网络（P-KANs）：用于可解释机器学习的熵驱动函数空间发现Subjects: Neural and Evolutionary Computing (cs.NE) ; Artificial Intelligence (cs.AI) ; Machine Learning (cs.LG)
Kolmogorov-Arnold Networks (KANs) relocate learnable nonlinearities from nodes to edges, demonstrating remarkable capabilities in scientific machine learning and interpretable modeling. However, current KAN implementations suffer from fundamental inefficiencies due to redundancy in high-dimensional spline parameter spaces, where numerous distinct parameterisations yield functionally equivalent behaviors. This redundancy manifests as a "nuisance space" in the model's Jacobian, leading to susceptibility to overfitting and poor generalization. We introduce Projective Kolmogorov-Arnold Networks (P-KANs), a novel training framework that guides edge function discovery towards interpretable functional representations through entropy-minimisation techniques from signal analysis and sparse dictionary learning. Rather than constraining functions to predetermined spaces, our approach maintains spline space flexibility while introducing "gravitational" terms that encourage convergence towards optimal functional representations. Our key insight recognizes that optimal representations can be identified through entropy analysis of projection coefficients, compressing edge functions to lower-parameter projective spaces (Fourier, Chebyshev, Bessel). P-KANs demonstrate superior performance across multiple domains, achieving up to 80% parameter reduction while maintaining representational capacity, significantly improved robustness to noise compared to standard KANs, and successful application to industrial automated fiber placement prediction. Our approach enables automatic discovery of mixed functional representations where different edges converge to different optimal spaces, providing both compression benefits and enhanced interpretability for scientific machine learning applications.
Kolmogorov-Arnold网络（KANs）将可学习的非线性从节点转移到边，展示了在科学机器学习和可解释建模中的显著能力。 然而，当前的KAN实现由于高维样条参数空间中的冗余而存在根本性的低效率，其中许多不同的参数化产生功能等效的行为。 这种冗余在模型的雅可比矩阵中表现为“干扰空间”，导致容易过拟合和泛化能力差。 我们引入了投影Kolmogorov-Arnold网络（P-KANs），这是一种新的训练框架，通过信号分析和稀疏字典学习中的熵最小化技术，引导边函数发现走向可解释的功能表示。 我们的方法不将函数限制在预定的空间中，而是在保持样条空间灵活性的同时，引入“引力”项，鼓励收敛到最优的功能表示。 我们的关键见解认识到，可以通过投影系数的熵分析来识别最优表示，将边函数压缩到低参数投影空间（傅里叶、切比雪夫、贝塞尔）。 P-KANs在多个领域表现出卓越的性能，在保持表示能力的同时，参数减少高达80%，与标准KAN相比，对噪声的鲁棒性显著提高，并成功应用于工业自动纤维铺放预测。 我们的方法能够自动发现混合功能表示，其中不同边收敛到不同的最优空间，为科学机器学习应用提供了压缩优势和增强的可解释性。
- [4] arXiv:2509.20284 [cn-pdf, pdf, html, other]
-
Title: Biologically Plausible Learning via Bidirectional Spike-Based DistillationTitle: 通过双向基于尖峰的蒸馏进行生物合理学习Changze Lv, Yifei Wang, Yanxun Zhang, Yiyang Lu, Jingwen Xu, Di Yu, Xin Du, Xuanjing Huang, Xiaoqing ZhengSubjects: Neural and Evolutionary Computing (cs.NE)
Developing biologically plausible learning algorithms that can achieve performance comparable to error backpropagation remains a longstanding challenge. Existing approaches often compromise biological plausibility by entirely avoiding the use of spikes for error propagation or relying on both positive and negative learning signals, while the question of how spikes can represent negative values remains unresolved. To address these limitations, we introduce Bidirectional Spike-based Distillation (BSD), a novel learning algorithm that jointly trains a feedforward and a backward spiking network. We formulate learning as a transformation between two spiking representations (i.e., stimulus encoding and concept encoding) so that the feedforward network implements perception and decision-making by mapping stimuli to actions, while the backward network supports memory recall by reconstructing stimuli from concept representations. Extensive experiments on diverse benchmarks, including image recognition, image generation, and sequential regression, show that BSD achieves performance comparable to networks trained with classical error backpropagation. These findings represent a significant step toward biologically grounded, spike-driven learning in neural networks.
开发出能够达到误差反向传播性能水平的生物合理学习算法仍然是一个长期存在的挑战。 现有的方法通常通过完全避免使用尖峰进行误差传播或依赖正负学习信号来牺牲生物合理性，而尖峰如何表示负值的问题仍未解决。 为了解决这些限制，我们引入了双向基于尖峰的知识蒸馏（BSD），这是一种新型的学习算法，联合训练前馈和反向尖峰网络。 我们将学习建模为两种尖峰表示之间的转换（即，刺激编码和概念编码），使得前馈网络通过将刺激映射到动作来实现感知和决策，而反向网络则通过从概念表示中重建刺激来支持记忆回忆。 在包括图像识别、图像生成和序列回归在内的多种基准上的大量实验表明，BSD的性能可与使用经典误差反向传播训练的网络相媲美。 这些发现标志着在神经网络中实现基于生物原理的尖峰驱动学习迈出了重要一步。
New submissions (showing 4 of 4 entries )
- [5] arXiv:2509.19351 (cross-list from q-bio.NC) [cn-pdf, pdf, other]
-
Title: The Impact of Structural Changes on Learning Capacity in the Fly Olfactory Neural CircuitTitle: 结构变化对果蝇嗅觉神经回路学习能力的影响Subjects: Neurons and Cognition (q-bio.NC) ; Artificial Intelligence (cs.AI) ; Machine Learning (cs.LG) ; Neural and Evolutionary Computing (cs.NE)
The Drosophila mushroom body (MB) is known to be involved in olfactory learning and memory; the synaptic plasticity of the Kenyon cell (KC) to mushroom body output neuron (MBON) synapses plays a key role in the learning process. Previous research has focused on projection neuron (PN) to Kenyon cell (KC) connectivity within the MB; we examine how perturbations to the mushroom body circuit structure and changes in connectivity, specifically within the KC to mushroom body output neuron (MBON) neural circuit, affect the MBONs' ability to distinguish between odor classes. We constructed a neural network that incorporates the connectivity between PNs, KCs, and MBONs. To train our model, we generated ten artificial input classes, which represent the projection neuron activity in response to different odors. We collected data on the number of KC-to-MBON connections, MBON error rates, and KC-to-MBON synaptic weights, among other metrics. We observed that MBONs with very few presynaptic KCs consistently performed worse than others in the odor classification task. The developmental types of KCs also played a significant role in each MBON's output. We performed random and targeted KC ablation and observed that ablating developmentally mature KCs had a greater negative impact on MBONs' learning capacity than ablating immature KCs. Random and targeted pruning of KC-MBON synaptic connections yielded results largely consistent with the ablation experiments. To further explore the various types of KCs, we also performed rewiring experiments in the PN to KC circuit. Our study furthers our understanding of olfactory neuroplasticity and provides important clues to understanding learning and memory in general. Understanding how the olfactory circuits process and learn can also have potential applications in artificial intelligence and treatments for neurodegenerative diseases.
果蝇蘑菇体（MB）已知参与嗅觉学习和记忆；肯辛细胞（KC）到蘑菇体输出神经元（MBON）突触的突触可塑性在学习过程中起关键作用。 先前的研究集中在MB内投射神经元（PN）到肯辛细胞（KC）的连接；我们研究了对蘑菇体电路结构和连接的变化，特别是在KC到蘑菇体输出神经元（MBON）神经电路中的变化，如何影响MBON区分气味类别的能力。 我们构建了一个包含PN、KC和MBON之间连接的神经网络。 为了训练我们的模型，我们生成了十个人工输入类别，这些类别代表投射神经元对不同气味的活动。 我们收集了关于KC到MBON连接数量、MBON错误率和KC到MBON突触权重等指标的数据。 我们观察到，具有很少前突触KC的MBON在气味分类任务中表现始终不如其他MBON。 KC的发展类型也对每个MBON的输出起到了重要作用。 我们进行了随机和有针对性的KC消融，并观察到消融发育成熟的KC对MBON的学习能力的负面影响大于消融未成熟KC的影响。 对KC-MBON突触连接的随机和有针对性的修剪结果与消融实验的结果基本一致。 为进一步探索各种类型的KC，我们还在PN到KC电路中进行了重连实验。 我们的研究加深了我们对嗅觉神经可塑性的理解，并为理解一般的学习和记忆提供了重要线索。 了解嗅觉电路如何处理和学习信息，也可能在人工智能和神经退行性疾病治疗方面有潜在应用。
- [6] arXiv:2509.20269 (cross-list from cs.LG) [cn-pdf, pdf, other]
-
Title: Predictive Coding-based Deep Neural Network Fine-tuning for Computationally Efficient Domain AdaptationTitle: 基于预测编码的深度神经网络微调以实现计算高效的领域自适应Comments: 20 pages, 4 figuresSubjects: Machine Learning (cs.LG) ; Computer Vision and Pattern Recognition (cs.CV) ; Neural and Evolutionary Computing (cs.NE)
As deep neural networks are increasingly deployed in dynamic, real-world environments, relying on a single static model is often insufficient. Changes in input data distributions caused by sensor drift or lighting variations necessitate continual model adaptation. In this paper, we propose a hybrid training methodology that enables efficient on-device domain adaptation by combining the strengths of Backpropagation and Predictive Coding. The method begins with a deep neural network trained offline using Backpropagation to achieve high initial performance. Subsequently, Predictive Coding is employed for online adaptation, allowing the model to recover accuracy lost due to shifts in the input data distribution. This approach leverages the robustness of Backpropagation for initial representation learning and the computational efficiency of Predictive Coding for continual learning, making it particularly well-suited for resource-constrained edge devices or future neuromorphic accelerators. Experimental results on the MNIST and CIFAR-10 datasets demonstrate that this hybrid strategy enables effective adaptation with a reduced computational overhead, offering a promising solution for maintaining model performance in dynamic environments.
随着深度神经网络在动态的现实环境中越来越广泛地部署，依赖单一静态模型往往不足以应对挑战。由于传感器漂移或光照变化导致的输入数据分布变化，需要持续的模型适应。在本文中，我们提出了一种混合训练方法，通过结合反向传播和预测编码的优势，实现高效的设备端领域自适应。该方法首先使用反向传播在离线状态下训练一个深度神经网络，以达到高的初始性能。随后，采用预测编码进行在线适应，使模型能够恢复由于输入数据分布变化而损失的准确性。这种方法利用了反向传播在初始表示学习中的鲁棒性以及预测编码在持续学习中的计算效率，使其特别适用于资源受限的边缘设备或未来的神经形态加速器。在MNIST和CIFAR-10数据集上的实验结果表明，这种混合策略能够以较低的计算开销实现有效的适应，为在动态环境中保持模型性能提供了一个有前景的解决方案。
Cross submissions (showing 2 of 2 entries )
- [7] arXiv:2206.15238 (replaced) [cn-pdf, pdf, html, other]
-
Title: Runtime Analysis of Competitive co-Evolutionary Algorithms for Maximin Optimisation of a Bilinear FunctionTitle: 竞争协同进化算法在双线性函数最大最小优化中的运行时间分析Comments: Published in Algorithmica. One theorem has been added to the appendixSubjects: Neural and Evolutionary Computing (cs.NE) ; Populations and Evolution (q-bio.PE)
Co-evolutionary algorithms have a wide range of applications, such as in hardware design, evolution of strategies for board games, and patching software bugs. However, these algorithms are poorly understood and applications are often limited by pathological behaviour, such as loss of gradient, relative over-generalisation, and mediocre objective stasis. It is an open challenge to develop a theory that can predict when co-evolutionary algorithms find solutions efficiently and reliable. This paper provides a first step in developing runtime analysis for population-based competitive co-evolutionary algorithms. We provide a mathematical framework for describing and reasoning about the performance of co-evolutionary processes. To illustrate the framework, we introduce a population-based co-evolutionary algorithm called \pdcoea, and prove that it obtains a solution to a bilinear maximin optimisation problem in expected polynomial time. Finally, we describe settings where \pdcoea needs exponential time with overwhelmingly high probability to obtain a solution.
协同进化算法有广泛的应用，例如在硬件设计、棋盘游戏策略的进化以及修复软件错误中。 然而，这些算法尚不为人所理解，应用常常受到病态行为的限制，例如梯度消失、相对过度泛化和中等目标停滞。 开发一种能够预测协同进化算法何时能高效且可靠地找到解决方案的理论是一个开放性的挑战。 本文为开发基于种群的竞争性协同进化算法的运行时间分析提供了一个初步步骤。 我们提供了一个数学框架，用于描述和推理协同进化过程的性能。 为了说明该框架，我们引入了一种基于种群的协同进化算法，称为\pdcoea ，并证明它在期望多项式时间内可以解决一个双线性极大极小优化问题。 最后，我们描述了\pdcoea 在极高的概率下需要指数时间才能获得解决方案的情况。
- [8] arXiv:2411.08437 (replaced) [cn-pdf, pdf, html, other]
-
Title: A Detection Region Method-Based Evolutionary Algorithm for Binary Constrained Multiobjective OptimizationTitle: 基于检测区域方法的二元约束多目标优化进化算法Subjects: Neural and Evolutionary Computing (cs.NE)
Solving constrained multi-objective optimization problems (CMOPs) is a challenging task. While many practical algorithms have been developed to tackle CMOPs, real-world scenarios often present cases where the constraint functions are unknown or unquantifiable, resulting in only binary outcomes (feasible or infeasible). This limitation reduces the effectiveness of constraint violation guidance, which can negatively impact the performance of existing algorithms that rely on this approach. Such challenges are particularly detrimental for algorithms employing the epsilon-based method, as they hinder effective relaxation of the feasible region. To address these challenges, this paper proposes a novel algorithm called DRMCMO based on the detection region method. In DRMCMO, detection regions dynamic monitor feasible solutions to enhance convergence, helping the population escape local optima. Additionally, these regions collaborate with the neighbor pairing strategy to improve population diversity within narrow feasible areas. We have modified three existing test suites to serve as benchmark test problems for CMOPs with binary constraints(CMOP/BC) and conducted comprehensive comparative experiments with state-of-the-art algorithms on these test suites and real-world problems. The results demonstrate the strong competitiveness of DRMCMO against state-of-the-art algorithms. Given the limited research on CMOP/BC, our study offers a new perspective for advancing this field.
解决约束多目标优化问题（CMOPs）是一个具有挑战性的任务。虽然已经开发了许多实际算法来处理CMOPs，但现实场景中常常出现约束函数未知或无法量化的情况，导致只有二元结果（可行或不可行）。这种限制降低了约束违反指导的有效性，可能对依赖这种方法的现有算法性能产生负面影响。对于采用基于epsilon的方法的算法来说，这些挑战尤其有害，因为它们阻碍了可行区域的有效放松。为了解决这些挑战，本文提出了一种基于检测区域方法的新算法，称为DRMCMO。在DRMCMO中，检测区域动态监控可行解以增强收敛性，帮助种群逃离局部最优。此外，这些区域与邻居配对策略协作，以提高狭窄可行区域内的种群多样性。我们修改了三个现有的测试套件，作为具有二元约束的CMOPs（CMOP/BC）的基准测试问题，并在这些测试套件和现实问题上与最先进的算法进行了全面的比较实验。结果表明，DRMCMO在与最先进的算法竞争中表现出强大的竞争力。鉴于对CMOP/BC的研究有限，我们的研究为推进这一领域提供了新的视角。
- [9] arXiv:2411.10697 (replaced) [cn-pdf, pdf, html, other]
-
Title: Language Model Evolutionary Algorithms for Recommender Systems: Benchmarks and Algorithm ComparisonsTitle: 语言模型进化算法在推荐系统中的应用：基准测试与算法比较Subjects: Neural and Evolutionary Computing (cs.NE)
In the evolutionary computing community, the remarkable language-handling capabilities and reasoning power of large language models (LLMs) have significantly enhanced the functionality of evolutionary algorithms (EAs), enabling them to tackle optimization problems involving structured language or program code. Although this field is still in its early stages, its impressive potential has led to the development of various LLM-based EAs. To effectively evaluate the performance and practical applicability of these LLM-based EAs, benchmarks with real-world relevance are essential. In this paper, we focus on LLM-based recommender systems (RSs) and introduce a benchmark problem set, named RSBench, specifically designed to assess the performance of LLM-based EAs in recommendation prompt optimization. RSBench emphasizes session-based recommendations, aiming to discover a set of Pareto optimal prompts that guide the recommendation process, providing accurate, diverse, and fair recommendations. We develop three LLM-based EAs based on established EA frameworks and experimentally evaluate their performance using RSBench. Our study offers valuable insights into the application of EAs in LLM-based RSs. Additionally, we explore key components that may influence the overall performance of the RS, providing meaningful guidance for future research on the development of LLM-based EAs in RSs. The source code of the proposed RSBench can be found at https://github.com/LiuJ-2023/RSBench/tree/main.
在进化计算领域，大型语言模型（LLMs）出色的语言处理能力和推理能力显著增强了进化算法（EAs）的功能，使其能够解决涉及结构化语言或程序代码的优化问题。 尽管该领域仍处于早期阶段，但其令人印象深刻的可能性已经促成了各种基于LLM的EAs的发展。 为了有效评估这些基于LLM的EAs的性能和实际适用性，具有现实相关性的基准测试是必不可少的。 在本文中，我们关注基于LLM的推荐系统（RSs），并引入了一个名为RSBench的基准问题集，专门用于评估基于LLM的EAs在推荐提示优化中的性能。 RSBench强调基于会话的推荐，旨在发现一组帕累托最优提示，引导推荐过程，提供准确、多样和公平的推荐。 我们基于已有的EA框架开发了三种基于LLM的EAs，并使用RSBench进行实验评估。 我们的研究为EAs在基于LLM的RSs中的应用提供了有价值的见解。 此外，我们探讨了可能影响RS整体性能的关键组件，为未来在RSs中开发基于LLM的EAs的研究提供了有意义的指导。 所提出的RSBench的源代码可在https://github.com/LiuJ-2023/RSBench/tree/main找到。
- [10] arXiv:2504.15147 (replaced) [cn-pdf, pdf, other]
-
Title: The Iterative Chainlet Partitioning Algorithm for the Traveling Salesman Problem with Drone and Neural AccelerationTitle: 用于带无人机的旅行商问题的迭代链块分割算法和神经加速Comments: v2: Major revision. Extended the neural acceleration model to support problems with a limited drone flying range. Added new experimental resultsSubjects: Neural and Evolutionary Computing (cs.NE)
This study introduces the Iterative Chainlet Partitioning (ICP) algorithm and its neural acceleration for solving the Traveling Salesman Problem with Drone (TSP-D). The proposed ICP algorithm decomposes a TSP-D solution into smaller segments called chainlets, each optimized individually by a dynamic programming subroutine. The chainlet with the highest improvement is updated, and the procedure is repeated until no further improvement is possible. We show that the subroutine runs in quadratic time and the number of subroutine calls is bounded linearly in problem size for the first iteration and remains constant in subsequent iterations, ensuring algorithmic scalability. Empirical results show that ICP outperforms existing algorithms in both solution quality and computational time. Tested over 1,249 benchmark instances, ICP yields an average improvement of 2.6\% in solution quality over the previous state-of-the-art algorithm while reducing computational time by 91.3\%. The procedure is deterministic, ensuring reliability without requiring multiple runs. The subroutine is the computational bottleneck in the already efficient ICP algorithm. To reduce the necessity of subroutine calls, we integrate a graph neural network (GNN) to predict incremental improvements. We demonstrate that the resulting Neuro ICP (NICP) achieves substantial acceleration while maintaining solution quality. Compared to ICP, NICP reduces the total computational time by 28.6\%, while the objective function value increase is limited to 0.14\%. A transfer learning framework enables efficient extension to various operational constraints, making this a valuable foundation for developing efficient algorithms for truck-drone synchronized routing problems.
本研究介绍了用于解决带无人机的旅行商问题（TSP-D）的迭代链节划分（ICP）算法及其神经加速方法。 所提出的ICP算法将TSP-D解分解为较小的段，称为链节，每个链节由动态规划子程序单独优化。 具有最高改进的链节被更新，并重复该过程直到无法进一步改进。 我们证明该子程序运行时间为二次时间，第一次迭代中子程序调用次数在问题规模上呈线性增长，后续迭代中保持恒定，从而确保算法的可扩展性。 实证结果表明，ICP在解的质量和计算时间方面均优于现有算法。 在1,249个基准实例上测试，ICP在解的质量上比之前的最先进算法平均提高了2.6%，同时计算时间减少了91.3%。 该过程是确定性的，无需多次运行即可确保可靠性。 子程序是已高效ICP算法中的计算瓶颈。 为了减少子程序调用的必要性，我们集成了一种图神经网络（GNN）来预测增量改进。 我们证明， resulting Neuro ICP（NICP）在保持解质量的同时实现了显著加速。 与ICP相比，NICP将总计算时间减少了28.6%，而目标函数值的增加仅限于0.14%。 一种迁移学习框架使得能够高效扩展到各种操作约束，这为开发卡车-无人机同步路由问题的高效算法提供了有价值的基石。