create simple genetic algorithm in c

5 files changed, 251 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..07c0265
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,3 @@
+*.swp
+*.swo
+example
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..658bce0
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,2 @@
+example: genalg.h genalg.c genalg.example.c
+	gcc -g -o example genalg.c genalg.example.c -Wall -Wextra -Wpedantic -Werror -lm
diff --git a/genalg.c b/genalg.c
new file mode 100644
index 0000000..01d394b
--- /dev/null
+++ b/genalg.c
@@ -0,0 +1,134 @@
+#include <float.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <math.h>
+#include "genalg.h"
+
+
+genalg_t * ga_create(
+  size_t pop_count, 
+  double (*fitness)(void*),
+  void * (*create_child)(void*),
+  void (*org_free)(void*)
+) {
+  genalg_t *ga = malloc(sizeof(genalg_t));
+  if (ga == NULL) {
+    fprintf(stderr, "failed to allocate genalg_t structure\n");
+    return NULL;
+  }
+  ga->population = malloc(pop_count * sizeof(void*));
+  if (ga->population == NULL) {
+    fprintf(stderr, "failed to allocate population buffer\n");
+    free(ga);
+    return NULL;
+  }
+  ga->pop_count = pop_count;
+  ga->fitness = fitness;
+  ga->create_child = create_child;
+  ga->org_free = org_free;
+  return ga;
+}
+
+
+void ga_free(genalg_t *ga) {
+  for (size_t i=0; i<ga->pop_count; i++) {
+    ga->org_free(ga->population[i]);
+  }
+  free(ga->population);
+  free(ga);
+}
+
+
+void * ga_tournament_select(genalg_t *ga, int tournament_sz) {
+  double best_fitness = -DBL_MAX;
+  size_t best_index = 0;
+
+  for (int i=0; i<tournament_sz; i++) {
+    size_t idx = rand() % ga->pop_count;
+    double fitness = ga->fitness(ga->population[idx]);
+    if (fitness > best_fitness) {
+      best_fitness = fitness;
+      best_index = idx;
+    }
+  }
+
+  return ga->population[best_index];
+}
+
+
+struct genalg_stats_t ga_population_statistics(genalg_t *ga) {
+  struct genalg_stats_t stats = { 0, 0, DBL_MAX, -DBL_MAX, NULL };
+  // compute mean
+  for (size_t i=0; i<ga->pop_count; i++) {
+    stats.mean += ga->fitness(ga->population[i]);
+  }
+  stats.mean /= ga->pop_count;
+  // compute other stats
+  for (size_t i=0; i<ga->pop_count; i++) {
+    double fitness = ga->fitness(ga->population[i]);
+    double diff = fitness - stats.mean;
+    stats.variance += diff*diff;
+    stats.min = fmin(stats.min, fitness);
+    stats.max = fmax(stats.max, fitness);
+    if (stats.max == fitness) {
+      stats.best = ga->population[i];
+    }
+  }
+
+  return stats;
+}
+
+
+// helper: qsort from fittest to least fit
+double (*fitness_sort_cmp)(void*) = NULL;
+int fitness_sort(const void *a, const void *b) {
+  if (fitness_sort_cmp == NULL) {
+    return 0;
+  }
+
+  double fa = fitness_sort_cmp((void*)a);
+  double fb = fitness_sort_cmp((void*)b);
+  if (fa < fb) { return 1; }
+  if (fa > fb) { return -1; }
+  return 0;
+}
+
+
+int ga_replace_population(genalg_t *ga, int tournament_sz, int keep) {
+  // create new population buffer
+  void **new_population = malloc(ga->pop_count * sizeof(void*));
+  if (new_population == NULL) {
+    fprintf(stderr, "failed to allocate new population buffer\n");
+    return 1;
+  }
+
+  // copy [keep] most fit from previous generation
+  if (keep) {
+    fitness_sort_cmp = ga->fitness;
+    qsort(ga->population, ga->pop_count, sizeof(void*), fitness_sort);
+    memcpy(new_population, ga->population, keep * sizeof(void*));
+  }
+
+  // fill new_population with children
+  for (size_t i=keep; i<ga->pop_count; i++) {
+    void * parent = ga_tournament_select(ga, tournament_sz);
+    new_population[i] = ga->create_child(parent);
+    if (new_population[i] == NULL) {
+      for (size_t j=0; j<i; j++) {
+        ga->org_free(new_population[j]);
+      }
+      free(new_population);
+      return 1;
+    }
+  }
+
+  // delete un-kept population
+  for (size_t i=keep; i<ga->pop_count; i++) {
+    ga->org_free(ga->population[i]);
+  }
+  free(ga->population);
+  ga->population = new_population;
+
+  return 0;
+}
diff --git a/genalg.example.c b/genalg.example.c
new file mode 100644
index 0000000..cfd7d4c
--- /dev/null
+++ b/genalg.example.c
@@ -0,0 +1,78 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+#include "genalg.h"
+
+
+struct organism_t {
+  double fitness, a, b;
+};
+
+
+double randf() {
+  return 2.0 * (((double)rand())/RAND_MAX) - 1.0;
+}
+
+
+struct organism_t * org_alloc(int randomize) {
+  struct organism_t * org = malloc(sizeof(struct organism_t));
+  if (org == NULL) {
+    fprintf(stderr, "failed to allocate organism!\n");
+    return NULL;
+  }
+
+  org->fitness = -1;
+  org->a = 0;
+  org->b = 0;
+
+  if (randomize) {
+    org->a = 20.0 * randf();
+    org->b = 20.0 * randf();
+  }
+
+  return org;
+}
+
+
+double org_fitness(void *ptr) {
+  struct organism_t *org = ptr;
+  if (org->fitness >= 0) {
+    return org->fitness;
+  } else {
+    double error = pow(org->a - 14.0, 2) + pow(org->b + 7.0, 2);
+    org->fitness = 1.0/(fabs(error)+1);
+    return org->fitness;
+  }
+}
+
+
+void * create_child(void *ptr) {
+  struct organism_t *org = ptr;
+  struct organism_t *child = org_alloc(0);
+  if (child == NULL) {
+    return NULL;
+  }
+  child->a = org->a + 0.1*randf();
+  child->b = org->b + 0.1*randf();
+  return child;
+}
+
+
+int main() {
+  genalg_t *ga = ga_create(1000, org_fitness, create_child, free);
+  for (size_t i=0; i<ga->pop_count; i++) {
+    ga->population[i] = org_alloc(1);
+  }
+  struct genalg_stats_t stats;
+  for (int i=0; i<100; i++) {
+    ga_replace_population(ga, 60, 50);
+    stats = ga_population_statistics(ga);
+    struct organism_t *org = stats.best;
+    printf(
+      "mean: %f, variance: %f\nmin: %f, max: %f\nbest: (%f, %f)\n",
+      stats.mean, stats.variance, stats.min, stats.max,
+      org->a, org->b
+    );
+  }
+  return 0;
+}
diff --git a/genalg.h b/genalg.h
new file mode 100644
index 0000000..33066bb
--- /dev/null
+++ b/genalg.h
@@ -0,0 +1,34 @@
+#ifndef GENALG_H
+#define GENALG_H
+
+
+typedef struct genalg_t {
+  void ** population;
+  size_t pop_count;
+
+  double (*fitness)(void*);
+  void * (*create_child)(void*);
+  void (*org_free)(void*);
+} genalg_t;
+
+
+struct genalg_stats_t {
+  double mean, variance;
+  double min, max;
+  void * best;
+};
+
+
+genalg_t * ga_create(
+  size_t pop_count, 
+  double (*fitness)(void*),
+  void * (*create_child)(void*),
+  void (*org_free)(void*)
+);
+void ga_free(genalg_t *ga);
+void * ga_tournament_select(genalg_t *ga, int tournament_sz);
+struct genalg_stats_t ga_population_statistics(genalg_t *ga);
+int ga_replace_population(genalg_t *ga, int tournament_sz, int keep);
+
+
+#endif