Remerciez-le!

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

Méthodes d’optimisation stochastiques Introduction : Dans un problème d'optimis

Méthodes d’optimisation stochastiques Introduction : Dans un problème d'optimisation déterministe, les valeurs de tous les paramètres sont supposées connues. Comment formuler un problème d'optimisation dans lequel les données sont incertaines (par exemple, les prix des énergies) ? Et quand certaines valeurs des données sont révélées au cours des étapes de décision (par exemple, les demandes en énergie) ? L'optimisation stochastique est un cadre pour répondre à de telles questions et pour formuler des problèmes sous incertitude. C'est également un ensemble de méthodes de résolution. I) Définition : L'optimisation stochastique (en) étudie le cas dans lequel certaines des contraintes dépendent de variables aléatoires. En optimisation robuste, les aléas sont supposés être situés dans des intervalles autour de positions nominales et on cherche à optimiser le système soumis à de tels aléas, dans le pire des cas. Introduction à la programmation stochastique : La notion d’incertitude dans la programmation mathématique est apparue pour la première fois dans les années ’50 avec les travaux de Bellman, Dantzig, Cooper et Charnes, Beale, et elle a rencontré depuis un d´enveloppement rapide. La figure 1montre la tendance en termes de publications d’articles depuis le début de la programmation stochastique jusqu’`à nos jours. Dans la suite on parlera d’incertitude dans le sens d’incertitude aléatoire ou une partie de l’information n´nécessaire pour la compréhension complète d’un phénomène est inconnue. L’incertitude dans les problèmes d’optimisation touche notamment les couts de production, les prix des marches, les pénalités en cas des violations des contrats, aussi bien que la demande de clients, les délais de livraison, les temps de traitement, la disponibilité des machines et d’autres coefficients technologiques. 1 Méthodes d’optimisation stochastiques Figure 1 : Nombre de publications annuelles depuis les années 50 jusqu’en mai 2003. Le but que l’on se fixe dans un problème d’optimisation est de prendre la meilleure décision vis à vis des situations qui comportent de l’incertitude. Le regard vers l’incertitude reste subjectif et varie d’un décideur à l’autre. On peut par exemple souhaiter que dans l’espace de tout évènement possible, la solution adoptée soit telle que son cout soit minimal en moyenne. Ainsi, les approches de l’incertitude comprennent des techniques orientées vers la minimisation (maximisation) de l’espérance mathématique (ou d’autres moments), la minimisation de la d´aviation par rapport aux cibles (de- viation from goals), la minimisation des couts maximaux, la minimisation de l´écart entre le meilleur et le pire cas, ou même la simple satisfaction des contraintes avec une probabilité donnée d’avance qui représente le taux de fiabilité du système. Lorsque l’on parle de la programmation stochastique, on entend la programmation mathématique sous incertitude. La programmation stochastique n’est pas une famille de problèmes, de modèles et d’outils différents des autres domaines d’optimisation (programmation linéaire, non-linéaire, dynamique) ; au contraire, elle constitue un 2 Méthodes d’optimisation stochastiques complément de ces familles lorsque la notion d’incertitude intervient. On se permet donc de parler de programmation stochastique linéaire, non-linéaire ou bien de programmation stochastique dynamique. Dans le présent travail on s’intéresse à la programmation stochastique linéaire ainsi qu’`a la programmation stochastique dynamique. Les approches qui dominent sur la modélisation et la résolution des problèmes de la programmation stochastique sont les suivantes : – Modèles avec des contraintes probabilistes. – Modèles de recours. – Modèles robustes. II) Méthodes d’optimisation stochastiques : Les méthodes d’optimisation stochastiques s’appuient sur des mécanismes de transition probabilistes et aléatoires. Cette caractéristique indique que plusieurs exécutions successives de ces méthodes peuvent conduire à des résultats différents pour une même configuration initiale d’un problème d’optimisation. Ces méthodes ont une grande capacité à trouver l’optimum global du problème. Contrairement à la plupart des méthodes déterministes, elles ne nécessitent ni point de départ, ni la connaissance du gradient de la fonction objective pour atteindre la solution optimale. Elles sont d’ordre zéro. Cependant, elles demandent un nombre important d’évaluations de la fonction objectif. La figure II.3 présente les méthodes stochastiques les plus utilisées. 3 Méthodes d’optimisation stochastiques Figure 2 : Méthodes d’optimisation stochastiques Parmi ces méthodes stochastiques, les méthodes Monte-Carlo et les méthodes évolutionnistes seront présentés brièvement. II.1) Monte-Carlo C’est la plus simple des méthodes stochastiques, Elle consiste à tirer une solution au hasard à chaque itération. La fonction objectif est évaluée en ce point. Si elle est meilleure que l’optimum courant, cette valeur est enregistrée, ainsi que la solution correspondante et le processus continue jusqu’à ce que les conditions d’arrêt soient vérifiées. Il s’agit donc d’un processus d’exploration. Les méthodes Monte-Carlo peuvent être utilisées, en première approche, pour avoir des renseignements utiles sur la forme de la fonction. Elles permettent par exemple de choisir de façon plus appropriée le point de départ d’un algorithme de recherche locale. Toutefois, cette association ne garantit pas la localisation de l’optimum global. 4 Algorithmes Génétiques Evolution Différentielle Programmation Evolutionniste Stratégies d’Evolution Méthodes Evolutionnistes Recherche Taboue Recuit Simulé Monte-Carlo Méthodes stochastiques Evaluation de la performance des individus de la population Initialisation aléatoire des premières générations g=0 Evaluation de la performance des individus de la population Enfants Evolution g = compteur de générations Test d’arrêt Vérifié ? g =g+1 Parent s non Sélection oui Solution optimale Méthodes d’optimisation stochastiques II.2) Méthodes évolutionnistes Les méthodes évolutionnistes font partie de la dernière grande classe de méthodes stochastiques. Elles reposent sur une analogie avec la théorie de l’évolution naturelle des espèces de Darwin selon laquelle, les individus les mieux adaptés à leur environnement survivent et peuvent se reproduire pour donner des enfants encore mieux adaptés de génération en génération. Contrairement aux techniques d’optimisation qui explorent l’espace à partir d’un point unique, les méthodes évolutionnistes partent d’un ensemble de configurations, c’est à dire d’une population d’individus, et la font évoluer à partir d’opérateurs à transition aléatoire, la sélection et l’évolution, selon le principe de la figure 3. Figure 3 : Principe d’une méthode évolutionniste 5 Méthodes d’optimisation stochastiques Les algorithmes évolutionnistes remontent à l’introduction des algorithmes génétiques (AG) par Holland, Reshenberg et Schwefel ont mis au point trois méthodes assez similaires : les stratégies d’évolution, la programmation évolutionniste et la programmation génétique. L’évolution différentielle est apparue plus récemment. Les différences entre ces méthodes sont liées à la représentation des individus et aux modes d’évolution de la population. Les AG utilisent un codage des paramètres de la fonction à optimiser alors que les autres techniques se servent directement de la valeur des paramètres. Chacune des méthodes est caractérisée par un opérateur d’évolution particulier. Les AG et l’évolution différentielle ont un mécanisme de croisement qui permet la génération de nouvelles configurations par recombinaison de solutions existantes. C’est donc un opérateur d’exploration. L’exploitation est faite par le processus de sélection. Les stratégies d’évolution et la programmation évolutionniste sont, pour leur part, basées principalement sur un procédé de mutation de la population par perturbation successive de chaque solution. Les méthodes évolutionnistes s’affirment peu à peu comme les techniques d’optimisation les plus robustes. Elles peuvent être appliquées à des problèmes très divers car elles sont indépendantes du processus à optimiser et n’utilisent pas les dérivées. Parmi les algorithmes évolutionnistes cités précédemment, les algorithmes génétiques occupent une place particulière car ils réunissent les trois opérateurs de sélection, croisement et mutation. II.3) Recherche Taboue : Définition : Méthode heuristique de recherche locale utilisée pour résoudre des problèmes complexes et/ou de très grande taille (souvent NP-durs). La RT a plusieurs applications en programmation non linéaire (PNL). 6 Méthodes d’optimisation stochastiques • Principe de base : poursuivre la recherche de solutions même lorsqu’un optimum local est rencontré. ⇒ en permettant des déplacements qui n’améliorent pas la solution. ⇒ en utilisant le principe de mémoire pour éviter les retours en arrière (mouvements cycliques). II.3.1) Domaine d’application : Problème de transport, Optimisation de la production et gestion des Inventaires, Planification et ordonnancement, Problèmes d’affectation et de localisation, Optimisation de graphes, Télécommunications, Logique et intelligence artificielle, Application à diverses technologies, Création d’horaires, Optimisation de structures, Techniques spécialisées , Design, Résolution en parallèle, Optimisation continue et stochastique, Analyses financières. II.4) Algorithmes d’optimisation : ◆ Objectif : faire mieux que la recherche aléatoire sur un domaine particulier (car, par le NFL, …) ◆ Il faut s’écarter de la Recherche Aléatoire pour faire mieux sur le domaine à résoudre (quitte à faire moins bien ailleurs). ◆ Il faut un algorithme avec tout plein de paramètres pour le faire « coller au problème ». II.4.1) Paramétrage d’algorithme d’optimisation : ◆ Beaucoup d’algorithmes avec « deux boutons » pour régler EvE (Exploitation vs Exploration) : ◆ Optimisation par colonie de fourmis (pondération objectif vs comportement collectif). ◆ Optimisation par essaim particulaire (pondération meilleure position globale / meilleur position personnelle connue). 7 Méthodes d’optimisation stochastiques ◆ Mais comment coller à un problème précis avec 2 boutons ? ◆ Algorithmes génétiques : très grand nombre de paramètres (taille de la population, opérateurs génétiques (croisement, mutation), opérateurs de sélection, de remplacement, … ◆ Garantie qu’on peut coller au problème à résoudre mais…paramétrage très difficile ! II.4.2) Comment choisir quel algorithme ? ◆ Critère de choix des méthodes de recherche : -Complexité du problème (unimodal, multimodal). - Type d’espace de recherche (continu, discontinu, discret, mixte). - Régularité de la fonction uploads/Management/ expose-optimisation-stochastique.pdf