[ Search ] [ What's New? ] [ About ] [ Bugs ] [ Misc ] [ Mailing Lists ] [ Newgroups ] [ NewsWire ] [ Papers ] [ People ] [ Pictures ] [ Publications ] [ Responce Teams ] [ Tools ] [ Upcoming Events ] [ Web Sites ]
Genetic Algorithms
Title: A Massively Parallel Neurocomputer Authors: Michael Soegtrop Henrik Klagges Abstract: This paper describes a SIMD massively parallel digital neural network simulator - called GeNet for Generic Network - which can evaluate large networks with a variety of learning algorithms at high speed. A medium-size installation with 256 physical nodes and 1 Gbyte of memory can sustain e.g. 1.7 giga 16bit-connection crossings/sec at network sizes of 2 layers with 64K neurons each, a fan-in of 1K and a random wired topology. The neural network core operations are supported by optimized and balanced computation and communication hardware that sustains heavily pipelined processing. In addition to an array of processing units with one global scalar (16 bit) bus, the system is equipped with a ring-shifter (32 bit) and a parallel (256 \002 16 bit) vector bus that feeds a tree-shaped global vector accumulator. This eases backward communication and the calculation of scalar products of distributed vectors. The VLIW-architecture is highly scalable. A prototype has been cost-effectively implemented without custom VLSI chips. Title: A Parallel Genetic Algorithm For The Graph Partitioning Problem Authors: E-G. Talbi P. Bessiere Abstract: Genetic algorithms are stochastic search and optimization techniques which can be used for a wide range of applications. This paper addresses the application of genetic algorithms to the graph partitioning problem. Standard genetic algorithms with large populations suffer from lack of efficiency (quite high execution time). A massively parallel genetic algorithm is proposed, an implementation on a SuperNode of Transputers and results of various benchmarks are given. Title: A Virtual Machine Model For Artificial Neural Network Programming Authors: Pierre Bessier Ali Chams Traian Muntean Abstract: This paper introduces the model of a virtual machine for A.N.N. (Artificial Neural Networks). The context of this work is a collaborative project to study new V.L.S.I. implementations and new architectures for neuronal machines. The work consists in the specification and a prototype implementation of a description language for A.N.N., of the associated virtual machine, of the compiler between them and of the compilers mapping the virtual machine on different highly parallel computers. In this short paper we present the virtual machine model which combines the features of various parallel programming paradigms. Our model allows, in particular, to have the same A.N.N. program running on both synchronous or asynchronous type of machines. In this framework a parallel architecture (S.M.A.R.T.) and a dynamically reconfigurable parallel machine of Transputers (SuperNode) are considered as target machines. Title: Biological metaphors and the Design of Modular Artificial Neural Networks Authors: Egbert J.W Herman Kuiper Abstract: In this thesis, a method is proposed with which good modular artificial neural network structures can be found automatically using a computer program. A number of biological metaphors are incorporated in the method. It will be argued that modular artificial neural networks have a better performance than their non-modular counterparts. the human brain can also be seen as a modular neural network, and the proposed search method is based on the natural process that resulted in the brain: Genetic algorithms are used to imitate evolution, and L-systems are used to model the kind of recipes nature uses in biological growth. Title: Evolution Ecology and Optimization of Digital Oranisms Authors: Thomas S. Ray Abstract: This paper presents here aims to parallel the second major event in the history of life, the origin of diversity. Rather than attempting to create prebiotic conditions from which life may emerge, this approach involves engineering over the early history of life to design complex evolvable organisms, and then attempting to create the conditions that will set off a spontaneous evolutionary process of increasing diversity and complexity of organisms. Title: Evolving Visually Guided Robots Authors: D. Cliff P. Husbands I. harvey Abstract: We have developed a methodology grounded in two beliefs: that autonomous agents need visual processing capabilities, and that the approach of hand-designing control architectures for autonomous agents is likely to be superseded by methods involving the artificial evolution of comparable architectures. In this paper we present results which demonstrate that neural-network control architectures can be evolved for an accurate simulation model of a visually guided robot. The simulation system involves detailed models of the physics of a real robot built at Sussex; and the simulated vision involves ray-tracing computer graphics, using models of optical systems which could readily be constructed from discrete components. The control-network architecture is entirely under genetic control, as are parameters governing the optical system. Significantly, we demonstrate that robust visually-guided control systems evolve from evaluation functions which do not explicitly involve monitoring visual input. The latter part of the paper discusses work now under development, which allows us to engage in long-term fundamental experiments aimed at thoroughly exploring the possibilities of concurrently evolving control networks and visual sensors for navigational tasks. This involves the construction of specialized visual-robotic equipment which eliminates the need for simulated sensing. Title: Genetic Algorithms as a form of Artificial Life. Authors: Melanie Mitchell Stephanie Forrest Abstract: This document review the history and current scope of research on genetic algorithms in artificial life, using illustrative examples in which the genetic algorithm is used to study how learning and evolution interact, and to model ecosystems, immune system, cognitive systems, and social systems. Title: Issues in Evolutionary Robotics Authors: I. Harvey P. Husbands Abstract: This paper authors propose and justify a methodology for the development of the control systems, or `cognitive architectures', of autonomous mobile robots. Author argue that the design by hand of such control systems becomes prohibitively difficult as complexity increases. Author discuss an alternative approach, involving artificial evolution, where the basic building blocks for cognitive architectures are adaptive noise-tolerant dynamical neural networks, rather than programs. These networks may be recurrent, and should operate in real time. Evolution should be incremental, using an extended and modified version of genetic algorithms. Author finally propose that, sooner rather than later, visual processing will be required in order for robots to engage in non-trivial navigation behaviours. Time constraints suggest that initial architecture evaluations should be largely done in simulation. The pitfalls of simulations compared with reality are discussed, together with the importance of incorporating noise. To support our claims and proposals, we present results from some preliminary experiments where robots which roam office-like environments are evolved. Title: List of Genetic Algorithm Publications: FTP Site Availability Authors: Edinburgh Parallel Computing Center Abstract: This paper contains a list shows the availability of genetic algorithms related papers in Postscript form through ftp sites. Title: Neural Networks And Genetic Algorithm For Economic Forecasting Authors: Francis Wong Pan Yong Tan Abstract: This paper describes the applications of an enhanced neural network and genetic algorithm to economic forecasting. The author proposed approach has several significant advantages over conventional forecasting methods such as regression and the Box-Jenkins methods. Apart from being simple and fast in learning, a major advantage is that no assumptions need to be made about the underlying function or model, since the neural network is able to extract hidden information from the historical data. In addition, the enhanced neural network offers selective activation and training of neurons based on the instantaneous causal relationship between the current set of input training data and the output target. This causal relationship is represented by the Accumulated Input Error (AIE) indices, which are computed based on the accumulated errors back-propagated to the input layers during training. The AIE indices are used in the selection of neurons for activation and training. Training time can be reduced significantly, especially for large networks designed to capture temporal information. Although neural networks represent a promising alternative for forecasting, the problem of network design remains a bottleneck that could impair widespread applications in practice. The genetic algorithm is used to evolve optimal neural network architectures automatically, thus eliminating the many pitfalls associated with human engineering approaches. The proposed concepts and design paradigm were tested on several real applications , including the forecast of GDP, air passenger arrival and currency exchange rates. Title: Predicting Convergence Time for Genetic Algorithms Authors: Sushil J. Louis Gregory J. E. Rawlins Abstract: It is difficult to predict a genetic algorithm's behavior on an arbitrary problem. Combining genetic algorithm theory with practice we use the average hamming distance as a syntactic metric to derive bounds on the time convergence of genetic algorithms. Analysis of aflatfunction provides worst case time complexity for static functions. Further, em- ploying linearly computable runtime information, we provide bounds on the time beyond which progress is unlikely on arbitrary static functions. As a byproduct, this analysis also provides qualitative bounds by predicting average fitness. Title: Stack-Based Genetic Programming Authors: Timothy Perkis Abstract: Some recent work in the field of Genetic Programming has been concerned with finding optimum representations for evolvable and efficient computer programs. In this paper, the author describe a new GP system in which target programs run on a slack-based virtual machine. The system is shown to have certain advantages in terms of efficiency and simplicity of implementation, and for certain classes of problems, its effectiveness is shown to be comparable or superior to current methods. Title: Strongly Typed Genetic Programming Authors: David J. Montana Abstract: Genetic programming is a powerful method for automatically generating computer programs via the process of natural selection [Koza 92]. However, it has the limitation known as "closure", i.e. that all the variables, constants, arguments for functions, and values returned from functions must be of the same data type. To correct this deficiency, we introduce a variation of genetic programming called "strongly typed" genetic programming (STGP). In STGP, variables, constants, arguments, and returned values can be of any data type with the provision that the data type for each such value be specified beforehand. This allows the initialization process and the genetic operators to only generate parse trees such that the arguments of each function in each tree have the required types. An extension to STGP which makes it easier to use is the concept of generic functions, which are not true strongly typed functions but rather templates for classes of such functions. To illustrate STGP, we present three examples involving vector and matrix manipulation: (1) a basis representation problem (which can be constructed to be deceptive by any reasonable definition of "deception"), (2) then-dimensional least-squares regression problem, and (3) preliminary work on the Kalman filter. Title: Thoughts on the Synthesis of Life Authors: Thomas S. Ray Abstract: This paper discusses an approach to AL that parallels the major event in the history of life, the origin of diversity. Rather than attempting to create pre-biotic conditions from which life may emerge, this approach involves engineering over the first 3 billion years of life's history to design complex evolvable artificial organisms, and attempting to create the biological conditions that will set off a spontaneous evolutionary process of increasing diversity and complexity of organisms. Title: Unarmed and Dangerous Authors: Ian Douglas Abstract: This article was published in a local electronic mag at the beginning of the year, and also posted onto the FidoNet virus echoes. I am posting it here as it has some relevance to the debate about good and bad viruses. Title: Using Genetic Algorithms to Explore Patterns in the Human Immune System. Authors: Stephanie Forrest Brenda Javormik Robert E. Smith Alan S. Perelson Abstract: This document describes an immune system based on a universe of binary strings. The model is directed at understanding the pattern recognition processes and learning that take place at both the individual and species levels in the immune system.
Aleph One / aleph1@underground.org Copyright © 1996 Computer Underground Society. All rights reserved.

[ Search ] [ What's New? ] [ About ]
[ Bugs ] [ Misc ] [ Mailing Lists ] [ Newgroups ] [ NewsWire ] [ Papers ] [ People ]
[ Pictures ] [ Publications ] [ Responce Teams ] [ Tools ] [ Upcoming Events ] [ Web Sites ]

Genetic Algorithms

Title: A Massively Parallel Neurocomputer

Authors: Michael Soegtrop Henrik Klagges

Abstract:

This paper describes a SIMD massively parallel digital neural network simulator - called GeNet for Generic Network - which can evaluate large networks with a variety of learning algorithms at high speed. A medium-size installation with 256 physical nodes and 1 Gbyte of memory can sustain e.g. 1.7 giga 16bit-connection crossings/sec at network sizes of 2 layers with 64K neurons each, a fan-in of 1K and a random wired topology. The neural network core operations are supported by optimized and balanced computation and communication hardware that sustains heavily pipelined processing. In addition to an array of processing units with one global scalar (16 bit) bus, the system is equipped with a ring-shifter (32 bit) and a parallel (256 \002 16 bit) vector bus that feeds a tree-shaped global vector accumulator. This eases backward communication and the calculation of scalar products of distributed vectors. The VLIW-architecture is highly scalable. A prototype has been cost-effectively implemented without custom VLSI chips.

Title: A Parallel Genetic Algorithm For The Graph Partitioning Problem

Authors: E-G. Talbi P. Bessiere

Abstract:

Genetic algorithms are stochastic search and optimization techniques which can be used for a wide range of applications. This paper addresses the application of genetic algorithms to the graph partitioning problem. Standard genetic algorithms with large populations suffer from lack of efficiency (quite high execution time). A massively parallel genetic algorithm is proposed, an implementation on a SuperNode of Transputers and results of various benchmarks are given.

Title: A Virtual Machine Model For Artificial Neural Network Programming

Authors: Pierre Bessier Ali Chams Traian Muntean

Abstract:

This paper introduces the model of a virtual machine for A.N.N. (Artificial Neural Networks). The context of this work is a collaborative project to study new V.L.S.I. implementations and new architectures for neuronal machines. The work consists in the specification and a prototype implementation of a description language for A.N.N., of the associated virtual machine, of the compiler between them and of the compilers mapping the virtual machine on different highly parallel computers. In this short paper we present the virtual machine model which combines the features of various parallel programming paradigms. Our model allows, in particular, to have the same A.N.N. program running on both synchronous or asynchronous type of machines. In this framework a parallel architecture (S.M.A.R.T.) and a dynamically reconfigurable parallel machine of Transputers (SuperNode) are considered as target machines.

Title: Biological metaphors and the Design of Modular Artificial Neural Networks

Authors: Egbert J.W Herman Kuiper

Abstract:

In this thesis, a method is proposed with which good modular artificial neural network structures can be found automatically using a computer program. A number of biological metaphors are incorporated in the method. It will be argued that modular artificial neural networks have a better performance than their non-modular counterparts. the human brain can also be seen as a modular neural network, and the proposed search method is based on the natural process that resulted in the brain: Genetic algorithms are used to imitate evolution, and L-systems are used to model the kind of recipes nature uses in biological growth.

Title: Evolution Ecology and Optimization of Digital Oranisms

Authors: Thomas S. Ray

Abstract:

This paper presents here aims to parallel the second major event in the history of life, the origin of diversity. Rather than attempting to create prebiotic conditions from which life may emerge, this approach involves engineering over the early history of life to design complex evolvable organisms, and then attempting to create the conditions that will set off a spontaneous evolutionary process of increasing diversity and complexity of organisms.

Title: Evolving Visually Guided Robots

Authors: D. Cliff P. Husbands I. harvey

Abstract:

We have developed a methodology grounded in two beliefs: that autonomous agents need visual processing capabilities, and that the approach of hand-designing control architectures for autonomous agents is likely to be superseded by methods involving the artificial evolution of comparable architectures. In this paper we present results which demonstrate that neural-network control architectures can be evolved for an accurate simulation model of a visually guided robot. The simulation system involves detailed models of the physics of a real robot built at Sussex; and the simulated vision involves ray-tracing computer graphics, using models of optical systems which could readily be constructed from discrete components. The control-network architecture is entirely under genetic control, as are parameters governing the optical system. Significantly, we demonstrate that robust visually-guided control systems evolve from evaluation functions which do not explicitly involve monitoring visual input. The latter part of the paper discusses work now under development, which allows us to engage in long-term fundamental experiments aimed at thoroughly exploring the possibilities of concurrently evolving control networks and visual sensors for navigational tasks. This involves the construction of specialized visual-robotic equipment which eliminates the need for simulated sensing.

Title: Genetic Algorithms as a form of Artificial Life.

Authors: Melanie Mitchell Stephanie Forrest

Abstract:

This document review the history and current scope of research on genetic algorithms in artificial life, using illustrative examples in which the genetic algorithm is used to study how learning and evolution interact, and to model ecosystems, immune system, cognitive systems, and social systems.

Title: Issues in Evolutionary Robotics

Authors: I. Harvey P. Husbands

Abstract:

This paper authors propose and justify a methodology for the development of the control systems, or `cognitive architectures', of autonomous mobile robots. Author argue that the design by hand of such control systems becomes prohibitively difficult as complexity increases. Author discuss an alternative approach, involving artificial evolution, where the basic building blocks for cognitive architectures are adaptive noise-tolerant dynamical neural networks, rather than programs. These networks may be recurrent, and should operate in real time. Evolution should be incremental, using an extended and modified version of genetic algorithms. Author finally propose that, sooner rather than later, visual processing will be required in order for robots to engage in non-trivial navigation behaviours. Time constraints suggest that initial architecture evaluations should be largely done in simulation. The pitfalls of simulations compared with reality are discussed, together with the importance of incorporating noise. To support our claims and proposals, we present results from some preliminary experiments where robots which roam office-like environments are evolved.

Title: List of Genetic Algorithm Publications: FTP Site Availability

Authors: Edinburgh Parallel Computing Center

Abstract:

This paper contains a list shows the availability of genetic algorithms related papers in Postscript form through ftp sites.

Title: Neural Networks And Genetic Algorithm For Economic Forecasting

Authors: Francis Wong Pan Yong Tan

Abstract:

This paper describes the applications of an enhanced neural network and genetic algorithm to economic forecasting. The author proposed approach has several significant advantages over conventional forecasting methods such as regression and the Box-Jenkins methods. Apart from being simple and fast in learning, a major advantage is that no assumptions need to be made about the underlying function or model, since the neural network is able to extract hidden information from the historical data. In addition, the enhanced neural network offers selective activation and training of neurons based on the instantaneous causal relationship between the current set of input training data and the output target. This causal relationship is represented by the Accumulated Input Error (AIE) indices, which are computed based on the accumulated errors back-propagated to the input layers during training. The AIE indices are used in the selection of neurons for activation and training. Training time can be reduced significantly, especially for large networks designed to capture temporal information. Although neural networks represent a promising alternative for forecasting, the problem of network design remains a bottleneck that could impair widespread applications in practice. The genetic algorithm is used to evolve optimal neural network architectures automatically, thus eliminating the many pitfalls associated with human engineering approaches. The proposed concepts and design paradigm were tested on several real applications , including the forecast of GDP, air passenger arrival and currency exchange rates.

Title: Predicting Convergence Time for Genetic Algorithms

Authors: Sushil J. Louis Gregory J. E. Rawlins

Abstract:

It is difficult to predict a genetic algorithm's behavior on an arbitrary problem. Combining genetic algorithm theory with practice we use the average hamming distance as a syntactic metric to derive bounds on the time convergence of genetic algorithms. Analysis of aflatfunction provides worst case time complexity for static functions. Further, em- ploying linearly computable runtime information, we provide bounds on the time beyond which progress is unlikely on arbitrary static functions. As a byproduct, this analysis also provides qualitative bounds by predicting average fitness.

Title: Stack-Based Genetic Programming

Authors: Timothy Perkis

Abstract:

Some recent work in the field of Genetic Programming has been concerned with finding optimum representations for evolvable and efficient computer programs. In this paper, the author describe a new GP system in which target programs run on a slack-based virtual machine. The system is shown to have certain advantages in terms of efficiency and simplicity of implementation, and for certain classes of problems, its effectiveness is shown to be comparable or superior to current methods.

Title: Strongly Typed Genetic Programming

Authors: David J. Montana

Abstract:

Genetic programming is a powerful method for automatically generating computer programs via the process of natural selection [Koza 92]. However, it has the limitation known as "closure", i.e. that all the variables, constants, arguments for functions, and values returned from functions must be of the same data type. To correct this deficiency, we introduce a variation of genetic programming called "strongly typed" genetic programming (STGP). In STGP, variables, constants, arguments, and returned values can be of any data type with the provision that the data type for each such value be specified beforehand. This allows the initialization process and the genetic operators to only generate parse trees such that the arguments of each function in each tree have the required types. An extension to STGP which makes it easier to use is the concept of generic functions, which are not true strongly typed functions but rather templates for classes of such functions. To illustrate STGP, we present three examples involving vector and matrix manipulation: (1) a basis representation problem (which can be constructed to be deceptive by any reasonable definition of "deception"), (2) then-dimensional least-squares regression problem, and (3) preliminary work on the Kalman filter.

Title: Thoughts on the Synthesis of Life

Authors: Thomas S. Ray

Abstract:

This paper discusses an approach to AL that parallels the major event in the history of life, the origin of diversity. Rather than attempting to create pre-biotic conditions from which life may emerge, this approach involves engineering over the first 3 billion years of life's history to design complex evolvable artificial organisms, and attempting to create the biological conditions that will set off a spontaneous evolutionary process of increasing diversity and complexity of organisms.

Title: Unarmed and Dangerous

Authors: Ian Douglas

Abstract:

This article was published in a local electronic mag at the beginning of the year, and also posted onto the FidoNet virus echoes. I am posting it here as it has some relevance to the debate about good and bad viruses.

Title: Using Genetic Algorithms to Explore Patterns in the Human Immune System.

Authors: Stephanie Forrest Brenda Javormik Robert E. Smith Alan S. Perelson

Abstract:

This document describes an immune system based on a universe of binary strings. The model is directed at understanding the pattern recognition processes and learning that take place at both the individual and species levels in the immune system.

Aleph One / aleph1@underground.org