GeneticAlgorithm.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <math.h>

typedef struct{
    int pop;
    int minGeneValue;
    int maxGeneValue;
    int size;
    int numParents;
    int mutationRate;
    int maxGens;
    int verbosity;
    char fitnessFunc[50];
}Config;

void printIndividual(char* pre, int* population, Config config, int i, int (*clac_ptr)());
void printPopulation(int* population, Config config, int* fitness);
int* initialisePopulation(int* population, Config config);
int* naturalSelection(int* primePopulation, int* population, int* fitness, Config config);
int* getFitness(int* fitness, int* population, Config config, int (*calc_ptr)());
int* reproduction(int* population, int* primePopulation, Config config);
int* geneticAlgorithm(Config config, int (*calc_ptr)());
int getMaxFitness(Config config);

//prints invidual at specified index
void printIndividual(char* pre, int* population, Config config, int i, int (*clac_ptr)())
{
    if (config.verbosity > 0){
        printf("%s",pre);
        for (int j = 0; j < config.size; j++)
        {
            printf("%d", *(population+i*config.size+j));
        }
        printf(" fitness: %d                                                       ",clac_ptr(population, config.size, i));
    }
}
//print each individual in the population
void printPopulation(int* population, Config config, int* fitness){
    if(config.verbosity > 0){
        for(int i = 0; i < config.pop ; i++){
            printf("%d/%d: ",i+1,config.pop);
            //printIndividual("|",population,GENE_SIZE,i); 
            printf("|>>%d",fitness[i]);
            printf("\n");
        }
        printf("_____________________________________________________________________\n");
    }
}
//create  population of genes that are 0 or 1
int* initialisePopulation(int* population, Config config){
    int i;
    for (i = 0; i < config.pop*config.size; i++)
    {
        *(population+i) = (rand() % (config.maxGeneValue - config.minGeneValue + 1)) + config.minGeneValue;
        if(*(population+i) < config.minGeneValue || *(population+i) > config.maxGeneValue){
                        printf("%d<\n",*(population+i));
                        printf("error, gene value out of range");
                        exit(1);
                    }
    }
    return population;
}
//returns an array of fitness values for each individual in the population
int* naturalSelection(int* primePopulation, int* population, int* fitness, Config config){
    int h = 0;
    for (int i = 0; i < config.pop && h < config.numParents; i++)
    {
        int success = 1;
        for (int j = 0; j < config.pop; j++)
        {
            if (fitness[i] < fitness[j])
            {
                success = 0;
                break;
            }
        }
        if (success)
        {
            for (int k = 0; k < config.size; k++)
            {
                *(primePopulation+h*config.size+k) = *(population+i*config.size+k);
            }
            h++;
        }
    }
    for(int i = h; i < config.numParents; i++){
        for(int k = 0; k < config.size; k++){
            *(primePopulation+i*config.size+k) = *(primePopulation+k);
        }
    }
    return primePopulation;
}
//returns the fitness of the population
int* getFitness(int* fitness, int* population, Config config, int (*calc_ptr)()){
    int i;
    for (i = 0; i < config.pop; i++)
    {
        fitness[i] = calc_ptr(population,config.size,i);
    }
    return fitness;
}
//creates a new population by randomly selecting individuals from the prime population with a chang of mutation
int* reproduction(int* population, int* primePopulation, Config config){
    for(int j = 0; j < config.numParents; j++){
        for(int i = 0; i < config.size; i++){
            *(population+j*config.size+i) = *(primePopulation+j*config.size+i);
        }
    }
    int i, j;
    for (i = config.numParents; i < config.pop - config.pop/10; i++)
    {
        for (j = 0; j < config.size; j++)
        {
            if(rand() % (config.mutationRate * config.numParents) >= config.numParents){
                *(population+i*config.size+j) = *(primePopulation+(rand() % config.numParents)*config.size+j);
            }
            else{
                *(population+i*config.size+j) = (rand() % (config.maxGeneValue - config.minGeneValue + 1)) + config.minGeneValue;
            }
        }
    }
    for (i = config.pop - config.pop / 10; i < config.pop; i++)
    {
        for (j = 0; j < config.size; j++)
        {
            *(population + i * config.size + j) = (rand() % (config.maxGeneValue - config.minGeneValue + 1)) + config.minGeneValue;
        }
    }
    return population;
}
//runs the genetic algorithm
int* geneticAlgorithm(Config config, int (*calc_ptr)()){
    int* population = (int*)malloc(config.pop * config.size * sizeof(int));
    int* fitness = (int*)malloc(config.pop * sizeof(int));
    int* primePopulation = (int*)malloc(config.numParents * config.size * sizeof(int));
    int* output = (int*)malloc(config.size * sizeof(int));

    fitness = getFitness(fitness,initialisePopulation(population,config),config,calc_ptr);
    int maxFitness = getMaxFitness(config);
    int count = 1;
    int maxFit = fitness[0];
    for(int i = 1; i < config.pop; i++){
        if(fitness[i] > maxFit) maxFit = fitness[i];
    }
    while(maxFit < maxFitness && count <= config.maxGens){
        fitness = getFitness(fitness,reproduction(population,naturalSelection(primePopulation,population,fitness,config),config),config,calc_ptr);

        if(config.verbosity == 1 || count % 1000 == 0){
            printf("Gen %d",count++);
            printIndividual("|Genes|",population,config,0,calc_ptr);
            printf("\r");
        } else {
            count++;
        }
        maxFit = fitness[0];
        for(int i = 1; i < config.pop; i++){
            if(fitness[i] > maxFit) maxFit = fitness[i];
        }
    }
    int bestIdx = 0;
    for(int i = 1; i < config.pop; i++){
        if(fitness[i] > fitness[bestIdx]) bestIdx = i;
    }
    printf("\rResult (Gen %d):", count);
    for(int i = 0; i < config.size; i++){
        printf("%d", *(population+bestIdx*config.size+i));
    }
    printf(" fitness: %d                                \n", fitness[bestIdx]);
    for(int i = 0; i < config.size; i++){
        *(output+i) = *(population+bestIdx*config.size+i);
    }
    free(population);
    free(fitness);
    free(primePopulation);
    return(output);
}

//__________Example Fitness Functions__________
//Custom fitness function designed by user, the population, the size of the genes and the index as an input
//this can be used to test the genes of an individual as shown below
//genes of an individual are in the range (population+index*size) to (population+index*size+size)
int fitnessCalculator(int* population, int size, int index){
    int fitness = 0;
    for (int i = 0; i < size; i++)
    {
        if(*(population+index*size+i) == 1){
            fitness++;
        }
    }
    return fitness;   
}
//this is another fitness function that can be used to test the genes of an individual
// in this the goal is to have a fitness that is lower, so we return the negative of the fitness
//a lower fitness value makes the number more "prime"
//but less than 2 factors is not prime so we return a very low value to filter out those results
int primeCalculator(int* population, int size, int index){
    int fitness = 0;
    int num = 0;

    for (int i = 0; i < size; i++)
    {
        num += *(population+index*size+i) * pow(10,size-i-1);
    }

    int cnt = 0;

    for (int i = 1; i <= num; i++) {
        if (num % i == 0) {
            cnt++;
        }
    }
    if (cnt < 2) {
        return -1000000000;
    }
    return cnt*-1;
}

//rewards genes that form a palindrome (e.g. 1,2,3,2,1)
//+1 for each pair that mirrors, max fitness = size/2
int palindromeCalculator(int* population, int size, int index){
    int fitness = 0;
    for(int i = 0; i < size/2; i++){
        if(*(population+index*size+i) == *(population+index*size+size-1-i)){
            fitness++;
        }
    }
    return fitness;
}

//rewards genes that are in ascending order
//+1 for each gene that is >= the previous gene, max fitness = size-1
int ascendingCalculator(int* population, int size, int index){
    int fitness = 0;
    for(int i = 1; i < size; i++){
        if(*(population+index*size+i) >= *(population+index*size+i-1)){
            fitness++;
        }
    }
    return fitness;
}

//rewards genes that alternate between min and max values (e.g. 1,3,1,3,1,3)
//+1 for each gene that follows the alternating pattern, max fitness = size
int alternatingCalculator(int* population, int size, int index){
    int fitness = 0;
    int min = *(population+index*size);
    int max = *(population+index*size);
    for(int i = 1; i < size; i++){
        if(*(population+index*size+i) < min) min = *(population+index*size+i);
        if(*(population+index*size+i) > max) max = *(population+index*size+i);
    }
    for(int i = 0; i < size; i++){
        if(i % 2 == 0 && *(population+index*size+i) == min) fitness++;
        else if(i % 2 == 1 && *(population+index*size+i) == max) fitness++;
    }
    return fitness;
}

//rewards genes where no two adjacent genes are the same value
//+1 for each adjacent pair that differs, max fitness = size-1
int noRepeatCalculator(int* population, int size, int index){
    int fitness = 0;
    for(int i = 1; i < size; i++){
        if(*(population+index*size+i) != *(population+index*size+i-1)){
            fitness++;
        }
    }
    return fitness;
}

//treats genes as digits and rewards closeness to a target sum
//max fitness = targetSum (when sum == target), decreases as sum diverges
int sumTargetCalculator(int* population, int size, int index){
    int target = size * 2;
    int sum = 0;
    for(int i = 0; i < size; i++){
        sum += *(population+index*size+i);
    }
    int diff = abs(sum - target);
    return target - diff;
}

int getMaxFitness(Config config){
    if(strcmp(config.fitnessFunc, "fitnessCalculator") == 0) return config.size;
    else if(strcmp(config.fitnessFunc, "primeCalculator") == 0) return -2;
    else if(strcmp(config.fitnessFunc, "palindromeCalculator") == 0) return config.size/2;
    else if(strcmp(config.fitnessFunc, "ascendingCalculator") == 0) return config.size-1;
    else if(strcmp(config.fitnessFunc, "alternatingCalculator") == 0) return config.size;
    else if(strcmp(config.fitnessFunc, "noRepeatCalculator") == 0) return config.size-1;
    else if(strcmp(config.fitnessFunc, "sumTargetCalculator") == 0) return config.size*2;
    return 0;
}

void readConfig(Config* config){
    FILE* file = fopen("config.txt", "r");
    if(file == NULL){
        printf("error: could not open config.txt\n");
        exit(1);
    }
    char key[50];
    char value[50];
    while(fscanf(file, "%[^=]=%s\n", key, value) == 2){
        if(strcmp(key, "pop") == 0) config->pop = atoi(value);
        else if(strcmp(key, "minGeneValue") == 0) config->minGeneValue = atoi(value);
        else if(strcmp(key, "maxGeneValue") == 0) config->maxGeneValue = atoi(value);
        else if(strcmp(key, "size") == 0) config->size = atoi(value);
        else if(strcmp(key, "numParents") == 0) config->numParents = atoi(value);
        else if(strcmp(key, "mutationRate") == 0) config->mutationRate = atoi(value);
        else if(strcmp(key, "maxGens") == 0) config->maxGens = atoi(value);
        else if(strcmp(key, "verbosity") == 0) config->verbosity = atoi(value);
        else if(strcmp(key, "fitnessFunc") == 0) strcpy(config->fitnessFunc, value);
    }
    fclose(file);
}
// gcc GeneticAlgorithm.c -o genetic_algorithm -lm ./genetic_algorithm
int main(){
    srand(time(NULL));
    Config config;
    readConfig(&config); 
    int (*calc_ptr)(int*population,int size, int index);
    if(strcmp(config.fitnessFunc, "fitnessCalculator") == 0) calc_ptr = &fitnessCalculator;
    else if(strcmp(config.fitnessFunc, "primeCalculator") == 0) calc_ptr = &primeCalculator;
    else if(strcmp(config.fitnessFunc, "palindromeCalculator") == 0) calc_ptr = &palindromeCalculator;
    else if(strcmp(config.fitnessFunc, "ascendingCalculator") == 0) calc_ptr = &ascendingCalculator;
    else if(strcmp(config.fitnessFunc, "alternatingCalculator") == 0) calc_ptr = &alternatingCalculator;
    else if(strcmp(config.fitnessFunc, "noRepeatCalculator") == 0) calc_ptr = &noRepeatCalculator;
    else if(strcmp(config.fitnessFunc, "sumTargetCalculator") == 0) calc_ptr = &sumTargetCalculator;
    else{
        printf("error: unknown fitness function '%s'\n", config.fitnessFunc);
        return 1;
    }
    int * result = geneticAlgorithm(config, calc_ptr);
    free(result);
    return 0;
}