1. Les algorithmes génétiques, AG

 

Les algorithmes génétiques s’inspirent de la théorie de l’évolution et des règles de la génétique qui expliquent la capacité des espèces vivantes à s’adapter à leur environnement par la combinaison des mécanismes suivants :

  • la sélection naturelle fait que les individus les mieux adaptés à l’environnement tendent à survivre plus longtemps et ont donc une plus grande probabilité de se reproduire ;
  • la reproduction par croisement fait qu’un individu hérite ses caractéristiques de ses parents, de sorte que le croisement de deux individus bien adaptés à leur environnement aura tendance à créer un nouvel individu bien adapté à l’environnement ;
  • la mutation fait que certaines caractéristiques peuvent apparaître ou disparaître de façon aléatoire, permettant ainsi d’introduire de nouvelles capacités d’adaptation à l’environnement, capacités qui pourront se propager grâce aux mécanismes de sélection et de croisement.



Figure 2. Schéma récapitulatif

Les algorithmes génétiques reprennent ces mécanismes pour définir une méta-heuristique. L’idée est de faire évoluer une population de combinaisons, par sélection, croisement et mutation, la capacité d’adaptation d’une combinaison étant ici évaluée par la fonction objectif à optimiser. L’algorithme 1 décrit ce principe général, dont les principales étapes sont détaillées ci-après.

Initialisation de la population : en général, la population initiale est générée de façon aléatoire, selon une distribution uniforme assurant une bonne diversité des combinaisons.

Sélection : cette étape consiste à choisir les combinaisons de la population qui seront ensuite candidates pour la recombinaison et la mutation. Il s’agit là de favoriser la sélection des meilleures combinaisons, tout en laissant une petite chance aux moins bonnes combinaisons. Il existe de nombreuses façons de procéder à cette étape de sélection. Par exemple, la sélection par tournoi consiste à choisir aléatoirement deux combinaisons et à sélectionner la meilleure des deux (ou bien à sélectionner une des deux selon une probabilité dépendant de la fonction objectif). La sélection peut également être réalisée selon d’autres critères comme la diversité. Dans ce cas de figure, seuls les individus “distancés" sont autorisés à survivre et à se reproduire.

Recombinaison (croisement) : cette étape vise à créer de nouveaux individus par un mélange de combinaisons sélectionnées. L’objectif est de conduire la recherche dans une nouvelle zone de l’espace où de meilleures combinaisons peuvent être trouvées. A cette fin, la recombinaison doit être bien adaptée à la fonction à optimiser et capable de transmettre de bonnes propriétés des parents vers la combinaison créée. De plus, l’opérateur de recombinaison devrait idéalement permettre de créer des descendants diversifiés. Du point de vue de l’exploration et l’exploitation, la recombinaison est destinée à jouer un rôle de diversification stratégique avec un objectif à long terme de renforcement de l’intensification.

Mutation : cette opération consiste à modifier de façon aléatoire certains composants des combinaisons obtenues par croisement.

Les stratégies d'évolution forment une famille de métaheuristiques d'optimisation. Elles sont inspirées de la théorie de l'évolution, et appartiennent à ce titre à la classe des algorithmes évolutionnaires.

La méthode fut initialement proposée par Ingo Rencherberg, en 1965, à l'université technique de Berlin, en Allemagne. Elle est, à ce titre, la première véritable métaheuristique et le premier algorithme évolutionnaire, bien avant le recuit simulé ou les algorithmes génétiques. La méthode fut ensuite développée durant la fin des années 1960, principalement par les travaux de IngoRechenberg, P. Bienert et Hans-Paul Schwefel sur la conception de profils aérodynamiques.

Par la suite, les stratégies d'évolutions furent utilisées sur des problèmes d'optimisation continus, discrets, contraints, multi-objectifs, etc.

Dans sa version de base, l'algorithme manipule itérativement un ensemble de vecteurs de variables réelles, à l'aide d'opérateurs de mutation et de sélection. L'étape de mutation est classiquement effectuée par l'ajout d'une valeur aléatoire, tirée au sein d'une distribution normale. La sélection s'effectue par un choix déterministe des meilleurs individus, selon l'échelle de valeur de la fonction objectif.

Espace de recherche : ensemble de toutes les solutions faisable, X ∊Rn

Fonction objectif: critère de cout f : Rn → R

But : trouver la meilleure solution selon le critère x*= argmin f

Mais, parfois, l'ensemble des meilleures solutions, bonne approximation de la meilleure solution, une bonne «robuste» solution ...

S ensemble de solutions (espace de recherche)

f: S → R fonction objectif

V (s) ensemble des solutions voisines de s

 


Figure 3.Algorithmes stochastiques avec solution unique

 

S ensemble des solutions (espace de recherche),

f : S → IR fonction objectif à maximiser (ou cout a minimiser)

V(s) ensemble des solutions voisines de s

 


Heuristique d’exploitation maximale. Hill Climber (meilleure amélioration).

Algorithme de comparaison

Operateur local de base de métaheuristique



Optimum local:
Etant donné (S, f , V), f à minimiser.
x* est un optimum local ssi pour tout x ∈ V(x*), f (x*) ≤ f (x)

Optimum local strict:
Etant donné (S, f , V), f à minimiser
x* est un optimum local ssi pour tout x ∈ V(x*), f (x*) < f (x)

Hill-climber de première amélioration (minimizer)



 


σ∈ IR (step size) et la matrice C ∈ IRn× n (covariance matrix) sont des paramètres de l’algorithme.