[Créationnisme scientifique athée]
[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 ?


< Précédent| |Suivant >





  • 1er article [SCIENCE]: e





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