path: root/src/main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <SDL.h>
#include <SDL_ttf.h>
#include <gtk/gtk.h>
#include <pthread.h>

#include "sdlutils.h"
#include "random.h"

#define CHARS_X 180
#define CHARS_Y 50

#define WIDTH CHARS_X * CHAR_WIDTH
#define HEIGHT CHARS_Y * CHAR_HEIGHT

#define NEW_SIMULATION 1
#define QUIT 2
#define IMPORT_SAVE 3

#define ASK_RUN_METHOD_MESSAGE "Please enter run method, substituting %s for where the genes should be inserted: "

typedef enum
{
    STATE_MENU,
    STATE_IMPORTING_SAVE,
    STATE_CREATE_SIMULATION,
    STATE_SIMULATION_OPTIONS,
    STATE_SIMULATING
} state_t;

typedef struct
{
    double* genes;
    double fitness;
} genes_t;

state_t state;
char* run_method;
pthread_t run_thread;
double** gene_lists;
genes_t* genes_ts;
int population = 100;
int num_genes = 100; // Number of genes or product of generation #
int are_genes_constant = 1; // Is the number of genes constant?
int population_change = 100;
int num_genes_change = 100;
int generation_survivors = 10; // Top n survivors breed
int parents_per_child = 2;
int mutation_rate = 70; // 70% of first mutation, after first, 70% of second mutation, etc.
int generation_number;
int was_loaded = 0;
int starting_generation;
int generations_to_run = -1;
int loading = 0; // Is it loading a new generation?
int stop; // Used to communicate with the simulating thread
int batch_genes = 0; // Can the program process multiple gene sets (a whole generation) at once?



void draw_simulation_options()
{
    char* popbuffer = malloc(12);
    char* popchangebuffer = malloc(12);
    char* ppcbuffer = malloc(12);
    char* topnbuffer = malloc(12);
    char* mutratebuffer = malloc(12);
    char* genesbuffer = malloc(12);

    write_str("Number of genes is ", 1, 3, WHITE, BLACK);
    write_str("Linear to the generation number (n)", 20, 3, !are_genes_constant ? LIGHTBLUE : WHITE, BLACK);
    write_str("/", 55, 3, WHITE, BLACK);
    write_str("Constant (c)", 56, 3, are_genes_constant ? LIGHTBLUE : WHITE, BLACK);
    char* genes_eq = are_genes_constant ? "Genes = " : "Genes = generation number * ";
    int len = strlen(genes_eq);
    write_str("                                                                      ", 1, 4, BLACK, BLACK);
    write_str(genes_eq, 1, 4, WHITE, BLACK);
    sprintf(genesbuffer, "%12d", num_genes);
    write_str(genesbuffer, 1+len, 4, WHITE, BLACK);
    write_str("-1 (1)", 14+len, 4, LIGHTRED, DARKRED);
    write_str("+1 (2)", 20+len, 4, LIGHTGREEN, DARKGREEN);
    write_str("/2 (3)", 26+len, 4, LIGHTRED, DARKRED);
    write_str("*2 (4)", 32+len, 4, LIGHTGREEN, DARKGREEN);

    write_str("Population: ", 1, 5, WHITE, BLACK);
    sprintf(popbuffer, "%12d", population);
    write_str(popbuffer, 13, 5, WHITE, BLACK);
    write_str("- (l)", 26, 5, LIGHTRED, DARKRED);
    write_str("+ (p)", 32, 5, LIGHTGREEN, DARKGREEN);
    write_str("(Increase by)", 37, 5, WHITE, BLACK);
    sprintf(popchangebuffer, "%12d", population_change);
    write_str(popchangebuffer, 50, 5, WHITE, BLACK);
    write_str("- (k)", 62, 5, LIGHTRED, DARKRED);
    write_str("+ (o)", 68, 5, LIGHTGREEN, DARKGREEN);

    write_str("Parents per child: ", 1, 6, WHITE, BLACK);
    sprintf(ppcbuffer, "%3d", parents_per_child);
    write_str(ppcbuffer, 20, 6, WHITE, BLACK);
    write_str("- (f)", 24, 6, LIGHTRED, DARKRED);
    write_str("+ (r)", 30, 6, LIGHTGREEN, DARKGREEN);

    write_str("Top n algorithms survive: ", 1, 7, WHITE, BLACK);
    sprintf(topnbuffer, "%12d", generation_survivors);
    write_str(topnbuffer, 27, 7, WHITE, BLACK);
    write_str("- (g)", 39, 7, LIGHTRED, DARKRED);
    write_str("+ (t)", 45, 7, LIGHTGREEN, DARKGREEN);
    write_str("/2 (v)", 51, 7, RED, DARKRED);
    write_str("*2 (b)", 57, 7, GREEN, DARKGREEN);

    write_str("Mutation rate: ", 1, 8, WHITE, BLACK);
    sprintf(mutratebuffer, "%3d", mutation_rate);
    write_str(mutratebuffer, 16, 8, WHITE, BLACK);
    write_str("- (h)", 20, 8, LIGHTRED, DARKRED);
    write_str("+ (y)", 26, 8, LIGHTGREEN, DARKGREEN);

    write_str("Batch genes? ", 1, 9, WHITE, BLACK);
    write_str("ON (z)", 14, 9, batch_genes ? LIGHTBLUE : WHITE, BLACK);
    write_str("OFF (x)", 21, 9, !batch_genes ? LIGHTBLUE : WHITE, BLACK);
    write_str("If you enable batch genes, the input will be provided as semicolon-separated comma-separated lists of genes. This will improve run time.",
                1, 10, WHITE, BLACK);
    write_str("Begin (Return)", 1, 12, LIGHTGREEN, DARKGREEN);
}

