I'm trying to solve a CodeWars problem called "Training on Binary Genetic Algorithms." There is a fitness function that is preloaded. When the program is run, a test function creates a random 35-bit string and it uses my run function which is supposed to return the same 35-bit string. This string is supposed to be found using a genetic algorithm.
Here is my code:
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
typedef double fitness_t (const char *, ...);
extern fitness_t fitness;
void generate (size_t length, char * s)
{
for (size_t i = 0; i < length; i )
s[i] = rand() % 2 48;
}
double sum(size_t n, double ar[n])
{
double sum = 0;
for (int i = 0; i < n; i )
sum = ar[i];
return sum;
}
void select (int size, char* population[size], double fitnesses[size])
{
double probabilities[size]; // normalized to 1
double r; // random number
int s1, s2;
int i;
for (i = 0; i < size; i )
probabilities[i] = fitnesses[i] / sum(size, fitnesses);
// select first chromosome
r = (double)(rand() % 1000000) / 1000000; // generates a random float between 0 and 1
for (i = 0; i < size && r > 0; i )
r -= probabilities[i];
s1 = i;
// select second chromosome
s2 = s1;
while (s2 == s1) // ensures the two chromosomes aren't the same
{
r = (double)(rand() % 1000000) / 1000000; // generates a random float between 0 and 1
for (i = 0; i < size && r > 0; i )
r -= probabilities[i];
s2 = i;
}
// places these two chromosomes on top
char * temp = population[0];
population[0] = population[s1];
population[s1] = temp;
temp = population[1];
population[1] = population[s2];
population[s2] = temp;
}
void crossover (size_t n, char* s1, char* s2)
{
int r = rand() % n; // select a random bit to cross over at
char temp;
for (size_t i = r; i < n; i ) // swap every bit from bit r to bit n
{
temp = s1[i];
s1[i] = s2[i];
s2[i] = temp;
}
}
void mutate (size_t n, char* s, double p)
{
double r;
for (size_t i = 0; i < n; i ) // for each bit
{
r = (double)(rand() % 1000000) / 1000000; // random float between 0 and 1
if (r <= p) // if random number is less than probability
{
if (s[i] == '1') s[i] = '0'; // swap 0s and 1s
else s[i] = '1';
}
}
}
void bubbleSortPop(int size, char * population[size], double fitnesses[size])
{
int i, j;
char * temp_chrome;
double temp_fitness;
for (i = 0; i < size - 1; i )
// Last i elements are already in place
for (j = 0; j < size - i - 1; j )
if (fitnesses[j] < fitnesses[j 1])
{
temp_chrome = population[j];
population[j] = population[j 1];
population[j 1] = temp_chrome;
temp_fitness = fitnesses[j];
fitnesses[j] = fitnesses[j 1];
fitnesses[j 1] = temp_fitness;
}
}
// this function changes the population.
// select, crossover, mutate
void evolve(fitness_t f, size_t size, int length, char * population[size],
double fitnesses[size], double p_c, double p_m)
{
char * s1, * s2;
double f1, f2;
char * temp_pop[size 2];
double temp_fit[size 2];
int i;
double r;
// moves two selected parents to the top
select(size, population, fitnesses);
// begin reproduction process; duplicate the chromosomes
s1 = population[0];
s2 = population[1];
// crossover
r = (double)(rand() % 1000000) / 1000000; // random float between 0 and 1
if (r < p_c) // probability of crossing over
crossover(length, s1, s2); // commences with crossover
// mutate
mutate(length, s1, p_m);
mutate(length, s2, p_m);
// calculate fitnesses
f1 = f(s1);
f2 = f(s2);
// merge fitneses
// copy original fitnesses into temp_fit
for (i = 0; i < size; i )
temp_fit[i] = fitnesses[i];
// add new fitnesses
temp_fit[size] = f1;
temp_fit[size 1] = f2;
// merge children into population
// copy original population into temp_pop
for (i = 0; i < size; i )
temp_pop[i] = population[i];
// add two children to temp_pop
temp_pop[size] = s1;
temp_pop[size 1] = s2;
// sort fitnesses and population
bubbleSortPop(size 2, temp_pop, temp_fit);
// add first 100 elements of temp_pop and fit to population and fitnesses
for (i = 0; i < size; i )
{
population[i] = temp_pop[i];
fitnesses[i] = temp_fit[i];
}
}
char* runN (fitness_t f, int length, double p_c, double p_m, size_t iterations) {
}
char* run (fitness_t f, int length, double p_c, double p_m)
{
size_t size = 100;
char * population[size];
double fitnesses[size];
size_t i;
int r;
srand(time(0));
// initialize population array
for (i = 0; i < size; i )
population[i] = malloc((length 1) * sizeof(char));
// generate original population
for (i = 0; i < size; i )
{
generate(length, population[i]);
fitnesses[i] = f(population[i]);
printf("[-] %s %lf\n", i, population[i], fitnesses[i]);
}
// evolve the population
for (i = 0; i < 10; i )
evolve(f, size, length, population, fitnesses, p_c, p_m);
// print result
printf("\nAFTER EVOLUTION\n");
for (i = 0; i < size; i ) // generates original population
printf("[-] %s %lf\n", i, population[i], fitnesses[i]);
// store best chromosome and free memory
char ret[length 1];
strcpy(ret, population[0]);
for (i = 0; i < size; i )
free(population[i]);
return ret;
}
The issue is when I run my code, it nearly always comes out with a segfault at some point while printing the contents of population and fitness.
CodePudding user response：
At least these problems:
Attempting to print a non-string with "%s"
Code uses "%s" and passes population[i] as if it points to a string. population[i] does not point to a string as it does not certainly have a null character. Result undefined behavior (UB). Perhaps attempting to access beyond allocated memory.
// Undefined behavior: population[i] not a string
printf("[-] %s %lf\n", i, population[i], fitnesses[i]);
Set the null character.
generate(length, population[i]);
population[i][length] = '\0'; // Add this here or equivalent in `generate()`.
Many compiler warnings (20 )
Enable all compiler warnings and fix those.
CodePudding user response：
I found the solution. It was all the places where I tried to copy a string by making a string pointer and assigning it the same address as the pointer I wanted to copy. For example, in 'select', when I tried to move the two strings to the top, I did
char * temp = population[0];
population[0] = population[s1];
population[s1] = temp;
temp = population[1];
population[1] = population[s2];
population[s2] = temp;
I changed this to using strcpy(). I made the same mistake in 'evolve' where I tried to duplicate the chromosomes by just copying their address into variables, rather than the strings themselves:
char * s1, * s2;
// begin reproduction process; duplicate the chromosomes
s1 = population[0];
s2 = population[1];
I changed it to this:
char s1[length 1], s2[length 1];
strcpy(s1, population[0]);
strcpy(s2, population[1]);
After I made this change the segfault went away. Thanks for all your answers.