<p>De nos jours, il est peu de processus ou de tâches qui ne requièrent pas l'optimisation d'une quantité :diminuer le temps de livraison, diminuer l'espace utilisé, réduire les efforts de développement, C'est donc sans surprise que la recherche en optimisation soit l'un des domaines les plus actifs des sciences des technologies de l'information. En optimisation combinatoire, les métaheuristiques sont à compter parmi le fleuron des techniques algorithmiques. Mais ce succès est encore au prix d'une quantité significative de temps de conception et développement. Ne serait-il pas possible d'aller encore plus loin ?D'automatiser la préparation des métaheuristiques ?En particulier dans des conditions telles le manque de temps, l'ignorance de techniques spécialisées ou encore la mauvaise compréhension du problème traité ?C'est ce à quoi nous répondons dans la présente thèse au moyen d'une approche de méta-modélisation de la recherche :l'heuristique de la Gestalt.</p><p><p><p>Considérant la représentation du problème comme un levier que l'on peut activer sous le processus de recherche mené par une métaheuristique, la thèse suggère la construction d'une abstraction de cette représentation capable d'assister la métaheuristique à trouver de bonnes solutions en contraignant sa recherche. Cette approche, inspirée de la psychologie de la Gestalt, nous l'appelons l'heuristique de la Gestalt. Son fonctionnement repose principalement sur l'agrégation des variables de la représentation. Cette agrégation donne lieu à une abstraction structurelle, mais également fonctionnelle en ce sens que les opérateurs de la métaheuristique doivent désormais respecter l'intégrité des agrégats définis.</p><p><p><p>Après avoir établi le contexte de la dissertation, nous discutons de la transposition de la psychologie de la Gestalt dans le cadre de l'optimisation combinatoire et des métaheuristiques. S'ensuit la formalisation de l'heuristique de la Gestalt et la description de sa réalisation. Finalement, une série d'études expérimentales sont menées pour éprouver le concept avancé et valider l'implémentation basée sur les algorithmes évolutionnistes que nous proposons. En conclusion, nous affirmons que l'implémentation de l'heuristique de la Gestalt basée, entre autres, sur un algorithme génétique de groupement est capable d'assister positivement des algorithmes génétiques lorsque les instances de problèmes traitées possèdent une structure riche et complexe, que leur taille est importante, que l'on est tôt dans le processus d'optimisation et que l'algorithme génétique n'est pas paramétré spécifiquement.</p> / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

