Research On Parameter Tuning Strategies For Metaheuristics Based On Fitness Landscape

Metaheuristic algorithm shows its superiority in solving complex combinatorial optimization problems in real life.Common algorithms include tabu search,simulated annealing,genetic algorithm,iterative local search and so on.These algorithms adopt different strategies based on local search to make the algorithm escape from local optimum.The neighborhood operator used in local search defines the adjacency relationship between the solutions in the search space of the algorithm.The improper neighborhood operator will make the search invalid,so the optimization of neighborhood operator directly affects the performance of meta-heuristic algorithm.In order to better combine the operator optimization strategy with the structural characteristics of the problem and make up for the shortcomings of the existing operator optimization strategy,this paper attempts to optimize the neighborhood operators of the meta-heuristic algorithm based on the fitness landscape.Fitness landscape originates from theoretical biology.It is proposed by geneticists when using mathematical models to understand the evolutionary mechanism of individual organisms.The model is based on optimization problem solution,neighborhood operator and fitness function,and can vividly describe the structure of the problem.Therefore,this paper measures the characteristics of fitness landscape and optimizes the neighborhood operators based on fitness landscape analysis.The main research contents are as follows:(1)In view of the important role of logistics distribution in logistics system,this paper takes vehicle routing problem as an example,and establishes the fitness landscape model of vehicle routing problem based on two neighborhood operators,inversion and interchange.(2)Considering the characteristics of the solution of vehicle routing problem,the distance space is established and the relevant entropy is defined.The characteristics of fitness landscape are analyzed more comprehensively from the angles of average distance,average step length,autocorrelation function,ruggedness and local optimal solution.(3)Multidimensional Scaling is used to project the reduced dimension of vehicle routing problem onto a two-dimensional plane,and then Delaunay triangulation is used to visualize the results of fitness landscape analysis.(4)Four basic meta-heuristic algorithms,i.e.iterative local search,simulated annealing,genetic algorithm and tabu search based on inversion or interchange operators,are constructed respectively.By comparing their performance in a given example,the effectiveness of the neighborhood operator optimization of meta-heuristic algorithm based on fitness landscape is verified.