Discussion :

[Maha Ing]

Bonjour,
j'ai une image faciale que je lui applique la transformée en cosinus discrète (en anglais DCT: Discrete Cosine Transform). J'utilise un premask pour sélectionner les fréquences moyennes et éliminer les hautes et les basses fréquences, comme le montre la figure suivante:



La taille du premask est arbitraire, ici j'utilise celui-là: [2 15 2 15]=[rs re cs ce].
Maintenant je veux changer la taille de ce premask plusieurs fois et choisir le meilleur qui donnera le minimum taux d'erreur de reconnaissance faciale, et ce en utilisant l'algorithme génétique.
En fait, je connais les basiques de cet algorithme mais je trouve une difficulté lors de son application à mon propre problème: comment choisir la population, comment écrire la fonction de fitnesse, ... ?
Aidez-moi s'il vous plait!

[cjacquel]

Il faut définir le problème : Qu'est ce qui doit être optimisé. Quelle est la fonction à optimiser.
Puis on en déduit la forme de l'espace des solutions.
Alors on fait les individus, dans ce cas ce sont les masques en 2D qui sont les individus, alors il faut programmer la mutation et le crossover sur ces masques.
Ensuite il faut faire la boucle de l'algorithme génétique:
Initialisation
Pour n générations
Evaluation de la population
Sélection et reproduction
Remplacement par la nouvelle population créée.

Christophe,

[Maha Ing]

Merci pour votre réponse
Je veux optimiser le taux d'erreur (je travaille sur un projet de reconnaissance de visage).
Voila un exemple: ici j'obtiens cette courbe en utilisant le premier prémask de mon choix, qui est [2 15 2 15]



maintenant je veux obtenir une meilleure courbe en essayant plusieurs premasks dont je veux trouver à la fin le meilleur. J'espère que mon objectif est clair.

j'ai pensé à cette façon d'écriture de la fonction de fitnesse:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
function err=fitness_funct(x)
err=x/75; 
%err c'est la moyenne du taux d'erreur à optimiser pour un nombre de caractéristique donné
end

mais je sais pas est ce que si c'est réalisable, car je croix que la fonction de fitness dois être en fonction des individus qui sont les premasks n'est ce pas, ou c'est pas toujours le cas ?
Une autre question, est ce que les individus peuvent être de tailles différentes? car je veux essayer de changer la taille du premask et voir quel premask va me donner la meilleure courbe.
J'espère que vous répondez à mes questions. Merci

[cjacquel]

Au départ il faut définir le chromosome 2D : Un tableau en 2D ou un vector. Ils peuvent être de taille différentes :des masques 10x10, ou des masques 7x7.

Puis il faut créer une population de 100 individus par exemple.

Puis il faut évaluer chacun des 100 individus, en calculant pour chaque masque le taux d'erreur. Ce sera la fonction fitness de l'individu qui est a minimiser. Plus le taux d'erreur sera faible, plus l'individu sera adapté. Prendre 1/taux d'erreur pour avoir une fonction à maximiser.

Puis il faut sélectionner les individus avec la sélection par la roue de la roulette. (RWS).

Puis il faut définir la mutation : le changement d'une valeur du masque et l'opérateur de crossover (en prenant 2 masques parents et en générant 2 masque enfants) en les combinant.

Puis la nouvelle population crée vient remplacer la population courante.

Puis il faut itérer le cycle Evaluation/Reproduction/Remplacement sur 300 générations.

Et ensuite au bout de 300 générations, le masque optimal devrait être trouvé.

Christophe

[dourouc05]

Et ensuite au bout de 300 générations, le masque optimal devrait être trouvé.

Sauf que, en fait, tu n'en as aucune idée . En moyenne, on estime qu'un certain nombre d'itérations (et une certaine taille de population initiale, et trente-six paramètres pour les heuristiques de combinaison, et…) devrait être suffisant pour trouver une (très) bonne solution — ce qui est très probablement suffisant dans un bon nombre d'applications. Les algorithmes génétiques ne sont que des métaheuristiques : elles ne peuvent donner aucune garantie formelle d'optimalité (mais sont parfois la seule solution envisageable).

[Golgotha]

Oui... les algorithmes génétiques ça se rapproche d'une recette de cuisine qu'on essaye d'ajuster avec des essais, plus ou moins de sel, de poivre, feux doux, temps de cuisson...

@Maha Ing Le problème est-il NP-complet ? si non, il est préférable de brute-forcé la solution.

- Faire attention aux mutations, il y à peut être des règles de conformité de l'individu a respecter.
- L'important est de pouvoir ordonner la population à la fin de chaque itération.
- Il faut essayer plusieurs manière de faire le cross-over.
- Attention à ne pas faire des enfants uniquement entre les meilleurs individus, tu t'enfermera trop vite dans un maximum local.

[Gwym.H]

mais je sais pas est ce que si c'est réalisable, car je croix que la fonction de fitness dois être en fonction des individus qui sont les premasks n'est ce pas, ou c'est pas toujours le cas ?
Une autre question, est ce que les individus peuvent être de tailles différentes? car je veux essayer de changer la taille du premask et voir quel premask va me donner la meilleure courbe.
J'espère que vous répondez à mes questions. Merci

