Algo Genetique [PDF]

Zitiervorschau

ALGORITHMES GENETIQUES Encadré par : Mme Lebbar

PLAN DE PRESENTATION :

01

Historique et principes des AG

02

Notions de base et opérateurs d’évolution

03

Algorithme

04

05

06

Cas pratiques d’utilisation

Avantages et inconvénients

Conclusion

2

Introduction

Introduction Les algorithmes génétiques appartiennent à la famille des algorithmes évolutionnistes // évolutionnaires. Leur but est d'obtenir une approximation de la solution à un problème NP-complet par un mécanisme d'optimisation. Ils utilisent la notion de sélection naturelle développée au XIXe siècle par Darwin et l'appliquent à une population de solutions potentielles au problème donné.

Pourquoi avons-nous besoin des algorithmes génétiques? Complexité Problème trop complexes pour que l'on puisse proposer un algorithme

Tolérance aux variations Ce sont des algorithmes tolérants aux

Solution inconnue

variations de données, susceptibles de

Il n'y a aucune méthode exacte pour

s'adapter à une nouvelle situation, pour

résoudre le problème , ou on a une

qu'ils évoluent. Par exemple le déplacement d'un robot

modélisation délicate et/ou confuse où la solution au problème est inconnue

5

Historique et Principes des AG

Histoire

Charles Darwin publie son livre

1860

Intitulé L'origine des espèces au moyen de la sélection naturelle ou la lutte pour l'existence dans la nature et expose sa théorie de l'évolution des espèces

1975

John Holland Introduit le premier modèle formel des algorithmes génétiques dans son livre

Modèle repris par Goldberg

1989

Adaptation in Natural and Artificial Systems

Publiera un ouvrage de vulgarisation des algorithmes génétiques ce qui contribuera à la popularisation de ces derniers

7

Origine et principes des algorithmes génétiques

Le principe de variation Chaque individu au sein d’une population est unique. Ces différences, plus ou moins importantes, vont être décisives dans le processus de sélection.

Blog de Burak Kanber, ingénieur ayant fait des travaux sur le Machine Learning Travaux sur les optimisations et algorithmes génétiques

8

Origine et principes des AG

Le principe d'adaptation Les individus les plus adaptés à leur environnement atteignent plus facilement l'âge adulte. Ceux ayant une meilleure capacité de survie pourront donc se reproduire davantage.

Blog de Burak Kanber, ingénieur ayant fait des travaux sur le Machine Learning Travaux sur les optimisations et algorithmes génétiques

9

Origine et principes des AG

Le principe d’hérédité Les caractéristiques des individus doivent être héréditaires pour pouvoir être transmises à leur descendance. Ce mécanisme permettra de faire évoluer l’espèce pour partager les caractéristiques avantageuse à sa survie.

Blog de Burak Kanber, ingénieur ayant fait des travaux sur le Machine Learning Travaux sur les optimisations et algorithmes génétiques

10

Domaines d’utilisation Finance Prédiction de l'évolution d'une action.

Robotique Comportement intuitif et apprentissage.

Planning Obtenir le meilleur planning en fonction de dispositions.

Plan de table

Data Mining

Effectuer la meilleure disposition de

Création et utilisation de règles pour

table en fonction des affinités de

obtenir de nouvelles informations.

chacun. Blog de Burak Kanber, ingénieur ayant fait des travaux sur le Machine Learning Travaux sur les optimisations et algorithmes génétiques

11

Notions de base et opérateurs d’évolution

Notions de base: Fitness: La fonction objectif qui mesure l’adaptation de l’individu à son environnement local

Population

Individu

est l’ensemble des solutions envisageables. Chromosome

représente une solution. Il a deux représentations appelées phénotype et génotype. • Le phénotype :représente une solution potentielle du problème à optimiser en utilisant la formulation originale du problème. • Le génotype: donne une représentation codée d’une solution potentielle sous la forme d’un chromosome.

Source:Tarek Chaari. Un algorithme génétique pour l’ordonnancement robuste: application au problème du flow shop hybride. Automatique / Robotique. Université de Valenciennes et du Hainaut-Cambresis, 2010.

Gènes

13

Notions de base: est une représentation ou un codage d’une solution du problème donné.

Population

Individu

est une caractéristique, une particularité, qui peut prendre plusieurs valeurs, appelées "allèles". Xi

Chromosome

Source:Tarek Chaari. Un algorithme génétique pour l’ordonnancement robuste: application au problème du flow shop hybride. Automatique / Robotique. Université de Valenciennes et du Hainaut-Cambresis, 2010.

Gènes

14

Notions de base: Une première population est choisie soit aléatoirement, soit par des heuristiques ou par des méthodes spécifiques au problème, soit encore par mélange de solutions aléatoires et heuristiques. Cette population doit être suffisamment diversifiée pour que l’algorithme ne reste pas bloqué dans un optimum local. C’est ce qui se produit lorsque trop d’individus sont semblables. Les algorithmes génétiques génèrent de nouveaux individus, de telle sorte qu’ils soient plus performants que leurs prédécesseurs. Le processus d’amélioration des individus s’effectue par utilisation d’opérateurs génétiques, qui sont la sélection, le croisement et la mutation.

