/QAP

Diferent solutions to the quadratic assignment problem for my metaheuristic practices

Primary LanguageRacketGNU General Public License v3.0GPL-3.0

QAP

Diferent solutions to the quadratic assignment problem for my metaheuristic practices

Implemented algorithms

  • Greedy
    • Flow and distance potentials
  • Local search
    • Best-first with DLB mask
    • Best neighbour
    • Variable neighbourhood descent
    • Short term memory tabu search
  • Genetic algorithms
    • Generational with positional crossover
    • Generational with PMX crossover
    • Steady-State with positional crossover
    • Steady-State with PMX crossover
  • Memetic algorithms
    • Generational with positional crossover and local search over all the population every 10 generations
    • Generational with PMX crossover and local search over all the population every 10 generations
    • Generational with positional crossover and local search over a random 10% of the population every 10 generations
    • Generational with PMX crossover and local search over a random 10% of the population every 10 generations
    • Generational with positional crossover and local search over the best 10% of the population every 10 generations
    • Generational with PMX crossover and local search over the best 10% of the population every 10 generations

Usage

racket qap.rkt [--help] [--csv-output | --debug-output] [-s seed] [-m max_evaluations] [-r repetitions_per_file] [--greedy | --local-search-bf | --local-search-bn | --local-search-vnd | --stm-tabu-search | --genetic-gen-pos | --genetic-gen-pmx | --genetic-st-pos | --genetic-st-pmx | --memetic-all-pos | --memetic-all-pmx | --memetic-rand-pos | --memetic-rand-pmx | --memetic-best-pos | --memetic-best-pmx] file1...

Example:

racket qap.rkt --csv-output -s 100 -m 20000 -r 50 --local-search-bf data/*.dat

Options

  • --help Prints help
  • --csv-output Prints the results in csv format
  • --debug-output Prints a trace of the algorithm
  • -s, --seed Seed for the random numbers generator
  • -m, --max-evaluations Maximum number of solution evaluations before stop the search, the default value is 50000
  • -r, --repetitions Executions of the algorithm on each file, the results are the arithmetic mean of all executions. The default value is 1
  • --greedy Executes the greedy algorithm
  • --local-search-bf Executes the local search with best-first selection algorithm
  • --local-search-bn Executes the local search with best neighbour selection algorithm
  • --local-search-vnd Executes the local search with variable neighbourhood descent
  • --stm-tabu-search Executes the short term memory tabu search
  • --genetic-gen-pos Executes a generational genetic with positional crossover
  • --genetic-gen-pmx Executes a generational genetic with PMX crossover
  • --genetic-st-pos Executes a steady-state genetic with positional crossover
  • --genetic-st-pmx Executes a steady-state genetic with PMX crossover
  • --memetic-all-pos Executes a memetic with positional crossover and local search over all the population
  • --memetic-all-pmx Executes a memetic with PMX crossover and local search over all the population
  • --memetic-rand-pos Executes a memetic with positional crossover and local search over a random 10% of the population
  • --memetic-rand-pmx Executes a memetic with PMX crossover and local search over a random 10% of the population
  • --memetic-best-pos Executes a memetic with positional crossover and local search over the best 10% of the population
  • --memetic-best-pmx Executes a memetic with PMX crossover and local search over the best 10% of the population