genetic_algorithm.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "initial_population.h"
#include "genetic_algorithm.h"



/* Update total_time and total_distance
    graph: matrix of times and distances between each node
    nb_nodes: total number of nodes in the graph
    path: path to update
*/
void update_path_metrics(Node** graph, Path* path){
    float total_time = 0.0;
    float total_distance = 0.0;
    int i, from_node, to_node;
    for (i = 0; i < path->path_length - 1; i++) {
        from_node = path->path[i];
        to_node = path->path[i + 1];
        total_time += graph[from_node][to_node].time;
        total_distance += graph[from_node][to_node].distance;
    }
    path->total_time = total_time;
    path->total_distance = total_distance;
}

/* Check if the path doesn't exceed the time limit */
/* Returns 1 if time < 3h */
int check_path(Path* path){
    if (!path) {
        fprintf(stderr, " check_path: invalid parameters\n");
        return 0;
    }
    return path->total_time <= MAX_TIME_PATH - (3*(path->path_length-2));
}

void update_indiv_metrics(Node** graph, Individual* individual) {
    int i;
    individual->total_distance = 0.0;
    individual->total_time = 0.0;
    for (i = 0; i < individual->nb_deliverers; i++) {
        update_path_metrics(graph, &individual->deliverers_paths[i]);
    } 
    for (i = 0; i < individual->nb_deliverers; i++) {
        individual->total_distance += individual->deliverers_paths[i].total_distance;
        individual->total_time += individual->deliverers_paths[i].total_time;
    }
    update_fitness(individual);
}

void update_fitness(Individual* individual) {
    if((individual->nb_deliverers * NB_DELIVERERS_WEIGHT + 
                              individual->total_distance * TOTAL_DISTANCE_WEIGHT + 
                              individual->total_time * TOTAL_TIME_WEIGHT)/100){
        individual->fitness = 1 / ((individual->nb_deliverers * NB_DELIVERERS_WEIGHT + 
                              individual->total_distance * TOTAL_DISTANCE_WEIGHT + 
                              individual->total_time * TOTAL_TIME_WEIGHT)/100);
    }
    else{
        individual->fitness = 0;
    }

}

/* Comparison function for sorting based on fitness
   Ascending order
*/ 
int compare_by_fitness(const void* a, const void* b) {
    const Individual* individualA;
    const Individual* individualB;
    float diff;
    individualA = *(const Individual**)a;
    individualB = *(const Individual**)b;
    if (!individualA && !individualB){
        return 0;
    }
    if (!individualA){
        return -1;  /* Consider null indivA as "less than" indivB*/
    }
    if (!individualB){
        return 1;
    }
    diff = individualB->fitness - individualA->fitness; /* Can be changed */
    return (diff > 0) ? 1 : ((diff < 0) ? -1 : 0);
}

float* evaluate_fitness(Population* population, float* total_fitness) {
    int i;
    float* cumulative_fitness;
    Individual* individual;
    float fitness[POPULATION_SIZE] = {0};
    cumulative_fitness = malloc(POPULATION_SIZE * sizeof(float));
    if (!cumulative_fitness) {
        fprintf(stderr, "malloc of cumulative_fitness failed\n");
        return NULL;
    }
    /* Sort the population array */
    qsort(population->population, POPULATION_SIZE, sizeof(Individual*), compare_by_fitness);
    for (i = 0; i < POPULATION_SIZE; i++) {
        individual = population->population[i];
        if (individual && individual->total_time > 0 && individual->total_distance > 0) {
            update_fitness(individual); 
            fitness[i] = individual->fitness;
            *total_fitness += fitness[i];
        } else {
            if (individual) {
                individual->fitness = 0;  
            }
            fitness[i] = 0;
        }
    }
    if (*total_fitness == 0) {
        fprintf(stderr, "All individuals have zero fitness\n");
        free(cumulative_fitness);
        return NULL;
    }
    cumulative_fitness[0] = fitness[0];
    for (i = 1; i < POPULATION_SIZE; i++) {
        cumulative_fitness[i] = cumulative_fitness[i - 1] + fitness[i];
    }
    return cumulative_fitness;
}

Parents* initialize_parents(){
    Parents* parents = (Parents*)malloc(sizeof(Parents));
    if(!parents){
        return NULL;
    }
    parents->parent1 = NULL;
    parents->parent2 = NULL;
    return parents;
}

void free_parents(Parents* parents){
    if(parents) {
        free(parents);
    }
}

