An adaptive hybrid genetic algorithm for the three-matching problem

This paper presents a hybrid genetic algorithm (GA with an adaptive applica tion of genetic operators for solving the three-matching problem (3MP), whi ch is an NP-complete graph problem. In the 3MP, we are searching for the pa rtition of a point set into triplets of minimal total cost, where the cost of a triplet is the Euclidean length of the minimal spanning tree of the th ree points. The problem can be viewed as a special case of grouping and fac ility location problems. One common problem with GA's applied to hard combinatorial optimization pro blems like the 3MP is to incorporate problem-dependent local search operato rs into the CA efficiently in order to find high-quality solutions. Small i nstances of the problem can be solved exactly, but for large problems, we m ust rely on local optimization. We introduce several general/heuristic crossover and local hillclimbing ope rators for the 3MP, and apply adaptation at the level of choosing among the operators. Our GA combines these operators to form an effective problem so lver. The algorithm is hybridized as it incorporates local search heuristic s, and it is adaptive as the individual recombination/improvement operators are fired according to their on-line performance. The test results show that this approach gives approximately the same or ev en slightly better results than our previous, fine-tuned GA without adaptat ion. The hybrid CA gives better performance than an implementation of a gro uping GA for the partitioning problem under consideration. The major advant age of the new algorithm is that the adaptive combination of genetic and lo cal search operators eliminates a large set of parameters of the traditiona l GA, making the method more robust, and it presents a convenient way to bu ild a hybrid problem sol, er. We therefore also suggest this approach for o ther hard optimization problems.