Resolving Quadratic Assignment Problem with Genetic Algorithm

To run clone repo, go to src folder and run

python main.py

In config.py you can find following configuration options:

INPUT_FILE = "had12.dat"
CROSSOVER_PROBABILITY = 0.7
MUTATION_PROBABILITY = 0.08
POPULATION_SIZE = 100
NUMBER_OF_GENERATIONS = 100
DRAW_VISUALIZATION = True
DRAW_CHART = True

Feel free to experiment with them.

• Red color of line means long distance, green one - short
• Thick line means big value of flow (aka cost), thin one - small

Both values are in context of particular distance and flow matrices

In short: thin green is better than thick red

The objective of the Quadratic Assignment Problem (QAP) is to assign n facilities to n locations in such a way as to minimize the assignment cost. The assignment cost is the sum, over all pairs, of the flow between a pair of facilities multiplied by the distance between their assigned locations.

Source and more information: neos-guide.org

Dataset available in res/data are taken from http://anjos.mgi.polymtl.ca/qaplib/inst.html#HRW

Authors: S.W. Hadley, F. Rendl and H. Wolkowicz

In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection. More

Some fragments of this implementation were inspired by code of mgr Filip Bachura from Wroclaw University of Science and Technology