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