Sorry, you need to enable JavaScript to visit this website.

Algorithmes génétiques : principes, opérateurs, paramètres et applications (Généré intégralement par IA)

Soumis par dpalicepeio le
Algorithmes_génétiques

Les algorithmes génétiques

Technique d’optimisation stochastique inspirée de la sélection naturelle et de la génétique. Exploration d’un espace de recherche à l’aide d’une population de solutions candidates, améliorées itérativement par sélection, croisement et mutation, selon une fonction d’évaluation (fitness).

Principes clés

  • Population: ensemble de solutions candidates (individus).
  • Encodage: représentation des solutions (binaire, réelle, permutation, structures mixtes).
  • Fitness: mesure de qualité de chaque individu.
  • Sélection: préférence donnée aux individus les mieux évalués.
  • Croisement: recombinaison d’individus pour créer de nouveaux candidats.
  • Mutation: petites perturbations pour maintenir la diversité et éviter la stagnation.
  • Élitisme: conservation des meilleurs individus d’une génération à l’autre.
  • Arrêt: condition basée sur un budget d’évaluations, un nombre de générations, ou la convergence.

Cycle de fonctionnement

  1. Initialisation aléatoire de la population.
  2. Évaluation de la fitness de chaque individu.
  3. Sélection de parents selon la fitness.
  4. Application du croisement et de la mutation pour produire une nouvelle population.
  5. Insertion élitiste éventuelle des meilleurs individus précédents.
  6. Vérification du critère d’arrêt, sinon répétition du cycle.

Représentation et fitness

  • Encodage binaire: chaînes de bits, opérateurs simples, adapté aux variables discrètes.
  • Encodage réel: vecteurs de nombres réels, croisement arithmétique, mutation gaussienne.
  • Encodage par permutation: problèmes d’ordonnancement et de tournée (ex. TSP), croisement PMX/OX, mutation swap.
  • Fitness: fonction à maximiser; en cas de minimisation, transformation possible par f’ = −f ou 1/(1+f).
  • Contraintes: stratégies de pénalisation, réparation, ou opérateurs fermant l’espace aux solutions invalides.

Opérateurs de sélection

  • Roulette (proportionnelle): probabilité liée à la fitness.
  • Tournoi: comparaison de petits sous-ensembles, contrôle simple de la pression de sélection.
  • Rang: robustesse face aux échelles de fitness, réduction des effets de domination.

Opérateurs de variation

  • Croisement:
    • 1 ou 2 points, uniforme (encodage binaire).
    • Arithmétique, BLX-α, SBX (encodage réel).
    • PMX, OX, CX (permutations).
  • Mutation:
    • Flip de bits (binaire).
    • Perturbation gaussienne ou uniforme (réel).
    • Échange, insertion, inversion (permutation).

Paramétrage courant

  • Taille de population: 20–500 (selon dimension et budget d’évaluations).
  • Taux de croisement: 0,6–0,9.
  • Taux de mutation: 1/L pour binaire (L = longueur du génome), 0,01–0,2 pour réel, 0,05–0,2 pour permutation.
  • Pression de sélection: modérée pour préserver la diversité.
  • Élitisme: 1–5 % des meilleurs individus.

Variantes et extensions

  • AG multi-objectifs: NSGA-II, SPEA2 pour optimiser plusieurs critères simultanément (front de Pareto).
  • AG hybrides (memétiques): intégration de recherche locale pour un raffinement intensif.
  • Stratégies d’évolution, Programmation génétique, Différentiel évolutif: familles voisines pour d’autres encodages et opérateurs.
  • AG parallèles/îles: sous-populations avec migrations pour améliorer l’exploration.

Applications

  • Optimisation combinatoire: tournées, affectation, ordonnancement.
  • Conception et ingénierie: optimisation de structures, paramètres de contrôle, CAO.
  • Apprentissage automatique: sélection de caractéristiques, réglage d’hyperparamètres, architecture de réseaux.
  • Finance et logistique: allocation d’actifs, planification, gestion d’inventaire.
  • Bioinformatique: alignement, dessin de primers, réseaux de gènes.

Avantages

  • Peu d’hypothèses sur la fonction objectif (boîte noire, non différentiable, bruitée).
  • Capacité à échapper aux minima locaux grâce à la diversité.
  • Parallélisation naturelle des évaluations.

Limites

  • Coût élevé en évaluations pour des fonctions chères.
  • Sensibilité au paramétrage et au choix des opérateurs/encodage.
  • Convergence prématurée en cas de diversité insuffisante.

Pseudo-code simplifié

Initialiser Population P
Évaluer P
Tant que critère d’arrêt non atteint:
  P' ← Sélection(P)
  P'' ← Croisement(P')
  P''' ← Mutation(P'')
  P_next ← Élitisme(P, P''')
  Évaluer P_next
  P ← P_next
Restituer le meilleur individu de P

Bonnes pratiques

  • Normalisation/rang de la fitness pour éviter les déséquilibres extrêmes.
  • Maintenance de la diversité: mutation adaptative, sélection par rang, îles.
  • Validation croisée ou ensembles de test pour éviter le surapprentissage sur la fitness.
  • Plusieurs réexécutions avec graines différentes pour robustesse statistique.
  • Surveillance des indicateurs: meilleure fitness, diversité génotypique/phénotypique, stagnation.

Complexité et performance

  • Coût dominant: évaluations de la fitness.
  • Complexité approximative: O(taille_population × générations × coût_évaluation).
  • Réduction du coût: méta-modèles, échantillonnage, parallélisation.

Étiquettes