Glossaire IA
Le dictionnaire complet de l'Intelligence Artificielle
Algorithme de Colonie de Fourmis (ACO)
Métaheuristique inspirée du comportement des fourmis réelles utilisant des phéromones artificielles pour trouver des solutions optimales dans les problèmes d'optimisation combinatoire. L'algorithme simule le dépôt et l'évaporation de phéromones pour guider la recherche vers les meilleures solutions.
Évaporation des phéromones
Mécanisme de décroissance exponentielle des concentrations de phéromones permettant d'éviter la convergence prématurée et de favoriser l'exploration de nouvelles solutions. Ce processus simule l'évaporation naturelle des phéromones dans les colonies de fourmis réelles.
Probabilité de transition
Règle probabiliste déterminant le choix du prochain élément à ajouter à une solution partielle par une fourmi, basée sur les niveaux de phéromones et l'information heuristique locale. Cette probabilité combine l'apprentissage collectif et l'information à priori pour guider la recherche.
Construction de solution
Processus itératif où chaque fourmi construit une solution complète en ajoutant séquentiellement des composants selon les probabilités de transition. La construction est probabiliste mais biaisée par les traces de phéromones laissées par les solutions précédentes.
Mise à jour locale des phéromones
Mécanisme de modification des traces de phéromones effectué par chaque fourmi immédiatement après avoir ajouté un composant à sa solution partielle. Cette mise à jour locale réduit la probabilité que les autres fourmis choisissent le même chemin pendant la même itération.
Mise à jour globale des phéromones
Processus appliqué après la construction de toutes les solutions dans une itération, où seules les meilleures solutions déposent des phéromones pour renforcer les composants prometteurs. Ce mécanisme concentre la recherche sur les régions les plus prometteuses de l'espace de solutions.
Optimisation combinatoire
Classe de problèmes mathématiques consistant à trouver la meilleure configuration parmi un ensemble fini mais très grand de solutions possibles. Les algorithmes de colonie de fourmis sont particulièrement efficaces pour résoudre ces problèmes NP-difficiles.
Problème du voyageur de commerce (TSP)
Problème classique d'optimisation combinatoire où l'objectif est de trouver le chemin le plus court visitant chaque ville exactement une fois avant de retourner au point de départ. Le TSP est souvent utilisé comme benchmark pour évaluer les performances des algorithmes de colonie de fourmis.
Paramètre alpha (α)
Coefficient contrôlant l'influence des traces de phéromones dans le calcul des probabilités de transition dans les algorithmes ACO. Une valeur élevée de alpha favorise l'exploitation des solutions précédemment découvertes.
Paramètre bêta (β)
Paramètre régulant l'importance de l'information heuristique dans le choix des transitions, représentant généralement la visibilité ou la désirabilité locale d'un mouvement. Ce paramètre équilibre l'apprentissage collectif avec l'information à priori du problème.
Paramètre rho (ρ)
Taux d'évaporation des phéromones, coefficient compris entre 0 et 1 déterminant la vitesse à laquelle les traces de phéromones décroissent entre les itérations. Ce paramètre contrôle la persistance de l'information accumulée dans le système.
Paramètre Q
Constante utilisée pour quantifier la quantité de phéromones déposée par les fourmis, souvent proportionnelle à la qualité de la solution trouvée. Ce paramètre influence l'intensité du renforcement des bonnes solutions dans le système.
Liste de candidats
Mécanisme d'optimisation restreignant le choix des prochains mouvements à un sous-ensemble des options les plus prometteuses basées sur une heuristique locale. Cette technique accélère la convergence en se concentrant sur les solutions potentiellement meilleures.
Heuristique de visibilité
Information statique ou dynamique sur la désirabilité locale d'un mouvement, généralement basée sur des propriétés du problème comme la distance dans le TSP. Cette heuristique guide les fourmis indépendamment des phéromones accumulées.
Diversification de la recherche
Stratégie visant à maintenir l'exploration de différentes régions de l'espace de solutions pour éviter la stagnation sur des optima locaux. Dans l'ACO, elle est contrôlée principalement par le taux d'évaporation et les paramètres de transition.
Intensification de la recherche
Processus de concentration des efforts de recherche autour des solutions les plus prometteuses identifiées jusqu'à présent. Cette stratégie exploite l'information accumulée via les phéromones pour affiner les solutions existantes.