Bonjour.
Virtuellement, les individus sont plutôt les vecteurs de coefficients. Utiliser les coordonnées de masques ne revient il me semble qu'à tenter de réduire la taille de représentation du génome, ce qui n'est a priori pas le plus important,
et pose le problème du risque la décorrélation des individus ("coefficient de DCT correspondant à la valeur d'une fréquence dans l'image") avec ces valeurs ("coordonnées dans un tableau").
Si par exemple les valeurs de fréquence sont des couples x, y de "chromosomes" allant de 0 à 2^32 ou au contraire des couples de coordonnées x, y dans un tableau allant de 0 à 32, l'effet d'une mutation unitaire sur ce chromosome sera sans commune mesure,
et utiliser les coordonnées de masque risque de ne jamais voir l'algorithme converger. De même, la mise sous forme de vecteur des coefficient peut arbitrairement se faire par ligne, en zig-zag (couple croissant de fréquences), etc...

Je suppose que vous avec déjà consulté le Web, mais a tout hasard vous pouvez vous inspirer des documents
http://www.m-hikari.com/ces/ces2012/...S9-12-2012.pdf
et
http://www.sersc.org/journals/IJSIP/vol2_no2/6.pdf

qui présentent les méthodes et les paramètres utilisés pour l'algorithme génétique (l'un des document est plus orienté optimisation par essaims particulaires, mais compare aussi les solutions obtenues avec un algorithme génétique)

- dans les deux cas ce sont les vecteurs de coefficients qui sont utilisés, ce qui résout la question de génomes multiforme (possible, mais plus complexe et plus risquée à mettre en oeuvre)
- sélection tout ou rien parmi les vecteurs de coefficients
- mécanisme de sélection basé sur une probabilité linéaire de la fonction fitness
- 30 à 50 individus
- taux de croisement de 10%
- taux de mutation de 1 à 2%
- 100 générations

[Maha Ing]

Merci à vous tous pour vos réponses, elles m'aident vraiment.
mais j'ai un problème lors de l'application de ma fonction de fitness, car mon objectif est de minimiser toutes les valeurs de cette courbe. A la fin je veux obtenir la meilleure courbe et non pas un seul meilleur point. C'est à dire je dois comparer deux premask selon un ensemble de points et non pas un seul point, vous voyez?



Cette courbe est associé au premask [2 15 2 15].
Mon but est d'avoir la meilleur courbe qui contient les minimum valeurs du taux d'erreur. Alors comment j'applique la fonction de fitness dans ce cas?

[dourouc05]

Le raisonnement est toujours le même : à partir de deux courbes, comment déterminer la meilleure pour ton application ? Il semblerait que tu veuilles une courbe qui est en-dessous de toutes les autres, ce qui me paraît difficile à garantir. Ne pourrais-tu pas te limiter au minimum de la courbe ?

[Maha Ing]

Ne pourrais-tu pas te limiter au minimum de la courbe ?

Non, je pense pas ça sera une bonne idée dans ce cas là.

Actuellement, j'utilise matlab pour l'implémentation de ce problème. Je vais essayer de faire un petit exemple pour mieux comprendre la situation:
Supposons que j'ai cette population initial de premasks (je vais me limiter à 2 individus juste pour la compréhension)
pm1=[0 0 1;1 1 1;1 0 0]
pm2=[0 1 1;1 1 0;0 0 0]

Les valeurs dans la courbe mean of error rate=f(number of features) sont:
pour pm1: mean_error_rate=[0.17 0.16 0.15 0.14 0.13 0.12 0.1]
pour pm2=mean_error_rate=[0.15 0.09 0.05 0 0 0 0 ]

Pour cela j'utilise la fonction de fitness suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
function y=Fitness(mean_error_rate)
y=mean_error_rate
end

et j'utilise cette ligne de commande

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
nvar=7; %la longueur du vecteur de mean_error_rate
[x fval]=ga(@Fitness,nvar,opt)

Mais là je trouve une ambiguité, est ce que l'algorithme génétique va muter et croiser les les valeurs des vecteurs du mean_error_rate ou bien les premasks?? En fait je comprend pas comment l'algorithme va retourner pour changer les premasks specifiquement et noon pas d'autres variables dans le progrmme. Je me trouve perdue là!!
pouvez vous me clarifier ce point s'il vous plait?

[dourouc05]

Le principe est que tu écrives les fonctions pour fusionner plusieurs solutions (croisement, puis mutations, même combat). À toi de trouver une bonne manière de le faire. Le calcul de ta fonction objectif (fitness) utilise les taux moyens d'erreur, mais ces résultats ne devraient pas sortir de cette évaluation d'un individu.

L'optimisation se passe exclusivement sur des masques : un individu est un masque, rien d'autre. Ensuite, tu fais des calculs compliqués pour évaluer la qualité d'un masque, ça te donne une courbe en sortie, la métaheuristique ne peut pas savoir ce qui se passe dans cette évaluation.

[Maha Ing]

Ne pourrais-tu pas te limiter au minimum de la courbe ?

Ne serait-il pas mieux si je me limite à la moyenne de toutes les valeurs de la courbe au lieu du minimum?

[dourouc05]

Ne serait-il pas mieux si je me limite à la moyenne de toutes les valeurs de la courbe au lieu du minimum?

Qu'est-ce qui t'intéresse vraiment ? Ici, à te lire, j'ai l'impression que c'est reconnaître au mieux des visages : peu importe le comportement de ton masque avec très peu de caractéristiques extraites de l'image, puisque tu ne t'attends pas à des miracles (plutôt : si tu as quelque chose de bien au début de la courbe, c'est plus un artefact qu'un signe que ta solution pourra s'appliquer avec de bons résultats à d'autres images que celles de ton ensemble de test). Que t'importe-t-il de prendre en compte cette partie de la courbe ? Plutôt, pour moi, ce qui t'intéresse, c'est plutôt le meilleur couple masque-nombre de caractéristiques.