-
Notifications
You must be signed in to change notification settings - Fork 12
TabuSearchTutorial
Stefan Vigerske edited this page Feb 28, 2020
·
2 revisions
NB: this tutorial is for version 0.4.x, updated tutorial for version 0.5.x is in the works
The N-Queens problem, a generalization of the 8-queens problem, consists in placing N queens on a NxN checkerboard so that none of them is able to capture any other using a single chess queen's movement. Thus, a solution requires that no two queens share the same row, column, or diagonal. A solution exists only for n=1 or n >= 4.
Note that this tutorial is intended as an example code on an extremely simple test problem. If you are interested in solving the N-Queens problem there are better ways of doing it. E.g. there are constructive solutions to the N-Queens problem that are much faster.
To compile the N-Queens example you need to first checkout and install METSlib 0.4.x
You can get it using subversion:
$ svn co --branch=stable/0.4 https://github.com/coin-or/metslib.git metslib-0.4
Then you must compile and install the METSlib core:
$ cd metslib-0.4
$ ./autogen.sh
$ make
$ sudo make install
Now, in your own folder, make a queens.cc file with the following content:
#include <iostream>
#include <valarray>
#include <algorithm>
#include <metslib/mets.h> // Include the metslib main header.
using namespace std;
using namespace mets; // the namespace for mets classes
int nmove = 0, tmove = 0; // take track of made moves
// The problem is well known and has n! solutions, most of which are not correct.
// A solution is correct only if no queen can eat another queen in one move.
class queens : public mets::feasible_solution
{
friend class queens_moves; // queens move knows a lot about us, it must.
friend ostream& operator<<(ostream& os, const queens& q);
public:
// take a random permutation of columns (we assume every queen must be on a different
// row and reduce the problem to the shuffling of the columns).
explicit queens(int dim) : feasible_solution(), dim_m(dim), sol_m(), rng() {
vector<int> init(dim);
for(int i=0; i < dim; i++) init[i] = i;
random_shuffle(init.begin(), init.end(), rng); /*** \label{lst:queensstart} */
sol_m.resize(dim);
for(int i=0; i < dim; i++) sol_m[i] = init[i];
}
// tabu search needs a copy constructor
// (the copy ctor must be implemented)
explicit queens(const queens& other)
: feasible_solution(other), dim_m(other.dim_m), sol_m(other.sol_m), rng() {
}
// tabu search needs to copy solutions
// (this must be implemented)
void copy_from(const feasible_solution& other) {
const queens& o = static_cast<const queens&>(other);
dim_m = o.dim_m;
sol_m = o.sol_m;
}
// The cost function counts queens under attack.
// (this must be implemented)
gol_type cost_function() const { /*** \label{lst:queenscost} */
int cost = 0; // un int basta per problemi fino a 500 regine ed oltre
for(int i = 0; i < dim_m - 1; i++)
for(int j = 1; j < dim_m - i; j++) {
if(sol_m[i+j] == sol_m[i]-j or sol_m[i+j] == sol_m[i]+j) cost++;
}
return cost;
}
// the following methods are your own model manipulation functions
// swap two columns
void swap(int a, int b) {
int tmp = sol_m[a];
sol_m[a] = sol_m[b];
sol_m[b] = tmp;
}
// problem dimension (m x m checkboard)
int dim() const { return dim_m; }
protected:
int dim_m;
valarray<int> sol_m; // valarrays are as fast as C arrays, but much nicer.
mets::random_integer rng;
};
// ostream operator to print a solution on a ostream (and cout)
ostream& operator<<(ostream& os, const queens& q) {
for(int ii = 0; ii < q.dim_m; ++ii) {
for(int jj=0; jj < q.sol_m[ii]; jj++)
os << ". ";
os << "Q ";
for(int jj = q.sol_m[ii] + 1; jj < q.dim(); jj++)
os << ". ";
os << endl;
}
os << endl;
for(int ii = 0; ii < q.dim_m; ++ii) {
os << "Q";
if(ii >= 26) os << (char)('a'-1+(ii)/26);
os << (char)('a'+ii%26);
os << (q.sol_m[ii]+1);
if(ii < q.dim_m-1) os << ", ";
}
os << endl;
return os;
}
// Implementation of the only move type we need, the swap move.
// A move class represents a type of move and an instance of this
// class is a particular move that can be made.
class queens_swap : public mets::mana_move
{
friend class queens_moves;
public:
// create a swap move between column "a" with column "b"
// this doesn't know on wich solution will be applyed,
// and is an abstract move.
queens_swap(int a, int b) : a_m(a), b_m(b) { }
// swap column "a" with column "b" on the given solution instance
void apply(feasible_solution& s) {
queens& q = static_cast<queens&>(s);
q.swap(a_m, b_m);
tmove++; nmove++;
}
// "un"swap column "a" with column "b" on the given solution instance
// unapply moves can be called only right after the relative apply, so
// if you need to you can memorize the move in apply and put it back here.
// Anyway knowing how to do the move backwars make the whole thing a lot faster.
void unapply(feasible_solution& s) {
queens& q = static_cast<queens&>(s);
q.swap(b_m, a_m);
nmove--;
}
// we need to copy moves
mets::mana_move* clone() const { return new queens_swap(a_m, b_m); }
// an hash used by the hash map in simple_tabu_list
// this is an hash code for the move, it should be
// "fairly" unique for each different move.
size_t hash() const { return a_m << 16 ^ b_m; }
// comparison operator, simple_tabu_list needs this to know
// if two moves are the same.
bool operator==(const mana_move& o) const {
const queens_swap& qs = static_cast<const queens_swap&>(o);
return (a_m == qs.a_m && b_m == qs.b_m);
}
private:
int a_m;
int b_m;
};
// neighborhood generator.
class queens_moves : public mets::move_manager
{
public:
// make "max" moves.
explicit queens_moves(int max) : mets::move_manager(), rng(), mm(max) {
for(int ii = 0; ii < mm; ++ii) moves_m.push_back(new queens_swap(0,0));
}
// fill all the moves with random values
void refresh(feasible_solution& s) {
queens& q = static_cast<queens&>(s);
for(int ii = 0; ii < mm; ++ii) {
int col = rng(q.dim());
int ncol = rng(q.dim());
while(ncol == col) ncol = rng(q.dim()); // use different values
static_cast<queens_swap*>(moves_m[ii])->a_m = col;
static_cast<queens_swap*>(moves_m[ii])->b_m = ncol;
}
}
protected:
mets::random_integer rng;
int mm;
};
// an observer/listener on the algorithm status
// that simply prints advance status
class tobserver : public search_listener
{
public:
tobserver() : search_listener() {}
void update(mets::abstract_search * as) {
if(as->step() == 0)
cerr << nmove << " " <<as->working().cost_function() << endl;
}
};
// print usage information
void usage() {
clog << "usage: queens n (with n >3)" << endl;
exit(1);
}
int main(int argc, char *argv[]) {
// handle command line parameter
if(argc != 2) usage();
int dim = atoi(argv[1]);
if(dim<=3) usage();
// make two new "dim" problem, one to work on and one
// to memorize the best solution so far.
queens working(dim);
queens best(working);
// do dim*2 moves every iteration
queens_moves moves(dim*2);
// take dim*7 moves int the tabu list
simple_tabu_list tabus(dim/7);
// use the best known aspiration criteria
best_ever_criteria beac;
// exit only when an optimal solution is found
threshold_termination_criteria ttc(0);
// initialize the search instance with working and best solutions,
// the move manager, the tabu list, the aspiration criteria and the
// termination criteria
mets::tabu_search ts(working, best, moves, tabus, beac, ttc);
// attach the observer to the algorithm
tobserver o;
ts.attach(o);
// start the search process
try {
ts.search();
} catch(no_moves_error) {
cerr << "There are no non-tabu moves" << endl;
return -1; // failure :(
}
// from now on "best" contains the best solution found
// print resultes
cerr << endl << "Moves: " << tmove << " " << nmove << endl;
cout << "Cost: " << best.cost_function() << endl;
// print the best solution
cout << best << endl;
// success! :)
return 0;
}
$ g++ -O3 -o queens queens.cc `pkg-config metslib --cflags --libs`
You can start a search with:
$ ./queens 8
or:
$ ./src/queens 16
or again:
$ ./src/queens 2500