Élaboré par :

I-INTRODUCTION AUX ALGORITHMES GENETIQUES :

- l'évolution a deux composantes : la sélection et la reproduction.

- la sélection garantit une reproduction plus fréquente des chromosomes les plus forts.

- la reproduction est la phase durant laquelle s'effectue l'évolution.

Dans les années 60s, John H. Holland expliqua comment ajouter de l'intelligence dans un programme informatique avec les croisements (échangeant le matériel génétique) et la mutation (source de la diversité génétique).

Il formalisa ensuite les principes fondamentaux des algorithmes génétiques :

- la capacité de représentations élémentaires, comme les chaînes de bits, à coder des structures complexes.

- le pouvoir de transformations élémentaires à améliorer de telles structures.

 

Et récemment, David E. Goldberg ajouta à la théorie des algorithmes génétiques les idées suivantes :

- un individu est lié à un environnement par son code d'ADN.

- une solution est liée à un problème par son indice de qualité.

3. Applications : 

Les applications des AG sont multiples : optimisation de fonctions numériques difficiles (discontinues…), traitement d’image (alignement de photos satellites, reconnaissance de suspects…), optimisation d’emplois du temps, optimisation de design, contrôle de systèmes industriels [Beasley, 1993a], apprentissage des réseaux de neurones [Renders, 1995], etc.

Les AG peuvent être utilisés pour contrôler un système évoluant dans le temps (chaîne de production, centrale nucléaire…) car la population peut s’adapter à des conditions changeantes. Ils peuvent aussi servir à déterminer la configuration d’énergie minimale d’une molécule.

Les AG sont également utilisés pour optimiser des réseaux (câbles, fibres optiques, mais aussi eau, gaz…), des antennes [Reineix, 1997]… Ils peuvent être utilisés pour trouver les paramètres d’un modèle petit-signal à partir des mesures expérimentales [Menozzi, 1997]

Après trouver ces deux fonctions on peut appliquer l’AG :

1- Générer aléatoirement quelques séquences de bits pour composer la

soupe initiale.

2- Mesurer l’adaptation de chacune des séquences présentes.

3- Reproduction des séquences en fonction de son adaptation.

4- Faire l’opération de croisement aléatoirement de quelque paire de séquences, et ce sera :

- une séquence est composée de la 1^ere partie de la 1^ere séquence et de la 2^nd partie de la 2^nd séquence.

- et une séquence est composée de la 2^nd partie de la 1^ere séquence et de la 1^ere partie de la 2^nd séquence.

5- Faire l’opération de mutation d’un bit choisi aléatoirement dans une ou

plusieurs séquences.

6- Retour à l’étape 2 (mesurer l’adaptation à nouveau).

Contrairement au codage binaire, dans le codage réel il n’y a pas d’opération de conversion vers le réel et le binaire, et alors l’AG soit plus dépendant du problème, chacune des composantes correspond à une inconnue du problème. Et pour l’insertion des chromosomes soit :

- Par l’insertion des chromosomes directement dans la population de la génération suivante.

• Par "l’élitisme " : c’est l’insertion du meilleur chromosome dans la population de la génération suivante et de compléter l’individu par des chromosomes d’uns manière traditionnelle.
• Par  "la population sans double " : c’est l’insertion du chromosome dans la population de la génération suivent à condition qu’il soit différent de tous les chromosomes de la nouvelle génération.

Représentation schématique du fonctionnement de l’AG

Il y’ a plusieurs méthodes de sélection, citons quelques-unes  :

a/ Roulette de casino : C’est la sélection naturelle la plus employée pour l’AG binaire. Chaque chromosome occupe un secteur de roulette dont l’angle est proportionnel à son indice de qualité. Un chromosome est considéré comme bon aura un indice de qualité élevé, un large secteur de roulette et alors il aura plus de chance d’être sélectionné.

B/ " N/2 –élitisme " : Les individus sont tries selon leur fonction d’adaptation, seul la moitié supérieure de la population correspondant aux meilleurs composants est sélectionnée, nous avons constates que la pression de sélection est trop forte, il est important de maintenir une diversité de gènes pour les utilise dans la population suivante et avoir des populations nouvelles quant on les combine.

C/ "par tournoi " : Choisir aléatoirement deux individus et on compare leur fonction d’adaptation (combattre) et on accepte la plus adapte pour accéder à la génération intermédiaire, et on répète cette opération jusqu'à remplir la génération intermédiaire (N/2 composants). Les individus qui gagnent à chaque fois on peut les copier plusieurs fois ce qui favorisera la pérennité de leurs gènes.

