Commentaires sur une source : INTELLIGENCE ARTIFICIELLE: ALGO GÉNÉTIQUE, VOYAGEUR DE COMMERCE AVEC QT (TROLLTE

aio13 Messages postés 8 Date d'inscription dimanche 11 avril 2004 Statut Membre Dernière intervention 4 juin 2008
19 déc. 2006 à 21:54

merci...

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
3 juin 2005 à 17:22

De un: c'est bcp plus de 100 solutions par seconde
De deux: les algos génétiques ne trouvent qu'une solution approchée
De trois: le fait que le site propose du contenu scientifique n'en fait pas une source sûre ;)

Mais de fait, l'intérêt d'un algo qui approxime plutôt bien (quand c'est bien configuré et codé) très rapidement est certain.

MacKhdo Messages postés 4 Date d'inscription dimanche 24 avril 2005 Statut Membre Dernière intervention 3 juin 2005
3 juin 2005 à 10:48

pour vous mettre tous d'accord j'ai lu je sai pu ou sur le net mais sur un site de science, donc sur , que le temps pour calculer le trajet du voyageur de commerce sur 40 villes pour un ordi calculant 100 solutions par secondes, par methode classique est de la moitié de l'age de l'univers (2e40 ou un truc comme ca) alors que par les algo genetique ca prend qq minutes voila l'interet, cherhcez avec google ya plein de site super riche sur les algo genetique

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
19 mai 2004 à 16:48

je sais que java utilise un code intermédiaire et qu'il est interprété par la machine virtuelle. Il s'agit de ByteCode ... mais en temps normalle entre ASM et code machine je ne vois pas d'intermédiaire.

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
19 mai 2004 à 14:31

par "niveau inférieur", il faut comprendre "plus proche du langage machine", et pas de qualité moindre, je précise. Tu le sais certainement, mais ça peut prêter à confusion.

À ce titre, le langage C est une merveille: proche de l'assembleur mais assez "haut-niveau" pour en comprendre aisément le fonctionnement et pour pouvoir rapidement créer des applications très complexes.

Question: est-ce qu'il y a un langage plus bas-niveau que l'assembleur? je veux dire, "après" l'ASM, il y a quoi avant le code hexadécimal passé au proco? (ou plutôt les 1 et les 0 ^^)

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
19 mai 2004 à 07:40

Effectivement, tu peux programmer les algo's dans le language de ton choix: C, C++, Java ... voir en assembleur si tu te sens à la hauteur !!! Et si t'es fou pourquoi pas en binaire ;-) ....

L'avantage des languages orientés objets, est que tu peux aisément travailler un projet comme une construction de maison.... Tu mets en place, pas à pas, les briques qui te permettrons d'élaborer l'architecture finale !

Mais à priori, rien ne t'empeche de choisir un language de niveau inférieur.

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
18 mai 2004 à 19:17

tu peux résoudre le problème dans n'importe quel langage. seulement, les langages de POO sont plus élégants (AMHA) pour une implémentation d'un tel algo puisqu'il s'agit d'objets (gènes, villes) qui interagissent.

Le C (langage structurel) doit permettre une gestion du même genre mais je pense que le code source serait moins beau (enfin, moi et l'esthétisme du code, ^_^ sondage: y en a d'autres que moi qui trouvent que certains codes sources sont beaux et d'autres pas? (purement du pt de vue de l'aspect))

pr résumer ma tartine: tu peux programmer ds le langage que tu veux

koubi93 Messages postés 2 Date d'inscription mercredi 28 avril 2004 Statut Membre Dernière intervention 18 mai 2004
18 mai 2004 à 19:10

Est-il possible de résoudre le problème du voyageur de commerce en langage C ? ou est-ce que l'on est obligé de recourir au C++ pour y arriver ?
Si oui, connaissez-vous des sites où la solution est explicitée (code source, méthode,e.t.c...) ; sinon, ya t-il une démarche particulière à prendre pour aborder ce problème ?
-> Quels moyens faut-il utiliser pour arriver à une solution convenable ?
-> Comment traduire les histoires "biologique" en outils informatiques ?
Merci d'avance à tous ceux qui pourront me répondre ;)

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
24 mars 2004 à 01:04

