Aujourd'hui, les réseaux de distribution sont de plus en plus complexes à cause de composants non linéaires (nouveaux types de sources, production décentralisée (PD) à taux de pénétration significatif, charges contrôlables, convertisseurs d'électronique de puissance) qui ont un comportement dynamique de plus en plus prépondérant, ce qui amène à de nouveaux besoins en terme de modélisation et de simulation, notamment vu des réseaux de transport. En effet, les réseaux de distribution sont les charges des réseaux de transport et leur impact dynamique sur ces mêmes réseaux de transport devient de plus en plus important. Il est donc nécessaire de développer des équivalents dynamiques des réseaux de distribution afin de pouvoir effectuer des simulations de grands réseaux de transport utilisant des modèles de taille raisonnable. Dans ce contexte, l'objectif de la thèse est de développer des équivalents dynamiques des réseaux de distribution en utilisant des méthodes d'estimation de paramètres basées sur des mesures prises à la frontière entre le réseau de transport et le réseau de distribution à réduire. Cette estimation de paramètres consiste en une minimisation d'une erreur quadratique entre la mesure et le résultat de la simulation avec modèle équivalent. Pour cette minimisation, on utilise des méthodes évolutionnaires (AG " Algorithme Génétique ", PSO " Particle Swarm Optimization "). L'originalité principale de la thèse par rapport aux travaux déjà effectués sur le même thème réside dans le développement d'une méthodologie de calcul systématique et adaptée des régulations des modèles équivalents. Il a en effet été montré dans la thèse qu'un calcul précis et méthodologique de ces régulateurs permet d'obtenir une meilleure précision des équivalents qu'un choix plus ou moins arbitraire ou par similitude des régulations et de leurs paramètres comme cela se pratique usuellement. Des validations de la méthodologie proposée ont été faites sur le réseau de transport test IEEE New-England 39 noeuds et sur ce même réseau test couplé à un réseau de distribution.

Cette recherche porte sur l'exploration et la qualification des dispositifs évolutionnaires appliquées à la conception architecturale. Ici, ce sont les qualités environnementales et plus particulièrement les qualités solaires passives de l'enveloppe de l'édifice qui guideront le processus évolutionnaire. Nous nous attachons plus particulièrement aux phases initiales de la conception, et nous cherchons à spécifier un outil d'assistance favorisant et stimulant une conception créative. Après avoir établi et structuré une connaissance sur les processus de conception, sur la créativité, sur les qualités thermiques et sur les méthodes évolutionnaires, nous proposons un outil prototypal, fondé sur un algorithme génétique et implanté dans un logiciel de type modeleur. Celui-ci a été expérimenté dans le milieu pédagogique, et nous a conduit à caractériser les modalités de création et de conceptualisation de la forme architecturale dans le cadre d'une instrumentation évolutionnaire. Ainsi nous notons le basculement cognitif d'une pensée implicite vers une pensée explicite comme caractéristique fondamentalement de l'instrumentation générative. De plus nous insistons sur l'importance de l'indétermination signifiante comme composante essentielle de la création. Enfin nous proposons la notion de « trans-forme » comme élément caractéristique d'une pensée du processus et de la multiplicité. Cette « meta-forme » serait issue de la description des conditions de mise en forme à travers la paramétrisation des comportements aux limites et des modalités d'émergence.

Les problèmes d'ordonnancement peuvent être rencontrés dans plusieurs situations de la vie courante. Organiser des activités quotidiennes, planifier un itinéraire de voyage sont autant d'exemples de petits problèmes d'optimisation que nous tentons de résoudre tous les jours sans nous en rendre compte. Mais quand ces problèmes prennent des proportions plus grandes, il devient difficile au cerveau humain de gérer tous ces paramètres et le recours à une solution informatique s'impose. Les problèmes d'ordonnancement en contexte industriel sont nombreux et celui qui retient particulièrement notre attention dans le cadre de ce mémoire est le problème d'ordonnancement de commandes sur machine unique avec temps de réglages dépendant de la séquence. Ce problème fait partie de la classe de problèmes NP-Difficiles. Etant donnée sa complexité, ce problème ne peut être résolu par une méthode exacte. Les métaheuristiques représentent ainsi une bonne alternative pour obtenir des solutions de bonne qualité dans des délais très courts. Les algorithmes génétiques, qui font partie des algorithmes évolutionnaires, sont utilisés dans ce travail pour résoudre ce problème d'ordonnancement. La prolifération des architectures parallèles a ouvert la voie à un nouvel éventail d'approches pour optimiser les algorithmes et plus spécialement les métaheuristiques. Ce mémoire propose une stratégie de parallélisation de l'algorithme génétique pour en étudier les bénéfices. Le premier algorithme génétique proposé est implémenté sur le modèle d'un algorithme de la littérature. Cet algorithme ne s'est pas avéré performant pour toute la série de problèmes test et, pour cette raison, des modifications de paramètres ont été rendues nécessaires. Ces modifications ont donné naissance à une deuxième version séquentielle dont les résultats se sont avérés satisfaisants. Une troisième version a ensuite été implémentée avec une optique d'exécution parallèle selon un modèle en îlot et une topologie en anneau unidirectionnel. Un plan d'expérience a ensuite été mis au point selon plusieurs variables et vise à identifier les meilleures configurations de l'algorithme tant sur le plan de la qualité des résultats que sur le plan de l'accélération. Les résultats obtenus dans ce mémoire montrent que l'introduction de la parallélisation dans un algorithme génétique est bénéfique à ce dernier tant sur le plan qualité des résultats que sur le plan accélération. Dans un premier temps, la version sans communications n'a pas amélioré une grande partie des problèmes mais a pu atteindre des accélérations linéaires. Par la suite, l'introduction des échanges a nettement influé sur la qualité des résultats. En effet, en adoptant une stratégie de division de la taille de la population par le nombre de processeurs, l'algorithme génétique parallèle parvient à donner des résultats équivalents voire meilleurs que la version séquentielle, et ceci pour plusieurs fréquences d'échanges entre les populations.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

