.png){kind=icon}
返回
Essential mutation framework for solving travelling salesman problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s10586-025-05789-w.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
本研究提出了一种新颖的Essential Mutation（EM）框架，用于提升进化算法在求解组合优化问题中的性能，重点关注旅行商问题（TSP）。所提EM的核心创新在于其能够通过分析高适应度解中反复出现的“essential edges”（关键边），来保留问题结构的关键组成部分。与传统的变异算子不同，本文提出的EM模型引入了一种基于适应度的策略，能够有选择地避免变异对解质量贡献高的边，从而有效平衡探索与开发。每条边的重要性通过种群统计动态评估，并根据可调的关键率（essential rate）在每一代中更新。尽管该框架与具体算法无关，但本文将其集成到遗传算法（GA）中以进行验证。在十二个TSPLIB基准实例上的广泛实验将EM与三种常用变异算子进行了比较：Swap Mutation（SM）、Reverse Mutation（RM）和Center Inverse Mutation（CIM）。结果表明，所提EM模型在保持更优解质量和更快收敛方面表现突出，尤其适用于较大规模实例。Wilcoxon符号秩检验证实，与RM和CIM相比，这些改进具有统计学显著性（p < 0.01），同时与SM保持竞争力。尽管所提EM模型会产生中等开销，但其对结构的认知能力使其能够提供更有效的搜索指导。总体而言，该框架引入了一种通用的变异策略，通过自适应的关键边保留来提升进化性能，并广泛适用于其他组合优化问题。
Keyword:
Artificial Intelligence (AI)
Essential mutation
Evolutionary Algorithms
Traveling salesman problem
Genetic algorithm
Swap mutation
Reverse mutation
期刊
C
IF:
0
论文数:
691
被引数:
1
机构
引用论文
A survey for recent applications and variants of nature-inspired immune search algorithm对自然启发式免疫搜索算法近期应用及变体的调查
PREAI
分享收藏Metaheuristics in combinatorial optimization: Overview and conceptual comparison组合优化中的元启发式: 概述和概念比较
PREAI
分享收藏An Enhanced Swap Sequence-Based Particle Swarm Optimization Algorithm to Solve TSP一种改进的基于Swap序列的粒子群算法求解TSP.png)
IEEE ACCESS
OAAI
IEEE ACCESSIF3.6
OAAI分享收藏A disjunctive graph-based metaheuristic for flexible job-shop scheduling problems considering fixture shortages in customized manufacturing systems一种基于析取图的元启发式算法，用于解决定制化制造系统中考虑夹具短缺的柔性作业车间调度问题
PREAI
分享收藏MGA-TSP: modernised genetic algorithm for the travelling salesman problemMga-tsp：用于旅行商问题的现代化遗传算法
PREAI
分享收藏
查看更多内容