|
Laboratoire VIII |
 |
"Il y a une grandeur dans cette vision de la vie." |
Objectifs
Il s'agit d'explorer l'utilisation des algorithmes génétiques pour la résolution de problèmes d'ingénierie.1. Maximisation d'une fonction à l'aide d'un algorithme génétique
Le site GA Archives présente une collection de codes sources d'algorithmes génétiques. On vous propose d'utiliser le code SGA-C (Simple GA en C) Cette version C du code Pascal original, réalisé par le Prof. David E. Goldberg directeur du Illigal Laboratory (Illinois Genetic Algorithm Lab.), permet de résoudre un problème de maximisation.1.1 Code C
1.1.1 Copier les sources de l'application disponible ici.
Le code SGA-C implémente un algorithme génétique
et permet d'utiliser les principes d'évolution artificielle
pour résoudre un problème quelconque. Pour
résoudre un problème, il suffit de coder la
fonction de calcul du fitness et de parametrer l'algorithme
génétique.
Exemple: maximisation d'une fonction
Dans le fichier app.c vous trouvez la fonction objfunc(critter) qui reçoit comme paramètre un individu (critter) et rends la valeur de son fitness.
Pour calculer le fitness d'un individu, il faut décoder la chaîne
de bits pour afin d'y retrouver la solution potentielle.
Dans cet exemple il s'agit de trouver 8 valeurs entiers 1 < xi < 16 qui maximisent la fonction:
f = (x0 * x1 * x2 * x3) / (x4 * x5 * x6 * x7)
La solution de ce problème est facile... en fait, f est maximisée avec les valeurs x0 = x1 = x2 = x3 = 16 et
x4 = x5 = x6 = x7 = 1. Ceci va nous permettre de mieux comprendre
l'utilisation d'un algorithme génétique et
d'illustrer les limitations d'une telle approche.
1.1.2 Analyser le code de la fonction objfunc
1.1.3 Compiler le code C à l'aide de la commande make
1.1.4 Pour parametrer l'algorithme génétique vous pouvez
exécuter sga et ensuite entrer la valeur pour chaque
paramètre démandé: nombre de runs, taille de la
population, taille du genome, affichage des chaînes (y/n), nombre
max. de générations à exécuter,
probabilité de croissement, probabilité de mutation,
random seed.
Vous pouvez également créer un fichier de configuration contenant ces informations.
1.1.5 Exécuter le code à l'aide de la commande ./sga config
1.1.6 Dans cet exemple, chaque entier xi est
codé à l'aide de 4 bits (0000 code la valeur 16). Par
exemple, la chaîne:
1111 1111 0000 1111 1000 1000 1000 1000
code les valeurs x0 = 15, x1 = 15, x2 = 16, x3 = 15, x4 = 1, x5 = 1, x6 = 1, x7 = 1
Analyser la fonction objfunc pour comprendre
comment réaliser ce codage... SGA-C utilise des séquences
d'entiers pour coder de longues chaînes de bits!
1.1.7 Exécutez différents runs en
changeant la taille de la population et les paramètres de
croisement et mutation.
1.2 Code Java
1.2.1 Copier les sources de l'application disponible ici.
Le code Java-galib implémente un algorithme génétique
et permet d'utiliser les principes d'évolution artificielle
pour résoudre un problème quelconque. Pour
résoudre un problème, il suffit de coder la
fonction de calcul du fitness et de parametrer l'algorithme
génétique.
Cette librairie vient avec 5 exemples différents: BinaryOnes, CurveFit, Maze et TrigFunc. Pour compiler le code
utiliser ant et le fichier build.xml fourni ou importer le projet dans un environnement comme Eclipse.
Appeler le code, par exemple, avec ce fichier html. Sur Eclipse, exécuter le code comme un Applet Java.
1.2.2 Etudier les 5 exemples et analyzer comment pourriez vous coder l'exemple de maximisation d'une fonction, cité en 1.1.1
1.2.3 Analyser le code du fichier GASalesman.java que vous trouverez dans les exemples:
GA Exemples/src/com/softtechdesign/ga/exemples/
Vous y trouverez la parametrisation de l'algorithme et l'implémentation de la fonction de fitness.
1.2.4 Exécutez différents runs en changeant la taille de la population et les paramètres de croisement et de mutation.
2. Vers la Programmation Génétique
La Programmation Génétique proposée par John Koza (Stanford) vise l'utilisation d'algorithmes génétiques pour évoluer des programmes informatiques afin de résoudre des problèmes. Le principe de la Programmation Génétique consiste dans le codage d'un programme informatique à l'aide d'arbres (des programmes informatiques écrites à l'aide du langage de programmation LISP peuvent facilement être traduits en arbres).Nous allons évoluer des programmes informatiques afin de résoudre un problème classique: l'ordonancement de données et ceci sans avoir besoin de faire appel à la Programmation Génétique pure et dure.
2.1 Algorithmes d'ordonnancement de données
Pour faire l'ordonnancement de données vous avez certainement étudié les méthodes classiques de tri: tri bulles (bubble sort), tri par insertion, tri par sélection, le tri rapide (Quicksort) et le tri par tas (Heap sort).
Ces algorithmes nécessitent un nombre d'opérations (comparaisons et permutations) différent: par exemple le tri bulles nécessite typiquement l'exécution d'un nombre N^2 d'opérations pour N données à trier, tandis que l'algorithme comme le tri rapide permet de faire le tri de N données à l'aide d'un nombre d'opérations N * log (N), ce qui le rend plus intéressant.
A ce lien vous trouverez le code source de différents algorithmes de tri écrits en Java (voici le lien original http://www.geocities.com/SiliconValley/Network/1854/Sort1.html). Compilez ce code à l'aide de la commande javac SortApplet.java et ouvrez la page Sort1.html pour exécuter l'applet qui illustrant les différents temps d'exécution pour ces algorithmes.
Vous trouverez également d'autres applets illustrant ces algorithmes:
http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
http://maven.smith.edu/~thiebaut/java/sort/demo.html
2.2 "Sorting networks"
Les Sorting networks réalisent également l'ordonnacement de données. La répresentation de ces réseaux se fait graphiquement à l'aide de lignes horizontales via lequelles les données "passent",les lignes verticales impliquent une comparaison entre les données des lignes horizontales et une permutation. La permutation a lieu dans le cas où la valeur de la ligne "en haut" est plus petite que la valeur de la ligne "en bas".
Exemple:
Le but est d'entrer les données à trier à gauche et de réaliser les comparaisons et permutations indiqués par les lignes verticales. Par exemple, la première ligne indique qu'il faut comparer la première et la dernière donnée et de faire une permutation dans le cas où la valeur de la ligne "en haut" est plus petite que la valeur de la ligne "en bas". Ensuite, il faut comparer l'ancienne ou la nouvelle valeur de la première ligne et la donnée de la troisième ligne, etc, etc..
En sortant sur la droite, on devrait retrouver les données triés.
2.3 Programmation d'une solution d'ordonnancement à l'aide d'un algorithme génétique
Il s'agit d'utiliser le code SGA-C ou la librairie Java-galib et d'adapter la fonction objfunc ou le fichier GASalesman.java pour résoudre le problème d'ordonnancement de 5 chiffres à l'aide d'un "sorting network" qui fait 9 comparaisons et permutations.
Si vous utilisez le code C, utiliser une codification binaire de la solution, l'évoluer à l'aide de l'algorithme SGA-C et interpreter la solution en la décrivant à l'aide d'un pseudocode.
Si vous utilisez la librairie Java-GAlib, vous pouvez adapter la classe GASalesman qui hérite de la classe GASequenceList, mais faite attention parce que la classe GASequenceList vous génère une liste des caractères sans répéter des caractères dans la liste. En effet, dans un sorting network on peut avoir besoin de faire plusieurs fois une même comparaison-permutation, donc une solution doit être codée par une séquence de caractères qui peut contenir des caractères répétées.
Pour générer ces séquences il faut hériter de la classe GAString.
Alors, changez:
public class GASalesman extends GASequenceList
par
public class GASalesman extends GAString
Rendre un rapport avec le code de la fonction objfunc ou le fichier
GaSalesman.java bien
commenté, expliquer le codage utilisé et les
résultats obtenus (chaînes de bits et pseudocode) en
indiquant les paramètres utilisés.
Delai: vendredi 22 juin 2007 à 18h00
SBI 2007