• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 48
  • 11
  • 6
  • Tagged with
  • 65
  • 65
  • 24
  • 23
  • 21
  • 20
  • 18
  • 16
  • 16
  • 15
  • 13
  • 11
  • 9
  • 9
  • 9
  • 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.
1

Étude des algorithmes de recuit simulé, de recherche tabou et génétique implémentés dans un système de construction d'horaires de cours universitaires

Abid, Mohamed Amine January 2008 (has links)
Dans ce travail on s'intéresse à la conception et au développement d'un système d'aide à la confection d'horaires. Le banc d'essai"Benchmark" utilisé est le problème d'horaires de cours dans une université basé sur l'inscription des étudiants aux cours"Post Enrolment based Course Timetabling", proposé en deuxième volet lors de la compétition internationale d'horaires en 2007"International Timetabling Competition". Le système d'aide à la confection d'horaires applique une approche heuristique basée sur la recherche locale stochastique. L'originalité du système consiste à implémenter les algorithmes de recuit simulé, recherche tabou et génétique, qui s'exécutent sur les mêmes énoncés des problèmes proposés par l'ITC et qui se partagent les mêmes structures de données et la majorité des modules de recherche locale. Ensuite une étude qualitative et quantitative de performance à produire des horaires de qualité comparable à ceux réalisés lors de la compétition est effectuée pour chaque algorithme implémenté.
2

Etude d'un problème d'optimisation en aéroélasticité avec incertitudes / Optimization of an aeroelastic system with uncertainties

Arnaud, Rémi 10 April 2014 (has links)
La recherche en optimisation est un secteur crucial pour les constructeurs aéronautiques. La performance des appareils est un élément déterminant dans la compétition commerciale qui oppose les principaux manufacturiers du marché. L'incorporation de plus en plus massive des matériaux composites dans les avions de ligne dans les années 2000 illustre le désir des constructeurs de réduire la masse de leurs appareils pour en diminuer la consommation de kérosène. Parallèlement, la sécurité est devenue au fil des années une préoccupation majeure pour l'ensemble des acteurs. Cependant, l'emploi massif de matériaux composites, dont les propriétés physiques sont très intéressantes pour les constructeurs mais qui sont conçus avec une marge de tolérance pour des raisons de coût, induit des variations indésirables dans la structure, des incertitudes. Outre ces matériaux, d'autres éléments non prévisibles sont susceptibles de perturber la structure de l'appareil. Le modèle d'un avion en avant-projet est toujours amené à évoluer pour répondre aux évolutions des exigences du constructeur, mais des études de faisabilité doivent être menées avant que la structure ne soit totalement définie, afin de s'assurer de la viabilité du modèle. Des éléments non pris en compte dans la structure, comme les câbles, peuvent également avoir une influence non négligeable sur le comportement global de l'appareil. Ces incertitudes ont un impact non négligeable sur la stabilité de la structure en vol. Des études ont commencé à incorporer cet aspect incertain dans les processus d'optimisation, mais généralement en adaptant les algorithmes existants et sans exploiter la nature incertaine des problèmes. Afin de tenir compte de l'aspect incertain, on se propose de représenter ces incertitudes par des variables aléatoires et d'exploiter des outils théoriques développés dans d'autres domaines, notamment les outils des mathématiques financières. / Research in optimization is a fundamental field for aircraft manufacturers. The performance of airplanes is a crucial element in the commercial competition that pit main aircraft manufacturers against each other. Since 2000, composite materials have been more and more used in aircraft design. This shows the manufacturers' desire to reduce the airplane weight to diminish kerosene consumption. At the same time, safety has become a major concern for all the parties involved. But the use of composite materials, which are designed with a margin of tolerance on the physical properties to cut cost, causes unwanted variations in the structure. Other factors in the airplane design could also disrupt the overall structure of the final product. An airplane model is intended to be modified according to the manufacturer's wishes and their evolution, but feasibility studies must be carried out before the structural design is complete, in order to make sure that the model is viable. Elements which are not modeled in the structure, e.g. cables, can affect the overall behavior of the airplane. These uncertainties have a non-negligible influence on the stability of the structure during flights. Some studies have started to take into account these uncertainties in the optimization process, but they usually consist in adapting existing deterministic algorithms, without regard for the inherent uncertainty of the problem. In order to take uncertainty into account, we propose to represent these uncertainties by random variables and to use theoretical tools that are used in other domains, such as financial mathematics.
3

