Th. 3e cycle--Math. pures--Besançon, 1977. N°: 274.

Th. doct.-ing.--Inform.--Nancy--I.N.P.L., 1984.

Th.--Sci. math.--Besançon, 1981. N°: 148.

Th. 3e cycle--Méthodes d'approximation et algorithmes en anal. et théor. des nombres--Besançon, 1979. N°: 330.

De nombreux problèmes d'optimisation issus du monde réel. notamment dans le domaine de la logistique, doivent faire face à beaucoup de difficultés, En effet, ils sont souvent caractérisés par des espaces de recherche vastes et complexes, de multiples fonctions objectif contradictoires, et une foule d'incertitudes qui doivent être prises en compte, Les métaheuristiques sont des candidats naturels pour résoudre ces problèmes, ce qui les rend préférables aux méthodes d'optimisation classiques, Toutefois, le développent de métaheuristiques efficaces résulte en un processus d'ingénierie complexe, Le coeur de ce travail réside en la conception, l'implémentation et l'analyse expérimentale de métaheuristiques pour l'optimisation multiobjectif ainsi que leurs applications à des problèmes logistiques de tournées et d'ordonnancement. Tout d'abord, une vue unifiée de ces approches est présentée, puis intégrée dans une plateforme logicielle dédiée à leur implémentation, ParadisEO-MOEO, Ensuite, plusieurs approches de coopération, combinant des métaheuristiques pour l'optimisation multiobjectif, sont proposées, Enfin, la question de la prise en compte de l'incertitude est abordée dans le context de l'optimisation multiobjectif. / Many real-world optimization problems, especially in the field of logistics, have to face a lot of difficulties, Indeed, they are often characterized by large and complex search'spaces, multiple conflicting objective functions, and a host of uncertainties that have ta be taken into account. Metaheuristics are natural candidates ta solve those problems and make them preferable to classical optimization methods, However, the development of efficient metaheuristics results in a complex engineering process, The core subject of this work lies in the design, implementation and experimental analysis of metaheuristics for multiobjective optimization, together with theu applications to logis tic problems from routing and scheduling, Firstly, a unitïed view of such approaches is presented and then integrated into a software framework for their implementation, ParadisEO-MOEO, Next, sorne cooperative approaches combining metaheuristics for multiobjective optimization are proposed, At last, the issue of uncertainty handling is discussed in the context of multiobjective optimization.

Ce mémoire présente une analyse des performances d'algorithmes de pistage dans le cas d'un lidar à faible résolution angulaire. Plus particulièrement, on s'intéresse à un système lidar composé de capteurs individuels couvrant chacun une région angulaire distincte. Les capteurs utilisés ont la particularité de mesurer uniquement la distance des objets rencontrés, limitant ainsi la résolution angulaire à leur faisceau. Les algorithmes ont été testés à l'aide de données de simulations basées sur le système lidar. Dans les cas de détections simples, un algorithme de pistage instantané basé sur un filtre de Kalman a été amplement suffisant. Pour des cas plus complexes, l'utilisation de la théorie des hypothèses multiples ( MHT pour multiple hypothesis theory ) a permis d'améliorer les résultats d'associations. Dans cette méthode, lorsqu'il y a une ambiguïté d'associations, les hypothèses probables sont considérées en parallèle jusqu'à ce que l'information reçue aux instants subséquents permette d'identifier l'association la plus probable. Pour le cas à l'étude, les résultats optimaux ont été obtenus pour un MHT considérant au plus 3 hypothèses à chaque instant et en attendant au plus 3 pas de temps pour prendre une décision. Globalement, les algorithmes présentés ont mieux réagi face aux fausses alarmes plutôt que face aux non détections. Une méthode permettant d'optimiser les temps de calcul des algorithmes a également été développée. Cette méthode se base sur l'algorithme de Murty et permet de passer d'une méthode d'association simple et rapide (ici l'algorithme d'associations par plus proches voisins)à une méthode d'associations plus complexe (ici par filtre de Kalman) seulement lorsqu'une ambiguïté est détectée dans l'association. Dans le cas d'une situation simple à deux cibles, des performances comparables à celle d'une association par filtre de Kalman ont été obtenues avec un temps de calcul de moins de 10% de celui nécessaire habituellement. / This thesis presents an analysis of the performance of tracking algorithms in the case of a lidar with low angular resolution. More particularly, we are interested in a lidar system composed of individual sensors each covering a distinct angular region. The sensors used have the particularity of measuring only the distance of the objects encountered, thus limiting the angular resolution to their beam. The algorithms were tested using simulation data based on the lidar system. In the case of simple detections, an instant tracking algorithm based on a Kalman filter was more than sufficient. For more complex cases, the use of multiple hypothesis theory (MHT) made it possible to improve tracking results. In this method, when there is an ambiguity in the tracking, the possible hypotheses are considered simultaneously until the information received at subsequent times makes it possible to identify the correct one. For the case under study, optimal results were obtained for an MHT considering at most 3 hypotheses at any time and waiting at most 3 time steps to make a decision. Overall, the algorithms presented reacted better to false alarms rather than to non-detections. A method for optimizing the calculation times of the algorithms has also been developed. This method is based on Murty's algorithm goes from a simple and fast tracking method (here by nearest neighbors) to a more complex association method (here using a Kalman lter) only when an ambiguity is detected. In the case of a simple situation with two targets, performances comparable to that of an association by Kalman filter were obtained with a calculation time of less than 10% of that usually required.

