Determınıng The Best Settıngs for the Operators and Parameters of Genetıc Algorıthms: A Methodology and Its Applıcatıon to Travelıng Salesperson Problem

Abstract

Genetic Algorithms (GAs) are heuristic algorithms that are used to approximate the optimal solutions of optimization problems. They are inspired by the theory of natural evolution, where a population of solutions evolves through generations and only the fittest individuals survive at the end. GAs perform very well in many optimization problems in terms of approximation quality and run time. However, a typical GA has several operators such as mutation and crossover, and parameters such as population size and generation number that affect the performance of the GA significantly. In the literature, the operators and parameters of GAs are set based on either the previous experiences of users or trial-error experiments since finding optimum settings of GAs is quite difficult.

In this thesis, a methodology is developed for effectively setting the operators and parameters of GAs. Hence, the best settings that will exploit the potential of the used genetic algorithm can be determined. Typically, performance of a GA is evaluated based on two criteria: (1) approximation quality and (2) run time. Approximation quality of an algorithm is determined based on the closeness of the solution found by the algorithm to the optimal solution. Run time is measured by the computational time the algorithm consumes until termination. In general, there are trade-offs between these two criteria, i.e. higher approximation quality requires more run time, and a GA is expected to find a solution with high approximation quality in a short time. Settings of the operators and parameters affect both criteria, and different settings can be advantageous in terms of different criteria. Therefore, we model the problem of effectively setting the parameters of a GA as a multi-objective optimization problem, using approximation quality and run time as the objectives.

In the thesis, we employ a multi-objective evolutionary algorithm (MOEA) to solve the problem and discover the trade-offs between approximation quality and run time of GAs. MOEAs are population-based heuristics that mimic natural evolution process and find a well-converged and well-diversified set of nondominated solutions. In our approach, each solution of MOEA represents a setting for operators and parameters of the GA considered. To evaluate a solution in the population, the GA is run using the settings defined in the solution. The fittest settings in terms of approximation quality and run time survive through generations. At the end, a set of settings, each of which is better on another criterion, is found.

The developed methodology is demonstrated on travelling salesperson problems (TSP). A GA that is used to solve TSP is selected. Several alternatives for operators and parameters are considered for the GA, and the best settings are investigated by experimenting on 31 TSP instances selected from the literature. The set of best settings is searched using NSGA-II, a well-known MOEA. Then a greedy heuristic is developed to help decision makers to reduce the size of the set of final solutions based on their preferences.