Codage des solutions La première particularité des AG réside dans le fait qu'ils n'agissent pas directement sur l'espace des solutions : les solutions sont codées. Le codage permet de représenté l’individu sous la forme d’un chromosome. Ce chromosome est constitué de gènes qui prennent des valeurs dans un alphabet binaire ou non, ça dépend du choix du codage qui est délicat. Il doit permettre de coder toutes les solutions et permettre la mise en œuvre des opérateurs de reproduction. C’est ainsi que le bon déroulement des algorithmes génétiques sera assuré. Plusieurs type de codages sont utilisés, on citera à titre d'exemple:  Codage binaire X : {00000 11111} //  Codage réel

: X { 1 4 5 2 …}

Source: Terki Amel. Analyse des performances des algorithmes génétiques utilisant différentes techniques d’évolution de la population. Universite Mentouri, 2006.

16

Notations Pb Optimisation combinatoire : vecteur des variables de décision S : l’ensemble des solution réalisables qui respectent les contraintes Min f( )

S

f : capacités d’adaptation des individus The Power of PowerPoint | thepopp.com

17

Codage des solutions

Chromosome A 1

0

0

Codage binaire 0

1

0

1

1 • Les AG utilisent généralement la représentation binaire;

Chromosome B 0

0

1

• Dans le codage binaire le gène est codé par un caractère binaire, 0

0

1

1

1

0

ou 1; • Un des avantages du codage binaire est que l’on peut ainsi facilement coder toutes sortes d’objets : des réels, des entiers, des valeurs booléennes, des chaînes de caractères

Source: Terki Amel. Analyse des performances des algorithmes génétiques utilisant différentes techniques d’évolution de la population. Universite Mentouri, 2006.

18

Codage des solutions

Codage réel • Dans ce codage le chromosome est un vecteur réel et l’espace de recherche est un sous-ensemble de IR • Très utilisée dans les problèmes d’optimisation car dans de nombreuses applications du monde réel, ces problèmes sont naturellement formulés sous forme paramétrique.

Source: Terki Amel. Analyse des performances des algorithmes génétiques utilisant différentes techniques d’évolution de la population. Universite Mentouri, 2006.

19

Codage binaire vs Codage réel  Historiquement, le codage utilisé par les algorithmes génétiques était le codage binaire. C’est en utilisant ce type de codage que les premiers résultats de convergence théorique ont été obtenus. Cependant, ce type de codage n’est pas toujours bon.  Pour des problèmes d’optimisation dans des espaces de grande dimension, le codage binaire peut rapidement devenir mauvais. Généralement, chaque variable est représentée par une partie de la chaîne de bits et la structure du problème n’est pas bien reflétée, l’ordre des variables ayant une importance dans la structure du chromosome, alors qu’il n’en a pas forcément dans la structure du problème.  Les algorithmes génétiques utilisant des vecteurs réels évitent ce problème en conservant les variables du problème dans le codage de l’élément de population, sans passer par le codage binaire intermédiaire.

 Les codages réels sont désormais largement utilisés, notamment dans les domaines applicatifs, pour l’optimisation de

.

problèmes à variables continues

Source: Nicolas Durand. Algorithmes Génétiques et autres méthodes d’optimisation appliqués à la gestion de trafic aérien. Optimisation et contrôle. INPT, 2004.

20

Sélection

Sélection par rang Une sélection est opérée pour déterminer quels individus sont plus enclins à obtenir les meilleurs résultats.

Sélection par roulette

Sélection par tournoi

Sélection aléatoire

21

Sélection par rang

Cette méthode consiste à ranger les individus de la population dans un ordre croissant ou décroissant, selon l’objectif (fonction fitness) On prélève ensuite la nouvelle population à partir d’ensemble d’individus ordonnés en utilisant des probabilités indexées sur les rangs des individus.

La probabilité de sélection =

Source: Terki Amel. Analyse des performances des algorithmes génétiques utilisant différentes techniques d’évolution de la population. Universite Mentouri, 2006.

22

Sélection par roulette La Sélection par roulette consiste à attribuer à chaque individu une probabilité de survie proportionnelle à son adaptation dans la population. Lors de la phase de sélection, les individus sont sélectionnés aléatoirement en respectant les probabilités Probi associées pour former la population de la nouvelle génération.

Cette méthode consiste à dupliquer chaque individu de la population proportionnellement à son milieu. Ainsi, les individus ayant la plus grande valeur de fitness Fi auront plus de chance d'être choisis.

Source: Terki Amel. Analyse des performances des algorithmes génétiques utilisant différentes techniques d’évolution de la population. Universite Mentouri, 2006.

23

Sélection par roulette (suite)

En utilisant cette probabilité de reproduction, on crée une roue de loterie biaisée. Chaque individu de la population occupe une section de la roue proportionnellement à son adaptation et qui indique Exemple de sélection par roulette

aléatoirement quel individu peut se reproduire.

Source: Terki Amel. Analyse des performances des algorithmes génétiques utilisant différentes techniques d’évolution de la population. Universite Mentouri, 2006.

24

