Simple C genetic algorithm example

/**
 * description:
 *  Simple genetic algorithm for finding equation that equals target number
 *  example for number 27 has many results:
 *      - 7+29-8-1
 *      - 15+28-16
 *  this code isn't really perfect ^_^ but shows some basics.
 *  tested in linux fedora 14 with valgrind.
 *
 * author: ADRABI Abderrahim (adrabi[at]mail[dot]ru)
 * date: 2011-10-03
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define POPSIZE     1024
#define ELITRATE    0.1f
#define MUTATIONRATE    0.25f
#define ELEMENTS    8
#define MUTATION    RAND_MAX * MUTATIONRATE
#define TARGET      27

/**
 * Basic elements for construction an equation
 */
static const char *BIN_ELEMENTS[12] = {
  "0000\0",         // 0
  "0001\0",         // 1
  "0010\0",         // 2
  "0011\0",         // 3
  "0100\0",         // 4
  "0101\0",         // 5
  "0110\0",         // 6
  "0111\0",         // 7
  "1000\0",         // 8
  "1001\0",         // 9
  "1010\0",         // +
  "1011\0"          // -
};

/**
 * Structure base of genome
 */
typedef struct
{
  unsigned int fitness;
  char *gen;
} ga_struct;

/**
 * Initialize new random population
 */
void
init_population (ga_struct * population, ga_struct * beta_population)
{
  const int bin_size = (sizeof (char) * ELEMENTS * 4) + 1;
  int index = 0;
  for (; index < POPSIZE; index++)
    {
      // default initialization/ create empty genome
      population[index].fitness = 0;
      population[index].gen = malloc (bin_size);
      *population[index].gen = '\0';

      // default initialization/ create empty genome
      beta_population[index].fitness = 0;
      beta_population[index].gen = malloc (bin_size);
      *beta_population[index].gen = '\0';

      int e = 0;
      for (; e < ELEMENTS; e++)
    {
      // put random element in population
      // 12 is count of elements in BIN_ELEMENTS array
      strcat (population[index].gen, BIN_ELEMENTS[(rand () % 12)]);
    }
    }
}

/**
 * Calculate each individual fitness in population
 */
void
cal_fitness (ga_struct * population)
{
  int index = 0;
  int unsigned fitness = 0;
  for (; index < POPSIZE; index++)
    {
      char *gen_str = population[index].gen;
      int gen_len = strlen (gen_str), sum = 0, current_value = 0, step = 0;
      unsigned int last_operator_index = -1;
      char last_operator = (char) 0;

      for (; step < ELEMENTS; step++)
    {
      char element[5] = "\0";
      strncpy (element, gen_str, 4);
      if (strcmp ("0000", element) == 0)
        {
          current_value *= 10;
        }
      else if (strcmp ("0001", element) == 0)
        {
          current_value = (current_value * 10) + 1;
        }
      else if (strcmp ("0010", element) == 0)
        {
          current_value = (current_value * 10) + 2;
        }
      else if (strcmp ("0011", element) == 0)
        {
          current_value = (current_value * 10) + 3;
        }
      else if (strcmp ("0100", element) == 0)
        {
          current_value = (current_value * 10) + 4;
        }
      else if (strcmp ("0101", element) == 0)
        {
          current_value = (current_value * 10) + 5;
        }
      else if (strcmp ("0110", element) == 0)
        {
          current_value = (current_value * 10) + 6;
        }
      else if (strcmp ("0111", element) == 0)
        {
          current_value = (current_value * 10) + 7;
        }
      else if (strcmp ("1000", element) == 0)
        {
          current_value = (current_value * 10) + 8;
        }
      else if (strcmp ("1001", element) == 0)
        {
          current_value = (current_value * 10) + 9;
        }
      // ignore elements that have two flowed operators or ends with operators like:
      //         * 1+-1++-1
      //         * 2333+55+
      else if (strcmp ("1010", element) == 0
           && step - last_operator_index > 1 && step + 1 < ELEMENTS)
        {
          if (last_operator == (char) 0)
        {
          sum = current_value;
        }
          else if (last_operator == '+')
        {
          sum += current_value;
        }
          else if (last_operator == '-')
        {
          sum -= current_value;
        }

          current_value = 0;
          last_operator_index = step;
          last_operator = '+';
        }
      // ignore elements that have two flowed operators or ends with operators like:
      //         * 1+-1++-1
      //         * 2333+55+
      else if (strcmp ("1011", element) == 0
           && step - last_operator_index > 1 && step + 1 < ELEMENTS)
        {
          if (last_operator == (char) 0)
        {
          sum = current_value;
        }
          else if (last_operator == '+')
        {
          sum += current_value;
        }
          else if (last_operator == '-')
        {
          sum -= current_value;
        }

          current_value = 0;
          last_operator_index = step;
          last_operator = '-';
        }
      else
        {
          /// error the binary string not found
          sum = 999999;
          break;
        }
      gen_str += 4;
    }

      if (last_operator == '+')
    {
      sum += current_value;
    }
      else if (last_operator == '-')
    {
      sum -= current_value;
    }

      // abs, because fitness is unsigned integer ^_^
      population[index].fitness = abs (sum - TARGET);
    }
}

