Effective Heuristic Algorithms For Minimum Differential Dispersion Problem

The minimum differential dispersion problem is a combinatorial optimization problem with numerous relevant applications,which has been proved to be a NP-hard problem.Given n elements and distances between pairs of elements,the goal of this problem is to determine a subset of m(m<n)so that the difference of the selected elements is minimized.In this way,the balance of the selected elements is guaranteed by minimizing the differences between the selected elements.This problem is widely used in real life.For example,it is necessary to ensure the fairness of the location selection of public facilities in order to make all people have access to public measures such as schools,parks and hospitals in the location selection of urban public facilities.In addition,it has great application value in the selection of homogeneous groups,equity based measures in network flows and densest k-subgraph identification.Therefore,this problem has a wide range of applications in real life and production so that the research on this problem has an important value for solving the actual problem.Based on IDTS algorithm and HEAD algorithm,this paper proposes a strong perturbation-driven tabu search algorithm(SPDTS)and a two-individual hybrid evolutionary algorithm(TIHE).The SPDTS algorithm adopts a constrained neighborhood,a solution-based tabu strategy and a strong disturbance search mechanism.Different from the typical tabu attribute strategy,the solution-based tabu strategy makes the search process more centralized.At the same time,hash functions can quickly determine the tabu state of the solution and the strong disturbance search mechanism an make the search area jump to a further search space.The TIHE algorithm uses tabu search and cross operation within the population to search for better solutions,which ensures the algorithm's intensification and diversification.In the 250 benchmark instances,35 of them are improved by strong perturbationdriven tabu search algorithm(SPDTS)and 101 of them are the same as the current optimal solution.The two-individual hybrid evolutionary algorithm(TIHE)improves 44 instances and 103 instances are the same as the current optimal solution.By testing and comparing the effects of tabu strategy and disturbance strategy based on the search ability of the algorithm,the importance of the two strategies is proved.In addition,it has certain value for solving other dispersion problems due to the generality of the framework of the two-individual hybrid evolutionary algorithm(TIHE).