Bonsoir à tous.
Il y a quelque temps, sur un autre fil de ce forum parlant d'intelligence artificielle, j'ai déposé 2 ou 3 fichiers/programmes utilisant un algorithme d'évolution génétique.
Mais après réflexion je me suis rendu compte qu'il n'était pas nécessaire d'utiliser un tel algorithme pour résoudre les problèmes posés. (Sinon juste pour comprendre comment fonctionne cet algorithme).
En effet, la solution de ces problèmes étant connue d'avance, il "suffirait" de la coder directement.
Il me fallait prendre un problème pour lequel il n'existe pas d'algorithme connu à ce jour permettant de trouver la solution exacte.
J'ai donc retenu le "problème du voyageur de commerce".
(Voir Wikipédia pour plus d'informations sur ce problème).
En résumé :
Pour un nombre de lieux X, déterminer un plus court chemin qui passe par chaque lieu une et une seule fois.
J'ai donc codé un programme écrit en HTML et Javascript (sans aucune librairie extérieure) qui, par plusieurs approches, tente de répondre au problème.
- L'approche mode Recherche par Force brute (ou recherche exhaustive) utilise un algorithme testant tous les circuits possibles.
Chaque circuit possible est évalué, si le circuit actuel est meilleur, il est conservé et défini comme étant le meilleur circuit puis on recommence avec le circuit suivant.
Cet algorithme se termine lorsque tous les circuits possibles ont été testés. Il permet de définir, à coup sûr, le meilleur circuit. Mais il peut mettre très,très longtemps pour arriver à son terme.
Compte tenu de "l'explosion" du nombre de circuits possibles en fonction du nombre de lieux, cet algorithme ne fonctionnera dans le fichier que pour 7 lieux au maximum.
- L'approche mode Lieu proche utilise un algorithme glouton par insertion.
Pour chaque lieu, un circuit est construit pas à pas en y insérant de nouveaux lieux.
Le circuit est composé du lieu de départ et celui qui en est le plus proche.
Les étapes suivantes consistent à insérer un lieu supplémentaire dans le circuit de manière optimale, c'est-à-dire qu’elle augmente au minimum la longueur totale du circuit.
Cet algorithme se termine lorsque tous les lieux de départ et les lieux à parcourir ont été testés.
Si l’insertion d'un lieu dans un circuit est optimale et rapide à calculer la solution finale n’est pas nécessairement optimale.
- L'approche mode Algorithme d'évolution génétique.
Les algorithmes génétiques s’inspirent de la théorie de l’évolution des espèces.
Comme dans la vie, les espèces peuvent se reproduire pour créer de nouveaux individus, et leur ADN peut subir des mutations au cours de leur vie. De plus, comme dans la nature, plus un individu est "fort", plus il a de chance de se reproduire.
Les grandes étapes de l'algorithme :
-1- Création au hasard de la population initiale (génération 1).
-2- Evaluation des individus de cette population (calcul des circuits, des meilleurs individus, tri de la population).
-3- Sélection des meilleurs individus et de quelques individus moins bons.
-4- Création des nouveaux individus par croisements des individus sélectionnés.
-5- Mutation de certains de ces nouveaux individus.
-6- Validation de la nouvelle population pour la génération suivante et retour à l'étape 2.
Cet algorithme ne se termine jamais. (Mais les résultats obtenus se stabilisent à un niveau 'acceptables').
Il est impossible de savoir si le circuit sélectionné est le meilleur de tous les circuits possibles.
- L'approche mode Algorithme de colonie de fourmis.
Les algorithmes de colonie de fourmis s’inspirent du comportement d'une colonie de fourmis.
Les fourmis sont capables de sélectionner le plus court chemin pour aller du nid à une source de nourriture grâce au dépôts et au suivi de pistes de marqueurs appelés phéromones.
Les phéromones sont déposées par les fourmis sur leur chemin. les fourmis ont tendance à suivre le chemin le plus marqué.
Les phéromones s'évaporent mais au fil du temps les fourmis choisiront la piste la plus courte entre le nid et la nourriture.
Les grandes étapes de l'algorithme :
-1- Création de la population initiale : Chaque fourmi est déposée sur un lieu du circuit choisi au hasard.
-2- Les fourmis parcourent le circuit en choisissant l'ordre des lieux à parcourir selon la puissance du marquage ou la distance entre les lieux.
-3- Le circuit de chaque fourmi est évalué
-4- La fourmi ayant trouvé le chemin le plus court dépose ses phéromones.
-5- Les fourmis sont repositionnées à leur point de départ et retour à l'étape 2.
Cet algorithme ne se termine jamais. (Mais les résultats obtenus se stabilisent rapidement à un niveau 'acceptables').
Il est impossible de savoir si le circuit sélectionné est le meilleur de tous les circuits possibles.
Le plus difficile pour moi dans ce projet a été de déterminer les meilleures valeurs pour les variables déterminantes pour l'algorithme d'évolution génétique et celui de la colonie de fourmis.
Pour l'algorithme génétique :
- Nombre initial de voyageurs
- Nombre des meilleurs voyageurs à retenir pour la génération suivante
- Probabilité pour qu'un un peu moins bon voyageur soit tout de même retenu pour la génération suivante
- Probabilité de mutation et type de la mutation
Renversement d'une partie de l'ADN
Permutation de 2 gènes
Hasard
Pour l'algorithme de la colonie de fourmis
- Nombre initial de fourmis
- Valeur d'une dose de phéromones et taux d'évaporation
- Valeurs minimum et maximum du marquage pour un chemin entre deux lieux
- Seuils pour le choix des chemins à emprunter
Selon le marquage
Selon la distance
Hasard
Mes différents tests m'ont également montré que pour le problème posé l'algorithme de la colonie de fourmi semble donner les meilleurs résultats en un nombre "raisonnable" d'itérations.
En codant ce programme en Javascript j'ai appris comment trier un tableau, comment trouver des doublons et/ou des manquants dans un tableau, permuter des données, utiliser les index et pleins d'autres choses.
(A noter, je n'ai pas trouvé sur le net de fichier écrit en pur javascript - cad sans librairie spécifique - traitant ce problème).
Je vous laisse tester par vous même si vous le souhaitez.
Voici en pièce joint le fichier livré "en l'état".
Le fichier est limité à 50 lieux maximum ( modifiable ) car au delà de cette limite mon ordinateur ( un peu ancien ) rame sérieusement.
Voili, voilà.
Didier.
Fichier(s) joint(s)
-
_LeCircuit.html 68,54 Ko
108 téléchargement(s)
) à plus de 40h pour faire un pauvre diffie hellman (qui utilise l'équivalent d'un RSA, avec des clefs 1024bits de mémoire).
