Skip to content
TheChatArchiveThe Chat Archive
gpt-4-0314· openaiHugging Face Suzhen/CodeChat

Écrire une procédure croisement en C permettant de réaliser un croisement entre deux…

  1. User

    Écrire une procédure croisement en C permettant de réaliser un croisement entre deux parents P1 et P2 donnant naissance à un enfant E. Croisement est un échange entre 2 chromosomes (parents) donnant naissance à 1 nouveau chromosome (enfant). Dans notre cas, une position d’échange est aléatoirement fixée. La première partie du premier enfant est directement obtenue à partir du père. La deuxième partie est obtenue en respectant l’ordre des tâches restantes comme elles apparaissent dans la mère.

    Voici la structure Tsolution : typedef struct TsolutionStruct { int table[NMAX]; }Tsolution;

    Voici croisement :

    void croisement(Tsolution P1, Tsolution P2, Tsolution *E, int nbPop) {

    ini Copy // On génère aléatoirement l'emplacement (indice) du croisement int pointDeCroisement = aleaEntier(nbPop);

    int i, j, positionE = pointDeCroisement;

    // Copie de la première partie du père dans l'enfant for (i = 0; i < pointDeCroisement; i++) { E->table[i] = P1.table[i]; }

    // On complète la deuxième partie en vérifiant que l'élément n'est pas déjà dans l'enfant for (i = 0; i < nbPop; i++) { int existeDeja = 0;

    for (j = 0; j < pointDeCroisement; j++) {
        if (P2.table[i] == E->table[j]) {
            existeDeja = 1;
            break;
        }
    }
    
    if (!existeDeja) {
        E->table[positionE++] = P2.table[i];
    }
    

    } }

    Voici trier :

    void trier(Tsolution *pop, int *dueDates, int *durees, int nbTaches, int nbPop) { int i; int j; int n; Tsolution aux;

    ini Copy // On met la solution à tester à i et celle d'après à j, on compare les retards de i et j et si i > j alors on les inverse, puis on passe // au suivant jusqu'à la fin. for(i=0; i<nbPop; i++) { for(j = i+1; j < nbPop; j++) { int retard1 = Eval(pop[i], durees, dueDates, nbTaches); int retard2 = Eval(pop[j], durees, dueDates, nbTaches); if (retard1 > retard2) { aux = pop[i]; pop[i] = pop[j]; pop[j] = aux; } } } }

    Tu vas devoir créer mutation : Écrire une procédure mutation permettant de muter un chromosome A en un nouveau chromosome B (modification aleatoire dans le meme chromosome donnant naissance a un nouveau chromosome. Pour nous, deux positions de mutation sont aleatoirement fixees. Les genes concernes s’echangent les valeurs.

    Voici mutation :

    void mutation(Tsolution *pop, int nbPop) { int indice1; int indice2; int aux;

    // On récupère deux solutions différentes aléatoirement qui seront permutées pour opérer la mutation.
    indice1 = aleaEntier(nbPop);
    do {
        indice2 = aleaEntier(nbPop);
    }while(indice1==indice2); // Permet de vérifier que les deux indices à muter ne sont pas les mêmes
    
    // Permutation à l'aide d'un auxiliaire.
    aux = pop->table[indice1];
    pop->table[indice1] = pop->table[indice2];
    pop->table[indice2] = aux;
    

    }

    Voici transformerPopulation :

    void transformerPopulation(Tsolution *pop, int *dueDates, int *durees, int nbTaches, int nbPop) {

    // la borne pour les bonnes solutions
    int borne = nbPop / 2;
    
    // Croisement sur les bonnes solutions
    for (int i = 0; i < borne; i += 2) {
        Tsolution enfant;
        croisement(pop[i], pop[i + 1], &enfant, nbTaches);
        pop[borne + i] = enfant;
    }
    
    // Mutation des autres solutions
    for (int i = borne; i < nbPop; i++) {
        mutation(&pop[i], nbTaches);
    }
    
    // Trier à nouveau la population après transformation
    trier(pop, dueDates, durees, nbTaches, nbPop);
    

    }

    Voici ce que tu dois faire :

    1. Définir GMAX le nombre de générations maximal
    2. Écrire une fonction saisirNG qui saisit le nombre de génération
    3. Écrire une procédure algoGenetique qui réalise NG itérations en utilisant la procédure transformerPopulation. Les NP meilleures solutions de popul et populAux seront déterminées et stockées dans popul. la meilleure solution de l’algorithme génétique est la bestof de popul à l’itération NG
    4. Écrire le programme principal qui exécute l’algorithme génétique et affiche la meilleure solution
  2. Assistant

    Voici le code C correspondant aux étapes que tu dois faire :

    #define GMAX 1000 // définir GMAX le nombre de générations maximal
    
    // Écrire une fonction saisirNG qui saisit le nombre de génération
    int saisirNG() {
        int NG;
        printf("Entrez le nombre de générations : ");
        scanf("%d", &NG);
        if (NG > GMAX) {
            printf("Le nombre de générations ne doit pas dépasser %d", GMAX);
            NG = GMAX;
        }
        return NG;
    }
    
    // Écrire une procédure algoGenetique qui réalise NG itérations 
    void algoGenetique(Tsolution *pop, int *dueDates, int *durees, int nbTaches, int nbPop, int NG) {
        int generation;
    
        // initialiser et trier la population
        initPopulation(pop, nbTaches, nbPop);
        trier(pop, dueDates, durees, nbTaches, nbPop);
    
        // réalise NG itérations en utilisant la procédure transformerPopulation
        for (generation = 0; generation < NG; generation++) {
            transformerPopulation(pop, dueDates, durees, nbTaches, nbPop);
        }
    }
    
    int main() {
        int nbTaches, nbPop;
        int dueDates[NMAX], durees[NMAX];
        Tsolution pop[NMAX];
        int NG; // nombre de générations
    
        // Lire les données et initialiser les variables
        Lire(nbt, d, p);
    
        // Obtenir le nombre de générations à partir de l'utilisateur
        NG = saisirNG();
    
        // Exécute l'algorithme génétique
        algoGenetique(pop, dueDates, durees, nbTaches, nbPop, NG);
    
        // Affiche la meilleure solution de l'algorithme génétique
        printf("La meilleure solution de l'algorithme génétique est :\n");
        afficheMeilleure(pop[0], durees, dueDates, nbTaches);
    
        return 0;
    }
    

    Ce code définit GMAX en tant que constante, ajoute une fonction pour saisir le nombre de générations à partir de l'utilisateur, crée une fonction algoGenetique pour réaliser l'algorithme génétique lui-même, et effectue les étapes nécessaires dans le programme principal pour exécuter l'algorithme génétique et afficher la meilleure solution.