[SCIENCE-2010]
Les fourmis - - .
- - - optimisation selon des algorythmes mathématiques...
Cet article est en cours d'élaboration, l'internaute est invité à revenir en novembre 2012
co ?
| Artile de l'université colombienne de ---- Disponible sur : http://www.unab.edu.co/editorialunab/revistas/rcc/pdfs/r21_art1_c.pdf |
|
| TRADUCTION EN FRANCAIS |
|
| Page 1 REVISTA Colombiana de Computación Volumen 2, Numéro 1 Págs. 7-18 Un modèle Ant Colony général pour résoudre combinatoire Les problèmes d'optimisation José Aguilar * Abstrait Un système de fourmis est un système artificiel basé sur le comportement des colonies de fourmis réelles, qui est utilisé pour résoudre des problèmes combinatoires. Il s'agit d'un algorithme distribué composé d'un ensemble d'agents coopérants appelés fourmis qui coopèrent entre eux pour trouver de bonnes solutions à des problèmes d'optimisation combinatoire. La coopération suit le comportement des fourmis réelles en utilisant une forme indirecte de la communication médiée par un phéromone. Dans ce travail, nous présentons un nouvel algorithme distribué basé sur Ant System concepts, appelé le Système Ant général, pour résoudre optimisation combinatoire Problèmes. Notre approche consiste à mapper l'espace de solution de la combinatoire Problème d'optimisation de l'espace où les fourmis se promener, et sur la définition de la probabilité de transition du système Ant selon la fonction de performance de l' Problème d'optimisation combinatoire. Nous avons testé notre approche sur le partitionnement de graphe et Le. Voyager problèmes Salesman Les résultats montrent que notre approche a l' mêmes performances que les versions précédentes des systèmes d'Ant. Mots-clés: problème d'optimisation combinatoire, Ant System, le partitionnement de graphe et Le. Voyager problèmes Salesman 1 Introduction Les études de l'Intelligence Collective Antimalware comment les actions et les inter-relations d'un ensemble d'agents simples (par par exemple, les abeilles, les fourmis, etc) réaliser les objectifs globaux du système où ces agents sont immergés. Chaque agent collabore à la réalisation des tâches à accomplir ces objectifs, sans centrale coordination ou de contrôle, à travers des mécanismes d'inter-relation et la communication entre eux [1, 10]. Dans ces systèmes, leurs agents ne sont pas individuellement intelligent, mais leurs actions dans leur ensemble ont un comportement intelligent pour mener à bien certains objectifs des systèmes (par exemple: la la recherche de sources de nourriture). Des exemples de ces systèmes sont des systèmes d'insectes (par exemple: abeille ou les colonies de fourmis). Par exemple, réel Les fourmis sont capables de trouver le plus court chemin entre une source de nourriture dans leur nid sans l'aide visuelle en exploitant les informations des signaux de phéromone [2, 5, 6, 7]. Tout en marchant, les fourmis dépôt de phéromone sentiers sur le terrain et suivre phéromone précédemment déposée par d'autres fourmis. Le comportement ci-dessus du réel fourmis a inspiré le système de fourmis (AS), un algorithme dans lequel un ensemble de fourmis artificielles coopérer à l' solution d'un problème en échangeant des informations par l'intermédiaire de phéromone déposée sur un graphique. La principale caractéristiques de l'AS sont les suivants: il s'ensuit une réaction positive (il permet de trouver de bonnes solutions rapidement), * Universidad de los Andes, Mérida, 5101. Venezuela, CEMISID. Departamento de Computación, Facultad de Ingeniería, fax: (58.74) 402 872 fax (domicile): (775) 5422983, e-mail: aguilar@ing.ula.ve Page 2 2 José Aguilar il est basé sur le calcul distribué (il évite convergence prématurée), il utilise une approche constructive heuristique gloutonne (ça aide à trouver des solutions acceptables) et il s'agit d'une approche basée sur la population. Dorigo a proposé le premier comme dans son Ph.D. thèse [5]. À l'heure actuelle, la plupart des travaux ont été réalisés dans le sens d'application AS à des problèmes d'optimisation combinatoire [4, 6, 10, 11, 12, 13, 14]. AS a été appliquée au problème du voyageur de commerce, sur le problème d'affectation quadratique, entre autres. Sur l'autre part, les différents groupes ont travaillé sur différentes versions étendues de l'AS paradigme (Ant-Q, etc) [7, 8, 9]. Dans l'AS appliqué à l'Traveling Salesman Problem (TSP), un ensemble d'agents coopérants, appelés fourmis, coopérer afin de trouver de bonnes solutions aux TSP en utilisant une forme indirecte de la communication à travers des pistes de phéromones qu'elles se déposent sur les arêtes du graphe TSP tout en construisant des solutions. Officieusement, chaque fourmi construit une solution TSP de manière itérative: il ajoute de nouvelles villes à une solution partielle par exploiter les informations tirées de l'expérience passée et une heuristique gloutonne. Prend la mémoire sous forme de traces de phéromone déposée par les fourmis sur les bords de TSP, alors que l'information heuristique est tout simplement donnée par poids de l'arête. Il ya deux raisons pour une application facile de l'AS sur le TSP: a. Le graphique représente l'espace TSP solution de ce problème. Ce graphique TSP peut être utilisé pour décrire l'espace où les fourmis marcher (AS graph). Autrement dit, le graphe TSP peut être directement utilisé par l'AS, car sa structure est la même que la utilise comme solutions pour construire les (AS graphique). b. La fonction de transition a des objectifs similaires à ceux de la fonction objectif TSP. La transition objectif de fonction est un compromis entre la visibilité (qui dit nœuds étroits devraient être choisis avec une forte probabilité) et l'intensité piste à un moment donné (la phéromone formule est mise à jour sur la base de la longueur de bord et le trafic fourmis). L'objectif est de trouver TSP une longueur minimale Tour fermé qui rend chacun ville. Ce n'est pas le cas pour d'autres combinatoire problèmes d'optimisation. Nous proposons un nouvel algorithme distribué basé sur AS concepts, appelé le Système Ant général (SGA), pour résoudre des problèmes d'optimisation combinatoire. L'idée principale roman présenté par notre approche est la définition d'une procédure générale pour résoudre des problèmes d'optimisation combinatoire en utilisant AS. Dans notre approche, le graphique qui décrit l'espace des solutions du problème d'optimisation combinatoire est mappé sur le graphique AS, et la fonction de transition et la mise à jour de la phéromone de formule AS sont construit selon la fonction objectif du problème d'optimisation combinatoire. Nous avons testé notre approche sur le problème de partitionnement de graphe classique (GPP) et le TSP. Ce papier est organisé comme suit: la section II de l'AS et le PPM. Ensuite, nous présentons notre approche. La section IV présente les expériences. Nous comparons nos résultats avec un précédent pour le PPM et le TSP. Enfin, nous présenter notre conclusion. 2 Aspects théoriques 2.1 Systèmes de Ant Les études de l'Intelligence Collective Antimalware comment apparaissent les capacités cognitives collectives sur les systèmes d'insectes [1, 10]. Ces capacités cognitives sur les systèmes d'insectes de leur permettre de remplir les objectifs qui garantissent leur survie / la vitalité des environnements hostiles avec une grande efficacité. Des exemples de ces systèmes sont colonies de fourmis, les colonies d'abeilles, de guêpes, etc colonies Ainsi, l'intelligence collective est une émergence phénomène d'activités des individus qui génèrent un comportement collectif et sophistiqué dans le système (par exemple: la construction des nids, la recherche des aliments, etc.) Les principales caractéristiques de Page 3 Un modèle Ant Colony général pour résoudre les problèmes d'optimisation combinatoire 3 Ces systèmes sont les suivants: - Ils n'ont pas un contrôle central. - Ils ont des capacités d'auto-organisation. - Existe un objectif commun à tous les individus / agents du système. - Elles sont basées sur une division des tâches. En général, le comportement des colonies de fourmis est impressionnant de réaliser leurs objectifs de survie. Il est dérivée d'un processus d'intelligence collective. Ce processus est basé sur la communication de la fourmi capacités, qui définissent les inter-relations entre eux. Ces inter-relations permettent de transmettre les informations que chaque fourmi va de traitement. La communication entre les agents (fourmis) est faite par une trace, appelée phéromone. Ainsi, une fourmi laisse une certaine quantité de phéromone quand il il se déplace. En outre, la probabilité qu'une fourmi suit une trajectoire dépend du nombre de fourmis que a pris le chemin (une grande quantité de phéromone dans un chemin, un grande probabilité d'être visité). AS est l'ancêtre de tous les efforts de recherche avec des algorithmes de fourmis et a d'abord été appliqué à la TSP [2, 3, 5, 6]. Algorithmes inspirés sur AS sont apparus comme des méthodes heuristiques qui permettent la résolution problèmes d'optimisation combinatoire. Les principales caractéristiques de ces algorithmes sont les suivante: leurs versatilités, leur robustesse et leurs activités en fonction des populations. La procédure est basée sur la distribution de la recherche sur les agents dits «fourmis», c'est-à-agents à très capacités simples qui tentent de simuler le comportement des fourmis. AS utilise une représentation graphique où (AS graphique) de chaque bord (r, s) est une mesure souhaitable g (r, s), appelée phéromone-, qui est mis à jour lors de l'exécution par des fourmis artificielles. Officieusement, l'AS fonctionne comme suit. Chaque fourmi génère un tour complet en choisissant les nœuds en fonction de l'état probabiliste règle de transition; fourmis préfèrent se déplacer vers des noeuds qui sont reliés par des arêtes courtes, qui ont une grande phéromone montant. Une fois que toutes les fourmis ont terminé leurs visites, une règle phéromone mise à jour globale est appliquée: une fraction des phéromones s'évaporent sur tous les bords, puis chacun des dépôts d'un montant de fourmis de phéromone sur les arêtes qui appartiennent à son tour en proportion de sa tournée était courte. Le procédé est ensuite itérée. La règle de transition d'état utilisées par le système de fourmi est donnée par l'équation (1), qui donne la probabilité avec laquelle la fourmi k dans la ville r décide de déménager à la ville s (probabilité de transition de noeud à noeud r s pour le k e ant): [[ γ (R, S) n (r, s)] β / Σ u ∈ J k (R) [ γ (R, u) n (r, u)] β si s ∈ J k (R) P k (R, S) = { (1) 0 autrement Où γ est la phéromone, n = 1 / d est l'inverse de la distance d (r, s), J k (R) est l'ensemble des noeuds restent à être visité par la fourmi k positionné sur le nœud r et β est un paramètre qui détermine le rapport importance de phéromone fonction de la distance. Dans AS, la règle de mise à jour globale est réalisé comme suit. Une fois que toutes les fourmis ont construit leurs visites, phéromone est mis à jour sur tous les bords selon (qui est, l'intensité sentier est mis à jour): γ (R, s) = (1 - α ) γ (R, S) + Σ k = 1 Δγ k (R, s) (2) m Page 4 4 José Aguilar Où α est un coefficient de telle sorte que (1 - α) représente l'évaporation piste dans une itération, m est l' nombre de fourmis, et Δγ k (R, s) est la quantité par unité de longueur de piste substance prévue sur le bord (r, s) par le k e ant en ce que l'itération 1 / L k si bord (r, s) ∈ visite effectuée par la fourmi k Δγ k (R, S) = { 0 autrement Où L k est la longueur du tour effectué par la fourmi k. Pheromone mise à jour est destinée à allouer une plus grande quantité de phéromone de courtes visites. Pheromone placés sur les bords joue le rôle d'un système distribué mémoire à long terme; cette mémoire n'est pas localement dans les fourmis individuelles, mais est réparti sur les arêtes du graphe. L'algorithme général est le à la suite: 1. Placez les fourmis m au hasard sur les nœuds du graphe AS 2. Répétez jusqu'à ce que la convergence du système 2.1 Pour i = 1, n2.1.1 Pour j = 1, m 2.1.1.1. Choisir le noeud s pour passer, en fonction de la transition probabilité (équation 1) 2.1.1.2. Déplacez le m fourmi pour le sommet s 2,2 Mise à jour de la phéromone en utilisant la phéromone mise à la formule (équation 2) La complexité en temps de l'AS est en O (t * n 2 * m), où t est le nombre d'itérations effectuées (jusqu'à système convergence). Différentes versions pour améliorer la classique AS ont été proposées [6, 7, 8, 9]. Deux des elles sont la fourmi densité et la quantité de fourmis algorithmes. Ils diffèrent dans la façon dont la piste est mis à jour. En ces modèles chaque fourmi dépose son chemin à chaque étape, sans attendre la fin de la tournée. Ant au- un modèle de densité de Q quantité de traînée apparaisse sur le bord (r, s) à chaque fois une fourmi passe de R à S; dans la fourmilière modèle quantité d'une fourmi va de r à s laisse une quantité Q / j (r, s) de sentier sur le bord (r, s) chaque fois qu'il va de r à s. Dans un ouvrage plus récent, ils proposent une nouvelle extension à l'AS, appelé ACS. L'ACS diffère de la précédente en: - La règle de transition d'état fournit un moyen direct de l'équilibre entre l'exploration de nouvelles arêtes et l'exploitation des a priori et des connaissances accumulées sur le problème. - La règle de mise à jour globale est appliquée uniquement aux bords qui appartiennent à la tournée meilleure fourmi. - Un local à phéromones mise à jour règle est appliquée tandis que les fourmis construire une solution. 2.2 Problème de partitionnement de graphe Le PPM consiste à diviser en sous-graphes d'un diagramme de plusieurs, de façon à minimiser les coûts de connexion entre eux. Nous pouvons compliquer le problème en pondérant les arcs. Dans ce cas, nous devons minimiser la somme des poids entre les sous-ensembles. En outre, on peut ajouter un poids aux nœuds et de définir à nouveau ce que nous voulons minimiser en fonction des caractéristiques particulières du problème [1, 13]. Afin de formuler mathématiquement le problème, la définition suivante est nécessaire: G = (N, A), où, Page 5 Un modèle Ant Colony général pour résoudre les problèmes d'optimisation combinatoire 5 - G est un graphe non orienté, - N = {1, ..., n} est un ensemble de n nœuds sur lesquels on peut associer une fonction de poids Q: N -> R. Dans le document nôtre Q (i) = 1 pour i = 1, .., n, - A = a ij , Sont des paires de noeuds qui définissent des arcs. Elle est connue comme la matrice d'adjacence. Selon certaines contraintes, le problème consiste à diviser le graphique en K différents sous- graphiques. Les contraintes classiques sont les suivantes: - Sous-graphes doivent avoir une taille spécifique ou doivent avoir une somme en poids des nœuds moins à une valeur donnée. - Arcs avec des extrémités en sous-graphes différents doivent être minimes, ou la somme des poids des arcs qui se rejoignent nœuds dans différents sous-graphes doivent être minimisés. Les associés d'une fonction de coût réelle valeur ajoutée à toutes les configurations de sous-graphe. Nous proposons le coût prochain fonction: Fc = Σ i, j ∈ D un ij + B Σ z = 1 (N Gz - N / K) 2 / K (3) où: - D = {i ∈ G et j ∈ Gl et l ≠ m} - N Gz = Nombre de nœuds sous-graphe z, - B = facteur d'équilibre [0,2]. Le premier terme minimise la somme des poids des arcs qui appartiennent à la coupe. Le terme de sommation deuxième avoir une valeur minimale uniquement lorsque le nombre de noeuds par sous-graphe est le même. Le facteur d'équilibre (b) définit l'importance du coût d'interconnexion par rapport au coût déséquilibre. Le GPP est réduit à trouver une configuration avec sous-graphe valeur minimale pour la fonction de coût: F = MIN (Fc) Figure 1: partition d'un graphe G avec 3 nœuds en 2 sous-graphes. K Page 6 6 José Aguilar 2.3 Le problème du voyageur de commerce Le problème du voyageur de commerce est un problème d'optimisation classique qui pourrait décrire selon la déclaration suivante: étant donné n villes, le Vendeur doit visiter chaque ville une fois et le coût total de l' visite devrait être minime. On peut définir le coût de la visite que la somme des distances entre le visité des villes. Ce problème peut être exprimé de la manière suivante: G = (N, A) où: - N = {1, ..., n}, il est le graphe avec n noeuds, - A = {a ij }, C'est la matrice de contiguïté. Si nous supposons que les villes sont numérotées de 1 à n, une solution au problème pourrait exprimer à travers une matrice d'état (E) qui indique que l'ordre dans les villes sont visités: e ij = { 1 si la ville i a été visité dans la position j 0 Autrement La matrice E permettra de vérifier la validité d'une solution, c'est toutes les villes doivent être visitée qu'une seule fois: Σ i = 1 Σ j = 1 e ij N = Σ i = 1 e ij = 1 Σ j = 1 e ij = 1 La matrice E permet de définir une matrice V de n éléments, qui contiennent de la ville qui ont vu dans chaque position. V j = I (i Si la ville a été visité dans la position j) Enfin, nous proposons une fonction compose de deux parties, la première calcule les distances entre les villes, et l'autre détermine le degré de validité de la solution. Ces fonctions sont les suivantes: F1 = Σ i = 1 Σ k = 1 Σ j = 1 l ik e ij e kj 1 où l ij = Distance entre les villes i et j et F2 = C (| Σ i = 1 Σ k = 1 e ik - N | + Σ i = 1 | Σ k = 1 e ik - 1 | + Σ k = 1 | Σ i = 1 e ik -1 |) Enfin, Fc = F1 + F2 où C = facteur de pénalité. Le problème consiste à trouver le tour des villes qui minimise la valeur de la fonction coût Fc. n n n n n n n n n n n n n Page 7 Un modèle Ant Colony général pour résoudre les problèmes d'optimisation combinatoire 7 3 Notre approche: le système de Ant général Il ya deux raisons pour une application facile de l'AS sur le TSP: la première, le graphique peut TSP être directement mappés sur le graphe des AS. L'autre, la fonction de transition a des objectifs similaires à celles du TSP. Le but AS est un compromis entre la visibilité (qui dit nœuds étroits devraient être choisis avec forte probabilité) et l'intensité piste à un moment donné (la formule phéromone mise à jour est basée sur le longueur d'arête et le trafic des fourmis). L'objectif est de trouver TSP une visite longueur minimale fermé qui se rend dans chaque même ville. Ce n'est pas le cas pour d'autres problèmes d'optimisation combinatoire. Nous proposons un nouvel algorithme distribué basé sur AS concepts, appelé le Système Ant général (SGA), pour résoudre des problèmes d'optimisation combinatoire. Dans notre approche, nous devons définir: - Le graphique qui décrit l'espace des solutions du problème d'optimisation combinatoire (Graphique COP). L'espace de solution est défini par un graphe où les noeuds représentent partielle solutions possibles à ce problème, et les bords de la relation entre la partie solutions. Ce graphique sera utilisé pour définir le graphe des AS (ce qui est le graphe où les fourmis willwalk). - La fonction de transition et la formule mise à jour de la phéromone AS, qui sont construits selon la fonction objectif du problème d'optimisation combinatoire. De cette façon, nous pouvons résoudre n'importe quel problème d'optimisation combinatoire. Le graphique COP définir la structure du graphe des AS. Chaque fourmi construit une solution marche à travers ce graphique en fonction d'un règle de transition et une phéromone formule définie selon l'une mise à jour de la fonction de performance de l' Problème d'optimisation combinatoire. Les principales étapes sont les suivantes: a) Construire le graphe des AS b) Définition de la fonction de transition et la formule mise à jour de la phéromone AS c) Exécutez la procédure classique AS (ou l'une des versions améliorées) 3.1 Build le graphique AS La première étape consiste à construire le graphe COP, puis nous définissons le graphe des AS avec la même structure de l' Graphe Conférence des Parties. Le graphique AS dispose de deux matrices de poids: le premier est défini en fonction de la Conférence des Parties graphique et enregistre la relation entre les éléments de l'espace de solution (COP matrice). La un seconde enregistre la trace de phéromone accumulée sur chaque bord (phéromone matrice). Ce poids matrice est calculée / mise à jour selon la formule de la mise à jour de la phéromone. Un nœud a plus de probabilité d'être visité si le poids des bords de la matrice de phéromone entrant, il est élevé. Si un bord entre deux noeuds de la matrice COP est faible, ce qui signifie que, idéalement, si l'un de ces nœuds appartient à la finale solution, l'autre doit appartenir aussi. Si le bord est égale à moyens infinis qu'ils sont incom- tible. Nous définissons une structure de données pour enregistrer la solution que chaque fourmi construit. Cette structure de données est un vecteur (Vk) avec une longueur égale à la longueur de la solution (nombre de noeuds que la fourmi doit visiter). Pour une fourmi donnée, le vecteur enregistre chaque noeud de l'espace de solution qu'il visite. 3.2 Définir la fonction de transition et la formule phéromone mise à jour La règle de transition d'état dépend de l'intensité de piste à un moment donné et du trafic de fourmi. Le sentier intensité à un moment donné est défini par la formule mise phéromone. La règle de transition d'état et Page 8 8 José Aguilar la formule phéromone mise à jour sont construits en utilisant la fonction objectif de l'optimisation combinatoire problème. La fonction de transition entre les noeuds est la suivante: Pi (γ (r, s), Fc z ) = Γ (r, s) / Fc k (R-> s) z +1 Où Fc k (R-> s) z +1 est le nouveau coût quand une fourmi k traverser l'arête (r, s) au temps z si elle est en r. La probabilité de transition est calculé selon l'équation suivante: Pi ( γ (R, s), Fc k z ) / Σ u ∈ J k (R) Ft ( γ (R, u), Fc k z ) si s ∈ J k (R) P k (R, S) = { (4) 0 autrement Et la règle de mise à jour de phéromone est calculée en fonction de la formule suivante: 1/fc k si bord (r, s) a été traversé par k ant Δγ k (R, S) = { (5) 0 autrement La procédure générale de notre approche est la suivante: 1. Génération du graphe AS 2. Initialisation de la matrice de phéromone 3. Définition de la règle de transition d'état et la formule phéromone mise à jour en fonction de la Problème d'optimisation combinatoire 4. Placez les fourmis m sur différents nœuds du graphe des AS 5. Répétez jusqu'à ce que la convergence du système 5.1 Pour i = 1, n 5.1.1 Pour j = 1, m 5.1.1.1. Choisissez le sommet s à déplacer, en fonction de la probabilité de transition (équation 4) 5.1.1.2. Déplacez le m fourmi pour le sommet s 5.2 Mise à jour de la phéromone en utilisant la phéromone mise à la formule (équations 2 et 5) La complexité de l'algorithme de temps est le même que le AS algorithme, O (t * n 2 * m), où t est le nombre d'itérations effectué. 4 Expériences Nous avons développé une version de notre approche sur C + +, et nous avons exécuté notre programme sur un PC. Nous avons testé notre approche pour un ensemble de référence pour le PPM et TSP.We avez exécuté notre algorithme 30 fois pour calculer chaque point. Notre implémentation de calcul est composée de trois classes: Graphique classe a): qui définit le graphe des AS. b) la classe Ant: qui gère la structure de données de chaque fourmi (Vk), etc c) AntSystem: qui gère l'AS (phéromone mise à jour, etc) 4.1 Build le graphique AS Pour le cas du PPM, le graphe COP est défini par des noeuds qui représentent l'affectation possible de chaque noeud du graphe de diviser (par exemple, le noeud (A, 1) de la figure 2 représentent l'assignation Page 9 Un modèle Ant Colony général pour résoudre les problèmes d'optimisation combinatoire 9 du noeud A du graphe G de la figure 1, le sous-graphe premier), et des arcs qui représentent la relation entre l'affectation possible. A bord du poids est égal aux moyens infinis que ces nœuds ne peuvent pas appartenir à la solution finale ensemble (ils sont incompatibles solution). Par exemple, le nœud A ne peut pas être affecté à des sous-graphes 1 (A, 1) et 2 (A, 2) à l'arc time.A même poids égal à 0 signifie que ces nœuds ainsi n'introduisent pas de coûts de communication supplémentaires (parce qu'ils représentent les affectations au sous-graphe même). Une valeur est égale à un poids AB correspond au bord poids entre les nœuds A et B du graphe G de diviser (graphe de la figure 1). Nous utilisons cette information pour construire l'AS structure du graphe et sa matrice Conférence des Parties. Figure 2. Graphe COP pour le PPM du graphe G défini sur la figure 1. Dans le cas du problème GPP, la structure de données (Vk) pour enregistrer la solution que chaque fourmi construit est un vecteur de longueur n. Chaque élément (V k Je ) Enregistre la cession de l'un des nœuds du graphe de diviser dans un sous-graphe donné (par exemple, la figure 3 montre que le noeud B est attribué à sous-graphe 1, etc.) Figure 3. Structure de données d'une fourmi pour le PPM. Dans le cas du TSP, le graphique AS est le graphe TSP qui décrit la distance entre les villes. Chaque Elément de Vk (V k Je ) Enregistre le nœud qui a été visité dans cette position. Figure 4. Structure de données d'une fourmi pour le TSP. Page 10 10 José Aguilar 4.2 Définir la fonction de transition et la mise à jour des phéromones formule Pour le PPM, Fc k est défini selon l'équation 3: Fc k = Cc + Cb Où Cc est le coût de la communication Cc = Σ ((R, p), (x, m) ∈ Vk et p, m ∈ D1) un rx D1 = {p ≠ m} et Cb est l'équilibre entre les coûts Cb = Σ j = 1 (N c/K- Gj k ) 2 / K Où c est le nombre de noeuds affectés par la fourmi k (longueur actuelle de Vk) et N Gj k est le nombre d' nœuds qui la fourmi k est affecté à sous-graphe Gj. Dans le cas du TSP, la fonction de coût (Fc k ) Est: Fc k = Σ (M = 1 δ ij ∈ ) D2 l ij D2 = {i = V k m δ j = V k m +1 } Où c est le nombre de noeuds traversés par la fourmi k (longueur actuelle de Vk) et l ij est la distance entre les villes i et j. Ce coût est équivalent au paramètre Lc de la Δγ k (R, s) équation. Pour calculer Fc k (R-> s) z +1 , Le noeud s est inclus dans Vk. De cette façon, nous pouvons utiliser les mêmes fonctions de coût pour chaque problème. 4.3 Analyse Résultat Pour tester notre algorithme, nous utilisons les graphes de la http://www.iwr.uni-heidelberg.de/iwr/ page web comopt/soft/TSPLIB95/TSPLIB.html pour le TSP et le graphique généré sur [10] pour le PPM. Pour le cas du TSP, nous comparons notre approche avec la dernière version du système de fourmis proposé par Dorigo (ACS) et les meilleurs résultats rapportés pour les algorithmes génétiques (AG) [1]. Dans le cas de marchés publics écologiques, nous comparons notre approche avec nos travaux précédents [10]. Les résultats sont présentés dans les tableaux suivants. Le nombre premier est le coût de la solution et le second nombre est le nombre d'itérations de l'algorithme. Tableau 1. Résultats pour le TSP K c-1 Page 11 Un modèle Ant Colony général pour résoudre les problèmes d'optimisation combinatoire 11 Tableau 2. Résultats pour le TSP symétrique Tableau 3. Résultats pour le TSP asymétrique Tableau 4. Résultats pour le GPP Dans notre approche, nous obtenons de bons résultats avec un faible nombre d'itérations. Dans certains cas, on obtient la même résultat à l'approche de l'ACS et GA. Notre approche est très lent (il a un temps d'exécution important), mais besoin le plus petit nombre d'itérations. Dans notre approche, nous devons améliorer la combinaison entre la recherche globale (nous aimons ce que chaque fourmi recherches pour différentes zones de l'espace des solutions) et le local recherche (la bonne information trouvée pour une fourmi doit être transmise aux autres). Actuellement, la section locale recherche est transmise sous forme de piste lors de la phéromone est mis à jour, et la recherche globale est effectuée parce que nous attribuons les fourmis dans des endroits différents au début. Nous devons ajouter un autre mécanisme pour assurer une recherche globale efficace. L'un des moyens est d'éviter le même chemin pour les fourmis dans la première itérations. 5 Conclusions Dans ce travail, nous avons présenté une approche générale pour l'AS pour résoudre différentes optimisation combinatoire problèmes. Dans notre approche, nous définissons l'espace des solutions du problème d'optimisation combinatoire (Graphique COP) comment l'espace où les fourmis vont marcher (AS graph). Les fourmis marchent à travers cet espace selon un ensemble de probabilités de mise à jour par un état de transition et une mise à jour de règle définie phéromone selon la fonction objectif du problème d'optimisation combinatoire. De cette façon, nous pouvons résoudre un problème d'optimisation combinatoire. Nous avons testé notre approche sur le GPP et le TSP. Nous devons faire davantage d'expériences pour définir la combinaison idéale des paramètres de notre approche (nombre de fourmis, mise à jour locale des phéromones, etc.) Les résultats montrent que notre approche a l' mêmes performances que les versions précédentes. Actuellement, nous testons notre approche sur le graphique Page 12 José Aguilar 12 problème de coloration. Au loin, nous allons tester notre approche sur l'optimisation combinatoire autre problèmes. Bien sûr, l'espace des solutions du problème d'optimisation combinatoire pour tester aura pour pouvoir être décrit par un graphe (graphe COP). Aussi, nous allons améliorer le calcul en cours version de notre approche. Nous allons développer une nouvelle version pour poste de travail. Références [1] E. Bonabeau, M. Dorigo et G. Theraulaz, De Natural Swarm Intelligence Artificielle à Oxford University Press, 1999. [2] A. Coloni, M. Dorigo et V. Maniezzo, Optimisation Distribué par colonies de fourmis. Dans: Proc. Conférence européenne sur la vie artificielle, pp 134-142, 1991. [3] D. Corne, M. Dorigo et F. Paire de gants, de nouvelles idées en optimisation, McGraw Hill, 1999. [4] Costa D. et A. Hertz, les fourmis peuvent Graphiques Couleur Journal de la Société de Recherche Opérationnelle, 48.: 295-305, 1997. [5] M. Dorigo, optimisation, algorithmes d'apprentissage et naturelles, Thèse de doctorat, Ecole Polytechnique de Milan, Italie, 1992. [6] M. Dorigo, V. Maniezzo, A. Coloni, Le système de fourmi: Optimisation par une colonie de coopérer agents, IEEE Trans. Syst. Homme, Cybern, 26 (2):. 29-41, 1996. [7] M. Dorigo et L. Gambardella, une étude de certaines propriétés de Ant-Q. Dans: Proc. 4 e Int. Conf. Résoudre un problème parallèle de la Nature, pp 656-665, 1996. [8] M. Dorigo et Gambardella L., Système de colonie de fourmis: une approche d'apprentissage coopératif à l' Traveling Salesman Problem, IEEE Trans. sur Evolutionary Computation, 1 (1): 53-66, 1997. [9] L. et M. Dorigo Gambardella, Ant-Q: A l'approche de soutien à l'apprentissage Voyager Salesman Problem. Dans: Proc. Int de 12. Conf. sur l'apprentissage machine, pp 252-260, 1995. [10] F. et J. Aguilar Hidrobo "Vers une approche algorithme génétique parallèle Basé sur collective Renseignement pour les problèmes d'optimisation combinatoire ", in: Proc. de la Conférence internationale IEEE Conférence sur Evolutionary Computation, pp 715-720, 1998. [11] P. Kuntz et D. Snyers. La colonisation émergente et de partitionnement de graphe. Dans: Proc du troisième Conférence internationale sur la simulation du comportement adaptatif: de l'animal à Animats 3, 1994. [12] P.Kuntz, P.Layzell et D. Snyers. Une colonie de fourmis-comme agents de partitionnement dans la technologie VLSI. Dans: Proc. de la quatrième Conférence européenne sur la vie artificielle, pp 417-424, 1997. [13] R. Schoonderwoerd, O. Hollande, J. et L. Bruten Rothkrantz, l'équilibrage de charge basé sur Ant- Les réseaux de télécommunications, le comportement adaptatif, 5 (2): 169-207, 1997. [14] Y. et H. Hoos Stützle, Le système Max-Min Ant et la recherche locale pour le voyag |