Parents* selection(Population* population, float* cumulative_fitness, float total_fitness){
    Parents* parents;
    float r1, r2;
    int i, index1, index2;
    index1 = -1;
    index2 = -2;
    parents = initialize_parents();
    if(!parents){
        return NULL;
    }
    /* First parent */
    r1 = ((float)rand() + 1) / ((float)RAND_MAX + 1) * total_fitness;
    for (i = 0; i < POPULATION_SIZE; i++) {
        if (cumulative_fitness[i] >= r1) {
            index1 = i;
            break;
        }
    }
    /* Second parent (should be different from parent1) */
    do {
        r2 = ((float)rand() + 1) / ((float)RAND_MAX + 1) * total_fitness;
        for (i = 0; i < POPULATION_SIZE; i++) {
            if (cumulative_fitness[i] >= r2) {
                index2 = i;
                break;
            }
        }
    } while (index2 == index1);
    parents->parent1 = population->population[index1];
    parents->parent2 = population->population[index2];
    return parents;
}

void mutate(Individual* individual, Node** graph) {
    /* Fixed mutation rate of 0.2 */
    int d, pos1, pos2, temp, i;
    Path* path; /* Pointer instead of copy */
    int* backup_path = NULL;
    int backup_length = 0;
    float backup_time = 0.0;
    float backup_distance = 0.0;
    int mutation_applied = 0;

    /*test */
    int mutation_type;
    
    if(!individual){
        fprintf(stderr, "individual is NULL");
        return;
    }
    /* For each deliverer's path */
    for (d = 0; d < individual->nb_deliverers; d++) {
        /* Apply mutation based on probability */
        if ((float)rand() / ((float)RAND_MAX) < MUTATION_RATE) {
            path = &individual->deliverers_paths[d];

            /* Only mutate if path has at least 4 nodes (depot + 2 cities + depot) */
            if (path->path_length >= 4) {
                /* Backup current path state */
                backup_length = path->path_length;
                backup_time = path->total_time;
                backup_distance = path->total_distance;
                backup_path = malloc(path->path_length * sizeof(int));
                if (!backup_path) {
                    fprintf(stderr, " Failed to allocate backup memory in mutate\n");
                    continue;
                }
                for (i = 0; i < path->path_length; i++) {
                    backup_path[i] = path->path[i];
                }
                /* Select two random positions (excluding depot at start/end) */
                pos1 = 1 + rand() % (path->path_length - 2);
                do {
                    pos2 = 1 + rand() % (path->path_length - 2);
                } while (pos2 == pos1);
                /*choix de la mutation 0: swap , 1 inversion, 2 insertion*/
                mutation_type = rand( )%2;
                switch(mutation_type){
                    case 0: /*Swap the positions of two cities in the delivery path */
                        temp = path->path[pos1];
                        path->path[pos1] = path->path[pos2];
                        path->path[pos2] = temp;
                        break;
                    case 1: /*inversion : inverts the city subsequence between two randomly chosen positions*/
                        if(pos1 > pos2)
                        {
                            temp=pos1;
                            pos1=pos2;
                            pos2=temp;
                            while(pos1<pos2){
                                temp=path->path[pos1];
                                path->path[pos1]=path->path[pos2];
                                path->path[pos2]=temp;
                                pos1++;
                                pos2--;
                            }
                        }
                        break;
                }
                /* Recalculate path metrics */
                update_path_metrics(graph, path);
                /* Check if the mutation respects time constraint */
                if (!check_path(path)) {
                    /* Mutation violated time constraint, restore backup */
                    for (i = 0; i < backup_length; i++) {
                        path->path[i] = backup_path[i];
                    }
                    path->path_length = backup_length;
                    path->total_time = backup_time;
                    path->total_distance = backup_distance;
                } else {
                    mutation_applied = 1;
                }
                free(backup_path);
                backup_path = NULL;
            }
        }
    }
    /* Update individual's total metrics */
    update_indiv_metrics(graph, individual);
    /* If mutations were applied and any path violations exist, repair the individual */
    if (mutation_applied) {
        /* Check if any path violates time constraint */
        int needs_repair = 0;
        for (d = 0; d < individual->nb_deliverers; d++) {
            if (!check_path(&individual->deliverers_paths[d])) {
                needs_repair = 1;
                break;
            }
        }
        if (needs_repair) {
            if (!repair_individual(graph, individual)) {
                fprintf(stderr, " Failed to repair individual after mutation\n");
            }
        }
    }
}

void update_population(Population* population, Individual* child) {
    int worst_index=0;
    int i;
    float worst_fitness = population->population[0]->fitness;
    if(!child){
        fprintf(stderr, "child is NULL");
        return;
    }
    for(i=0; i<POPULATION_SIZE;i++){
        if(population->population[i]->fitness < worst_fitness){
            worst_fitness = population->population[i]->fitness;
            worst_index = i;
        }
    }
    if(child->fitness > worst_fitness){
        population->population[worst_index]=child;
    } else {
        free_individual(child);
    }
}