Le phénomène de croisement est une propriété naturelle de l’ADN, et c’est analogiquement qu’on fait les opérations de croisement dans les AG.

a-1 / " croisement en un point " : on choisit au hasard un point de croisement, pour chaque couple (fig. 1). Notons que le croisement s’effectue directement au niveau binaire, et non pas au niveau des gènes. Un chromosome peut donc être coupé au milieu d’un gène.

a-2 / " croisement en deux points " : On choisit au hasard deux points de croisement (Fig. 2). Par la suite, nous avons utilisé cet opérateur car il est généralement considéré comme plus efficace que le précédent [Beasley, 1993b]. Néanmoins nous n’avons pas constaté de différence notable dans la convergence de l’algorithme.

Notons que d’autres formes de croisement existent, du croisement en k points jusqu’au cas limite du croisement uniforme.

Le croisement réel ne se différencie du croisement binaire que par la nature des éléments qu'il altère : ce ne sont plus des bits qui sont échangés à droite du point de croisement, mais des variables réelles.

Le croisement arithmétique est propre à la représentation réelle. Il s'applique à une paire de chromosomes et se résume à une moyenne pondérée des variables des deux parents.

Soient [ai, bi, ci] et [aj, bj, cj] deux parents, et p un poids appartenant à l'intervalle [0, 1],
alors les enfants sont [pai + (1-p)aj, pbi + (1-p)bj, pci + (1 - p)cj] ...

Si nous considérons que p est un pourcentage, et que i et j sont nos deux parents, alors l'enfant i est constitué à p% du parent i et à (100-p)% du parent j, et réciproquement pour l'enfant j.

Nous définissons une mutation comme étant l’inversion d’un bit dans un chromosome (Fig. 3 ). Cela revient à modifier aléatoirement la valeur d’un paramètre du dispositif. Les mutations jouent le rôle de bruit et empêchent l’évolution de se figer. Elles permettent d’assurer une recherche aussi bien globale que locale, selon le poids et le nombre des bits mutés. De plus, elles garantissent mathématiquement que l’optimum global peut être atteint.

D’autre part, une population trop petite peut s’homogénéiser à cause des erreurs stochastiques : les gènes favorisés par le hasard peuvent se répandre au détriment des autres. Cet autre mécanisme de l’évolution, qui existe même en l’absence de sélection, est connu sous le nom de dérive génétique. Du point de vue du dispositif, cela signifie que l’on risque alors d’aboutir à des dispositifs qui ne seront pas forcément optimaux. Les mutations permettent de contrebalancer cet effet en introduisant constamment de nouveaux gènes dans la population [Beasley, 1993b].

Comment réaliser notre opérateur mutation ? De nombreuses méthodes existent. Souvent la probabilité de mutation p_m par bit et par génération est fixée entre 0,001 et 0,01. On peut prendre également p_m=1/l où l est le nombre de bits composant un chromosome. Il est possible d’associer une probabilité différente de chaque gène. Et ces probabilités peuvent être fixes ou évoluer dans le temps.

Après divers essais, ils ont abouti à la méthode d’auto-adaptation des probabilités de mutation [Bäck, 1992]. Si dans un environnement stable il est préférable d’avoir un taux de mutation faible, la survie d’une espèce dans un environnement subissant une évolution rapide nécessite un taux de mutation élevé permettant une adaptation rapide. Les taux de mutation d’une espèce dépendent donc de leur environnement [Wills, 1991].

Pour prendre en compte cette formulation biologique et l’adapter à notre cas, ils ont introduit dans chaque individu (dispositif) un second chromosome (ensemble de paramètres) dont les gènes (paramètres) représentent les probabilités de mutation de chaque gène du premier chromosome (Fig. 4 ). Ce second chromosome est géré de façon identique au premier, c’est-à-dire qu’il est lui-même soumis aux opérateurs génétiques (croisement et mutation). Cela revient à fixer les probabilités assurant la modification des valeurs des paramètres du composant en fonction des valeurs d’un ensemble d’autres paramètres (les probabilités de mutation).

Lors de la genèse, les probabilités de mutation sont posées égales à 0,1 (valeur qui a paru la meilleure après plusieurs essais). Au cours du déroulement de l’algorithme, les gènes et les individus ayant des probabilités de mutation trop élevées ont tendance à disparaître. De même, les gènes ayant des probabilités de mutation trop faibles ne peuvent pas évoluer favorablement et tendent à être supplantés. Les probabilités de mutation dépendent donc du gène considéré et de la taille de la population. De plus, elles évoluent au cours du temps. Il y a donc auto-adaptation des probabilités de mutation.

