Genetic multi-step search in interpolation and extrapolation domain

The deterministic Multi-step Crossover Fusion (dMSXF) is an improved crossover method of MSXF which is a promising method of JSP, and it shows high availability in TSP. Both of these crossover methods introduce a neighborhood structure and distance in each permutation problem and perform multi-step searches in the interpolation domain focusing on inheritance of parents' characteristic. They cannot work effectively when parents stand close each other since they search in interpolation domain. Therefore in the case of the MSXF, the Multi-step Mutation Fusion (MSMF), which is the multi-step search in the extrapolation domain, is combined as the supplementary search to improve its search performance. On the other hand, the search mechanism for acquisition of characteristics, such as MSMF, is not applied to dMSXF. In this paper, we introduce a deterministic MSMF (dMSMF) mechanism as complementary multi-step extrapolation search. We apply dMSXF+dMSMF to TSP and JSP, which have structural difference between their landscapes. Through the experiments it was shown that the deterministic multi-step search in interpolation/extrapolation domain performed effectively in combinatorial problems.