We present a set of approximation results for several covering problems in dense graphs. These results show that for several problems, classical algorithms with constant approximation ratios can be analyzed in a finer way, and provide better constant approximation ratios under some density constraints. In particular, we show that the maximal matching heuristic approximates VERTEX COVER (VC) and MINIMUM MAXIMAL MATCHING (MMM) with a constant ratio strictly smaller than 2 when the proportion of edges present in the graph (weak density) is at least 3/4, or when the normalized minimum degree (strong density) is at least 1/2. We also show that this result can be improved by a greedy algorithm which provides a constant ratio smaller than 2 when the weak density is at least 1/2. We also provide tight families of graphs for all these approximation ratios. We then looked at several algorithms from the literature for VC and SET COVER (SC). We present a unified and critical approach to the Karpinski/Zelikovsky, Imamura/Iwama and Bar-Yehuda/Kehat algorithms, identifying the general the general scheme underlying these algorithms.<p>Finally, we look at the CONNECTED VERTEX COVER (CVC) problem,for which we proposed new approximation results in dense graphs. We first analyze Carla Savage's algorithm, then a new variant of the Karpinski-Zelikovsky algorithm. Our results show that these algorithms provide the same approximation ratios for CVC as the maximal matching heuristic and the Karpinski-Zelikovsky algorithm did for VC. We provide tight examples for the ratios guaranteed by both algorithms. We also introduce a new invariant, the "price of connectivity of VC", defined as the ratio between the optimal solutions of CVC and VC, and showed a nearly tight upper bound on its value as a function of the weak density. Our last chapter discusses software aspects, and presents the use of the GRAPHEDRON software in the framework of approximation algorithms, as well as our contributions to the development of this system.<p><p>/<p><p>Nous présentons un ensemble de résultats d'approximation pour plusieurs problèmes de couverture dans les graphes denses. Ces résultats montrent que pour plusieurs problèmes, des algorithmes classiques à facteur d'approximation constant peuvent être analysés de manière plus fine, et garantissent de meilleurs facteurs d'aproximation constants sous certaines contraintes de densité. Nous montrons en particulier que l'heuristique du matching maximal approxime les problèmes VERTEX COVER (VC) et MINIMUM MAXIMAL MATCHING (MMM) avec un facteur constant inférieur à 2 quand la proportion d'arêtes présentes dans le graphe (densité faible) est supérieure à 3/4 ou quand le degré minimum normalisé (densité forte) est supérieur à 1/2. Nous montrons également que ce résultat peut être amélioré par un algorithme de type GREEDY, qui fournit un facteur constant inférieur à 2 pour des densités faibles supérieures à 1/2. Nous donnons également des familles de graphes extrémaux pour nos facteurs d'approximation. Nous nous somme ensuite intéressés à plusieurs algorithmes de la littérature pour les problèmes VC et SET COVER (SC). Nous avons présenté une approche unifiée et critique des algorithmes de Karpinski-Zelikovsky, Imamura-Iwama, et Bar-Yehuda-Kehat, identifiant un schéma général dans lequel s'intègrent ces algorithmes.<p>Nous nous sommes finalement intéressés au problème CONNECTED VERTEX COVER (CVC), pour lequel nous avons proposé de nouveaux résultats d'approximation dans les graphes denses, au travers de l'algorithme de Carla Savage d'une part, et d'une nouvelle variante de l'algorithme de Karpinski-Zelikovsky d'autre part. Ces résultats montrent que nous pouvons obtenir pour CVC les mêmes facteurs d'approximation que ceux obtenus pour VC à l'aide de l'heuristique du matching maximal et de l'algorithme de Karpinski-Zelikovsky. Nous montrons également des familles de graphes extrémaux pour les ratios garantis par ces deux algorithmes. Nous avons également étudié un nouvel invariant, le coût de connectivité de VC, défini comme le rapport entre les solutions optimales de CVC et de VC, et montré une borne supérieure sur sa valeur en fonction de la densité faible. Notre dernier chapitre discute d'aspects logiciels, et présente l'utilisation du logiciel GRAPHEDRON dans le cadre des algorithmes d'approximation, ainsi que nos contributions au développement du logiciel. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Notre thèse est consacrée à l’étude des méthodes de rangements multicritères dans le cadre de la problématique de tri.<p> <p>Dans un problème de tri une personne, appelée décideur, désire assigner un objet, appelé action, à des catégories prédéfinies. Des problèmes de tri surgissent régulièrement dans la vie de tous les jours. Par exemple, un médecin ausculte son patient et sur base des symptômes observés, il assigne son patient à une catégorie de pathologies. Ainsi, le médecin peut prescrire un traitement approprié. Par ailleurs, on catégorise les cyclones tropicaux en fonction de leur vitesse, pression superficielle et de la hauteur de marée. En fonction de la catégorie du cyclone, des dégâts éventuels peuvent être prédits et des mesures de protection adéquates devront être prises. <p> <p>Dans un problème de tri, un décideur regroupe ainsi les actions qu’il considère similaires, à des fins descriptives, organisationnelles ou préventives. Nous supposerons en outre que le décideur exprime une relation de préférence entre les classes préalablement définies.<p> <p>D’autre part, les méthodes de rangement permettent de ranger les actions de la meilleure à la moins bonne. Nul étudiant ne peut nier l’existence des " rankings " d’universités. Une société ordonne les candidats à l’issue d’un entretien d’embauche. Une société désire par ailleurs établir des partenariats avec les fournisseurs les plus performants. Nous sommes tous confrontés à cette tâche délicate de ranger les actions de la meilleure à la moins bonne. Les méthodes d’aide à la décision proposent des techniques permettant à un décideur d’obtenir un rangement d’actions.<p> <p>L’objectif de cette thèse est d’étudier la possibilité de résoudre des problèmes de tri à l’aide de méthodes de rangement. L’approche adoptée est de ranger une action particulière par rapport à des normes ou profils définissant les catégories. L’assignation de l’action sera dès lors basée sur sa position dans ce rangement particulier.<p> <p>Quelles sont les hypothèses nécessaires pour un tel modèle ?Ces méthodes présentent-elles un biais ou ont-elles d’autres avantages par rapport aux méthodes de tri existantes? Est-il préférable de modéliser les catégories à l’aide de critères même si celles-ci ne présentent pas de relation de préférence ?Dans cette thèse nous donnerons des premiers éléments de réponse en développant de nouvelles méthodes de tri basées sur des méthodes de rangement existantes.<p> <p><p> / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

