Expliquer la méthode de L'évolution différentielle

Répondre à ma propre question...

vue d'ensemble

• la principale différence entre les Algorithmes génétiques et L'évolution différentielle (DE) est que les Algorithmes génétiques reposent sur le croisement alors que les stratégies évolutives utilisent la mutation comme principal mécanisme de recherche.
• DE génère de nouveaux candidats en ajoutant une différence pondérée entre deux membres de la population à un troisième membre (plus de détails ci-dessous).
• Si le candidat est supérieur au candidat avec lequel il a été comparé, il le remplace; sinon, le candidat d'origine reste inchangé.

Définitions

• La population est composée de NP les candidats.
• Xi = un parent candidat à l'index i(les indices varient de 0NP-1) de la génération actuelle. Aussi connu comme le vecteur cible.
• Chaque candidat contient D paramètre.
• Xi(j) = j e paramètre du candidat Xi.
• Xa,Xb,Xc = trois candidats parents au hasard.
• vecteur de Différence = (Xb - Xa)
• F = un poids qui détermine le taux d'évolution de la population.
  • les valeurs Idéales: [0.5, 1.0]
• CR = Probabilité de croisement.
  • Portée: [0, 1]
• Xc` = un vecteur mutant obtenu par l'opération de mutation différentielle. Aussi connu comme le vecteur donneur.
• Xt = L'enfant de Xi et Xc`. Aussi connu comme le vecteur d'essai.

Algorithme

1. pour chaque candidat dans la population
   • for (int i = 0; i<NP; ++i)
2. choisir au hasard trois parents distincts (ils doivent être différents les uns des autres et i)

do
{
  a = random.nextInt(NP);
} while (a == i)
do
{
  b = random.nextInt(NP);
} while (b == i || b == a);
do
{
  c = random.nextInt(NP);
} while (c == i || c == b || c == a);

3. (étape de Mutation) Ajouter un vecteur de différence pondérée entre deux membres de la population à un troisième membre
   • Xc` = Xc + F * (Xb - Xa)
4. (Crossover étape) Pour chaque variable Xi, s'appliquent uniforme crossover avec une probabilité CR hérite de Xc`; sinon, hériter de Xi. Au moins une variable doit être héritée de Xc`

int R = random.nextInt(D);
for (int j=0; j < D; ++j)
{
  double probability = random.nextDouble();
  if (probability < CR || j == R)
    Xt[j] = Xc`[j]
  else
    Xt[j] = Xi[j]
}

5. (étape de Sélection) Si Xt supérieur à XiXt remplace Xi dans la prochaine génération. Autrement,Xi n'est pas modifié.

Ressources

• Voir pour un aperçu de la terminologie
• Voir Optimisation de l'Utilisation de Différentiel d'Évolution par Vasan Arunachalam pour une explication de l'Évolution Différentielle algorithme
• Voir Evolution: Une Enquête de l'État-of-the-Art par Swagatam Das et Ponnuthurai Nagaratnam Suganthan pour différentes variantes de l'algorithme de L'évolution différentielle
• Voir Évolution Différentielle d'Optimisation à partir de Zéro avec Python pour une description détaillée d'une implémentation d'un algorithme DE en python.

le fonctionnement de l'algorithme DE est très simple. Pensez vous avez besoin pour optimiser(minimiser,par exemple) ∑Xi^2 (modèle de sphère) dans une plage donnée, disons [-100,100]. Nous savons que la valeur minimale est 0. Nous allons voir comment DE travaux.

