-
-
Save codepr/e4d0b564b49c621aa6c3 to your computer and use it in GitHub Desktop.
Simple genetic algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
#include <time.h> | |
#define POP_SIZE 4096 | |
#define STEP 96 | |
#define UNIFORM_RATE 0.5 | |
#define MUTATION_RATE 0.15 | |
#define TOURNAMENT_SIZE 15 | |
#define ELITISM 1 | |
#define RANDBETWEEN(A,B) A + rand()/(RAND_MAX/(B - A)) | |
#define CHANCE(A) rand() < A * RAND_MAX | |
static void pretty_print(char *string) { | |
for(string; *string != '\0'; ++string) { | |
printf("%c", *string); | |
} | |
printf("\n"); | |
} | |
static int fitness(char* solution, char* gene) { | |
int fitness = 0; | |
for(solution; *solution != '\0'; ++solution, ++gene) { | |
if(*solution == *gene) | |
fitness++; | |
} | |
return fitness; | |
} | |
static char* fittest(char* population, char *solution) { | |
int cur_fitness = 0; | |
int max_fitness = 0; | |
char *p = malloc(sizeof(*p) * (STEP + 1)); | |
for(population; *population != '\0'; population += STEP) { | |
cur_fitness = fitness(solution, population); | |
if(cur_fitness >= max_fitness) { | |
max_fitness = cur_fitness; | |
memcpy(p, population, STEP); | |
} | |
} | |
return p; | |
} | |
static void mutate(char* gene) { | |
for(gene; *gene != '\0'; ++gene) { | |
if(RANDBETWEEN(0.0, 1.0) <= MUTATION_RATE) { | |
*gene = RANDBETWEEN(0, 2) + '0'; | |
} | |
} | |
} | |
static char* crossover(char* individual1, char* individual2) { | |
char *p = malloc(sizeof(*p) * (STEP + 1)); | |
int i = 0; | |
for(i = 0; i < strlen(individual1); ++i) { | |
if(RANDBETWEEN(0.0, 1.0) <= UNIFORM_RATE) { | |
memcpy(p+i, individual1+i, 1); | |
} else { | |
memcpy(p+i, individual2+i, 1); | |
} | |
} | |
return p; | |
} | |
static char* tournament_selection(char *population, char *solution) { | |
int i = 0; | |
char p[TOURNAMENT_SIZE * STEP]; | |
for(i; i < TOURNAMENT_SIZE*STEP; i += STEP) { | |
memcpy(p+i, population+(RANDBETWEEN(0, strlen(population) / STEP)), STEP); | |
} | |
return fittest(p, solution); | |
} | |
static char* evolve(char* population, char* solution) { | |
char *p = malloc(sizeof(*p) * (POP_SIZE + 1)); | |
int i = 0; | |
if(ELITISM) { | |
char *f = fittest(population, solution); | |
memcpy(p, f, STEP); | |
free(f); | |
i += STEP; | |
} | |
for(i; i < POP_SIZE - STEP; i += STEP) { | |
char *gene_1 = tournament_selection(population, solution); | |
char *gene_2 = tournament_selection(population, solution); | |
char *new_gene = crossover(gene_1, gene_2); | |
mutate(new_gene); | |
memcpy(p+i, new_gene, STEP); | |
free(gene_1); | |
free(gene_2); | |
free(new_gene); | |
} | |
return p; | |
} | |
int main(int argv, char** argc) { | |
srand((unsigned int)time(NULL)); | |
char a[STEP]; | |
int i = 0; | |
for(i = 0; i < STEP; ++i) { | |
*(a + i) = RANDBETWEEN(0, 2) + '0'; | |
} | |
char population[POP_SIZE]; | |
for(i = 0; i < POP_SIZE; ++i) { | |
*(population + i) = RANDBETWEEN(0, 2) + '0'; | |
} | |
int generations = 0; | |
int fit = 0; | |
int loop = 1; | |
while(loop == 1) { | |
char *fittest_gene = fittest(population, a); | |
fit = fitness(a, fittest_gene); | |
generations++; | |
printf("Generation: %d Fitness: %d\n", generations, fit); | |
free(fittest_gene); | |
if(fit == STEP) { | |
loop = 0; | |
} else { | |
char *new_pop = evolve(population, a); | |
memcpy(population, new_pop, POP_SIZE); | |
free(new_pop); | |
} | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment