A greedy genetic algorithm for the quadratic assignment problem

A greedy genetic algorithm for the quadratic assignment problem

0.00 Avg rating0 Votes
Article ID: iaor20011472
Country: United Kingdom
Volume: 27
Issue: 10
Start Page Number: 917
End Page Number: 934
Publication Date: Sep 2000
Journal: Computers and Operations Research
Authors: , ,
Keywords: quadratic assignment, genetic algorithms
Abstract:

The Quadratic Assignment Problem (QAP) is one of the classical combinatorial optimization problems and is known for its diverse applications. In this paper, we suggest a genetic algorithm for the QAP and report its computational behavior. The genetic algorithm incorporates many greedy principles in its design and, hence, we refer to it as a greedy genetic algorithm. The ideas we incorporate in the greedy genetic algorithm include (i) generating the initial population using a randomized construction heuristic; (ii) new crossover schemes; (iii) a special purpose immigration scheme that promotes diversity; (iv) periodic local optimization of a subset of the population; (v) tournamenting among different populations; and (vi) an overall design that attempts to strike a balance between diversity and a bias towards fitter individuals. We test our algorithm on all the benchmark instances of QAPLIB, a well-known library of QAP instances. Out of the 132 total instances in QAPLIB of varied sizes, the greedy genetic algorithm obtained the best known solution for 103 instances, and for the remaining instances (except one) found solutions within 1% of the best known solutions.

Reviews

Required fields are marked *. Your email address will not be published.