ga.cc

神经网络和遗传算法组合应用

/*
  YAKS, Optann, a Khepera simulator including a separate GA and ANN 
  (Genetic Algoritm, Artificial Neural Net).
  Copyright (C) 2000  Johan Carlsson ([e-mail])
  
  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);
  }
}