En zone dense, la croissance actuelle du trafic sur les lignes ferroviaires suburbaines conduit les exploitants à déployer des systèmes de contrôle-commande avancés des trains, tels que les systèmes dits « CBTC » (Communication Based Train Control) jusque-là réservés aux systèmes de métro. Les systèmes CBTC mettent en œuvre un pilotage automatique des trains et permettent une amélioration significative des performances. Par ailleurs, ils peuvent inclure un module de supervision de la ligne en charge de réguler la marche des trains en cas d’aléa, améliorant ainsi la robustesse du trafic. Face au problème de régulation, la recherche opérationnelle a produit un certain nombre de méthodes permettant de répondre efficacement aux perturbations, d’une part dans le secteur métro et d’autre part dans le secteur ferroviaire lourd. En tirant profit de l’état de l’art et des avancées faites dans les deux secteurs, les travaux présentés dans ce manuscrit cherchent à contribuer à l’adaptation des fonctions de régulation des systèmes CBTC pour l’exploitation de lignes ferroviaires suburbaines. L’approche du problème débute par la construction de l’architecture fonctionnelle d’un module de supervision pour un système CBTC standard. Nous proposons ensuite une méthode de régulation basée sur une stratégie de commande prédictive et sur une optimisation multi-objectif des consignes des trains automatiques. Afin d’être en mesure d’évaluer précisément les performances d’une ligne ferroviaire suburbaine équipée d’un automatisme CBTC, il est nécessaire de s’équiper d’un outil de simulation microscopique adapté. Nous présentons dans ce manuscrit l’outil SNCF nommé SIMONE qui permet une simulation réaliste du point de vue fonctionnel et dynamique d’un système ferroviaire incluant un système CBTC. Les objectifs des travaux de thèse nous ont naturellement conduits à prendre part, avec l’équipe SNCF, à la spécification, à la conception et à l’implémentation de cet outil. Finalement, grâce à l’outil SIMONE, nous avons pu tester la méthode de régulation proposée sur des scénarios impliquant des perturbations. Afin d’évaluer la qualité des solutions, la méthode multi-objectif proposée a été comparée à une méthode de régulation individuelle basée sur une heuristique simple. La méthode de régulation multi-objectif propose de bonnes solutions au problème, dans la majorité des cas plus satisfaisantes que celles proposées par la régulation individuelle, et avec un temps de calcul jugé acceptable. Le manuscrit se termine par des perspectives de recherche intéressantes. / In high-density area, the demand for railway transportation is continuously increasing. Operating companies turn to new intelligent signaling and control systems, such as Communication Based Train Control (CBTC) systems previously deployed on underground systems only. CBTC systems operate trains in automatic pilot and lead to increase the line capacity without expensive modification of infrastructures. They can also include a supervision module in charge of adapting train behavior according to operating objectives and to disturbances, increasing line robustness. In the literature of real-time traffic management, various methods have been proposed to supervise and reschedule trains, on the one hand for underground systems, on the other hand for railway systems. Making the most of the state-of-the-art in both fields, the presented work intend to contribute to the design of supervision and rescheduling functions of CBTC systems operating suburban railway systems. Our approach starts by designing a supervision module for a standard CBTC system. Then, we propose a rescheduling method based on a model predictive control approach and a multi-objective optimization of automatic train commands. In order to evaluate the performances of a railway system, it is necessary to use a microscopic simulation tool including a CBTC model. In this thesis, we present the tool developed by SNCF and named SIMONE. It allows realistic simulation of a railway system and a CBTC system, in terms of functional architecture and dynamics. The presented work has been directly involved in the design and implementation of the tool. Eventually, the proposed rescheduling method was tested with the tool SIMONE on disturbed scenarios. The proposed method was compared to a simple heuristic strategy intending to recover delays. The proposed multi-objective method is able to provide good solutions to the rescheduling problem and over-performs the simple strategy in most cases, with an acceptable process time. We conclude with interesting perspectives for future work.

