ScienceAsia 33 (2007): 215-222|doi: 10.2306/scienceasia1513-1874.2007.33.215

Exploration of Genetic Parameters and Operators through Travelling Salesman Problem

Pupong Pongcharoen*, Warattapop Chainate and Peeraya Thapatsuwan

 
ABSTRACT: In this paper, we describe the use of advanced statistical design in the screening experiment to configure parameters and operators of genetic algorithm (GA), which applied to find a shortest distance in a classical travelling salesman problem (TSP). Due to the number of GA parameters, operators and its levels considered in the experiment, the total numbers of program executions required by the proposed design (in which an one-ninth fractional factorial experimental design is embedded within a full Latin Square) were dramatically decreased from 6,561 (using full factorial design) to 81 runs for each replication. The analysis of simulation results based on 36 cities TSP in Thailand indicated that all GA parameters and operators except the probability of mutation were statistically significant. Although the mutation operator was significant, the results were however not particularly sensitive to the degree of mutation with 95% confident level. The appropriate settings of these parameters and operators found in the screening experiment were then applied to solve 76 cities travelling problem in the sequential experiment, which aimed to compare the results obtained from the GA using the best setting found in this work and those results with settings suggested in previous research. It was found that the distance obtained from GA using our finding on the parameters’ setting outperformed the settings suggested by other research.


KEYWORDS: Genetic Algorithm, Travelling Salesman Problem, Experimental Design, Latin Square.

Download PDF