Remerciez-le!

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

Université Mohammed V - Agdal Institut National des Sciences École Mohammadia d

Université Mohammed V - Agdal Institut National des Sciences École Mohammadia d’Ingénieurs Appliquées - Rouen Laboratoire d’Étude et Recherche Laboratoire de Mécanique de Rouen en Mathématiques Appliquées Rouen - France Rabat - Maroc THÈSE EN COTUTELLE présentée à L’ÉCOLE MOHAMMADIA D’INGÉNIEURS pour obtenir le grade de DOCTEUR EN SCIENCES APPLIQUÉES et L’INSA de Rouen pour obtenir le grade de DOCTEUR DE L’INSA DE Rouen Mention : MATHÉMATIQUES Équipe d’acceuil : LMR par Mohamed Zeriab ES-SADEK CONTRIBUTION A L’OPTIMISATION GLOBALE. APPROCHE DÉTERMINISTE ET STOCHASTIQUE ET APPLICATION Soutenue le 21 Novembre 2009 devant la commission d’examen M. : Abdelkhalek EL HAMI INSA, Rouen Président M. : Youssef BENADADA ENSIAS, Rabat Rapporteur M. : Piotr BREITKOPF U. T, Compiègne Rapporteur M. : Mohamed TKIOUAT EMI, Rabat Rapporteur M. : Omar KAITOUNI IDRISSI EMI, Rabat Éxaminateur M. : Rachid ELLAIA EMI, Rabat Directeur de thèse M. : José Eduardo SOUZA DE CURSI INSA, Rouen Directeur de thèse REMERCIEMENTS Permettez moi de citer nominativement, ces personnes qui à mes yeux sont les substrats de mon essence scientiﬁque et morale, aﬁn de les remercier en ces quelques lignes : A tous les membres de ma famille et plus spécialement mon Père, ma Mère et ma Soeur, Monsieur le Président du jury : Professeur El Hami Abdelkhalek, d’un profond respect de soi et des autres et d’une humilité à l’image de sa prestance, Messieurs les encadrants : Professeur Ellaia Rachid , encadrant d’une grande disponibilité et d’une valeur encyclopédique incommensurable, Professeur Souza De Cursi José Eduardo, encadrant d’une clairvoyance et d’une pertinence rare, Messieurs les Rapporteurs : Professeur Tkiouat Mohamed, Professeur Benadada Youssef, Professeur Breitkopf Piotr, Monsieur l’examinateur : Professeur Idrissi Kaitouni Omar, Tous les membres du laboratoire d’étude et de recherche en mathématiques appliquées à l’ E.M.I. et tous les membres du laboratoire de mécanique de l’I.N.S.A. de Rouen ; Suite à l’achèvement de notre thèse intitulée : CONTRIBUTION A L’OPTI- MISATION GLOBALE, APPROCHE DETERMINISTE ET STOCHASTIQUE ET APPLICATION, nous tenons à mettre l’accent que sous votre supervision et votre collaboration, nous avons prôné plusieurs idées motrices : principe d’une meilleure valeur ajoutée. Votre mobilisation, vos directives et suggestions ont été garantes de l’atteinte de l’objectif escompté. Et ce en plus, nous tenons à souligner, par la même occasion que cet en- semble synergétique, a enclenché en nous une nouvelle dynamique, que nous tenons à faire consolider en vous proposant ce travail contributif. ii Nous saisissons cette opportunité, pour nous rappeler à jamais que l’en- semble de vos interventions pertinentes, ont été pour ma personne un mémo- randum d’une coopération fructueuse et prometteuse. Le volume, d’échange et d’idées, bilatéral, qui tranche, par son objectivité, nous a amené à porter plus nos critères, que partage nos aspirations dans un éternel respect mutuel . Je vous réitère, encore une fois, mes sincères remerciements et vous souligne notre éternel attachement aux méthodes, processus et déontologie qui, force d’acharnement de votre part, vous avez tenu à m’inculquer profondément. Je remercie l’institution CMIFM (Egide, PAI Volubilis, MA/07/173) pour son ﬁnancement de mes stages au sein de l’I.N.S.A. de Rouen. iii Abstract This thesis concerns the global optimization of a non convex function un- der non linear restrictions, this problem cannot be solved using the classic de- terministic methods like the projected gradient algorithm and the sqp method because they can solve only the convex problems. The stochastic algorithms like the genetic algorithm and the simulated annealing algorithm are also inef- ﬁcients for solving this type of problems. For solving this kind of problems, we try to perturb stocasicly the deterministic classic method and to combine this perturbation with genetic algorithm and the simulated annealing. So we do the combination between the perturbed projected gradient and the genetic algorithm, the perturbed sqp method and the genetic algorithm, the perturbed projected gradient and the simulated annealing, the Piyavskii algo- rithm and the genetic algorithm. We applicate the coupled algorithms to dif- ferent classic examples for concretited the thesis. For illustration in the real life, we applicate the coupled perturbed projected gradient end the genetic algo- rithm to logistic problem eventuelly transport. In this view, we sold the efﬁcient practices. Keywords Global optimization, stochastic perturbation, projected gradient, sqp, gene- tic algorithm, simulated annealing, hybridation, logistic problem. iv RÉSUMÉ Dans les situations convexes, le problème d’optimisation globale peut être abordé par un ensemble de méthodes classiques, telles, par exemple, celles ba- sées sur le gradient, qui ont montré leur efﬁcacité en ce domaine. Lorsque la situation n’est pas convexe, ces méthodes peuvent être mises en défaut et ne pas trouver un optimum global. La contribution de cette thèse est une méthodologie pour la détermination de l’optimum global d’une fonction non convexe, en utilisant des algorithmes hybrides basés sur un couplage entre des algorithmes stochastiques issus de fa- milles connues, telles, par exemple, celle des algorithmes génétiques ou celle du recuit simulé et des algorithmes détérministes pertubés aléatoirement de façon convenable. D’une part, les familles d’algorithmes stochastiques considérées ont fait preuve d’efﬁcacité pour certaines classes de problèmes et, d’autre part, l’adjonction de perturbations aléatoires permet de construire des méthodes qui sont – en théorie – convergents vers un optimum global. En pratique, chacune de ces approches a ses limitations et insufﬁsantes, de manière que le couplage envisagé dans cette thèse est une alternative susceptible d’augmenter l’efﬁcacité numérique. Nous examinons dans cette thèse quelques unes de ces possibilités de couplage. Pour établir leur efﬁcacité, nous les appliquons à des situations- test classiques et à un problème de nature stochastique du domaine des trans- ports. Mots clés Optimisation globale, perturbation aléatoire, gradient projeté, sqp, algorithme génétique, recuit simulé, hybridation, problème logistique. Table des matières 1 Introduction générale 1 1.1 Optimisation d’un dispositif . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Fonctions objectif et fonction d’adaptation . . . . . . . . . . . . . . 5 1.3 Méthodes d’optimisation . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Compromis exploration et exploitation . . . . . . . . . . . . . . . . 8 1.5 Sujet de thèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 I Algorithmes déterministes et perturbation 13 2 Algorithme de Piyavskii et extension 14 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Algorithme de Piyavskii . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2.1 Introduction et description . . . . . . . . . . . . . . . . . . 15 2.2.2 L’algorithme de Piyavskii-Shubert . . . . . . . . . . . . . . 16 2.3 Optimisation multidimensionnelle . . . . . . . . . . . . . . . . . . 17 2.3.1 Optimisation sans contraintes . . . . . . . . . . . . . . . . . 17 2.3.2 Convergence de l’algorithme . . . . . . . . . . . . . . . . . 20 2.3.3 Optimisation avec contraintes . . . . . . . . . . . . . . . . . 21 2.4 Résultats numériques . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.4.1 Problèmes sans contraintes . . . . . . . . . . . . . . . . . . 22 2.4.2 Problèmes avec contraintes . . . . . . . . . . . . . . . . . . 22 2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 v vi TABLE DES MATIÈRES 3 Gradient projeté perturbé 27 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2 Notations et hypothèses . . . . . . . . . . . . . . . . . . . . . . . . 28 3.3 Méthode du gradient projeté . . . . . . . . . . . . . . . . . . . . . 30 3.3.1 Direction de descente . . . . . . uploads/Science et Technologie/es-sadek.pdf