Sélection par tournoi Le principe de cette méthode consiste à choisir une sous population, de taille M fixée à priori par l’utilisateur, aléatoirement. L’individu de meilleure qualité par rapport à la sous population sera sélectionné pour l’application de l’opérateur de croisement. En effet c’est une compétition entre les individus d’une sous population de taille M (M≤N). Cette méthode donne plus de chance aux individus de mauvaise qualité de participer à l’amélioration de la qualité de la population.

Source: Jean-Marc Alliot, Nicolas Durand. Algorithmes génétiques.

Le paramètre M joue un rôle important dans la méthode du tournoi. Dans le cas où M=N avec N qui est la taille de la population, le résultat par la sélection de tournoi donne à chaque fois un seul individu qui est le meilleur individu par rapport à la valeur de la fonction objectif, ce qui réduit l’algorithme génétique à un algorithme de recherche locale. Dans le cas où M=1, la sélection correspond à la sélection aléatoire. Source: Radhia Zaghdoud. Hybridation d’algorithme génétique pour les problèmes des véhicules intelligents autonomes : applications aux infrastructures portuaires de moyenne taille. Automatique. Ecole Centrale de Lille, 2015.

25

Sélection aléatoire

Cette sélection se fait aléatoirement, uniformément et sans intervention de la valeur d’adaptation. Chaque individu a donc une probabilité uniforme 1/Psize d’être sélectionné, où Psize est le nombre total d’individus dans la population.

 Voici un exemple avec des individus en représentation binaire une fois la sélection effectuée :

Source: Tarek Chaari. Un algorithme génétique pour l’ordonnancement robuste: application au problème du flow shop hybride. Automatique / Robotique. Université de Valenciennes et du Hainaut-Cambresis, 2010. Français.

26

Le croisement (crossover):

Le croisement est un opérateur de recombinaison permettant d’enrichir la population en manipulant les composantes des chromosomes. Un croisement est envisagé avec deux parents et génère un ou deux enfants. Il est appliqué avec une probabilité Pcross, appelée probabilité de croisement. Après la sélection de deux individus, nous générons un nombre aléatoire α

[0, 1]. Si α ≤ Pcross, nous appliquons l’opérateur de croisement sur les deux parents.

Source:Tarek Chaari. Un algorithme génétique pour l’ordonnancement robuste: application au problème du flow shop hybride. Automatique / Robotique. Université de Valenciennes et du Hainaut-Cambresis, 2010.

27

Le croisement:

Croisement en 1-point : Si le chromosome est une chaîne binaire de longueur n. Le croisement à un point place un point de croisement au hasard. Un enfant prend une section avant le point de croisement d’un parent et prend l’autre section après le point de croisement de l’autre parent puis recombine les deux sections en maintenant l’ordre des gènes, pour former une nouvelle chaîne binaire. Et inversement pour l’enfant2.

Source: MÉTAHEURISTIQUES POUR L’OPTIMISATION DIFFICILE

28

Le croisement:

Croisement en 2-points : Ce type de croisement est utilisé en choisissant aléatoirement 2 points de coupure pour dissocier chaque parent en 3 fragments. Les 2 fragments en extrémités pour le Parent1 (respectivement Parent2 ) sont copiés à l’Enfant1 (respectivement Enfant2 ). On complète la partie restante de l’Enfant1 par les éléments du Parent2 et la partie restante de l’Enfant2 par les éléments du Parent1 en balayant de gauche à droite et en ne reprenant que les éléments non encore transmis Source:Tarek Chaari. Un algorithme génétique pour l’ordonnancement robuste: application au problème du flow shop hybride. Automatique / Robotique. Université de Valenciennes et du Hainaut-Cambresis, 2010.

29

Le croisement:

Parent 1

Croisement uniforme : Enfant

Il consiste à choisir avec la même probabilité un allèle de l’un ou de l’autre parent, pour transmettre sa valeur à la même position, aux enfants. Parent 2 Source:MÉTAHEURISTIQUES POUR L’OPTIMISATION DIFFICILE

30

Remarque Plus le nombre de points de croisements sera grand et plus la probabilité de croisement sera élevée plus il y aura d'échange de segments, donc d'échange de paramètres, d'information, et plus le nombre de points de croisements sera petit et plus la probabilité de croisement sera faible, moins le croisement apportera de diversité.

La mutation Conformément à la mutation naturelle, Cet opérateur permet de changer la valeur d’un chromosome dans le but d’améliorer les caractéristiques de l’individu. Il est utilisé avec une probabilité Pmut. Si β, généré aléatoirement, appartient à [0, Pmut], nous appliquons l’opérateur de mutation sur cet individu Il modifie donc de manière complètement aléatoire les caractéristiques d'une solution, ce qui permet d'introduire et de maintenir la diversité au sein de notre population de solutions. Cet opérateur joue le rôle d'un "élément perturbateur", il introduit du "bruit" au sein de la population.

ALGORITHMES GENETIQUES TE de fin d’année présenté par Souquet Amédée et Radet Francois-Gérard

32

Méthodes de mutation

Opérateur d’inversion simple

Opérateur d’échange réciproque

Cet opérateur consiste à choisir aléatoirement deux

C’est un opérateur qui permet de sélectionner deux

