Pour ce
chapitre je vais de nouveau repartir du livre de Virginie MATHIVET
« L’Intelligence Artificielle pour les développeurs » en suivant le chapitre sur les algorithmes de
méta heuristiques d’optimisation écrit pour le langage Java.
Les
algorithmes développés dans ce chapitre sont : l’algorithme glouton, la
descente de gradient, la recherche taboue, le recuit simulé et l’optimisation
par essaims particulaires. Pour la théorie, je vous laisse aller voir le livre
ci-dessus ou wikipedia ou d’autres sites sur internet. Dans le livre,
l 'application de ces algorithmes s’effectue sur le célèbre problème du sac
à dos, qui consiste à remplir un sac à dos de 20kg avec diverses boites de
poids différents et d’optimiser la valeur totale du contenu.
Dans notre
programme sacados64.s, nous allons cette fois ci, utiliser les listes chainées
pour générer les diverses solutions.
J’ai essayé
dans ce programme, d’améliorer l’utilisation des registres en respectant la
norme préconisée. Mais il reste encore des points à revoir !!
Au début du
programme nous décrivons 2 structures, une pour les boites et une pour la liste
chainée de chaque solution. La structure boite contient le pointeur vers le nom
de la boite, le poids et sa valeur. La liste chainée contient ses 3 éléments
plus un pointeur sur le nœud suivant et un ratio égal à la valeur divisée par
le poids. Pour éviter des calculs en virgule flottante ce ratio est calculé en
multipliant en premier la valeur par 100. La liste chainée possède un nœud
d’entête qui contiendra la somme de tous les poids des nœuds de la chaine, la
valeur totale et le nombre de nœuds (ce dernier utilise la place du pointeur
nom de la boite puisqu’il est inutile au niveau de l’entête).
La
description des boites possibles est effectuée dans une table dont la
modification est plus aisée. La création du problème consistera à transformer
cette table en une liste chainée de toutes les boites disponibles, liste qui
sera exploitée par tous les algorithmes.
Au niveau du code, nous retrouvons les routines vues au chapitre sur les
listes chainées : creerNoeud, insererNoeud, supprimerNoeud, et triListe.
Cette
dernière effectue un tri sur le ratio et en ordre inverse, la boite au plus
fort ratio est triée en premier.
Nous
rajoutons à ces fonctions, des fonctions de copie de liste, de copie de nœuds
et les fonctions spécifiques à certains algorithmes.
Tout en
respectant la logique des algorithmes tels que décrit dans le livre, J’ai
simplifié certains calculs. Par exemple pour le recuit simulé il faut calculer
une exponentielle pour déterminer la probabilité de maintenir une solution
moins bonne. Après avoir fait des simulations avec Excel, et si je n’ai pas
fait erreur le simple fait de diminuer la température de 1 à partir de 50
convenait parfaitement. Bien sûr si vous voulez utiliser cet algorithme pour
d’autres types de problème, il faudra l’adapter pour que le calcul soit
réaliste !!
Après de
nombreux tests, le programme semble fonctionner correctement du moins avec les
valeurs données dans le livre. Mais j’ai dû modifier le générateur de nombres
aléatoires qui figure dans les routines asm64 car pour de petites valeurs il
ne semble pas aléatoire du tout. J’ai donc utilisé une possibilité du système
d 'exploitation qui fournit un appel system (urandom). Celui-ci fournit
une suite de nombres aléatoires de la longueur que l’on désire. Mais avec l’inconvénient que les tirages sont différents à chaque lancement.
Voici un
exemple de résultat :
SolutionEssaims
Valeur
totale = 54 poids total = 19 nb de boites : 5
Liste des
boites :
I ==>
poids = 5 valeur = 12 ratio = 240
A ==>
poids = 4 valeur = 15 ratio = 375
L ==>
poids = 3 valeur = 7 ratio = 233
D ==>
poids = 3 valeur = 10 ratio = 333
K ==>
poids = 4 valeur = 10 ratio = 250
Remarque :
si on supprime la dernière boite de la liste des boites disponibles (L) l’algorithme glouton ne trouve pas la
bonne solution !!
Aucun commentaire:
Enregistrer un commentaire