Hey Guys,
I found an interesting website that has a tutorial for Genetic Algorithm.
Here is the article: http://www.realintelligence.net/tut_genetic
This is the code of its author. I can combine, but there are an errors that I can't fix it. Anyone could help me to fix this.
Here is the code in Genetic.cpp
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* Genetic algorithms tutorial
* A sudoku solver.
* written by Lefteris of Real Intelligence Project
*
* you can email for questions/or suggestions
* at : lefteris@realintelligence.net
* or: lefkar@msn.com
*
* You can tweak the program by playing with the genetic
* parameters which are defined as macros in both main
* and Genetic.h. Moreover you can add new puzzles for solving
* by editing the sudokuRepresentation array.
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#include "Genetic.h"
Chromosome::Chromosome(int unknowns)
{
size = unknowns;
representation = (int*) malloc(sizeof(int)*unknowns); //allocate memory for the representation
fitness = NO_FITNESS_YET;
}
Chromosome::~Chromosome()
{
free(representation);
}
Chromosome& Chromosome::operator=(const Chromosome& c)
{
for(int i = 0 ; i < c.size; i++)
*(representation+i) = *(c.representation+i);
size = c.size;
fitness = c.fitness;
return *this;
}
void Chromosome::evaluate(int* startingSetup)
{
int fit = 0; //that's what will be counting our fitness, the more you have the better off you are
penalty = 0;
int lineskip = 9;
// int* chromo = (genePool.at(chromoNum))->representation;
int numbers[9]; //holds the numbers which are being used, just to check for abidance or not of the sudoku rules
int chromoOff;
for(int j = 0; j <10 ; j++)
numbers[j] = 0; //zero out the numbers holder
int offset = 0;
for(int i = 0; i < 9; i++)//lets check all the 9 squares to assign the square rule fitness
{
for(int k = 0; k < 3; k++)
{
if(*(startingSetup+offset+k*lineskip) != X )//if the corresponding number is given from the starting setup
numbers[*(startingSetup+offset+k*lineskip)] ++;
else//it comes from the chromosome
{
getChromoOffset(offset+k*lineskip,startingSetup,chromoOff);
numbers[*(representation+chromoOff)]++;
}
if(*(startingSetup+offset+1+k*lineskip) != X )//if the corresponding number is given from the starting setup
numbers[*(startingSetup+offset+1+k*lineskip)] ++;
else//it comes from the chromosome
{
getChromoOffset(offset+1+k*lineskip,startingSetup,chromoOff);
numbers[*(representation+chromoOff)]++;
}
if(*(startingSetup+offset+2+k*lineskip) != X )//if the corresponding number is given from the starting setup
numbers[*(startingSetup+offset+2+k*lineskip)] ++;
else//it comes from the chromosome
{
getChromoOffset(offset+2+k*lineskip,startingSetup,chromoOff);
numbers[*(representation+chromoOff)]++;
}
}
//now for every number existing only once in the current square add points
for(int j = 1; j <10 ; j++)
{
if(numbers[j] == 1)
fit += SQUARE_RULE_POINTS;
else
penalty++;
numbers[j] = 0; //zero it out for the next iteration
}
//also increase the offset to start in the next square in next iteration
if(offset == 6 || offset == 33 || offset == 51)//if(offset%6 == 0 && offset != 0)
offset += 2*lineskip +3; //if we reached the end of the big square gotta go to the lower squares
else
offset += 3;
}
//now let's go for the rows rule
for(int j = 0; j < 9; j ++)
{
for(int i = 0; i < 9; i ++)
{
if(*(startingSetup+i+(lineskip*j)) != X)
numbers[*(startingSetup+i+(j*lineskip))] ++;
else
{
getChromoOffset(i+lineskip*j,startingSetup,chromoOff);
numbers[*(representation+chromoOff)]++;
}
}
//now for every number existing only once in the current row
for(int k = 1; k <10 ; k++)
{
if(numbers[k] == 1)
fit += ROW_RULE_POINTS;
else
penalty++;
numbers[k] = 0; //zero it out for the next iteration
}
}
//finally let's get the columns rule
for(int j = 0; j < 9; j ++)
{
for(int i = 0; i < 9; i ++)
{
if(*(startingSetup+j+(lineskip*i)) != X)
numbers[*(startingSetup+j+(i*lineskip))] ++;
else
{
getChromoOffset(j+(lineskip*i),startingSetup,chromoOff);
numbers[*(representation+chromoOff)]++;
}
}
//now for every number existing only once in the current column
for(int k = 1; k <10 ; k++)
{
if(numbers[k] == 1)
fit += COLUMN_RULE_POINTS;
else
penalty++;
numbers[k] = 0; //zero it out for the next iteration
}
}
fitness = fit;
}
void Chromosome::getChromoOffset(int pos,int* setup,int &offset)
{
offset = 0;
for(int i =0; i<=pos; i++)
{
if(*(setup+i) == -1)
offset++;
}
offset-=1;
}
//Population constructor
Population::Population(int populationNumber,int *rules)
{
srand((unsigned)time(0)); //just seeding the random function with the current system time
startingSetup = rules;
genePool.resize(populationNumber);
int* currentChromo;
int unknowns;
getUnknowns(rules,unknowns);
this->populationNumber = populationNumber;
for(int k = 0; k < populationNumber; k ++)
{
genePool.at(k) = new Chromosome(unknowns);
currentChromo = (genePool.at(k))->representation;
for(int i =0; i < unknowns; i++)
{
*(currentChromo+i) = 1+int(9*rand()/(RAND_MAX + 1)); //random number from 1 to 9
}
}
}
//Returns the fittest chromosome in our population
Chromosome* Population::getFittest()
{
int bestFitness = 0;
Chromosome* best;
for(int i = 0; i < populationNumber; i++)
{
if((genePool.at(i))->fitness > bestFitness)
{
bestFitness = (genePool.at(i))->fitness;
best = genePool.at(i);
}
}
return best;
}
//roule selection and recombination
void Population::selectAndRecombine(int crossoverpoints,int mutationRate,bool injectNewGeneticMaterial,bool superMutation)
{
int popSize = genePool.size();
int totalFitness = 0;
int chromoSize = (genePool.at(0))->size;//just a variable holding the chromosome size
//first of all let's clear the roulette
rouletteWheel.clear();
std::vector<Chromosome*> newGenePool;
Chromosome* Parent1,*Parent2;
Chromosome* Child1,*Child2;
//evaluate the genePool
for(int i = 0; i < popSize; i++)
{
(genePool.at(i))->evaluate(startingSetup);
}
//now let's find the total fitness
for(int i = 0; i < popSize; i ++)
{
totalFitness += (genePool.at(i))->fitness;
}
int ratio = totalFitness/(RAND_MAX/2);
int cFitness= 0;
int prFitness = 0;
for(int i =0 ; i< popSize; i++)
{
if(!injectNewGeneticMaterial)
{
prFitness = cFitness;
cFitness +=(genePool.at(i))->fitness;
for(int j=prFitness/ratio;j<cFitness/ratio;j++)
{
rouletteWheel.push_back(i);
}
}
else//give equal chance to all
{
rouletteWheel.push_back(i);
}
// int from = prFitness/ratio;
//int to = cFitness/ratio;
// int eleos = 5;
}
int rouletteSize = rouletteWheel.size();
newGenePool.resize(popSize);
std::vector<Chromosome*> newM;
for(int i = 0; i < popSize; i +=2)//let's create a new population, the +=2 is since from 2 parents we get 2 children , so each run creates 2 new chromosomes
{
//random number from 0 to roulettesize-1
Parent1 = genePool.at( rouletteWheel.at( int((rouletteSize*rand())/(RAND_MAX + 1)) ) );
if(!injectNewGeneticMaterial)
{
//random number from 0 to roulettesize-1
Parent2 = genePool.at( rouletteWheel.at( int((rouletteSize*rand())/(RAND_MAX + 1)) ) );
}
else
{
newM.push_back(new Chromosome(chromoSize));
for(int j = 0; j < chromoSize; j ++)
{
* ((newM.at(i/2))->representation+j) = 1+int(9*rand()/(RAND_MAX + 1)); //random number from 1 to 9
}
Parent2 = newM.at(i/2);
}
//these represent the possible crossover points
std::vector<int> crossPoints;
crossPoints.resize(chromoSize);
for(int j = 0; j < chromoSize; j++)
crossPoints.at(j) = j;
std::vector<int> points;//this will hold the actual crossover points in the chromosome
points.resize(crossoverpoints);
int currentSize = chromoSize; //since the size will diminish the more crossover points we give
//for the number of crossover points given, randomly select their positions
for(int j = 0; j < crossoverpoints; j ++)
{
int randReturn = int((currentSize*rand())/(RAND_MAX + 1));//random num from 0 to currentSize -1
points.at(j) = crossPoints.at(randReturn); //add that randomly chosen point to the temporary vectors
currentSize-=1;//reduce the size of the random pool by 1
crossPoints.erase(crossPoints.begin()+randReturn);//and remove the chosen crossover point from the random pool
}
crossPoints.clear();
int swapped = true;
//bubble sort the crossover points so that they are in increasing order in the vector
while(swapped)
{
int temp;
swapped = false;
for(int j = 0; j< (points.size()-1); j++)
{
if(points.at(j) > points.at(j+1))
{
swapped = true;
temp = points.at(j+1);
points.at(j+1) = points.at(j);
points.at(j) = temp;
}
}
}
int offset = 0;
Child1 = newGenePool.at(i) = new Chromosome(chromoSize);
Child2 = newGenePool.at(i+1) = new Chromosome(chromoSize);
int* source;
int* destination;
//Performing recombination
for(int s = 0; s<= crossoverpoints; s++)
{
if(s != crossoverpoints)
{
destination = Child1->representation;
if(s%2 == 0)
source = Parent1->representation;
else
source = Parent2->representation;
memcpy(destination+offset,source+offset,(points.at(s)-offset)*sizeof(int));
destination = Child2->representation;
if(s%2 == 0)
source = Parent2->representation;
else
source = Parent1->representation;
memcpy(destination+offset,source+offset,(points.at(s)-offset)*sizeof(int));
offset = points.at(s);
}
else
{
destination = Child1->representation;
if(s%2 == 0)
source = Parent1->representation;
else
source = Parent2->representation;
memcpy(destination+offset,source+offset,(chromoSize-offset)*sizeof(int));
destination = Child2->representation;
if(s%2 == 0)
source = Parent2->representation;
else
source = Parent1->representation;
memcpy(destination+offset,source+offset,(chromoSize-offset)*sizeof(int));
}
}
points.clear();
}
if(mutationRate != 0)
{
for(int i =0;i<popSize;i++)
{
int eleos = 0;
for(int j =0; j< chromoSize; j ++)
{
int randy = int((RAND_MAX*rand())/(RAND_MAX + 1));
if( mutationRate > randy )//if it happens to mutate
{
*((newGenePool.at(i))->representation+j) = 1+int(9*rand()/(RAND_MAX + 1)); //give it any number from 1 to 9
}
}
}
}
int newFitness = 0;
//let's evaluate the new gene pool
for(int i = 0; i < popSize; i++)
{
(newGenePool.at(i))->evaluate(startingSetup);
}
std::vector<Chromosome*> tempPool;
tempPool.resize(popSize);
for(int i = 0; i < popSize; i ++)
{
tempPool.at(i) = new Chromosome(chromoSize);
*(tempPool.at(i)) = *(genePool.at(i));
// printf("%d \n\r",(tempPool.at(i))->fitness);
// Sleep(1000);
}
Chromosome* best;//will keep the best chromosome for transfer
int bFit;
int index = 0;
bool foundInSecond= false;
for(int i =0; i < popSize; i++)
{
bFit = 0;
foundInSecond = false;
for(int j = 0; j < tempPool.size(); j++)
{
if((tempPool.at(j))->fitness > bFit)
{
best = tempPool.at(j);
bFit = (tempPool.at(j))->fitness;
foundInSecond = false;
index = j;
}
}
for(int j = 0; j < newGenePool.size(); j++)
{
if((newGenePool.at(j))->fitness > bFit)
{
best = newGenePool.at(j);
bFit = (newGenePool.at(j))->fitness;
foundInSecond = true;
index = j;
}
}
//move it to the new genepool
*(genePool.at(i)) = *best;
//remove it from wherever it was found
if(!foundInSecond)
{
delete tempPool[index];
tempPool.erase(tempPool.begin()+index);
}
else
{
delete newGenePool[index];
newGenePool.erase(newGenePool.begin()+index);
}
}
if(superMutation)
{
for(int i =0;i<popSize;i++)
{
int eleos = 0;
for(int j =0; j< chromoSize; j ++)
{
int randy = int((RAND_MAX*rand())/(RAND_MAX + 1));
if( superMutationRate > randy )//if it happens to mutate
{
*((genePool.at(i))->representation+j) = 1+int(9*rand()/(RAND_MAX + 1)); //give it any number from 1 to 9
}
}
}
}
clearPool(newGenePool,newGenePool.size());
clearPool(tempPool,tempPool.size());
clearPool(newM,newM.size());
}
//Just prints the particular chromosome's solution
//to the sudoky puzzle
void Population::printSolution(Chromosome* chromo)
{
int* rep = chromo->representation;
int chOff = 0;
for(int i = 0; i <81; i ++)
{
if(*(startingSetup+i) != X)
printf("%d ",*(startingSetup+i));
else
{
printf("%d ",*(rep+chOff));
chOff ++;
}
if((i+1)%3 ==0)
printf(" ");
if((i+1) % 9 == 0 )
printf("\n\r");
if((i+1) % 27 == 0)
printf("\n\r");
}
}
//Clears the pool and frees memory, since memory leaks are bad
void Population::clearPool(std::vector<Chromosome*> &a,int size)
{
Chromosome* c;
size = a.size();
for(size_t j = 0 ;j < a.size();j++)
{
delete a[j];
}
a.clear();
}Here is the code in Genetic.h
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* Genetic algorithms tutorial
* A sudoku solver.
* written by Lefteris of Real Intelligence Project
*
* you can email for questions/or suggestions
* at : lefteris@realintelligence.net
* or: lefkar@msn.com
*
* You can tweak the program by playing with the genetic
* parameters which are defined as macros in both main
* and Genetic.h. Moreover you can add new puzzles for solving
* by editing the sudokuRepresentation array.
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>//for malloc
#include <time.h>//for time()
#include <iostream>
#include <vector>
#define X -1 //represents a number we don't know, a blank in sudoku
#define getUnknowns(s,count) {count = 0;\
for(int i=0;i<81;i++){\
if(*(s+i) == -1)count++;}}
#define chromoPrint(TEXT,chromosome,points,crossoverpoints) {printf(TEXT);\
int pCounter = 0;\
for(int j = 0; j < chromoSize; j++)\
{\
if(j == points.at(pCounter))\
{\
printf("|");\
if(pCounter < crossoverpoints-1)\
pCounter++;\
}\
printf("%d ",*((chromosome->representation)+j));\
}\
printf("\n\r\n\r");}
#define NO_FITNESS_YET -1
#define SQUARE_RULE_POINTS 20 //these points denote the fitness for not breaking the square rule
#define ROW_RULE_POINTS 20//these points denote the fitness for not breaking the row rule
#define COLUMN_RULE_POINTS 20//these points denote the fitness for not breaking the column rule
#define superMutationRate 32000
class Chromosome
{
public:
int* representation;
int size;
int fitness;
int penalty;
//constructor and destructor
Chromosome(int unknowns);
~Chromosome();
//operator overloading just so we can assign chromosomes in the population
Chromosome& operator=(const Chromosome& c);
//the evaluation function
void evaluate(int* startingSetup);
//helper function to get the offset of the chromosome
//when seen in the whole filled sudoku puzzle
void getChromoOffset(int pos,int* setup,int &offset);
};
class Population
{
private:
//our starting sudoku puzzle
int* startingSetup;
//the population count
int populationNumber;
public:
//the actual chromosome population
std::vector<Chromosome*> genePool;
//this is our selection method
//a roulette wheel selection
std::vector<int> rouletteWheel;
//constructor
Population(int populationNumber,int* rules);
//performs Selection of chromosomes, recombinations
//and mutations and creates the next generation of solutions
void selectAndRecombine(int crossoverpoints,int mutationRate,bool newMaterial,bool superMutation);
//Returns the fittest chromosome in our population
Chromosome* getFittest();
//prints the solution to the sudoku puzzle that the
//parameter chromosome reperesents
void printSolution(Chromosome* chromo);
//clears the given population gene pool
//since memory leaks are bad
void clearPool(std::vector<Chromosome*>& a, int size);
};Here is the code of main.cpp
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* Genetic algorithms tutorial
* A sudoku solver.
* written by Lefteris of Real Intelligence Project
*
* you can email for questions/or suggestions
* at : lefteris@realintelligence.net
* or: lefkar@msn.com
*
* You can tweak the program by playing with the genetic
* parameters which are defined as macros in both main
* and Genetic.h. Moreover you can add new puzzles for solving
* by editing the sudokuRepresentation array.
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#include "Genetic.h"
//the number of chromosomes in each generation
#define populationN 1500//2000
#define crossoverPoints 14
/*
Wikipedia sudoku:
800 population
14 crossover
int sudokuRepresentation[] = {
5,3,X, X,7,X, X,X,X,
6,X,X, 1,9,5, X,X,X,
X,9,8, X,X,X, X,6,X,
8,X,X, X,6,X, X,X,3,
4,X,X, 8,X,3, X,X,1,
7,X,X, X,2,X, X,X,6,
X,6,X, X,X,X, 2,8,X,
X,X,X, 4,1,9, X,X,5,
X,X,X, X,8,X, X,7,9
};
*/
/*
//extreme
int sudokuRepresentation[] ={
X,7,X, 6,X,X, X,3,X,
X,X,4, 3,X,X, 9,X,X,
3,2,X, X,X,7, 5,6,X,
X,4,X, X,1,X, X,X,X,
X,X,8, X,X,X, 7,X,X,
X,X,X, X,3,X, X,2,X,
X,6,2, 8,X,X, X,1,9,
X,X,7, X,X,9, 6,X,X,
X,8,X, X,X,3, X,7,X,
};*/
//expert
/*
int sudokuRepresentation[] ={
5,X,X, X,X,2, 6,X,X,
X,X,X, X,6,5, X,3,1,
X,1,X, X,X,3, X,7,5,
X,X,X, X,X,1, X,2,X,
8,X,X, 3,X,7, X,X,6,
X,3,X, 4,X,X, X,X,X,
3,6,X, 7,X,X, X,8,X,
2,8,X, 5,3,X, X,X,X,
X,X,4, 2,X,X, X,X,7,
};*/
/*
//hard
int sudokuRepresentation[] ={
8,7,X, X,X,X, X,X,X,
X,6,3, X,2,X, X,X,X,
5,X,X, 7,X,X, X,X,6,
X,1,X, 3,6,5, X,9,X,
X,X,X, X,X,X, X,X,X,
X,5,X, 1,9,8, X,6,X,
2,X,X, X,X,6, X,X,3,
X,X,X, X,7,X, 4,5,X,
X,X,X, X,X,X, X,7,1,
};
*/
//standard
int sudokuRepresentation[] ={
X,6,X, X,X,9, X,1,8,
2,X,X, X,X,X, X,X,X,
3,X,X, X,X,1, 6,X,X,
X,X,X, X,5,X, X,2,1,
X,2,X, X,8,X, X,9,X,
5,4,X, X,3,X, X,X,X,
X,X,7, 4,X,X, X,X,5,
X,X,X, X,X,X, X,X,9,
4,3,X, 6,X,X, X,8,X,
};
int main()
{
Population pop(populationN ,(int*)sudokuRepresentation);
int fitness = 0;
int generations = 0;
int mutation = 100;
int samePenaltyCount = 0;
int prPenalty = 999;
int backTrackCount = 0;
int penalty = 99;
while(penalty > 0 )
{
if(samePenaltyCount > 50)
{
samePenaltyCount = 0;
pop.selectAndRecombine(crossoverPoints,mutation,true,true);//100/32765 seems to be nice
backTrackCount++;
}
else
pop.selectAndRecombine(crossoverPoints,mutation,false,false);
printf("Best Fitness in generation %d is %d with backtracks: %d \n\r",generations,(pop.getFittest())->fitness,backTrackCount);
penalty = (pop.getFittest())->penalty;
if(penalty == prPenalty)
samePenaltyCount++;
else
samePenaltyCount = 0;
prPenalty = penalty;
printf("The penalty of the fittest one is %d \n\r",penalty);
pop.printSolution(pop.getFittest());
generations++;
}
return 0;
}Could anyone please combine code of these 3 files and runs it. I got EXC_ARITHMETIC problem. I think it's the problem of division by zero. I forgot to tell you guys that this is a sudoku solver.
Thanks