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
|
// genetic_char.c - Example: evolving a string to match a target
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
typedef char *ga_individual_t;
#define GENETIC_IMPLEMENTATION
#include "../include/genetic.h"
#define POPULATION_N 100
#define RATE_SELECTION 0.5
#define RATE_MUTATION 0.2
#define ERROR 0
#define TARGET_STRING \
" !\"#$%&'()*+,-./" \
"0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`" \
"abcdefghijklmnopqrstuvwxyz{|}~"
#define generate() ((char)(rand() % (127 - 32) + 32))
void crossover(char **y, char *x0, char *x1) {
if (!y || !x0 || !x1)
return;
uint32_t lx0 = strlen(x0);
uint32_t lx1 = strlen(x1);
if (lx0 == 0 || lx1 == 0)
return;
uint32_t ix0 = rand() % lx0;
uint32_t ix1 = rand() % lx1;
uint32_t ly = ix0 + (lx1 - ix1);
char *sy = malloc(ly + 1);
if (!sy) {
free(*y);
*y = NULL;
return;
}
memcpy(sy, x0, ix0);
memcpy(sy + ix0, x1 + ix1, lx1 - ix1);
sy[ly] = 0;
free(*y);
*y = sy;
}
void mutation(char **x) {
if (!x || !*x) return;
uint32_t l = strlen(*x);
if (l == 0) return;
uint32_t i = rand() % l;
(*x)[i] = generate();
}
double fitness(char *individual, void const *data) {
if (!individual) return 1e30;
double error = 0;
char const *target = (char const *)data;
while (*individual && *target) {
error += abs((unsigned char)*target - (unsigned char)*individual);
target++;
individual++;
}
while (*individual) {
error += (unsigned char)*individual++;
}
while (*target) {
error += (unsigned char)*target++;
}
return error;
}
int main(void) {
char const *target = TARGET_STRING;
char *population[POPULATION_N];
srand(time(0));
// Initialize population
for (uint64_t i = 0; i < POPULATION_N; i++) {
uint64_t n = rand() % 5 + 20;
char *str = malloc(n + 1);
if (!str) {
fprintf(stderr, "Failed to allocate string\n");
for (uint64_t k = 0; k < i; k++) free(population[k]);
exit(1);
}
str[n] = (uint8_t)0;
for (uint64_t j = 0; j < n; j++) {
str[j] = generate();
}
population[i] = str;
}
printf("TARGET: %s\n", TARGET_STRING);
fflush(stdout);
clock_t t0 = clock();
uint32_t n = 0;
// Conduct optimization
double error = 1;
uint32_t max_iterations = 1000000;
while (error > ERROR && n < max_iterations) {
error =
ga_generation(population, POPULATION_N, RATE_SELECTION, RATE_MUTATION,
fitness, (void const *)target, crossover, mutation);
n++;
printf("\rSOLUTION: %s", population[0]);
}
clock_t t1 = clock();
printf("\nSOLUTION: %s\nITERATIONS: %u\nTIME: %f ms\n", population[0], n,
1000.0 * (t1 - t0) / CLOCKS_PER_SEC);
for (int i = 0; i < POPULATION_N; i++) {
free(population[i]);
}
}
|