|
|
Elite Troups
-= Chaos Elite Troops =-
Inscription le 06-07-02
Messages : 1574
 Age : 42 ans
Lieu de résidence : Sur la Frontiere
|
|
|
|
|
Réponse au Sujet 'algorithmes génétiques' a été posté le : 15/01/09 16:28
|
Pour l'évaluation de la valeur de tes solutions, il n'y a pas de solution miracle, c'est à toi de voir en fonction de tes attentes.
Pour le codage des solutions, tu peux utiliser tout bêtement un vecteur qui contient les numéros des villes dans l'ordre dans lequel tu te proposes de les visiter.
Ça te fait une taille linéaire, c'est pas la mort.
Si je me rappelle bien, une approche qui ne fonctionne pas trop mal dans le cas du voyageur de commerce, c'est de prendre trois villes consécutives sur ton trajet et modifier leur ordre.
Ton algorithme ressemblerait à :
1/ Génération de la population initiale
2/ Sélection des spécimens les plus intéressants en utilisant la fonction d'évaluation
3/ Suppression de la partie inintéressante de la population
4/ Génération des nouvelles solutions
5/ Goto 2
Le point 1 est important, il faut que la population de base couvre une large partie des possibilités de combinaisons. Il y a des méthodes pour générer ça correctement, mais je ne me souviens plus (le carré latin je crois).
Les points 2 et 3 c'est, dans le cas du voyageur de commerce, la longueur du chemin. Mais pas forcément juste ça. Le problème si on dégage direct les solutions les moins bonnes, c'est de se retrouver avec un optimum local dont on n'est plus capable de sortir par reproduction ou mutation. Une méthode possible pour éviter cette situation est de conserver une fraction des mauvaises solutions malgré tout, ça permet de diversifier ton bassin génétique.
Le point 4 pourrait être la mutation telle que la permutation de trois villes consécutives. Ou bien on peut utiliser la reproduction "sexuée" mais dans le cas du voyageur de commerce, c'est un peu chiant puisqu'il faut vérifier si on ne se retrouve pas avec plusieurs fois la même ville dans sa solution. Ou alors il faut utiliser une méthode qui le garantit direct.
Si tu décides d'opter pour la reproduction sexuée, une solution possible pour régler le problème de l'accouplement est d'autoriser les meilleures solutions à se reproduire plusieurs fois (c'est applicable aussi à la mutation en fait)
Enfin, il faut décider quand s'arrêter, et ça aussi c'est sujet à discussion. Une bonne façon c'est de calculer la moyenne des solutions et lorsque celle-ci n'évolue plus, on peut supposer que l'algorithme a atteint l'optimum.
Un truc avec les algorithmes génétiques, c'est qu'il ne faut pas se laisser enfermer dans une vision trop biologique de la chose. Par exemple, à mon avis, considérer le codage binaire des solutions dans le cas du voyageur de commerce, ça ne sert à rien, parce que la contrainte "toutes les villes sur le chemin doivent être différentes" obligera à faire une vérification de la solution après mutation ou reproduction pour vérifier qu'elle reste valide.
Les algorithmes génétiques c'est un cadre super général au sein duquel toutes les étapes sont sujettes à discussion en fonction du problème auquel tu t'attaques.
Il n'y a pas de méthode universellement bonnes.
Pour le voyageur de commerce, c'est sur que tu trouveras une documentation très volumineuse sur le sujet, avec des dizaines d'approches différentes.
|
|
|
|
 Cachée
|
|
|
Elite Troups
-= Chaos Elite Troops =-
Inscription le 06-07-02
Messages : 1574
Age : 42 ans
Lieu de résidence : Sur la Frontiere
|
|
|
|
|
|
Réponse au Sujet 'algorithmes génétiques' a été posté le : 15/01/09 21:35
|
Effectivement, la roue permet ce genre de comportements. Mais tu n'es pas à l'abri d'un coup qui te dégagerait tous les mauvais.
Un algo génétique c'est pratique quand tu n'as aucune idée de la forme de la solution optimale et que, par conséquent, tu n'arrives pas à trouver des heuristiques efficaces pour accélérer le traitement de ton problème.
Il y a quelques applications amusantes, la plus célèbre c'est la reproduction du déplacement de certains animaux. Mais j'ai aussi vu des algorithmes génétiques qui créent des images, des sons et où la sélection se fait en demandant à des humains quels images ou sons ils ont préféré.
Ce que personnellement je n'aime pas avec ce type d'algos, c'est que tu obtiens des résultats expérimentaux sujets à interprétation. Il n'est pas facile de dire pourquoi telles règles de sélection permettent d'obtenir de bons résultats, pourquoi telle mutation permet d'approcher rapidement la meilleure solution, etc.
Du coup, on se ramasse avec un algorithme qui est fait sur mesure pour un problème précis et on ne peut pas généraliser.
Ça a un côté bricolage un peu agaçant.
Finalement, on ne peut pas employer un algorithme génétique pour traiter un problème qui exige une solution exacte.
Petit rajout tout mignon : les algorithmes génétiques sont fort probablement sans intérêt pour traiter un problème qui peut se résoudre en temps polynomial.
|
|
Dernière mise à jour par : Jormugaund le 15/01/09 22:35
|
|
|
|
|
|
Cachée
|
|
Pal pas triste
-= Chaos Elite Troops =-
Inscription le 12-07-04
Messages : 3384
Age : 54 ans
Lieu de résidence : 20e Nuit Lutècienne
|
|
|
|
|
Réponse au Sujet 'algorithmes génétiques' a été posté le : 16/01/09 08:10
|
Pour éviter la concentration d'optimums localisés, tu peux aussi te baser sur un facteur similitude-parentale/viabilité qui s'inspirerait d'un réalité biologique.
C'est à dire qu'à force de ne faire survivre que les plus parfaits, tu réduis le pool génétique qui tend vers un profil génétique localement unique, donc vers une forme de "consanguinité".
Si tu te bases sur un schéma naturel réel, les chances de mutation "débile" chez des consanguins sont plus élevées. Le débile ayant moins de chances de survivre, tu réduis sa durée de vie proportionnellement à la similitude chromosomiale des parents, jusqu'à un point antérieur à sa propre fertilité, et le "problème" d'"optimum" se règle de lui même. Tu obtiens alors une sorte de "jeu de la vie" où l'optimum débilisé laisse en disparaissant un espace vide que les "non-optimums" alentours viendront conquérir à leur tour.
Edit:
Ou alors, tu permets à ton optimum débilisé de chercher à se reproduire avec un non-optimum plutôt qu'un autre optimum, ce qui "raffraichira" ton pool génétique sans générer d'espace.
|
|
Dernière mise à jour par : Faeldihn le 16/01/09 08:16
|
--------------------
CREO ERGO SUM
"Commencez vous à voir quelle sorte de monde nous créons? [...] Un monde d'écraseurs et d'écrasés, un monde qui, au fur et à mesure qu'il s'affinera, deviendra plus impitoyable."
1984, Georges Orwell
|
|
|
|
|
Cachée
|
|
|
|
|
Pal pas triste
-= Chaos Elite Troops =-
Inscription le 12-07-04
Messages : 3384
Age : 54 ans
Lieu de résidence : 20e Nuit Lutècienne
|
|
|
|
|
|
Réponse au Sujet 'algorithmes génétiques' a été posté le : 20/01/09 11:22
|
Le renouvellement?
En un sens, c'est quoi l'intéret d'arriver à un point d'équilibre?
Si le but est de ne plus avoir qu'un caryotype optimal envahissant tout l'espace (qu'on peut aussi bien considérer comme un déséquilibre absolu que comme un équilibre parfait), les règles sont relativement simples.
Si le but est d'avoir un équilibre entre N caryotypes qui déploient leurs territoires et bloquent leurs frontières façon Go, c'est à peine plus compliqué.
Ou tu peux avoir un système oscillant avec une prévallence temporaire de l'un ou l'autre des caryotypes...
Si en revanche, le but est d'avoir une évolution permanente avec un renouvellement constant des populations, sans frontière définie et interactions fortes pour apparition continue de nouvelles combinaisons de caryotypes... ben ça me semble plus intéressant niveau règles à établir. Et en ce sens, le principe de dégénérescence des optimums évite de se retrouver dans le premier cas (ci-dessus).
Tu auras alors un système oscillant irrégulier/instable mais qui jamais ne devrait atteindre l'extinction totale ou la domination absolue.
|
|
Dernière mise à jour par : Faeldihn le 20/01/09 11:24
|
--------------------
CREO ERGO SUM
"Commencez vous à voir quelle sorte de monde nous créons? [...] Un monde d'écraseurs et d'écrasés, un monde qui, au fur et à mesure qu'il s'affinera, deviendra plus impitoyable."
1984, Georges Orwell
|
|
|
|
|
Cachée
|
|
|
|
Elite Troups
-= Chaos Elite Troops =-
Inscription le 06-07-02
Messages : 1574
Age : 42 ans
Lieu de résidence : Sur la Frontiere
|
|
|
|
|
|
Réponse au Sujet 'algorithmes génétiques' a été posté le : 23/01/09 16:29
|
|
|
|
|
|
Cachée
|
|
Grand Pourrisseur
-= Chaos Servants =-
Inscription le 11-11-07
Messages : 400
Age : 44 ans
Lieu de résidence :
|
|
|
|
|
Réponse au Sujet 'algorithmes génétiques' a été posté le : 11/03/09 16:13
|
Citation :Jormugaund dans une contemplation à Dlul a dit:
|
|
|
C'est impoli de linker directement l'image d'un webcomic. Donne le lien vers la page.
|
|
|
|
|
Cachée
|
|
Elite Troups
-= Chaos Elite Troops =-
Inscription le 06-07-02
Messages : 1574
Age : 42 ans
Lieu de résidence : Sur la Frontiere
|
|
|
|
|
|
Réponse au Sujet 'algorithmes génétiques' a été posté le : 11/03/09 16:42
|
Bah comme Munroe propose le lien pour le hotlink sous chacun de ses dessins, j'ai présumé qu'il s'en tamponne un peu en fait.
|
|
|
|
|
Cachée
|
|
Grand Pourrisseur
-= Chaos Servants =-
Inscription le 11-11-07
Messages : 400
Age : 44 ans
Lieu de résidence :
|
|
|
|
|
|
Réponse au Sujet 'algorithmes génétiques' a été posté le : 12/03/09 13:50
|
Bof, ça manche pas de pain. Puis c'est l'occasion de faire de la propagande pour XKCD
|
|
|
|
|
Cachée
|
|
