Comparison of classification ability of hyperball algorithms to neural network and k-nearest neighbour algorithms

The main focus of this thesis is to evaluate and compare Hyperbalilearning algorithm (HBL) to other learning algorithms. In this work HBL is compared to feed forward artificial neural networks using back propagation learning, K-nearest neighbor and 103 algorithms. In order to evaluate the similarity of these algorithms, we carried out three experiments using nine benchmark data sets from UCI machine learning repository. The first experiment compares HBL to other algorithms when sample size of dataset is changing. The second experiment compares HBL to other algorithms when dimensionality of data changes. The last experiment compares HBL to other algorithms according to the level of agreement to data target values. Our observations in general showed, considering classification accuracy as a measure, HBL is performing as good as most ANn variants. Additionally, we also deduced that HBL.:s classification accuracy outperforms 103's and K-nearest neighbour's for the selected data sets.

Multi-Objective Genetic Algorithms for the Single Allocation Hub Location Problem

Hub Location Problems play vital economic roles in transportation and telecommunication networks where goods or people must be efficiently transferred from an origin to a destination point whilst direct origin-destination links are impractical. This work investigates the single allocation hub location problem, and proposes a genetic algorithm (GA) approach for it. The effectiveness of using a single-objective criterion measure for the problem is first explored. Next, a multi-objective GA employing various fitness evaluation strategies such as Pareto ranking, sum of ranks, and weighted sum strategies is presented. The effectiveness of the multi-objective GA is shown by comparison with an Integer Programming strategy, the only other multi-objective approach found in the literature for this problem. Lastly, two new crossover operators are proposed and an empirical study is done using small to large problem instances of the Civil Aeronautics Board (CAB) and Australian Post (AP) data sets.

Properties and Algorithms of the KCube Graphs

The KCube interconnection topology was rst introduced in 2010. The KCube graph is a compound graph of a Kautz digraph and hypercubes. Compared with the at- tractive Kautz digraph and well known hypercube graph, the KCube graph could accommodate as many nodes as possible for a given indegree (and outdegree) and the diameter of interconnection networks. However, there are few algorithms designed for the KCube graph. In this thesis, we will concentrate on nding graph theoretical properties of the KCube graph and designing parallel algorithms that run on this network. We will explore several topological properties, such as bipartiteness, Hamiltonianicity, and symmetry property. These properties for the KCube graph are very useful to develop efficient algorithms on this network. We will then study the KCube network from the algorithmic point of view, and will give an improved routing algorithm. In addition, we will present two optimal broadcasting algorithms. They are fundamental algorithms to many applications. A literature review of the state of the art network designs in relation to the KCube network as well as some open problems in this field will also be given.

Characterizing Dynamic Optimization Benchmarks for the Comparison of Multi-Modal Tracking Algorithms

Population-based metaheuristics, such as particle swarm optimization (PSO), have been employed to solve many real-world optimization problems. Although it is of- ten sufficient to find a single solution to these problems, there does exist those cases where identifying multiple, diverse solutions can be beneficial or even required. Some of these problems are further complicated by a change in their objective function over time. This type of optimization is referred to as dynamic, multi-modal optimization. Algorithms which exploit multiple optima in a search space are identified as niching algorithms. Although numerous dynamic, niching algorithms have been developed, their performance is often measured solely on their ability to find a single, global optimum. Furthermore, the comparisons often use synthetic benchmarks whose landscape characteristics are generally limited and unknown. This thesis provides a landscape analysis of the dynamic benchmark functions commonly developed for multi-modal optimization. The benchmark analysis results reveal that the mechanisms responsible for dynamism in the current dynamic bench- marks do not significantly affect landscape features, thus suggesting a lack of representation for problems whose landscape features vary over time. This analysis is used in a comparison of current niching algorithms to identify the effects that specific landscape features have on niching performance. Two performance metrics are proposed to measure both the scalability and accuracy of the niching algorithms. The algorithm comparison results demonstrate the algorithms best suited for a variety of dynamic environments. This comparison also examines each of the algorithms in terms of their niching behaviours and analyzing the range and trade-off between scalability and accuracy when tuning the algorithms respective parameters. These results contribute to the understanding of current niching techniques as well as the problem features that ultimately dictate their success.

Properties and Algorithms of the KCube Interconnection Networks

The KCube interconnection network was first introduced in 2010 in order to exploit the good characteristics of two well-known interconnection networks, the hypercube and the Kautz graph. KCube links up multiple processors in a communication network with high density for a fixed degree. Since the KCube network is newly proposed, much study is required to demonstrate its potential properties and algorithms that can be designed to solve parallel computation problems. In this thesis we introduce a new methodology to construct the KCube graph. Also, with regard to this new approach, we will prove its Hamiltonicity in the general KC(m; k). Moreover, we will find its connectivity followed by an optimal broadcasting scheme in which a source node containing a message is to communicate it with all other processors. In addition to KCube networks, we have studied a version of the routing problem in the traditional hypercube, investigating this problem: whether there exists a shortest path in a Qn between two nodes 0n and 1n, when the network is experiencing failed components. We first conditionally discuss this problem when there is a constraint on the number of faulty nodes, and subsequently introduce an algorithm to tackle the problem without restrictions on the number of nodes.

A Scalability Study and New Algorithms for Large-Scale Many-Objective Optimization

Many real-world optimization problems contain multiple (often conflicting) goals to be optimized concurrently, commonly referred to as multi-objective problems (MOPs). Over the past few decades, a plethora of multi-objective algorithms have been proposed, often tested on MOPs possessing two or three objectives. Unfortunately, when tasked with solving MOPs with four or more objectives, referred to as many-objective problems (MaOPs), a large majority of optimizers experience significant performance degradation. The downfall of these optimizers is that simultaneously maintaining a well-spread set of solutions along with appropriate selection pressure to converge becomes difficult as the number of objectives increase. This difficulty is further compounded for large-scale MaOPs, i.e., MaOPs possessing large amounts of decision variables. In this thesis, we explore the challenges of many-objective optimization and propose three new promising algorithms designed to efficiently solve MaOPs. Experimental results demonstrate the proposed optimizers to perform very well, often outperforming state-of-the-art many-objective algorithms.

Models, algorithms, and heuristics for multiobjetive commercial territory design.

Tesis (Doctor en Ingeniería de Sistemas) UANL, 2010.

Models and algorithms for transit network planning.

Tesis (Doctor en Ingeniería con Especialidad en Ingeniería de Sistemas) UANL, 2012.

Évaluation et contrôle de l'irrégularité de la prise médicamenteuse : proposition et développement de stratégies rationnelles fondées sur une démarche de modélisations pharmacocinétiques et pharmacodynamiques

L'hétérogénéité de réponses dans un groupe de patients soumis à un même régime thérapeutique doit être réduite au cours d'un traitement ou d'un essai clinique. Deux approches sont habituellement utilisées pour atteindre cet objectif. L'une vise essentiellement à construire une observance active. Cette approche se veut interactive et fondée sur l'échange ``médecin-patient '', ``pharmacien-patient'' ou ``vétérinaire-éleveurs''. L'autre plutôt passive et basée sur les caractéristiques du médicament, vise à contrôler en amont cette irrégularité. L'objectif principal de cette thèse était de développer de nouvelles stratégies d'évaluation et de contrôle de l'impact de l'irrégularité de la prise du médicament sur l'issue thérapeutique. Plus spécifiquement, le premier volet de cette recherche consistait à proposer des algorithmes mathématiques permettant d'estimer efficacement l'effet des médicaments dans un contexte de variabilité interindividuelle de profils pharmacocinétiques (PK). Cette nouvelle méthode est fondée sur l'utilisation concommitante de données \textit{in vitro} et \textit{in vivo}. Il s'agit de quantifier l'efficience ( c-à-dire efficacité plus fluctuation de concentrations \textit{in vivo}) de chaque profil PK en incorporant dans les modèles actuels d'estimation de l'efficacité \textit{in vivo}, la fonction qui relie la concentration du médicament de façon \textit{in vitro} à l'effet pharmacodynamique. Comparativement aux approches traditionnelles, cette combinaison de fonction capte de manière explicite la fluctuation des concentrations plasmatiques \textit{in vivo} due à la fonction dynamique de prise médicamenteuse. De plus, elle soulève, à travers quelques exemples, des questions sur la pertinence de l'utilisation des indices statiques traditionnels ($C_{max}$, $AUC$, etc.) d'efficacité comme outil de contrôle de l'antibiorésistance. Le deuxième volet de ce travail de doctorat était d'estimer les meilleurs temps d'échantillonnage sanguin dans une thérapie collective initiée chez les porcs. Pour ce faire, nous avons développé un modèle du comportement alimentaire collectif qui a été par la suite couplé à un modèle classique PK. À l'aide de ce modèle combiné, il a été possible de générer un profil PK typique à chaque stratégie alimentaire particulière. Les données ainsi générées, ont été utilisées pour estimer les temps d'échantillonnage appropriés afin de réduire les incertitudes dues à l'irrégularité de la prise médicamenteuse dans l'estimation des paramètres PK et PD . Parmi les algorithmes proposés à cet effet, la méthode des médianes semble donner des temps d'échantillonnage convenables à la fois pour l'employé et pour les animaux. Enfin, le dernier volet du projet de recherche a consisté à proposer une approche rationnelle de caractérisation et de classification des médicaments selon leur capacité à tolérer des oublis sporadiques. Méthodologiquement, nous avons, à travers une analyse globale de sensibilité, quantifié la corrélation entre les paramètres PK/PD d'un médicament et l'effet d'irrégularité de la prise médicamenteuse. Cette approche a consisté à évaluer de façon concomitante l'influence de tous les paramètres PK/PD et à prendre en compte, par la même occasion, les relations complexes pouvant exister entre ces différents paramètres. Cette étude a été réalisée pour les inhibiteurs calciques qui sont des antihypertenseurs agissant selon un modèle indirect d'effet. En prenant en compte les valeurs des corrélations ainsi calculées, nous avons estimé et proposé un indice comparatif propre à chaque médicament. Cet indice est apte à caractériser et à classer les médicaments agissant par un même mécanisme pharmacodynamique en terme d'indulgence à des oublis de prises médicamenteuses. Il a été appliqué à quatre inhibiteurs calciques. Les résultats obtenus étaient en accord avec les données expérimentales, traduisant ainsi la pertinence et la robustesse de cette nouvelle approche. Les stratégies développées dans ce projet de doctorat sont essentiellement fondées sur l'analyse des relations complexes entre l'histoire de la prise médicamenteuse, la pharmacocinétique et la pharmacodynamique. De cette analyse, elles sont capables d'évaluer et de contrôler l'impact de l'irrégularité de la prise médicamenteuse avec une précision acceptable. De façon générale, les algorithmes qui sous-tendent ces démarches constitueront sans aucun doute, des outils efficients dans le suivi et le traitement des patients. En outre, ils contribueront à contrôler les effets néfastes de la non-observance au traitement par la mise au point de médicaments indulgents aux oublis

Models and algorithms for the capacitated location-routing problem

