A Study of Genetic Algorithms for use in Combinatorial Optimization Problems

I. Introduction

The purpose of this project is to study how genetic algorithms could be used to solve combinatorial optimization problems.

Some of the aspects of GAs that I discuss are:

1. Use of different crossover methods

2. Use of different mutation operations

3. Use of more than two parents

4. Use of migrations and parallel populations

II. The problem

The problem that my genetic algorithm will be solving is the Quadratic Assignment Problem (QAP). It is a combinatorial optimization problem involving the placing of a number of facilities at a number of locations with various distance and flow matrices. The traveling salesman problem, for example, is an instance of QAP. Another problem which falls into the same category is minimizing the amount of wire needed to manufacture an electronic circuit under given specification. For more information about the problem, visit http://www.opt.math.tu-graz.ac.at/qaplib/#intro. This website also offers a large number of problem instances which I used to test my program.

III. Implementation

I implemented a parallel GA utilizing several populations evolving in parallel. I introduced various crossover and mutation operators, as well as population migrations to increase diversity as populations converge. More details on the implementation details will be available in the upcoming paper.

IV. Results

So far I have tested my program on a number of problem instances of sizes n < 25 and the results have been promising – for many of them my GA was capable of finding the optimal solution in a short amount of time. A more detailed report on the results is coming soon!

V. Paper

http://www.cs.iastate.edu/~jsinapov/GA/GA_QAP.pdf