points de coupure et inverser les positions des gènes

gènes et de les changer.

situées au milieu

Tarek Chaari. Un algorithme génétique pour l’ordonnancement robuste: application au problème du flow shop hybride. Automatique / Robotique. Université de Valenciennes et du Hainaut-Cambresis, 2010. Français.

33

Méthodes de mutation Opérateur d’insertion : Cet opérateur consiste à sélectionner au hasard un gène et une position dans le chromosome à muter, puis à insérer le gène sélectionné dans la position choisie .

Tarek Chaari. Un algorithme génétique pour l’ordonnancement robuste: application au problème du flow shop hybride. Automatique / Robotique. Université de Valenciennes et du Hainaut-Cambresis, 2010. Français.

34

Avantages de la mutation Atteindre la propriété d'ergodicité

Garantir une diversité de la population

C’est la propriété garantissant que chaque

Ce qui est primordial pour les algorithmes

point de l'espace de recherche puisse être

génétiques

atteint et d’explorer efficacement l’espace de recherche.

Limiter les risques d'une convergence prématurée

Eviter le phénomène de dérive génétique

Dans le cas d'une convergence prématurée on

On parle de dérive génétique quand certains

se retrouve avec une population dont tous les

gènes favorisés par le hasard se répandent au

individus sont identiques mais ne sont que des

détriment des autres et sont ainsi présents au

optimums locaux. Tous les individus étant

même endroit sur tout les chromosomes

identiques, le croisement ne changera rien à la situation

ALGORITHMES GENETIQUES TE de fin d’année présenté par Souquet Amédée Radet Francois-Gérard

35

Algorithme :

Architecture générale d’un algorithme génétique Générer un ensemble de solutions initiales Aléatoire : génération 1

Insertion

Rare

Choix des chromosomes Individus : parents

Générer les chromosomes des enfants

Source: Radhia Zaghdoud. Hybridation d’algorithme génétique pour les problèmes des véhicules intelligents autonomes : applications aux infrastructures portuaires de moyenne taille. Automatique. Ecole Centrale de Lille, 2015.

37

Aperçu de l'algorithme génétique de base 1. [Start] Générer aléatoirement une population de n chromosomes; 2. [Fitness] Evaluer la fonction objectif ou fitness f(x) de chaque chromosome x dans la population; 3. [New population] Créer une nouvelle population en réitérant les mêmes étapes jusqu’à ce que la nouvelle population soit compléter [Selection] Sélectionner deux parents de la population selon leur fitness (the better fitness, the bigger chance to be selected) [Crossover] Avec une probabilité de croisement, on croise les parents pour former de nouveaux individus (enfants). Si aucun croisement n’est effectué, les nouveaux individus sont une exacte copie des parents [Mutation] Avec une probabilité de mutation, on altère aléatoirement les particularités d'un individu [Accepting] Insérer les nouveaux individus dans la nouvelle population 4. [Replace] Utiliser la nouvelle population pour une compilation ultérieure de l’algorithme 5. [Test] Si le critère d’arrêt est satisfait, stop, et retourner la meilleure solution dans la population actuel 6. [Loop] Aller à l’etape 2

Source: Marek Obitko. Genetic algorithms tutorials,1998.

38

Insertion Choisir les Psize individus à partir des Psize enfants déjà créés par les opérateurs de croisement et de mutation. Dans ce cas, les parents sont remplacés par les enfants mutés.

Choisir les Psize individus à partir des Psize parents de la population précédente et de Psize nouveaux enfants. A chaque itération, les individus ayant les meilleures fitness seront sélectionnés afin de créer des individus fils qui remplaceront les plus mauvais parents. Le reste survit et sera copié dans la nouvelle génération.

L’élitisme , consiste à copier quelques meilleurs individus dans la nouvelle population. L’objectif est d’éviter que les meilleurs individus soient perdus après les opérateurs de croisement et de mutation. Cette méthode permet de conserver, à une itération donnée, le meilleur individu trouvé dans toutes les populations générées antérieurement.

Source: Tarek Chaari. Un algorithme génétique pour l’ordonnancement robuste: application au problème du flow shop hybride. Automatique / Robotique. Université de Valenciennes et du Hainaut-Cambresis, 2010. Français.

39

La fin de l’algorithme

Condition d’arrêt Le test d’arrêt joue un rôle très important dans le jugement de la qualité des individus. Les critères d’arrêt sont de deux types : Arrêt après un nombre fixé a priori de générations ; Arrêt lorsque la population cesse d’évoluer ou n’évolue plus suffisamment.

Source: Tarek Chaari. Un algorithme génétique pour l’ordonnancement robuste: application au problème du flow shop hybride. Automatique / Robotique. Université de Valenciennes et du Hainaut-Cambresis, 2010. Français.

40

Cas pratiques d’utilisation Exemple de Goldberg (1989) Modélisation du PVC sous MATLAB Application industrielle

Exemple de Goldberg (1989)

