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
|
#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;
}
|