Le problème de localisation-routage avec capacités (PLRC) apparaît comme un problème clé dans la conception de réseaux de distribution de marchandises. Il généralisele problème de localisation avec capacités (PLC) ainsi que le problème de tournées de véhicules à multiples dépôts (PTVMD), le premier en ajoutant des décisions liées au routage et le deuxième en ajoutant des décisions liées à la localisation des dépôts. Dans cette thèse on dévelope des outils pour résoudre le PLRC à l’aide de la programmation mathématique. Dans le chapitre 3, on introduit trois nouveaux modèles pour le PLRC basés sur des flots de véhicules et des flots de commodités, et on montre comment ceux-ci dominent, en termes de la qualité de la borne inférieure, la formulation originale à deux indices [19]. Des nouvelles inégalités valides ont été dévelopées et ajoutées aux modèles, de même que des inégalités connues. De nouveaux algorithmes de séparation ont aussi été dévelopés qui dans la plupart de cas généralisent ceux trouvés dans la litterature. Les résultats numériques montrent que ces modèles de flot sont en fait utiles pour résoudre des instances de petite à moyenne taille. Dans le chapitre 4, on présente une nouvelle méthode de génération de colonnes basée sur une formulation de partition d’ensemble. Le sous-problème consiste en un problème de plus court chemin avec capacités (PCCC). En particulier, on utilise une relaxation de ce problème dans laquelle il est possible de produire des routes avec des cycles de longueur trois ou plus. Ceci est complété par des nouvelles coupes qui permettent de réduire encore davantage le saut d’intégralité en même temps que de défavoriser l’apparition de cycles dans les routes. Ces résultats suggèrent que cette méthode fournit la meilleure méthode exacte pour le PLRC. Dans le chapitre 5, on introduit une nouvelle méthode heuristique pour le PLRC. Premièrement, on démarre une méthode randomisée de type GRASP pour trouver un premier ensemble de solutions de bonne qualité. Les solutions de cet ensemble sont alors combinées de façon à les améliorer. Finalement, on démarre une méthode de type détruir et réparer basée sur la résolution d’un nouveau modèle de localisation et réaffectation qui généralise le problème de réaffectaction [48].

Clustering algorithms and shape factor methods to discriminate among small GTPase phenotypes using DIC image analysis.

Naïvement perçu, le processus d’évolution est une succession d’événements de duplication et de mutations graduelles dans le génome qui mènent à des changements dans les fonctions et les interactions du protéome. La famille des hydrolases de guanosine triphosphate (GTPases) similaire à Ras constitue un bon modèle de travail afin de comprendre ce phénomène fondamental, car cette famille de protéines contient un nombre limité d’éléments qui diffèrent en fonctionnalité et en interactions. Globalement, nous désirons comprendre comment les mutations singulières au niveau des GTPases affectent la morphologie des cellules ainsi que leur degré d’impact sur les populations asynchrones. Mon travail de maîtrise vise à classifier de manière significative différents phénotypes de la levure Saccaromyces cerevisiae via l’analyse de plusieurs critères morphologiques de souches exprimant des GTPases mutées et natives. Notre approche à base de microscopie et d’analyses bioinformatique des images DIC (microscopie d’interférence différentielle de contraste) permet de distinguer les phénotypes propres aux cellules natives et aux mutants. L’emploi de cette méthode a permis une détection automatisée et une caractérisation des phénotypes mutants associés à la sur-expression de GTPases constitutivement actives. Les mutants de GTPases constitutivement actifs Cdc42 Q61L, Rho5 Q91H, Ras1 Q68L et Rsr1 G12V ont été analysés avec succès. En effet, l’implémentation de différents algorithmes de partitionnement, permet d’analyser des données qui combinent les mesures morphologiques de population native et mutantes. Nos résultats démontrent que l’algorithme Fuzzy C-Means performe un partitionnement efficace des cellules natives ou mutantes, où les différents types de cellules sont classifiés en fonction de plusieurs facteurs de formes cellulaires obtenus à partir des images DIC. Cette analyse démontre que les mutations Cdc42 Q61L, Rho5 Q91H, Ras1 Q68L et Rsr1 G12V induisent respectivement des phénotypes amorphe, allongé, rond et large qui sont représentés par des vecteurs de facteurs de forme distincts. Ces distinctions sont observées avec différentes proportions (morphologie mutante / morphologie native) dans les populations de mutants. Le développement de nouvelles méthodes automatisées d’analyse morphologique des cellules natives et mutantes s’avère extrêmement utile pour l’étude de la famille des GTPases ainsi que des résidus spécifiques qui dictent leurs fonctions et réseau d’interaction. Nous pouvons maintenant envisager de produire des mutants de GTPases qui inversent leur fonction en ciblant des résidus divergents. La substitution fonctionnelle est ensuite détectée au niveau morphologique grâce à notre nouvelle stratégie quantitative. Ce type d’analyse peut également être transposé à d’autres familles de protéines et contribuer de manière significative au domaine de la biologie évolutive.

