summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.gitignore3
-rw-r--r--Makefile2
-rw-r--r--genalg.c134
-rw-r--r--genalg.example.c78
-rw-r--r--genalg.h34
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
generated by cgit v1.2.1 (git 2.18.0) at 2025-10-31 06:03:31 +0000