Multivariate statistical methods for studying the mechanics of heuristics

Algorithms are the most effective knowledge repositories yet conceived by mankind for they automate computations on a given formal medium, the computer system. NP-Completeness tell us that among the computable treatable problems there are some which we do not know an efficient way of dealing with, i.e. we do not know how to conceive efficient algorithms for them. Nevertheless, practical experience tells us that many algorithms for these problems are indeed quite effective. That is to say that the experimental analysis of their input/output relationship reveal a far better situation than what can be derived by the mathematical analysis of these algorithms' properties. It also means that the dynamic process induced by the algorithm (i.e. the computational process) exceeds our capacity of express and communicate the knowledge we embed in such algorithm. Without the actual implementation of the algorithm we would not be able to tell their behavior. The work in this thesis concerns such dynamic process. Rather than analyze the properties of the knowledge we represent on an algorithm, we want to investigate the mechanics of the computational process in order to infer the knowledge behind it. That is what we call exploratory studies, for we want to acquire new knowledge about the treatment given by our algorithm to the problem. We approach this matter by a data analysis perspective. Our method consists on probing the computational process in search for insightful statistical evidences about its mechanics. In order to guarantee the insightful aspect of these evidences it is essential that they report on a pertinent computational process, i.e. for large input problems. Data analysis is therefore a crucial issue in such kind of study. In this work we present a systematic application of Multivariate Descriptive Statistical Analysis techniques to raise statistical evidences on the mechanics of the computational process induced by heuristic algorithms for hard optimization problems. We present a case study of a state of the art heuristic for the Traveling Salesman Problem where we interpret and discuss the evidences raised by our studies, showing their ability to provide us new knowledge about the heuristic. The practical motivation behind this work is the optimization context defined by the design of wireless telecommunications networks. Such a peculiar context poses severe constraints to the analysis of algorithms even by traditional experimentation.Les algorithmes constituent la plus efficace base de connaissances conçue par l'homme jusqu'à présent. La NP-completude indique que parmi l'ensemble des problèmes décidables il y en a que nous ne savons pas traiter de manière efficace, c.-à-d. nous ne savons pas concevoir des algorithmes efficaces pour eux. Cependant, la pratique montre que beaucoup d'algorithmes sont quand même efficaces pour résoudre ces problèmes. C'est à dire que l'analyse expérimentale de leur relation entrée/sortie révèle une bien meilleure situation que ce qui peut être déduit d'une analyse mathématique des propriétés de ces algorithmes. Cela signifie également que le processus dynamique induit par l'algorithme (i.e. le processus informatique) dépasse notre capacité d'expression et de communication du savoir que nous incluons dans un tel algorithme. Sans la mise en oeuvre effective de l'algorithme, nous ne serions pas capables de prédire son comportement de manière juste. Le travail de cette thèse concerne de tels processus dynamiques. Plutôt que d'analyser la connaissance que nous introduisons dans un algorithme, nous voulons étudier les mécanismes de ce processus informatique afin de déduire la connaissance qu'il contient. C'est ce que nous appelons "études exploratoires" car nous voulons acquérir de nouvelles connaissances sur le traitement du problème fourni par notre algorithme. Nous abordons ce sujet dans une perspective d'analyse de données. Notre méthode consiste à analyser le processus informatique dans sa recherche de tendances statistiques tangibles quant a sa mécanique. Afin de garantir l'aspect tangible de ces tendances, il est essentiel qu'elles rendent compte d'un processus informatique pertinent, c'est à dire reposant sur un grand nombre de données. L'analyse des données est donc un point crucial dans ce type d'études. Dans ce travail, nous présentons une application systématique des techniques statistiques d'analyse descriptive afin de mettre en évidence statistiquement les mécanismes des processus informatiques induits par les algorithmes heuristiques pour les problèmes d'optimisation difficiles. Nous présentons une étude de cas sur une heuristique à l'état de l'art sur le problème du voyageur de commerce dans laquelle nous interprétons et discutons les tendances mises en évidence par notre étude. La motivation pratique sous jacente à ce travail est l'optimisation dans le cadre du design des réseaux radio mobiles. Un contexte si particulier pose de lourdes contraintes quant a l'analyse des algorithmes, même par des expérimentations traditionnelles.NICE-BU Sciences (060882101) / SudocSudocFranceF