/*  YAKS, Optann, a Khepera simulator including a separate GA and ANN   (Genetic Algoritm, Artificial Neural Net).  Copyright (C) 2000  Johan Carlsson (johanc@ida.his.se)    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 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA. */#include "ga.h"int storre(const void *f2, const void *f1){	  return (int)((*(double*)f1-*(double*)f2)*1000);}int compareF(const void *f2,const void *f1){  double t1,t2;  t1 = (*(FINDEX_T**)f1)->fitness;  t2 = (*(FINDEX_T**)f2)->fitness;  return (int)((t1-t2)*1000);}/** * Mutate the individ of the current generation * @param bitMutateProbability The chance that a bit in an ANN link weight mutates */void Ga::mutateIndivids(int bitMutateProbability){  for(int i=0; i < nrOfIndivids; i++){    individs[i]->mutateNeurons(bitMutateProbability);  }}/** * Creates a new generation without applying any mutation. * New generation is parents * offsprings * @param parents The number of parents * @param offsprings The number of offspring each parent produces */void Ga::createNewGeneration(int parents, int offsprings){  createNewGenerationWithMutation(parents, offsprings, 0);}/** * Creates a new generation using tounament selection. The new individs * are mutaded.  * @attention Note that a individ can be compared with itself. * @attention It is safe to use this method with a GA that uses different ANN architectures * @param bitMutation The probability that a bit in a ANN link weight mutates */void Ga::tournamentSelectionWithMutation(int bitMutation){  int *index;  int i,i1,i2;  Ann **new_individs;  index = (int*)alloca(sizeof(int)*nrOfIndivids);  new_individs = (Ann**)malloc(nrOfIndivids*sizeof(Ann*));     for(i=0; i < nrOfIndivids;i++){    /*  ok we can choose same individ twice - so what ? */    i1 = g_mrand(nrOfIndivids);    i2 = g_mrand(nrOfIndivids);    if(totalFitness[i1] > totalFitness[i2])      index[i] = i1;    else      index[i] = i2;  }  for(i = 0; i < nrOfIndivids; i++){    new_individs[i] = individs[index[i]]->duplicate();    new_individs[i]->mutateNeurons(bitMutation);  }  for(i = 0; i < nrOfIndivids; i++){    delete(individs[i]);  }  free(individs);  individs = new_individs;   /* We uses alloca for index so we dont need to free that memory */}/** * Creates a new generation with weight mutation. * New generation is parents * offsprings. * @attention Individs must have the same ANN architecture * @param parents The number of parents * @param offsprings The number of offspring each parent produces * @param bitMutation The probability that a bit in a ANN link weight mutates */void Ga::createNewGenerationWithWeightMutation(int parents, 					       int offsprings, 					       int bitMutation){  FINDEX_T **index;  Ann *tmp;  int i,p,childIndex;  if(parents*offsprings==nrOfIndivids  || (parents==1 && parents+offsprings-1 == nrOfIndivids)){    /* Make a sorted array in order to map best individs to parents*/    index = (FINDEX_T**)malloc(sizeof(FINDEX_T*)*nrOfIndivids);    for(i=0; i < nrOfIndivids;i++){      index[i]= (FINDEX_T*)alloca(sizeof(FINDEX_T));      index[i]->fitness=totalFitness[i];      index[i]->index=i;    }    qsort(index,nrOfIndivids,sizeof(FINDEX_T*),compareF);    /* move parents to the beginning ot the array */    for(i=0; i < parents; i++){      tmp = individs[i];      individs[i] = individs[index[i]->index];      individs[index[i]->index] = tmp;    }    /* Shall we mutate the offsprings directly ?*/    if(bitMutation>0){      for(p=0;p<parents;p++){	for(i=0;i < offsprings-1; i++){	  childIndex = parents + i*parents + p;	  /* Copy weights from parent */	  individs[childIndex]->copyWeightsFrom(individs[p]);	  /* Mutate offspring */	  individs[childIndex]->mutateNeurons(bitMutation);	}      }    }    else{      for(p=0;p<parents;p++){	for(i=0;i < offsprings-1; i++){	  childIndex = parents + i*parents + p;	  /* Copy weights from parent */	  individs[childIndex]->copyWeightsFrom(individs[p]);	}      }    }    /*We uses alloca for the members (memory allocated on the stack)      so we dont need to free the memory for every individ */     free(index);  }  else{    printf("Parents * offsprings doesn't match number of individs, %i * %i != %i\n",	   parents,offsprings,nrOfIndivids);    exit(-1);  }}/** * Creates a new generation with weight mutation. Saves the best individ. * New generation is parents * offsprings. * @attention Individs must have the same ANN architecture * @param parents The number of parents * @param offsprings The number of offspring each parent produces * @param bitMutation The probability that a bit in a ANN link weight mutates * @param fp A pointer to a filedescriptor where the file is open for writing */void Ga::createNewGenerationWithWeightMutation(int parents, 					       int offsprings, 					       int bitMutation,					       FILE *fp){  FINDEX_T **index;  Ann *tmp;  int i,p,childIndex;  if(parents*offsprings==nrOfIndivids  || (parents==1 && parents+offsprings-1 == nrOfIndivids)){    /* Make a sorted array in order to map best individs to parents*/    index = (FINDEX_T**)malloc(sizeof(FINDEX_T*)*nrOfIndivids);    for(i=0; i < nrOfIndivids;i++){      index[i]= (FINDEX_T*)alloca(sizeof(FINDEX_T));      index[i]->fitness=totalFitness[i];      index[i]->index=i;    }    qsort(index,nrOfIndivids,sizeof(FINDEX_T*),compareF);    /* move parents to the beginning ot the array */    for(i=0; i < parents; i++){      tmp = individs[i];      individs[i] = individs[index[i]->index];      individs[index[i]->index] = tmp;    }    individs[i]->saveWeights(fp);    /* Shall we mutate the offsprings directly ?*/    if(bitMutation>0){      for(p=0;p<parents;p++){	for(i=0;i < offsprings-1; i++){	  childIndex = parents + i*parents + p;	  /* Copy weights from parent */	  individs[childIndex]->copyWeightsFrom(individs[p]);	  /* Mutate offspring */	  individs[childIndex]->mutateNeurons(bitMutation);	}      }    }    else{      for(p=0;p<parents;p++){	for(i=0;i < offsprings-1; i++){	  childIndex = parents + i*parents + p;	  /* Copy weights from parent */	  individs[childIndex]->copyWeightsFrom(individs[p]);	}      }    }    /*We uses alloca for the members (memory allocated on the stack)      so we dont need to free the memory for every individ */     free(index);  }  else{    printf("Parents * offsprings doesn't match number of individs, %i * %i != %i\n",	   parents,offsprings,nrOfIndivids);    exit(-1);  }}/** * Creates a new generation with weight mutation. * New generation is parents * offsprings. * @attention Use createNewGenerationWithWeightMutation if all individs has the same structure. * @attention That method is much faster since we dont have to deallocate and allocate memory. * @param parents The number of parents * @param offsprings The number of offspring each parent produces * @param bitMutation The probability that a bit in a ANN link weight mutates */void Ga::createNewGenerationWithMutation(int parents, int offsprings, int bitMutation){  FINDEX_T **index;  Ann *tmp;  int i,p,childIndex;  if(parents*offsprings==nrOfIndivids || (parents==1 && parents+offsprings-1 == nrOfIndivids)) {    /* Make a sorted array in order to map best individs to parents*/    index = (FINDEX_T**)malloc(sizeof(FINDEX_T*)*nrOfIndivids);    for(i=0; i < nrOfIndivids;i++){      index[i]= (FINDEX_T*)alloca(sizeof(FINDEX_T));      index[i]->fitness=totalFitness[i];      index[i]->index=i;    }    qsort(index,nrOfIndivids,sizeof(FINDEX_T*),compareF);    /* move parents to the beginning ot the array */    for(i=0; i < parents; i++){      tmp = individs[i];      individs[i] = individs[index[i]->index];      individs[index[i]->index] = tmp;    }    /* destroy/remove non parents */    for(i=parents; i < nrOfIndivids; i++){      delete(individs[i]);    }    /* Shall we mutate the offsprings directly ?*/    if(bitMutation>0){      for(p=0;p<parents;p++){	for(i=0;i < offsprings-1; i++){	  childIndex = parents + i*parents + p;	  /* Duplicate parent */	  individs[childIndex] = individs[p]->duplicate();	  /* Mutate offspring */	  individs[childIndex]->mutateNeurons(bitMutation);	}      }    }    else{      for(p=0;p<parents;p++){	for(i=0;i < offsprings-1; i++){	  childIndex = parents + i*parents + p;	  /* Duplicate parent */	  individs[childIndex] = individs[p]->duplicate();	}      }    }    /*We uses alloca for the members (memory allocated on the stack)      so we dont need to free the memory for every individ */     free(index);  }  else{    printf("Parents * offsprings doesn't match number of individs, %i * %i  != %i\n",	   parents,offsprings,nrOfIndivids);    exit(-1);  }}/** * Set fitness for all individs, epochs and total to zero */void Ga::resetFitness(){  int i,u;  for(i = 0; i < nrOfIndivids; i++){    for(u = 0; u < epochs; u++){      fitness[i][u] = 0;    }    totalFitness[i] = 0;  }}/** * Save the average fitness and the fitness for the "nr" best individs to file. * If whished print it to stdout also. * @param nr How many of the best individs to log * @param fp A pointer to a file descriptor which file is open for writing * @param show If show > 0 output, to stdout also */void Ga::saveBestIndividsFitness(int nr,FILE *fp, int show){  double *sort;  double average=0;  sort = (double*) malloc(sizeof(double)*nrOfIndivids);  for(int i=0; i < nrOfIndivids; i++){    sort[i]=totalFitness[i];    average+=totalFitness[i];  }  qsort(sort,nrOfIndivids,sizeof(double),storre);  fprintf(fp,"%.2f ", average / nrOfIndivids);  if(show>0)      printf(" (average %.2f) ", average / nrOfIndivids);  for(int i=0; i < nrOfIndivids && i < nr; i++){    fprintf(fp,"%.2f ",sort[i]);    if(show>0)      printf("%.2f ",sort[i]);  }  if(show>0)    printf("\n");  fprintf(fp,"\n");  free(sort);}/** * Constructor, creates a new GA with iNrOfIndivids and iEpochs * Allocates space for fitness. * @param iNrOfIndivids The number of individs for the GA * @param iEpochs The number of epochs to store fitness for each ANN */Ga::Ga(int iNrOfIndivids, int iEpochs){  fitness = (double**) malloc(iNrOfIndivids*sizeof(double*));  for(int i=0; i < iNrOfIndivids; i++){    fitness[i]= (double*) malloc(iEpochs * sizeof(double));  }  totalFitness = (double*) malloc(iNrOfIndivids*sizeof(double));  nrOfIndivids = iNrOfIndivids;  epochs = iEpochs;  for(int i=0; i < nrOfIndivids; i++){    totalFitness[i] = 0;    for(int e=0; e < epochs; e++){      fitness[i][e] = 0;    }  }}/** *Deconstructor for GA, deallocates all individs and all fitness  */Ga::~Ga(){  if(nrOfIndivids>0){    for(int i=0; i < nrOfIndivids; i++){      delete(individs[i]);    }    free(individs);  }  free(*fitness);  free(fitness);  free(totalFitness);}/** * Create all individs for the GA using original as a template * @attention It is safe to deallocate original after this method * @param orginal Template ANN to duplicate to the new individs */void Ga::createIndivids(const Ann *orginal){  individs = (Ann**)malloc(nrOfIndivids*sizeof(Ann*));  for(int i=0; i < nrOfIndivids; i++){#ifdef GA_DEBUG    cout << "Creating individ " << i << " ANN->duplicate " << endl;#endif    individs[i] = orginal->duplicate();  }}/** *Sets the fitness for iIndivid, iEpoch to newFitness updates the total fitness for that individ *@param iIndivid Which individ *@param iEpoch Which epoch *@param newFitness The new fitness */void Ga::setFitness(int iIndivid, int iEpoch, double newFitness){  if(iIndivid >= 0 && iIndivid < nrOfIndivids && iEpoch >= 0 && iEpoch < epochs){    fitness[iIndivid][iEpoch] = newFitness;    totalFitness[iIndivid] += newFitness;  }  else{    printf("Ga::setFitness(int,int,double) indexes out of range individ %d, epoch %d\n",iIndivid,iEpoch);  }}/** * Get the fitness for iIndivid and iEpoch *@param iIndivid Which individ *@param iEpoch Which epoch *@return The fitness or -1 if iIndivid or iEpoch is out of range */double Ga::getFitness(int iIndivid,int iEpoch){    if(iIndivid >= 0 && iIndivid < nrOfIndivids && iEpoch >= 0 && iEpoch < epochs){    return fitness[iIndivid][iEpoch];  }  else    return(-1);}/** * Get the total fitness for individ n *@param n Which individ *@return The fitness or -1 if n is out of range */double Ga::getTotalFitness(int n){  if(n >= 0 && n < nrOfIndivids)    return totalFitness[n];  else    return (-1);}/** * Get the fitness for the best individ * @return The fitness */int Ga::getBestIndivid(){  int best = 0;  for(int i=0; i < nrOfIndivids; i++){    if(totalFitness[best] < totalFitness[i])      best=i;  }  return best;}/** * Not implemented * */void Ga::addIndivid(){}/** *Saves all individs weights to file *@param fp A pointer to a file descriptor where the file is open for writing * */void Ga::saveAllIndividsWeights(FILE *fp){  for(int i=0; i < nrOfIndivids; i++){    individs[i]->saveWeights(fp);  }}/** *Loads individs from a weight file *@attention The number of individs and the architecture of the individs *@attention must be the same as in the file. *@param fp A pointer to a file descriptor where the file is open for reading */void Ga::loadAllIndividsWeights(FILE *fp){  for(int i=0; i < nrOfIndivids; i++){     individs[i]->loadWeights(fp);  }}