Aller au contenu


Photo
- - - - -

Le problème du voyageur de commerce ( Javascript )


11 réponses à ce sujet

#1 Didier

Didier

    Nouveau membre

  • Membres
  • 22 messages

Posté 15 mai 2018 - 09:29

 
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)



#2 ashira

ashira

    Pilier du forum

  • Modérateur
  • PipPipPipPipPip
  • 1 264 messages
  • Gender:Male

Posté 15 mai 2018 - 09:59

Salut!

 

Pas mal ce sujet, je trouve ça super intéressant.

 

On retrouve aussi des algos détaillés dans ce poste

 

Effectivement l'algo des fourmis fonctionne mieux que celui de l'évolution génétique :)



#3 Path

Path

    Made By Humans

  • Modérateur
  • PipPipPipPipPip
  • 2 260 messages
  • Gender:Male
  • Location:Paris

Posté 15 mai 2018 - 10:17

Rhoo j'adorais faire ça quand j'étais plus jeune. :) Il faut savoir faire tout ça ^^
Maintenant, j'avoue, je suis flemmard. J'utilise ces lib pour aller plus vite. Si ça te fait envie.

http://underscorejs.org
https://lodash.com
https://caolan.github.io/async/

Podcast Made By Humans

Je cherche des volontaires de tous niveaux pour nos petites conversations entre hobbyistes.

Accès aux salles secrètes

 


#4 Didier

Didier

    Nouveau membre

  • Membres
  • 22 messages

Posté 16 mai 2018 - 07:50

Bonjour.

 

Merci pour les liens.

 

En fait j'ai codé le programme sans librairie externe car je voulais bien comprendre le mécanisme de ces algorithmes.

 

Didier.



#5 cocothebo

cocothebo

    Habitué

  • Membres
  • PipPip
  • 293 messages
  • Gender:Male

Posté 16 mai 2018 - 10:49

Bonjour,

 

Sympa le sujet t intéressant.

 

Une petite remarque en passant:

 

Il me fallait prendre un problème pour lequel il n'existe pas d'algorithme connu à ce jour permettant de trouver la solution exacte.

C'est pas vraiment vrai ;)

 

/* mode ressort ses cours d'algorithmique et complexité */

 

Cette classe de problème est appelée NP-complet, et on pense (mais personne ne l'a démontré jusqu'à présent) que ce types de problèmes n'a pas de solution qui fonctionne en temps polynomial, ie on ne connait pas à l'heure actuelle un algorithme en temps polynomial pour résoudre ce problème. 

C'est une bien grande phrase pour dire qu'en gros plus on augmente les variables d'entrées du pb et plus la complexité augmente vite (pas en temps polynomial, ie pas avec une relation du type y = x^qqc + ....)

 

Le truc "marrant" c'est que si un jour, qqu trouve un algo en temps polynomial pour un seul de ces problèmes (le voyageur de commerce, le sac à dos, ...), alors tous ces problèmes NP-complets ont une solution en temps polynomial. Bref c'est le saint graal des chercheurs sur la complexité et algorithmique xD

 

Bref ça veut dire que souvent c'est problèmes qui sont facilement calculables pour une entrée pas trop grosse, dans ton cas avec pas trop de villes à visiter (mettons maxi 7 sur ton PC), mais le temps explose si on passe de 6 à 7 et après de 7 à 8 etc.

En reprenant le voyageur de commerce, le nombre de chemins à explorer est (en fonction de n, n étant le nombre de ville): 

1/2 (n-1)!

(avec ! étant la factorielle)

ce qui nous donne pour n:

3 => 1

4 => 3

5 => 12

6 => 60                         

7 => 360                       

8 => 2 520

10 => 181 440             

20 => 6,082 e16          

30 => 4,421 e30          

50 => 3,041 e62           

75 => 1,240 e109

 

 

Bref on voit bien que ça grimpte vite...

 

Pour mieux situer, si un calcul prend mettons 1ns (1 milliardieme de seconde), pour 3 villes, la résolution prendra 1ns, pour 4, 3ns. 

Mais pour 10 ce sera déjà 181 440 ns, soit  environ 181 µs

pour 20 ce sera 6,082 e16 ns soit presque 61 milliards de secondes, ce qui est environ 46 ans...

