Edge histogram based sampling with local search for solving permutation problems

Abstract

A basic scheme for solving permutation problems in the framework of probabilistic model-building genetic algorithms (PMBGAs) that uses edge histogram based sampling techniques was reported in [23]. Two sampling algorithms – sampling without template, and the sampling with template were presented. In this paper, we combine local search heuristics with those sampling algorithms to solve the traveling salesman problem (TSP). We tested two types of heuristics; one is a simple heuristic called 2-OPT, and the other is a sophisticated Lin-Kernighan heuristic. The results show that edge histogram based sampling with these heuristics improve the performance significantly, and can solve large problems having thousands of cities fairly well. The algorithm is thus seen to be scalable.