Algorithme Colonies de fourmis

import numpy as np
import random

def calculer_heuristique(distances):
    """
    Calcule l'information heuristique (inverse des distances)
    Retourne une matrice n x n où η[i][j] = 1 / distances[i][j]
    """
    n = len(distances)
    heuristique = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            if i != j:
                heuristique[i][j] = 1.0 / distances[i][j]
    return heuristique

def calculer_longueur_tournee(tournee, distances):
    """Calcule la longueur totale d'une tournée"""
    n = len(tournee)
    longueur = 0
    for i in range(n - 1):
        longueur += distances[tournee[i]][tournee[i + 1]]
    longueur += distances[tournee[-1]][tournee[0]]
    return longueur

def choisir_prochaine_ville(ville_courante, visitees, pheromones, heuristique, alpha, beta):
    """
    Sélectionne la prochaine ville selon la règle de transition probabiliste
    Retourne l'indice de la ville choisie
    """
    n = len(pheromones)
    non_visitees = [v for v in range(n) if v not in visitees]
    
    if not non_visitees:
        return None
    
    # Calcul des probabilités
    numerateurs = []
    for j in non_visitees:
        pheromone = pheromones[ville_courante][j] ** alpha
        heur = heuristique[ville_courante][j] ** beta
        numerateurs.append(pheromone * heur)
    
    total = sum(numerateurs)
    probabilites = [num / total for num in numerateurs]
    
    # Choix probabiliste
    return random.choices(non_visitees, weights=probabilites)[0]

def construire_tournee(distances, pheromones, heuristique, alpha, beta):
    """
    Une fourmi construit une tournée complète
    Retourne la tournée et sa longueur
    """
    n = len(distances)
    depart = random.randint(0, n - 1)
    tournee = [depart]
    visitees = set([depart])
    
    while len(tournee) < n:
        courante = tournee[-1]
        prochaine = choisir_prochaine_ville(courante, visitees, pheromones, 
                                            heuristique, alpha, beta)
        tournee.append(prochaine)
        visitees.add(prochaine)
    
    longueur = calculer_longueur_tournee(tournee, distances)
    return tournee, longueur

def deposer_pheromones(pheromones, tournees, longueurs, rho, Q):
    """
    Met à jour les phéromones (évaporation + dépôt par toutes les fourmis)
    """
    n = len(pheromones)
    
    # Évaporation
    pheromones *= (1 - rho)
    
    # Dépôt par chaque fourmi
    for tournee, longueur in zip(tournees, longueurs):
        depot = Q / longueur
        for i in range(n - 1):
            pheromones[tournee[i]][tournee[i + 1]] += depot
            pheromones[tournee[i + 1]][tournee[i]] += depot
        # Retour à la ville de départ
        pheromones[tournee[-1]][tournee[0]] += depot
        pheromones[tournee[0]][tournee[-1]] += depot

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

#define N_VILLES 5
#define N_FOURMIS 10
#define MAX_ITERATIONS 50
#define ALPHA 1.0
#define BETA 2.0
#define RHO 0.5
#define Q 100.0
#define TAU0 0.01

// Matrice des distances
double distances[N_VILLES][N_VILLES] = {
    {0, 10, 15, 20, 25},
    {10, 0, 35, 30, 20},
    {15, 35, 0, 25, 30},
    {20, 30, 25, 0, 15},
    {25, 20, 30, 15, 0}
};

// Phéromones
double pheromones[N_VILLES][N_VILLES];
double heuristique[N_VILLES][N_VILLES];

// Calcul de l'information heuristique
void initialiser_heuristique() {
    for (int i = 0; i < N_VILLES; i++) {
        for (int j = 0; j < N_VILLES; j++) {
            if (i != j) {
                heuristique[i][j] = 1.0 / distances[i][j];
            } else {
                heuristique[i][j] = 0.0;
            }
        }
    }
}

// Initialisation des phéromones
void initialiser_pheromones() {
    for (int i = 0; i < N_VILLES; i++) {
        for (int j = 0; j < N_VILLES; j++) {
            pheromones[i][j] = TAU0;
        }
    }
}

