Performance Analysis of TSP Training Instance Generation Methods in Policy-Based Hyper-Heuristic Optimization Framework

The Policy-Based Hyper-Heuristic Optimization framework (PHH), which utilizes reinforcement learning to solve combinatorial optimization problems, has demonstrated promising results in prior studies. However, training PHH models with real problem instances can be resource-intensive and challenging to obtain. To address this issue, this paper explores the effects of different randomization methods for generating training instances in the context of the traveling salesman problem (TSP). Seven randomization methods, namely grid, uniform, square, circle, Gaussian, wave, and mixed, were employed to generate TSP instances. The PHH models were trained using these instances, and their performance was evaluated on unseen TSP instances from TSPLIB. Experimental results indicate that training with TSP instances generated by the square method consistently achieved the lowest travel distances across small, medium, and large test instances. This research contributes to the understanding of instance-generation techniques for combinatorial optimization problems and provides insights for designing efficient hyper-heuristic frameworks.