/**
 * sort function needed by quick sort
 */
int
sort_func (const void *e1, const void *e2)
{
  return ((ga_struct *) e1)->fitness - ((ga_struct *) e2)->fitness;
}

/**
 * sort population by fitness
 */
inline void
sort_by_fitness (ga_struct * population)
{
  qsort (population, POPSIZE, sizeof (ga_struct), sort_func);
}

/**
 * select elit element in top array after sort
 */
void
elitism (ga_struct * population, ga_struct * beta_population, int esize)
{
  const int gen_len = ELEMENTS * 4 + 1;
  int index = 0;
  for (; index < esize; index++)
    {
      int e = 0;
      for (; e < gen_len; e++)
    {
      beta_population[index].gen[e] = population[index].gen[e];
    }
    }
}

/**
 * mutate an individual with random rate
 */
void
mutate (ga_struct * member)
{
  int tsize = strlen (member->gen);
  int number_of_mutations = rand () % 10;
  int m = 0;
  for (; m < number_of_mutations; m++)
    {
      int apos = rand () % tsize;

      if (member->gen[apos] == '0')
    {
      member->gen[apos] = '1';
    }
      else
    {
      member->gen[apos] = '0';
    }
    }
}

/**
 * mate randomly the rest of population after elitism
 */
void
mate (ga_struct * population, ga_struct * beta_population)
{
  int esize = POPSIZE * ELITRATE;

  // elitism of top elements in array
  elitism (population, beta_population, esize);

  // mate the rest of shitty population xD
  int m = esize, i1 = -1, i2 = -1, pos = -1, tsize = ELEMENTS * 4 + 1;
  for (; m < POPSIZE; m++)
    {
      pos = rand () % tsize;
      i1 = rand () % POPSIZE;
      i2 = rand () % POPSIZE;

      int i = 0;
      for (; i < pos; i++)
    {
      beta_population[m].gen[i] = population[i1].gen[i];
    }
      for (i = pos; i < tsize; i++)
    {
      beta_population[m].gen[i] = population[i2].gen[i];
    }

      if (rand () < MUTATION)
    {
      mutate (&beta_population[m]);
    }
    }
}

/**
 * decode binary string to readable format
 */
void
decode_gen (ga_struct * member)
{
  char *gen_str = member->gen;
  int step = 0;

  for (; step < ELEMENTS; step++)
    {
      char element[5] = "\0";
      strncpy (element, gen_str, 4);
      if (strcmp ("0000", element) == 0)
    {
      printf ("0");
    }
      else if (strcmp ("0001", element) == 0)
    {
      printf ("1");
    }
      else if (strcmp ("0010", element) == 0)
    {
      printf ("2");
    }
      else if (strcmp ("0011", element) == 0)
    {
      printf ("3");
    }
      else if (strcmp ("0100", element) == 0)
    {
      printf ("4");
    }
      else if (strcmp ("0101", element) == 0)
    {
      printf ("5");
    }
      else if (strcmp ("0110", element) == 0)
    {
      printf ("6");
    }
      else if (strcmp ("0111", element) == 0)
    {
      printf ("7");
    }
      else if (strcmp ("1000", element) == 0)
    {
      printf ("8");
    }
      else if (strcmp ("1001", element) == 0)
    {
      printf ("9");
    }
      else if (strcmp ("1010", element) == 0)
    {
      printf ("+");
    }
      else if (strcmp ("1011", element) == 0)
    {
      printf ("-");
    }
      gen_str += 4;
    }

  printf ("\n");
}

/**
 * free memory before exit program
 */
void
free_population (ga_struct * population)
{
  int index = 0;
  for (; index < POPSIZE; index++)
    {
      free (population[index].gen);
    }
  free (population);
}

/**
 * swap arrays pointers
 */
void
swap (ga_struct ** p1, ga_struct ** p2)
{
  ga_struct *tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}

/**
 * main program
 */
int
main (void)
{
  srand (time (NULL));

  ga_struct *population = malloc (sizeof (ga_struct) * POPSIZE);
  ga_struct *beta_population = malloc (sizeof (ga_struct) * POPSIZE);

  init_population (population, beta_population);

  int index = 0;
  for (; index < POPSIZE; index++)
    {
      cal_fitness (population);
      sort_by_fitness (population);

      // print current best individual
      printf ("binary string: %s - fitness: %d\n", population[0].gen,
          population[0].fitness);

      if (population[0].fitness == 0)
    {
      //~ print equation
      decode_gen (&population[0]);
      break;
    }

      mate (population, beta_population);
      swap (&population, &beta_population);
    }

  free_population (population);
  free_population (beta_population);

  return 0;
}