Java est semi-compilé comme tu dis, le code source est traduit en bytecode qui sera interprété par la machine virtuelle... Mais là n'est pas le seul b-mole... En effet, un des gros problème avec java est le garbage colector qui cause des soucis des qu'on fait de la simulation multi-tâche en temps-réel car le temps réel n'en n'est plus un réellement du à la présence de ce fichus garbage colector...

Autrement, oui, nous avons appris COBOL.... C'est bien parceque c'est un language préhistorique que nombreux sont les programme (surtout les anciennes base de données ) qui sont codé dans ce language... D'où l'utilité de l'étudier. Histoire, de ne pas être entièrement dépourvu si nous avons à faire un l'un de ces vieux programme une fois sorti de l'unif...

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
23 mars 2004 à 19:14

en java c qd même semi-compilé, la VM interprète du code déjà traité (à moitié) mais évidemment c'est tjs ça de plus à faire lors de l'exécution et dc c du tps perdu (y a des contre parties qd même).

vs devez coder en COBOL??? mais ça a quel âge ce langage? mon père programmait en cobol! O_o

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
23 mars 2004 à 17:51

En effet... nous dévellopons essentiellement en C(++) ou Java. Principalement car se sont des languages orienté objet, forts proches l'un de l'autre... Donc idéale pour une belle programmation. Deplus, de nombreuses librairies graphique sont disponibles. Il n'y a aucune obligation pour le Printemps des sciences en tout cas... En pratiques, le language sources d'un projets à remettre est parfois imposé: C(++), JAVA mais aussi FORTRAN, COBOL ou bien même ASM (ASSEMBLER)... Personnelement je programme essentiellement en C++ avec les librairies super mega géniales du toner qui tue ... QT !!! ;-) ... L'avantage du C++ face à java est sa rapadité... En effet, le code java est émulé alors que le C++ est compiler entièrement en langage machine.. Un programme dédier en C++ sera toujours plus rapide que son équivalent en Java.

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
23 mars 2004 à 17:31

Salut,

j'en reviens, suis resté jusqu'à ce qu'on m'expulse lol ^^
c'était vraiment bien en effet, j'ai (un petit peu) cherché après toi, mais "gvhecke" c t pas suffisant comme info ;-) (pas vu de béquille lol)

j'ai causé avec les deux gars du jeu de foot (vrmnt une chouette idée en effet) à propos de l'optimalité de l'algo, et de la question: comment savoir si c terminé. il disait comme toi que ce n'était pas possible, mais que si après x générations aucune amélioration remarquable n'était observée on pouvait en conclure que la fin avait été atteinte (une bonne approximation).

j'ai aussi vu le "stand" algo d'apprenteissage par renforcement qui était pas mal, même si j'ai du mal à comprendre pourquoi ça marche (le principe de base est proche du brute force en fait, mais avec une amélioration dans la durée. un truc intéressant qd même: tu peux paramètrer si la "tête chercheuse" veut gagner de l'expérience (explorer l'inconnu) ou assurer la réussite au maximum (càd atteindre un point du labyrinthe)

j'ai qd même vu bcp de projets pas encore terminés ^^ du côté robots etc...

j'ai cru remarquer que les dvp utilisaient soit le C/C++ (C en robotique "évidemment") soit le Java (en fait, ttes les applis visuelles que j'ai vues étaient en java) C'est imposé par l'unif ou c libre?

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
23 mars 2004 à 15:47

Le printemps des sciences à l'ULB... C'était pas mal non ? Ce jeu de foot avec algogénétique, sympa... hein ? Et ces plantes générées par algo génétique ? Et le reste: simulation de trafic spatial, chaîne de montage d'usine en modèle réduit, Intelligence artificielle avec QLearning, etc... Bref, je dois dire que les projets de cette année fut exeptionnellement bien fais... Un petit b-mole toute fois pour le groupe exposant la vie artificielle avec herbivores et carnivores virtuels. Ca ne marchait pas encore quand j'y suis passé.... Mais bon dans l'ensemble c'était plutôt exellent.

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
23 mars 2004 à 08:33

un problème NP est un problème Non Polynomial... Autrement dit, c'est un problème dont la résolution prend un temps exponentiellement long ... Par exemple pour le voyageur de commerce... s'il y a 10 villes le problème prend en moyenne 10! (factorielle de 10) unités de temps pour être résolu... s'il y a 100 villes, le temps de résolution sera de l'ordre de 100! (factorielle de 100) unités de temps... qui est bien plus grand que 10*(10)!