pour 24, on approche l'âge de l'univers (ici plus de 9 milliards d'années)

pour 25, on dépasse et de beaucoup l'âge de l'univers (plus de 230 milliards d'années)

 

Bref même avec une puissance de calcul très (très très...) élevée, vouloir faire toutes les combinaisons de du problème du voyageur de commerce avec plus de 23 villes reste techniquement très très difficile voir impossible.

 

 

Edit: Par conte attention, ce que j'ai mis au dessus est valable si on veut vérifier tout et avoir l'ensembles des solutions, sur ce pb il me semble qu'il faille le faire puisqu'on ne connait pas la meilleure solution à atteindre (la longueur du chemin optimal), par contre pour certains problèmes du même type (donc NP complets) on connait la valeur optimum à trouver et la si c'est juste de l'optimisation, une seule solution est nécessaire ce qui peut réduire énormément les temps de calcul.



#6 Didier

Didier

    Nouveau membre

  • Membres
  • 22 messages

Posté 16 mai 2018 - 01:29

Bonjour.

 

Ces explications sont très claires, merci.

 

j'aurais donc plutôt dû écrire :

 

Il me fallait prendre un problème pour lequel il n'existe pas d'algorithme connu à ce jour permettant de trouver la solution exacte dans un délai raisonnable.

 

Ceci dit, je me demandais dans qu'elle mesure on pouvait utiliser ce genre d'algorithme pour faire apprendre à un robot à marcher...

Exemple pour un quadrupède : Apprendre à se mettre debout, avancer, tourner > Calcul des angles de chaque articulation, timing des mouvements, ...

 

Didier.

 



#7 cocothebo

cocothebo

    Habitué

  • Membres
  • PipPip
  • 293 messages
  • Gender:Male

Posté 16 mai 2018 - 03:02

Oui mais bon c'était un peu pour chipoter, parce que c'est ce que tu avais dit un peu après en disant que la méthode "brute force" permet de trouver la solution optimale. 

 

Et un point aussi, même un programme de complexité de temps polynomial peut être très très couteux en temps, si le nombre de variables d'entrée est élevé, ou si le polynome impliqué est très élevé (xbcp, genre x500) mais je connais pas d'algo polynomiaux ayant une complexité aussi élevée, après même un algo en o(n3) peut couter déjà très cher.

 

Je me souviens avoir fait des essais d'implémentation de calculs RSA sur une carte à puce (en Java Card), de mémoire nous avions implémenter cela avec une complexité en O(n3), c'est à dire que le temps était fonction du cube de la taille de l'entrée (et des patates mais avec une taille suffisament grande c'est le premier facteur du polynome qui est significatif).

Ben déjà la c'était beaucoup mais beaucoup trop mal optimisé (je sais pas si on pouvait faire beaucoup mieux, j'en suis pas sur) pour être exploitable même sur des clés de "petite" taille (par exemple 1024 bits), on avait des durées de calcul (estimées, on s'est pas amusé à tuer une carte pour ça :P) à plus de 40h pour faire un pauvre diffie hellman (qui utilise l'équivalent d'un RSA, avec des clefs 1024bits de mémoire).

 

Bien sur c'est parce que dans notre cas une carte à puce est beaucoup beaucoup moins puissante qu'un PC, sur PC, cela ne prend même pas une seconde.

 

 

Pour apprendre à marcher, un algo génétique fonctionne, ya des vidéos sur YT (de mémoire) du résultat. pour le reste je sais pas si on peut appliquer.



#8 Didier

Didier

    Nouveau membre

  • Membres
  • 22 messages

Posté 16 mai 2018 - 03:45

Re

 

Euh... Comment dire. Là je suis largué.

 

Complexité en O(n3), RSA, diffie hellman : Késako ?

 

Pour la marche d'un robot, je vais regarder à cela. ( Juste qu'il me faudra trouver un quadrupède pas trop cher ).

 

Didier.



#9 Mike118

Mike118

    Staff Robot Maker

  • Administrateur
  • PipPipPipPipPip
  • 7 254 messages
  • Gender:Male
  • Location:Cholet
  • Interests:Robotique, Entrepreneuriat, Innovation, Programmation, Résolution de problème, Recherche de solutions, Mécanique, Electronique, Créer, Concevoir

Posté 16 mai 2018 - 04:48

