Mon premier projet dans l'univers de l'algorithme génétique portera sur un sujet largement connu du grand public, il sagi du problème du voyageur du commerce.
Mon but est de découvrir à travers ce problème, comment fonctionne les algorithmes génétique (AG), pour une utilisation plus complexe dans une application plus complexe.
Au finale, l'application devra être capable de résoudre dans un temps moyen, un chemin optimale pour 200 villes.
j'ai commencer à implémenter une solution que je vais mettre en ligne.
-----------------------------------------------------------
Version 0.5 de mon projet (Version Actuel en ligne)
-----------------------------------------------------------
Caractéristiques de l'AG actuel :
Nb de villes Max : [20,30]
Crossover : 2 ( simple et double)
Évaluation de la Population : Simple tri.
Méthode de réinsertion : garde 10 meilleurs, remplace le reste.
Donc, pour le moment l'AG n'est pas super.. et demande encore pas mal
de modification avant de pouvoir résoudre des gros trajet.
je rencontre pas mal de difficulté a sortir des maximums local, ce qui à
pour effet de converger trop vite vers une solutions local, je pense que c'est ce qui bloque le plus l'AG pour le moment.
Voici les points que je vais travailler :
- Amélioré la population initiale.
En effet, pour le, moment ma populations initiale est construire aléatoirement,
hors il existe quelques méthode qui permet de rendre la population initial plus performante, tel que de partir d'une ville et de rechercher toujours la ville la plus proche.
- Amélioration de la selection :
Encore une fois, ici plusieurs méthode existe, il semblerai que la roue de la fortune soit meilleurs que les autres. l'interet de la roue de la fortune est de pas enlever totalement les individus qui on un mauvais fitness.
- Amélioration du croisement :
Après les deux méthodes que j'ai implémenter, on peut mettre aussi en place la méthode "Bestof2" qui consiste à sélectionner les meilleurs gènes des deux parents pour former le fils. A voir si c'est applicable dans notre cas.
- Mise en Place de Populations en Threading.
j'ai vue ça il y as pas longtemps sur un site, on fait évoluer plusieurs populations en mêmes temps sur le même problème, puis au bout d'un nombres n de génération on regroupe les meilleurs des sous populations dans une populations finale que l'on fait évoluer a son tour.
Voila déjà, ça fait pas mal de chose a revoir et à implémenter.
Bien sur il faut aussi que je commente mon code, et que je le débeug en parallèle..
Si vous voulez apporté votre aide, surtout pour des idées qui pourait améliorer mon projet, n'hésier pas à en parler ici !
__________________________
