Genetic programming for the RoboCup Rescue Simulation System

The Robocup Rescue Simulation System (RCRSS) is a dynamic system of multi-agent interaction, simulating a large-scale urban disaster scenario. Teams of rescue agents are charged with the tasks of minimizing civilian casualties and infrastructure damage while competing against limitations on time, communication, and awareness. This thesis provides the first known attempt of applying Genetic Programming (GP) to the development of behaviours necessary to perform well in the RCRSS. Specifically, this thesis studies the suitability of GP to evolve the operational behaviours required of each type of rescue agent in the RCRSS. The system developed is evaluated in terms of the consistency with which expected solutions are the target of convergence as well as by comparison to previous competition results. The results indicate that GP is capable of converging to some forms of expected behaviour, but that additional evolution in strategizing behaviours must be performed in order to become competitive. An enhancement to the standard GP algorithm is proposed which is shown to simplify the initial search space allowing evolution to occur much quicker. In addition, two forms of population are employed and compared in terms of their apparent effects on the evolution of control structures for intelligent rescue agents. The first is a single population in which each individual is comprised of three distinct trees for the respective control of three types of agents, the second is a set of three co-evolving subpopulations one for each type of agent. Multiple populations of cooperating individuals appear to achieve higher proficiencies in training, but testing on unseen instances raises the issue of overfitting.

Genetic Programming for Non-Photorealistic Rendering

This thesis focuses on developing an evolutionary art system using genetic programming. The main goal is to produce new forms of evolutionary art that filter existing images into new non-photorealistic (NPR) styles, by obtaining images that look like traditional media such as watercolor or pencil, as well as brand new effects. The approach permits GP to generate creative forms of NPR results. The GP language is extended with different techniques and methods inspired from NPR research such as colour mixing expressions, image processing filters and painting algorithm. Colour mixing is a major new contribution, as it enables many familiar and innovative NPR effects to arise. Another major innovation is that many GP functions process the canvas (rendered image), while is dynamically changing. Automatic fitness scoring uses aesthetic evaluation models and statistical analysis, and multi-objective fitness evaluation is used. Results showed a variety of NPR effects, as well as new, creative possibilities.

Real-Time Automatic Object Classification and Tracking using Genetic Programming and NVIDIA R CUDA TM

Genetic Programming (GP) is a widely used methodology for solving various computational problems. GP's problem solving ability is usually hindered by its long execution times. In this thesis, GP is applied toward real-time computer vision. In particular, object classification and tracking using a parallel GP system is discussed. First, a study of suitable GP languages for object classification is presented. Two main GP approaches for visual pattern classification, namely the block-classifiers and the pixel-classifiers, were studied. Results showed that the pixel-classifiers generally performed better. Using these results, a suitable language was selected for the real-time implementation. Synthetic video data was used in the experiments. The goal of the experiments was to evolve a unique classifier for each texture pattern that existed in the video. The experiments revealed that the system was capable of correctly tracking the textures in the video. The performance of the system was on-par with real-time requirements.

Approches générales de résolution pour les problèmes multi-attributs de tournées de véhicules et confection d'horaires

Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes

Uncovering parallel ribosome biogenesis pathways during pre-60S subunit maturation

Paralogs are present during ribosome biogenesis as well as in mature ribosomes in form of ribosomal proteins, and are commonly believed to play redundant functions within the cell. Two previously identified paralogs are the protein pair Ssf1 and Ssf2 (94% homologous). Ssf2 is believed to replace Ssf1 in case of its absence from cells, and depletion of both proteins leads to severely impaired cell growth. Results reveal that, under normal conditions, the Ssf paralogs associate with similar sets of proteins but with varying stabilities. Moreover, disruption of their pre-rRNP particles using high stringency buffers revealed that at least three proteins, possibly Dbp9, Drs1 and Nog1, are strongly associated with each Ssf protein under these conditions, and most likely represent a distinct subcomplex. In this study, depletion phenotypes obtained upon altering Nop7, Ssf1 and/or Ssf2 protein levels revealed that the Ssf paralogs cannot fully compensate for the depletion of one another because they are both, independently, required along parallel pathways that are dependent on the levels of availability of specific ribosome biogenesis proteins. Finally, this work provides evidence that, in yeast, Nop7 is genetically linked with both Ssf proteins.

Characterization of polycystin-1 in ADPKD pathogenetic mechanism : biogenesis and functional implications by genetic approaches in mouse

La polykystose rénale autosomique dominante (ADPKD) est une des maladies génétiques les plus communes. ADPKD se manifeste le plus souvent au stade adulte par la présence de kystes rénaux, et bien souvent de kystes hépatiques, avec une progression très variable. ADPKD mène à une insuffisance rénale: les seuls recours sont la dialyse puis la transplantation rénale. Les mutations dispersées sur les gènes PKD1 (majoritairement; la protéine polycystine-1, PC1) et PKD2 (la protéine polycystine-2, PC2) sont responsables de l’ADPKD. Le mécanisme pathogénétique de perte de fonction (LOF) et donc d’un effet récessif cellulaire est évoqué comme causatif de l’ADPKD. LOF est en effet supporté par les modèles murins d’inactivation de gènes PKD1/PKD2, qui développent de kystes, quoique in utéro et avec une rapidité impressionnante dans les reins mais pas dans le foie. Malgré de nombreuses études in vitro, le rôle de PC1/PC2 membranaire/ciliaire reste plutôt hypothétique et contexte-dépendant. Ces études ont associé PC1/PC2 à une panoplie de voies de signalisation et ont souligné une complexité structurelle et fonctionnelle exceptionnelle, dont l’implication a été testée notamment chez les modèles de LOF. Toutefois, les observations patho-cellulaires chez l’humain dont une expression soutenue, voire augmentée, de PKD1/PC1 et l’absence de phénotypes extrarénaux particuliers remet en question l’exclusivité du mécanisme de LOF. Il était donc primordial 1) d’éclaircir le mécanisme pathogénétique, 2) de générer des outils in vivo authentiques d’ADPKD en terme d’initiation et de progression de la maladie et 3) de mieux connaitre les fonctions des PC1/PC2 indispensables pour une translation clinique adéquate. Cette thèse aborde tous ces points. Tout d’abord, nous avons démontré qu’une augmentation de PKD1 endogène sauvage, tout comme chez l’humain, est pathogénétique en générant et caractérisant en détail un modèle murin transgénique de Pkd1 (Pkd1TAG). Ce modèle reproduit non seulement les caractéristiques humaines rénales, associées aux défauts du cil primaire, mais aussi extrarénales comme les kystes hépatiques. La sévérité du phénotype corrèle avec le niveau d’expression de Pkd1 ce qui supporte fortement un modèle de dosage. Dans un deuxième temps, nous avons démontré par les études de complémentations génétiques que ces deux organes reposent sur une balance du clivage GPS de Pc1, une modification post-traductionelle typique des aGPCR, et dont l’activité et l’abondance semblent strictement contrôlées. De plus, nous avons caractérisé extensivement la biogénèse de Pc1 et de ses dérivés in vivo générés suite au clivage GPS. Nous avons identifié une toute nouvelle forme et prédominante à la membrane, la forme Pc1deN, en plus de confirmer deux fragments N- et C-terminal de Pc1 (NTF et CTF, respectivement) qui eux s’associent de manière non-covalente. Nous avons démontré de façon importante que le trafic de Pc1deN i.e., une forme NTF détachée du CTF, est toutefois dépendant de l’intégrité du fragment CTF in vivo. Par la suite, nous avons généré un premier modèle humanisant une mutation PKD1 non-sens tronquée au niveau du domaine NTF(E3043X) en la reproduisant chez une souris transgénique (Pkd1extra). Structurellement, cette mutation, qui mimique la forme Pc1deN, s’est également avérée causative de PKD. Le modèle Pkd1extra a permis entre autre de postuler l’existence d’une cross-interaction entre différentes formes de Pc1. De plus, nos deux modèles murins sont tous les deux associés à des niveaux altérés de c-Myc et Pc2, et soutiennent une implication réelle de ces derniers dans l’ADPKD tou comme une interaction fonctionnelle entre les polycystines. Finalement, nous avons démontré un chevauchement significatif entre l’ADPKD et le dommage rénal aigüe (ischémie/AKI) dont une expression augmentée de Pc1 et Pc2 mais aussi une stimulation de plusieurs facteurs cystogéniques tel que la tubérine, la β-caténine et l’oncogène c-Myc. Nos études ont donc apporté des évidences cruciales sur la contribution du gène dosage dans l’ADPKD. Nous avons développé deux modèles murins qui serviront d’outil pour l’analyse de la pathologie humaine ainsi que pour la validation préclinique ADPKD. L’identification d’une nouvelle forme de Pc1 ajoute un niveau de complexité supplémentaire expliquant en partie une capacité de régulation de plusieurs voies de signalisation par Pc1. Nos résultats nous amènent à proposer de nouvelles approches thérapeutiques: d’une part, le ciblage de CTF i.e., de style chaperonne, et d’autre part le ciblage de modulateurs intracellulaires (c-Myc, Pc2, Hif1α). Ensemble, nos travaux sont d’une importance primordiale du point de vue informatif et pratique pour un avancement vers une thérapie contre l’ADPKD. Le partage de voies communes entre AKI et ADPKD ouvre la voie aux approches thérapeutiques parallèles pour un traitement assurément beaucoup plus rapide.

Fixed Point Decimal Multiplication Using RPS Algorithm

Decimal multiplication is an integral part of financial, commercial, and internet-based computations. A novel design for single digit decimal multiplication that reduces the critical path delay and area for an iterative multiplier is proposed in this research. The partial products are generated using single digit multipliers, and are accumulated based on a novel RPS algorithm. This design uses n single digit multipliers for an n × n multiplication. The latency for the multiplication of two n-digit Binary Coded Decimal (BCD) operands is (n + 1) cycles and a new multiplication can begin every n cycle. The accumulation of final partial products and the first iteration of partial product generation for next set of inputs are done simultaneously. This iterative decimal multiplier offers low latency and high throughput, and can be extended for decimal floating-point multiplication.

Genetic Programming meets Model-Driven Development

Genetic programming is known to provide good solutions for many problems like the evolution of network protocols and distributed algorithms. In such cases it is most likely a hardwired module of a design framework that assists the engineer to optimize specific aspects of the system to be developed. It provides its results in a fixed format through an internal interface. In this paper we show how the utility of genetic programming can be increased remarkably by isolating it as a component and integrating it into the model-driven software development process. Our genetic programming framework produces XMI-encoded UML models that can easily be loaded into widely available modeling tools which in turn posses code generation as well as additional analysis and test capabilities. We use the evolution of a distributed election algorithm as an example to illustrate how genetic programming can be combined with model-driven development. This example clearly illustrates the advantages of our approach – the generation of source code in different programming languages.

An O(N) Algorithm for Three-Dimensional N-Body Simulations

We develop an algorithm that computes the gravitational potentials and forces on N point-masses interacting in three-dimensional space. The algorithm, based on analytical techniques developed by Rokhlin and Greengard, runs in order N time. In contrast to other fast N-body methods such as tree codes, which only approximate the interaction potentials and forces, this method is exact ?? computes the potentials and forces to within any prespecified tolerance up to machine precision. We present an implementation of the algorithm for a sequential machine. We numerically verify the algorithm, and compare its speed with that of an O(N2) direct force computation. We also describe a parallel version of the algorithm that runs on the Connection Machine in order 0(logN) time. We compare experimental results with those of the sequential implementation and discuss how to minimize communication overhead on the parallel machine.

On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs

A key capability of data-race detectors is to determine whether one thread executes logically in parallel with another or whether the threads must operate in series. This paper provides two algorithms, one serial and one parallel, to maintain series-parallel (SP) relationships "on the fly" for fork-join multithreaded programs. The serial SP-order algorithm runs in O(1) amortized time per operation. In contrast, the previously best algorithm requires a time per operation that is proportional to Tarjan’s functional inverse of Ackermann’s function. SP-order employs an order-maintenance data structure that allows us to implement a more efficient "English-Hebrew" labeling scheme than was used in earlier race detectors, which immediately yields an improved determinacy-race detector. In particular, any fork-join program running in T₁ time on a single processor can be checked on the fly for determinacy races in O(T₁) time. Corresponding improved bounds can also be obtained for more sophisticated data-race detectors, for example, those that use locks. By combining SP-order with Feng and Leiserson’s serial SP-bags algorithm, we obtain a parallel SP-maintenance algorithm, called SP-hybrid. Suppose that a fork-join program has n threads, T₁ work, and a critical-path length of T[subscript ∞]. When executed on P processors, we prove that SP-hybrid runs in O((T₁/P + PT[subscript ∞]) lg n) expected time. To understand this bound, consider that the original program obtains linear speed-up over a 1-processor execution when P = O(T₁/T[subscript ∞]). In contrast, SP-hybrid obtains linear speed-up when P = O(√T₁/T[subscript ∞]), but the work is increased by a factor of O(lg n).

Speculative parallelization of multipath radiosity algorithm

In computer graphics, global illumination algorithms take into account not only the light that comes directly from the sources, but also the light interreflections. This kind of algorithms produce very realistic images, but at a high computational cost, especially when dealing with complex environments. Parallel computation has been successfully applied to such algorithms in order to make it possible to compute highly-realistic images in a reasonable time. We introduce here a speculation-based parallel solution for a global illumination algorithm in the context of radiosity, in which we have taken advantage of the hierarchical nature of such an algorithm

Scalability of efficient parallel K-Means

Clustering is defined as the grouping of similar items in a set, and is an important process within the field of data mining. As the amount of data for various applications continues to increase, in terms of its size and dimensionality, it is necessary to have efficient clustering methods. A popular clustering algorithm is K-Means, which adopts a greedy approach to produce a set of K-clusters with associated centres of mass, and uses a squared error distortion measure to determine convergence. Methods for improving the efficiency of K-Means have been largely explored in two main directions. The amount of computation can be significantly reduced by adopting a more efficient data structure, notably a multi-dimensional binary search tree (KD-Tree) to store either centroids or data points. A second direction is parallel processing, where data and computation loads are distributed over many processing nodes. However, little work has been done to provide a parallel formulation of the efficient sequential techniques based on KD-Trees. Such approaches are expected to have an irregular distribution of computation load and can suffer from load imbalance. This issue has so far limited the adoption of these efficient K-Means techniques in parallel computational environments. In this work, we provide a parallel formulation for the KD-Tree based K-Means algorithm and address its load balancing issues.

Dynamic load balancing in parallel KD-tree k-means

One among the most influential and popular data mining methods is the k-Means algorithm for cluster analysis. Techniques for improving the efficiency of k-Means have been largely explored in two main directions. The amount of computation can be significantly reduced by adopting geometrical constraints and an efficient data structure, notably a multidimensional binary search tree (KD-Tree). These techniques allow to reduce the number of distance computations the algorithm performs at each iteration. A second direction is parallel processing, where data and computation loads are distributed over many processing nodes. However, little work has been done to provide a parallel formulation of the efficient sequential techniques based on KD-Trees. Such approaches are expected to have an irregular distribution of computation load and can suffer from load imbalance. This issue has so far limited the adoption of these efficient k-Means variants in parallel computing environments. In this work, we provide a parallel formulation of the KD-Tree based k-Means algorithm for distributed memory systems and address its load balancing issue. Three solutions have been developed and tested. Two approaches are based on a static partitioning of the data set and a third solution incorporates a dynamic load balancing policy.

A novel parallel approach to the likelihood-based estimation of admixture in population genetics

Inferring population admixture from genetic data and quantifying it is a difficult but crucial task in evolutionary and conservation biology. Unfortunately state-of-the-art probabilistic approaches are computationally demanding. Effectively exploiting the computational power of modern multiprocessor systems can thus have a positive impact to Monte Carlo-based simulation of admixture modeling. A novel parallel approach is briefly described and promising results on its message passing interface (MPI)-based C implementation are reported.