Scholarlink

<p>This study presents a novel <i>Essential Mutation (EM) framework</i> that enhances the performance of evolutionary algorithms for solving combinatorial optimization problems, with a focus on the Traveling Salesman Problem (TSP). The core innovation of proposed EM lies in its ability to preserve essential structural components, or “essential edges”, by analyzing their recurring presence in high-fitness solutions. Unlike traditional mutation operators, our proposed EM model introduces a <i>fitness-informed strategy</i> that selectively avoids mutating edges with high contribution to solution quality, effectively balancing exploration and exploitation. The importance of each edge is dynamically evaluated using population statistics and updated in each generation based on a tunable essential rate. Although the framework is algorithm-agnostic, it is integrated into a Genetic Algorithm (GA) in this work for validation. Extensive experiments on twelve TSPLIB benchmark instances compare EM against three widely used mutation operators: Swap Mutation (SM), Reverse Mutation (RM), and Center Inverse Mutation (CIM). Results show that our proposed EM model consistently achieves superior solution quality and faster convergence, particularly for larger instances. A Wilcoxon signed-rank test confirms that these improvements are statistically significant compared to RM and CIM (<i>p</i> &lt; 0.01), while remaining competitive with SM. Although the proposed EM model incurs moderate overhead, its structural awareness enables more effective search guidance. Overall, this framework introduces a generalizable mutation strategy that improves evolutionary performance through adaptive edge preservation and is broadly applicable to other combinatorial problems.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Essential mutation framework for solving travelling salesman problem

  • 期刊论文

  • 发表日期：

    2025年11月21日

查看全文
  • Iyad Abu Doush,
  • Ra’ed M. Al-Khatib,
  • Bader Alotaibi,
  • Salem Alhatamleh

摘要

This study presents a novel Essential Mutation (EM) framework that enhances the performance of evolutionary algorithms for solving combinatorial optimization problems, with a focus on the Traveling Salesman Problem (TSP). The core innovation of proposed EM lies in its ability to preserve essential structural components, or “essential edges”, by analyzing their recurring presence in high-fitness solutions. Unlike traditional mutation operators, our proposed EM model introduces a fitness-informed strategy that selectively avoids mutating edges with high contribution to solution quality, effectively balancing exploration and exploitation. The importance of each edge is dynamically evaluated using population statistics and updated in each generation based on a tunable essential rate. Although the framework is algorithm-agnostic, it is integrated into a Genetic Algorithm (GA) in this work for validation. Extensive experiments on twelve TSPLIB benchmark instances compare EM against three widely used mutation operators: Swap Mutation (SM), Reverse Mutation (RM), and Center Inverse Mutation (CIM). Results show that our proposed EM model consistently achieves superior solution quality and faster convergence, particularly for larger instances. A Wilcoxon signed-rank test confirms that these improvements are statistically significant compared to RM and CIM (p < 0.01), while remaining competitive with SM. Although the proposed EM model incurs moderate overhead, its structural awareness enables more effective search guidance. Overall, this framework introduces a generalizable mutation strategy that improves evolutionary performance through adaptive edge preservation and is broadly applicable to other combinatorial problems.