Edge histogram based sampling with local search for solving permutation problems

Article type: Research Article

Authors: Tsutsui, Shigeyoshi^{a; *} | Pelikan, Martin^b | Ghosh, Ashish^c

Affiliations: [a] Department of Management Information, Hannan University, 5-4-33, Amamihigashi, Matsubara Osaka 580-8502 Japan | [b] Department of Math and Computer Science, University of Missouri at St. Louis, 8001 Natural Bridge Rd., St. Louis, MO 63121, USA | [c] Machine Intelligence Unit, Indian Statistical Institute, 203 B. T. Road, Kolkata 700 108, India

Correspondence: [*] Corresponding author. Tel.: +81 72 332 1224; Fax: +81 72 336 2633; E-mail: tsutsui@hannan-u.ac.jp

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.

Keywords: Probabilistic model-building genetic algorithms, edge histogram based sampling algorithm, 2-OPT, lin-kernighan heuristic, traveling salesman problem

DOI: 10.3233/HIS-2006-3102

Journal: International Journal of Hybrid Intelligent Systems, vol. 3, no. 1, pp. 11-22, 2006