L'objectif de cette thèse est de proposer des algorithmes d'optimisation efficaces pour un système de tranport en commun à la demande proposé par Padam Mobility, une start-up Parisienne. Après avoir modélisé le problème comme un DARP dynamique, trois modules d'optimisation sont présentés : un module online destiné à répondre aux requêtes en temps réel, un module de réinsertion pour insérer les requêtes rejetées par le module online et enfin un module offline basé sur une métaheuristique permettant d'optimiser en continue les itinéraires. / The purpose of this thesis is to propose efficient optimization algorithms for an on-demand common transportation system operated by Padam Mobility, a Parisian company. Formalised as a dynamic DARP, we propose three optimisation modules to tackle the underlying problem : an online module to answer real-time requests, a reinsertion module to re-insert rejected requests and a metaheuristic-based offline module to continuously optimize the rides. The proposed methods are directly implemented in the company system and extensively tested on real instances.

<p>De nos jours, il est peu de processus ou de tâches qui ne requièrent pas l'optimisation d'une quantité : diminuer le temps de livraison, diminuer l'espace utilisé, réduire les efforts de développement, ... C'est donc sans surprise que la recherche en optimisation soit l'un des domaines les plus actifs des sciences des technologies de l'information. En optimisation combinatoire, les métaheuristiques sont à compter parmi le fleuron des techniques algorithmiques. Mais ce succès est encore au prix d'une quantité significative de temps de conception et développement. Ne serait-il pas possible d'aller encore plus loin ? D'automatiser la préparation des métaheuristiques ? En particulier dans des conditions telles le manque de temps, l'ignorance de techniques spécialisées ou encore la mauvaise compréhension du problème traité ? C'est ce à quoi nous répondons dans la présente thèse au moyen d'une approche de méta-modélisation de la recherche : l'heuristique de la Gestalt.</p> <p>Considérant la représentation du problème comme un levier que l'on peut activer sous le processus de recherche mené par une métaheuristique, la thèse suggère la construction d'une abstraction de cette représentation capable d'assister la métaheuristique à trouver de bonnes solutions en contraignant sa recherche. Cette approche, inspirée de la psychologie de la Gestalt, nous l'appelons l'heuristique de la Gestalt. Son fonctionnement repose principalement sur l'agrégation des variables de la représentation. Cette agrégation donne lieu à une abstraction structurelle, mais également fonctionnelle en ce sens que les opérateurs de la métaheuristique doivent désormais respecter l'intégrité des agrégats définis.</p> <p>Après avoir établi le contexte de la dissertation, nous discutons de la transposition de la psychologie de la Gestalt dans le cadre de l'optimisation combinatoire et des métaheuristiques. S'ensuit la formalisation de l'heuristique de la Gestalt et la description de sa réalisation. Finalement, une série d'études expérimentales sont menées pour éprouver le concept avancé et valider l'implémentation basée sur les algorithmes évolutionnistes que nous proposons. En conclusion, nous affirmons que l'implémentation de l'heuristique de la Gestalt basée, entre autres, sur un algorithme génétique de groupement est capable d'assister positivement des algorithmes génétiques lorsque les instances de problèmes traitées possèdent une structure riche et complexe, que leur taille est importante, que l'on est tôt dans le processus d'optimisation et que l'algorithme génétique n'est pas paramétré spécifiquement.</p>

Cette thèse s'inscrit dans le cadre d'un projet pluridisciplinaire, le projet DRAMA, qui consiste à générer des scènes virtuelles 3D à partir des descriptions contenues dans les textes théâtraux. L'un des objectifs de ce projet consiste à simplifier au maximum la tâche des utilisateurs finaux en leur offrant un outil simple, rapide, et efficace. Ainsi, la technique adoptée dans cette étude est axée sur la modélisation déclarative d'environnements virtuels qui s'appuie sur trois phases (description, génération et prise de connaissances). La phase de description permet au concepteur de décrire l'environnement à partir d'un ensemble de propriétés, interprétées en un ensemble de contraintes destinées à un système de génération qui produit un ou plusieurs environnements virtuels solutions.Dans le cadre de ce projet DRAMA, des nouvelles méthodes de balisage ont été proposées afin de détecter les éléments essentiels pour la création d'une pièce théâtrale, notamment les informations sur les placements d'objets. Par ailleurs, les utilisateurs peuvent, aussi, lancer des requêtes au niveau du texte à partir de ces balises. Les propriétés sur les placements seront traduites en contraintes spatiales grâce aux données initialement stockées dans une base de connaissance qui utilise le langage XML. Une technique adoptant la méthode des métaheuristiques est ensuite utilisée pour la résolution des contraintes de placements obtenues précédemment. La gestion des propriétés physiques des objets (collision, gravité, friction) a été aussi gérée à partir d'un moteur physique. À la fin, les scènes solutions finales seront proposées à l'utilisateur, en utilisant un moteur de rendu 3D.

La littérature scientifique propose une grande variété de stratégies pour la résolution des problèmes d'optimisation combinatoire (POC). Ces problèmes sont d'une grande complexité et demandent des méthodes évoluées pour les résoudre. Les algorithmes exacts, comme la programmation linéaire en nombres entiers (PLNE) à l'aide de l'algorithme Branch and Bound (B&B), arrivent à trouver une solution optimale pour certaines instances de problèmes. Par contre, plus la taille du problème à résoudre est grande, plus ces algorithmes ont de la difficulté à en venir à bout. Les métaheuristiques représentent alors une alternative intéressante pour trouver une solution de qualité acceptable dans des délais très courts. Toutefois, il est impossible de garantir qu'une métaheuristique trouvera la solution optimale d'un problème. Parmi ces méthodes, on retrouve l'optimisation par colonies de fourmis (OCF), qui a su faire ses preuves pendant les dernières années pour la résolution de différents problèmes d'optimisation combinatoire. Une autre avenue consiste à créer des algorithmes hybrides. L'objectif principal de ce mémoire est de proposer trois algorithmes hybridant un OCF et la PLNE pour résoudre le problème d'ordonnancement de voitures (POV). Le POV est un POC qui consiste à déterminer dans quel ordre placer un ensemble de voitures à produire sur une chaîne d'assemblage en se soumettant à un ensemble de contraintes. On cherche parfois la séquence minimisant le nombre de conflits, où un conflit représente une surcharge de travail occasionnée à un poste particulier de l'atelier de montage par l'arrivée successive de plusieurs voitures similaires, ou encore minimisant le nombre de changements de couleurs à l'atelier de peinture. Pour simplifier le problème, on ne s'attardera qu'aux contraintes liées à l'atelier de montage où sont installées les différentes options des voitures. Cette version théorique du POV que l'on retrouve dans la littérature est une simplification du problème industriel. Différentes méthodes ont été proposées pour solutionner ce problème. Celles qui attirent notre attention sont l'OCF et la PLNE. On cherchera, dans ce mémoire, à concevoir des approches hybrides exploitant les forces de ces deux approches. Il sera également possible de comparer la performance des algorithmes hybrides avec les résultats obtenus avec l'OCF pour établir l'apport de telles hybridations. Le premier algorithme hybride proposé consiste à créer un sous-problème à partir de la meilleure solution de chaque cycle de l'OCF et de résoudre ce sous-problème avec le B&B. Cette méthode ne s'est pas avérée très performante, car aucune intensification n'est effectuée sur une solution. Le second algorithme tente de combler cette lacune en appelant le B&B de manière répétitive à un intervalle régulier de cycles de l'OCF. Cet appel répété du B&B représente, en fait, une recherche locale exacte (RLE). Pour l'ensemble des problèmes utilisés pour tester cette hybridation, des résultats de qualité légèrement supérieure ou égale à l'OCF, intégrant une recherche locale, ont été obtenus pour environ deux problèmes sur trois. On peut en dire autant de la troisième hybridation proposée, qui consiste, dans un premier temps, à exécuter l'OCF et à fournir la meilleure solution trouvée comme solution de départ à la RLE. Les objectifs fixés dans cette recherche ont été atteints en concevant des méthodes de résolution hybrides, adaptées au POV, combinant une métaheuristique et une méthode exacte. On avait aussi pour but d'établir la performance des méthodes hybrides face à leurs contreparties singulières. En règle générale, les hybridations parviennent à donner des résultats de qualité équivalente à celle des résultats de l'OCF avec recherche locale mais avec un coût en temps d'exécution. Il s'agit tout de même d'une conclusion réjouissante puisque des améliorations pourraient être apportées à ces algorithmes pour les rendre encore plus performants. On a aussi exploré quelques façons de créer des sous-problèmes plus faciles à résoudre par un algorithme exact. Ceci ouvre donc une porte à une autre approche de la résolution de POC.

Le concept de paysage adaptatif a été introduit par S. Wright dans le domaine de la biologie de l'évolution dans les années 1930. Il est l'un des concepts pertinents pour modéliser l'évolution d'une population d'organismes. Dans le domaine de l'optimisation combinatoire par métaheuristiques, il est également utilisé et <br />permet de lier une description géométrique d'un problème d'optimisation avec la dynamique des algorithmes de recherche.<br />Deux géométries de paysage correspondant à deux dynamiques d'algorithme ont été principalement étudiées. La géométrie de paysage multimodale est liée à la présence d'optima locaux,<br />où la dynamique est une succession de marches adaptatives vers de meilleures solutions et de dégradations de performance. La géométrie des paysages adaptatifs neutres, mise en avant par la théorie de la neutralité en évolution moléculaire de Motoo Kimura,<br />est liée à la présence de plateaux ; la dynamique se caractérise alors par une dérive aléatoire entrecoupée de rares découvertes de solutions plus performantes. Cette thèse se propose d'approfondir <br />l'étude des paysages neutres dans le contexte de l'optimisation et de proposer de nouvelles métaheuristiques adaptées à ce type de paysages.<br /><br />La thèse se compose de quatre chapitres. Dans un premier chapitre,<br />nous présentons les principaux résultats concernant les paysages adaptatifs et plus particulièrement les paysages adaptatifs neutres.<br />Dans un deuxième chapitre, nous développons le concept d'ensemble de neutralité en introduisant la notion de 'nuage adaptatif' qui permet d'étudier la corrélation de performance entre solutions voisines et nous l'appliquons à la classe des paysages 'embarqués' qui regroupe les paysages NK et Max-SAT. Dans un troisième chapitre, nous résumons l'ensemble des mesures relatives aux réseaux de neutralité et nous proposons une nouvelle mesure. Une étude expérimentale est réalisée sur trois familles de paysages pour lesquelles la neutralité est ajustable et deux problèmes classiques de la littérature. Enfin, un nouvel algorithme de recherche adapté aux paysages neutres lié à la nouvelle mesure est proposé et évalué sur différents paysages neutres. Nous réalisons l'étude du paysage adaptatif massivement neutre<br />issu du problème d'apprentissage de la règle d'un automate cellulaire réalisant la tâche de classification par la densité, afin d'en améliorer les métaheuristiques connues existantes.

Dans l’industrie, l’automaticien doit concevoir une loi de commande unique qu’il valide sur un prototype unique, ayant un degré de robustesse suffisant pour satisfaire un cahier des charges complexe sur un grand nombre de systèmes. Pour cela, la méthodologie de développement qu’il emploie consiste en un processus itératif expérimental (phase d’essai-erreur), qui fait grandement appel à l’expérience de l’ingénieur. Dans cette thèse, on tente de rendre la méthodologie de synthèse des correcteurs des asservissements plus efficace car plus directe et donc moins couteuse en temps de développement en calculant un correcteur final (structuré) par une attaque directe de la spécification système haut niveau. La complexité des spécifications systèmes haut-niveau nous pousse à l’emploi des métaheuristiques : ces techniques d’optimisation ne nécessitent pas la formulation du gradient, la seule contrainte étant la possibilité d’évaluer la spécification. Ainsi avons-nous proposé dans ce travail de reformuler les problèmes de commande robuste pour l’optimisation stochastique : on montre dans ce travail comment on peut synthétiser des correcteurs structurés à partir de problématiques de type H ou -synthèse et on montre que l’intérêt de l’approche formulée réside dans sa flexibilité et la prise en compte de contraintes « exotiques » complexes ; les algorithmes évolutionnaires s’avérant très performants et compétitifs, nous avons finalement développé sur cette base une méthode originale de synthèse de correcteurs structurés et robustes vis-à-vis de critères d’optimisation de forme quelconque. La validation de ces travaux a été réalisée sur des exemples industriels de viseurs. / In the industrial framework, the control engineer must design a unique control law that valid on a single prototype, with a sufficient degree of robustness to satisfy a complex specification on many systems. For that purpose, his development methodology consists of an experimental iterative process (trial and error phase), which relies heavily on the experience of the engineer. In this thesis, we try to make the methodology for computing controllers more efficient and more direct with a less costly development time by calculating a final structured controller by a direct optimization on the high level specification.The complexity of high-level specifications pushes us to the use of metaheuristics: these optimization techniques do not require the formulation of the gradient, the only constraint being the possibility of evaluating the specification. Thus we proposed in this work to reformulate robust control problems for stochastic optimization: we show in this work how to synthesize structured controllers for control problems such H synthesis or -synthesis and show that the interest of the formulated approach lies in its flexibility and the consideration of exotic complex constraints. Evolutionary algorithms proving very effective and competitive, we finally developed on this basis a new method for synthesizing robust and structured controllers with respect to any form of optimization criteria. The validation of this work was carried out on the industrial example of the line of sight stabilization problem.

Les problèmes d'optimisation continue sont nombreux, en économie, en traitement de signal, en réseaux de neurones, etc. L'une des solutions les plus connues et les plus employées est l'algorithme évolutionnaire, métaheuristique basée sur les théories de l'évolution qui emprunte des mécanismes stochastiques et qui a surtout montré de bonnes performances dans la résolution des problèmes d'optimisation continue. L’utilisation de cette famille d'algorithmes est très populaire, malgré les nombreuses difficultés qui peuvent être rencontrées lors de leur conception. En effet, ces algorithmes ont plusieurs paramètres à régler et plusieurs opérateurs à fixer en fonction des problèmes à résoudre. Dans la littérature, on trouve pléthore d'opérateurs décrits, et il devient compliqué pour l'utilisateur de savoir lesquels sélectionner afin d'avoir le meilleur résultat possible. Dans ce contexte, cette thèse avait pour objectif principal de proposer des méthodes permettant de remédier à ces problèmes sans pour autant détériorer les performances de ces algorithmes. Ainsi nous proposons deux algorithmes :- une méthode basée sur le maximum a posteriori qui utilise les probabilités de diversité afin de sélectionner les opérateurs à appliquer, et qui remet ce choix régulièrement en jeu,- une méthode basée sur un graphe dynamique d'opérateurs représentant les probabilités de passages entre les opérateurs, et en s'appuyant sur un modèle de la fonction objectif construit par un réseau de neurones pour mettre régulièrement à jour ces probabilités. Ces deux méthodes sont détaillées, ainsi qu'analysées via un benchmark d'optimisation continue / The problems of continuous optimization are numerous, in economics, in signal processing, in neural networks, and so on. One of the best-known and most widely used solutions is the evolutionary algorithm, a metaheuristic algorithm based on evolutionary theories that borrows stochastic mechanisms and has shown good performance in solving problems of continuous optimization. The use of this family of algorithms is very popular, despite the many difficulties that can be encountered in their design. Indeed, these algorithms have several parameters to adjust and a lot of operators to set according to the problems to solve. In the literature, we find a plethora of operators described, and it becomes complicated for the user to know which one to select in order to have the best possible result. In this context, this thesis has the main objective to propose methods to solve the problems raised without deteriorating the performance of these algorithms. Thus we propose two algorithms:- a method based on the maximum a posteriori that uses diversity probabilities for the operators to apply, and which puts this choice regularly in play,- a method based on a dynamic graph of operators representing the probabilities of transitions between operators, and relying on a model of the objective function built by a neural network to regularly update these probabilities. These two methods are detailed, as well as analyzed via a continuous optimization benchmark

Le transport de matériaux pour la réalisation d’infrastructures routières et le terrassement représente, en 2013, plus de la moitié de l’activité du secteur des travaux publics. Les méthodes d’optimisation de tournées de véhicules permettent aujourd’hui de résoudre des problèmes de grandes tailles en intégrant les contraintes liées au métier. Dans cette thèse, nous nous intéressons à la résolution du problème riche de collectes et livraisons en camions complets avec des contraintes de synchronisation sur les ressources. Dans un premier temps, nous résolvons le problème de tournées de véhicules avec une méthode heuristique en deux phases. Dans un second temps, nous étudions l’intégration des contraintes liées aux temps de conduite des chauffeurs ainsi que l’ajout des pauses déjeuners aux tournées. Nous testons les algorithmes proposés sur des instances de la littérature et des instances réelles issues d’une application industrielle d’une entreprise de Travaux Publics. / In 2013, the transportation of materials for roads construction and earthwork represents more than half of the whole activity of in the public works sector. Optimization methods for vehicle routing problems allow to solve big-size problems with industrial sector constraints. In this thesis, we focus on solving the rich full truckload pickup and delivery problem with resource synchronization. First, we solve this vehicle routing problem with a two phase heuristic method. Then, we study the integration of regulation of drivers’ working hours and the addition of lunch breaks in routes of vehicles. These methods are tested on instances from the literature and real life instances from a public works company.

L'objectif du travail présenté dans cette thèse est de proposer une stratégie de planification automatique des réseaux locaux sans fil de type WiFi en environnement Indoor. Il s'agit de rechercher une ou plusieurs configurations des points d'accès (AP) au réseau garantissant une certaine qualité de service (QoS). La qualité d'une telle stratégie dépend en grande partie du modèle de prédiction de couverture radio utilisé. La première partie de ces travaux a donc été consacrée au développement et à la validation des prédictions de couverture radio du modèle Multi-Resolution Fourier Domain ParFlow (MR-FDPF). Une étape de calibration du modèle nous a permis de définir un paramétrage adéquat du modèle MR-FDPF pour des bâtiments standard, garantissant une erreur quadratique de moins de 5 dB.<br /><br />La seconde partie se concentre sur le problème de planification wLAN. Des critères de couverture radio, de minimisation des interférences, d'optimisation de la bande passante et d'amélioration des services de localisation ont été proposés. Deux heuristiques de recherche basées sur une approche Tabou ont été développées : une heuristique mono-objectif et une heuristique multiobjectifs. Ces travaux ont mis en évidence les avantages d'une recherche multiobjectifs car elle permet d'obtenir plusieurs solutions appartenant au front de Pareto de l'espace des fonctions associées au problème traité. Chaque solution représente alors un compromis différent entre les critères du problème à résoudre. Le choix de la solution à déployer se fait à posteriori dans l'ensemble limité des \textit{bonnes} solutions.

Les métaheuristiques de colonies de fourmis s'inspirent des comportements collectifs observés chez les fourmis pour résoudre des problèmes d'optimisation difficile.<br /><br />La première approche pour concevoir des métaheuristiques d'optimisation continue en suivant cette métaphore consiste à créer un système multi-agent. Nous proposons ainsi un algorithme de "colonies de fourmis interagissantes" (CIAC). La deuxième approche décrit ces métaheuristiques comme des méthodes manipulant un échantillonnage d'une distribution de probabilité. Nous proposons ainsi un algorithme "à estimation de distribution" (CHEDA).<br /><br />En accord avec le concept de programmation à mémoire adaptative, nos algorithmes font l'objet d'une hybridation avec une recherche locale de Nelder-Mead (HCIAC). Nous avons ensuite adapté cette méthode à des problèmes continus dynamiques (DHCIAC), pour lesquels nous proposons également un nouveau jeu de test cohérent.<br /><br />Nos algorithmes sont enfin appliqués dans le cadre de l'automatisation du suivi des lésions de l'oeil.