Construction of Neural Network using Cellular Encoding and the Genetic Algorithm.

  • By: Frederic Gruau
  • Number: PhD1994-01
  • Date: January 1994
  • Abstract:
    Artificial neural networks used to be considered only as a machine that learns using small modifications of internal parameters. Now this is changing. Such learning method do not allow to generate big neural networks for solving real world problems. This thesis defends the following view point: - The key word to go out of that dead-end is "modularity". - The tool that can generate modular neural network is cellular encoding. - The optimization algorithm adapted to the search of cellular codes is the genetic algorithm. The first point is now a common idea. A modular neural network means a neural network that is made of several sub-networks, arranged in a hierarchical way. For example, the same sub-network can be repeated. This thesis encompasses two parts. The first part demonstrates the second point. Cellular encoding is presented as a machine language for neural networks, with a theoretical basis (it is a parallel graph grammar that checks a number of properties) and a compiler of high level language. The second part of the thesis show the third point. Application of genetic algorithm to the synthesis of neural networks using cellular encoding is a new technology. This technology can solve problems that were still unsolved with neural networks. It can automatically and dynamically decompose a problem into a hierarchy of sub-problems, and generate a neural network solution to the problem. The structure of this network is a hierarchy of sub-networks that reflect the structure of the problem. The technology allows to experience new scientific domains like the interaction between learning and evolution, or the set up of learning algorithms that suit the GA.
  • Keywords:
    Genetic Algorithms, Neural Networks, Cellular Encoding, Neural Compilation, Switch Learning, Develomental Learning.
  • Availability: Electronic copy only.
  • Size: 151p
  • Comment: This thesis is also available in French at
  • Format: Compressed PostScript
  • Get it

Procedures de base pour le calcul scientifique sur machines paralleles a memoire distribuee.

  • By: Frederic Desprez
  • Number: PhD1994-02
  • Date: January 6, 1994
  • Availability: Paper copy available. Not available by FTP.

Parallelisation automatique : du modele systolique a la compilation de nids de boucles.

  • By: Tanguy Risset
  • Number: PhD1994-03
  • Date: February 1994
  • Abstract:
    The techniques developed by researchers for systolic architectures are very close to the ones that are used nowadays for the automatic parallelization of simple programs. This thesis studies these techniques through their different applications. We first study pure systolic synthesis for matrix computations algorithms. Then we extend the systolic model to a more general architecture model. We work on techniques for SIMD programming, using results obtained on semi-systolic architectures. Then we study automatic parallelization of simple programs namely ``nested loops''. We work more particularly on loop transformations such as loop rewriting or loop tiling.
  • Keywords:
    Systolic arrays, Synthesis methodologies, Automatic parallelization, Nested loops, Rewriting loops.
  • Availability: Electronic copy only.
  • Size: 113p
  • Format: Compressed PostScript
  • Get it

Cellular automata: reversibility and complexity.

  • By: Bruno Durand
  • Number: PhD1994-04
  • Date: February 1994
  • Abstract:
    We study cellular automata (CA) from several points of view. We first consider them as dynamical systems and give a new proof of a well-known theorem due to Richardson: "cellular automata are continuous functions which commute with shifts". Our proof allows us to study the minimization of their representation. Then, we present a classification of CA according to their limit behaviour. We prove that this classification is partially decidable in the one-dimensionnal case. We also establish an extention, in terms of probabilities, of a theorem proved by Karel Culik in 1989. The methods we use are based on topological and combinatorial constructions. The second part is devoted to algoritms and complexity. We present there two reductions from tilings problem into problems concerning cellular automata. With these reductions, we give a simplified proof of the undecidability of the surjectivity problem in 2-dimensionnal spaces (this result was first established by Jarkko Kari in 1989) and we prove the co-NP-completeness in the worst case and in the average case for the following decision problems: - Given a 2D CA, is it bijective when restricted to finite configurations smaller than the length of its coding? - Given a 2D CA, is it bijective when restricted to periodic configurations with period smaller than the length of its coding?
  • Keywords:
    Cellular Automata, Complexity, Reversibility, Limit Sets.
  • Availability: Electronic copy only.
  • Size: 64p
  • Format: Compressed PostScript
  • Get it

