root/trunk/samples/n-queens/gas/galib-queens.C

// galib-queens.C - N Queens w/galib                         -*- C++ -*-
//
// N-Queens solution search by Genetic Algorithms. This demo code was
// used to show how tabu search is much faster on this problem. Tabu
// search is also a simpler to implement right because it has fewer
// variables to act on.
//
// Copyright (C) 2006 Mirko Maischberger <mirko.maischberger@gmail.com>,
//                    Paolo Vaccari <paoz at lilik dot it>
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
//
//
// Notes: to compile this program you can simply copyt the file in
// the examples path of your galib sources and add it to the 
// examples/Makefile

#include <stdio.h>
#include <stdlib.h>
#include <ga/ga.h>
//#include <ga/std_stream.h>

#define cout STD_COUT
#define endl STD_ENDL
//#define ostream STD_OSTREAM

int dim = 100;  
int popsize = 50;
int ngen = 100000;
float pcross = 0.795; 
float pmut = 0.10;
float mutq = 0.25;
float preplace = 0.78;

float objective(GAGenome &);
void init(GAGenome &);
int mutate(GAGenome &, float);
GABoolean stopwhenzero(GAGeneticAlgorithm &);

void print(const GAGenome &);

int main(int argc, char *argv[])
{
  GA1DArrayGenome<int> genome(dim, objective);
  genome.initializer(init);
  genome.mutator(mutate);
  genome.crossover(GA1DArrayGenome<int>::PartialMatchCrossover);
  
  GASteadyStateGA ga(genome);
  ga.pReplacement(preplace);
  /*
    GASimpleGA ga(genome);
    gasimplega.elitist();
  */
  //GAIncrementalGA ga(genome);
  
  ga.populationSize(popsize);
  ga.nGenerations(ngen);
  ga.pMutation(pmut);
  ga.pCrossover(pcross);
  ga.terminator(stopwhenzero);
  ga.minimize();
  
  ga.initialize(clock());
  
  // initial population
  GAPopulation pop = ga.population();
  cout << "pop. size = " << pop.size() << endl;
  for (int i = 0; i < pop.size(); i++)
    {
      cout << "pop(" << i << ") = " << pop.individual(i) << 
        " (" << pop.individual(i).score() <<  ")" << endl;
    }
  cout << "\nbest   = " << pop.best()<< 
    " (" << pop.best().score() << ")" << endl;
  //print(pop.best());
  cout << "worst  = " << pop.worst() << 
    " (" << pop.worst().score() << ")" << endl;
  //print(pop.worst());
  
  cout << "evolving...";
  while(!ga.done()){
    ga.step();
    if(ga.generation() % 50 == 0) {
      cout << "." << ga.statistics().bestIndividual().score(); 
      cout.flush();
    }
  }
  cout << "\n\n";
  
  cout << "best generated @ generation #" << ga.generation() << ":\n" << 
    ga.statistics().bestIndividual() << 
    " (" << ga.statistics().bestIndividual().score() << ")" << endl;
  print(ga.statistics().bestIndividual());
  return 0;
}


void init(GAGenome& c)
{
  GA1DArrayGenome<int> & genome = (GA1DArrayGenome<int> &)c;
  
  for(int i = 0; i < dim; i++) 
    genome.gene(i, i);
  
  for(int i = 0; i < dim; i++)   
    {
      int r = GARandomInt(0, dim - 1);
      genome.swap(i, r);
    }
}


int mutate(GAGenome& c, float mutprob)
{
  GA1DArrayGenome<int>& genome = (GA1DArrayGenome<int>&)c;
  
  if(mutprob <= 0.0) 
    return(0);
  
  int i, j;
  float mut = GARandomFloat(0.0, 1.0);

  if(mut < mutprob)
    {
      for(int d = 0; d < dim; d++) {
        mut = GARandomFloat(0.0, 1.0);
        if(mut < mutq/dim) {
          i = GARandomInt(0, dim - 1);
          j = GARandomInt(0, dim - 1);
          genome.swap(i, j); 
        }
      }
      return(1);
    }
  else
    return(0);
}


float objective(GAGenome& c)
{
  GA1DArrayGenome<int> & genome = (GA1DArrayGenome<int> &)c;
  
  float cost = 0;
  for(int i = 0; i < dim - 1; i++)
    for(int j = 1; j < dim - i; j++) 
      {
        if( genome.gene(i + j) == genome.gene(i) - j 
            or 
            genome.gene(i + j) == genome.gene(i) + j ) 
          {
            cost+=1.0; 
            //break;
          }
      }
  return cost;
}


GABoolean stopwhenzero(GAGeneticAlgorithm & ga)
{
  if (ga.statistics().bestIndividual().score() == 0 or ga.generation() == ngen )
    return gaTrue;
  else
    return gaFalse;
}


void print(const GAGenome& c)
{
  GA1DArrayGenome<int> & genome = (GA1DArrayGenome<int> &)c;
  
  for(int i = 0; i < dim; i++)
    {
      for(int j = 0; j < dim; j++)
        {
          if (genome.gene(j) == i)
            cout << "@ ";
          else
            cout << "x ";
        }
      cout << endl;
    }
  cout << endl;
}


// force instantiations for compilers that do not do auto instantiation
// for some compilers (e.g. metrowerks) this must come after any
// specializations or you will get 'multiply-defined errors when you compile.
#if !defined(GALIB_USE_AUTO_INST)
//#include <ga/GAAllele.C>
#include <ga/GA1DArrayGenome.C>
GALIB_INSTANTIATION_PREFIX GAArray<int>;
GALIB_INSTANTIATION_PREFIX GA1DArrayGenome<int>;
#endif