An Introduction to Genetic Algorithms

Listing 1 Demo program and global functions to solve knapsack problem

#include <stdlib.h>
#include <stdio.h>
#include "pop.h"

static enum Bool {FALSE, TRUE};

// MAXWEIGHT defines the constraint of the knapsack
// example and ItemDesc is simply the coding scheme.

static const int MAXWEIGHT = 17;
static const struct
{
   int    Weight;
   int    Value;
} ItemDesc[] = {
   {3,  4}, {3,  4}, {3,  4}, {3,  4}, {3,  4},
   {4,  5}, {4,  5}, {4,  5}, {4,  5},
   {7, 10}, {7, 10}, {8, 11}, {8, 11}, {9, 13}};

void CalcWeightAndValue(CGAChromosome *Chromosome,
                    int& Weight, int& Value);
Bool FoundSolution(CGAPopulation& Pop);
void PrintPop(CGAPopulation& Pop);

// Main creates the population of chromosomes and
// continues creating new generations until a solution
// is found.


int main(void)
{
   const float  MaxMutationRate = 0.2;
   const int    PopulationSize  = 30;

   CGAPopulation Pop(PopulationSize, sizeof(ItemDesc) /
                  sizeof(ItemDesc[0]),
                  MaxMutationRate);

   while (!FoundSolution(Pop)) {
      Pop.CreateNextGeneration();
      PrintPop(Pop);
   }
   return EXIT_SUCCESS;
}

// Print information and statistics about population.

void PrintPop(
   CGAPopulation& Pop)
{
   float TotalFitness = 0;

   printf("Idx Fit Val Wt Chromosome\n");
   for (size_t ChromIdx = 0;
       ChromIdx < Pop.GetPopulationSize();
       ChromIdx++) {

      int   Weight;
      int   Value;
      CGAChromosome *Chromosome =
         Pop.GetChromosome(ChromIdx);

      TotalFitness += Chromosome->GetFitness();
      CalcWeightAndValue(Chromosome, Weight, Value);
      printf("%3u %4.0f %3d %3d ",
            ChromIdx, Chromosome->GetFitness(),
            Value, Weight);
      for (size_t BitIdx = 0;
          BitIdx < Chromosome->GetLength();

          BitIdx++) {
        printf("%1u", (*Chromosome)[BitIdx]);
      }
      printf("\n");
   }
   printf(
   "Gen, Best, Avg, Worst: %4d, %6.2f, %6.2f, %6.2f\n",
    Pop.GetGeneration(), Pop.GetBestFitness(),
    TotalFitness / ChromIdx,
    Pop.GetChromosome(ChromIdx - 1)->GetFitness());
   getchar();
}

// Check if a solution has been found. By definition
// it must have a value of ANSWER (24) and not exceed
// MAXWEIGHT (17). Since the fittest chromosome could
// violate the weight constraint FoundSolution must
// search through the population of chromosomes.

Bool FoundSolution(
   CGAPopulation& Pop)
{
   const int  ANSWER = 24;
   int        Weight;
   int        Value;

   for (size_t ChromIdx = 0;
       ChromIdx < Pop.GetPopulationSize();
       ChromIdx++) {
     CalcWeightAndValue(Pop.GetChromosome(ChromIdx),
                     Weight, Value);
     if (Weight <= MAXWEIGHT && Value == ANSWER) {
        return TRUE;
     }
   }
   return FALSE;
}

// Calculate the fitness of each chromosome by adding
// its weight to its value then subtracting a PENALITY
// for the excess weight.

float CalcFitness(
   CGAChromosome *Chromosome)
{
   const float  PENALITY = 3.0;
   int          Weight;
   int          Value;

   CalcWeightAndValue(Chromosome, Weight, Value);
   if (Weight > MAXWEIGHT) {
      return Value - PENALITY * (Weight - MAXWEIGHT);
   } else {
      return Value;
   }
}

// Calculate the weight and value of the chromosome by
// accumulating the weight and value of each item
// whose bit in the chromosome is set true.

void CalcWeightAndValue(
   CGAChromosome *Chromosome,
   int& Weight,
   int& Value)
{
   Weight = 0;
   Value  = 0;
   for (size_t Idx = 0; Idx < Chromosome->GetLength();
       Idx++) {
     if ((*Chromosome)[Idx]) {
        Weight += ItemDesc[Idx].Weight;
        Value += ItemDesc[Idx].Value;
     }
   }
}
/* End of File */