From cc69389d79e4bed927e9aa29b8769c2ad4f90d8c Mon Sep 17 00:00:00 2001 From: sanine Date: Sat, 25 Oct 2025 11:09:32 -0500 Subject: create simple genetic algorithm in c --- .gitignore | 3 ++ Makefile | 2 + genalg.c | 134 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ genalg.example.c | 78 ++++++++++++++++++++++++++++++++ genalg.h | 34 ++++++++++++++ 5 files changed, 251 insertions(+) create mode 100644 .gitignore create mode 100644 Makefile create mode 100644 genalg.c create mode 100644 genalg.example.c create mode 100644 genalg.h 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 +#include +#include +#include +#include +#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; ipop_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; ipop_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; ipop_count; i++) { + stats.mean += ga->fitness(ga->population[i]); + } + stats.mean /= ga->pop_count; + // compute other stats + for (size_t i=0; ipop_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; ipop_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; jorg_free(new_population[j]); + } + free(new_population); + return 1; + } + } + + // delete un-kept population + for (size_t i=keep; ipop_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 +#include +#include +#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; ipop_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 -- cgit v1.2.1