Système de fourmis

L’algorithme du système de fourmis est inspiré par le comportement de recherche de nourriture des fourmis, en particulier la communication par des phéromones entre les fourmis concernant un bon chemin entre la colonie et une source de nourriture dans un environnement. Ce mécanisme est appelé stigmergie.

Les fourmis errent initialement au hasard dans leur environnement. Une fois la nourriture localisée, une fourmi commencera à déposer des phéromones dans l’environnement. De nombreux voyages entre la nourriture et la colonie sont effectués et si la même route qui mène à la nourriture est suivie, des phéromones supplémentaires sont déposées. Les phéromones se désintègrent dans l’environnement, de sorte que les anciennes voies sont moins susceptibles d’être suivies. D’autres fourmis peuvent découvrir le même chemin vers la nourriture et à leur tour peuvent le suivre et également déposer des phéromones. Un processus de rétroaction positive achemine de plus en plus de fourmis vers des voies productives qui sont à leur tour affinées par l’utilisation.

L’objectif de la stratégie est d’exploiter des informations historiques et heuristiques pour construire des solutions candidates et replier les informations tirées de la construction de solutions dans l’historique. Les solutions sont discrètes et construite de façon probabiliste pour chaque étape. La probabilité de sélection d’un composant est déterminée par la contribution heuristique du composant au coût global de la solution et à la qualité des solutions à partir desquelles le composant est historiquement connu pour avoir été inclus. L’historique est mis à jour proportionnellement à la qualité des solutions candidates et est uniformément diminué, garantissant la conservation des informations les plus récentes et utiles.

L’algorithme suivant fournit un pseudocode de l’algorithme principal pour minimiser une fonction de coût. Le processus de mise à jour des phéromones est décrit par une équation unique qui combine les contributions de toutes les solutions candidates avec un coefficient de désintégration pour déterminer la nouvelle valeur des phéromones, comme suit:

où τ_i,j représente la phéromone pour le composant (une arête dans un graphe) (i; j), ρ est le facteur de désintégration, m est le nombre de fourmis et la somme des deltas est la somme de 1/S_cost (maximisation du coût de la solution) pour les solutions qui incluent le composant i,j. L’algorithme montre cette équation comme un équivalent d’un processus de désintégration en deux étapes suivi d’une mise à jour pour plus de simplicité.

La construction probabiliste par étapes de la solution utilise à la fois l’historique (phéromone) et des informations heuristiques spécifiques au problème pour construire progressivement une solution pièce par pièce. Chaque composant ne peut être sélectionné que s’il n’a pas déjà été choisi (pour la plupart des problèmes combinatoires), et pour les composants qui peuvent être sélectionnés (compte tenu du composant actuel i), leur probabilité de sélection est définie comme suit :

où η_i,j est la contribution maximisante au score global de sélection du composant (tel que 1/distance pour le problème du voyageur de commerce), α est le coefficient heuristique, τ_i,j est la valeur de phéromone pour le composant, β est le coefficient de l’historique , et c est l’ensemble des composants utilisables.

L’algorithme a été conçu pour être utilisé avec des problèmes combinatoires tels que le TSP, le problème du sac à dos, les problèmes d’affectation quadratique, les problèmes de coloration des graphes et bien d’autres.

Le coefficient d’historique (α) contrôle la quantité de l’historique des contributions dans la probabilité de sélection des composants et est généralement défini sur 1,0. Le coefficient heuristique (β) contrôle la quantité d’informations heuristiques spécifiques au problème de contribution jouées dans une probabilité de sélection des composants et se situe généralement entre 2 et 5, comme 2,5. Le facteur de décroissance (ρ) contrôle la vitesse à laquelle les informations historiques sont perdues et est généralement fixé à 0,5. Le nombre total de fourmis (m) est généralement défini sur le nombre de composants du problème, tels que le nombre de villes dans le TSP.