Dynamic sub-route-based self-adaptive beam search Q-learning algorithm for traveling salesman problem.

Area of Science:

• Artificial Intelligence
• Operations Research
• Computer Science

Background:

• The Traveling Salesman Problem (TSP) is a complex combinatorial optimization challenge.
• Traditional Q-learning (QL) for TSP suffers from slow convergence and low accuracy.
• Existing reinforcement learning (RL) methods require enhancement for complex problem-solving.

Purpose of the Study:

• To introduce a novel dynamic sub-route-based self-adaptive beam search Q-learning (DSRABSQL) algorithm for solving the TSP.
• To improve upon the Q-learning algorithm by addressing its limitations in convergence speed and solution accuracy.
• To evaluate the effectiveness of DSRABSQL against other advanced algorithms and analyze the contribution of its key strategies.

Main Methods:

• Developed a DSRABSQL algorithm integrating RL with local search, building on Q-learning.
• Incorporated four key strategies within the QL framework: a weighting function-based reward matrix, a power function-based initial Q-table, a self-adaptive ε-beam search, and a new Q-value update formula.
• Introduced a dynamic sub-route optimization strategy outside the QL framework to enhance sub-route solutions.

Main Results:

• DSRABSQL demonstrated significantly superior performance compared to QL, ABSQL, a whale optimization algorithm, and other RL algorithms.
• Experimental analysis confirmed the substantial contributions of the dynamic sub-route optimization and self-adaptive ε-beam search strategies across various instance scales.
• A synergistic effect was observed between the four internal QL strategies, with collaboration increasing with problem scale.

Conclusions:

• The proposed DSRABSQL algorithm offers a highly effective reinforcement learning framework for the Traveling Salesman Problem.
• The dynamic sub-route optimization and self-adaptive ε-beam search are critical components driving the algorithm's enhanced performance.
• The findings highlight the potential of combining advanced RL techniques with local search for complex optimization tasks.