Un des buts principaux de la biologie évolutive et de la médecine moléculaire consiste à reconstruire les relations phylogénétiques entre organismes à partir de leurs séquences moléculaires. En littérature, cette question est connue sous le nom d’inférence phylogénétique et a d'importantes applications dans la recherche médicale et pharmaceutique, ainsi que dans l’immunologie, l’épidémiologie, et la dynamique des populations. L’accumulation récente de données de séquences d’ADN dans les bases de données publiques, ainsi que la facilité relative avec laquelle des données nouvelles peuvent être obtenues, rend l’inférence phylogénétique particulièrement difficile (l'inférence phylogénétique est un problème NP-Hard sous tous les critères d’optimalité connus), de telle manière que des nouveaux critères et des algorithmes efficaces doivent être développés. Cette thèse a pour but: (i) d’analyser les limites mathématiques et biologiques des critères utilisés en inférence phylogénétique, (ii) de développer de nouveaux algorithmes efficaces permettant d’analyser de plus grands jeux de données. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

<p>La tolérance et la gestion des fautes dans les grilles de données/calcul est d’une importance capitale. En effet, comme dans tout autre système distribué, les composants d’une grille sont susceptibles de tomber en panne à tout moment. Mais le risque de panne croît avec la taille du système, et est donc plus exacerbé dans un système de grille. En plus, tout en essayant de mettre à profit les ressources offertes par la grille, les applications tournant sur celle-ci sont de plus en plus complexes (ex. impliquent des interactions complexes, prennent des jours d’exécution), ce qui les rend plus vulnérables aux fautes. Le plus difficile dans la gestion des fautes dans une grille, c’est qu’il est difficile de savoir si une faute qui survient sur une entité de la grille est induite malicieusement ou accidentellement.<p><p>Dans notre travail de thèse, nous utilisons le terme faute, au sens large, pour faire référence à tout étant inattendu qui survient sur tout composant de la grille. Certains de ces états provoquent des comportements aussi inattendus et perceptibles au niveau de la grille tandis que d’autres passent inaperçues. De plus, certaines de ces fautes sont le résultat d’une action malveillante alors que d’autres surviennent accidentellement ou instantanément. Dans ce travail de thèse, nous avons traité le cas de ces fautes induites malicieusement, et qui généralement passent inaperçues. Nous avons considéré en particulier le problème de la confidentialité et de l’intégrité des données stockées à long-terme sur la grille.<p><p>L’étude de la confidentialité des données a été faite en deux temps dont la première partie concerne la confidentialité des données actives. Dans cette partie, nous avons considéré une application liée à la recherche des similitudes d’une séquence d’ADN dans une base de données contenant des séquences d’ADN et stockée sur la grille. Pour cela, nous avons proposé une méthode qui permet d’effectuer la comparaison sur un composant distant, mais tout en gardant confidentielle la séquence qui fait l’objet de la comparaison. <p>Concernant les données passives, nous avons proposé une méthode de partage des données confidentielles et chiffrés sur la grille.<p> <p>En rapport avec l’intégrité des données, nous avons considéré le cas des données anonymes dans le cadre de l’intégrité des données passives. Pour les données actives, nous avons considéré le problème de la corruption des jobs exécutés sur la grille. Pour chacune des cas, nous avons proposé des mécanismes permettant de vérifier l’authenticité des données utilisées ou produites par ces applications.<p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

In this work, we present a way to extend Ant Colony Optimization (ACO), so that it can be applied to both continuous and mixed-variable optimization problems. We demonstrate, first, how ACO may be extended to continuous domains. We describe the algorithm proposed, discuss the different design decisions made, and we position it among other metaheuristics.<p>Following this, we present the results of numerous simulations and testing. We compare the results obtained by the proposed algorithm on typical benchmark problems with those obtained by other methods used for tackling continuous optimization problems in the literature. Finally, we investigate how our algorithm performs on a real-world problem coming from the medical field—we use our algorithm for training neural network used for pattern classification in disease recognition.<p>Following an extensive analysis of the performance of ACO extended to continuous domains, we present how it may be further adapted to handle both continuous and discrete variables simultaneously. We thus introduce the first native mixed-variable version of an ACO algorithm. Then, we analyze and compare the performance of both continuous and mixed-variable<p>ACO algorithms on different benchmark problems from the literature. Through the research performed, we gain some insight into the relationship between the formulation of mixed-variable problems, and the best methods to tackle them. Furthermore, we demonstrate that the performance of ACO on various real-world mixed-variable optimization problems coming from the mechanical engineering field is comparable to the state of the art. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

A reactive control system is a computer system reacting to certain stimuli emitted by its environment in order to maintain it in a desired state. Distributed reactive control systems are generally composed of several processes, running in parallel on one or more computers, communicating with one another to perform the required control task. By their very nature, distributed reactive control systems are hard to design. Their distributed nature and/or the communication scheme used can introduce subtle unforeseen behaviours. When dealing with critical applications, such as plane control systems, or traffic light control systems, those unintended behaviours can have disastrous consequences. It is therefore essential, for the designer, to ensure that this does not happen. For that purpose, rigorous and systematic techniques can (and should) be applied as early as possible in the development process. In that spirit, this work aims at providing the designer with the necessary tools in order to facilitate the development and validation of such distributed reactive control systems. In particular, we show how using a dedicated language called dSL (Distributed Supervision language) can be used to ease the development process. We also study how validations techniques such as model-checking and testing can be applied in this context. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Un stable (ou ensemble indépendant) est un ensemble de sommets qui sont deux à deux non adjacents. De nombreux résultats classiques en optimisation combinatoire portent sur le nombre de stabilité (défini comme la plus grande taille d'un stable), et les stables se classent certainement parmi les structures les plus simples et fondamentales en théorie des graphes.<p><p>La thèse est divisée en deux parties, toutes deux liées à la notion de stables dans un graphe. Dans la première partie, nous étudions un problème de coloration de graphes, c'est à dire de partition en stables, où le but est de minimiser l'entropie de la partition. C'est une variante du problème classique de minimiser le nombre de couleurs utilisées. Nous considérons aussi une généralisation du problème aux couvertures d'ensembles. Ces deux problèmes sont appelés respectivement minimum entropy coloring et minimum entropy set cover, et sont motivés par diverses applications en théorie de l'information et en bioinformatique. Nous obtenons entre autres une caractérisation précise de la complexité de minimum entropy set cover :le problème peut être approximé à une constante lg e (environ 1.44) près, et il est NP-difficile de faire strictement mieux. Des résultats analogues sont prouvés concernant la complexité de minimum entropy coloring.<p><p>Dans la deuxième partie de la thèse, nous considérons les graphes dont le nombre de stabilité augmente dès qu'une arête est enlevée. Ces graphes sont dit être "alpha-critiques", et jouent un rôle important dans de nombreux domaines, comme la théorie extrémale des graphes ou la combinatoire polyédrique. Nous revisitons d'une part la théorie des graphes alpha-critiques, donnant à cette occasion de nouvelles démonstrations plus simples pour certains théorèmes centraux. D'autre part, nous étudions certaines facettes du polytope des ordres totaux qui peuvent être vues comme une généralisation de la notion de graphe alpha-critique. Nous étendons de nombreux résultats de la théorie des graphes alpha-critiques à cette famille de facettes.<p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

<P align="justify">Model-checking is an automated technique which aims at verifying properties of computer systems. A model-checker is fed with a model of the system (which capture all its possible behaviors) and a property to verify on this model. Both are given by a convenient mathematical formalism like, for instance, a transition system for the model and a temporal logic formula for the property.</P><p><p><P align="justify">For several reasons (the model-checking is undecidable for this class of model or the model-checking needs too much resources for this model) model-checking may not be applicable. For safety properties (which basically says "nothing bad happen"), a solution to this problem uses a simpler model for which model-checkers might terminate without too much resources. This simpler model, called the abstract model, over-approximates the behaviors of the concrete model. However the abstract model might be too imprecise. In fact, if the property is true on the abstract model, the same holds on the concrete. On the contrary, when the abstract model violates the property, either the violation is reproducible on the concrete model and so we found an error; or it is not reproducible and so the model-checker is said to be inconclusive. Inconclusiveness stems from the over-approximation of the concrete model by the abstract model. So a precise model yields the model-checker to conclude, but precision comes generally with an increased computational cost.</P><p><p><P align="justify">Recently, a lot of work has been done to define abstraction refinement algorithms. Those algorithms compute automatically abstract models which are refined as long as the model-checker is inconclusive. In the thesis, we give a new abstraction refinement algorithm which applies for safety properties. We compare our algorithm with previous attempts to build abstract models automatically and show, using formal proofs that our approach has several advantages. We also give several extensions of our algorithm which allow to integrate existing techniques used in model-checking such as acceleration techniques.</P><p><p><P align="justify">Following a rigorous methodology we then instantiate our algorithm for a variety of models ranging from finite state transition systems to infinite state transition systems. For each of those models we prove the instantiated algorithm terminates and provide encouraging preliminary experimental results.</P><p><br><p><br><p><P align="justify">Le model-checking est une technique automatisée qui vise à vérifier des propriétés sur des systèmes informatiques. Les données passées au model-checker sont le modèle du système (qui en capture tous les comportements possibles) et la propriété à vérifier. Les deux sont donnés dans un formalisme mathématique adéquat tel qu'un système de transition pour le modèle et une formule de logique temporelle pour la propriété.</P><p><p><P align="justify">Pour diverses raisons (le model-checking est indécidable pour cette classe de modèle ou le model-checking nécessite trop de ressources pour ce modèle) le model-checking peut être inapplicable. Pour des propriétés de sûreté (qui disent dans l'ensemble "il ne se produit rien d'incorrect"), une solution à ce problème recourt à un modèle simplifié pour lequel le model-checker peut terminer sans trop de ressources. Ce modèle simplifié, appelé modèle abstrait, surapproxime les comportements du modèle concret. Le modèle abstrait peut cependant être trop imprécis. En effet, si la propriété est vraie sur le modèle abstrait alors elle l'est aussi sur le modèle concret. En revanche, lorsque le modèle abstrait enfreint la propriété :soit l'infraction peut être reproduite sur le modèle concret et alors nous avons trouvé une erreur ;soit l'infraction ne peut être reproduite et dans ce cas le model-checker est dit non conclusif. Ceci provient de la surapproximation du modèle concret faite par le modèle abstrait. Un modèle précis aboutit donc à un model-checking conclusif mais son coût augmente avec sa précision.</P><p><P align="justify">Récemment, différents algorithmes d'abstraction raffinement ont été proposés. Ces algorithmes calculent automatiquement des modèles abstraits qui sont progressivement raffinés jusqu'à ce que leur model-checking soit conclusif. Dans la thèse, nous définissons un nouvel algorithme d'abstraction raffinement pour les propriétés de sûreté. Nous comparons notre algorithme avec les algorithmes d'abstraction raffinement antérieurs. A l'aide de preuves formelles, nous montrons les avantages de notre approche. Par ailleurs, nous définissons des extensions de l'algorithme qui intègrent d'autres techniques utilisées en model-checking comme les techniques d'accélérations.</P><p><P align="justify">Suivant une méthodologie rigoureuse, nous instancions ensuite notre algorithme pour une variété de modèles allant des systèmes de transitions finis aux systèmes de transitions infinis. Pour chacun des modèles nous établissons la terminaison de l'algorithme instancié et donnons des résultats expérimentaux préliminaires encourageants.</P><p><p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