Enoncé: Il consiste à trouver le maximum de la fonction f(x)=x sur l’intervalle [0, 31] où x est un entier. La première étape consiste à coder la fonction. Par exemple, nous utilisons un codage binaire de x, la séquence (chromo-some) contenant au maximum 5 bits. Ainsi, nous avons de même . x=2->{0,0,1,0} et x=31->{1,1,1,1,1} Nous recherchons donc le maximum d’une fonction de « fitness » dans un espace de 32 valeurs possibles de x Source:MÉTAHEURISTIQUES POUR L’OPTIMISATION DIFFICILE

42

Exemple de Goldberg (1989)

Tirage et évaluation de la population initiale: Numéro

Total

Séquence

Fitness

% du total

Nous fixons la taille de la population à N = 4.

1

00101

5

14,3

Nous tirons donc de façon aléatoire 4

2

10000

16

45,7

chromosomes sachant qu’un chromosome

3

00010

2

5,7

est composé de 5 bits et que chaque bit

4

01100

12

34,3

35

100

dispose d’une probabilité 1/2 d’avoir une valeur 0 ou 1.Le maximum, 16, est atteint par la deuxième séquence.

Source:MÉTAHEURISTIQUES POUR L’OPTIMISATION DIFFICILE

43

Exemple de Goldberg (1989)

La sélection: Numéro

Séquence

Une nouvelle population va être créée à partir de l’ancienne par le processus de sélection

1

10000

2

01100

3

00101

nouvelle population décrite dans le tableau

4

10000

suivant:

de la roue de loterie biaisée. Nous tournons cette roue 4 fois et nous obtenons au final la

Nouvelle population Source:MÉTAHEURISTIQUES POUR L’OPTIMISATION DIFFICILE

44

Exemple de Goldberg (1989)

Le croisement: Les parents sont sélectionnés au hasard. Nous tirons

Parents 1 I=3 100|00 001|01 10001 00100

Parents 2 I=2

aléatoirement un lieu de croisement (site ou locus)

01|100 10|000

lieu avec une probabilité Pcross. Le tableau suivant

01000 10100

dans la séquence. Le croisement s’opère alors à ce donne les conséquences de cet opérateur en supposant que les chromosomes 1 et 3, puis 2 et 4 sont appariés et qu’à chaque fois le croisement s’opère (par exemple avec Pcross = 1).

Source:MÉTAHEURISTIQUES POUR L’OPTIMISATION DIFFICILE

45

Exemple de Goldberg (1989)

La mutation: Tirage Ancien chromosome aléatoire

Dans cet exemple à codage binaire, la mutation

10001

00010

Nouve Nouveau au bit chromoso consiste à inverser un bit .Nous tirons ainsi pour me chaque bit un chiffre aléatoire entre 0 et 1 et si ce 1 10011

00100

00000

-

00100

s’opère. Le

01000

00000

-

01000

tableau 3, avec Pm = 0,05, met en évidence ce

10100

01000

chiffre est inférieur à Pm alors la mutation

1

11100

processus

Source:MÉTAHEURISTIQUES POUR L’OPTIMISATION DIFFICILE

46

Exemple de Goldberg (1989)

Retour à la phase d’évaluation: Numéro

Séquence Fitness

% du total

Le maximum est maintenant de 28 (séquence 4). Donc, nous sommes passés

1

10011

32,2

2

00100

6,8

sûr, nous devons recommencer la procédure

3

01000

13,5

à partir de l’étape de sélection jusqu’à ce

4

11100

47,5

Total

de 16 à 28 après une seule génération. Bien

que le maximum global, 31, soit obtenu, ou bien qu’un critère d’arrêt ait été satisfait

100 Source:MÉTAHEURISTIQUES POUR L’OPTIMISATION DIFFICILE

47

Problème du voyageur de commerce (PVC) C'est sous forme de jeu que William Rowan Hamilton a posé pour la première fois ce problème, dès 1859. Sous sa forme la plus classique, son énoncé est le suivant : « Un voyageur de commerce doit visiter une et une seule fois un nombre fini de villes et revenir à son point d’origine. Trouvez l’ordre de visite des villes qui minimise la distance totale parcourue par le voyageur »

Modélisation du PVC sous MATLAB Source: Shravan Kumar. Travelling Sales Man Problem MATLAB code.Youtube, 2016.

Source: Yifang Li, Yannick Kergosien et Jean-Charles Billaut. Le problème du voyageur de commerce. Université de Tours, 2008.

48

PVC Démarche suivie 1. On génère aléatoirement une population de 500 individus (séquence des villes parcouru). 2. On crée une boucle de génération c.-à-d. le nombre de fois que l’algorithme sera exécuté avant de trouver le résultat optimal. 3. Lors de chaque génération :  On crée la matrice des distances ;  On calcul le fitness « la longueur du cycle parcouru par le voyageur » ;  On tri les résultats dans l’ordre croissant ;  On augmente la population, on rajoutant de nouveaux individus grâce à l’opérateur de croisement ;  On réévalue le fitness ;  On sélectionne le meilleur résultat et on plot. : garde les 500 meilleurs  On réitère

Source: Shravan Kumar. Travelling Sales Man Problem MATLAB code.Youtube, 2016.

49

