|
collective Laboratoire VIII |
 |
L’intelligence collective se base sur l’idée qu’il existe des méthodes de résolution de problèmes à un niveau supérieur à celui dont nos méthodes traditionnelles fonctionnent.
Chaque agent individuel ne sait pas qu’il est en train de résoudre un problème, mais l’action collective des agents trouve des solutions au problème. |
Objectifs
- Utiliser des applets JAVA qui implementent le déplacement collectif d'un group d'agents (e.g., banc de poissons, bande d'oisseaux, etc) en faisant appel aux comportements de base proposés par C. Reynolds dans son modèle Boids.
- Utiliser l'implémentation d'un algorithme de formation de tas à l'aide des règles simples et locales dans le but d'illustrer comment un comportement complexe (la formation de tas) emerge de l'interaction entre de multiples agents qui ont des comportements simples.
- Mettre en place une application d'optimisation à l'aide d'un algorithme de fourmis.
1. Boids
- Boids de C. Reynold
- Java Floys
- Applet sur les Boids à l'ENST Bretagne (Cours sur sysèmes multi-agents)
2. Formation de tas
a. Copier les fichiers sources java_csort-1.0.tar.gz écrits par S. Wulc. Analyser le code et trouver quelles sont les règles utilisées par ces agents pour former des tas.
b. Exécutez l'applet Java Java sort applet. Quel est le problème avec cet approche ?
c. Utiliser le bouton CLEAR, inserer 20 objetcs bleus et 20 objets rouges, et quelques fourmis (e.g., 6). Qu'est-ce qui se passe avec la performance du système ?
d. Augmentez le nombre de fourmis à 20 et testez la performance du système
e. Augmentez le nombre de forumis à 50 et régardez ce qui se passe...
3. ANT Colony System
a. Copier cette implémentation C d'un algorithme inspiré du comportement de fourmis: Ant Colony System (ACS) appliqué au problème du voyageur de commerce (TSP).b. Identifiez les différentes parties de l'algorithme:
Initialize
Repeat {
Place each ant in a randomly chosen city;
For each ant
Repeat {
Choose NextCity (each ant);
Update pheromone levels using a local rule;
} Until (No more cities to visit);
Return to the initial cities;
Compute the length of the Tour found by each ant;
End For;
Update pheromone level using a global rule;
}
Print Best Path;
8. Exécuter l'exemple pour résoudre le problème du voyageur de commerce (14 villes de Birmanie)
a) gcc -lm -o acs-tsp acs-tsp2003.c
b) ./acs-tsp
c) Le chemin le plus court trouvé à l'aide de cet algorithme est 32.547367. Quelle est la performance du système lorsque vous l'avez exécuté ? Comment améliorer cette performance ?
d) Modifier les paramètres de l'algorithme pour améliorer sa performance pour le problème de 14 villes
- Combien de fourmis utilisez-vous ?
- Quelle est la signification du paramètre rho ?
- Quel est l'effet du paramètre q0 ?
e) Adapter le code pour résoudre le problème de 42 villes de la Suisse (swiss42.zip).
Challenge: The TSP problem of 15,112 cities from Germany was solved in 1998 using a network of 110 processors located at Rice University and at Princeton University. The total computer time used in the computation was 22.6 years, scaled to a Compaq EV6 Alpha processor running at 500 MHz.
SBI 2005-2006