The all-over trend for an universal access and ubiquitous access to the Internet is driving a revolution in our societies. In order to support this era of nomadic applications, new flexible network architectures have emerged. They are referred to as “wireless ad-hoc networks.” <p><p>Since human-operated devices will more likely be used indoor, it leads to many issues related to the strength of the fading in this environment. Recently, it has been suggested that a possible interaction might exist between various parameters of the ad-hoc networks and, more precisely, between the propagation model and the routing protocol. <p><p>To address this question, we present in this dissertation a cross-layer perspective of the analysis of these indoor ad-hoc networks. Our reasoning is made of four stages. First, the cross-layer interactions are analyzed by the means of multivariate statistical techniques. Since a cross-layering between the physical layer and the routing protocol has been proven to be significant, we further investigate the possible development a physical layer-constrained routing algorithm. <p><p>Second, fundamental equations governing the wireless telecommunications systems are developed in order to provide insightful informations on how a reliable routing strategy should be implemented in a strongly-faded environment. After that, and in order to allow a better spatial reuse, the routing protocol we propose is further enhanced by the adjonction of a power control algorithm. This last feature is extensively analyzed and a closed-form expression of the link probability of outage in presence of non-homogeneous transmission powers is given. Numerous simulations corroborate the applicability and the performance of the derived protocol. Also, we evaluate the gain, in terms of radio channel ressources, that has been achieved by the means of the power control algorithm. <p><p>Third, an architecture for the interconnection with a cellular network is investigated. A closed-form expression of the relaying stability of a node is given. This equation expresses the minimal requirement that a relaying node from the ad-hoc network must fullfil in order to bridge properly the connections to the base-station. <p><p>Finally, a real-life implementation is provided as a validation of the applicability of this novel ad-hoc routing protocol. It is concluded that, both from the performance and the spatial re-use point-of-views, it can be taken advantage from the cross-layering between the physical and the routing layers to positively enhance the networking architectures deployed in an indoor environment. / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished