les algorithme genetique

Question

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

deadhand · Answer

lut !
A propos de quoi ? Des algo génétique ou la quantification vectoriel ?

maximus888 · Answer

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

deadhand · Answer

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 !

semaesma · Answer

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

deadhand · Answer

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.

awatifaaa · Answer

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

Les algorithme genetique

6 réponses

Votre réponse

Discussions similaires