Revisiting optimization algorithms for maximum likelihood estimation

Parmi les méthodes d’estimation de paramètres de loi de probabilité en statistique, le maximum de vraisemblance est une des techniques les plus populaires, comme, sous des conditions l´egères, les estimateurs ainsi produits sont consistants et asymptotiquement efficaces. Les problèmes de maximum de vraisemblance peuvent être traités comme des problèmes de programmation non linéaires, éventuellement non convexe, pour lesquels deux grandes classes de méthodes de résolution sont les techniques de région de confiance et les méthodes de recherche linéaire. En outre, il est possible d’exploiter la structure de ces problèmes pour tenter d’accélerer la convergence de ces méthodes, sous certaines hypothèses. Dans ce travail, nous revisitons certaines approches classiques ou récemment d´eveloppées en optimisation non linéaire, dans le contexte particulier de l’estimation de maximum de vraisemblance. Nous développons également de nouveaux algorithmes pour résoudre ce problème, reconsidérant différentes techniques d’approximation de hessiens, et proposons de nouvelles méthodes de calcul de pas, en particulier dans le cadre des algorithmes de recherche linéaire. Il s’agit notamment d’algorithmes nous permettant de changer d’approximation de hessien et d’adapter la longueur du pas dans une direction de recherche fixée. Finalement, nous évaluons l’efficacité numérique des méthodes proposées dans le cadre de l’estimation de modèles de choix discrets, en particulier les modèles logit mélangés.

Warfarin-induced vitamin K deficiency is associated with cognitive and behavioral perturbations, and alterations in brain sphingolipids in rats

La Vitamine K (VK) est largement reconnue pour son rôle dans la coagulation sanguine toutefois, de plus en plus de travaux indiquent son implication dans la fonction cérébrale. La VK est requise pour l'activation de différentes protéines, par exemple la protéine Gas6, et la ménaquinone-4 (MK-4), le principal vitamère K dans le cerveau, est impliquée dans le métabolisme des sphingolipides. Dans un rapport précédent, nous avons montré qu'un régime alimentaire faible en VK tout au long de la vie était associé à des déficits cognitifs chez des rats âgés. La warfarine sodique est un puissant antagoniste de la VK qui agit en bloquant le cycle de la VK, provoquant un «déficit relatif de VK » au niveau cellulaire. À la lumière du rôle émergent de la VK dans le cerveau, la warfarine pourrait représenter un facteur de risque pour la fonction cérébrale. Ce travail est donc pertinente en raison de la forte proportion d'adultes traîtés à la warfarine sodique. Dans la présente étude, 14 rats mâles Wistar ont été traités avec 14 mg de warfarine/kg /jour (dans l'eau potable) et des injections sous-cutanées de VK (85 mg/kg), 3x/sem, pendant 10 semaines. Quatorze rats témoins ont été traités avec de l'eau normale et injectés avec une solution saline. Les rats ont été soumis à différents tests comportementaux après quoi les niveaux de phylloquinone, MK-4, sphingolipides (cérébroside, sulfatide, sphingomyéline, céramide et gangliosides), et les sous-types de gangliosides (GT1b, GD1a, GM1, GD1b), ont été évalués dans différentes régions du cerveau. Comparativement aux rats du groupe contrôle, les rats traités à la warfarine présentaient des latences plus longues au test de la piscine de Morris (p <0,05) ainsi qu'une hypoactivité et un comportement exploratoire plus faible au test de « l’open field » (p <0,05). Le traitement par warfarine a également entraîné une diminution spectaculaire du niveau de MK-4 dans toutes les régions du cerveau (p <0,001), une altération des concentrations de sphingolipidiques, en particulier dans le cortex frontal et le mésencéphale (p <0,05), et une perte de différences régionales sphingolipidiques, notamment pour les gangliosides. Le traitement par warfarine a été associé à un niveau inférieur de GD1a dans l'hippocampe et un niveau supérieur de GT1b dans le cortex préfrontal et le striatum. En conclusion, la déficience en VK induite par warfarine altère les niveaux de VK et sphingolipides dans le cerveau, avec de potentiels effets néfastes sur les fonctions cérébrales.

Dynamic Facility Location with Modular Capacities : Models, Algorithms and Applications in Forestry

Les décisions de localisation sont souvent soumises à des aspects dynamiques comme des changements dans la demande des clients. Pour y répondre, la solution consiste à considérer une flexibilité accrue concernant l’emplacement et la capacité des installations. Même lorsque la demande est prévisible, trouver le planning optimal pour le déploiement et l'ajustement dynamique des capacités reste un défi. Dans cette thèse, nous nous concentrons sur des problèmes de localisation avec périodes multiples, et permettant l'ajustement dynamique des capacités, en particulier ceux avec des structures de coûts complexes. Nous étudions ces problèmes sous différents points de vue de recherche opérationnelle, en présentant et en comparant plusieurs modèles de programmation linéaire en nombres entiers (PLNE), l'évaluation de leur utilisation dans la pratique et en développant des algorithmes de résolution efficaces. Cette thèse est divisée en quatre parties. Tout d’abord, nous présentons le contexte industriel à l’origine de nos travaux: une compagnie forestière qui a besoin de localiser des campements pour accueillir les travailleurs forestiers. Nous présentons un modèle PLNE permettant la construction de nouveaux campements, l’extension, le déplacement et la fermeture temporaire partielle des campements existants. Ce modèle utilise des contraintes de capacité particulières, ainsi qu’une structure de coût à économie d’échelle sur plusieurs niveaux. L'utilité du modèle est évaluée par deux études de cas. La deuxième partie introduit le problème dynamique de localisation avec des capacités modulaires généralisées. Le modèle généralise plusieurs problèmes dynamiques de localisation et fournit de meilleures bornes de la relaxation linéaire que leurs formulations spécialisées. Le modèle peut résoudre des problèmes de localisation où les coûts pour les changements de capacité sont définis pour toutes les paires de niveaux de capacité, comme c'est le cas dans le problème industriel mentionnée ci-dessus. Il est appliqué à trois cas particuliers: l'expansion et la réduction des capacités, la fermeture temporaire des installations, et la combinaison des deux. Nous démontrons des relations de dominance entre notre formulation et les modèles existants pour les cas particuliers. Des expériences de calcul sur un grand nombre d’instances générées aléatoirement jusqu’à 100 installations et 1000 clients, montrent que notre modèle peut obtenir des solutions optimales plus rapidement que les formulations spécialisées existantes. Compte tenu de la complexité des modèles précédents pour les grandes instances, la troisième partie de la thèse propose des heuristiques lagrangiennes. Basées sur les méthodes du sous-gradient et des faisceaux, elles trouvent des solutions de bonne qualité même pour les instances de grande taille comportant jusqu’à 250 installations et 1000 clients. Nous améliorons ensuite la qualité de la solution obtenue en résolvent un modèle PLNE restreint qui tire parti des informations recueillies lors de la résolution du dual lagrangien. Les résultats des calculs montrent que les heuristiques donnent rapidement des solutions de bonne qualité, même pour les instances où les solveurs génériques ne trouvent pas de solutions réalisables. Finalement, nous adaptons les heuristiques précédentes pour résoudre le problème industriel. Deux relaxations différentes sont proposées et comparées. Des extensions des concepts précédents sont présentées afin d'assurer une résolution fiable en un temps raisonnable.