Techniques d'optimisation déterministe et stochastique pour la résolution de problèmes difficiles en cryptologie

Bouallagui, Sarra 05 July 2010 (has links) (PDF)
Cette thèse s'articule autour des fonctions booléennes liées à la cryptographie et la cryptanalyse de certains schémas d'identification. Les fonctions booléennes possèdent des propriétés algébriques fréquemment utilisées en cryptographie pour constituer des S-Boxes (tables de substitution).Nous nous intéressons, en particulier, à la construction de deux types de fonctions : les fonctions courbes et les fonctions équilibrées de haut degré de non-linéarité.Concernant la cryptanalyse, nous nous focalisons sur les techniques d'identification basées sur les problèmes de perceptron et de perceptron permuté. Nous réalisons une nouvelle attaque sur le schéma afin de décider de sa faisabilité.Nous développons ici des nouvelles méthodes combinant l'approche déterministe DCA (Difference of Convex functions Algorithm) et heuristique (recuit simulé, entropie croisée, algorithmes génétiques...). Cette approche hybride, utilisée dans toute cette thèse, est motivée par les résultats intéressants de la programmation DC.
4

Advanced methods to solve the maximum parsimony problem / Méthodes avancées pour la résolution du problème de maximum parcimonie

Vazquez ortiz, Karla Esmeralda 14 June 2016 (has links)
La reconstruction phylogénétique est considérée comme un élément central de divers domaines comme l’écologie, la biologie et la physiologie moléculaire pour lesquels les relations généalogiques entre séquences d’espèces ou de gènes, représentées sous forme d’arbres, peuvent apporter des éclairages significatifs à la compréhension de phénomènes biologiques. Le problème de Maximum de Parcimonie est une approche importante pour résoudre la reconstruction phylogénétique en se basant sur un critère d’optimalité pour lequel l’arbre comprenant le moins de mutations est préféré. Dans cette thèse nous proposons différentes méthodes pour s’attaquer à la nature combinatoire de ce problème NP-complet. Premièrement, nous présentons un algorithme de Recuit Simulé compétitif qui nous a permis de trouver des solutions de meilleure qualité pour un ensemble de problèmes. Deuxièmement, nous proposons une nouvelle technique de Path-Relinking qui semble intéressante pour comparer des arbres mais pas pour trouver des solutions de meilleure qualité. Troisièmement, nous donnons le code d’une implantation sur GPU de la fonction objectif dont l’intérêt est de réduire le temps d’exécution de la recherche pour des instances dont la longueur des séquences est importante. Finalement, nous introduisons un prédicteur capable d’estimer le score optimum pour un vaste ensemble d’instances avec une très grande précision. / Phylogenetic reconstruction is considered a central underpinning of diverse fields like ecology, molecular biology and physiology where genealogical relationships of species or gene sequences represented as trees can provide the most meaningful insights into biology. Maximum Parsimony (MP) is an important approach to solve the phylogenetic reconstruction based on an optimality criterion under which the tree that minimizes the total number of genetic transformations is preferred. In this thesis we propose different methods to cope with the combinatorial nature of this NP-complete problem. First we present a competitive Simulated Annealing algorithm which helped us find trees of better parsimony score than the ones that were known for a set of instances. Second, we propose a Path-Relinking technique that appears to be suitable for tree comparison but not for finding trees of better quality. Third, we give a GPU implementation of the objective function of the problem that can reduce the runtime for instances that have an important number of residues per taxon. Finally, we introduce a predictor that is able to estimate the best parsimony score of a huge set of instances with a high accuracy.
5

Méthodes heuristiques pour un problème d'ordonnancement avec contraintes sur les ressources

Bouffard, Véronique January 2003 (has links)
Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.
6

Amélioration de la prédiction de la qualité du logiciel par combinaison et adaptation de modèles

Bouktif, Salah January 2005 (has links)
Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.
7

Optimisation globale sous incertitude : algorithmes stochastiques et bandits continus avec application aux performances avion / Stochastic global optimization : stochastic algorithms and continuous bandits with application to aircraft performance

Bouttier, Clément 29 June 2017 (has links)
Cette thèse est consacrée à l'étude théorique et numérique d'algorithmes d'optimisation stochastiques adaptés au traitement du problème de planification des trajectoires d'avions en environnement incertain. L'optimisation des temps de vol et de la consommation de carburant est un élément central de la compétitivité des compagnies aériennes. Elles sont à la recherche d'outils permettant d'optimiser le choix de leurs routes aériennes avec toujours plus de précision. Pourtant, les méthodes actuellement disponibles pour l'optimisation de ces routes aériennes requièrent l'utilisation de représentations simplifiées des performances avion. Nous proposons, dans cette thèse, de répondre à cette exigence de précision et d'adapter, par conséquent, nos méthodes de résolution aux contraintes de la modélisation industrielle des performances avion tout en tenant compte de l'incertitude qui pèse sur les conditions réelles de vol (trafic aérien et conditions atmosphériques). Nous appuyons notre démarche par trois contributions scientifiques. Premièrement, nous avons mis en place un environnement de test pour algorithmes d'optimisation de trajectoires. Ce cadre a permis d'unifier la procédure de test pour l'ensemble des modèles de performances avion. Deuxièmement, nous avons développé et analysé sur le plan théorique deux nouveaux algorithmes d'optimisation stochastique globale en l'absence de dérivés. La première approche, très générique, n'utilise pas d'information particulière liée à la dynamique avion. Il s'agit de l'algorithme NSA basé sur la méthode du recuit simulé. Les développements théoriques ont abouti à la formulation des conditions et vitesse de convergence de cet algorithme. La seconde approche, l'algorithme SPY, est plus spécifique, il utilise une information de régularité lipschitzienne autour de l'optimum recherche. Il s'agit d'un algorithme de type bandits Lipschitz, basé sur la méthode de Piyavskii. De même, nous analysons les conditions de convergence de cet algorithme et fournissons une borne supérieure sur son erreur d'optimisation (regret simple). / This PhD thesis is dedicated to the theoretical and numerical analysis of stochastic algorithms for the stochastic flight planning problem. Optimizing the fuel consumption and flight time is a key factor for airlines to be competitive. These companies thus look for flight optimization tools with higher and higher accuracy requirements. However, nowadays available methodologies for flight planning are based on simplified aircraft performance models. In this PhD, we propose to fulfill the accuracy requirements by adapting our methodology to both the constraints induced by the utilization of an industrial aircraft performance computation code and the consideration of the uncertainty about the real flight conditions, i.e., air traffic and weather conditions. Our proposal is supported by three main contributions. First, we design a numerical framework for benchmarking aircraft trajectory optimization tools. This provides us a unified testing procedure for all aircraft performance models. Second, we propose and study (both theoretically and numerically) two global derivative-free algorithms for stochastic optimization problems. The first approach, the NSA algorithm, is highly generic and does not use any prior knowledge about the aircraft performance model. It is an extension of the simulated annealing algorithm adapted to noisy cost functions. We provide an upper bound on the convergence speed of NSA to globally optimal solutions. The second approach, the SPY algorithm, is a Lipschitz bandit algorithm derived from Piyavskii's algorithm. It is more specific as it requires the knowledge of some Lipschitz regularity property around the optimum, but it is therefore far more efficient. We also provide a theoretical study of this algorithm through an upper bound on its simple regret.
8

Algorithmes stochastiques d'optimisation sous incertitude sur des structures complexes : convergence et applications / Stochastic algorithms for optimization under uncertainty on complex structures : convergence and applications

