Open AccessA New Recombination Operator for the Genetic Algorithm Solution of the Quadratic Assignment Problem
Author(s) -
Umut Tosun
Publication year - 2014
Publication title -
procedia computer science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.334
H-Index - 76
ISSN - 1877-0509
DOI - 10.1016/j.procs.2014.05.394
Subject(s) - crossover , quadratic assignment problem , computer science , tabu search , heuristics , travelling salesman problem , algorithm , partition (number theory) , mathematical optimization , operator (biology) , genetic algorithm , assignment problem , combinatorial optimization , set (abstract data type) , chromosome , mathematics , artificial intelligence , combinatorics , biochemistry , chemistry , repressor , transcription factor , gene , programming language
The Quadratic Assignment Problem (QAP) is a well known combinatorial optimization problem with a diverse set of applications. It can be transformed into many problems such as the travelling salesman, weapon target assignment, and query optimization in distributed databases. Exhaustive search methods are inadequate to solve large data sets. Genetic algorithms and tabu search meta-heuristics may provide near optimal solutions for large QAP instances taking a reasonable time to complete. In this paper, we present a new recombination operator based on Order-1 crossover algorithm. The suggested approach runs quick sort partitioning algorithm to generate different chromosomes from partitions. The minimum cost partition produces offsprings with the other chromosome. The proposed approach shows outstanding performance especially for instance sizes smaller than 50 with respect to the optimal results proposed in QAPLIB
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom