• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 41
  • 19
  • 3
  • Tagged with
  • 63
  • 50
  • 32
  • 32
  • 24
  • 17
  • 17
  • 16
  • 16
  • 11
  • 9
  • 9
  • 8
  • 7
  • 7
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
41

Découverte de règles d'association multi-relationnelles à partir de bases de connaissances ontologiques pour l'enrichissement d'ontologies / Discovering multi-relational association rules from ontological knowledge bases to enrich ontologies

Tran, Duc Minh 23 July 2018 (has links)
Dans le contexte du Web sémantique, les ontologies OWL représentent des connaissances explicites sur un domaine sur la base d'une conceptualisation des domaines d'intérêt, tandis que la connaissance correspondante sur les individus est donnée par les données RDF qui s'y réfèrent. Dans cette thèse, sur la base d'idées dérivées de l'ILP, nous visons à découvrir des motifs de connaissance cachés sous la forme de règles d'association multi-relationnelles en exploitant l'évidence provenant des assertions contenues dans les bases de connaissances ontologiques. Plus précisément, les règles découvertes sont codées en SWRL pour être facilement intégrées dans l'ontologie, enrichissant ainsi son pouvoir expressif et augmentant les connaissances sur les individus (assertions) qui en peuvent être dérivées. Deux algorithmes appliqués aux bases de connaissances ontologiques peuplées sont proposés pour trouver des règles à forte puissance inductive : (i) un algorithme de génération et test par niveaux et (ii) un algorithme évolutif. Nous avons effectué des expériences sur des ontologies accessibles au public, validant les performances de notre approche et les comparant avec les principaux systèmes de l'état de l'art. En outre, nous effectuons une comparaison des métriques asymétriques les plus répandues, proposées à l'origine pour la notation de règles d'association, comme éléments constitutifs d'une fonction de fitness pour l'algorithme évolutif afin de sélectionner les métriques qui conviennent à la sémantique des données. Afin d'améliorer les performances du système, nous avons proposé de construire un algorithme pour calculer les métriques au lieu d'interroger viaSPARQL-DL. / In the Semantic Web context, OWL ontologies represent explicit domain knowledge based on the conceptualization of domains of interest while the corresponding assertional knowledge is given by RDF data referring to them. In this thesis, based on ideas derived from ILP, we aim at discovering hidden knowledge patterns in the form of multi-relational association rules by exploiting the evidence coming from the assertional data of ontological knowledge bases. Specifically, discovered rules are coded in SWRL to be easily integrated within the ontology, thus enriching its expressive power and augmenting the assertional knowledge that can be derived. Two algorithms applied to populated ontological knowledge bases are proposed for finding rules with a high inductive power: (i) level-wise generated-and-test algorithm and (ii) evolutionary algorithm. We performed experiments on publicly available ontologies, validating the performances of our approach and comparing them with the main state-of-the-art systems. In addition, we carry out a comparison of popular asymmetric metrics, originally proposed for scoring association rules, as building blocks for a fitness function for evolutionary algorithm to select metrics that are suitable with data semantics. In order to improve the system performance, we proposed to build an algorithm to compute metrics instead of querying via SPARQL-DL.
42

Evolving‌ ‌artificial‌ ‌neural‌ ‌networks‌‌ ‌to‌ ‌imitate‌ ‌human‌ ‌behaviour‌‌ ‌in‌ ‌Shinobi‌ ‌III‌ ‌:‌ ‌return‌ ‌of‌ ‌the‌ ‌Ninja‌ ‌master‌

Le Cleï, Maximilien 08 1900 (has links)
Notre société est de plus en plus friande d’outils informatiques. Ce phénomène s’est particulièrement accru lors de cette dernière décennie suite, entre autres, à l’émergence d’un nouveau paradigme d’Intelligence Artificielle. Plus précisément, le couplage de deux techniques algorithmiques, les Réseaux de Neurones Profonds et la Descente de Gradient Stochastique, propulsé par une force de calcul exponentiellement croissante, est devenu et continue de devenir un atout majeur dans de nombreuses nouvelles technologies. Néanmoins, alors que le progrès suit son cours, certains se demandent toujours si d’autres méthodes pourraient similairement, voire davantage, bénéficier de ces diverses avancées matérielles. Afin de pousser cette étude, nous nous attelons dans ce mémoire aux Algorithmes Évolutionnaires et leur application aux Réseaux de Neurones Dynamiques, deux techniques dotées d’un grand nombre de propriétés avantageuses n’ayant toutefois pas trouvé leur place au sein de l’Intelligence Artificielle contemporaine. Nous trouvons qu’en élaborant de nouvelles méthodes tout en exploitant une forte puissance informatique, il nous devient alors possible de développer des agents à haute performance sur des bases de référence ainsi que d’autres agents se comportant de façon très similaire à des sujets humains sur le jeu vidéo Shinobi III : Return of The Ninja Master, cas typique de tâches complexes que seule l’optimisation par gradient était capable d’aborder jusqu’alors. / Our society is increasingly fond of computational tools. This phenomenon has greatly increased over the past decade following, among other factors, the emergence of a new Artificial Intelligence paradigm. Specifically, the coupling of two algorithmic techniques, Deep Neural Networks and Stochastic Gradient Descent, thrusted by an exponentially increasing computing capacity, has and is continuing to become a major asset in many modern technologies. However, as progress takes its course, some still wonder whether other methods could similarly or even more greatly benefit from these various hardware advances. In order to further this study, we delve in this thesis into Evolutionary Algorithms and their application to Dynamic Neural Networks, two techniques which despite enjoying many advantageous properties have yet to find their niche in contemporary Artificial Intelligence. We find that by elaborating new methods while exploiting strong computational resources, it becomes possible to develop strongly performing agents on a variety of benchmarks but also some other agents behaving very similarly to human subjects on the video game Shinobi III : Return of The Ninja Master, typical complex tasks previously out of reach for non-gradient-based optimization.
43

Optimisation évolutionnaire multi-objectif parallèle : application à la combustion Diesel / Multi-objective parallel evolutionary algorithms : Application to Diesel Combustion

Yagoubi, Mouadh 03 July 2012 (has links)
Avec la sévérisation des réglementations environnementales sur les émissions polluantes (normes Euro) des moteurs d'automobiles, la nécessité de maitriser les phénomènes de combustion a motivé le développement de la simulation numérique comme outil d'aide à la conception. Tenant compte de la complexité des phénomènes à modéliser, et de l'antagonisme des objectifs à optimiser, l'optimisation évolutionnaire multi-objectif semble être la mieux adaptée pour résoudre ce type de problèmes. Cependant, l'inconvénient principal de cette approche reste le coût très élevé en termes de nombre d'évaluations qui peut devenir très contraignant dans le contexte des optimisations réelles caractérisées par des évaluations très coûteuseL'objectif principal de ce travail de thèse est de réduire le coût global des optimisations du monde réel, en explorant la parallélisation des algorithmes évolutionnaires multi-objectifs, et en utilisant les techniques de réduction du nombre d'évaluations (méta-modèles).Motivés par le phénomène d'hétérogénéité des coûts des évaluations, nous nous proposons d'étudier les schémas d'évolution stationnaires asynchrones dans une configuration parallèle de type « maître-esclave ». Ces schémas permettent une utilisation plus efficace des processeurs sur la grille de calcul, et par conséquent de réduire le coût global de l'optimisation.Ce problème a été attaqué dans un premier temps d'un point de vue algorithmique, à travers une adaptation artificielle des algorithmes évolutionnaires multi-objectifs au contexte des optimisations réelles caractérisées par un coût d'évaluation hétérogène. Dans un deuxième temps, les approches développées et validées dans la première partie sur des problèmes analytiques, ont été appliquées sur la problématique de la combustion Diesel qui représente le contexte industriel de cette thèse. Dans ce cadre, deux types de modélisations ont été utilisés: la modélisation phénoménologique 0D et la modélisation multidimensionnelle 3D. La modélisation 0D a permis par son temps de retour raisonnable (quelques heures par évaluation) de comparer l'approche stationnaire asynchrone avec celle de l'état de l'art en réalisant deux optimisations distinctes. Un gain de l'ordre de 42 % a été réalisé avec l'approche stationnaire asynchrone. Compte tenu du temps de retour très coûteux de la modélisation complète 3D (quelques jours par évaluation), l'approche asynchrone stationnaire déjà validée a été directement appliquée. L'analyse physique des résultats a permis de dégager un concept intéressant de bol de combustion permettant de réaliser un gain en termes d'émissions polluantes. / In order to comply with environmental regulations, automotive manufacturers have to develop efficient engines with low fuel consumption and low emissions. Thus, development of engine combustion systems (chamber, injector, air loop) becomes a hard task since many parameters have to be defined in order to optimize many objectives in conflict. Evolutionary Multi-objective optimization algorithms (EMOAs) represent an efficient tool to explore the search space and find promising engine combustion systems. Unfortunately, the main drawback of Evolutionary Algorithms (EAs) in general, and EMOAs in particular, is their high cost in terms of number of function evaluations required to reach a satisfactory solution. And this drawback can become prohibitive for those real-world problems where the computation of the objectives is made through heavy numerical simulations that can take hours or even days to complete.The main objective of this work is to reduce the global cost of real-world optimization, using the parallelization of EMOAs and surrogate models.Motivated by the heterogeneity of the evaluation costs observed on real-world applications, we study asynchronous steady-state selection schemes in a master-slave parallel configuration. This approach allows an efficient use of the available processors on the grid computing system, and consequently reduces the global optimization cost.In the first part of this work, this problem has been studied in an algorithmical point of view, through an artificial adaptation of EMOAs to the context of real-world optimizations characterized by a heterogeneous evaluation cost.In the second part, the proposed approaches, already validated on analytical functions, have been applied on the Diesel combustion problem, which represents the industrial context of this thesis. Two modelling approaches have been used: phenomenological modelling (0D model) and multi-dimensional modelling (3D model).The 0D model allowed us, thanks to its reasonable evaluation cost (few hours per evaluation) to compare the asynchronous steady-state approach with the standard generational one by performing two distinct optimizations. A gain of 42 % was observed with the asynchronous steady-state approach.Given the very high evaluation cost of the full 3D model, the asynchronous steady-state approach already validated has been applied directly. The physical analysis of results allowed us to identify an interesting concept of combustion bowl with a gain in terms of pollutant emissions.
44

Surrogate-Assisted Evolutionary Algorithms / Les algorithmes évolutionnaires à la base de méta-modèles scalaires

Loshchilov, Ilya 08 January 2013 (has links)
Les Algorithmes Évolutionnaires (AEs) ont été très étudiés en raison de leur capacité à résoudre des problèmes d'optimisation complexes en utilisant des opérateurs de variation adaptés à des problèmes spécifiques. Une recherche dirigée par une population de solutions offre une bonne robustesse par rapport à un bruit modéré et la multi-modalité de la fonction optimisée, contrairement à d'autres méthodes d'optimisation classiques telles que les méthodes de quasi-Newton. La principale limitation de AEs, le grand nombre d'évaluations de la fonction objectif,pénalise toutefois l'usage des AEs pour l'optimisation de fonctions chères en temps calcul.La présente thèse se concentre sur un algorithme évolutionnaire, Covariance Matrix Adaptation Evolution Strategy (CMA-ES), connu comme un algorithme puissant pour l'optimisation continue boîte noire. Nous présentons l'état de l'art des algorithmes, dérivés de CMA-ES, pour résoudre les problèmes d'optimisation mono- et multi-objectifs dans le scénario boîte noire.Une première contribution, visant l'optimisation de fonctions coûteuses, concerne l'approximation scalaire de la fonction objectif. Le meta-modèle appris respecte l'ordre des solutions (induit par la valeur de la fonction objectif pour ces solutions); il est ainsi invariant par transformation monotone de la fonction objectif. L'algorithme ainsi défini, saACM-ES, intègre étroitement l'optimisation réalisée par CMA-ES et l'apprentissage statistique de meta-modèles adaptatifs; en particulier les meta-modèles reposent sur la matrice de covariance adaptée par CMA-ES. saACM-ES préserve ainsi les deux propriété clé d'invariance de CMA-ES: invariance i) par rapport aux transformations monotones de la fonction objectif; et ii) par rapport aux transformations orthogonales de l'espace de recherche.L'approche est étendue au cadre de l'optimisation multi-objectifs, en proposant deux types de meta-modèles (scalaires). La première repose sur la caractérisation du front de Pareto courant (utilisant une variante mixte de One Class Support Vector Machone (SVM) pour les points dominés et de Regression SVM pour les points non-dominés). La seconde repose sur l'apprentissage d'ordre des solutions (rang de Pareto) des solutions. Ces deux approches sont intégrées à CMA-ES pour l'optimisation multi-objectif (MO-CMA-ES) et nous discutons quelques aspects de l'exploitation de meta-modèles dans le contexte de l'optimisation multi-objectif.Une seconde contribution concerne la conception d'algorithmes nouveaux pour l'optimi\-sation mono-objectif, multi-objectifs et multi-modale, développés pour comprendre, explorer et élargir les frontières du domaine des algorithmes évolutionnaires et CMA-ES en particulier. Spécifiquement, l'adaptation du système de coordonnées proposée par CMA-ES est coupléeà une méthode adaptative de descente coordonnée par coordonnée. Une stratégie adaptative de redémarrage de CMA-ES est proposée pour l'optimisation multi-modale. Enfin, des stratégies de sélection adaptées aux cas de l'optimisation multi-objectifs et remédiant aux difficultés rencontrées par MO-CMA-ES sont proposées. / Evolutionary Algorithms (EAs) have received a lot of attention regarding their potential to solve complex optimization problems using problem-specific variation operators. A search directed by a population of candidate solutions is quite robust with respect to a moderate noise and multi-modality of the optimized function, in contrast to some classical optimization methods such as quasi-Newton methods. The main limitation of EAs, the large number of function evaluations required, prevents from using EAs on computationally expensive problems, where one evaluation takes much longer than 1 second.The present thesis focuses on an evolutionary algorithm, Covariance Matrix Adaptation Evolution Strategy (CMA-ES), which has become a standard powerful tool for continuous black-box optimization. We present several state-of-the-art algorithms, derived from CMA-ES, for solving single- and multi-objective black-box optimization problems.First, in order to deal with expensive optimization, we propose to use comparison-based surrogate (approximation) models of the optimized function, which do not exploit function values of candidate solutions, but only their quality-based ranking.The resulting self-adaptive surrogate-assisted CMA-ES represents a tight coupling of statistical machine learning and CMA-ES, where a surrogate model is build, taking advantage of the function topology given by the covariance matrix adapted by CMA-ES. This allows to preserve two key invariance properties of CMA-ES: invariance with respect to i). monotonous transformation of the function, and ii). orthogonal transformation of the search space. For multi-objective optimization we propose two mono-surrogate approaches: i). a mixed variant of One Class Support Vector Machine (SVM) for dominated points and Regression SVM for non-dominated points; ii). Ranking SVM for preference learning of candidate solutions in the multi-objective space. We further integrate these two approaches into multi-objective CMA-ES (MO-CMA-ES) and discuss aspects of surrogate-model exploitation.Second, we introduce and discuss various algorithms, developed to understand, explore and expand frontiers of the Evolutionary Computation domain, and CMA-ES in particular. We introduce linear time Adaptive Coordinate Descent method for non-linear optimization, which inherits a CMA-like procedure of adaptation of an appropriate coordinate system without losing the initial simplicity of Coordinate Descent.For multi-modal optimization we propose to adaptively select the most suitable regime of restarts of CMA-ES and introduce corresponding alternative restart strategies.For multi-objective optimization we analyze case studies, where original parent selection procedures of MO-CMA-ES are inefficient, and introduce reward-based parent selection strategies, focused on a comparative success of generated solutions.
45