Gavra, Iona Alexandra 05 October 2017 (has links)
Les principaux sujets étudiés dans cette thèse concernent le développement d'algorithmes stochastiques d'optimisation sous incertitude, l'étude de leurs propriétés théoriques et leurs applications. Les algorithmes proposés sont des variantes du recuit simulé qui n'utilisent que des estimations sans biais de la fonction de coût. On étudie leur convergence en utilisant des outils développés dans la théorie des processus de Markov : on utilise les propriétés du générateur infinitésimal et des inégalités fonctionnelles pour mesurer la distance entre leur distribution et une distribution cible. La première partie est dédiée aux graphes quantiques, munis d'une mesure de probabilité sur l'ensemble des sommets. Les graphes quantiques sont des versions continues de graphes pondérés non-orientés. Le point de départ de cette thèse a été de trouver la moyenne de Fréchet de tels graphes. La moyenne de Fréchet est une extension aux espaces métriques de la moyenne euclidienne et est définie comme étant le point qui minimise la somme des carrés des distances pondérées à tous les sommets. Notre méthode est basée sur une formulation de Langevin d'un recuit simulé bruité et utilise une technique d'homogénéisation. Dans le but d'établir la convergence en probabilité du processus, on étudie l'évolution de l'entropie relative de sa loi par rapport a une mesure de Gibbs bien choisie. En utilisant des inégalités fonctionnelles (Poincaré et Sobolev) et le lemme de Gronwall, on montre ensuite que l'entropie relative tend vers zéro. Notre méthode est testée sur des données réelles et nous proposons une méthode heuristique pour adapter l'algorithme à de très grands graphes, en utilisant un clustering préliminaire. Dans le même cadre, on introduit une définition d'analyse en composantes principales pour un graphe quantique. Ceci implique, une fois de plus, un problème d'optimisation stochastique, cette fois-ci sur l'espace des géodésiques du graphe. Nous présentons un algorithme pour trouver la première composante principale et conjecturons la convergence du processus de Markov associé vers l'ensemble voulu. Dans une deuxième partie, on propose une version modifiée de l'algorithme du recuit simulé pour résoudre un problème d'optimisation stochastique global sur un espace d'états fini. Notre approche est inspirée du domaine général des méthodes Monte-Carlo et repose sur une chaine de Markov dont la probabilité de transition à chaque étape est définie à l'aide de " mini-lots " de taille croissante (aléatoire). On montre la convergence en probabilité de l'algorithme vers l'ensemble optimal, on donne la vitesse de convergence et un choix de paramètres optimisés pour assurer un nombre minimal d'évaluations pour une précision donnée et un intervalle de confiance proche de 1. Ce travail est complété par un ensemble de simulations numériques qui illustrent la performance pratique de notre algorithme à la fois sur des fonctions tests et sur des données réelles issues de cas concrets. / The main topics of this thesis involve the development of stochastic algorithms for optimization under uncertainty, the study of their theoretical properties and applications. The proposed algorithms are modified versions of simulated an- nealing that use only unbiased estimators of the cost function. We study their convergence using the tools developed in the theory of Markov processes: we use properties of infinitesimal generators and functional inequalities to measure the distance between their probability law and a target one. The first part is concerned with quantum graphs endowed with a probability measure on their vertex set. Quantum graphs are continuous versions of undirected weighted graphs. The starting point of the present work was the question of finding Fréchet means on such a graph. The Fréchet mean is an extension of the Euclidean mean to general metric spaces and is defined as an element that minimizes the sum of weighted square distances to all vertices. Our method relies on a Langevin formulation of a noisy simulated annealing dealt with using homogenization. In order to establish the convergence in probability of the process, we study the evolution of the relative entropy of its law with respect to a convenient Gibbs measure. Using functional inequalities (Poincare and Sobolev) and Gronwall's Lemma, we then show that the relative entropy goes to zero. We test our method on some real data sets and propose an heuristic method to adapt the algorithm to huge graphs, using a preliminary clustering. In the same framework, we introduce a definition of principal component analysis for quantum graphs. This implies, once more, a stochastic optimization problem, this time on the space of the graph's geodesics. We suggest an algorithm for finding the first principal component and conjecture the convergence of the associated Markov process to the wanted set. On the second part, we propose a modified version of the simulated annealing algorithm for solving a stochastic global optimization problem on a finite space. Our approach is inspired by the general field of Monte Carlo methods and relies on a Markov chain whose probability transition at each step is defined with the help of mini batches of increasing (random) size. We prove the algorithm's convergence in probability towards the optimal set, provide convergence rate and its optimized parametrization to ensure a minimal number of evaluations for a given accuracy and a confidence level close to 1. This work is completed with a set of numerical experiments and the assessment of the practical performance both on benchmark test cases and on real world examples.
9