Contribution à l'étude du contrôle moteur, du connexionnisme et du parallélisme.

  • By: Jean Christophe Mignot
  • Number: PhD1994-05
  • Date: February 18, 1994
  • Abstract:
    This thesis deals with artificial and biological neural networks, and parallel computers. The study of biological neural networks is done through the analysis of motor control during grasping movements. The basic knowledge of neurobiology is reminded as well as some open problems in the domain of motor control. An exprimental framework is presented that has been developped for grasping movements. It allows us to record 3D coordinates of the movement and to perform perturbations of the environement depending on some features of the movement detected in real-time. Neural network based modelisations are presented that allow generating static goal directed trajectories. The learning of connexionnist models is a very long iterative process. Parallel computers have the potential power to satisfy researchers needs. A Connection Machine CM-2 has been use to implement backpropagation neural networks. The algorithm uses the knowledge of the hardware of the machine and some software tools to obtain an optimal computation time. The idea of the implementation is to use the inherent parallelism of the many exemples of the database. An industrial application is presented concerning the prediction of pollution using backpropagation neural networks. It exhibited better results than those obtain by statistic methods without having any expertise in the subject. An implementation of Kohonen maps on a SIMD computer, the MasPar MP-1 is presented. A new algorithm is described that uses a block strategy to reduce the computation time. The study of the load of Kohonen maps allows us to perform an optimal mapping of the neurons on the processors. Experimental results, on learning the unit square, exhibit a reduction of the computation time by a factor around two.
  • Keywords:
    Neural networks, Motor Control of Arm Movement, Parallel Computers with Distributed Memory Contribution to the study of motor control, connexionnism and parallelism.
  • Availability: Electronic copy only.
  • Size: 202p
  • Format: Compressed PostScript
  • Get it

Bases discretes et calcul des fonctions elementaires par materiel.

  • By: Xavier Merrheim
  • Number: PhD1994-06
  • Date: February 24, 1994
  • Availability: Paper copy available. Not available by FTP.

Conception et simulation d'une machine massivement parallele en grande precision.

  • By: Mario Fiallos-Aguilar
  • Number: PhD1994-07
  • Date: June 21, 1994
  • Availability: Paper copy available. Not available by FTP.

Cellular automata on Cayley graphs.

  • By: Zsuzsanna Roka
  • Number: PhD1994-08
  • Date: Juillet 11, 1994
  • Abstract:
    Two notions of automata network has been studied in the literature. The first one is the notion of cellular automata: we put copies of the same finite automaton in the vertices of Z, Z^2, ..., Z^n, and these automata communicate according to the directions of the space. The second notion is that of automata-graphs: finite automata are placed in the vertices of the graph and communicate through the arcs. The first notion is based on very simple graphs, and in the second one, cells do not know their local situation with respect to their neighbors. That is why we decided to define cellular automata on Cayley graphs which are graphical representations of groups and hence regular graphs. There are three main parts in our thesis. In the first one, we generalize the notion of one-way cellular automata defined in the one-dimensional space, to a notion on Cayley graphs. We give some simulation results for cellular automata working on some usual graphs like hexagonal and triangular tilings of the plane. In the general case, we give some sufficient and some necessary conditions for that every cellular automaton on a Cayley graph to be simulated by a one-way cellular automaton on the same graph. In the second part of our thesis, we study the notion of simulation between cellular automata. In particular, we study cellular automata on Cayley graphs corresponding to the Archimedean tilings of the plane. We show that all these graphs are equivalent to the grid. We also give sufficient conditions for that such simulations to exist, in terms of morphisms with a finite kernel and a finite index. In the last part, we show how to synchronize minimal length paths between two vertices of a Cayley graph. In this study, we have met an algorithmical difficulty called the existence of "culs-de-sac", that is, the existence of points at distance n from the center point such that none of the neighbor points is at distance n+1.
  • Keywords:
    Cellular Automata, One-way Cellular Automata, Simulations, Cayley Graphs.
  • Availability: Electronic copy only.
  • Size: 110p
  • Format: Compressed PostScript
  • Get it