Optimisation of the weapon target assignment problem foir naval and ground command and control systems / Optimisation du problème d'allocation d'armes à des cibles pour les systèmes de commandes et contrôles terrestres et navals

Leboucher, Cédric 21 October 2014 (has links)
Ces travaux de recherche abordent un problème de défense anti-aérien, usuellement appelé problème d'allocation d'armes à des cibles dans la littérature. L'allocation d'armes à des cibles est un problème bien connu de la recherche opérationnelle militaire qui a rencontré un franc succès parmi la communauté des chercheurs, et qui aujourd'hui encore suscite un large engouement puisque sa propriété démontrée NP-difficile en fait un problème qui reste irrésolu. Que ce soit par des méthodes analytiques ou meta-heuristiques, le problème d'allocation d'armes à des cibles a fait l'objet de nombreuses propositions de résolution. Cependant, il est assez surprenant de voir que la modélisation proposée pour ce problème n'a guère évolué depuis qu'il est apparu pour la première fois dans la littérature en 1950. Cette modélisation peut être considérée comme obsolète aujourd'hui et ne répond plus aux exigences qui accompagnent les technologies modernes. En effet, en 60 ans le champ de bataille a complètement changé, et dans la littérature seulement un nombre limité d'études proposent de prendre en compte ces évolutions. L'étude menée dans cette thèse propose de s'intéresser aux systèmes de Commandes et Contrôles (C2) pour des applications anti-aériennes. Habituellement un système C2 est composé de senseurs, d'un centre d'opérations tactiques et d'un ou plusieurs lanceurs. Les senseurs alimentent le centre d'opérations tactiques à partir des informations qu'ils recueillent, puis, une fois ces informations reçues, le centre d'opérations tactiques va interpréter ces données afin de calculer l'atteignabilité des menaces. Enfin, un plan d'engagement qui comprend l'allocation des munitions disponibles aux cibles et une date de tir sont proposés à un opérateur humain qui aura pour mission de valider cette proposition en totalité ou partiellement, puis va procéder à l'engagement des menaces. Pour remplir cet objectif, une approche innovante et faisant l'objet d'un dépôt de brevet a été développée afin de répondre aux difficultés relatives aux problèmes d'optimisation multi-objectifs. Ensuite, un algorithme d'optimisation continue basé sur la combinaison de l'optimisation par essaim particulaires avec la théorie des jeux évolutionnaires est proposé pour optimiser les dates de tirs. L'allocation optimale, elle, est obtenue en adaptant cette méthode continue au cas discret. La preuve que l'algorithme développé est localement convergent est donnée dans cette thèse. D'autre part, l'aspect temps-réel a également fait l'objet d'une recherche attentive et l'algorithme précédemment cité a été hybridé avec les réseaux de neurones afin d'accélérer le temps de calcul des composants identifiés comme "lourds" en termes de charge de calcul. Enfin, cette étude ne se limite pas à une application de recherche opérationnelle militaire, mais inclut quelques concepts élémentaires de guidage et de navigation pour le calcul d'atteignabilité des menaces. Finalement, cette thèse permet d'identifier que les points suivants doivent faire l'objet d'une attention très particulière afin de développer un outil d'aide à la décision efficace. D'abord, la métrique d'évaluation d'un bon plan d'engagement doit être clairement analysée. Ensuite, le plan d'engagement proposé doit être stable et ne pas proposer de changements soudains qui pourraient perturber l'opérateur. Le troisième point concerne la robustesse de la solution proposée et sa capacité à faire face aux situations les plus compliquées. Quatrièmement, le temps et la charge de calcul sont des contraintes techniques qui ne peuvent pas être outrepassées. Finalement, les exigences posées lors de la préparation de mission et qui dépendent du contexte doivent faire l'objet d'une attention particulière. C'est pourquoi, l'outil d'aide à la décision proposé doit permettre un allègement significatif de la charge de travail de l'opérateur ainsi que la réduction considérable du stress lié à ce contexte / This research investigates a practical air defence problem, usually named Weapon Target Assignment (WTA) in the literature. The WTA problem is a well-known problem of military operation research that encountered a wide success in the research community, but still nowadays since it remains an unsolved problem because of its NP-hardness property. From analytical to heuristic methods, the WTA was deeply investigated and many attempts to solve this problem have been proposed. However, the proposed modelling of this problem is consistent with the 1950's technologies. Thus, the proposed modelling found in the literature can be considered as obsolete and cannot fit the requirement of the current technology advances. Indeed, the battle field dramatically changes over 60 years, and the recent literature proposes only few studies taking into account these amendments. The herein study proposes to investigate a Command & Control system (C2) in air defence applications. Usually a C2 system includes sensors, a Tactical Operation Centre (TOC) and one or more launchers. The sensors provide information about aerial tactical situation to the TOC. This TOC is in charge of evaluating the received information in order to compute the attainability of the targets, then an engagement plan that includes the assignment of the available weapons to the incoming targets and a date to fire for each assignment. This engagement plan is then proposed to one human operator in charge of accepting whole or part of this engagement plan and engage the targets following the received instructions. To achieve this goal, an innovative and patented approach to mitigate the issues related to multi-objective optimisation is proposed. Then, a continuous optimisation algorithm based on the combination of the Particle Swarm Optimisation and the Evolutionary Game Theory was proposed to determine the best dates to fire. The optimal assignment was obtained by adapting the aforementioned algorithm to the discrete case. This thesis also gives the proof that the designed algorithms are locally convergent and intensive benchmarking confirms the developed theory. In order to respect the real-time requirement, it was also devised to use the Neural Networks to lighten the identified burdensome parts of the algorithm and decrease computational time. Not limited to the military operation research field, the herein study reuse some basic concepts of missile guidance and navigation to compute the attainability of the targets. From this thesis, it can be identified that following aspects need to be carefully considered to provide an efficient decision making support to a human operator: First, clearly define what a good engagement plan is. Second, the engagement plan must be steady to avoid high rate changing in the assignments that could significantly disturb the operator. Third, the proposed engagement also must be reliable and robust to face any possible situations. Fourth, the computation time and computation load are technical constraints that cannot be overstepped. Finally, the operational constraints related to the mission context defined during a pre-mission stage must also be taken into account. Therefore, the proposed decision making support must help and significantly reduce the operator's work load in this situation of high stress and sensitive context
46

