A Hybrid Algorithm For The Maximally Diverse Grouping Problem

Maximally diverse grouping problem(MDGP) is combinatorial optimization problem that comes from practice. MDGP consists of forming maximally diverse groups from a given set of elements and their distance matrix. MDGP has many applications in the real world and has been proved to be a NP-hard problem. The trajectory analysis shows that the tabu search with strategic oscillation algorithm proposed for MDGP is lack of intensification of search, hence there is further improvement space to explore in solving MDGP.Based on the existing problem, a hybrid algorithm for MDGP is proposed. This hybrid algorithm makes use of tabu search as a component for intensification. A proper perturbation will make the search escape from the current local solution space and explore more solution space when the search gets stuck in local solution space. Biased sampling in the solution space and perturbation flowed by tabu search with a certain probability make the search concentrate on good solution space and enhance the stability of algorithm. A qualitative analysis on the intensification and diversification of search derives the dependencies among the parameters of the depth of search, the strength of perturbation, the length of tabu list and the amount of sampling, then a reasonable configuration of parameters is proposed. This strategy and configuration of parameters strengthens the intensification and exploration of search.The experiment results show that the hybrid algorithm is much better than the tabu search with strategic oscillation and still has advantage when compared with the artificial bee colony algorithm for MDGP. Furthermore key strategy and the configuration of parameters are also analyzed and the results reveal the rationality of them.