192
Recherche opérationnelle
1) Créer une population initiale
de
solutions codées chacune par un
chromosome.
2) Calculer la valeur de la fonction économique
pour chaque solution de
.
La force est du type
, où est une constante.
3) On sélectionne solutions dans
en utilisant une loi aléatoire. Une solution peut
donc apparaître plusieurs fois. On fait en sorte que plus elle est forte, plus elle a de
chances d'apparaître. On obtient un ensemble
de solutions sélectionnées.
4) Croisement : on apparie deux à deux les solutions de
. Pour chaque paire, avec
une probabilité
, on applique une fonction de croisement : les deux solutions vont
donner deux solutions « filles » dont les chromosomes seront des combinaisons des
chromosomes des « parents ». Les deux filles sont placées dans un nouveau sous
ensemble
. Avec la probabilité
, ce sont les parents qui sont placés dans
5) Mutation : pour chaque individu (solution) de
, on applique une fonction de
mutation, avec la probabilité
. On le laisse intact avec la probabilité
. On
recopie tous les individus, mutés ou non, dans
6) On retourne en 2) en passant à l'itération
et on continue jusqu'à un critère d'arrêt
(en général le nombre d'itérations).
Comme on le voit, il y a ici un nombre non négligeable d'ingrédients à choisir. Donnons
quelques précisions sur chacun d'eux :
- Codage
On a déjà évoqué ce point. Dans beaucoup de cas (mais pas dans tous) on
trouvera un codage en
. Par exemple, les solutions du problème de sac à
dos se codent spontanément de cette façon. Remarque : quand le problème
comporte des variables à valeurs réelles, ayant une certaine précision, on peut
toujours se ramener à un codage en
, mais il s'agit d'opérations souvent
très lourdes. De même, quand les variables sont entières, on peut prendre leur
codage binaire ; le chromosome sera constitué par la séquence des codages
binaires.
- Sélection
La « force » d'une solution, on l'a dit, est du type
dans le cas
d'une minimisation. En général, on prend pour
le maximum observé pour
, soit dans la population considérée pour la sélection, soit depuis le début
de la procédure (de telle sorte que est positive).
Recherche opérationnelle
1) Créer une population initiale
de
solutions codées chacune par un
chromosome.
2) Calculer la valeur de la fonction économique
pour chaque solution de
.
La force est du type
, où est une constante.
3) On sélectionne solutions dans
en utilisant une loi aléatoire. Une solution peut
donc apparaître plusieurs fois. On fait en sorte que plus elle est forte, plus elle a de
chances d'apparaître. On obtient un ensemble
de solutions sélectionnées.
4) Croisement : on apparie deux à deux les solutions de
. Pour chaque paire, avec
une probabilité
, on applique une fonction de croisement : les deux solutions vont
donner deux solutions « filles » dont les chromosomes seront des combinaisons des
chromosomes des « parents ». Les deux filles sont placées dans un nouveau sous
ensemble
. Avec la probabilité
, ce sont les parents qui sont placés dans
5) Mutation : pour chaque individu (solution) de
, on applique une fonction de
mutation, avec la probabilité
. On le laisse intact avec la probabilité
. On
recopie tous les individus, mutés ou non, dans
6) On retourne en 2) en passant à l'itération
et on continue jusqu'à un critère d'arrêt
(en général le nombre d'itérations).
Comme on le voit, il y a ici un nombre non négligeable d'ingrédients à choisir. Donnons
quelques précisions sur chacun d'eux :
- Codage
On a déjà évoqué ce point. Dans beaucoup de cas (mais pas dans tous) on
trouvera un codage en
. Par exemple, les solutions du problème de sac à
dos se codent spontanément de cette façon. Remarque : quand le problème
comporte des variables à valeurs réelles, ayant une certaine précision, on peut
toujours se ramener à un codage en
, mais il s'agit d'opérations souvent
très lourdes. De même, quand les variables sont entières, on peut prendre leur
codage binaire ; le chromosome sera constitué par la séquence des codages
binaires.
- Sélection
La « force » d'une solution, on l'a dit, est du type
dans le cas
d'une minimisation. En général, on prend pour
le maximum observé pour
, soit dans la population considérée pour la sélection, soit depuis le début
de la procédure (de telle sorte que est positive).