La mutation binaire s'applique à un seul chromosome. Un bit du chromosome est tiré au hasard. Sa valeur est alors inversée.

Il existe une variante où plusieurs bits peuvent muter au sein d'un même chromosome. Un test sous le taux de mutation est effectué non plus pour le chromosome mais pour chacun de ses bits : en cas de succès, un nouveau bit tiré au hasard remplace l'ancien.

La mutation réelle ne se différencie de la mutation binaire que par la nature de l'élément qu'elle altère : ce n'est plus un bit qui est inversé, mais une variable réelle qui est de nouveau tirée au hasard sur son intervalle de définition.

La mutation non uniforme possède la particularité de retirer les éléments qu'elle altère dans un intervalle de définition variable et de plus en plus petit. Plus nous avançons dans les générations, moins la mutation n'écarte les éléments de la zone de convergence. Cette mutation adaptative offre un bon équilibre entre l'exploration du domaine de recherche et un affinement des individus.
Le coefficient d'atténuation de l'intervalle est un paramètre de cet opérateur.

- Les deux avions sont considérés comme des points matériels qui se déplacent à une vitesse constante égale par exemple a 220m/s.

- L’avion peut manœuvrer de trois façons : virer soit à droite, soit à gauche d’un angle donné (30°), nous n’appliquons pas la montée et la descente car au contrôle aérien ces deux manœuvres sont utilise qu’au dernier recoure à cause de leur coût de consommation et de confort du passager.

- Nous prenons le pas de discrétisation de 16 (Le temps devise en intervalle de longueur fixe)

La première opération c’est le codage :

Nous codons les trois mouvements possibles de l’avion sur deux bits :

- la ligne droite par 00 et 01.

- tourner à droite par 10.

- Tourner à gauche par 11.

Le critère d’évaluation retenu est la distance restante à parcourir pour rejoindre le point d’arrivée après l’application des 16 actions codées par la séquence (ceci équivalant strictement a mesurer la distance totale parcourue puisque la distance parcourue en un pas est constante ).

Il est ramené à l’intervalle [0,1] la formule empirique suivante :A=e**(-(d/2ds)²)……(ks)

Ou : d : la distance restante à parcourir.

ds : la distance de séparation (15km).

Les séquences de trajectoire ne respectent pas la norme de sécurité sont affectées d’une adaptation nulle.

La difficulté de cette méthode est de définir une bonne fonction d’adaptation ainsi que de régler les différents paramètres régissants l’évolution des séquences.

La figure 5.1 montre une solution obtenue après 54 générations de l’AG.

Les paramètres choisis étaient :

- population comprenant 400 individus.

- 60% de croisement à chaque génération.

- 0.1% de mutation à chaque génération.

Cette solution est optimale, après l’application de l’algorithme (ks) on obtient des résultats équivalents à celle de l’AG mais dans un temps très long.

 

 

Principe :

• A chaque avion un point de départ et un point d’arrivée.
• Si les deux avions volent en ligne droite et à la même vitesse ils entreront en conflit
• Les deux avions peuvent changer de cap, accélérer et décélérer.

Modélisation :

• Le temps et fixe en un intervalle de longueur fixe et qui est égale a 16.
• L’avion peut augmenter et diminuer sa vitesse de 20 m/s mais elle ne peut pas dépasser les vitesses limites définies par ses performances, et aussi elle peut changer sa direction.
• La vitesse max. est de 260 m/s et la vitesse min. est de 170 m/s.

Modification de la fonction d’adaptation :

• En conservant le cap et en changent la vitesse, la consommation de l’avion sera proportionnelle a sa vitesse comme ca les deux avions pourraient s’éviter avec un coût nul.
• Cependant, il n’est pas possible d’interdire les séquences qui ne menant pas a des positions proche des buts. En effet il est probable que la totalité de la population initiale serait pénalisée et que les séquences acceptables qui émergeraient ensuite ne seraient que peut diversifier.
• La fonction d’adaptation est en fonction de la distance au but et la consommation, les séquences auront une adaptation faible sont celles qui ne permettant pas d’approcher le but, et celles qui sont proche du but c’est la consommation qui déterminera l’a adaptation.
• L’évolution d l’adaptation moyenne de la population et celle du meilleur individu généré sont présentées respectivement sur les figures 6.1et 6.2.
• Les résultats obtenus après 82 générations sont assez semblables a ceux obtenus par l’algorithme (ks) :