Résolution du problème d’affectation des conteneurs aux Véhicules Autonomes Etude du problème d’affectation des tâches aux AIVs Le problème d'affectation des tâches aux AIVs dans un terminal à conteneurs est un problème complexe, il s’agit d’une combinaison de trois sous problèmes ; le problème de répartition des tâches, le problème de routage des véhicules et le problème d'ordonnancement des tâches. Chaque sous problème dépend de certains critères tels que ; l'infrastructure du port, en particulier le réseau routier, la limitation de charge électrique des véhicules à cause de leurs autonomies et la date d'arrivée et de départ du navire. Ces facteurs rendent le problème global multicritères. Radhia Zaghdoud. Hybridation d’algorithme génétique pour les problèmes des véhicules intelligents autonomes : applications

aux infrastructures portuaires de moyenne taille. Automatique. Ecole Centrale de Lille, 2015. Français.

50

Approche • Pour résoudre ce problème global, l'idée proposée consiste à étudier chaque sous problème sous forme d'un problème monocritère . • Le makespan de ce problème dépend de trois facteurs : la distance totale parcourue par tous les AIVs, la durée totale de travail pour chaque AIV et la date de traitement de chaque tâche. • Le problème global peut être assimilé à un problème d’ordonnancement des tâches à des machines. Une tâche est représenté l’opération de déplacer un conteneur de sa position initiale vers sa position finale et le véhicule joue le rôle d’une machine • Il peut être aussi assimilé à un problème de tournée de véhicules VRP dont chaque véhicule doit faire un nombre des allez et retour d’un dépôt de chargement vers un dépôt de déchargement et inversement, ce qui peut représenter une tournée. L’ensemble des taches des véhicules sera un ensemble de tournées (VRP)

Radhia Zaghdoud. Hybridation d’algorithme génétique pour les problèmes des véhicules intelligents autonomes : applications aux infrastructures portuaires de moyenne taille. Automatique. Ecole Centrale de Lille, 2015. Français.

51

Le codage Une solution sera représentée par une liste d’éléments. Chaque élément est composé d'une tâche, d’un AIV affecté à cette tâche et du rang de la tâche dans la liste des tâches de l’AIV.

 Ti est la tâche à exécuter,  Aj est l’AIV qui va déplacer cette tâche et  Rk est le rang de la tâche dans la liste des tâches de l'AIV Aj.

Radhia Zaghdoud. Hybridation d’algorithme génétique pour les problèmes des véhicules intelligents autonomes : applications aux infrastructures portuaires de moyenne taille. Automatique. Ecole Centrale de Lille, 2015. Français.

52

La sélection

• Les individus de la population initiale et les individus de croisement sont sélectionnés aléatoirement. • Ensuite, le descendant ayant une valeur de la fonction coût qui est meilleure que celles de ses parents, va remplacer l’un de ses parents. •

Également pour l’individu après mutation, il sera inséré dans la population si la valeur de sa fonction coût est meilleure que celle avant la mutation.

• Pour choisir les individus qui survivront, nous appliquons la méthode de sélection de la roulette grâce à la variété qu’elle peut assurer à la nouvelle population

Radhia Zaghdoud. Hybridation d’algorithme génétique pour les problèmes des véhicules intelligents autonomes : applications aux infrastructures portuaires de moyenne taille. Automatique. Ecole Centrale de Lille, 2015. Français.

53

Le croisement Le croisement doit se faire entre deux individus. Opérateurs de croisement adaptés au problème : génèrent des enfants qui représentent des X  S L'opération consiste à modifier la répartition des tâches entre les AIVs afin de trouver des descendants ayant une valeur de la fonction coût meilleure que celles de leurs parents. Par exemple on a deux individus, le parent P1 et le parent P2 présentant l’affectation de 3 tâches sur 2 AIVs. Nous choisissons le croisement à point.

Radhia Zaghdoud. Hybridation d’algorithme génétique pour les problèmes des véhicules intelligents autonomes : applications aux infrastructures portuaires de moyenne taille. Automatique. Ecole Centrale de Lille, 2015. Français.

54

La correction du croisement

• En étudiant les représentations des deux descendants de cette opération de croisement, on remarque des anomalies de formation, ce qui nécessite une opération de correction. Pour le descendant D1, la tâche T1 se répète deux fois par contre la tâche T2 n’existe pas. Pour le descendant D2, la tâche T2 se répète deux fois mais la tâche T1 est absente. Ensuite, il faut corriger l’ordre de chaque tâche. • C'est donc une opération qui consiste à vérifier si, une tâche n'est pas affectée à un AIV et s’il existe des tâches qui sont présentent plus qu’une fois. Dans ce cas, la tâche qui est répétée sera remplacée par celle qui ne l'est pas. Le classement des tâches est également modifié, il faut donc corriger ce rang en se référant à la date de début de la tâche.

Radhia Zaghdoud. Hybridation d’algorithme génétique pour les problèmes des véhicules intelligents autonomes : applications aux infrastructures portuaires de moyenne taille. Automatique. Ecole Centrale de Lille, 2015. Français.

55

La mutation Elle est faite pour changer l'affectation d'une tâche d'un AIV à un autre Par exemple :