De manière générale, pour N villes, le voyageur de commerce à une complexité de l'ordre de N! = N*(N-1)*(N-2)*N-3)*...*(N-N+2)*(N-N+1)

Quant aux algos fourmis... ce sont des algorithme basés sur le comportement des fourmis. Explication: les fourmis bien que considérées individuellement sont très idiotes, il en est tout différent lorsqu'elles agissent ensemble. Tout ce passe comme si une intelligence collective émergeait du comportement de milliers de fourmis. En fait, les fourmis parte à la recherche de nourriture... et reviennnent en déposant des phéromone (sorte de parfum). Bien qu'au départ, elles vont au hasard... les phéromones laissées par les autres ayant déjà trouvé de la nourriture influence le déplacement de celles qui sont à la recherche d'un peu de bouf et qui a leur tour déposeront des phéromone en revenant à la fourmilière. Comme on peut s'en douter, les route menant droit à la nourriture vont vite se chargées en phéromone. De ce faite les phéromone finissent par dessiner une carte menant à la nourriture. C'est cette idée qu'on utilise dans certains algo où il s'agit de trouver le chemin le plus cours.
pour les fourmis: http://www.rennard.org/alife/french/ants.html

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
22 mars 2004 à 21:21

c'est quoi un problème NP?
parle moi des algos fourmis :-)

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
22 mars 2004 à 18:47

Tu soulève là tout le problème des algorithmes génétique... Les algorithmes génétiques fournisse une solution qui tend vers la meilleurs... Autrement dit, la meilleurs solution proposée par l'algo génétique n'est pas loin de ce que devrait être la meilleurs... Nous ne sommes pas pour autant certains que la solution trouvée est la meilleure existante.
Prq dès lors s'intéresse t on si bien au algo génétique ? Hé bien, car ils sont parmis les meilleurs algorithmes de résolutions pour les problèmes NP par exemple. C'est à dire que là où un algorithme déterministe mettrait un temps super long pour trouver LA meilleure des solutions, l'algo génétique répondra avec une approximation raisonnéblement proche dans un temps bcp plus cours. D'où tout son intéret dans des programmes qui doivent avoir une réponse rapide et raisonnable à un problème difficile. Les développeurs doivent parfois trouver un compromis entre temps et qualité de la réponse... les algo génétique sont une alternative parmis d'autre... Les algos fourmis sont pas mal non-plus pour ca

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
22 mars 2004 à 18:33

de tt ce que j'ai lu, ressort une question. ts les documents décrivent (très bien) le processus de génération, de mutation, de crossing-over, mais aucun des articles que j'ai eu sous les yeux n'indique comment déterminer si telle ou telle solution est bien la meilleure. est-ce qu'on doit déterminer une valeure souhaitée, ou y a-t-il moyen (je suppose pas pr ts les problèmes) de déterminer si la solution est optimale?

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
22 mars 2004 à 18:31

Ce liens correspond aux "workings groups" mais si tu veux des info plus pratique sur les algo génétiques vise plutot http://www.evonet.polytechnique.fr/evoweb/resources/ec_nutshell/index.html

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
22 mars 2004 à 18:25

http://www.evonet.polytechnique.fr/evoweb/working_groups/evogp/index.html

cette partie du site semble down, et forcément c la partie sur la prog génétique :(

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
22 mars 2004 à 18:16

Bonne question, faudra poser le question

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
22 mars 2004 à 18:13

pamis les liens que je vous ait fournis plus haut
http://www.gentic-programma ne mène nulle part préférez plutot http://www.genetic-programming.com/

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
22 mars 2004 à 18:12

pamis les liens que je vous ait fournis plus haut
http://www.gentic-programma ne mène nulle part préférez plutot http://www.genetic-programming.com/

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
22 mars 2004 à 18:10

pamis les liens que je vous ait fournis plus haut
http://www.gentic-programma ne mène nulle part préférez plutot http://www.genetic-programming.com/

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
22 mars 2004 à 18:08

je tenterai de passer ;-) c un des stands que je voulais pas manquer, autant y passer dès mon arrivée.
dis, les profs ns demandent de prendre des notes, tu penses que c'est jouable de demander aux étudiants de m'envoyer leur travail écrit par E-mail?

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
22 mars 2004 à 18:02

Bon ben, je serai au stand info vers 13h30 alors... je serai reconnaissable à la béquille que je trimballe ;-)

Ceci dit, les algos génétiques sont présenter par d'autres étudiants que moi... J'ai malheureusement trop de boulot pour participer aux printemps des sciences.

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
22 mars 2004 à 17:57

bon, ben toujours dans le registres des liens sur les algorithmes génétiques... je vous mets ici les liens qu'on nous avait fourgés à l'unif...
http://www.evonet.polytechnique.fr/
http://www.genetic-programma/ (chercher surtout après Jhon Koza)
http://lancet.mit.edu/ga/
http://www.aic.nrl.navy.mil/galist/
http://www.isgec.org/

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
22 mars 2004 à 17:56

13h10 à 16h il me semble, enfin, moi je compte partir à la fermeture, mais je sais pas encore qd ça termine.

bon rétablissement pr ton orteil :-/

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
22 mars 2004 à 17:45

Je me suis fait une fracture ouverte d'un orteil la semaine passér... de ce fait je ne resterai pas toute la journée à l'unif afin de limiter mes déplacements. D'autre part, j'ai cours de 10à12h ... Cependant, je peux toujours envisager de rester un peu plus tard sur le campus. Vers quelle heure serais tu présents?

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
22 mars 2004 à 17:45

http://www.vieartificielle.com/article/index.php?action=article&id=95

suis en train de le lire, une explication des algos génétiques, bonne lecture à tous ;-)

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
22 mars 2004 à 17:38

En fait les organisme sont trier entre eux selon leur adaptation au problème. Ici un organisme A est mieux adapté qu'un autre organisme B, si la longueur totale du chemin qu'il détermine est plus petit que celui de B... Si le chemin totale de A est < que celui de B on dira que A est meilleur (mieux adapté que B)... Si c'est pas le cas c'est que le chemin de total de B est <= à celui de A. Et de ce fait B serait meilleur que A. Il est clair que < est l'oposé de >= et non de > mais le cas = n'est pas important puisq'il détermine des organismes de solutions équivalentes.

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
22 mars 2004 à 17:06

tiens, y a un truc qui m'étonne dans le code (class Organism:

bool operator<(Organism & A) const;
bool operator>(Organism & A) const {return !((*this) est la négation de <, or si les deux organismes sont égaux, ce n'est pas vrai! puisque < retourne false, or > devrait aussi retourner false, et ça deviendra vrai. il y a une subtilité?

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
22 mars 2004 à 16:57

gvhecke, est-ce que tu seras au printemps des sciences de l'ULB demain? j'y vais avec ma classe et j'ai vu qu'il y a un "stand" algos génétiques, y a une chance que je t'y voies? Sinon dis moi à quel stand tu es (si par chance tu y es) ;-)

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
22 mars 2004 à 16:40

Dans l'algorithme génétiquen, tout est portable à l'exeption de la structure qui stockent les coordonnées des différentes villes... J'ai utilisé un tableau dynamique de QPoint (objet Qt pour les coordonnées cartésiennes d'un point) pour les garder en mémoire mais il suffirait de coder votre propre structure pour que cela fonctionne

PS: Mes études me prennent un temps dingue et j'ai du délaisser le code pour l'instant mais je ne l'oublie pas et j'y apporterai des améliorations d'ici peu (j'espère)

cs_djin Messages postés 3 Date d'inscription jeudi 13 mars 2003 Statut Membre Dernière intervention 22 mars 2004
22 mars 2004 à 16:05

L'algorithme lui même est portable. Par contre, je ne sais pas si le code fait appel à des routines de l'OS, mais je ne pense pas

lpikachu58 Messages postés 351 Date d'inscription samedi 2 février 2002 Statut Membre Dernière intervention 6 mai 2004 2
22 mars 2004 à 13:59

est ce que l'algo genetique seul est portable

garslouche Messages postés 583 Date d'inscription mardi 26 novembre 2002 Statut Membre Dernière intervention 29 mai 2015 1
12 nov. 2003 à 21:24

Euh coco (djin)...
je te rappelle que le problème du voyageur de commerce n'est pas de savoir combien de kilomètres il va devoir parcourir, mais seulement de savoir par où passer pour minimiser son trajet.

Je ne vois pas en quoi :

Ville A -> B : 20km
Ville B-> C : 15km
Ville C->D : 70 km
....

est plus facile à utiliser que la capture d'écran!

En plus le code sépare bien le noyau de l'IHM donc la compréhension de l'algo que ce soit en console ou en graphique est la même!

Après que wxWindows soit une bonne lib je ne le nie absolument pas.

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
12 nov. 2003 à 21:20

Je m'explique quant à mon choix pour Qt...

L'AVANTAGE ULTIME de Qt est de pouvoir JUSTEMENT s'attarder à la partie IMPORTANTE d'un programme sans devoir TROP se SOUCIER de l'interface !

Il serait bien que certains se renseignent sur Qt: www.trolltech.com

Je sais qu'il est particulierement difficile de comprendre le fonctionnement d'un programme s'il se trouve melangé à tout une série d'instructions propres aux fonctions graphiques. C'est donc parce que Qt permet de se concentrer sur l'essentiel que je l'ai choisi afin de developper.

Je ne veux pas, non plus, me faire paraitre pour un adepte pur et dur de linux, mais il s'avère que pour l'open source, c'est l'environnement de travaille idéal... mais il s'agit la d'un choix personnel que je ne veux imposer à personne. Raison de plus pour laquel j'ai choisi l'usage des librairie Qt... puisque portable pour windows !

Quant à ceux qui ont du mal à s'y retrouver dans mon algorithme, je les invite à ouvrir les fichiers "algoGenetique.h" et "algoGenetique.cpp". Je me suis concentrer sur une programmation orienter Objet afin de rendre le code le plus propre possible. La boucle principale est situer dans la classe "AlgoGenetique", il s'agit de la fonction "AlgoGenetique::run()".

J'ai fais de mon mieux et vous assure que les fonctions graphique ne sont pas mélangées avec l'algorithme génétique !!!

Et comme je n'aime pas rester bête, je vais, de mon côté, me renseigner sur wxWindows (merci Djin pour ton avis)

MoDDiB Messages postés 546 Date d'inscription mardi 26 novembre 2002 Statut Membre Dernière intervention 4 mai 2007 1
12 nov. 2003 à 20:12

Meme avis que Djinn : la version console rebuterai moins de monde !!

cs_djin Messages postés 3 Date d'inscription jeudi 13 mars 2003 Statut Membre Dernière intervention 22 mars 2004
12 nov. 2003 à 20:08

doucement mon coco,

je ne dis pas qu'il faut tout recoder avec wx plutôt que Qt, je n'ai jamais codé en Qt. Je souligne seulement l'avantage de wx.

Ensuite, c'est bien joli de faire une représentation graphique des villes parcourure, mais une distance numérique est plus facile à interpréter (même pour un humain) qu'une distance graphique, surtout quand il s'agit de trouver une tournée plus courte entre 40 villes...

Enfin, l'avantage d'un code en console, c'est la lisibilité de l'algorithme, chacun est ainsi capable de l'interpréter (enfin d'essayer..., les algo génétiques ne sont pas évidents) sans se préoccuper des fonctions graphiques qui interviennent en plus.

:) m'enfin, les avis tout le monde en à un, à toi de voir. Merci encore pour le mal que tu te donnes pour mettre au point des algorithme accessibles.

garslouche Messages postés 583 Date d'inscription mardi 26 novembre 2002 Statut Membre Dernière intervention 29 mai 2015 1
12 nov. 2003 à 16:34

pas d'accord!
Le problème du voyageur de commerce a tout intérêt à avoir une visualisation graphique!

Après qu'il développe avec Qt wxWindows ou autre chose ça le regarde. Il ne va quand même pas changer toute son IHM juste pareceque tout le monde n'utilise pas les mêmes classes!

cs_djin Messages postés 3 Date d'inscription jeudi 13 mars 2003 Statut Membre Dernière intervention 22 mars 2004
12 nov. 2003 à 16:08

Si je puis me permettre cher gvhecke, le plus simple, pour que tout le monde puisse profiter de ton exemple d'algorithme génétique, serait de faire une version console sans "fioritures".

L'interface graphique risque de perturber plusieurs personnes (si ce n'est pas déjà le cas...), notamment les utilisateurs Windows.

Enfin, si tu peux un environnement graphique portable, j'apprécie énormément wxWindows. Il est portable mais en plus Open source et gratuit.

Merci et bon travail ! ;-)

Que demande le peuple ?

