Optimisation combinatoire multicritère

Optimisation combinatoire multicritère

Introduction aux algorithmes génétiques

Les algorithmes génétiques, introduits en 1975 par Holland [Hol75], s’inspirent des mécanismes de sélection naturelle dans l’évolution des espèces. Au sein d’une population, les individus les moins adaptés à l’environnement disparaissent. Les autres survivent et transmettent leurs caractéristiques aux générations suivantes. La population devient ainsi, au cours des générations, de plus en plus adaptée à son environnement.

Un des intérêts majeurs des algorithmes génétiques est de ne faire, contrairement aux méthodes mathématiques plus classiques, aucune hypothèse quant à la nature des fonctions à optimiser. Ils peuvent donc en théorie traiter tous types de problèmes, et s’adapter à des fonctions non dérivables ou non continues, ce qui rend très vaste leur champ d’application. 

Principes généraux

Les individus formant la population d’un AG sont représentés par des chaînes de caractères sur un alphabet A, et de longeur fixe L. Les éléments d’une chaîne de caractères sont appelés « gènes », et la chaîne elle-même constitue le « génome » (ou le « chromosome ») d’un individu. L’optimisation par algorithmes génétiques suppose donc l’existence d’une fonction de « lecture » du génome, associant à tout élément de AL une configuration de l’espace de recherche. Traditionnellement, les auteurs préconisent un encodage binaire des individus (A = {0; 1}).

Dans une étude théorique, Whitley [Whi93] a montré que les capacités exploratoires des AGs résolvant des problèmes continus étaient maximales avec des alphabets binaires. De nombreuses méthodes récentes ont toutefois recours à des alphabets de plus grande cardinalité, voire infinis (alphabets réels). La conception d’un algorithme génétique repose sur quatre piliers fondamentaux : 1. une fonction de lecture permettant de représenter tout élément de l’espace de recherche par au moins un chromosome ;

2. une fonction d’évaluation à valeurs réelles, mesurant le niveau d’adaptabilité d’un individu à l’environnement, appelée couramment fonction de fitness1 ; 3. un ensemble d’opérateurs génétiques, c’est-à-dire des opérations internes, d’arité variable, sur l’espace des chromosomes, permettant d’engendrer de nouveaux individus ; 4. des stratégies de sélection et de remplacement, qui gouvernent l’évolution de la population. 

Opérateurs génétiques

En général, les opérateurs génétiques sont de deux types. On distingue les opérateurs binaires (souvent appelés opérateurs de croisement, ou crossovers), qui à une paire de chromosomes associent généralement un ou deux « rejetons », et les opérateurs unaires (mutation), n’agissant que sur un seul chromosome. Les opérateurs binaires imitent les mécanismes de la reproduction sexuée, dans laquelle les gènes de deux « parents » sont recombinés pour créer de nouveaux chromosomes, tandis que la mutation simule, comme son nom l’indique, des « accidents » survenant dans le génome au cours de l’évolution.

Alors que les croisements favorisent la transmission des caractéristiques d’une génération à la suivante, les mutations en introduisent de nouvelles, parfois salutaires. Les croisements les plus utilisés dans les AGs sont le crossover monopoint et le crossover uniforme. Dans le crossover monopoint, deux chromosomes sont « sectionnés » en un point aléatoire et les branches résultantes sont échangées. Dans le crossover uniforme, les gènes sont échangés aléatoirement entre les deux chromosomes. Quant à la mutation, elle consiste en général à altérer un seul gène du chromosome. La figure 5.5 illustre ces trois opérations.

Remarque 5.2. Les opérations de crossover (aussi bien monopoint qu’uniforme) conservent les schémas génétiques (voir Holland [Hol75] et Whitley [Whi93]) : si les mêmes gènes sont présents chez les deux chromosomes parents (en bleu sur la figure 5.5), ils sont alors transmis aux deux chromosomes issus du crossover.