Parfois ,une correction de la mutation similaire à la correction de croisement doit être effectuée. Mais dans cette opération, le risque de perte de tâches ou des tâches répétitives n’existe pas. Elle consiste seulement à corriger les rangs des tâches pour chaque AIV. Il faut seulement corriger ce rang en se référant à la date de début de la tâche

Radhia Zaghdoud. Hybridation d’algorithme génétique pour les problèmes des véhicules intelligents autonomes : applications aux infrastructures portuaires de moyenne taille. Automatique. Ecole Centrale de Lille, 2015. Français.

56

Application Premier individu I1

C1 AIV2

C4 AIV1

C7 AIV3

C8 AIV1

C3 AIV2

C2 AIV2

C5 AIV3

C6 AIV1

Deuxième individu I2

C1 AIV1

C2 AIV1

C3 AIV3

C8 AIV1

C4 AIV2

C5 AIV3

C6 AIV2

C7 AIV1

 Après le croisement Descendant D1

C1 AIV2

C4 AIV1

C7 AIV3

C8 AIV1

C4 AIV2

C5 AIV3

C6 AIV2

C7 AIV1

Descendant D2

C1

C2

C3

C8

C4

C5

C6

C7

AIV1

AIV1

AIV3

AIV1

AIV2

AIV2

AIV3

AIV1

Radhia Zaghdoud. Hybridation d’algorithme génétique pour les problèmes des véhicules intelligents autonomes : applications aux infrastructures portuaires de moyenne taille. Automatique. Ecole Centrale de Lille, 2015. Français.

57

Correction du croisement et mutation Descendant D1 C1 AIV2

C4 AIV1

C7 AIV3

C8 AIV1

C4 AIV2

C5 AIV3

C6 AIV2

C7 AIV1

C1

C2

C3

C8

C4

C5

C6

C7

AIV1

AIV1

AIV3

AIV1

AIV2

AIV2

AIV3

AIV1

C1 AIV2

C4 AIV1

C7 AIV1

C8 AIV1

C4 AIV2

C5 AIV3

C6 AIV2

C7 AIV1

Descendant D2

Radhia Zaghdoud. Hybridation d’algorithme génétique pour les problèmes des véhicules intelligents autonomes : applications aux infrastructures portuaires de moyenne taille. Automatique. Ecole Centrale de Lille, 2015. Français.

58

Etude empirique

Données Nous avons testé l’approche génétique avec différents nombres de tâches et différents nombres d’AIVs. Les paramètres de l'algorithme génétique sont les suivants: 70% de la population est choisi pour le croisement et 10% pour la mutation. Le graphe représente la variation du coût total en fonction du nombre de générations.

Radhia Zaghdoud. Hybridation d’algorithme génétique pour les problèmes des véhicules intelligents autonomes : applications aux infrastructures portuaires de moyenne taille. Automatique. Ecole Centrale de Lille, 2015. Français.

59

Conclusion • L'approche génétique converge vers une solution optimale. • Cette convergence est autour de la génération 70 pour 20 tâches, mais elle est un peu plus tard, autour de la 80eme génération pour 40 tâches et la 90eme génération pour 60 tâches. • La valeur de la fonction objectif varie selon le nombre de tâches, elle augmente lorsque le nombre de tâches augmente et inversement. • Par exemple, dans le test avec 20 tâches et 40 tâches, le nombre d’AIVs est le même, mais les valeurs de la fonction objectif sont différentes. La valeur correspondante à 40 tâches est plus grande que celle pour 20 tâches. •

Ce résultat est justifié parce que pour transporter 40 conteneurs de leurs positions initiales vers leurs positions finales, nous avons besoin de plus de temps que pour transporter 20 conteneurs.

Radhia Zaghdoud. Hybridation d’algorithme génétique pour les problèmes des véhicules intelligents autonomes : applications aux infrastructures portuaires de moyenne taille. Automatique. Ecole Centrale de Lille, 2015. Français.

60

Résolution du problème d’ordonnancement flow shop

Le codage: de longueur égale au nombre total de jobs à réaliser.

L’individu : est représenté par une séquence de jobs. • Cette séquence est appliquée seulement au premier étage. • De l’étage 2 à l’étage k: les jobs sont ordonnés selon leurs dates d’achèvement minimales de l’étage précédent. Source:Tarek Chaari. Un algorithme génétique pour l’ordonnancement robuste: application au problème du flow shop hybride. Automatique / Robotique. Université de Valenciennes et du Hainaut-Cambresis, 2010.

61

Résolution du problème d’ordonnancement flow shop

Etape 1:Fonction d’évaluation ( fitness) La fonction d’évaluation consiste à minimiser le makespan (noté Cmax). Cjt désigne le temps d’achèvement du job j dans l’étage t.

Etape 2:Génération d’une population initiale La procédure que nous avons utilisée pour générer la population initiale des individus, est une génération aléatoire de Psize individus. C’est le meilleur choix, car il permet l’hétérogénéité de la population.

Source:Tarek Chaari. Un algorithme génétique pour l’ordonnancement robuste: application au problème du flow shop hybride. Automatique / Robotique. Université de Valenciennes et du Hainaut-Cambresis, 2010.

Etape 3:Opérateur de sélection • La méthode utilisée est la sélection aléatoire. • Chaque individu a donc une probabilité uniforme (1/Psize) d’être sélectionné

62

Résolution du problème d’ordonnancement flow shop Etape 4:Opérateur de croisement

Etape 5:Opérateur de mutation

Nous utiliserons l’opérateur de croisement en 2-

L’opérateur de mutation utilisé est l’opérateur

points.

d’insertion.

Etape 6:Opérateur d’insertion

Etape 7:Critère d’arrêt

L’insertion dans le contexte de l’ordonnancement est employée pour réduire au minimum la fonction fitness.

Le critère d’arrêt utilisé est le nombre de générations égal à

Cette insertion permet d’éliminer de la population les chromosomes les plus faibles.

Après IterMax générations, l’algorithme génétique s’arrête et

IterMax.

donne le meilleur chromosome qui possède un Cmax minimum.

Source:Tarek Chaari. Un algorithme génétique pour l’ordonnancement robuste: application au problème du flow shop hybride. Automatique / Robotique. Université de Valenciennes et du Hainaut-Cambresis, 2010.

63

Avantages et inconvénients

Avantages

L’utilisation d’une fonction objectif (fitness) indépendamment de sa nature ; convexe, continue et dérivable lui donne plus de souplesse et un large domaine d’application. La probabilité de croisement et de mutation permettent parfois d’éviter de tomber dans un optimum local et se diriger vers l’optimum global. Les algorithmes génétiques présentent par rapport aux algorithmes de type recuit simulé (1 solution) plusieurs solutions viables (plusieurs de bonne qualité) , et non une seule, au terme d’une exécution du programme. Il faut donc éviter l’élimination de tous les individus au bénéfice d’un seul, même s’il est mieux adapté. Source:Tarek Chaari. Un algorithme génétique pour l’ordonnancement robuste: application au problème du flow shop hybride. Automatique / Robotique. Université de Valenciennes et du Hainaut-Cambresis, 2010.

65

Inconvénients

Le temps de calcul long : par rapport à d'autres métaheuristiques, les AG nécessitent de nombreux calculs, en particulier au niveau de la fonction d'évaluation. Ils sont le plus souvent difficiles à mettre en œuvre : des paramètres comme la taille de la population ou le taux de mutation sont parfois difficiles à déterminer. Matlab …. L'impossibilité

d'être

assuré,

même

après

un

nombre

important

de

générations, que la solution trouvée soit la meilleure. On peut seulement être sûr que l'on s'est approché de la solution optimale.

Source: Wiképedia « Algorithme Génétique»

66

Conclusion

Récapitulatif Les origines de l’algorithme génétique S’inspire de la théorie

Les notions de base

darwinienne de l'évolution.

01

 Fitness

Les opérateurs

 Population  Individu  Chromosome  Gène

02

 Sélection  Croisement  Mutation

03

L’architecture d’un AG

04

68

Architecture générale d’un algorithme génétique

Insertion

Source: Radhia Zaghdoud. Hybridation d’algorithme génétique pour les problèmes des véhicules intelligents autonomes : applications aux infrastructures portuaires de moyenne taille. Automatique. Ecole Centrale de Lille, 2015.

69

Merci pour votre attention

Bibliographie  Blog de Burak Kanber, ingénieur ayant fait des travaux sur le Machine Learning.  Travaux sur les optimisations et algorithmes génétiques.  Tarek Chaari. Un algorithme génétique pour l’ordonnancement robuste: application au problème du flow shop hybride. Automatique / Robotique. Université de Valenciennes et du Hainaut-Cambresis, 2010.  Terki Amel. Analyse des performances des algorithmes génétiques utilisant différentes techniques d’évolution de la population. Universite Mentouri, 2006.  Jean-Marc Alliot, Nicolas Durand. Algorithmes génétiques.  Yifang Li, Yannick Kergosien et Jean-Charles Billaut. Le problème du voyageur de commerce. Université de Tours, 2008.  Marek Obitko. Genetic algorithms tutorials, 1998.  Nicolas Durand. Algorithmes Génétiques et autres méthodes d’optimisation appliqués à la gestion de trafic aérien. Optimisation et contrôle. INPT, 2004.

71

Bibliographie  Radhia Zaghdoud. Hybridation d’algorithme génétique pour les problèmes des véhicules intelligents autonomes : applications aux infrastructures portuaires de moyenne taille. Automatique. Ecole Centrale de Lille, 2015.  MÉTAHEURISTIQUES POUR L’OPTIMISATION DIFFICILE.  TE de fin d’année présenté par Souquet Amédée Radet Francois-Gérard. ALGORITHMES GENETIQUES.  Shravan Kumar. Travelling Sales Man Problem MATLAB code.Youtube, 2016.  Wiképedia « Algorithme Génétique».  Hanaa Hachimi. Hybridations d’algorithmes Meta-heuristiques en optimisation globale et leurs applications. INSA de Rouen; Ecole Mohammadia d’ingénieurs (Rabat, Maroc), 2013.  Imen Boulnemour. Optimisation par Essaim de Particules Quantiques et ses Nouvelles Hybridations pour le Clustering des Données. Département d’informatique, Université du 20 août 1955 de Skikda. Algérie, 2013.

72