L'inclusion de l'énergie dans les procédés de planification inverse : une étude appliquée aux cancers pulmonaires

Sévigny, Caroline January 2006 (has links)
Ballista est un nouveau système de planification de traitement qui a été développé en alternative à la radiothérapie par modulation d'intensité. L'optimisation à la base de ce dispositif contrôle la configuration des plans de traitement ainsi que le poids des différents champs générés en vue de moduler la radiation. Malgré sa grande flexibilité, Ballista se limite toutefois à la création de plans monoénergétiques. Ce mémoire s'est donc penché sur le rôle de l'énergie dans les plateformes de planification inverse. Le fonctionnement de Ballista s'appuie sur l'emploi de deux engins d'optimisation distincts : un algorithme de recuit simulé qui gère la configuration du traitement et un algorithme de quasi-Newton avec contraintes qui fixe le poids des différents champs. Afin de tirer profit de la nature bidimensionnelle du système, l'introduction de l'énergie en tant que variable versatile se fait par le biais de l'une ou l'autre de ces techniques de calcul. / Cette stratégie permet de créer des plans multiénergétiques qui possèdent une ou plusieurs énergies par incidence. Une étude rétrospective détaillée de l'efficacité du système a été réalisée sur la base de cinq patients atteints d'un cancer pulmonaire avancé. L'optimisation de l'énergie a en fait permis d'améliorer la conformité des traitements, mais surtout de limiter la dose délivrée aux poumons sains, l'organe à risque le plus problématique pour ce type d'irradiation. L'introduction de ce paramètre dans les procédés d'optimisation semble donc améliorer sensiblement la qualité des plans produits sans alourdir inutilement le poids clinique de la planification.
10

Etude théorique sur le calcul des mécanismes au foyer dans un réservoir et application à la sismicité de la saline de Vauvert (Gard)

Godano, Maxime 09 July 2009 (has links) (PDF)
Nous proposons une méthode d'inversion non linéaire des amplitudes des ondes directes P, SV et SH basée sur l'algorithme du recuit simulé, afin de déterminer à partir d'un nombre limité de stations, le mécanisme au foyer de séismes induits en contexte de réservoir. Cette méthode permet de déterminer aussi bien les paramètres du plan de faille (azimut, pendage et angle de glissement) décrivant une source double-couple, que les six composantes du tenseur des moments décrivant une source plus générale. <br />L'inversion double-couple et l'inversion du tenseur des moments sont testées sur quatre séismes induits dans le réservoir géothermique de Soultz-sous-Forêts. Les mécanismes obtenus sont en accord avec ceux déterminés par Charléty et al. 2007.<br />La méthode d'inversion est appliquée à la sismicité de la saline de Vauvert enregistrée par un réseau permanent de deux stations 3-composante. Dans un premier temps, la méthode est testée sur 15 séismes enregistrés durant le déploiement temporaire d'une antenne de quatre capteurs 3-composante. La comparaison entre l'inversion utilisant les deux stations permanentes et l'antenne temporaires et l'inversion utilisant seulement les deux stations permanentes montre des mécanismes au foyer double-couple identiques pour les séismes localisés entre les deux stations permanentes. Dans un deuxième temps, la méthode est appliquée à un essaim de sismicité. Les mécanismes au foyer obtenus pour 532 évènements, indiquent pour la majorité une rupture le long de fractures sub-verticales NE-SW, interprétée comme de probables ruptures sur les plans stratigraphiques des bancs d'insolubles intercalés dans la formation de sel.

Page generated in 0.0862 seconds