gistfile1.h

/*
 * Practicing genetic algoritms
 * Daniel Mateos
 * Problem: find an equation out of 0-9 *+/- that comes up with 42
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define GENES 10
#define CHROMOSOMES 16
#define TARGETVAL 10 //42

struct chromosome {
    char *gene[GENES];
    float fitness;
};

static int binstr2dec(char *binstr);
static void init_chromosomes(struct chromosome c[], int count);
static void kill_chromosomes(struct chromosome c[], int count);
static void print_chromosomes(struct chromosome c[], int count);
static int parse_chromosome(struct chromosome *c, int *resbuff, int bsize);
static float set_fitness(struct chromosome *c);
int main(int argc, char *argv[]);

/* Convert a string of chars representing binary into a decimal value. */
static int binstr2dec(char *binstr) {
    int i, val, valadd;
    val = 0;
    valadd = 1;
    for(i = strlen(binstr); i > 0; i--) {
        if(binstr[i-1] == '1')
            val += valadd;        
        valadd *= 2;
    }
    return val;
}

/* Init an array of chromosome structures with random values. */
static void init_chromosomes(struct chromosome c[], int count) {
    int i, y, z;
    srand(time(NULL));
    /* For each chromosone. */
    for(i = 0; i < count; i++) {
        c[i].fitness = 0;
        /* For each gene. */
        for(y = 0; y < GENES; y++) {
            c[i].gene[y] = malloc(5); /* Each gene stores 4 bins + a null. */
            /* Each gene char. */
            for(z = 0; z < 5; z++) {
                c[i].gene[y][z] = (rand() % 2) ? '1' : '0';
            }
            c[i].gene[y][4] = '\0';
        }
    }
}

/* Free up memory allocation of chromosomes, hi valgrind!. */
static void kill_chromosomes(struct chromosome c[], int count) {
    int i, y;
    for(i = 0; i < count; i++)
        for(y = 0; y < GENES; y++)
            free(c[i].gene[y]);
}

/* Crudely print the chromosome structure and a basic translation of
 * its insides. */
static void print_chromosomes(struct chromosome c[], int count) {
    int i, y, parsebuff[1024], pcnt;

    for(i = 0; i < count; i++) {
        printf("CHROMOSOME %d/%d fitness: %f\n", i+1, count, c[i].fitness);
        pcnt = parse_chromosome(&c[i], parsebuff, sizeof(int) * 1024); 

        for(y = 0; y < GENES; y++) {
            printf("%s(%d) ", c[i].gene[y], binstr2dec(c[i].gene[y]));
        }
        printf("\n");
        for(y = 0; y < pcnt; y++)
            switch(parsebuff[y]) {
                case 10:
                    printf("+ ");
                    break;
                case 11:
                    printf("- ");
                    break;
                case 12:
                    printf("* ");
                    break;
                case 13:
                    printf("/ ");
                    break;
                default:
                    printf("%d ", parsebuff[y]);
                    break;
            }
        printf("\n");
    }
}

/* Parse a chromosomes gene buffer into number -> operator pairs,
 * note that we disgard anything between that doesnt make sense. */
static int parse_chromosome(struct chromosome *c, int *resbuff, int bsize) {
    int operator, count;
    int i, genedec, *origb;

    count = operator = 0;
    origb = resbuff;
    operator = 1;
    memset(resbuff, '\0', bsize);

    for(i = 0; i < GENES; i++) {
        genedec = binstr2dec(c->gene[i]);

        /* Looking for an operator? */
        if(operator) {
            /* Is operator. */
            if(genedec > 9 && genedec < 14) {
                *resbuff = genedec;
                resbuff++;
                count++;
                operator = 0;
            }
        }
        else {
            /* Number. */
            if(genedec < 9) {
                *resbuff = genedec;
                resbuff++;
                count++;
                operator = 1;
            }
        }
    }

    /* Fix floaitng points. */
    for(i = 0; i < count; i++) {
        if(origb[i] == 13 && origb[i+1] == 0)
            origb[i] = 10;
    }
    return count;
}

/* Sets a fitness level based on how close the chromosomes
 * genes are to matching the number wanted. */
static float set_fitness(struct chromosome *c) {
    int i, sum, resbuff[1024], rcount;
    float fitness;
    rcount = parse_chromosome(c, resbuff, sizeof(int) * 1024);
    sum = 0;
    fitness = 0.0;

    /* Catch +*-/ and operate the next value upon them. */
    for(i = 0; i < rcount; i+=2) {
        switch(resbuff[i]) {
            case 10:
                sum += resbuff[i+1];
                break;
            case 11:
                sum -= resbuff[i+1];
                break;
            case 12:
                sum *= resbuff[i+1];
                break;
            case 13:
                sum /= resbuff[i+1];
                break;
        }
    }

    /* Fuck yeah target value. */
    if(sum == TARGETVAL)
        fitness = 999.0;
    else
        fitness = 1/fabs((TARGETVAL - sum));

    c->fitness = fitness;
    return fitness;
}

int main(int argc, char *argv[]) {
    int i, resbuff[1024];
    struct chromosome chromes[CHROMOSOMES];
    memset(chromes, '\0', sizeof(chromes));   
 
    init_chromosomes(chromes, CHROMOSOMES);
    
    for(i = 0; i < CHROMOSOMES; i++)
        set_fitness(&chromes[i]);
    print_chromosomes(chromes, CHROMOSOMES);
    
    kill_chromosomes(chromes, CHROMOSOMES);
    return 0;
}