AI Glossary
The complete dictionary of Artificial Intelligence
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.
Alpha parameter (α)
Coefficient controlling the influence of pheromone trails in the calculation of transition probabilities in ACO algorithms. A high alpha value favors the exploitation of previously discovered solutions.
Beta parameter (β)
Parameter regulating the importance of heuristic information in transition choices, generally representing the visibility or local desirability of a move. This parameter balances collective learning with a priori problem information.
Rho parameter (ρ)
Pheromone evaporation rate, a coefficient between 0 and 1 determining the speed at which pheromone trails decrease between iterations. This parameter controls the persistence of accumulated information in the system.
Q parameter
Constant used to quantify the amount of pheromones deposited by ants, often proportional to the quality of the solution found. This parameter influences the intensity of reinforcement of good solutions in the system.
Candidate list
Optimization mechanism restricting the choice of next moves to a subset of the most promising options based on a local heuristic. This technique accelerates convergence by focusing on potentially better solutions.
Visibility heuristic
Static or dynamic information on the local desirability of a move, generally based on problem properties such as distance in TSP. This heuristic guides ants independently of accumulated pheromones.
Search diversification
Strategy aiming to maintain exploration of different regions of the solution space to avoid stagnation on local optima. In ACO, it is mainly controlled by the evaporation rate and transition parameters.
Search intensification
Process of concentrating search efforts around the most promising solutions identified so far. This strategy exploits accumulated information via pheromones to refine existing solutions.