int get_num_genes()
{
    return are_genes_constant ? num_genes : (num_genes * generation_number);
}

void allocate_genes()
{
    int i;
    int num_genes = get_num_genes(generation_number);
    for (i = 0; i < population; i++)
        gene_lists[i] = malloc(num_genes * sizeof(double));
}

double get_fitness(double* genes)
{
    int ngenes = get_num_genes();
    char* csgenes = malloc(ngenes * 16); // Comma-separated genes
    csgenes[0] = 0;
    strcat(csgenes, double_to_str(genes[0]));
    int i;
    for (i = 1; i < ngenes; i++)
    {
        strcat(csgenes, ",");
        strcat(csgenes, double_to_str(genes[i]));
    }
    char* command = malloc(ngenes * 16 + 64);
    sprintf(command, run_method, csgenes);
    FILE* fp = popen(command, "r");
    float fitness;
    fscanf(fp, "%f", &fitness);
    pclose(fp);
    return (double) fitness;
}

double* get_fitnesses(double** genes)
{
    int i, j, ngenes = get_num_genes();
    char* buffer = malloc(ngenes * population * 12);
    strcat(buffer, double_to_str(genes[0][0]));
    for (i = 1; i < ngenes; i++)
    {
        strcat(buffer, ",");
        strcat(buffer, double_to_str(genes[0][i]));
    }
    for (j = 1; j < population; j++)
    {
        strcat(buffer, ";");
        strcat(buffer, double_to_str(genes[j][0]));
        for (i = 1; i < ngenes; i++)
        {
            strcat(buffer, ",");
            strcat(buffer, double_to_str(genes[j][i]));
        }
    }
    char* command = malloc(strlen(buffer) + strlen(run_method) + 50);
    sprintf(command, run_method, buffer);
    FILE* fp = popen(command, "r");
    double* fitnesses;
    float f;
    fitnesses = malloc(population * sizeof(double));
    fscanf(fp, "%f", &f);
    fitnesses[0] = (double) f;
    for (i = 1; i < population; i++)
    {
        fscanf(fp, ",%f", &f);
        fitnesses[i] = (double) f;
    }
    fclose(fp);
    return fitnesses;
}

