1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
// genetic.h - A simple genetic algorithm implementation
#ifndef GENETIC_H
#define GENETIC_H
#include <assert.h>
#include <stdint.h>
struct ga_individual_t;
// ga_crossover_t
//
// Type definition for a crossover function
//
// uintptr_t * - The address for the child pointer
// uintptr_t - Parent pointer
// uintptr_t - Parent pointer
typedef void (*ga_crossover_t)(ga_individual_t *, ga_individual_t,
ga_individual_t);
// ga_mutation_t
//
// Type definition for a crossover function
//
// uintptr_t - The individual being mutated
typedef void (*ga_mutation_t)(ga_individual_t);
// ga_fitness_t()
//
// Type definition for a fitness function
//
// uintptr_t - The individual on which to run the fitness function
// void const * - The user defined data pointer
typedef double (*ga_fitness_t)(ga_individual_t, void const *);
double ga_generation(ga_individual_t *, uint32_t, double, double, ga_fitness_t,
void const *, ga_crossover_t, ga_mutation_t);
#endif // ga_H
#ifdef GENETIC_IMPLEMENTATION // IMPLEMENTATION
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <tgmath.h>
// ga_finess_sort()
//
// Run the fitness function on
//
// population - An array of pointers to each individual
// population_n - The size of the population array
// fitness - The function used to evaluate the fitness of an individual
// fitness_data - Additional data required for the fitness function
//
// return - The error for the best performing individual
static double ga_fitness_sort(ga_individual_t *population,
uint32_t population_n, ga_fitness_t fitness,
void const *fitness_data) {
double *fitness_buffer = calloc(population_n, sizeof(double));
double fitness_current = 0;
ga_individual_t individual;
// Insertion sort
uint32_t i, j, k;
for (i = 0; i < population_n; i++) {
fitness_current = fabs(fitness(population[i], fitness_data));
individual = population[i];
// for (j = i; j > 0 && fitness_current > fitness_buffer[j - 1]; j--) {
for (j = i; j > 0 && fitness_current < fitness_buffer[j - 1]; j--) {
}
// Shift array back by one for sorting
for (k = i; k > j; k--) {
population[k] = population[k - 1];
fitness_buffer[k] = fitness_buffer[k - 1];
}
population[j] = individual;
fitness_buffer[j] = fitness_current;
}
// for (i = 0; i < population_n; i++) {
// printf("%u - %lf\n", i, fitness_buffer[i]);
// }
double error = fitness_buffer[0];
free(fitness_buffer);
return error;
}
// ga_generation()
//
// Run a single generation of the genetic algorithm
//
// population - An array of pointers to each individual
// population_n - The size of the population array
// rate_selection - A number [0,1] denoting the percentage of the population
// which survives to the next generation
// rate_mutation - A number [0,1] denoting the percentage of new individuals
// which will recieve mutations
// fitness - The function used to evaluate the fitness of an individual
// fitness_data - Additional data required for the fitness function
// crossover - The function used to perform repopulation via the
// combination of two parents
// mutation - The function used to perform mutations on a given individual
//
// return - The error of the best performing individual
double ga_generation(ga_individual_t *population, uint32_t population_n,
double rate_selection, double rate_mutation,
ga_fitness_t fitness, void const *fitness_data,
ga_crossover_t crossover, ga_mutation_t mutation) {
// assert(0 < rate_selection && rate_selection <= 1.0);
// assert(0 < rate_mutation && rate_mutation <= 1.0);
assert(2 < population_n);
uint32_t selection_n = rate_selection * population_n;
// Crossover
for (uint32_t i = selection_n; i < population_n; i++) {
uint32_t parent_i = rand() % selection_n;
uint32_t parent_j = rand() % selection_n;
// printf("%p - %p\n", &population[i], population[i]);
crossover(&population[i], population[parent_i], population[parent_j]);
}
// Mutation
uint32_t mutation_n = rate_mutation * (population_n - selection_n);
for (uint32_t i = 0; i < mutation_n; i++) {
uint32_t mutation_i = rand() % (population_n - selection_n) + selection_n;
mutation(population[mutation_i]);
}
// Fitness
return ga_fitness_sort(population, population_n, fitness, fitness_data);
}
#endif
|