Genetic Algorithms Digest Thursday, April 1, 1993 Volume 7 : Issue 6 - Send submissions to GA-List@AIC.NRL.NAVY.MIL - Send administrative requests to GA-List-Request@AIC.NRL.NAVY.MIL - anonymous ftp archive: FTP.AIC.NRL.NAVY.MIL (Info in /pub/galist/FTP) Today's Topics: - Genetic Algorithms vs Tailored Heuristics - Request for information - Genetic Algorithms applied to Neural Nets - Request for Information on Evolutionary/Genetic Programming - GAs and route / tactical planning - New TCGA Report - Genetic Neural Network Research Report - Evolutionary Robotics Tech Reports(GA used to develop NN controllers) ---------------------------------------------------------------------- **************************************************************************** CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) ECML-93, European Conf. on Machine Learning, Vienna (v6n26) Apr 05-07, 93 Intl. Conf. on Neural Networks and GAs, Innsbruck (v6n22) Apr 13-16, 93 ECAL-93, 2nd European Conference on A-Life, Brussels (v6n31) May 24-26, 93 CSCS93, 9th Int Conf on control systems & CS, Romania (v7n3) May 24-27, 93 ANN93, IEE Intl Conf on Artificial Neural Nets, Brighton May 25-27, 93 ICGA-93, Fifth Intl. Conf. on GAs, Urbana-Champaign (v6n29) Jul 17-22, 93 COLT93, ACM Conf on Computational Learning Theory, UCSC (v6n34) Jul 26-28, 93 Machine Learning & Knowledge Acq. Workshop (IJCAI), France (v7n1) Aug 29, 93 IEE/IEEE Workshop on Nat Alg in Signal Processing, Essex (v7n5) Nov 15-16, 93 ISEC-94 Int. Symp. on Evolutionary Computation, Orlando (v6n40) Jun 25-30, 94 (Send announcements of other activities to GA-List@aic.nrl.navy.mil) **************************************************************************** ------------------------------ From: "James P. Ignizio" Date: Tue, 9 Feb 93 09:51:10 -0500 Subject: Genetic Algorithms vs Tailored Heuristics GENETIC ALGORITHMS VS TAILORED HEURISTICS James P. Ignizio University of Virginia ignizio@virginia.edu For the past several years I have been conducting, albeit on an admittedly limited scale, an evaluation of genetic algorithms --- particularly those GA adaptations used and/or proposed for the solution of problems of combinatorial optimization (e.g., problems of scheduling, layout, location, configuration, knapsack, etc.). This endeavor was motivated by the numerous reports in the literature (as well as in this digest) of the implementation of the GA approach for such problem types ---- coupled with the fact that the vast majority of papers on genetic algorithms appear to simply ignore (and certainly fail to cite) alternative heuristic approaches. I have found that virtually every effort (i.e., for such specific problem types) for which I have been able to obtain details sufficient for replication could have been approached via means of existing, tailored heuristics (i.e., specifically designed heuristic methods that have appeared, over the years, in the open literature; i.e., in the Operations Research/Management Science and Industrial Engineering journals and textbooks in particular). As a consequence of this observation, I have been comparing the computational performance of these tailored heuristics with that of genetic algorithms on the basis of such measures as: Solution Value (i.e., which approach provides the best solution in terms of the measure, or measures of solution performance) Computation Time Computational Resources Required Solution Replication I have thus far been able to compare the performance of the two approaches on more than 30 problems of combinatorial optimization. To date, I have found that the performance of the tailored heuristics has either dominated or at least equaled that of the genetic algorithms in every instance. Based upon this study, I would like to offer two (possibly unpopular) suggestions to the GA community: 1. Before proceeding directly to the use of genetic algorithm, consider doing a simple literature review so as to establish whether or not there already exists an efficient tailored heuristic approach for the problem at hand. While a literature survey may sound like a truly radical concept (particularly when it involves the search of material outside the AI/GA community), it could possibly result in a significant savings in time --- as well as improved results. 2. Realize that, while the term *genetic algorithms* has a certain seductive quality, GAs are but one representation of heuristic solution methods. Please appreciate that this is not a call to abandon research in genetic algorithms. Believe it or not, I am an advocate of the approach ---- if used by the right people, on the right problem, in the right manner. ------------------------------ From: James Robertson Date: Tue, 2 Mar 93 12:25:03 EST Subject: Request for information I am a 4th year (honours) Applied Mathematics student doing a project in Genetic Algorithms applied to Neural Networks. However, I've been having problems finding references for this field, and I would prefer not to duplicate existing work. Does anyone know any references (papers, books, etc) about this that they have come across. Please send anything (at all) to: Internet: jamesr@minnie.cs.su.oz.au Real: James Robertson 4th year honours Department of Applied Mathematics Sydney University NSW 2006 Australia Thanks in advance. ------------------------------ From: Steve Greig Date: Wed, 3 Mar 93 17:11:04 GMT Subject: Request for Information on Evolutionary/Genetic Programming Currently, a colleague and I are trying to initiate a pan-european ESPRIT funded project in the area of evolutionary/genetic programming, and have decided to turn to the GA community for some assistance (should you want to give it). In referring to evolutionary/genetic programming, we are more inclined towards the use of GAs in the breeding of computer programs (*) as opposed to GENNETs or GANNETs which are used to produce neural networks. * For further information, refer to J.R. Kosa's "Genetic Programming", MIT Press, 1991. We are looking for a "few" things: (a) recent references on evolutionary/genetic programming (inc. if these can be obtained via an anonymous ftp site). We shall, of course, make the completed bibliography available to anyone when it is completed, probably in BibTeX format. (b) examples of any work that is going on at the moment, both individual projects and large-scale projects. We don't want people to give away any closely guarded secrets, but we're just trying to avoid duplication. (c) people who are interested in getting involved. We are very keen to develop this project into a full international collaboration, and would welcome any input from others (who probably know a lot more than we do). Finally, other than making the bibliography available, we aim also to produce a survey report detailing the current state-of-the-art in evolutionary/genetic programming. This will also be made available. Thanks in advance, Steve Greig Pete Barclay Computer Studies Department, Napier University, Edinburgh ------------------------------ From: pellazar@lava.nrtc.northrop.com Date: Mon, 1 Mar 93 9:21:56 PST Subject: GAs and route / tactical planning This is a request for bibliography references or in-progress information on the application of genetic algorithms or classifier systems to: * single- or multi-air-vehicle route planning (optimization) * multi-agent coordinated tactical planning * aircraft mission planning (and dynamic in-flight replanning) Your help would be greatly appreciated, mpellazar@lava.nrtc.northrop.com ------------------------------ From: Robert Elliott Smith Date: Tue, 09 Feb 93 09:44:54 -0600 Subject: New TCGA Report The Clearinghouse for Genetic Algorithms at the University of Alabama announces the availability of the following technical report: Adaptively Resizing Populations: An Algorithm and Analysis TCGA Report #93001 Robert E. Smith Department of Engineering Mechanics Deciding on an appropriate population size for a given GA application can often be critical to the algorithm's success. Too small, and the GA can fall victim to sampling error, effecting the efficacy of its search. Too large, and the GA wastes computational resources. Although advice exists for sizing GA populations, much of this advice involves theoretical aspects that are not accessible to the novice user. This paper suggests an algorithm for adaptively resizing GA populations. This algorithm is based on recent theoretical developments that relate population size to schema fitness variance. The suggested algorithm is described and simulated with expected value equations. The simulations suggest that the algorithm may be a viable way to eliminate the population sizing decision from the application of GAs. You can obtain this paper from the following contact points: <> Robert Elliott Smith Department of Engineering of Mechanics Room 210 Hardaway Hall The University of Alabama Box 870278 Tuscaloosa, Alabama 35487 <> rob@comec4.mh.ua.edu <> (205) 348-1618 <> (205) 348-6419 ------------------------------ From: Frederic Gruau Date: 11 Mar 93 09:02:30+0000 Subject: Genetic Neural Network The Laboratory of Computer Science For Parallelism is pleased to announce the availability of the following Research Report: The cellular developmental of neural networks: the interaction of learning and evolution Authors: Fr\'ed\'eric Gruau Darrell Whitley C.E.N.G. DRFMC SP2M PSC Computer Science Department BP 85X 38041 Grenoble, France Colorado State University LIP, ENS-Lyon 46 Allee d'Italie Fort Collins, CO 80523 69007 Lyon, France USA gruau@lip.ens-lyon.fr whitley@cs.colostate.edu A grammar tree is used to encode a cellular developmental process that can develop whole families of Boolean neural networks for computing parity and symmetry. The development process resembles biological cell division. A genetic algorithm is used to find a grammar tree that yields both architecture and weights specifying a particular neural network for solving specific Boolean functions. The current study particularly focuses on the addition of learning to the development process and the evolution of grammar trees. Three ways of adding learning to development process are explored. Two of these exploit the Baldwin effect by changing the fitness landscape without using Lamarkian learning. The third strategy is Lamarkian in nature. Results for these three modes of combining learning with genetic search are compared against genetic search without learning. Our results suggest that merely using learning to change the fitness landscape may be as effective as Lamarkian strategies at improving search. To get this report, make an anonymous FTP at: lip.ens-lyon.fr the file is: pub/LIP/RR/RR93/RR93-04.ps.Z ------------------------------ From: Inman Harvey Date: Wed, 24 Mar 93 10:43:12 GMT Subject: Evolutionary Robotics - Tech. Reports Evolutionary Robotics at Sussex -- Technical Reports =============================== The following six technical reports describe our recent work in using genetic algorithms to develop neural-network controllers for a simulated simple visually-guided robot. Currently only hard-copies are available. To request copies, mail one of: inmanh@cogs.susx.ac.uk or davec@cogs.susx.ac.uk or philh@cogs.susx.ac.uk giving a surface mail address and the CSRP numbers of the reports you want. or write to us at: School of Cognitive and Computing Sciences University of Sussex Brighton BN1 9QH England, UK. ------------ABSTRACTS-------------------- Genetic convergence in a species of evolved robot control architectures I. Harvey, P. Husbands, D. Cliff Cognitive Science Research Paper CSRP267 February 1993 We analyse how the project of evolving 'neural' network controller for autonomous visually guided robots is significantly different from the usual function optimisation problems standard genetic algorithms are asked to tackle. The need to have open ended increase in complexity of the controllers, to allow for an indefinite number of new tasks to be incrementally added to the robot's capabilities in the long term, means that genotypes of arbitrary length need to be allowed. This results in populations being genetically converged as new tasks are added, and needs a change to usual genetic algorithm practices. Results of successful runs are shown, and the population is analysed in terms of genetic convergence and movement in time across sequence space. Analysing recurrent dynamical networks evolved for robot control P. Husbands, I. Harvey, D. Cliff Cognitive Science Research Paper CSRP265 January 1993 This paper shows how a mixture of qualitative and quantitative analysis can be used to understand a particular brand of arbitrarily recurrent continuous dynamical neural network used to generate robust behaviours in autonomous mobile robots. These networks have been evolved in an open-ended way using an extended form of genetic algorithm. After briefly covering the background to our research, properties of special frequently occurring subnetworks are analysed mathematically. Networks evolved to control simple robots with low resolution sensing are then analysed, using a combination of knowledge of these mathematical properties and careful interpretation of time plots of sensor, neuron and motor activities. Analysis of evolved sensory-motor controllers D. Cliff, P. Husbands, I. Harvey Cognitive Science Research Paper CSRP264 December 1992 We present results from the concurrent evolution of visual sensing morphologies and sensory-motor controller-networks for visually guided robots. In this paper we analyse two (of many) networks which result from using incremental evolution with variable-length genotypes. The two networks come from separate populations, evolved using a common fitness function. The observable behaviours of the two robots are very similar, and close to the optimal behaviour. However, the underlying sensing morphologies and sensory-motor controllers are strikingly different. This is a case of convergent evolution at the behavioural level, coupled with divergent evolution at the morphological level. The action of the evolved networks is described. We discuss the process of analysing evolved artificial networks, a process which bears many similarities to analysing biological nervous systems in the field of neuroethology. Incremental evolution of neural network architectures for adaptive behaviour D. Cliff, I. Harvey, P. Husbands Cognitive Science Research Paper CSRP256 December 1992 This paper describes aspects of our ongoing work in evolving recurrent dynamical artificial neural networks which act as sensory-motor controllers, generating adaptive behaviour in artificial agents. We start with a discussion of the rationale for our approach. Our approach involves the use of recurrent networks of artificial neurons with rich dynamics, resilience to noise (both internal and external); and separate excitation and inhibition channels. The networks allow artificial agents (simulated or robotic) to exhibit adaptive behaviour. The complexity of designing networks built from such units leads us to use our own extended form of genetic algorithm, which allows for incremental automatic evolution of controller-networks. Finally, we review some of our recent results, applying our methods to work with simple visually-guided robots. The genetic algorithm generates useful network architectures from an initial set of randomly-connected networks. During evolution, uniform noise was added to the activation of each neuron. After evolution, we studied two evolved networks, to see how their performance varied when the noise range was altered. Significantly, we discovered that when the noise was eliminated, the performance of the networks degraded: the networks use noise to operate efficiently. Evolving visually guided robots D. Cliff, P. Husbands, I. Harvey Cognitive Science Research Paper CSRP220 July 1992 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 simula- tion 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 specialised visual-robotic equipment which eliminates the need for simulated sensing. Issues in evolutionary robotics I. Harvey, P. Husbands, D. Cliff Cognitive Science Research Paper CSRP219 July 1992 In this paper we propose and justify a methodology for the development of the control systems, or `cognitive architectures', of autonomous mobile robots. We argue that the design by hand of such control systems becomes prohibitively difficult as complexity increases. We 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. We 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. ------------------------------ End of Genetic Algorithms Digest ******************************