void mutate(double* genes)
{
    int ngenes = get_num_genes();
    int selected_gene;
    while (rand01() < ((double) mutation_rate / 100))
    {
        selected_gene = randrange_int(0, ngenes);
        genes[selected_gene] = rand01();
    }
}

double* breed(double** genes)
{
    int i, newngenes, ngenes = get_num_genes();

    generation_number++;
    newngenes = get_num_genes();
    generation_number--;

    double* newgenes = malloc(newngenes*sizeof(double));

    for (i = 0; i < ngenes; i++)
    {
        newgenes[i] = genes[randrange_int(0, parents_per_child)][i];
    }
    for (; i < newngenes; i++)
    {
        newgenes[i] = rand01();
    }
    mutate(newgenes);
    return newgenes;
}

double** select_parents(genes_t* sorted_genes)
{
    int* selected = malloc(parents_per_child*sizeof(int));
    int i, j, hasBeenSelected, sel;
    for (i = 0; i < parents_per_child; i++)
    {
        do
        {
            sel = randrange_int(0, generation_survivors);
            hasBeenSelected = 0;
            for (j = 0; j < i; j++)
            {
                if (sel == selected[j])
                    hasBeenSelected = 1;
            }
        }
        while (hasBeenSelected);
        selected[i] = sel;
    }
    double** parents = malloc(parents_per_child*sizeof(double*));
    for (i = 0; i < parents_per_child; i++)
    {
        parents[i] = sorted_genes[selected[i]].genes;
    }
    return parents;
}

int compare_genes(const void* a, const void* b)
{
    genes_t genes_a = *(genes_t*) a;
    genes_t genes_b = *(genes_t*) b;
    double diff = genes_b.fitness - genes_a.fitness;
    return diff > 0 ? 1 : (diff == 0 ? 0 : -1);
}



void* run_generations(void* data)
{
    // Runs generations_to_run generations
    if (loading) return NULL;
    loading = 1;
    stop = 0;
    int i, gn; // Number of local generations (out of n)
    starting_generation = generation_number;
    double* fitnesses;
    for (gn = 0; generations_to_run == -1 ? 1 : (gn < generations_to_run); gn++)
    {
        if (batch_genes)
        {
            fitnesses = get_fitnesses(gene_lists);
            for (i = 0; i < population; i++)
            {
                genes_ts[i].genes = gene_lists[i];
                genes_ts[i].fitness = fitnesses[i];
            }
        }
        else
        {
            for (i = 0; i < population; i++)
            {
                genes_ts[i].genes = gene_lists[i];
                genes_ts[i].fitness = get_fitness(genes_ts[i].genes);
            }
        }
        qsort(genes_ts, population, sizeof(genes_t), compare_genes);
        if (stop)
        {
            loading = -1;
            return NULL;
        }
        for (i = 0; i < population; i++)
        {
            gene_lists[i] = breed(select_parents(genes_ts));
        }
        printf("Generation %d; Best fitness: %f\n", generation_number, genes_ts[0].fitness);
        generation_number++;
        if (stop)
        {
            loading = -1;
            return NULL;
        }
    }

    loading = -1;
    generations_to_run = -1;
    return NULL;
}

void simulate()
{
    int i, j, num_genes;
    if (!was_loaded)
    {
        generation_number = 1;
        gene_lists = malloc(population * sizeof(double*));
        num_genes = get_num_genes();
        allocate_genes();
        for (i = 0; i < population; i++)
            for (j = 0; j < num_genes; j++)
                gene_lists[i][j] = rand01();
    }

    write_str("Run 1 generation (1)", 1, 1, WHITE, DARKBLUE);
    write_str("Run 10 generations (2)", 23, 1, WHITE, DARKBLUE);
    write_str("Run 100 generations (3)", 47, 1, WHITE, DARKBLUE);
    write_str("Run 1000 generations (4)", 72, 1, WHITE, DARKBLUE);
    write_str("Run 10000 generations (5)", 98, 1, WHITE, DARKBLUE);
    write_str("Keep running generations (6)", 125, 1, WHITE, DARKBLUE);
    write_str("Stop (7)", 155, 1, WHITE, DARKBLUE);
}

