MÉTAHEURISTIQUES : LES ALGORITHMES GÉNÉTIQUES ET L'OPTIMISATION PAR ESSAIMS PARTICULAIRES

MÉTAHEURISTIQUES : LES ALGORITHMES GÉNÉTIQUES ET L’OPTIMISATION PAR ESSAIMS PARTICULAIRES

Le croisement

Le croisement permet, par la manipulation de la structure des chromosomes,l’enrichissement de la population. Il consiste en un échange de gènes entre deux ou plusieurs chromosomes afin d’en former de nouveaux. Classiquement, les croisements impliquent deux parents qui génèrent un ou deux enfants. Selon Davis [1991], c’est le croisement (encore appelé recombinaison ou crossover) qui fait la force des AG. Il s’agit de sélectionner deux individus parmi les parents potentiels, aléatoirement ou à l’aide d’une des méthodes de sélection pour la reproduction. Ces derniers sont croisés suivant une probabilité pcroiS appelée probabilité de croisement afin d’obtenir de nouveaux individus appelés ‘enfants’. Parfois, les ‘bons’ gènes d’un parent se substituent aux ‘mauvais’ gènes
de l’autre pour former un meilleur descendant. La probabilité de croisement est plus ou moins élevée dans les AG. Elle varie souvent entre 0,7 et 1 [Yang 2008].Il existe plusieurs méthodes de croisement en fonction de la méthode de représentation des solutions. Pour la représentation par permutation, les méthodes suivantes peuvent être citées : le croisement à un ou plusieurs points, le croisement partiellement tracé (PMX), le croisement par ordre (OX), le croisement par cycle (CX) et le croisement par recombinaison d’arêtes (ERX).
Le croisement à un point [Holland 1962] consiste à choisir aléatoirement, sur les chromosomes parents, un point de croisement à partir duquel ceux-ci échangent leurs gènes. Il faut noter que le croisement s’effectue au niveau des gènes, ce qui permet de couper les chromosomes à n’importe quel niveau. Il existe aussi des croisements multipoints. Le plus courant, le croisement à deux points, consiste à choisir aléatoirement deux points sur les chromosomes ‘Parents’ et à échanger les gènes compris entre ces deux points. Dans le cas de la représentation de solutions par permutation des gènes, ces méthodes de croisement entraînent à coup sûr la formation de solutions non viables (répétition de certains gènes et suppression d’autres). Reeves [1995] définit une technique générale de croisement (à un ou plusieurs points) pour la représentation des solutions par permutation. La Figure 3.7 présente un exemple pour le croisement à deux points où les chromosomes sont coupés entre le troisième et le sixième emplacement. Les gènes du premier chromosome sont recopiés dans le chromosome ‘enfant’ jusqu’au premier point de croisement. Ensuite, les gènes du second chromosome qui ne font pas encore partie du chromosome ‘enfant’ sont recopiés dans l’ordre à partir du début jusqu’au second point de croisement. Les gènes restants sont enfin recopiés dans le chromosome ‘enfant’ selon leur ordre dans le premier parent. La procédure est la même pour les autres types de croisement à points basés sur la représentation par permutation. Dans le cas du RCPSP, cette technique conserve aussi les relations de préséance au sein du chromosome [Hartmann 1998]. Dans l’exemple de la Figure 3.7, toutes les relations de préséance communes aux deux chromosomes ‘parents’ sont en effet maintenues dans les chromosomes ‘enfants’.

La mutation

La mutation permet de favoriser la diversification dans la population afin d’avoir des individus de tout genre et de pouvoir choisir les meilleurs. Dans le but d’empêcher une convergence trop rapide et d’obtenir cette variété dans la population, on applique donc aux individus de chaque génération une mutation selon une probabilité pmMf donnée. Cette probabilité est appelée le taux de mutation. Contrairement au croisement, la mutation est une opération qui implique un seul chromosome. Le taux de mutation est généralement faible dans le cas des AG [Dréo et al. 2003]. Selon les auteurs, un taux de mutation élevé équivaudrait à une marche aléatoire dans l’espace de recherche; le rôle de l’opérateur de croisement serait dérisoire et on assisterait à une convergence trop lente de l’algorithme. Us proposent un taux de mutation compris entre 0,01 et 0,1. Yang [2008] abonde dans le même sens en proposant un taux de mutation compris entre 0,007 et 0,05. D existe plusieurs méthodes de mutation. Les méthodes les plus courantes pour la représentation par permutation sont la mutation par insertion, la mutation par échange et la mutation par inversion.

L’optimisation par essaims particulaires (OEP)

L’OEP est une métaheuristique récente qui a été mise au point par le sociologue James Kennedy et l’ingénieur électrique Russell C. Eberhart en 1995 [Kennedy et Eberhart 1995]. Les auteurs s’inspirent des observations effectuées lors de simulations informatiques des comportements sociaux des êtres vivants tels que le déplacement collectif d’un banc de poissons ou d’un groupe d’oiseaux par Reynolds [1987] et Heppner et Grenander [1990]. Contrairement à la plupart des métaheuristiques, l’OEP est utilisée à l’origine pour déterminer l’optimum de fonctions continues non linéaires. Cependant, plusieurs auteurs l’ont récemment adaptée pour résoudre des problèmes discrets tels que le PVC [Tasgetiren et al. 2007b], l’ordonnancement de véhicules [Chen et al. 2006], le problème d’atelier à cheminement unique [Liao et al. 2007], le problème d’atelier à cheminements multiples [Sha et Hsu 2006], le problème de machine unique [Anghinolfi et Paolucci 2009], ainsi que le RCPSP [Zhang et al. 2005],L’OEP présente quelques similarités avec les AG en ce sens qu’elle fonctionne sur la base d’une population de solutions qui interagissent entre elles afin de trouver la meilleure solution possible à un problème d’optimisation. Cependant, contrairement aux AG où l’évolution est basée sur la compétition et l’élimination des individus les moins performants, l’OEP se base sur la coopération entre les individus afin de faire évoluer chacun. Aucune solution n’est éliminée, chacune utilisant les connaissances que ses voisines possèdent du milieu afin de se déplacer efficacement et de s’améliorer.

Fonctionnement général de l’OEP

L’OEP repose sur un ensemble de solutions disposées aléatoirement au début de l’algorithme. Chaque solution est appelée particule et se situe à une position donnée dans l’espace de recherche. Chaque particule dispose d’une mémoire dans laquelle est conservée sa meilleure position visitée. L’OEP fonctionne aussi de manière itérative. À chaque itération de l’algorithme, les particules se déplacent dans l’espace de recherche selon une certaine vitesse. Le calcul de cette vitesse dépend de plusieurs facteurs tels que la vitesse actuelle pondérée par un coefficient d’inertie w, ainsi que l’écart par rapport à leur meilleure position connue et à celle de leurs voisines pondérées respectivement par des coefficients de confiance c; et C2. Les particules voisines d’une autre particule sont appelées ses informatrices.
La structure de base d’un algorithme d’OEP est illustrée par le schéma de la Figure 3.16. Comme dans le cas des AG, une population initiale est d’abord générée et évaluée. Les principes de génération de cette population et d’évaluation des solutions demeurent les mêmes pour les deux méthodes. À chaque itération de l’algorithme, la nouvelle vitesse et la nouvelle position de chaque particule sont calculées. Les particules sont ensuite évaluées et leurs mémoires, i.e. leurs meilleures positions connues, sont mises à jour. La diversité au sein de la population permet à l’algorithme de ne pas rester bloqué dans un optimum local.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport-gratuit.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

RÉSUMÉ
DEDICACE
REMERCIEMENTS
TABLE DES MATIÈRES
LISTE DES TABLEAUX
CHAPITRE 1 : INTRODUCTION
CHAPITRE 2; LE PROBLEME D’ORDONNANCEMENT DE PROJET SOUS CONTRAINTES DE RESSOURCES DANS LA LITTÉRATURE
2.Î Introduction
2.2 La représentation du RCPSP dans la littérature
2.3 Les méthodes de résolution du RCPSP
2.3.1 Les méthodes exactes
2.3.2 Les méthodes approchées ou heuristiques
2.4 Conclusion
CHAPITRE 3 : MÉTAHEURISTIQUES : LES ALGORITHMES GÉNÉTIQUES ET L’OPTIMISATION PAR ESSAIMS PARTICULAIRES
3.1 Introduction
3.2 Les algorithmes génétiques (AG)
3.2.1 Analogie avec la génétique
3.2.2 Le principe d’un algorithme génétique
3.2.3 La représentation des individus (encodage)
3.2.4 La génération de la population initiale
3.2.5 La sélection
3.2.6 Le croisement
3.2.7 La mutation
3.3 L’optimisation par essaims particulaires (OEP)
3.3.1 Fonctionnement général de ï’OEP
3.3.2 L’OEP pour l’optimisation continue
3.3.3 L’OEP pour l’optimisation combinatoire
3.4 Objectifs de la recherche
3.5 Conclusion
CHAPITRE 4: ALGORITHME D’OPTIMISATION PAR ESSAIMS PARTICULAIRES ET ALGORITHME GÉNÉTIQUE POUR LE RCPSP
4.1 Introduction
4.2 Conception d’un algorithme d’OEP discrète pour le RCPSP
4.2.1 Description de l’algorithme
4.2.2 Essais numériques et résultats obtenus
4.2.3 Comparaison avec les algorithmes OEP proposés par Zhang et al. [2005]
4.3 Reproduction d’un AG avec croisement à deux points (AG2P)
4.3.1 Description de l’algorithme
4.3.2 Essais numériques et résultats obtenus
4.4 Conclusion
CHAPITRE 5: HYBRIDATION DE L’ALGORITHME GÉNÉTIQUE ET DE L’OPTIMISATION PAR ESSAIMS PARTICULAIRES
5.1 Introduction
5.2 Conception d’un croisement de type OEP pour F AG
5.2.1 Description du croisement de type OEP
5.2.2 Essais numériques et résultats obtenus
5.3 Combinaison du croisement à deux points avec le croisement de type OEP
5.3.1 Essais numériques et résultats obtenus
5.3.2 Comparaisons et analyse des résultats
5.4 Conclusion
CHAPITRE 6 : CONCLUSION
V1I1
BIBLIOGRAPHIE „…„.„