How Do Dynamic Events Change the Fitness Landscape of Traveling Salesman Problems?
研究了动态旅行商问题中节点增加、删除和权重变化三种事件如何影响问题的适应度景观，发现权重变化会引入更多局部最优并缩小全局最优吸引域，提示算法需增强探索能力。
Traveling salesman problem (TSP) is a combinatorial optimization problem, serving as basis for many real-world applications (e.g., transportation planning, circuit board design, and DNA sequencing). In TSP, it is common to encounter some dynamic events, for example, traffic jam, and roadworks in transportation planning. To deal with such dynamic TSP (DTSP) scenarios, numerous techniques have been designed over decades. In this article, we take a different perspective to study DTSP. Instead of focusing only on algorithm design for DTSP, we investigate how dynamic events in DTSP affect its fitness landscape (e.g., the location of local optimal solutions and the ruggedness level of search space). We consider three dynamic events, including node addition, node deletion and weight changes, and analyze how they affect the TSP with respect to the overall landscape structure and solution optimality. Experimental results show that the weight change event has great effect on the problem’s fitness landscape, introducing more local optima and reducing the basin of attraction for the global optimum. This may suggest that search algorithms need to have stronger exploration capability when handling weight change dynamic events. Furthermore, our experimental studies also demonstrate that the dynamic solution adaptation strategy on the original global optimum is effective for tracking the new optimum after dynamic changes.