void change_state(state_t to)
{
    state = to;
    clear_options();
    SDL_SetRenderDrawColor(renderer, 0, 0, 0, 255);
    SDL_RenderClear(renderer);
    switch (to)
    {
    case STATE_IMPORTING_SAVE:
        write_str("Please enter the path to the save file: ", 1, 1, WHITE, BLACK);
        setup_entry("", 41, 1);
        break;
    case STATE_CREATE_SIMULATION:
        setup_entry("", strlen(ASK_RUN_METHOD_MESSAGE)+1, 1);
        write_str(ASK_RUN_METHOD_MESSAGE, 1, 1, WHITE, BLACK);
        write_str("When this command is run, %s will be replaced with a comma-separated list of genes.", 1, 2, WHITE, BLACK);
        break;
    case STATE_SIMULATION_OPTIONS:
        hcenter_str("Simulation Options", CHARS_X, 1, WHITE, BLACK);
        draw_simulation_options();
        break;
    case STATE_SIMULATING:
        simulate();
        break;
    }
}

void save(char* filename)
{
    int i, j;
    FILE* fp = fopen(filename, "w");
    fprintf(fp, "%d\n", generation_number);
    fprintf(fp, "%s\n", run_method);
    fprintf(fp, "%d\n", population);
    fprintf(fp, "%d\n", num_genes);
    fprintf(fp, "%d\n", are_genes_constant);
    fprintf(fp, "%d\n", parents_per_child);
    fprintf(fp, "%d\n", generation_survivors);
    fprintf(fp, "%d\n", mutation_rate);
    fprintf(fp, "%d\n", batch_genes);
    for (i = 0; i < population; i++)
    {
        for (j = 0; j < get_num_genes(); j++)
            fprintf(fp, "%f ", genes_ts[i].genes[j]);
        fprintf(fp, "\n");
    }
    fclose(fp);
}

void load(char* filename)
{
    int i, j;
    FILE* fp = fopen(filename, "r");
    run_method = malloc(512);
    fscanf(fp, "%d\n", &generation_number);
    fscanf(fp, "%[^\n]s\n", run_method);
    fscanf(fp, "%d\n", &population);
    fscanf(fp, "%d\n", &num_genes);
    fscanf(fp, "%d\n", &are_genes_constant);
    fscanf(fp, "%d\n", &parents_per_child);
    fscanf(fp, "%d\n", &generation_survivors);
    fscanf(fp, "%d\n", &mutation_rate);
    fscanf(fp, "%d\n", &batch_genes);
    float f;
    gene_lists = malloc(population * sizeof(double*));
    allocate_genes();
    for (i = 0; i < population; i++)
    {
        for (j = 0; j < get_num_genes(); j++)
        {
            fscanf(fp, "%f ", &f);
            gene_lists[i][j] = f;
        }
        fscanf(fp, "\n");
    }
    fclose(fp);
    was_loaded = 1;
    change_state(STATE_SIMULATING);
}