DE est un algorithme basé sur la population. Et pour chaque individu de la population, un nombre fixe de chromosomes sont présents (à l'imaginer comme un ensemble d'êtres humains et les chromosomes ou des gènes dans chacun d'eux). Laissez-moi vous expliquer DE w.R. t fonction ci-dessus

nous devons fixer la taille de la population et le nombre de chromosomes ou de gènes(nommés comme paramètres). Par exemple, considérons une population de taille 4 et chacun des individus a 3 chromosomes(ou des gènes ou des paramètres). Appelons les individus R1, R2,R3, R4.

Étape 1:Initialiser la population

il faut initialiser au hasard la population dans l'intervalle [-100,100]

        G1    G2    G3    objective fn value
R1 -> |-90  |  2  | 1   |   =>8105
R2 -> |  7  |  9  | -50 |   =>2630
R3 -> |  4  |  2  | -9.2|   =>104.64
R4 -> | 8.5 |  7  |  9  |   =>202.25

objectif la fonction de valeur est calculée à l'aide de la fonction objectif.Dans ce cas, c'est ∑Xi^2. Ainsi, pour R1, la valeur FN obj sera -90^2+2^2+2^2 = 8105. De même, il est pour tous.

Etape 2 : Mutation

fixer un vecteur cible,disons pour eg R1 et ensuite sélectionner au hasard trois autres vecteurs(individus)disons pour eg.R2,R3, R4 et effectue la mutation. La Mutation se fait comme suit,

MutantVector = R2 + F(R3-R4)

(vecteurs peuvent être choisis au hasard, n'ont pas besoin d'être dans un ordre). F (facteur d'échelle/constante de mutation) à l'intérieur de la fourchette [0,1] est l'un des rares paramètres de contrôle que DE possède.En termes simples, il décrit comment le vecteur muté devient différent. Gardons F = 0.5.

|  7  |  9  | -50 |
        +

       0.5 *

|  4  |  2  | -9.2|

        +

| 8.5 |  7  |  9  |

la Mutation en cours donnera le vecteur Mutant suivant

MV = | 13.25 | 13.5 | -50.1 | =>2867.82

Etape 3: Crossover

maintenant que nous avons un vecteur cible (R1) et un vecteur mutant MV formé de R2, R3 & R4, nous avons besoin de faire un crossover. Considérez R1 et MV comme deux parents et nous avons besoin d'un enfant de ces deux parents. Le recoupement est fait pour déterminer la quantité d'information qui doit être prise des deux parents. Il est contrôlé par taux de Croisement(CR). Chaque gène / chromosome de l'enfant est déterminé comme suit,

un nombre aléatoire entre 0 et 1 est généré, s'il est supérieur à CR, puis hériter un gène de cible (R1) autrement de mutant (MV).

réglons CR = 0.9. Puisque nous avons 3 chromosomes pour les individus, nous avons besoin de générer 3 nombres aléatoires entre 0 et 1. Par exemple, ces chiffres sont respectivement de 0,21, 0,97 et 0,8. La première et la dernière sont inférieures à la valeur CR, de sorte que ces positions dans le vecteur de l'enfant seront remplies par les valeurs de MV et la deuxième position sera remplie par le gène pris de la cible(R1).

Cible-> |-90 | 2 | 1 | Mutant -> | 13.25 | 13.5 | -50.1 |

random num - 0.21, =>  `Child -> |13.25| -- | --    |`
random num - 0.97, =>  `Child -> |13.25| 2  | --    |`
random num - 0.80, =>  `Child -> |13.25| 2  | -50.1 |`

Trial vector/child vector -> | 13.25 | 2 | -50.1 | =>2689.57

Étape 4 : Sélection

maintenant nous avons enfant et cible. Comparez l'obj fn des deux, voyez lequel est le plus petit (problème de minimisation). Sélectionnez cette personne parmi les deux pour la prochaine génération

 R1                       -> |-90    |  2  | 1     |   =>8105
Trial vector/child vector -> | 13.25 | 2   | -50.1 |   =>2689.57

de toute évidence, l'enfant est mieux, alors remplacez la cible(R1) par l'enfant. Ainsi la nouvelle population deviendra

        G1    G2    G3    objective fn value
R1 -> | 13.25 | 2   | -50.1 |   =>2689.57
R2 -> |  7    |  9  | -50   |   =>2500
R3 -> |  4    |  2  | -9.2  |   =>104.64
R4 -> | -8.5  |  7  |  9    |   =>202.25

Cette procédure sera continué jusqu'le nombre de générations souhaité est atteint ou jusqu'à ce que nous obtenir notre valeur souhaitée. Espérons que cela donnera vous aider.