Les algorithme genetique

Signaler
Messages postés
2
Date d'inscription
jeudi 11 mars 2010
Statut
Membre
Dernière intervention
17 mars 2010
-
Messages postés
2
Date d'inscription
samedi 24 avril 2010
Statut
Membre
Dernière intervention
26 avril 2010
-
bonjour a vous tous,
je dois concevoir un algorithme génétique pour quantification (compression) vectoriel (s'applique a la parole) mais a se sujet je nai pas encore trouvé assez de document pour démarrer mon projet donc si vous avez des docs ou des suggestions a propos de cela n'hésitez pas merci

6 réponses

Messages postés
157
Date d'inscription
dimanche 15 octobre 2006
Statut
Membre
Dernière intervention
27 août 2010
4
lut !
A propos de quoi ? Des algo génétique ou la quantification vectoriel ?
Messages postés
2
Date d'inscription
jeudi 11 mars 2010
Statut
Membre
Dernière intervention
17 mars 2010

les 2 , c pour une conception optimale d'un dictionnaire(codebook) pour la quantification vectorielle par plusieurs méthode d'optimisation et l'une d'elle est les algorithmes génétique
Messages postés
157
Date d'inscription
dimanche 15 octobre 2006
Statut
Membre
Dernière intervention
27 août 2010
4
Et bien, je peux t'aider pour ce qui est des algorithmes génétiques.
C'est relativement simple.
On va prendre le cas de la fonction y(x) = -x²
Le but est de chercher le maximum de cette fonction (qui est y=0 en x=0).
Les algortihmes génétiques fonctionnent comme un groupe de fourmis. Chacune essaye d'aller vers la nouriture à sa façon à chaque génération.
Une fourmi est appelé "individu", un groupe de fourmi est appelé "population", et chaque essai est appelé "génération".
Lors de la première génération, tu génére une population où chaque individu est représenté par un X choisi au hasard. Ce sera ta première génération.

Puis commence le cycle de la vie :

1ère étape : Le tournoi : La meilleur méthode pour récupérer les meilleurs individus est de procéder par la méthode "Roland Garros" pour les intimes. C'est à dire : les individus s'affrontent deux à deux et on ne garde que le meilleur (celui le plus proche de 0). (lorsque tu auras plusieurs paramettres à faire varier, celà permettra d'éviter d'avoir un individu très bon dans un domaine mais nul dans les autres qui prennent le pas sur les autres individus). Ainsi tu divises ta population en deux en ne gardant que les meilleurs individus.

2ème étape : Le croisement : où la reproduction. Ici, les parents (les meilleurs individus selectionnés précedement) vont donner naissance aux enfants. Chaque parent est croisé avec un autre et donne naissance à deux enfants. Pour celà, le paramètre 'x' de l'individu est converti en une chaine binaire, on choisit alors "des points de croisement" (1 ou 2, la meilleur méthode étant d'en choisir 2) et on intervertit la portion de code binaire entre ces deux points de croisement d'un parent à l'autre. On se retrouve alors avec quatre individus : 2 parents (sans modifications) et 2 enfants (correspondant au croisement des parents avec 2 nouveaux paramètres). Ainsi tu as regénéré ta population.

3ème étape : La mutation : Dans cet exemple, cette étape n'est pas pertinente. En effet, l'algorithme ne peut converger que vers 0 mais imagine une courbe avec plusieurs piques où tu veux le pique central mais tout les individus sont autour d'un pique secondaire et convergeront donc vers celui-ci. Ici, intervient alors la mutation. Chaque individu à une probabilité de muter (celà dépend mais de mon point de vu, une probabilité de 50% apporte de la diversité mais celà mettra plus de temps à converger). La mutation est le fait d'intervertir 2 bits d'un même individu, pouvant aboutir à une peite ou à une énorme différence, assurant ainsi que toutes les possibilités seront envisagés.

Et tu continue ce cycle jusqu'a ce que tu trouve un individu qui correspond à tes attentes.

Comme tu vois ce n'est pas du tout compliqué, tu appliques toujours la même méthode quelque soit le nombre de paramètre. Je suis actuellement entrain d'en faire un avec environ 300 paramètres et 5 points d'évaluation pour les meilleurs individus mais les algortihmes génétiques sont suffisament costaud pour digérer tout ca, ca prendra seulement un peu plus de temps. Pour un cas aussi simple que l'exemple que je t'ais donnés, pour un population de 64 individus (une populatio nest toujours paire et supérieur à 2), ca ne devrait mettre que moins d'une dizaine de génération grand maximum.

Voilà, j'espère avoir répondu à l'une de tes questions. J'espère avoir été clair aussi !
Messages postés
17
Date d'inscription
dimanche 19 avril 2009
Statut
Membre
Dernière intervention
4 juillet 2012

Bonjour,

C'est quoi la différence ou le rapport entre l'algorithme génétique et la programmation linéaire?

Merci
Messages postés
157
Date d'inscription
dimanche 15 octobre 2006
Statut
Membre
Dernière intervention
27 août 2010
4
Et bien ! Un algo génétique peut bouffeer n'importe quoi et donner un résultat très satisfaisant. La programmation linéaire est la recherche de solution simple à des problèmes simples. En gros, c'est déterminer un maximum d'une fonction à partir d'autre paramètre. Un algo génétique s'adapte à n'importe quoi. La par exemple, celui que je fais est un algo qui determinera les paramètres idéaux d'une molécule pour que sont intéraction avec un faisceaux correspondent le mieux à la réalité, ce qui est un problème autrement plus compliqué. Pour ton problème, les algo génétiques seraient les plsu adapté , surtout qu'ils sont facile à faire.
Messages postés
2
Date d'inscription
samedi 24 avril 2010
Statut
Membre
Dernière intervention
26 avril 2010

bonjour
je suis entrain de travailler sur le problème du voyageur de commerce (c'est un problème linière )est ce que vous pouvez m'aidé pour choisir la méthode la plus efficace pour optimiser ce problème
merci