int main()
{
    srand(time(NULL));
    int end = 0;
    SDL_Event event;

    sdlutils_init(WIDTH, HEIGHT);
    sdlutils_set_capacity(256);

    // Title
    write_str("Genetic Algorithm Framework", 1, 1, WHITE, BLACK);
    create_option("New simulation", NEW_SIMULATION, 1, 2, LIGHTGREEN, DARKGREEN, rgba(100, 200, 100, 255));
    create_option("Import from save file", IMPORT_SAVE, 1, 3, LIGHTBLUE, DARKBLUE, rgba(100, 100, 200, 255));
    create_option("Quit", QUIT, 1, 4, LIGHTRED, DARKRED, rgba(200, 100, 100, 255));
    draw_options();
    write_str("See github.com/pommicket/genetic for more information.", 1, 5, WHITE, BLACK);

    int action;


    genes_ts = malloc(population * sizeof(genes_t));

    char* filename;
    int i, j, r1, r2;
    FILE* fp;
    char* buffer;
    char* gen = malloc(256);
    int lgnum = -1;
    int lgtrun = -1;
    while (!end)
    {
        if (state == STATE_SIMULATING && (lgnum != generation_number || lgtrun != generations_to_run))
        {
            if (generations_to_run > 0)
                sprintf(gen, "      Generation %12d of %12d      ", generation_number, starting_generation + generations_to_run);
            else
                sprintf(gen, "            Generation %12d             ", generation_number);
            lgnum = generation_number;
            lgtrun = generations_to_run;
            hcenter_str(gen, CHARS_X, 4, WHITE, BLACK);
        }
        if (loading == -1)
        {
            // When done loading
            write_str("          ", 1, 2, BLACK, BLACK);
            write_str("Export best set of genes (b)", 1, 3, WHITE, DARKGREEN);
            write_str("Export generation (g)", 31, 3, WHITE, DARKGREEN);
            write_str("Save progress (s)", 54, 3, WHITE, DARKGREEN);
            buffer = malloc(32);
            write_str("Best fitness: ", 1, 4, WHITE, BLACK);
            sprintf(buffer, "%f", genes_ts[0].fitness);
            write_str(buffer, 15, 4, WHITE, BLACK);
            write_str("Genes:", 1, 5, WHITE, BLACK);
            for (i = 0; i < get_num_genes() && i < CHARS_Y; i++)
            {
                sprintf(buffer, "%f", genes_ts[0].genes[i]);
                write_str(buffer, 1, i + 6, WHITE, BLACK);
            }
            loading = 0;

        }
        SDL_RenderPresent(renderer);
        while (SDL_PollEvent(&event))
        {

            switch (event.type)
            {
            case SDL_QUIT:
                end = 1;
                break;
            case SDL_KEYDOWN:
                switch (state)
                {
                case STATE_SIMULATION_OPTIONS:
                    switch (event.key.keysym.sym)
                    {
                    case SDLK_p:
                        if (population + population_change > 0) population += population_change;
                        break;
                    case SDLK_l:
                        if (population - population_change > 0) population -= population_change;
                        break;
                    case SDLK_o:
                        if (population_change * 2 > 0) population_change *= 2;
                        break;
                    case SDLK_k:
                        if (population_change / 2 > 0) population_change /= 2;
                        break;
                    case SDLK_n:
                        are_genes_constant = 0;
                        break;
                    case SDLK_c:
                        are_genes_constant = 1;
                        break;
                    case SDLK_f:
                        if (parents_per_child > 1) parents_per_child--;
                        break;
                    case SDLK_r:
                        if (parents_per_child < generation_survivors) parents_per_child++;
                        break;
                    case SDLK_g:
                        if (generation_survivors > 1) generation_survivors--;
                        break;
                    case SDLK_t:
                        if (generation_survivors < population) generation_survivors++;
                        break;
                    case SDLK_v:
                        if (generation_survivors / 2 >= 1) generation_survivors /= 2;
                        break;
                    case SDLK_b:
                        if (generation_survivors * 2 <= population) generation_survivors *= 2;
                        break;
                    case SDLK_h:
                        if (mutation_rate) mutation_rate--;
                        break;
                    case SDLK_y:
                        if (mutation_rate < 100) mutation_rate++;
                        break;
                    case SDLK_z:
                        batch_genes = 1;
                        break;
                    case SDLK_x:
                        batch_genes = 0;
                        break;
                    case SDLK_1:
                        if (num_genes > 0) num_genes--;
                        break;
                    case SDLK_2:
                        num_genes++;
                        break;
                    case SDLK_3:
                        num_genes /= 2;
                        break;
                    case SDLK_4:
                        num_genes *= 2;
                        break;
                    case SDLK_RETURN:
                        change_state(STATE_SIMULATING);
                        break;
                    }
                    if (state == STATE_SIMULATION_OPTIONS) draw_simulation_options();
                    break;
                case STATE_SIMULATING:
                    generations_to_run = 0;
                    switch (event.key.keysym.sym)
                    {
                    case SDLK_1:
                        generations_to_run = 1;
                        break;
                    case SDLK_2:
                        generations_to_run = 10;
                        break;
                    case SDLK_3:
                        generations_to_run = 100;
                        break;
                    case SDLK_4:
                        generations_to_run = 1000;
                        break;
                    case SDLK_5:
                        generations_to_run = 10000;
                        break;
                    case SDLK_6:
                        generations_to_run = -1;
                        break;
                    case SDLK_7:
                        stop = 1;
                        loading = -1;
                        break;
                    case SDLK_b:
                        if (loading) break;
                        filename = malloc(64);
                        r1 = rand() % 100000;
                        r2 = rand() % 100000;
                        sprintf(filename, "genes%05d%05d.txt", r1, r2);
                        fp = fopen(filename, "w");
                        for (i = 0; i < get_num_genes(); i++)
                            fprintf(fp, "%f\n", genes_ts[0].genes[i]);
                        fclose(fp);
                        write_str("Exported to ", 73, 3, WHITE, BLACK);
                        write_str(filename, 85, 3, WHITE, BLACK);
                        write_str("            ", 104, 3, BLACK, BLACK);
                        break;
                    case SDLK_g:
                        if (loading) break;
                        filename = malloc(64);
                        r1 = rand() % 100000;
                        r2 = rand() % 100000;
                        sprintf(filename, "generation%05d%05d.txt", r1, r2);
                        fp = fopen(filename, "w");
                        for (i = 0; i < population; i++){
                            for (j = 0; j < get_num_genes(); j++)
                                fprintf(fp, "%f ", genes_ts[i].genes[j]);
                            fprintf(fp, "\n");
                        }
                        fclose(fp);
                        write_str("Exported to ", 73, 3, WHITE, BLACK);
                        write_str(filename, 85, 3, WHITE, BLACK);
                        break;
                    case SDLK_s:
                        if (loading) break;
                        filename = malloc(64);
                        r1 = rand() % 10000;
                        r2 = rand() % 10000;
                        sprintf(filename, "save%04d%04d.save", r1, r2);
                        save(filename);
                        write_str("Saved to ", 73, 3, WHITE, BLACK);
                        write_str(filename, 82, 3, WHITE, BLACK);
                        write_str("              ", 99, 3, BLACK, BLACK);
                        break;
                    }
                    if (generations_to_run)
                    {
                        write_str("Loading...", 1, 2, WHITE, BLACK);
                        pthread_create(&run_thread, NULL, run_generations, NULL);
                    }
                    break;
                }
                action = sdlutils_process_key(event.key.keysym.sym);
                if (action)
                {
                    switch (action)
                    {
                    case NEW_SIMULATION:
                        change_state(STATE_CREATE_SIMULATION);
                        break;
                    case ENTRY_SUBMIT:
                        switch (state)
                        {
                        case STATE_CREATE_SIMULATION:
                            run_method = malloc(512);
                            strcpy(run_method, get_entry_contents());
                            change_state(STATE_SIMULATION_OPTIONS);
                            break;
                        case STATE_IMPORTING_SAVE:
                            buffer = malloc(512);
                            strcpy(buffer, get_entry_contents());
                            load(buffer);
                            break;
                        }
                        break;
                    case QUIT:
                        end = 1;
                        break;
                    case IMPORT_SAVE:
                        change_state(STATE_IMPORTING_SAVE);
                        break;
                    }
                }
                break;
            case SDL_TEXTINPUT:
                handle_text(event.text.text);
            }

        }
    }

    quit();
    return 0;
}