// Calcul de la longueur d'une tournée
double calculer_longueur(int tournee[N_VILLES]) {
    double longueur = 0.0;
    for (int i = 0; i < N_VILLES - 1; i++) {
        longueur += distances[tournee[i]][tournee[i + 1]];
    }
    longueur += distances[tournee[N_VILLES - 1]][tournee[0]];
    return longueur;
}

// Vérifie si une ville a déjà été visitée
int est_visitee(int ville, int visitees[N_VILLES], int nb_visitees) {
    for (int i = 0; i < nb_visitees; i++) {
        if (visitees[i] == ville) return 1;
    }
    return 0;
}

// Sélectionne la prochaine ville selon la règle probabiliste
int choisir_prochaine_ville(int courante, int visitees[N_VILLES], int nb_visitees) {
    double probas[N_VILLES];
    double somme = 0.0;
    
    // Calcul des numérateurs
    for (int j = 0; j < N_VILLES; j++) {
        if (!est_visitee(j, visitees, nb_visitees)) {
            double pheromone = pow(pheromones[courante][j], ALPHA);
            double heur = pow(heuristique[courante][j], BETA);
            probas[j] = pheromone * heur;
            somme += probas[j];
        } else {
            probas[j] = 0.0;
        }
    }
    
    // Normalisation
    if (somme == 0.0) return -1;
    for (int j = 0; j < N_VILLES; j++) {
        probas[j] /= somme;
    }
    
    // Choix probabiliste
    double r = (double)rand() / RAND_MAX;
    double cumul = 0.0;
    for (int j = 0; j < N_VILLES; j++) {
        if (probas[j] > 0) {
            cumul += probas[j];
            if (r <= cumul) return j;
        }
    }
    return -1;
}

// Construction d'une tournée par une fourmi
void construire_tournee(int tournee[N_VILLES], double *longueur) {
    int visitees[N_VILLES];
    int nb_visitees = 0;
    
    // Départ aléatoire
    tournee[0] = rand() % N_VILLES;
    visitees[0] = tournee[0];
    nb_visitees = 1;
    
    // Construction
    for (int i = 1; i < N_VILLES; i++) {
        int courante = tournee[i - 1];
        int prochaine = choisir_prochaine_ville(courante, visitees, nb_visitees);
        tournee[i] = prochaine;
        visitees[nb_visitees] = prochaine;
        nb_visitees++;
    }
    
    *longueur = calculer_longueur(tournee);
}

// Mise à jour des phéromones
void mettre_a_jour_pheromones(int tournees[N_FOURMIS][N_VILLES], 
                               double longueurs[N_FOURMIS]) {
    // Évaporation
    for (int i = 0; i < N_VILLES; i++) {
        for (int j = 0; j < N_VILLES; j++) {
            pheromones[i][j] *= (1 - RHO);
        }
    }
    
    // Dépôt
    for (int k = 0; k < N_FOURMIS; k++) {
        double depot = Q / longueurs[k];
        for (int i = 0; i < N_VILLES - 1; i++) {
            int a = tournees[k][i];
            int b = tournees[k][i + 1];
            pheromones[a][b] += depot;
            pheromones[b][a] += depot;
        }
        int a = tournees[k][N_VILLES - 1];
        int b = tournees[k][0];
        pheromones[a][b] += depot;
        pheromones[b][a] += depot;
    }
}

// Algorithme ACO principal
void ant_colony_optimization(int meilleure_tournee[N_VILLES], double *meilleure_longueur) {
    int tournees[N_FOURMIS][N_VILLES];
    double longueurs[N_FOURMIS];
    
    initialiser_heuristique();
    initialiser_pheromones();
    
    *meilleure_longueur = 1e9;
    
    for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) {
        // Construction des tournées
        for (int k = 0; k < N_FOURMIS; k++) {
            construire_tournee(tournees[k], &longueurs[k]);
            
            if (longueurs[k] < *meilleure_longueur) {
                *meilleure_longueur = longueurs[k];
                for (int i = 0; i < N_VILLES; i++) {
                    meilleure_tournee[i] = tournees[k][i];
                }
            }
        }
        
        // Mise à jour des phéromones
        mettre_a_jour_pheromones(tournees, longueurs);
        
        if (iteration % 10 == 0) {
            printf("Itération %d: meilleure longueur = %.2f\n", iteration, *meilleure_longueur);
        }
    }
}