Parallel segmentation of 3D images.

  • By: Laurent Perroton
  • Number: PhD1994-09
  • Date: December 5, 1995
  • Abstract:
    In this thesis, we present several results related to discrete 3D image processing for one part, and to parallelization of image segmentation for another part. In a first part, several problems related to discrete 3D image processing are presented. Cellular complex approach is introduced. Its goal is to allow a consistent modelization of discrete 3D images. A notion of discrete surface composed of bidimensional elements of the 3D space is reminded. Several theoretical results on this topic are gathered in a research report provided in annex of the thesis. Main author results are included in the thesis itself: an extension of the definition of the discrete surfaces to 26-connected objects verifying the fundamental property that there exists a unique connected surface for each pair of object component, background component. Finally, we present a PRAM surface tracking algorithm of the pixels of the surface. In a second part, a bibliography about image segmentation is presented. Image segmentation algorithms by region merging are introduced and we compare existing sequential algorithms with intrinsic parallel algorithms. In that frame, a study about the parallelization of the connected component labeling of 3D binary discrete images is presented. A bibliography of the subject describes all the main known sequential and parallel algorithms. We then introduce our personal contribution which is a parallel algorithm for the iPSC860 hypercube machine. The last part of the thesis is dedicated to several tools for the parallelization of 3D image processing: the PPCM library which defines a communication standard for MIMD distributed memory machines, and a data structure including load balancing features.
  • Keywords:
    Parallel 3D Image Processing, Discrete Surfaces, Component Labeling, Load-balancing.
  • Availability: Paper copy available.
  • Size: 212p
  • Format: Compressed PostScript
  • Get it

Approches paralleles pour la squelettisation 3-D.

  • By: Virginie Marion-Poty
  • Number: PhD1994-10
  • Date: December 9, 1994
  • Abstract:
    Skeletonization methods in 3-D, and second the parallelization onto general purpose parallel distributed memory machines. The document is divided into three parts, and the annexes include papers presented in international conferences or workshops. The first chapter is a brief introduction of the main concepts and the classical skeletonization methods. The studied domain is presented: it belongs to the thinning methods. It presents the domain of work, and the specificproblems involved by the 3-D extension. The second chapter presents two new skeletonization algorithms. The first is a 2-D algorithm based on O'Gorman operator using $k \times k$ windows, and one algorithm improvement. The second is a contour-based thinning algorithm simulating Pavlidis'operator. A new operator is proposed by changing multiple point Pavlidis'definition with a local process named "coloration". Then this approach is extended in 3-D. The third chapter deals with the parallel implementation of skeletonization algorithms onto distributed memory machines. Two problems are addressed: first the data allocation onto a processors network configurated in grid, and second the implementation methods. A study of a such data allocation concludes that the images division into squared sub-images is not the good solution. This work is limited to the 2-D images, because the problem in 3-D leads to fifth degree equations. Then two implementation methods of skeletonization algorithms with non-parallel operator are studied. In 3-D space, the operator decomposition into sub-operators is illustrated by Jonker in one hand and by Bertrand and Gong in other hand. And the domain decomposition into sub-domains is illustrated by the chessboard decomposition into two sub-domains in one hand, and by Neusius and Olzewski'decomposition into four sub-domains in other hand. The last decomposition is extended to the volumic images. Then a comparison between these two decomposition methods, operator and domain, is given. A conclusion, based on the results and further works, allows to give some directives to follow the skeletonization extension to 3-D images, particularly with the medial surface reconnection and the parallelization of this last method.
  • Keywords:
    Parallel Algorithms, Skeletonization, Tridimensional Images, Discrete Geometry.
  • Availability: Electronic copy only.
  • Format: Compressed PostScript
  • Get it