Spelling suggestions: "subject:"algorithmes génétique"" "subject:"lgorithmes génétique""
121 |
Approches générales de résolution pour les problèmes multi-attributs de tournées de véhicules et confection d'horairesVidal, Thibaut 03 1900 (has links)
Le problème de tournées de véhicules (VRP) implique de planifier les itinéraires d'une flotte de véhicules afin de desservir un ensemble de clients à moindre coût. Ce problème d'optimisation combinatoire NP-difficile apparait dans de nombreux domaines d'application, notamment en logistique, télécommunications, robotique ou gestion de crise dans des contextes militaires et humanitaires. Ces applications amènent différents contraintes, objectifs et décisions supplémentaires ; des "attributs" qui viennent compléter les formulations classiques du problème. Les nombreux VRP Multi-Attributs (MAVRP) qui s'ensuivent sont le support d'une littérature considérable, mais qui manque de méthodes généralistes capables de traiter efficacement un éventail significatif de variantes. Par ailleurs, la résolution de problèmes "riches", combinant de nombreux attributs, pose d'importantes difficultés méthodologiques.
Cette thèse contribue à relever ces défis par le biais d'analyses structurelles des problèmes, de développements de stratégies métaheuristiques, et de méthodes unifiées. Nous présentons tout d'abord une étude transversale des concepts à succès de 64 méta-heuristiques pour 15 MAVRP afin d'en cerner les "stratégies gagnantes". Puis, nous analysons les problèmes et algorithmes d'ajustement d'horaires en présence d'une séquence de tâches fixée, appelés problèmes de "timing". Ces méthodes, développées indépendamment dans différents domaines de recherche liés au transport, ordonnancement, allocation de ressource et même régression isotonique, sont unifiés dans une revue multidisciplinaire.
Un algorithme génétique hybride efficace est ensuite proposé, combinant l'exploration large des méthodes évolutionnaires, les capacités d'amélioration agressive des métaheuristiques à voisinage, et une évaluation bi-critère des solutions considérant coût et contribution à la diversité de la population. Les meilleures solutions connues de la littérature sont retrouvées ou améliorées pour le VRP classique ainsi que des variantes avec multiples dépôts et périodes. La méthode est étendue aux VRP avec contraintes de fenêtres de temps, durée de route, et horaires de conducteurs. Ces applications mettent en jeu de nouvelles méthodes d'évaluation efficaces de contraintes temporelles relaxées, des phases de décomposition, et des recherches arborescentes pour l'insertion des pauses des conducteurs. Un algorithme de gestion implicite du placement des dépôts au cours de recherches locales, par programmation dynamique, est aussi proposé. Des études expérimentales approfondies démontrent la contribution notable des nouvelles stratégies au sein de plusieurs cadres méta-heuristiques.
Afin de traiter la variété des attributs, un cadre de résolution heuristique modulaire est présenté ainsi qu'un algorithme génétique hybride unifié (UHGS). Les attributs sont gérés par des composants élémentaires adaptatifs. Des expérimentations sur 26 variantes du VRP et 39 groupes d'instances démontrent la performance remarquable de UHGS qui, avec une unique implémentation et paramétrage, égalise ou surpasse les nombreux algorithmes dédiés, issus de plus de 180 articles, révélant ainsi que la généralité ne s'obtient pas forcément aux dépends de l'efficacité pour cette classe de problèmes. Enfin, pour traiter les problèmes riches, UHGS est étendu au sein d'un cadre de résolution parallèle coopératif à base de décomposition, d'intégration de solutions partielles, et de recherche guidée.
L'ensemble de ces travaux permet de jeter un nouveau regard sur les MAVRP et les problèmes de timing, leur résolution par des méthodes méta-heuristiques, ainsi que les méthodes généralistes pour l'optimisation combinatoire. / The Vehicle Routing Problem (VRP) involves designing least cost delivery routes to service a geographically-dispersed set of customers while taking into account vehicle-capacity constraints. This NP-hard combinatorial optimization problem is linked with multiple applications in logistics, telecommunications, robotics, crisis management in military and humanitarian frameworks, among others. Practical routing applications are usually quite distinct from the academic cases, encompassing additional sets of specific constraints, objectives and decisions which breed further new problem variants. The resulting "Multi-Attribute" Vehicle Routing Problems (MAVRP) are the support of a vast literature which, however, lacks unified methods capable of addressing multiple MAVRP. In addition, some "rich" VRPs, i.e. those that involve several attributes, may be difficult to address because of the wide array of combined and possibly antagonistic decisions they require.
This thesis contributes to address these challenges by means of problem structure analysis, new metaheuristics and unified method developments. The "winning strategies" of 64 state-of-the-art algorithms for 15 different MAVRP are scrutinized in a unifying review. Another analysis is targeted on "timing" problems and algorithms for adjusting the execution dates of a given sequence of tasks. Such methods, independently studied in different research domains related to routing, scheduling, resource allocation, and even isotonic regression are here surveyed in a multidisciplinary review.
A Hybrid Genetic Search with Advanced Diversity Control (HGSADC) is then introduced, which combines the exploration breadth of population-based evolutionary search, the aggressive-improvement capabilities of neighborhood-based metaheuristics, and a bi-criteria evaluation of solutions based on cost and diversity measures. Results of remarkable quality are achieved on classic benchmark instances of the capacitated VRP, the multi-depot VRP, and the periodic VRP. Further extensions of the method to VRP variants with constraints on time windows, limited route duration, and truck drivers' statutory pauses are also proposed.
New route and neighborhood evaluation procedures are introduced to manage penalized infeasible solutions w.r.t. to time-window and duration constraints. Tree-search procedures are used for drivers' rest scheduling, as well as advanced search limitation strategies, memories and decomposition phases. A dynamic programming-based neighborhood search is introduced to optimally select the depot, vehicle type, and first customer visited in the route during local searches. The notable contribution of these new methodological elements is assessed within two different metaheuristic frameworks.
To further advance general-purpose MAVRP methods, we introduce a new component-based heuristic resolution framework and a Unified Hybrid Genetic Search (UHGS), which relies on modular self-adaptive components for addressing problem specifics. Computational experiments demonstrate the groundbreaking performance of UHGS. With a single implementation, unique parameter setting and termination criterion, this algorithm matches or outperforms all current problem-tailored methods from more than 180 articles, on 26 vehicle routing variants and 39 benchmark sets. To address rich problems, UHGS was included in a new parallel cooperative solution framework called "Integrative Cooperative Search (ICS)", based on problem decompositions, partial solutions integration, and global search guidance.
This compendium of results provides a novel view on a wide range of MAVRP and timing problems, on efficient heuristic searches, and on general-purpose solution methods for combinatorial optimization problems. / Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes
|
122 |
Multi-objective optimization for Green Supply Chain Management and Design : Application to the orange juice agrofood cluster / Optimisation multi-objectif pour la gestion et la conception d'une chaine logistique verte : Application au cas de la filière agroalimentaire du jus d'orangeMiranda Ackerman, Marco Augusto 05 November 2015 (has links)
La gestion de la chaîne logistique a gagné en maturité depuis l’extension de son champ d’application qui portait sur des problématiques opérationnelles et économiques s’est élargi à des questions environnementales et sociales auxquelles sont confrontées les organisations industrielles actuelles. L’addition du terme «vert» aux activités de la chaîne logistique vise à intégrer une conscience écologique dans tous les processus de la chaîne d'approvisionnement. Le but de ce travail est de développer un cadre méthodologique pour traiter la gestion de la chaîne logistique verte (GrSCM) basée sur une approche d'optimisation multi-objectif, en se focalisant sur la conception, la planification et les opérations de la chaîne agroalimentaire, à travers la mise en oeuvre des principes de gestion et de logistique de la chaîne d'approvisionnement verte. L'étude de cas retenu est la filière du jus d'orange. L'objectif du travail consiste en la minimisation de l'impact environnemental et la maximisation de la rentabilité économique pour des catégories de produits sélectionnés. Ce travail se concentre sur l'application de la GrSCM à deux questions stratégiques fondamentales visant les chaînes d'approvisionnement agroalimentaire. La première est liée au problème de la sélection des fournisseurs en produits « verts » (GSS) pour les systèmes de production agricole et à leur intégration dans le réseau globalisé de la chaîne d'approvisionnement. Le second se concentre sur la conception globale du réseau de la chaîne logistique verte (GSCND). Ces deux sujets complémentaires sont finalement intégrés afin d'évaluer et exploiter les caractéristiques des chaînes d'approvisionnement agro-alimentaire en vue du développement d’un éco-label. La méthodologie est basée sur le couplage entre analyse du cycle de vie (ACV), optimisation multi-objectifs par algorithmes génétiques et technique d’aide à la décision multicritère (de type TOPSIS). L’approche est illustrée et validée par le développement et l'analyse d'une étude de cas de la chaîne logistique de jus d'orange, modélisée comme une chaîne logistique verte (GrSC) à trois échelons composés de la production d’oranges, de leur transformation en jus, puis de leur distribution, chaque échelon étant modélisé de façon plus fine en sous-composants. D’un point de vue méthodologique, le travail a démontré l’intérêt du cadre de modélisation et d’optimisation de GrSC dans le contexte des chaînes d'approvisionnement, notamment pour le développement d’un éco-label dans le domaine de l’agro-alimentaire. Il peut aider les décideurs pour gérer la complexité inhérente aux décisions de conception de la chaîne d'approvisionnement agroalimentaire, induite par la nature multi-objectifs multi-acteurs multi-périodes du problème, empêchant ainsi une prise de décision empirique et segmentée. D’un point de vue expérimental, sous les hypothèses utilisées dans l'étude de cas, les résultats du travail soulignent que si l’on restreint l’éco-label "bio" à l'aspect agricole, seule une faible, voire aucune amélioration sur la performance environnementale de la chaîne d'approvisionnement n’est atteinte. La prise en compte des critères environnementaux pertinents sur l’ensemble du cycle de vie s’avère être une meilleure option pour les stratégies publiques et privées afin de tendre vers des chaînes agro-alimentaires plus durables. / Supply chain and operations management has matured from a field that addressed only operational and economic concerns to one that comprehensively considers the broader environmental and social issues that face industrial organizations of today. Adding the term “green” to supply chain activities seeks to incorporate environmentally conscious thinking in all processes in the supply chain. The aim of this work is to develop a Green Supply Chain (GrSC) framework based on a multi-objective optimization approach, with specific emphasis on agrofood supply chain design, planning and operations through the implementation of appropriate green supply chain management and logistics principles. The case study is the orange juice cluster. The research objective is the minimization of the environmental burden and the maximization of economic profitability of the selected product categories. This work focuses on the application of GrSCM to two fundamental strategic issues targeting agro food supply chains. The former is related to the Green Supplier Selection (GSS) problem devoted to the farming production systems and the way they are integrated into the global supply chain network. The latter focuses on the global Green Supply Chain Network Design (GSCND) as a whole. These two complementary and ultimately integrated strategic topics are framed in order to evaluate and exploit the unique characteristics of agro food supply chains in relation to eco-labeling. The methodology is based on the use of Life Cycle Assessment, Multi-objective Optimization via Genetic Algorithms and Multiple-criteria Decision Making tools (TOPSIS type). The approach is illustrated and validated through the development and analysis of an Orange Juice Supply Chain case study modelled as a three echelon GrSC composed of the supplier, manufacturing and market levels that in turn are decomposed into more detailed subcomponents. Methodologically, the work has shown the development of the modelling and optimization GrSCM framework is useful in the context of eco-labeled agro food supply chain and feasible in particular for the orange juice cluster. The proposed framework can help decision makers handle the complexity that characterizes agro food supply chain design decision and that is brought on by the multi-objective and multi-period nature of the problem as well as by the multiple stakeholders, thus preventing to make the decision in a segmented empirical manner. Experimentally, under the assumptions used in the case study, the work highlights that by focusing only on the “organic” eco-label to improve the agricultural aspect, low to no improvement on overall supply chain environmental performance is reached in relative terms. In contrast, the environmental criteria resulting from a full lifecycle approach is a better option for future public and private policies to reach more sustainable agro food supply chains.
|
123 |
Stratégies de regroupement pour la maintenance des systèmes à composants multiples avec structure complexe / Grouping strategies for the maintenance of multi-component systems with complex structureVu, Hai Canh 12 March 2015 (has links)
Au cours des dernières décennies, avec un fort développement de l'économie mondiale et des nouvelles technologies, la structure des systèmes industriels devient de plus en plus complexe. Elle peut être une combinaison des structures élémentaires telles que structures séries, structures parallèles, structures séries-parallèles, etc. Dans la littérature, la plupart des travaux s'intéressent à développer des stratégies de regroupement en considérant des structures séries. Cette hypothèse est parfois très pénalisée et se limite l'application de ces stratégies dans la réalité. C'est pourquoi, l'objectif principal de cette thèse est de développer des stratégies de regroupement (dynamique et stationnaire) pour la maintenance des systèmes multi-composants avec structure complexe. Ces stratégies développées se basent sur des modèles de durée de vie avec la durée de maintenance non-négligeable. De plus, les conditions dynamiques (contextes dynamiques) telles que opportunités de faire la maintenance, changements de la structure, etc. sont étudiées et intégrées dans la planification de maintenance. Les études montrent la nécessité et les difficultés de la prise en compte de la structure complexe dans les décisions de maintenance. Exemples numériques confirment les avantages de nos stratégies de maintenance en comparant avec les autres stratégies existantes dans la littérature / In the recent decades, with a strong development of the global economy and new technologies, the structure of industrial systems is more and more complex. It can be a combination of elementary structures such as series structures, parallel structures, series-parallel structures, etc. In the literature, the most work focused on developing grouping strategies by considering series structures. This assumption is sometimes much penalized and limited the application of these strategies in reality. Therefore, the main objective of this thesis is to develop dynamic and stationary grouping strategies for the maintenance of multi-component systems with complex structure. These strategies have been developed for age-based models with non-negligible maintenance durations. In addition, dynamic conditions (dynamic context) such as maintenance opportunities, changes of the structure, etc., are considered and integrated into the maintenance scheduling.Our studies show the necessity and the difficulties of taking into account of the complex structure in the maintenance decisions. Numerical examples confirm the advantages of our maintenance strategies by comparing with other existing strategies in the literature
|
124 |
Conception d’une architecture robuste pour l’acquisition de grandeurs physiques dans un système aéronautique critique : application à la mesure de température, pression, couple, et vitesse d’une turbomachine / Design of an architecture for measurement and diagnosis of physical parameters in critical airborne systemsMartin, Romain 03 April 2015 (has links)
L’acquisition de paramètres physiques tels que la température, la pression, le couple et la vitesse est nécessaire aux systèmes aéronautiques critiques afin d’atteindre et d’assurer les performances requises de disponibilité et de sécurité de fonctionnement. L’acquisition de ces paramètres physiques nécessite donc la mise en oeuvre de technologies et de techniques hautement éprouvées pouvant supporter les conditions de fonctionnement sévères.L'objectif des travaux présentés dans ce mémoire est de proposer une nouvelle architecture de chaîne d'acquisition de grandeurs physiques pour être intégrée à un système aéronautique critique. Le but de cette architecture est d'améliorer l'intégrité des données mesurées tout en maintenant leur disponibilité et le niveau de sûreté de fonctionnement propre aux systèmes aéronautiques de haute criticité. La solution se déploie sous la forme d'une amélioration de la tolérance aux défauts de la chaîne de traitement du signal issu du capteur. Pour ce faire, nous intégrons des fonctions supplémentaires, dont le modèle mathématique de la chaîne d'acquisition, rendant ainsi le système plus intelligent.Dans le cadre de nos travaux de recherche, nous nous appuyons sur les spécifications techniques d'un projet industriel typique des systèmes aéronautiques critiques, qui est le coeur de notre thématique principale. / The acquisition of physical parameters as such as temperature, pressure, torque, and speed are necessary to flight critical systems in order to reach and ensure safety and availability required. Consequently, it requires implementing high technologies and techniques which are able to work in rugged environments.The aim of our work is to design a new architecture for sensor acquisition systems in order to be integrated onto a flight critical system. The goal of the architecture is to ensure data integrity, system's availability and safety relative to airborne critical systems. The solution adds the fault tolerance ability to the signal conditioning. Consequently, we implement additional functionalities, as such as mathematical model of the signal conditioning, in order to make the acquisition system more intelligent.Our research work is partially based on technical specifications from SYRENA project, which is a typical example of flight critical systems, which is the main thematic of our purpose.
|
125 |
Evaluation de la performance acoustique des protections antibruit innovantes utilisant des moyens naturels : application aux transports terrestresKoussa, Faouzi 28 September 2012 (has links)
Le bruit dû aux infrastructures de transports terrestres fait partie des premières préoccupations environnementales de ce début de 21e siècle. Un moyen utilisé pour réduire ce bruit est de placer des protections acoustiques le long des grands axes routiers et ferroviaires. Actuellement, les choix de ces protections antibruit se portent généralement sur des solutions traditionnelles : écran droit, merlon, écran incliné, écran avec un couronnement. Le but de ce travail est de proposer des protections acoustiques innovantes utilisant des moyens naturels et d’en étudier la performance acoustique en utilisant des approches numériques et expérimentales. L’approche numérique peut être couplée en outre à un outil d’optimisation, développé dans cette thèse, pour chercher des formes améliorées de tels dispositifs antibruit novateurs. Après une présentation des principaux phénomènes mis en jeu dans la propagation des ondes acoustiques en milieu extérieur complexe, un état de l’art des principaux écrans acoustiques dédiés aux transports terrestres a été établi, permettant de choisir trois protections antibruit innovantes pour en étudier la performance acoustique. Une analyse des principales méthodes de simulation numérique, de mesure et d’optimisation des protections antibruit a permis de choisir les méthodes adaptées à notre problématique des écrans acoustiques utilisant des moyens naturels. Les méthodes choisies ont été utilisées dans ce travail pour évaluer la performance acoustique de ces écrans innovants. Pour le premier écran choisi, dit écran en gabions, nous avons effectué des mesures in-situ et sur modèles réduits, ainsi que des simulations numériques montrant une efficacité satisfaisante. Pour le deuxième écran, utilisant des cristaux soniques, et pour le troisième écran, de type merlon acoustique de forme complexe, nous avons réalisé une étude numérique paramétrique suivie d’une étude d’optimisation. Les résultats des calculs ont montré l’intérêt de tels dispositifs antibruit pour réduire le bruit de circulation routière et ferroviaire en milieu urbain et ils ont abouti à des formes améliorées des protections acoustiques utilisant des moyens naturels. / Noise due to ground transportation infrastructures is among the first environmental concerns of this beginning of 21th century. Building noise protections along motorways and railways is usually the chosen solution to reduce this noise. Currently, noise abatement systems used are mainly conventional ones: straight barriers, earth berms, tilted barriers, capped barriers. The purpose of this work is to propose innovative noise barriers using natural means and to study their acoustic performance by using numerical and experimental approaches. The numerical approach can also be coupled with an optimization tool, developed in this thesis, to obtain improved shapes of such devices using natural means. First, the main phenomena that appear during acoustic wave propagation in a complex outdoor medium are described. Then, a state of the art of the main noise barriers dedicated to ground transportation noise is achieved. It drives the choice of three innovative noise barriers using natural means. An analysis of the main numerical, experimental and optimization methods is carried out which allows to choose the methods adapted to our problem of noise barriers using natural means. The chosen methods are used in this work to assess the acoustic performance of the three innovative noise barriers. For the first chosen noise barrier called “gabions barrier”, we perform in-situ and scale model measurements and numerical simulations. The results show a satisfactory efficiency of such noise devices. For the second and the third chosen noise barriers called respectively “sonic crystal assisted barrier” and “complex shaped earth berm”, we perform a parametric numerical and an optimization studies. The results show the capacity of such noise devices to reduce motorways and railways noises in urban areas and they lead to improved shapes of innovative noise barriers using natural means.
|
126 |
Optimization of an innovative thermal energy storage technology at low temperatures when coupled to multi-source energy architectures / Optimisation d'une technique avancée de stockage d'énergie thermique couplée à des architectures énergétiques multi-sourcesRoccamena, Letizia 15 December 2017 (has links)
A ce jour, les solutions de stockage d'énergie apparaissent comme des solutions pertinentes permettant d'atteindre les cibles énergétiques futures et de répondre aux exigences environnementales actuelles. Le but de cette thèse est d’optimiser un système de stockage d'énergie thermique innovant basé sur un échangeur eau – matériaux à changement de phase. Ce système est couplé à l’architecture énergétique multi-sources d’un îlot composé de trois bâtiments à énergie positive situé à Lyon : l’îlot HIKARI. Afin de disposer d’un outil numérique robuste pour pouvoir optimiser cette technologie, un modèle numérique du système de stockage d’énergie thermique a été développé dans le but de reproduire le comportement du système de stockage de référence. Une fois fini, le modèle a été validé en trois étapes: une numérique et deux expérimentales. Dans un premier temps il a été validé numériquement, en comparant ses résultats avec un modèle conçu en adoptant une approche numérique différente (« Computational Fluid Dynamics »), dans un second temps il a été validé à l’échelle réelle en exploitant les données in-situ du système de HIKARI. Enfin, le modèle numérique a été validé expérimentalement grâce à un prototype expérimental conçu et réalisé à l’ENTPE dans le cadre des travaux de cette thèse reproduisant le comportement du système de stockage étudié. Après avoir été validé, le modèle a été utilisé pour procéder à l’optimisation de sa performance en utilisant la technique des algorithmes génétiques. L’analyse des résultats de ces simulations a notamment abouti sur des recommandations de dimensionnement et d’usage pour l’Ilot HIKARI et des bâtiments futurs intégrant la technologie de stockage étudiée. La thèse a été financée par l’Agence de l’environnement et de la maîtrise de l’énergie (ADEME) dans le cadre du projet « Optimisation des architectures Énergétiques multi-sources couplées aux techniques avancées du stockage d'énergie dans le bâtiment » en partenariat avec Bouygues immobilier et Manaslu – CMDL. / One of the most promising technics used in building applications for energy efficiency purposes is the thermal energy storage (TES). Despite the thorough research on TES techniques of the last years, the release to market of cost effective technologies is quite recent. The aim of this study is to optimize the energetic behavior of an innovative TES technology consisting on a water/PCM exchanger that is part of the multi-energy production and storage systems of HIKARI, a positive energy district located in Lyon and consisting of three buildings. In order to optimize this innovative technic, a numerical model reproducing the functioning of the reference system was created. In order to make a numerical validation a second numerical model was developed using a different software based on a different numerical method and, once the in situ data obtained from the reference system monitoring, a first experimental validation was obtained. Subsequently, an innovative experimental prototype reproducing the behavior of the reference PCM-Water heat exchanger has been realized, in order to validate and calibrate the numerical model and carry out a large amount of operating scenarios. Once the model numerically and experimentally validated, the optimization of the HIKARI’s cold storage system technology has been obtained using Genetic Algorithms (GAs) finding the best values to allocate to four characteristics of the cold storage system, in order to minimize two predefined objective functions linked to its functioning. This work was supported by the French Agency for Environment and Energy Management (ADEME) and it was part of the project “Optimization of innovative energy storage technologies when coupled to multi-sources energy architectures”, in cooperation with Bouygues immobilier and Manaslu – CMDL.
|
127 |
Simulation and optimization of energy consumption in wireless sensor networks / Simulation et optimisation de la consommation énergétique de réseaux de capteurs sans filZhu, Nanhao 11 October 2013 (has links)
Les grandes évolutions de la technique de systèmes embarqués au cours des dernières années ont permis avec succès la combinaison de la détection, le traitement des données, et diverses technologies de communication sans fil tout en un nœud. Les réseaux de capteurs sans fil (WSN) qui se composent d’un grand nombre de ces nœuds ont attiré l’attention du monde entier sur les établissements scolaires et les communautés industrielles, puisque leurs applications sont très répandues dans des domaines tels que la surveillance de l’environnement, le domaine militaire, le suivi des événements et la détection des catastrophes. En raison de la dépendance sur la batterie, la consommation d’énergie des réseaux de capteurs a toujours été la préoccupation la plus importante. Dans cet article, une méthode mixte est utilisée pour l’évaluation précise de l’énergie sur les réseaux de capteurs, ce qui inclut la conception d’un environnement de SystemC simulation base au niveau du système et au niveau des transactions pour l’exploration de l’énergie, et la construction d’une plate-forme de mesure d’énergie pour les mesures de nœud banc d’essai dans le monde réel pour calibrer et valider à la fois le modèle de simulation énergétique de nœud et le modèle de fonctionnement. La consommation d’énergie élaborée de plusieurs différents réseaux basés sur la plate-forme de nœud sont étudiées et comparées dans différents types de scénarios, et puis des stratégies globales d’économie d’énergie sont également données après chaque scénario pour les développeurs et les chercheurs qui se concentrent sur la conception des réseaux de capteurs efficacité énergétique. Un cadre de l’optimisation basée sur un algorithme génétique est conçu et mis en œuvre à l’aide de MATLAB pour les réseaux de capteurs conscients de l’énergie. En raison de la propriété de recherche global des algorithmes génétiques, le cadre de l’optimisation peut automatiquement et intelligemment régler des centaines de solutions possibles pour trouver le compromis le plus approprié entre la consommation d’énergie et d’autres indicateurs de performance. Haute efficacité et la fiabilité du cadre de la recherche des solutions de compromis entre l’énergie de nœud, la perte de paquets réseau et la latence ont été prouvés par réglage paramètres de l’algorithme CSMA / CA de unslotted (le mode non-beacon de IEEE 802.15.4) dans notre simulation basé sur SystemC via une fonction de coût de la somme pondérée. En outre, le cadre est également disponible pour la tâche d’optimisation basée sur multi-scénarios et multi-objectif par l’étude d’une application médicale typique sur le corps humain. / The great technique developments of embedded system in recent years have successfully enabled the combination of sensing, data processing and various wireless communication technologies all in one node. Wireless sensor networks (WSNs) that consist of many of such node have gained worldwide attention from academic institutions and industrial communities, since their applications are widespread in such as environment monitoring, military fields, event tracing/tracking and disaster detection. Due to the reliance on battery, energy consumption of WSNs has always been the most significant concern. In this paper, a mixed method is employed for the accurate energy evaluation on WSNs, which involves the design of a transaction-level system-level based SystemC simulation environment for energy exploration, and the building of an energy measurement system platform for the real world testbed node measurements to calibrate and validate both node energy simulation model and operation model. Elaborate energy consumption of several different node platform based networks are investigated and compared under different kinds of scenarios, and then comprehensive energy-saving strategies are also given after each case scenario for the developers and researchers who focus on the energy-efficient WSNs design. A genetic algorithm (GA) based optimization framework is designed and implemented using MATLAB for the energy aware WSNs. Due to the global search property of genetic algorithms, the optimization framework is able to automatically and intelligently fine tune hundreds/thousands of potential solutions to find the most suitable tradeoff among energy consumption and other performance metrics. The framework’s high efficiency and reliability of finding the tradeoff solutions among node energy, network packet loss and latency have been proved by tuning unslotted CSMA/CA algorithm parameters (used by non-beacon mode of IEEE 802.15.4) in our SystemC-based simulation via a weighted sum cost function. Furthermore, the framework is also available for the multi-scenario and multi-objective based optimization task by studying a typical medical application on human body. Keywords: Wireless sensor networks (WSNs), energy consumption, simulation/emulation, SystemC, testbeds, measurements, calibration, optimization, genetic algorithms, performance metrics, weighted sum cost function, multi-scenario and multi-objective optimization, Pareto-front
|
128 |
Models and methods for molecular phylogeneticsCatanzaro, Daniele 28 October 2008 (has links)
Un des buts principaux de la biologie évolutive et de la médecine moléculaire consiste à reconstruire les relations phylogénétiques entre organismes à partir de leurs séquences moléculaires. En littérature, cette question est connue sous le nom d’inférence phylogénétique et a d'importantes applications dans la recherche médicale et pharmaceutique, ainsi que dans l’immunologie, l’épidémiologie, et la dynamique des populations. L’accumulation récente de données de séquences d’ADN dans les bases de données publiques, ainsi que la facilité relative avec laquelle des données nouvelles peuvent être obtenues, rend l’inférence phylogénétique particulièrement difficile (l'inférence phylogénétique est un problème NP-Hard sous tous les critères d’optimalité connus), de telle manière que des nouveaux critères et des algorithmes efficaces doivent être développés. Cette thèse a pour but: (i) d’analyser les limites mathématiques et biologiques des critères utilisés en inférence phylogénétique, (ii) de développer de nouveaux algorithmes efficaces permettant d’analyser de plus grands jeux de données. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished
|
129 |
Ant colony optimization for continuous and mixed-variable domainsSocha, Krzysztof 09 May 2008 (has links)
In this work, we present a way to extend Ant Colony Optimization (ACO), so that it can be applied to both continuous and mixed-variable optimization problems. We demonstrate, first, how ACO may be extended to continuous domains. We describe the algorithm proposed, discuss the different design decisions made, and we position it among other metaheuristics.<p>Following this, we present the results of numerous simulations and testing. We compare the results obtained by the proposed algorithm on typical benchmark problems with those obtained by other methods used for tackling continuous optimization problems in the literature. Finally, we investigate how our algorithm performs on a real-world problem coming from the medical field—we use our algorithm for training neural network used for pattern classification in disease recognition.<p>Following an extensive analysis of the performance of ACO extended to continuous domains, we present how it may be further adapted to handle both continuous and discrete variables simultaneously. We thus introduce the first native mixed-variable version of an ACO algorithm. Then, we analyze and compare the performance of both continuous and mixed-variable<p>ACO algorithms on different benchmark problems from the literature. Through the research performed, we gain some insight into the relationship between the formulation of mixed-variable problems, and the best methods to tackle them. Furthermore, we demonstrate that the performance of ACO on various real-world mixed-variable optimization problems coming from the mechanical engineering field is comparable to the state of the art. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished
|
130 |
Theoretical and practical aspects of ant colony optimizationBlum, Christian 23 January 2004 (has links)
Combinatorial optimization problems are of high academical as well as practical importance. Many instances of relevant combinatorial optimization problems are, due to their dimensions, intractable for complete methods such as branch and bound. Therefore, approximate algorithms such as metaheuristics received much attention in the past 20 years. Examples of metaheuristics are simulated annealing, tabu search, and evolutionary computation. One of the most recent metaheuristics is ant colony optimization (ACO), which was developed by Prof. M. Dorigo (who is the supervisor of this thesis) and colleagues. This thesis deals with theoretical as well as practical aspects of ant colony optimization.<p><p>* A survey of metaheuristics. Chapter 1 gives an extensive overview on the nowadays most important metaheuristics. This overview points out the importance of two important concepts in metaheuristics: intensification and diversification. <p><p>* The hyper-cube framework. Chapter 2 introduces a new framework for implementing ACO algorithms. This framework brings two main benefits to ACO researchers. First, from the point of view of the theoretician: we prove that Ant System (the first ACO algorithm to be proposed in the literature) in the hyper-cube framework generates solutions whose expected quality monotonically increases with the number of algorithm iterations when applied to unconstrained problems. Second, from the point of view of the experimental researcher, we show through examples that the implementation of ACO algorithms in the hyper-cube framework increases their robustness and makes the handling of the pheromone values easier.<p><p>* Deception. In the first part of Chapter 3 we formally define the notions of first and second order deception in ant colony optimization. Hereby, first order deception corresponds to deception as defined in the field of evolutionary computation and is therefore a bias introduced by the problem (instance) to be solved. Second order deception is an ACO-specific phenomenon. It describes the observation that the quality of the solutions generated by ACO algorithms may decrease over time in certain settings. In the second part of Chapter 3 we propose different ways of avoiding second order deception.<p><p>* ACO for the KCT problem. In Chapter 4 we outline an ACO algorithm for the edge-weighted k-cardinality tree (KCT) problem. This algorithm is implemented in the hyper-cube framework and uses a pheromone model that was determined to be well-working in Chapter 3. Together with the evolutionary computation and the tabu search approaches that we develop in Chapter 4, this ACO algorithm belongs to the current state-of-the-art algorithms for the KCT problem.<p><p>* ACO for the GSS problem. Chapter 5 describes a new ACO algorithm for the group shop scheduling (GSS) problem, which is a general shop scheduling problem that includes among others the well-known job shop scheduling (JSS) and the open shop scheduling (OSS) problems. This ACO algorithm, which is implemented in the hyper-cube framework and which uses a new pheromone model that was experimentally tested in Chapter 3, is currently the best ACO algorithm for the JSS as well as the OSS problem. In particular when applied to OSS problem instances, this algorithm obtains excellent results, improving the best known solution for several OSS benchmark instances. A final contribution of this thesis is the development of a general method for the solution of combinatorial optimization problems which we refer to as Beam-ACO. This method is a hybrid between ACO and a tree search technique known as beam search. We show that Beam-ACO is currently a state-of-the-art method for the application to the existing open shop scheduling (OSS) problem instances.<p><p> / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished
|
Page generated in 0.2287 seconds