Il y a l'ouvrage de Nulentout qui décrit son expérience avec un petit quadrupède

 

et là la présentation faites par jekert  avec le même quadrupède.

 

sur la boutique tu as tout ce qu'il te faut pour réaliser le petit quadrupède de l'ouvrage : 

Kit mécanique

Servo 9g   *12
driver pour servo 

arduino nano 

convertisseur 5V7A 
Interrupteur On Off 
paire de cosse pour interrupteur  ( 0,30€)

gaine thermo retractable 5mm
Câble 
connecteur XT60 

Batterie lipo 2S  ( 10,80€ )

Chargeur de lipo 
Alarme pour batterie 

 

Tout est dispo en stock mais tout n'a pas encore été ajouté en fiche produit =)

(  lipo 2S conseillé car plus léger que 3s et suffisant ;) )


Si mon commentaire vous a plus laissez nous un avis  !  :thank_you:

Nouveau sur Robot Maker ? 

Jetez un oeil aux blogs, aux tutoriels, aux ouvrages, au robotscope  aux articles,  à la boutique  et aux différents services disponible !

 

Les réalisations de Mike118  

 

 

 


#10 Didier

Didier

    Nouveau membre

  • Membres
  • 22 messages

Posté 16 mai 2018 - 09:26

Re

 

Merci pour la nomenclature. La structure permettrait-elle de supporter un Raspi 3B ?

 

J'ai, rapidement, parcouru les liens concernant le quadrupède de Jekert...

 

Whaouu, bravo à lui. Je suis à des lieues de ce niveau ( et pas besoin d'un algo pour en calculer la distance exacte ).

 

Jusqu'à présent j'avais fait KRT1 ( un robot roulant ) mais contrairement à certain robot qui cherchent à grimper des escaliers

ce crétin à réussi à les descendre tout seul et très rapidement. Résultat des courses il est HS.

 

Didier.



#11 Mike118

Mike118

    Staff Robot Maker

  • Administrateur
  • PipPipPipPipPip
  • 7 254 messages
  • Gender:Male
  • Location:Cholet
  • Interests:Robotique, Entrepreneuriat, Innovation, Programmation, Résolution de problème, Recherche de solutions, Mécanique, Electronique, Créer, Concevoir

Posté 16 mai 2018 - 10:58

Je pense qu'en terme de poids ça devrait passer, mais en terme de dimension le quadrupède me paraît un peu petit...

ça pourrait peut être se monter avec quelques adaptation mécanique à imaginer ( de base c'est pas prévu de monter un Pi dessus) et il ressemblerait à une grosse tortue je pense... x)

 

Je suis curieux d'avoir les avis de Jekert et Nulentout sur le sujet.

Après sinon tu peux faire un quadrupède avec de MG995 ... On peut imprimer un châssis en 3D ... 
Pas mal de choses peuvent se faire ... 


 


Si mon commentaire vous a plus laissez nous un avis  !  :thank_you:

Nouveau sur Robot Maker ? 

Jetez un oeil aux blogs, aux tutoriels, aux ouvrages, au robotscope  aux articles,  à la boutique  et aux différents services disponible !

 

Les réalisations de Mike118  

 

 

 


#12 cocothebo

cocothebo

    Habitué

  • Membres
  • PipPip
  • 293 messages
  • Gender:Male

Posté 17 mai 2018 - 08:15

C'est vrai que les livres de Nulentout (qui porte donc mal son nom) sont vraiment superbes.

 

Pour le reste (RSA, DH), c'était complétement hors sujet (RSA est un algorithme de cryptographie pour (dé)chiffrer des données, Diffie Hellman un algo pour se trnamettre des clefs secretes), juste pour illustrer le fait que même avec un problème qui ne soit pas si "compliuqé" suivant le cas d'usage c'est déjà trop.

O(n3), ça veut dire que le temps d'execution de l'algorithme est fonction du cube de son entrée, et mine de rien même au cube ça grimpe très vite :).

 

Bref j'arrête le hors sujet et je réittère mes félicitations pour tes recherches et leurs implémentations en JS, c'est super de partager ce genre de choses, surotu avec les explications fournies.





Répondre à ce sujet



  


0 utilisateur(s) li(sen)t ce sujet

0 members, 0 guests, 0 anonymous users