population.c

比较完整的遗传算法的源代码

#include <stdlib.h>

#ifdef USE_PVM
#include <pvm3.h>
#endif /* USE_PVM */

#include "petrol.h"
#include "utils.h"

static void        PopulationInit(Settings *s, Population *p);
static void        PopulationIndividualsInit(Individual *i, int size, int len);
static void        PopulationDelete(Population *p);
static void        PopulationGeneration(Settings *s, Population *p);
static void        PopulationFitness(Settings *s, Population *p);

static Individual *Roulette(Population *p);
static void        Crossover(Population *p, Individual *p1, Individual *p2,
			     Individual *c1, Individual *c2);
static int         Mutation(Population *p, int x);

void PopulationRun(Settings *s, Population *p) {
  int gen;

  /* Initialize the population */
  PopulationInit(s, p);

  /* Report on the initial population */
  ReportInitial(s, p);

  for (gen = 1; gen <= p->numGenerations; gen++) {
    /* Create a new population out of the old */
    PopulationGeneration(s, p);
    
    /* Report on the new generation */
    ReportGeneration(s, p, gen);
  }

#ifdef USE_PVM
  /* Cleanup the slave processes */
  PVMFitnessExit();
#endif

  /* Report final details */
  ReportDone(s, p);

}

void PopulationInit(Settings *s, Population *p) {
  p->pop = (Individual *)malloc(sizeof(Individual) * p->popSize);
  if (!p->pop) {
    syserror("PopulationInit");
  }

  p->numCrossovers = 0;
  p->numMutations  = 0;

  PopulationIndividualsInit(p->pop, p->popSize, p->chromosomeLen);
  PopulationFitness(s, p);
}

void PopulationIndividualsInit(Individual *i, int size, int len) {
  int n, m;

  for (n = 0; n < size; n++) {
    (i + n)->chrom = (int *)malloc(sizeof(int) * len);
    if (!(i + n)->chrom) {
      syserror("PopulationIndividualsInit");
    }
    (i + n)->chromLen = len;
    (i + n)->fitness = 0.0;

    for (m = 0; m < i->chromLen; m++) {
      (i + n)->chrom[m] = flip(0.5);
    }
  }

}

void PopulationDelete(Population *p) {
  int         n;
  Individual *pop;

  if (p == NULL)
    return;

  pop = p->pop;
  for (n = 0; n < p->popSize; n++) {
    free((pop + n)->chrom);
  }
  free(pop);
  p->pop = NULL;

}
void PopulationGeneration(Settings *s, Population *p) {
  Individual *newpop;
  Individual *p1, *p2;
  int i;

  newpop = (Individual *)malloc(sizeof(Individual) * p->popSize);
  if (!newpop) {
    syserror("PopulationGeneration");
  }
  PopulationIndividualsInit(newpop, p->popSize, p->chromosomeLen);

  /* The famous assumption of an even population takes place here, too */
  for (i = 0; i < p->popSize; i += 2) {
    p1 = Roulette(p);
    p2 = Roulette(p);

    Crossover(p, p1, p2, (newpop + i), (newpop + i + 1));
  }

  PopulationDelete(p);
  p->pop = newpop;

  PopulationFitness(s, p);

}

void PopulationFitness(Settings *s, Population *p) {
  int         n, min, max;
  double      sum, fitness;
  Individual *pop;

  pop = p->pop;

#ifdef USE_PVM

  PVMFitness(s, p);

#else 
  
  for (n = 0; n < p->popSize; n++) {
    (pop + n)->fitness = Fitness(pop + n);
  }

#endif /* USE_PVM */

  /* Finally, figure the total fitness of the population */
  for (n = 0, min = 0, max = 0, sum = 0.0; n < p->popSize; n++) {
    fitness = (pop + n)->fitness;
    if (fitness < (pop + min)->fitness)
      min = n;
    if (fitness > (pop + max)->fitness)
      max = n;
    
    sum += fitness;
  }
  p->sumFitness = sum;
  p->avgFitness = sum / p->popSize;
  p->minFitness = min;
  p->maxFitness = max;

}

Individual *Roulette(Population *p) {
  int         n;
  double      partSum, mark;
  Individual *pop;

  pop = p->pop;

  mark = randFraction() * p->sumFitness;
  for (n = 0, partSum = 0.0; partSum <= mark && n < p->popSize; n++) {
    partSum += (pop + n)->fitness;
  }

  if (n == 0) {
    return (pop);
  } else {
    return (pop + n - 1);
  }

}

void Crossover(Population *p, Individual *p1, Individual *p2, Individual *c1,
	       Individual *c2) {

  int i, icross;

  if (flip(p->probCrossover)) {
    icross = randInt(0, p->chromosomeLen - 1);
    p->numCrossovers++;
  } else {
    icross = p->chromosomeLen;
  }

  for (i = 0; i < icross; i++) {
    c1->chrom[i] = Mutation(p, p1->chrom[i]);
    c2->chrom[i] = Mutation(p, p2->chrom[i]);
  }

  for (i = icross; i < p->chromosomeLen; i++) {
    c1->chrom[i] = Mutation(p, p2->chrom[i]);
    c2->chrom[i] = Mutation(p, p1->chrom[i]);
  }

}

int Mutation(Population *p, int x) {
  if (flip(p->probMutation)) {
    p->numMutations++;
    return !x;
  } else {
    return x;
  }
}