Solving the Quadratic Assignment Problems by a Genetic Algorithm with a New Replacement Strategy
This paper proposes a genetic algorithm based on a
new replacement strategy to solve the quadratic assignment problems,
which are NP-hard. The new replacement strategy aims to improve the
performance of the genetic algorithm through well balancing the
convergence of the searching process and the diversity of the
population. In order to test the performance of the algorithm, the
instances in QAPLIB, a quadratic assignment problem library, are
tried and the results are compared with those reported in the literature.
The performance of the genetic algorithm is promising. The
significance is that this genetic algorithm is generic. It does not rely on
problem-specific genetic operators, and may be easily applied to
various types of combinatorial problems.