Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Chapitre 3 Algorithmes Evolutionnaires et Optimisation III.1 Introduction L’app

Chapitre 3 Algorithmes Evolutionnaires et Optimisation III.1 Introduction L’approche fondamentale d’optimisation consiste à formuler une fonction de coût qui résume la performance ou la valeur d’une décision et l’améliore de manière itérative en sélectionnant parmi les alternatives disponibles. La plupart des méthodes d’optimisation classiques génèrent une séquence déterministe de solutions d’essai basée sur le gradient ou les statistiques d’ordre supérieur de la fonction de coût [3.1]. Dans les conditions de régularité de cette fonction, il est possible de montrer que ces techniques génèrent des séquences qui convergent asymptotiquement vers des solutions localement optimales, et dans certains cas, elles convergent de manière exponentielle rapide [3.2]. Des variations de ces procédures sont souvent appliquées à la formation de réseaux de neurones (rétropropagation) [3.3],[3.4] ou à l'estimation de paramètres dans des applications d'identification de systèmes et de commandes adaptatives (méthodes d'erreur de prédiction récursive, Newton-Gauss) [3.2],[3.5]. Mais ces méthodes ne fonctionnent souvent pas correctement lorsque des perturbations aléatoires sont imposées à la fonction de coût. De plus, les solutions localement optimales s'avèrent souvent insuffisantes pour résoudre les problèmes d'ingénierie du monde réel. Le développement et l’application de techniques de recherche basées sur les principes de l’évolution naturelle constituent un domaine important de la recherche actuelle. Est basé sur la notion de la sélection naturelle développé par ‘Charles Darwin ’dans ‘the Origin of Species’. Les algorithmes évolutifs sont caractérisés par l’existence d’une population constituée d’individus exposés à la pression de l’environnement, ce qui conduit à la sélection naturelle, c’est-à-dire à la survie du plus apte, et donc à l’accroissement de l’aptitude moyenne de la population. La condition physique est la mesure du degré d'adaptation d'un organisme à son environnement. Plus la forme physique est grande, plus l'organisme est en forme et adapté à l'environnement. En général, les algorithmes évolutifs se concentrent uniquement sur un sous-ensemble de mécanismes définis sur le processus évolutif biologique[3.6].Dans les années 1950 et 1960, plusieurs informaticiens ont indépendamment étudié les systèmes évolutifs dans l’idée que l’évolution pourrait être utilisée comme un outil d’optimisation des problèmes d’ingénierie. L'idée dans tous ces systèmes était de développer une population de solutions candidates à un problème donné, en utilisant des opérateurs inspirés par la variation génétique naturelle et la sélection naturelle. Enchenberg a introduit "les stratégies d'évolution", méthode qu'il utilisait pour optimiser les paramètres à valeurs réelles pour des dispositifs tels que les pales 1 | P a g e Chapitre 3 Algorithmes Evolutionnaires et Optimisation aérodynamiques [3.7]. Les algorithmes évolutionnaires on appelle aussi les algorithmes d’optimisation stochastiques se basant sur les principes de l’évolution naturelle [3.8]. Quelques problèmes d'ʹoptimisation ne peuvent être résolus ni de façon exacte (on n'ʹen connaît pas de solution mathématique ), ni de manière optimale .Ce sont des problèmes « difficiles », pour lesquels on va concevoir des heuristiques de résolution. Figure 1. Exemple de recherche d'une fonction d'une seule variable, avec un seul extremum global (rouge) et plusieurs extrema locaux (vert) dans la (figure 1) représente la répartition des extrema de f parmi l'ensemble des valeurs possibles, pour évaluer la difficulté du problème. Il peut exister un seul extremum global, ou plusieurs, ou encore plusieurs extrema locaux proches ou éloignés, répartis uniformément ou pas, denses ou pas. On appelle intensification toute démarche visant à diriger l’effort de recherche vers les meilleures solutions, et diversification toute démarche permettant de découvrir de nouvelles zones contenant éventuellement de meilleures solutions. Le bon équilibre entre ces deux notions dépend du problème à résoudre, et des réglages de l'algorithme utilisé. On ne connaît toujours pas de méthode universelle permettant de trouver les extrema globaux d'une fonction arbitraire. Mais, parmi les heuristiques, certaines pouvant optimiser une large gamme de problèmes différents pour lesquels on ne connaît pas de méthode classique plus efficace, sans nécessiter de changements profonds dans l’algorithme employé : les méta-heuristiques. Elles utilisent un haut niveau de concept, dont l'intérêt majeur est la facilité d'utilisation dans des problèmes 2 | P a g e Chapitre 3 Algorithmes Evolutionnaires et Optimisation concrets. De plus, elles sont efficaces pour atteindre un optimum avec une précision acceptable, dans un temps raisonnable. La majorité des problèmes du monde réel nécessitent l’optimisation simultanée de plusieurs objectifs dépendants les uns des autres. Alors qu’en optimisation à objectif unique, la solution optimale est clairement définie. Nombreux papiers abordent les limites des méthodes classiques et mettent en œuvre également plusieurs outils heuristiques modernes qui ont évolué au cours des deux dernières décennies et visant a résoudre le problème d’optimisation des coefficients de matrice de séparation W, tels que le calcul évolutif, algorithme génétique (GA : Génetique algoritm), la recherche tabou (TS :Tabu Search), (BBO : Biogeography-based optimization ), l’optimisation par essaim de particules (PSO : Particle Swarm Optimization), La méthode d’ascension de collines (HC : Hill Climbing), le recuit simulé (SA : Simulated Annealing), etc. Ces outils facilitent la résolution des problèmes d’optimisation qui étaient auparavant difficiles ou impossibles a résoudre. III.2Terminologie Et Notations On cherche à optimiser une fonction f à valeurs réelles définie sur un espace de recherche Ω (figure 1).  La fonction objectif f est appelée fonction (fitness).  Les points de l’espace de recherche Ω sont appelés des individus.  les tuples d’individus sont appelés des populations.  on parle d’une génération pour la boucle principale de l’algorithme.  On notera ∏ila population de taille fixe P à la génération i. III.2.1 Schéma Général D'un Algorithme Evolutionnaire La majorité des algorithme évolutionnaire (AE) reposent sur une représentation darwinienne relativement simpliste et une optimisation stochastique résumées dans le diagramme de la (figure 2). L’algorithme fait évoluer une population de solutions Π. Cette évolution résulte : d’une part d’un darwinisme artificiel, qui se manifeste par la sélection 3 | P a g e Chapitre 3 Algorithmes Evolutionnaires et Optimisation et le remplacement et ne dépend que de la fonction de fiteness f ; d’autre part de l’effet du hasard, qui s’exprime dans l’initialisation et les opérateurs de variation, et ne dépend que de la représentation de l’espace de recherche. L’idée est que la sélection favorise les individus qui optimisent la fonction d’objectif et que les variations font apparaître dans la population sélectionnée des individus que l’on peut souhaiter meilleurs vis-à-vis de la fonction d’objectif. Dans cette évolution, les générations successives de la population restent à taille constante et la forme stochastique ne dépend que de la génération précédente. les principes darwiniens sont implémentés dans l’algorithme de la manière suivante:  Initialisation de la population ∏0 en choisissant P individus dans Ω , généralement par tirage aléatoire avec une probabilité uniforme sur Ω.  Évaluation des individus de ∏0 (calcul des valeurs de f pour tous les individus).  La génération i construit la population ∏ià partir de la population∏i−1 .  Sélection des individus les plus performants de ∏i−1 au sens de f (les plus adaptés se reproduisent).  Application (avec une probabilité donnée) des opérateurs de variation aux parents sélectionnés, ce qui génère de nouveaux individus, les enfants. On parle de mutation pour les opérateurs unaires, et de croisement pour les opérateurs binaires (ou n- aires). à noter que cette étape est toujours stochastique .  Evaluation des enfants.  Remplacement de la population ∏i−1 par une nouvelle population créée à partir des Enfants et/ou des vieux parents de la population Πi−1 au moyen d’une sélection Darwinienne (les plus adaptés survivent).  L’évolution stoppe quand le niveau de performance souhaité est atteint. 4 | P a g e Chapitre 3 Algorithmes Evolutionnaires et Optimisation Figure 2. Schéma général d'un algorithme évolutionnaire [3.9] III.3 Recherche tabou Dans la vie actuelle, la technologie et l’information augmentent rapidement, ce qui complique la recherche d’une solution optimale. Pour trouver une solution à un problème discret avec la présence de contraintes ou de variables de décision est appelée optimisation combinatoire. Dans le but de résoudre ce problème, le concept méta-heuristique est introduit. appelé algorithme tabou(Tabu Search) .C’est l’une des heuristiques les plus efficaces pour trouver des «solutions de qualité» dans des délais relativement courts. La principale caractéristique de la recherche taboue est basée sur l'utilisation d'un mécanisme qui s'inspire de la mémoire humaine [3.10], Au cours dernières années, plus d'une centaine d'articles présentant les applications de tabou(Tabu Search ), une méthode heuristique initialement proposée par Glover [3.11], à divers problèmes de combinatoire. Dans plusieurs cas, les méthodes décrites apportent des solutions très proches de l'optimalité. Et permet résoudre les problèmes difficiles qui se posent. Ces succès ont rendu tabou extrêmement populaire parmi ceux qui souhaitent trouver de bonnes solutions aux grands problèmes de combinaison rencontrés dans de la pratiques. La recherche tabou (Tabu Search : TS) est une méthode d’optimisation mathématique, appartenant à la catégorie des techniques recherche locale utilisée pour résoudre des problèmes complexes de très grande taille [3.12], [3.13],[3.14]. La recherche taboue améliore les performances d’une méthode de recherche locale. Cette technique utilise une mémoire (une ou plusieurs mémoires) qui sont mises à jour et exploitées au cours de la 5 | P a g e Chapitre 3 Algorithmes Evolutionnaires et Optimisation recherche. Une fois une solution a été uploads/Science et Technologie/ chapitre-3.pdf