Spelling suggestions: "subject:"algorithme""
101 |
Estimation haute-résolution de la position de cibles en mouvement à partir du suivi du sous-espace sources et d'un estimateur statistique de 2e ordreIsabel, Marc-André January 2018 (has links)
En 1995, la technologie LIDAR fait émergence en télédétection et entraîne avec elle une nouvelle forme de concurrence dans un domaine jusqu'alors dominé par les systèmes RADAR. Contrairement à ces derniers, l'émetteur d'un LIDAR opère à des fréquences au-delà des ondes radios, habituellement dans l'infrarouge, ce qui fait qu'une détection non cohérente doit être employée et que seule l'enveloppe des signaux est récupérée, formant ainsi des signaux réels. Alors que de multiples algorithmes ont été développés au l des années pour faire le traitement des signaux captés par l'antenne-réseau d'un RADAR, aucun n'était reconnu jusqu'à présent comme étant particulièrement performant lorsque utilisé avec des signaux réels. En 2015, dans le cadre d'un projet de recherche visant à améliorer la distance et la précision de la détection des objets à l'aide d'un LIDAR, une adaptation [1] du très populaire algorithme MUSIC développé par Schmidt fut réalisée a n de pouvoir l'utiliser selon le principe du temps de vol plutôt que pour les directions d'arrivée. Cette adaptation ouvrit la voie à l'utilisation d'algorithmes statistiques, à l'origine conçus pour les signaux avec information de phase, pour des signaux réels. Malheureusement, l'application directe de ces algorithmes requiert un temps d'exécution considérable et ce, en particulier lors de la formation, du traitement et de la décomposition propre de la matrice ReXX. Par conséquent, des optimisations doivent être considérées pour être en mesure d'en faire l'implantation dans du matériel à faible coût lorsqu'il est question d'opération en temps réel. Parmi ces optimisations, c'est l'utilisation de méthodes de suivi fondées sur la notion de sous-espace qui fait l'objet de cet ouvrage. Ces algorithmes reposent sur l'idée qu'il est possible d'oublier, de façon graduelle, les données du passé au pro t des nouvelles données sans avoir à passer par la formation de la matrice ReXX à chaque fois. Ainsi, les résultats démontrent qu'une réduction de 25% à 95% du temps d'exécution est possible dans un contexte d'utilisation conjointe, mais moins fréquente, avec une méthode à complexité algorithmique plus élevée. Par ailleurs, les résultats des essais réalisés par [1] ne couvrent que les cibles stationnaires. Par conséquent, ce projet vise à étendre cette étude aux cibles en mouvement. Les résultats obtenus permettent de démontrer l'efficacité des méthodes de suivi du sous-espace pour de tels cas. / In 1995, LIDAR systems emerged as a new alternative to the well-known RADAR systems for remote sensing applications. However, unlike RADAR, the operating frequency of LIDAR systems is above the radio frequencies and usually in the infrared which means that a non-coherent detection has to be used to retrieve the signal's enveloppe. While several signal processing algorithms have been developped for RADAR phased arrays, none of these algorithms are known, to this day, to be e cient when dealing with real, phaseless signals. In 2015, as part of a research project to enhance the detection precision and maximal distance of a LIDAR system, an adaptation [1] of the so-called MUSIC algorithm developped by Schmidt was realised to be used with the time-of- ight principle instead of the direction of arrival principle. Unfortunately, the direct application of the adapted algorithm was time consuming, especially the creation, processing and eigendecomposition stages of the ReXX matrix. As so, optimizations are required to allow its implementation into a low-cost system for real-time purposes. Among those optimizations, the use of subspace tracking methods will be studied in this thesis. Subspace tracking algorithms are based on the idea that instead of having to create ReXX at each data update, one can use the known data while adding the new data with a forgetting factor. The result of these optimizations is that a decrease of 25% to 95% in execution time is observed when subspace tracking is used together with a higher complexity method to initialize its parameters. The study realised by [1] was mostly done for stationary objects. This thesis aims to extend that study to non stationary objects. Results show that using subspace tracking methods is even more efficient in these cases.
|
102 |
Inférence de la structure d'interactions de données bruitéesLizotte, Simon 22 December 2022 (has links)
La science des réseaux est notamment à la recherche de modèles mathématiques capables de reproduire le comportement de systèmes complexes empiriques. Cependant, la représentation usuelle, le graphe, est parfois inadéquate étant donné sa limitation à encoder uniquement les relations par paires. De nombreux travaux récents suggèrent que l'utilisation de l'hypergraphe, une généralisation décrivant les interactions d'ordre supérieur (plus de deux composantes), permet d'expliquer des phénomènes auparavant incompris avec le graphe. Or, la structure de ces réseaux complexes est rarement ou difficilement observée directement. De fait, on mesure plutôt une quantité intermédiaire, comme la fréquence de chaque interaction, pour ensuite reconstruire la structure originale. Bien que de nombreuses méthodes de reconstruction de graphes aient été développées, peu d'approches permettent de retrouver les interactions d'ordre supérieur d'un système complexe. Dans ce mémoire, on développe une nouvelle approche de reconstruction pouvant déceler les interactions connectant trois noeuds parmi des observations dyadiques bruitées. Basée sur l'inférence bayésienne, cette méthode génère la distribution des hypergraphes les plus plausibles pour un jeu de données grâce à un algorithme de type Metropolis-Hastings-within-Gibbs, une méthode de Monte-Carlo par chaînes de Markov. En vue d'évaluer la pertinence d'un modèle d'interactions d'ordre supérieur pour des observations dyadiques, le modèle d'hypergraphe développé est comparé à un second modèle bayésien supposant que la structure sous-jacente est un graphe admettant deux types d'interactions par paires. Les résultats obtenus pour des hypergraphes synthétiques et empiriques indiquent que la corrélation intrinsèque à la projection d'interactions d'ordre supérieur améliore le processus de reconstruction lorsque les observations associées aux interactions dyadiques et triadiques sont semblables. / Network science is looking for mathematical models capable of reproducing the behavior of empirical complex systems. However, the usual representation, the graph, is sometimes inadequate given its limitation to encode only pairwise relationships. Many recent works suggest that the use of the hypergraph, a generalization describing higher-order interactions (more than two components), allows to explain phenomena previously not understood with graphs. However, the structure of these complex networks is seldom or hardly observed directly. Instead, we measure an intermediate quantity, such as the frequency of each interaction, and then reconstruct the original structure. Although many graph reconstruction methods have been developed, few approaches recover the higher-order interactions of a complex system. In this thesis, we develop a new reconstruction approach which detects interactions connecting three vertices among noisy dyadic observations. Based on Bayesian inference, this method generates the distribution of the most plausible hypergraphs for a dataset using a Metropolis-Hastings-within-Gibbs algorithm, a Markov chain Monte Carlo method. In order to evaluate the relevance of a higher-order interaction model for dyadic observations, the developed hypergraph model is compared to a second Bayesian model assuming that the underlying structure is a graph admitting two types of pairwise interactions. Results for synthetic and empirical hypergraphs indicate that the intrinsic correlation to the projection of higher-order interactions improves the reconstruction process when observations associated with dyadic and triadic interactions are similar.
|
103 |
Développement d'algorithmes et d'outils logiciels pour l'assistance technique et le suivi en réadaptationSchweitzer, Frédéric 05 August 2022 (has links)
Ce mémoire présente deux projets de développement portant sur des algorithmes et des outils logiciels offrant des solutions pratiques à des problématiques courantes rencontrées en réadaptation. Le premier développement présenté est un algorithme de correspondance de séquence qui s'intègre à des interfaces de contrôle couramment utilisées en pratique. L'implémentation de cet algorithme offre une solution flexible pouvant s'adapter à n'importe quel utilisateur de technologies d'assistances. Le contrôle de tels appareils représente un défi de taille puisqu'ils ont, la plupart du temps, une dimensionnalité élevée (c-à-d. plusieurs degrés de liberté, modes ou commandes) et sont maniés à l'aide d'interfaces basées sur de capteurs de faible dimensionnalité offrant donc très peu de commandes physiques distinctes pour l'utilisateur. L'algorithme proposé se base donc sur de la reconnaissance de courts signaux temporels ayant la possibilité d'être agencés en séquences. L'éventail de combinaisons possibles augmente ainsi la dimensionnalité de l'interface. Deux applications de l'algorithme sont développées et testées. La première avec une interface de contrôle par le souffle pour un bras robotisé et la seconde pour une interface de gestes de la main pour le contrôle du clavier-souris d'un ordinateur. Le second développement présenté dans ce mémoire porte plutôt sur la collecte et l'analyse de données en réadaptation. Que ce soit en milieux cliniques, au laboratoires ou au domicile, nombreuses sont les situations où l'on souhaite récolter des données. La solution pour cette problématique se présente sous la forme d'un écosystème d'applications connectées incluant serveur et applications web, mobiles et embarquée. Ces outils logiciels sont développés sur mesure et offrent un procédé unique, peu coûteux, léger et rapide pour la collecte, la visualisation et la récupération de données. Ce manuscrit détaille une première version en décrivant l'architecture employée, les technologies utilisées et les raisons qui ont mené à ces choix tout en guidant les futures itérations. / This Master's thesis presents two development projects about algorithms and software tools providing practical solutions to commonly faced situations in rehabilitation context. The first project is the development of a sequence matching algorithm that can be integrated to the most commonly used control interfaces. The implementation of this algorithm provides a flexible solution that can be adapted to any assistive technology user. The control of such devices represents a challenge since their dimensionality is high (i.e., many degrees of freedom, modes, commands) and they are controlled with interfaces based on low-dimensionality sensors. Thus, the number of actual physical commands that the user can perform is low. The proposed algorithm is based on short time signals that can be organized into sequences. The multiple possible combinations then contribute to increasing the dimensionality of the interface. Two applications of the algorithm have been developed and tested. The first is a sip-and-puff control interface for a robotic assistive arm and the second is a hand gesture interface for the control of a computer's mouse and keyboard. The second project presented in this document addresses the issue of collecting and analyzing data. In a rehabilitation's clinical or laboratory environment, or at home, there are many situations that require gathering data. The proposed solution to this issue is a connected applications ecosystem that includes a web server and mobile, web and embedded applications. This custom-made software offers a unique, inexpensive, lightweight and fast workflow to visualize and retrieve data. The following document describes a first version by elaborating on the architecture, the technologies used, the reasons for those choices, and guide the next iterations.
|
104 |
Développement d'algorithmes d'estimation de la pose d'objets saisis par un préhenseur robotiqueCôté, Marianne 24 April 2018 (has links)
Les préhenseurs robotiques sont largement utilisés en industrie et leur déploiement pourrait être encore plus important si ces derniers étaient plus intelligents. En leur conférant des capacités tactiles et une intelligence leur permettant d’estimer la pose d’un objet saisi, une plus vaste gamme de tâches pourraient être accomplies par les robots. Ce mémoire présente le développement d’algorithmes d’estimation de la pose d’objets saisis par un préhenseur robotique. Des algorithmes ont été développés pour trois systèmes robotisés différents, mais pour les mêmes considérations. Effectivement, pour les trois systèmes la pose est estimée uniquement à partir d’une saisie d’objet, de données tactiles et de la configuration du préhenseur. Pour chaque système, la performance atteignable pour le système minimaliste étudié est évaluée. Dans ce mémoire, les concepts généraux sur l’estimation de la pose sont d’abord exposés. Ensuite, un préhenseur plan à deux doigts comprenant deux phalanges chacun est modélisé dans un environnement de simulation et un algorithme permettant d’estimer la pose d’un objet saisi par le préhenseur est décrit. Cet algorithme est basé sur les arbres d’interprétation et l’algorithme de RANSAC. Par la suite, un système expérimental plan comprenant une phalange supplémentaire par doigt est modélisé et étudié pour le développement d’un algorithme approprié d’estimation de la pose. Les principes de ce dernier sont similaires au premier algorithme, mais les capteurs compris dans le système sont moins précis et des adaptations et améliorations ont dû être appliquées. Entre autres, les mesures des capteurs ont été mieux exploitées. Finalement, un système expérimental spatial composé de trois doigts comprenant trois phalanges chacun est étudié. Suite à la modélisation, l’algorithme développé pour ce système complexe est présenté. Des hypothèses partiellement aléatoires sont générées, complétées, puis évaluées. L’étape d’évaluation fait notamment appel à l’algorithme de Levenberg-Marquardt.
|
105 |
Empirical analysis of imbalance countering strategies in binary classificationGingras, Jonathan 31 January 2021 (has links)
De nos jours, les algorithmes de classification binaire sont utilisés dans des tâches touchant plusieurs champs d’applications comme les fraudes en-ligne, le dépistage bio-médical ou bien la toxicité en-ligne. Malgré le nombre de données qui est souvent disponible pour ces applications, qui viennent habituellement de source réelles, une particularité y est fréquemment observée: la représentation débalancée des classes. Cette imbalance demeure un problème d’envergure pour les algorithmes de classification, car la vaste majorité d’entre eux ne sont pas conçus avec cette représentation inégale à l’esprit. De plus, dans les paramètres expérimentaux, les données sur lesquelles ils sont appliqués sont souvent bien balancées, à cause de la finalité-même de ces expérimentations. Dans le présent mémoire, une revue des stratégies et techniques existantes pour contrer l’imbalance binaire est proposée, dans laquelle un point de vue par modification de données ainsi qu’un point de vue par modification algorithmique seront adressés. Le premier sujet des présents travaux consiste en les approches de pré-traitement et leurs effets sur les métriques de classification, dans lequel des expérimentations contrôlées (présentant différents niveaux de débalancement) et des applications d’entreprises sont présentées et analysées. Le second sujet consiste en le paradigme sensible-au-coût appliqué à l’optimisation directe de la métrique de la F-mesure en utilisant un réseau de neurones, dans lequel des expérimentations sur un jeu de données très débalancé sont présentées et discutées, le tout accompagné d’une comparaison avec différents paramètres usuels. À la lecture du présent document, le lecteur aura une bonne idée des techniques de prétraitement existantes et ce qu’on peut en retirer d’un point de vue expérimental selon des ensembles de données variés. Également, l’application du paradigme sensible-au-coût par optimisation de la F-mesure donnera un aperçu positif quant au point de vue algorithmique dans un contexte de données très débalancées. / Nowadays, binary classification algorithms are used in detection-related tasks touching many fields of application such as online frauds, biomedical screening, or online toxicity. Despite the amount of data that’s usually available for those applications, which habitually comes from real-world data sources, a particularity is frequently observed in it: the imbalanced representation of the classes. This imbalance remains a significant problem for binary classification algorithms, because the vast majority of these algorithms are not designed with this unequal representation in mind. Moreover, in experimental setups, the data on which they are usually applied is more than often well-balanced, because of the very purpose of these experiments. In the current thesis, a review of the existing strategies and techniques to face the binary imbalance problem is proposed in which both a data-modification point of view and a algorithmmodification point of view are addressed. The first subject of this work are data prepocessing approaches and their effects on classification metrics, in which both controlled experimental setups (showing different levels of imbalance), and enterprise data applications are presented and analyzed. The second subject is the cost-sensitive paradigm applied to the direct optimization of the F-measure metric using a neural network, in which experimentations on a highly imbalanced data set are presented and discussed, as well as comparisons with different common settings. After reading the current document, the reader will be well aware of the existing preprocessing techniques and what they can be achieve in an experimental context using various data sets. Moreover, the application of the cost-sensitive paradigm by optimization of the F-measure will give positive insight regarding the algorithmic point of view in a context of very imbalanced data.
|
106 |
Analyse des algorithmes d'Euclide : une approche dynaniqueDaireaux, Benoit 22 June 2005 (has links) (PDF)
Les objets étudiés dans cette thèse sont des algorithmes de calcul de pgcd. Nous effectuons dans cette thèse des analyses probabilistes de plusieurs de ces algorithmes : les algorithmes alpha-euclidiens, l'algorithme LSB et l'algorithme de Lehmer-Euclide. Nous obtenons des résultats précis sur le comportement moyen de toute une gamme de paramètres, entre autres le nombre d'itérations et la complexité en bits. Les techniques employées sont celles de l'analyse dynamique d'algorithmes, et les analyses effectuées dans cette thèse permettent d'élargir le champ d'application de cette méthodologie. En particulier, nous étudions des systèmes dynamiques à branches non surjectives, des systèmes dynamiques définis sur l'ensemble des nombres p-adiques ou encore des systèmes de fonctions itérées. Ces analyses impliquent une étude très précise des opérateurs de Perron-Frobenius et des opérateurs de transfert associés à ces systèmes. En particulier, le comportement probabiliste des algorithmes est relié aux propriétés spectrales de ces opérateurs. Nous analysons également l'évolution des principaux paramètres des algorithmes au cours de leur execution.
|
107 |
Rangement d'objets multiboîtes : modèles et algorithmesLemaire, Pierre 06 September 2004 (has links) (PDF)
Un objet multiboîte est composé de plusieurs parties identiques qui doivent être rangées dans des boîtes différentes. La hauteur d'une boîte est alors la somme des hauteurs des objets qu'elle contient. Ce concept généralise et englobe de nombreux problèmes de la littérature de la recherche opérationnelle.<br /><br />Une classification de ces modèles est proposée. Les bases théoriques sont posées. En particulier, la complexité pour les principaux types d'objets et objectifs est déterminée.<br /><br />Une étude détaillée est effectuée lorsque les objets ont des largeurs constantes et que l'on veut minimiser la hauteur de la boîte la plus haute. Des bornes inférieures, des heuristiques avec de très bonnes garanties de performance et un algorithme génétique sont proposés pour résoudre ce modèle. Leurs comportements théoriques et expérimentaux sont analysés.
|
108 |
Algorithmes génétiques hybrides en optimisation combinatoireRebreyend, Pascal 14 January 1999 (has links) (PDF)
Cette thèse aborde le problème de la résolution des problèmes combinatoires à l'aide d'algorithmes génétiques. Ce type d'algorithme présente en effet nombres d'avantages. Cependant, ils sont généralement relativement lents. Cette thèse est donc centrée sur les algorithmes hybrides, c'est-à-dire des algorithmes construits à l'aide de plusieurs méthodes différentes. Dans notre cas, nous étudions les algorithmes qui réunissent algorithmes génétiques et heuristiques. Il existe deux méthodes pour générer de tels algorithmes qui sont la représentation directe et la représentation indirecte. Ces deux méthodes sont étudiés au travers de trois problèmes distincts : l'ordonnancement statique de programmes parallèles, le placement de composants électroniques et la planification de réseaux cellulaires. Pour chacun des trois problèmes, les algorithmes hybrides ont montrés leur efficacité. Pour le problème de la planification de réseaux cellulaires, une nouvelle modélisation a été faite. Cette modélisation permet d'effectuer en même temps le placement des émetteurs et l'allocation de fréquences.
|
109 |
Algorithme de partitionnement appliqué aux systèmes dynamiquement reconfigurables en télécommunicationsCardoso de Souza, Daniel 13 December 2006 (has links) (PDF)
Cette thèse a pour but de proposer un algorithme de partitionnement matériel/logiciel optimisé. On travaille sur l'hypothèse de que quelques caractéristiques spécifiques à certains algorithmes déjà publiés puissent être combinées de façon avantageuse, menant à l'amélioration d'un algorithme de partitionnement de base et, par conséquence, des systèmes hétérogènes générés par cet algorithme. L'ensemble d'optimisations proposées pour être réalisées dans ce nouvel algorithme consiste en : généralisation des architecturescible candidates avec l'ajout de FPGA's pour le partitionnement, considération précise des coûts et puissances des fonctions allouées en matériel, ordonnancement de systèmes au matériel dynamiquement reconfigurable, et prise en compte de plusieurs alternatives d'implémentation d'un noeud d'application dans un même processeur. Ces optimisations sont implémentées en versions successives de l'algorithme de partitionnement proposé, lesquelles sont testées avec deux applications de traitement du signal. Les résultats du partitionnement démontrent l'effet de chaque optimisation sur la qualité du système hétérogène obtenu.
|
110 |
Algorithmes évolutionnaires et résolution de problèmes de satisfaction de contraintes en domaines finisMadeline, Blaise 18 December 2002 (has links) (PDF)
Cette thèse traite de l'utilisation des algorithmes évolutionnaires (AE) pour résoudre des problèmes de satisfaction de contrainte (CSP) en domaines finis sans spécialisation ni hybridation particulière. Après avoir présenté les CSP et les méthodes couramment utilisées pour les résoudre (chapitres 1 et 2), nous présentons le paradigme évolutionnaire et ses applications (chapitres 3 et 4). Ensuite, nous proposons une comparaison entre les méthodes de recherche arborescente et les métaheuristiques sur des coloriages de graphe sur-contraints, dans un contexte de réglage des paramètres minimal (chapitre 5). Nous étudions le paysage de recherche pour comprendre les raisons des différences d'efficacité des méthodes. Enfin, nous proposons de nouveaux opérateurs génétiques (croisement, mutation, diversification) dont le paramétrage est moins fastidieux qu'avec les opérateurs classiques (chapitre 6). Nous concluons sur l'intérêt d'exploration des réseaux de neutralité.
|
Page generated in 0.0361 seconds