This repository will contain an implementation of the simulated annealing algorithm, for an integer variables case. Our program adjust the simulated annealing algorithm presented here: https://github.com/Freddy-94/Simulated-Annealing-Algorithm-Real-Vars-Case to the case where we consider a cost function of Integer variables, and provide approximate solutions for the quadratic assignment problem (https://en.wikipedia.org/wiki/Quadratic_assignment_problem), for problems of size: 9!, 12!, 15!, and 30!
https://en.wikipedia.org/wiki/Quadratic_assignment_problem
In order to adjust our previous algorithm, we implement 3 different "mutation" operations that generate a new neighbor of the random start solution. This operataions are:
- Swap operator: Two random indexes of the solution vector are taken, and their corresponding values are swaped:
- Reverse operator: Two random indexes of the solution vector are taken, and the values of this "sub-vector" are reversed:
- Insersion operator: A random element of the vector, along with a random index are taken, and the random element taken is inserted in the random index taken, moving the other elements of the vector:
The program needs a configuration file that needs to be passed in the terminal. The data in this file consists of the flux and distance matrices. Now, if for example, this config file is called "tai15.dat", then, you only need to locate in the directory where the QAP module and the mentioned config file is located, and run the command:
python QAP.py < tai9.dat
- swap_operator -> swap operator
- reverse_operator -> reverse operator
- insersion_operator -> insersion operator
- cost_function_perm -> cost function implementation described above
- acceptance_probability -> Acceptance probability criteria
- see_annealing -> Plot solutions, costs, vs. number iterations, respectively
- annealing -> Simulated annealing algorithm
Example of results obtained with the SWAP operator, for a problem of 9! size:
