Intelligence artificielle: algo génétique, voyageur de commerce avec qt (trolltech)

Soyez le premier à donner votre avis sur cette source.

Vue 26 543 fois - Téléchargée 2 955 fois

Description

La théorie de l'évolution de Darwin appliquée à l'informatique:
Cette application développé avec les librairie qt de chez trolltech (www.trolltech.com) est un exemple d'utilisation des algorithmes génétiques.

Le problème du voyageur de commerce est un problème NP-complet qui consiste à déterminer l'itinéraire le plus court pour joindre N villes. La résolution de ce type de problème prend un temps qui croît de manière exponentielle avec le nombre de ville.

A partir d'une population initiale d'organisme. On sélectionne ceux qui sont les mieux adapté aux problème. C'est dire tel que les itinéraires codés sur leur ADN sont les plus courts parmis l'ensemble des individus. Ils sont ensuite croisés entre eux afin de créer la nouvelle génération. Les organismes enfants sont ensuite sélectionnés en fonction de leur adaptation au problème ... on les recroise entre eux ... etc ... etc. On fini par évoluer vers la meilleur solution.

Conclusion :


Compiler avec les librairies qt-3.0.3-11 ou supérieur. www.trolltech.com

Mises à jour à venir:
===============
Pour l'instant l'algorithme de base fonctionne... Mais je dois encore travailler dessus pour regler en temps réel les paramètres tel que le nombre d'organismes par population et le pourcentage de mutation. Même si les sliders sont déjà prévu, je n'ai pas encore codé cela réellement ou du moins convenablement. Un peu de patience

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

MoDDiB
Messages postés
546
Date d'inscription
mardi 26 novembre 2002
Statut
Membre
Dernière intervention
4 mai 2007
1 -
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 ^^
gvhecke
Messages postés
65
Date d'inscription
vendredi 17 octobre 2003
Statut
Membre
Dernière intervention
21 mai 2008
-
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 !
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
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.
garslouche
Messages postés
584
Date d'inscription
mardi 26 novembre 2002
Statut
Membre
Dernière intervention
29 mai 2015
-
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
zanidip
Messages postés
76
Date d'inscription
lundi 30 septembre 2002
Statut
Membre
Dernière intervention
25 mars 2007
-
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!

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.