A Hierarchical Simple Probabilistic Population-Based Algorithm Applied to the Dynamic TSP
Edward Kupfer, Hoang Thanh Le, Johanna Zitt, Ying-Chi Lin, Martin Middendorf · 2021 IEEE Symposium Series on Computational Intelligence (SSCI) · 2021
This work presents a Hierarchical Simple Probabilistic Population-Based algorithm (H-SPPBO) which is a hierarchical version of SPPBO. The SPPBO framework is a general scheme to design population-based algorithms for combinatorial (and other) optimization problems. The proposed H-SPPBO algorithm uses a hierarchical tree structure to make it particularly suitable for dynamic (combinatorial) optimization problems. The hierarchy is used to detect dynamic changes. H-SPPBO adapts to changes by discarding low-quality solutions whenever a change is detected. The H-SPPBO is applied to the dynamic Traveling Salesperson Problem (DTSP). The experimental results show that the hierarchical tree structure and the number of swap operations within that tree can be used as an indicator for the occurrence of dynamic changes. It is discussed how the performance of the algorithm is influenced by the threshold for detecting changes and by the number of solutions that are reset when a change is detected. The best results are obtained with medium to high thresholds and when only a certain subset of the solutions is reset.