yakvador Messages postés 13 Date d'inscription mercredi 9 juillet 2003 Statut Membre Dernière intervention 17 janvier 2005
10 nov. 2003 à 21:15

tres tres beaéu programme.!
toute mes felicitations... et merci pour les commentaires, qui n'ont absolument rien d'inutile.!

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
10 nov. 2003 à 12:26

Comme promis, j'ai ajouter des commentaires... j'ai essayer de paraitre aussi clair que possible.

De plus, j'ai modifier le code pour que le pourcentage de mutation puisse etre regler en temps reel en ajustant le slider.

Encore a venir:
=============
Ajout d'un graphe pour montrer la convergeance de l'algorithme

MoDDiB Messages postés 546 Date d'inscription mardi 26 novembre 2002 Statut Membre Dernière intervention 4 mai 2007 1
8 nov. 2003 à 16:06

Kler !! OU alros ca serait sympa que gvhecke nous fasse une version windows ^^ c'est toujours bon a apprendre ^^

zanidip Messages postés 76 Date d'inscription lundi 30 septembre 2002 Statut Membre Dernière intervention 25 mars 2007
8 nov. 2003 à 08:56

zut!
personne n'a les moyens de compiler ca sous windows????

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
8 nov. 2003 à 07:17

Je ne dispose pas des librairies qt pour windows permettant de compiler mon projet pour windows. Je ne peux donc pas vous fournir d'exe pour l'instant. Navré pour les personnes ne disposant pas de linux... :-(

MoDDiB Messages postés 546 Date d'inscription mardi 26 novembre 2002 Statut Membre Dernière intervention 4 mai 2007 1
7 nov. 2003 à 23:47

Dis tu pourrais nous mettre l'exe stp car pas moyen de compiler a cause de qt qui est payant pour windows :(

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
7 nov. 2003 à 23:18

on dit pas crossing-over? comme pr la division cellulaire lors de la reproduction? (responsable de la diversité dans une même race)

Oui, Werber m'en a appris pas mal sur les fourmis ;-)

je te souhaite dors et déjà u ngrand succès pour ce programme, je ne manquerai pas de venir le commenter, ;-)

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
7 nov. 2003 à 22:20

Bien, je vais essayer de répondre à tous.

Effectivement la puissance des algos génétiques est telle qu'ils permettent de répondre, avec le plus de justesse possible, à des problèmes auquel les algorithmes déterministes (back-tracking) mettraient un temps inecceptable. Ils s'avèrent fort utiles pour toute une série de problèmes combinatoire, NP-complet.

Quant à garslouche, tu veux certainement parler de la technique de cross-over (croisement en français). C'est à dire qu'à partir de deux individus parents, on crée un individu enfant. Il existe plusieur manière de croisé des organismes. Pour ma part je l'ai implémenter dans l'opérateur *. Organism::operator*(const Organism& A). Le taux de mutation est reglé par l'un des deux sliders (visible sur le screenshot). Lorsqu'on bouge le slider en question, cela met à jour une variable volatile nommée _mutationRate et qui est utilisé par mon algo.

Il est vrai que j'ai homis de commenter mon code. Je vais directement m'attarder aux commentaires pour remédier à cet oubli.

Pour répondre à Kirua, je fais mes études à la Faculté des sciences de l'ULB. J'ai toujours été intéressé par l'intelligence Artificielle et c'est pourquoi j'ai choisi de suivre ce cours cette année. Nous disposons à l'ULB d'un laboratoir spécialisé dans ce domaine, le labo IRIDIA. L'un de ses chercheurs, le professeur Dorigo, vient d'ailleurs de recevoir le Prix Marie Currie pour ses travaux sur les algorithmes fourmis. C'était il y a tout juste 2 jours...Cependant, cet algorithme génétique ne fait pas partie de mes études, il s'agit plutôt d'un développement "loisir" que je me suis fait.

Prochainement, pour mon cours d'intelligence artificielle, je ferai un algo fourmis. Une simulation de fourmilière, afin de faire paraitre l'émergeance d'une mémoire collective. La mémoire collective est mis en place par l'usage de phéromones que les fourmis dépose en se déplacant. Après un certain temps, il finit par se tracer des routes (des plus courts chemins) vers les points de nourriture.

A bientôt

MoDDiB Messages postés 546 Date d'inscription mardi 26 novembre 2002 Statut Membre Dernière intervention 4 mai 2007 1
7 nov. 2003 à 16:31

Kirua c'est simple j'ai vu que pour le meme voyage avec 40 villes il faudrait 1x10^19 année pour resoudre le probleme !!d'ou la puissance d'un algo génétique qui le fais en quelque secondes ^^
Il n'aura pas la meilleure solution mais il tends vers la meilleure : comme un etre humain !!

zanidip Messages postés 76 Date d'inscription lundi 30 septembre 2002 Statut Membre Dernière intervention 25 mars 2007
7 nov. 2003 à 13:15

tres bon code je trouve! j'avait deja essayé de faire un algo genetique mais le resultat n'etait pas tres convaincant.

sinon puisque ta source utilise des librairies pas courantes un exe dans le zip serait le bienvenu.....

bonne prog et un exe please!

garslouche Messages postés 583 Date d'inscription mardi 26 novembre 2002 Statut Membre Dernière intervention 29 mai 2015 1
7 nov. 2003 à 09:54

Ca fait qq temps que je n'y ai plus touché mais pour autant que je me souvienne les algo génétiques utilisent davantage de notions normalement. Ici tu n'utilises que les mutations, mais il y avait une histroire de cross-bidule et de je ne sais quoi encore. Il me semble qu'il y a avait 3 types d' <<erreurs>> possibles. De plus je ne vois pas le taux de mutation ds ton prog.
Sinon je trouve ça un peu bizarre que le mutations ne soient pas utilisées pendant la "procréation" (càd dans l'opérateur *)

Sinon j'ai pas pu testé bicoz j'ai pas un linux sous la main mais d'après la capture d'écran ça a l'air assez efficace.

Sinon pour Kirua : la force brute est toujours la + mauvaise solution!!! (sauf pour trouver un mot de passe....). Et même si dans un cas particulier ça marche mieux (par exemple quand il y a peu de villes à traverser) il ne faut pas en tenir compte car la vitesse des algos se calcule généralement dans le cas des très grand ensembles.

Sinon c'est bien codé mais pas assez commenté...8/10

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
7 nov. 2003 à 07:57

salut gvhecke, t'es en quelle faculté à l'ULB ? j'habite à bruxelles aussi, j'irai probablement là ou à l'UCL dans 2 ans (suis en 5ème là). J'envisageais la FSA (Faculté des Sciences Appliquées), mais dans quel cadre tu as eu à coder ceci? C'est par intérêt personnel, ou tlm doit faire ça ?

pour qt, j'y penserai... quant mon réseau fonctionnera ss linux!!! là suis sous XP.

bravo pr ton code, mais as-tu vérifié l'efficacité par rapport à un "algo" de brut force? ça m'a l'air qd meme fichtrement compliqué ton machin.

gvhecke Messages postés 65 Date d'inscription vendredi 17 octobre 2003 Statut Membre Dernière intervention 21 mai 2008
6 nov. 2003 à 22:22

Dans le cadre de mes études (à l'Université Libre de Bruxelles) je développe essentiellement en c++ sous linux et avec les librairies qt.

Il s'agit de librairies entierement gratuites et disponible avec la majeure partie des distribution Linux. Ce qu'il y a de particulièrement génial lorsqu'on développe avec qt... c'est que le code devient entierement portable pour windows (et mac os x je pense). Le seul b-mole, c'est que les librairies qt pour windows sont payantes :-< . Mais sinon, c'est portable et sans changer une ligne d'instruction !!!! Super non ?

De plus, il existe, sous linux, un outils de conception d'interface graphique appelé "Qt designer" et gratuit également!... Je vous dit pas le gain de temps quand on développe avec qt !!!

Depuis que je l'ai tester, je suis devenu pro-qt... A vous de voir à présent !

MoDDiB Messages postés 546 Date d'inscription mardi 26 novembre 2002 Statut Membre Dernière intervention 4 mai 2007 1
6 nov. 2003 à 18:02

Merci merci bcoup c'est ce que je cherchais pour mon tpe ^^
Mais c'est quoi cette librairie? Enfin bon je v voir et je rale si ca va pas ^^

INTELLIGENCE ARTIFICIELLE: ALGO GÉNÉTIQUE, VOYAGEUR DE COMMERCE AVEC QT (TROLLTE

Votre réponse

Discussions similaires