Path copy_path_deep(Path* original) {
    Path copied;
    int i;
    
    copied.path_length = original->path_length;
    copied.total_time = original->total_time;
    copied.total_distance = original->total_distance;
    
    /* Allocate new memory for the path */
    copied.path = malloc(original->path_length * sizeof(int));
    if (!copied.path) {
        fprintf(stderr, "Memory allocation error in copy_path_deep\n");
        copied.path_length = 0;
        return copied;
    }
    
    /* Copy data */
    for (i = 0; i < original->path_length; i++) {
        copied.path[i] = original->path[i];
    }
    
    return copied;
}

Individual* copy_individual(Individual* individual) {
    Individual* copied_individual;
    int i;
    if(!individual){
        fprintf(stderr, "null individual in copy_individual");
        return NULL;
    }
    copied_individual = initialize_individual(individual->nb_nodes);
    if(!copied_individual){
        fprintf(stderr, "null individual in copy_individual");
        return NULL;
    }
    copied_individual->nb_deliverers = individual->nb_deliverers;
    copied_individual->total_time = individual->total_time;
    copied_individual->total_distance = individual->total_distance;
    copied_individual->fitness = individual->fitness;

    /* Copy visited array */
    for(i = 0; i < individual->nb_nodes; i++){
        copied_individual->visited[i] = individual->visited[i];
    }
    /* Copy each path with deep copy */
    for(i = 0; i < individual->nb_deliverers; i++){
        copied_individual->deliverers_paths[i] = copy_path_deep(&individual->deliverers_paths[i]);
    }
    return copied_individual;
}

Individual* crossover(Node** graph, Parents* parents) {
    Individual* parent1;
    Individual* parent2;
    Individual* child;
    int rate, index_section_p1, index_section_p2, i, j;
    if(!parents) {
        fprintf(stderr, "Parents are NULL in crossover\n");
        return NULL;
    }
    if (!parents->parent1 && !parents->parent2) {
        fprintf(stderr, "Both parents are NULL in crossover\n");
        return NULL;
    }
    else if(!parents->parent1) {
        return copy_individual(parents->parent2);
    }
    else if (!parents->parent2) {
        return copy_individual(parents->parent1);
    }
    parent1 = parents->parent1;
    parent2 = parents->parent2;
    rate = rand() % 100;
    if (rate >= CROSSOVER_RATE * 100) {
        int random_parent;
        random_parent = rand() % 2;
        if (random_parent) {
            return copy_individual(parent1);
        } else {
            return copy_individual(parent2);
        }
    }
    /* Create child */
    child = initialize_individual(parent1->nb_nodes);
    if (!child) {
        fprintf(stderr, "Crossover: failed to initialize child\n");
        return NULL;
    }
    /* Select sections to cross */
    index_section_p1 = rand() % parent1->nb_deliverers;
    index_section_p2 = rand() % parent2->nb_deliverers;
    /* Copy part of paths from parent 1 */
    for (i = index_section_p1; i < parent1->nb_deliverers && child->nb_deliverers < child->nb_nodes; i++) {
        child->deliverers_paths[child->nb_deliverers] = copy_path_deep(&parent1->deliverers_paths[i]);
        child->total_distance += parent1->deliverers_paths[i].total_distance;
        child->total_time += parent1->deliverers_paths[i].total_time;
        child->nb_deliverers++;
    }
    /* Copy part of paths from parent 2 */
    for (i = index_section_p2; i < parent2->nb_deliverers && child->nb_deliverers < child->nb_nodes; i++) {
        child->deliverers_paths[child->nb_deliverers] = copy_path_deep(&parent2->deliverers_paths[i]);
        child->total_distance += parent2->deliverers_paths[i].total_distance;
        child->total_time += parent2->deliverers_paths[i].total_time;
        child->nb_deliverers++;
    }
    /* Mark visited cities */
    for (i = 0; i < child->nb_nodes; i++) {
        child->visited[i] = 0;
    }
    for (i = 0; i < child->nb_deliverers; i++) {
        for(j = 0; j < child->deliverers_paths[i].path_length; j++) {
            int node = child->deliverers_paths[i].path[j];
            if (node >= 0 && node < child->nb_nodes) {
                child->visited[node] = 1;
            }
        }
    }
    /* Repair child */
    if(!repair_individual(graph, child)) {
        fprintf(stderr, "Crossover: child could not be repaired\n");
    }
    return child;
}

Individual* best_fitness(Population* population) {
    int i, best_index;
    best_index = 0;
    if (!population) {
        fprintf(stderr, "Population is NULL\n");
        return NULL;
    }
    for (i = 0; i < POPULATION_SIZE; i++) {
        if (population->population[i] && population->population[best_index]) {
            if (population->population[i]->fitness > population->population[best_index]->fitness && 
                all_cities_visited(population->population[i]->visited,population->population[i]->nb_nodes )) {
                best_index = i;
            }
        }
    }
    return population->population[best_index];
}