L'ambition du présent mémoire est la présentation d'un ensemble de principes appelés la théorie PAC-Bayes. L'approche offre des garanties de type PAC aux algorithmes d'apprentissage bayésiens généralisés. Le mémoire traite essentiellement des cas où la distribution prior dépend des données. Le mémoire est divisé en trois chapitres. Le premier chapitre détaille les notions de base en apprentissage automatique. Il s'agit d'idées nécessaires à la bonne compréhension des deux chapitres subséquents. Le deuxième chapitre présente et discute de la théorie PAC-Bayes. Finalement, le troisième chapitre aborde l'idée d'une garantie PAC-Bayes où le prior dépend des données. Il y a deux contributions principales. La première contribution est une formulation analytique du risque empirique espéré pour les distributions elliptiques. La seconde contribution est une extension du travail de Parrado-Hernández et al. (34). En effet, il s'agit du développement d'une garantie PAC-Bayes avec un prior espérance non sphérique. / The ambition of this thesis is to present a set of principles called the PAC-Bayes theory. The approach provides PAC-like guarantees for generalised Bayesian learning algorithms. This thesis deals essentially with cases where the prior distribution is data dependent. The paper is divided into three chapters. The first chapter details the core concepts of machine learning. These are ideas that are necessary for a good understanding of the two subsequent chapters. The second chapter presents and discusses the PAC-Bayes theory. Finally, the third chapter addresses the idea of a PAC-Bayes guarantee where the prior depend on the data. There are two main contributions. The first contribution is an analytical formulation of the empirical expected risk for elliptical distributions. The second contribution is an extension of the work of Parrado-Hernández et al. (34). Indeed, it is the development of a PAC-Bayes guarantee with a non-spherical prior expectation.

Ce mémoire présente une analyse des performances d'algorithmes de pistage dans le cas d'un lidar à faible résolution angulaire. Plus particulièrement, on s'intéresse à un système lidar composé de capteurs individuels couvrant chacun une région angulaire distincte. Les capteurs utilisés ont la particularité de mesurer uniquement la distance des objets rencontrés, limitant ainsi la résolution angulaire à leur faisceau. Les algorithmes ont été testés à l'aide de données de simulations basées sur le système lidar. Dans les cas de détections simples, un algorithme de pistage instantané basé sur un filtre de Kalman a été amplement suffisant. Pour des cas plus complexes, l'utilisation de la théorie des hypothèses multiples ( MHT pour multiple hypothesis theory ) a permis d'améliorer les résultats d'associations. Dans cette méthode, lorsqu'il y a une ambiguïté d'associations, les hypothèses probables sont considérées en parallèle jusqu'à ce que l'information reçue aux instants subséquents permette d'identifier l'association la plus probable. Pour le cas à l'étude, les résultats optimaux ont été obtenus pour un MHT considérant au plus 3 hypothèses à chaque instant et en attendant au plus 3 pas de temps pour prendre une décision. Globalement, les algorithmes présentés ont mieux réagi face aux fausses alarmes plutôt que face aux non détections. Une méthode permettant d'optimiser les temps de calcul des algorithmes a également été développée. Cette méthode se base sur l'algorithme de Murty et permet de passer d'une méthode d'association simple et rapide (ici l'algorithme d'associations par plus proches voisins)à une méthode d'associations plus complexe (ici par filtre de Kalman) seulement lorsqu'une ambiguïté est détectée dans l'association. Dans le cas d'une situation simple à deux cibles, des performances comparables à celle d'une association par filtre de Kalman ont été obtenues avec un temps de calcul de moins de 10% de celui nécessaire habituellement. / This thesis presents an analysis of the performance of tracking algorithms in the case of a lidar with low angular resolution. More particularly, we are interested in a lidar system composed of individual sensors each covering a distinct angular region. The sensors used have the particularity of measuring only the distance of the objects encountered, thus limiting the angular resolution to their beam. The algorithms were tested using simulation data based on the lidar system. In the case of simple detections, an instant tracking algorithm based on a Kalman filter was more than sufficient. For more complex cases, the use of multiple hypothesis theory (MHT) made it possible to improve tracking results. In this method, when there is an ambiguity in the tracking, the possible hypotheses are considered simultaneously until the information received at subsequent times makes it possible to identify the correct one. For the case under study, optimal results were obtained for an MHT considering at most 3 hypotheses at any time and waiting at most 3 time steps to make a decision. Overall, the algorithms presented reacted better to false alarms rather than to non-detections. A method for optimizing the calculation times of the algorithms has also been developed. This method is based on Murty's algorithm goes from a simple and fast tracking method (here by nearest neighbors) to a more complex association method (here using a Kalman lter) only when an ambiguity is detected. In the case of a simple situation with two targets, performances comparable to that of an association by Kalman filter were obtained with a calculation time of less than 10% of that usually required.

L'ambition du présent mémoire est la présentation d'un ensemble de principes appelés la théorie PAC-Bayes. L'approche offre des garanties de type PAC aux algorithmes d'apprentissage bayésiens généralisés. Le mémoire traite essentiellement des cas où la distribution prior dépend des données. Le mémoire est divisé en trois chapitres. Le premier chapitre détaille les notions de base en apprentissage automatique. Il s'agit d'idées nécessaires à la bonne compréhension des deux chapitres subséquents. Le deuxième chapitre présente et discute de la théorie PAC-Bayes. Finalement, le troisième chapitre aborde l'idée d'une garantie PAC-Bayes où le prior dépend des données. Il y a deux contributions principales. La première contribution est une formulation analytique du risque empirique espéré pour les distributions elliptiques. La seconde contribution est une extension du travail de Parrado-Hernández et al. (34). En effet, il s'agit du développement d'une garantie PAC-Bayes avec un prior espérance non sphérique. / The ambition of this thesis is to present a set of principles called the PAC-Bayes theory. The approach provides PAC-like guarantees for generalised Bayesian learning algorithms. This thesis deals essentially with cases where the prior distribution is data dependent. The paper is divided into three chapters. The first chapter details the core concepts of machine learning. These are ideas that are necessary for a good understanding of the two subsequent chapters. The second chapter presents and discusses the PAC-Bayes theory. Finally, the third chapter addresses the idea of a PAC-Bayes guarantee where the prior depend on the data. There are two main contributions. The first contribution is an analytical formulation of the empirical expected risk for elliptical distributions. The second contribution is an extension of the work of Parrado-Hernández et al. (34). Indeed, it is the development of a PAC-Bayes guarantee with a non-spherical prior expectation.

Titre de l'écran-titre (visionné le 10 janvier 2024) / La Transformée de Burrows-Wheeler (BWT) permet d'effectuer une excellente compression de données grâce à son tri de la séquence des caractères sources, regroupant ainsi des données similaires pour améliorer la compression. Bien que l'algorithme Move-to-Front (MTF) ne cause pas de compression en soi, la synergie qu'elle a avec l'algorithme de Huffman, classique ou amélioré, améliore la performance de compression. MTF, en augmentant la fréquence des petites valeurs dans les données codées, combiné au réarrangement des caractères effectué par BWT, crée un cadre optimal pour un codage efficace de Huffman. Néanmoins, la version classique de MTF a ses limites, car elle promeut uniformément les symboles accédés à l'avant de la liste, négligeant éventuellement les structures présentes dans le texte d'entrée. En introduisant une politique de promotion optimale qui réordonne minutieusement les symboles selon les modèles de données inhérents, on peut accentuer l'asymétrie de la distribution des valeurs, renforçant la compatibilité avec l'algorithme de Huffman. Cette méthode améliorée a démontré sa capacité à compresser des images complexes, non linéaires, avec une efficacité notable, bien que l'avantage obtenu diminue chez des images à la géométrie plus simple. / The Burrows-Wheeler Transform (BWT) allows for excellent data compression due to its sorting of the source character sequence, grouping similar data to enhance compression. Although the Moveto-Front (MTF) algorithm does not cause compression in itself, its synergy with the classic or enhanced Huffman algorithm improves compression performance. MTF, by increasing the frequency of small values in coded data, combined with the character rearrangement performed by BWT, creates an optimal framework for efficient Huffman coding. However, the classic version of MTF has its limits, as it uniformly promotes accessed symbols to the front of the list, possibly neglecting structures present in the input text. By introducing an optimal promotion policy that carefully reorders symbols according to inherent data patterns, one can accentuate the asymmetry of value distribution, enhancing compatibility with the Huffman algorithm. This improved method has demonstrated its ability to compress complex, non-linear images with notable efficiency, although the advantage obtained decreases for images with simpler geometry.