A=e**(-0.04[((d/dm)**4)+(c/cmin)²])

Ou :

• dm : La distance moyenne parcouru pendant un pas de calcul.
• cmin : la consommation minimale d’un avion sur le trajet.
• c : consommation effective.
• d : la distance parcourue.

la recherche du maximum d'une fonction du type y=f(x).

Un algorithme génétique travaille à partir d'un ensemble d'éléments choisis au hasard dans un espace de solutions potentielles. Dans notre cas, l'ensemble de départ se composera de nombres tirés au hasard dans l'intervalle où nous recherchons le maximum.

Sa connaissance du problème à résoudre se résume à une fonction d'évaluation qui mesure la qualité d'un élément en tant que solution au problème. La fonction d'évaluation sera ici la fonction elle-même : le x donnant le plus grand y par f sera considéré comme le maximum de f dans l'ensemble de départ, appelé génération 1.

La qualité de ce maximum est bien entendue très médiocre puisqu'il a été choisi au hasard. Cependant, l'algorithme génétique va tirer parti des meilleurs éléments à sa disposition pour fabriquer de toutes pièces un nouvel ensemble d'éléments répondant en moyenne de mieux en mieux au problème.

Pour passer de l'ancien au nouvel ensemble, les éléments sont sélectionnés aléatoirement et proportionnellement à leur qualité en tant que solution au problème. Ainsi, le x que nous avons considéré comme maximum aura plus de chances d'être sélectionné que les autres éléments. S’il est retenu, il contribuera à améliorer les éléments du nouvel ensemble. Dans le cas contraire, il est irrémédiablement perdu pour les ensembles futurs.

Les éléments sélectionnés sont ensuite combinés en de nouveaux éléments grâce à des méthodes inspirées de phénomènes naturels, comme le croisement génétique ou la mutation. Les méthodes seront détaillées dans les chapitres suivants. Il suffit d'admettre, pour l'instant, que nous obtenons un nouvel ensemble de x auxquels nous appliquerons f pour déterminer le maximum de la génération 2.

L'algorithme génétique travaille ensuite par générations successives jusqu'à un critère d'arrêt :

• Soit le temps imparti est écoulé.
• soit le meilleur élément de la dernière génération atteint un seuil de qualité fixé au départ...
• Il rend alors une solution approchée et acceptable en un temps bien inférieur à celui qu'aurait demandé la recherche de la solution exacte du problème.

Ces programmes, suivant le problème à traiter, peuvent être la traduction d'une fonction arithmétique, d'une fonction logique, d'un chemin à suivre pour atteindre une cible... On pourra les représenter par des S-expressions à la LISP ou encore sous forme d'arbre :

1- Exemple : La fonction ((a+b)*c) se traduit par :

Le programme, résultant de la programmation génétique, nous permettra de connaître le meilleur chemin emprunté par la fourmi pour manger tous les aliments à partir de sa position initiale.

Les opérateurs génétiques utilisés pour la programmation génétique sont les mêmes que pour les algorithmes génétiques. Cependant, leur mise en œuvre peut s'avérer plus difficile du fait des données qu'ils manipulent.

Ainsi, la programmation génétique permet de résoudre un très grand nombre de problèmes et d'obtenir des solutions complexes sous forme de programmes. Les problèmes résolubles par cette méthode, sont tous les problèmes où interviennent un nombre fini d'opérations que l'on peut mettre sous la forme d'un programme et où l'on peut trouver une fonction d'évaluation.

L’un des problèmes les plus importants est le codage des données :

• c’est difficile de trouvée un bon codage adaptée à la structure du problème.
• L’application de la fonction de décodage lords l’évaluation de la fitness est coûteuse en temps de calcul.
• Les opérateurs de croisement et mutation ne tiennent aucun compte de la structure du problème.

La domination d’un chromosome provoque la disparition rapide de certains élément de la population, mais la méthode des AG présente plusieurs solutions contrairement a d’autres algorithmes comme recuit simulé qui présent une seule solution, alors il faut éliminer les chromosomes et laisser le meilleur (le mieux adapté).

 

L’un des problèmes des AG c’est la position de codage, par exemple : une propriété importante est codée dans une chaîne de 8 bits par le 1^er et le 8^th bit, dans ce cas tout croisement peut ce faire facilement mais si le codage est fait entre le 1^er et le 2^nd bit le croisement sera presque insensible.

C’est de ca ou vient l’idée de réorganisé les bits dans un chromosome de façon à crée des blocs stables.