Système collaboratif d'aide à l'ordonnancement et à l'orchestration des tâches de soins à compétences muiltiples / Collaborative support system for multi-skill health care tasks scheduling and orchestration

Ben Othman, Sara 14 December 2015 (has links)
Dans la gestion des systèmes de soins, la maîtrise des flux hospitaliers et l’anticipation des tensions sont des enjeux majeurs. Le but de cette thèse est de contribuer à l’étude et au développement d’un Système Collaboratif d’Aide à l’Ordonnancement et à l’Orchestration (SysCAOO) des tâches de soins à compétences multiples pour gérer les tensions dans les Services d’Urgences Pédiatriques (SUP) afin d’améliorer la qualité de prise en charge des patients. Le SysCAOO intègre une approche Workflow collaboratif pour modéliser le parcours patient afin d’identifier les dysfonctionnements et les pics d’activités du personnel médical dans le SUP. L’aspect dynamique et incertain du problème nous a conduits à adopter une alliance entre les Systèmes Multi-Agent (SMA) et les Algorithmes Evolutionnaires (AE) pour le traitement et l’ordonnancement des tâches de soins en tenant compte du niveau d’expérience des acteurs du SUP et leurs disponibilités. En cas d’aléas dans le SUP, une coalition d’agents se forme pour collaborer et négocier afin de proposer des décisions d’orchestration du Workflow et minimiser le temps d’attente des patients en cours de leur prise en charge. Les résultats expérimentaux présentés dans cette thèse justifient l’intérêt de l’alliance entre les SMA et les Métaheuristiques afin de gérer les tensions dans le SUP. Les travaux de recherche présentés dans cette thèse s’intègrent dans le cadre du projet HOST (Hôpital : Optimisation, Simulation et évitement des tensions) (http://www.agence-nationale-recherche.fr/?Projet=ANR-11-TECS-0010). / Health care systems management and the avoidance of overcrowding phenomena are major issues. The aim of this thesis is to implement a Collaborative Support System for Scheduling and Orchestration (CSSystSO) of multi-skill health care tasks in order to avoid areas bottlenecks in the Pediatric Emergency Department (PED) and improve health care quality for patients. The CSSystSO integrates a collaborative Workflow approach to model patient journey in order to identify dysfunctions and peaks of activities of medical staff in the PED. The dynamic and uncertain aspect of the problem has led us to adopt an alliance between Multi-Agent Systems (MAS) and Evolutionary Algorithms (EA) for health care tasks treatment and scheduling taking into account the level of experience of the PED actors and their availabilities. In case of perturbations in the PED, a coalition of agents is formed to collaborate and negotiate in order to provide orchestration Workflow decisions to minimize the waiting time of patients during their treatment. The experimental results presented in this thesis justify the interest of the alliance between MAS and Metaheuristics to manage overcrowding phenomena in the PED. This work belongs to the project HOST (Hôpital: Optimisation, Simulation et évitement des tensions). (http://www.agence-nationale-recherche.fr/?Projet=ANR-11-TECS-0010).
47

Jeux évolutionnaires avec des interactions non uniformes et délais / Evolutionary Games with non-uniform interactions and delays

Ben Khalifa, Nesrine 16 December 2016 (has links)
La théorie des jeux évolutionnaires est un outil qui permet d’étudier l’évolution des stratégies dans une population composée d’un grand nombre d’agents qui interagissent d’une façon continue et aléatoire. Dans cette théorie, il y a deux concepts essentiels qui sont la stratégie évolutivement stable (ESS), et la dynamique de réplication. Une stratégie évolutivement stable est une stratégie, qui, si adoptée par toute la population,ne peut pas être envahie par une autre stratégie ”mutante” utilisée par une petite fraction de la population. Ce concept statique est un raffinement de l’équilibre de Nash, et il ne peut pas renseigner, par exemple, sur la durée du temps nécessaire pour que l’ESS élimine la stratégie mutante. La dynamique de réplication, originalement proposée par Hawk-Dove, est un modèle dynamique qui permet de prédire l’évolution de la fraction de chaque stratégie dans la population en fonction du temps, en réponse aux gains des stratégies et l’état de la population.Dans cette thèse, nous proposons dans une première partie une extension de la dynamique de réplication classique en y introduisant des délais hétérogènes et aléatoires.En effet, la plupart des phénomènes qui se produisent prennent un temps incertain avant d’avoir des résultats. Nous étudions l’effet de la distribution des délais sur la stabilité de l’ESS dans la dynamique de réplication et nous considérons les distributions uniforme, exponentielle, et Gamma (ou Erlang). Dans les cas des distributions uniforme et Gamma, nous trouvons la valeur critique de la moyenne à laquelle la stabilité de l’équilibre est perdue et des oscillations permanentes apparaissent. Dans le cas de la distribution exponentielle, nous montrons que la stabilité de l’équilibre ne peut être perdue,et ce pour toute valeur de la moyenne de la distribution. Par ailleurs, nous montrons que la distribution exponentielle peut affecter la stabilité de l’ESS quand une seule stratégie subit un délai aléatoire issu de cette distribution. Nous étudions également le cas où les délais sont discrets et nous trouvons une condition suffisante et indépendante des valeurs des délais pour la stabilité de l’équilibre. Dans tous les cas, nous montrons que les délais aléatoires sont moins risqués que les délais constants pour la stabilité de l’équilibre, vu que la valeur moyenne critique des délais aléatoires est toujours supérieure de celle des délais constants. En outre, nous considérons comme paramètre de bifurcation la moyenne de la distribution des délais et nous étudions les propriétés de la solution périodique qui apparait à la bifurcation de Hopf, et ce en utilisant une méthode de perturbation non linéaire. En effet, à la bifurcation de Hopf, une oscillation périodique stable apparait dont l’amplitude est fonction de la moyenne de la distribution. Nous déterminons analytiquement l’amplitude de l’oscillation au voisinage de la bifurcation de Hopf en fonction du paramètre de bifurcation et de la matrice des jeux dans les cas des distributions de Dirac, uniforme, Gamma et discrète, et nous appuyons nos résultats avec des simulations numériques. Dans une deuxième partie, nous considérons une population hétérogène composée de plusieurs communautés qui interagissent d’une manière non-uniforme. Pour chaque communauté, nous définissons les matrices des jeux et les probabilités d’interaction avec les autres communautés. Dans ce contexte, nous définissons trois ESS avec différents niveaux de stabilité contre les mutations: un ESS fort, un ESS faible et un ESS intermédiaire. Nous définissons un ESS fort comme suit: si toute la population adopte l’ESS, alors l’ESS ne peut pas être envahi par une petite fraction de mutants composée d’agents de toutes les communautés. / In this dissertation, we study evolutionary game theory which is a mathematical tool used to model and predict the evolution of strategies in a population composed of a largenumber of players. In this theory, there are two basic concepts which are the evolutionarilystable strategy (ESS) and the replicator dynamics. The ESS is originally definedas follows [1]: if all the population adopts the ESS, then no alternative strategy used bya sufficiently small fraction of the population can invade the population.The ESS is astatic concept and a refinement of a Nash equilibrium. It does not allow us, for example,to estimate the time required for the ESS to overcome the mutant strategy, neither to predictthe asymptotic distribution of strategies in the population. The replicator dynamics,originally introduced in [2], is a model of evolution of strategies according to which the growth rate of a given strategy is proportional to how well this strategy performs relative to the average pay off in the population.In the first part of this work, we propose an extended version of the replicator dynamics which takes into account heterogeneous random delays. Indeed, in many situations,the presence of uncertain delays is ubiquitous. We first consider continuous delays and we study the effect of the distribution of delays on the asymptotic stability of the mixed equilibrium in the replicator dynamics. In the case of uniform and Gamma delay distributions,we find the critical mean delay at which a Hopf bifurcation is created and the stability of the mixed equilibrium is lost. When the distribution of delays is exponential, we prove that the stability of the equilibrium cannot be affected by the delays. However, when only one strategy is delayed according to the exponential distribution,the asymptotic stability of the ESS can be lost. In all the cases, we show that the critical mean delay value is higher than that of constant delays, and thus random delays are less threatening than constant delays. In addition, we consider discrete delays and one o four results is that, when the instantaneous term is dominant, that is when the probabilityof zero delay is sufficiently high, the stability of the ESS cannot be lost.Furthermore, by taking as a bifurcation parameter the mean delay distribution, we examine the properties of the bifurcating periodic solution created near the Hopf bifurcationusing a nonlinear perturbation method. Indeed, near the Hopf bifurcation, a stable periodic oscillation appears whose amplitude depends on the value of the bifurcation parameter. We give a closed-form expression of the amplitude of the periodic solution and we validate our results with numerical simulations.In the second part, we consider an heterogeneous population composed of several communities which interact in a nonuniform manner. Each community has its own set of strategies, payoffs, and interaction probabilities. Indeed, individuals of a population have many inherent differences that favor the appearance of groups or clusters. In this scenario, we define three ESS with different levels of stability against mutations: strong,weak, and intermediate ESS, and we examine their connection to each other. A strongESS is a strategy that, when adopted by all the population, cannot be invaded by a sufficientlysmall fraction of mutants composed of agents from all the communities. Incontrast, a weak ESS is a strategy wherein each community resists invasion by a sufficientlysmall fraction of mutants in that community (local mutants). In the intermediateESS, the population adopting the ESS cannot be invaded by a small fraction of mutantswhen we consider the total fitness of the population rather than the fitness of eachcommunity separately.
48

Approche computationnelle de l'orchestration musciale - Optimisation multicritère sous contraintes de combinaisons instrumentales dans de grandes banques de sons

Carpentier, Grégoire 16 December 2008 (has links) (PDF)
De toutes les composantes de l'écriture musicale, l'orchestration - ou l'art d'assembler les timbres instrumentaux - est longtemps demeurée, dans son enseignement comme dans sa pratique, une activité empirique. La difficulté de formaliser de manière rigoureuse l'ensemble des techniques inhérentes à cette discipline fait qu'aujourd'hui encore, l'orchestration reste un domaine peu abordé par l'informatique musicale et l'aide à la composition.<br /><br />Les rares outils actuels ramènent le problème de l'orchestration à la découverte, au sein de banques d'échantillons sonores instrumentaux, de combinaisons approchant au mieux un timbre fixé par le compositeur. Cette approche sera également la nôtre. Mais là où les méthodes actuelles contournent systématiquement le problème combinatoire de l'orchestration par le recours à des principes de décomposition ou à des algorithmes de matching pursuit, l'originalité de notre démarche est de placer les enjeux combinatoires au coeur de nos travaux et de traiter l'orchestration à la mesure de sa complexité.<br /><br />Envisageant tout d'abord la question comme un problème de sac à dos multi-objectifs, nous montrons que les non-linéarités dans les modèles de perception du timbre imposent un cadre théorique plus large pour l'aide à l'orchestration. Nous proposons une formalisation générique et extensible en nous plaçant dans un cadre de recherche combinatoire multicritère sous contraintes, dans lequel plusieurs dimensions perceptives sont optimisées conjointement pour approcher un timbre cible défini par le compositeur.<br />Nous validons dans un premier temps notre approche théorique en montrant, sur un ensemble de problèmes de petite taille et pour une caractérisation exclusivement spectrale du timbre, que les solutions du problème formel correspondent à des propositions d'orchestration pertinentes. Nous présentons alors un algorithme évolutionnaire permettant de découvrir en un temps raisonnable un ensemble de solutions optimales. S'appuyant sur la prédiction des propriétés acoustiques des alliages instrumentaux, cette méthode propose des solutions d'orchestration en fonction de critères perceptifs et encourage ainsi la découverte de mélanges de timbres auxquels le savoir et l'expérience n'auraient pas nécessairement conduit.<br />En outre, la recherche peut-être à tout moment orientée dans une direction privilégiée. Parallèlement, nous définissons un cadre formel pour l'expression de contraintes globales et introduisons une métaheuristique innovante de résolution, permettant de guider la recherche vers des orchestrations satisfaisant un ensemble de propriétés symboliques en lien direct avec l'écriture musicale.<br /><br />Nous présentons enfin un prototype expérimental d'outil d'aide à l'orchestration utilisable directement par les compositeurs, dans lequel l'exploration des possibilités de timbres est facilitée à travers une représentation multi-points de vue des solutions et un mécanisme interactif des préférences d'écoute. Nous terminons avec une série d'exemples d'application de nos travaux à des problèmes compositionnels concrets.
49

Étude théorique et approximation numérique d'un problème inverse de transfert de la chaleur

Nachaoui, Mourad 01 December 2011 (has links) (PDF)
Nous nous intéressons à l'étude d'un problème d'analyse des transferts de chaleur qui modélise une opération de soudage. L'approche que nous considérons ne s'occupe que de la partie solide de la plaque. Elle consiste à résoudre un problème à frontière libre. Pour cela, nous proposons une formulation en optimisation de forme. Le problème d'état est gouverné par un opérateur qui, pour certaines données, n'est pas coercif. Cela complique l'étude de la continuité du problème d'état. Nous surmontons cette difficulté en utilisant le degré topologique de Leray-Shauder, ainsi nous montrons l'existence d'un domaine optimal. Ensuite, nous considérons une discrétisation de ce problème basée sur les éléments finis linéaires. Nous prouvons alors que le problème discret admet une solution et nous montrons qu'une sous-suite des solutions de ce problème convergence vers la solution du problème continu. Enfin, nous présentons des résultats numériques réalisés par deux méthodes : la méthode déterministe basée sur le calcul du gradient de forme, et les algorithmes génétiques combinés avec la logique floue et le calcul parallèle. Ainsi une étude comparative de ces deux méthodes aux niveaux qualitatif et quantitatif a été présentée.
50

Hybridation de métaheuristiques pour la résolution distribuée de problèmes d'optimisation spatialisés

Creput, Jean-Charles 21 November 2008 (has links) (PDF)
Les problèmes d'optimisation spatialisés font intervenir des entités (clients, demandes, trafic) réparties sur une étendue (la donnée) et des dispositifs physiques (antennes, véhicules) qui doivent leur être associés de manière optimale. Il en résulte de nombreux problèmes d'optimisation combinatoire difficile à résoudre (NP-hard). Pour résoudre ce type de problème, nous proposons des algorithmes à structure intermédiaire, des recherches locales et des approches de résolution collective selon des métaphores de systèmes naturels et biologiques. Le but est par exemple de prendre en compte dès le départ la potentialité d'application à des problèmes dynamiques, de fournir un canevas à la mise en œuvre distribuée possible des algorithmes, et de résoudre des problèmes de grandes tailles.

Page generated in 0.121 seconds