Les problèmes de placement sont généralement NP-difficiles, ou NP-complets suivant l'objectif à atteindre. Il s'agit ici de positionner un ensemble d'objets dans un ou plusieurs “container(s)”, de dimensions données ou de hauteur infinie, en respectant des contraintes liées à certaines caractéristiques (poids, quantité, rotation, équilibre, découpe guillotine...). Ces problèmes ont de nombreuses applications pratiques. Les stratégies de résolution les plus efficaces sont généralement les méthodes approchées, en particulier la recherche locale. Dans cette thèse, nous nous intéressons à un problème de placement particulier en deux dimensions (sans rotation possible des objets (rectangulaires) ni prise en compte de la contrainte guillotine) connu sous le nom de “strip packing” (SPP). L'objectif de ce problème est de minimiser la hauteur atteinte après placement (sans chevauchement) des objets. Nous avons développé deux approches “méta-heuristiques” incluant des composants novateurs reposant sur une connaissance approfondie du problème. La première est un algorithme génétique avec un nouveau croisement (très “visuel”) et une fonction d'évaluation hiérarchique. La seconde est une recherche tabou avec représentation “directe” (i.e. n'utilisant pas les habituelles permutations) dont les caractéristiques principales sont un voisinage consistant, une diversification reposant sur l'historique de la recherche et une fonction d'évaluation qui mesure la qualité de solutions éventuellement partielles. Les deux approches proposées, évaluées sur un jeux de test bien connu et très difficile, se sont révélées performantes comparées à d'autres stratégies.

La plupart des méthodes d'ordonnancement considèrent un environnement déterministe où les données du problème sont connues. Néanmoins, en réalité, plusieurs sortes d'aléas peuvent être rencontrées et l'ordonnancement robuste permet en tenir compte. Dans cette thèse, notre intuition initiale est que, d'une part, un ordonnancement non robuste deviendra rapidement inefficace avec les incertitudes qu'un ordonnancement robuste, et d'autre part, un ordonnancement robuste sera moins efficace qu'un ordonnancement non robuste en l'absence d'incertitudes. Dans ce cadre, nous avons proposé un algorithme génétique pour l'ordonnancement robuste. Un nouveau mécanisme de résolution et un nouveau critère de robustesse permettant de trouver une solution de bonne performance et peu sensible aux incertitudes ont été développés. Une phase expérimentale a été menée, d'une part, pour vérifier l'efficacité de l'algorithme génétique pour l'ordonnancement déterministe, sans tenir compte des incertitudes, et d'autre part, pour valider l'algorithme génétique pour l'ordonnancement robuste par la simulation afin de juger la qualité de la robustesse face aux incertitudes. Nous avons intégré cette approche de robustesse dans une démarche méthodologique générique intégrant des techniques d'optimisation et de simulation pour l'aide au dimensionnement des systèmes de production basé sur des ordonnancements robustes. Les différents modules de la démarche ont été développés sous forme d'un outil d'aide au dimensionnement, dans le cadre d'un cas applicatif réel, celui du bloc opératoire dans le secteur hospitalier.

Le développement de créatures artificielles est un domaine de recherche en plein essor. Depuis plus de vingt ans maintenant, de nombreuses techniques sont apparues afin de simuler à plusieurs niveaux des êtres artificiels : en commençant par la simulation de leur comportement au début des années 90, on a ensuite continué en modifiant leur morphologie pour qu'elle soit adaptée à leur environnement. Plus récemment, l'embryogenèse artificielle s'inspire des mécanismes de développement du vivant afin de générer de petites créatures de quelques dizaines à plusieurs centaines de cellules. Le but de ces systèmes est d'une part de mieux comprendre le vivant mais aussi de produire des modèles comportementaux pour les futurs robots modulaires. Après avoir étudié ces différents niveaux de simulation, nous nous sommes aperçus qu'il n'existait pas de modèle transversal permettant une simulation à plusieurs échelles des créatures. Le but de ces travaux est de développer une créature complète en partant d'une cellule unique, possédant différents organes et des fonctionnalités haut niveau. Le but de cette thèse est de construire le modèle chimique de cet ensemble de simulateurs. Nous avons ainsi proposé un modèle basé sur une forte simplification du modèle de développement naturel. Les créatures devront de plus intégrer un métabolisme afin de pouvoir extraire de l'énergie des différents constituants de son environnement. Ce métabolisme est trop souvent oublié dans les modèles de développement de la littérature bien qu'il soit à la base de la vie de tous les êtres vivants. A travers différentes expérimentations que nous avons effectuées, nous avons prouvé que ce modèle est capable de produire différents organes et de les assembler afin de créer un organisme plus complexe. Nous avons aussi montré la possibilité à produire une forme particulière. Enfin, nous avons observé d'importantes capacités d'auto-réparation inhérentes au modèle. Ce modèle de développement est un premier simulateur qui sera inclu dans un ensemble de simulateurs agissants à différentes échelles de la créature. Comme nous le verrons dans les perspectives de ces travaux, nous avons commencé à imaginer un simulateur physique et un simulateur hydrodynamique permettant de plonger une créature en train de se développer dans un monde physique aux lois newtoniennes et un monde hydrodynamique répondant aux équations de Navier et Stokes.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.