================================= VOLUME 18 NUMBER 4 DECEMBER 1994 ================================= First half is a special volume Evolutionary Computation/ Artificial Life. ---------------------------------- 0. An Introduction to the Special Issue on Evolutionary Computation Xin Yao Department of Computer Science University College, The University of New South Wales Australian Defence Force Academy Canberra, ACT, Australia 2600 Phone: +61 6 268 8819, Fax: +61 6 268 8581 Email: xin@csadfa.cs.adfa.oz.au Keywords: evolutionary computation, optimisation, learning Evolutionary computation is the study of computational systems that use ideas and get inspirations from natural evolution. There has been a sharp increase of interest in the field in recent years. The first five papers included in this special issue are selected from papers presented at the AI'93 Workshop on Evolutionary Computation held at the Grand Hyatt Hotel, Melbourne, Australia, on 16 November 1993. Although the papers do not represent all the subfields of evolutionary computation, they do cover the three major branches, i.e., genetic algorithms, evolution strategies and evolutionary programming. The first five papers address a wide range of issues related to evolutionary computation. The paper by Crosher discusses the evolution of adaptive processes in simulated environments. He tries to confirm his hypothesis that ``the answer to the question of how adaptive or learning processes can evolve is through an appropriately designed evolutionary search domain, search technique, and problem environment'' through a set of three experiments. This hypothesis can also be understood from a slightly different point of view. The evolutionary search is determined by both representation of the search space, i.e., representation of individuals and the search method. We must guarantee completeness and closure of the search space so that the probability of finding an optimal adaptive process is non-zero. The efficiency of a search algorithm to find such an adaptive process is also dependent on the algorithm itself and the representation, which affects the fitness landscape. The environment plays another important role in searching for a near optimal solution since it can introduce biases into the evolutionary search. The environment determines which part of the fitness landscape is known to the search algorithm, and thus biases the evolved solution towards this part. There is a strong connection between the environment and the generalisation ability of the evolved solution. Since the search algorithm and representation have a strong impact on searching a fitness landscape, techniques have been developed to design better and self-adaptive search operators so that the landscape is easier to search. The paper by Fogel et al represents such a technique. Two adaptive mutation operators are proposed in this paper. The preliminary experiments seem to confirm the advantage of using the adaptive mutations. By incorporating search operators themselves into the evolutionary search, more information about the fitness landscape obtained during previous search can be kept and used to bias subsequent search towards more promising regions. A related issue to adaptive search operators is how to characterise a fitness landscape so that some of the characteristics can be measured and used by adaptive operators in order to search efficiently. This is still an open issue although there has been a lot of research efforts devoted to it. Every search algorithm, except for uniformly random search, introduces some kind of bias into its search. Different algorithms have different biases. Evolutionary algorithms with different operators also have different biases. There have been some discussions on the biases introduced by various crossover operators in the genetic algorithm literature. It is such biases that make an algorithm very efficient for one class of problems (i.e., the biases lead to the efficient search of a class of fitness landscapes) but not for others. Since we still don't know how to characterise a fitness landscape so that some biases can be used to search efficiently, it is very difficult to determine which search algorithm should be applied to a problem because it has appropriate biases. The scarceness of a priori knowledge about a problem makes the design of a good search algorithm even more difficult. In addition to the study of adaptive search operators where biases can be changed automatically to achieve higher search efficiency, another way to reduce the possible detrimental effects of biases introduced by an algorithm is to use a hybrid algorithm which includes different biases introduced by several different algorithms in the hope that the best bias would always be used in search. Kido et al's paper presents such a hybrid algorithm and demonstrates its application to an instance of the well-known Traveling Saleman Problem (TSP). The classical genetic algorithm have long been criticised for their weak local search ability since it is biased towards global search. Kido et al have combined the global search bias of the genetic algorithm with the local search bias of simulated annealing and tabu search and achieved better results than those produced by any of the single algorithms for the particular TSP instance. Their result that GA+SA+TABU performs better than either GA+SA or GA+TABU seems to indicate that different biases in GA+SA+TABU enable search to be conducted efficiently in different regions of the search space, although more studies need to be carried out before a conclusion can be drawn. There have been quite a few studies relating to the iterated prisoner's dilemma game in the evolutionary computation and artificial life communities since Axelrod's work. The paper by Tomita and Kido investigates two variants of the single round prisoner's dilemma game. It is shown that a group of individuals who perform worse than an opponent individually in a population can actually grow and take over the whole population because individual sacrifices indirectly benefit the group as a whole. It might be confusing at first to find a paper in the special issue on evolutionary computation discussing computational evolution. What is computational evolution? It is described by Vaario in his paper as the study of using the evolutionary process for the construction of intelligence, rather than for optimisation. One distinct feature of Vaario's model of evolution is his emphasis on the environment. In the Darwinian evolution, the environment provides feedback to the evolution only through selection. Vaario however indicated that the environment has major impact on all of morphogenesis (the developmental process), ontogenesis and phylogenesis (See Figure 2 in his paper). There is no explicit fitness function in his model of evolution. In a sense, the evolution he is concerned about is open-ended and thus more ``creative'' than the close-end evolution. A new modelling language MLIS has been proposed in his paper to facilitate the simulation of various aspects of his model. Each object in his model is represented by a set of production rules which can be modified, added and deleted in the evolution. ---------------------------------- 1. The Artificial Evolution of Adaptive Processes Douglas T. Crosher, School of Electrical Engineering, Swinburne University of Technology, P.O. Box 218, Hawthorn 3122, Australia E-mail: dtc@scrooge.ee.swin.oz.au pp. 377-386 Keywords: evolution, learning, adaptation Abstract: It is hypothesised that the answer to the question of how adaptive or learning processes can evolve is through an appropriately designed evolutionary search domain, search technique, and problem environment. A representation is described that is able to represent a general class of adaptive processes. The hypothesis is explored through three experiments with a fixed evolutionary search algorithm and graded problems. The search algorithm is able to find solutions to two of the problems but fails on a slightly more difficult problem. The failure is explained by the lack of a priori knowledge, thus supporting the hypothesis. The implications for the study of the evolution of learning are discussed. ---------------------------------- 2. A Preliminary Investigation on Extending Evolutionary Programming to Include Self-Adaptation on Finite State Machines Lawrence J. Fogel and David B. Fogel, Natural Selection Inc., 1591 Calle De Cinco, La Jolla, CA 92037 and Peter J. Angeline, Loral Federal Systems, Rt. 17C, Mail Drop 0210, Owego, NY 13827 pp. 387-398 Keywords: evolutionary programming, evolutionary computation, self-adaptation Abstract: Evolutionary programming was first offered as an alternative method for generating artificial intelligence. Experiments were offered in which finite state machines were used to predict time series with respect to an arbitrary payoff function. Mutations were imposed on the evolving machines such that each of the possible modes of variation were given equal probability. The current study investigates the use of self-adaptive methods of evolutionary programming on finite state machines. Each machine incorporates a coding for its structure and an additional set of parameters that determine in part how it will distribute new trials. Two methods for accomplishing this self-adaptation are implemented and tested on two simple prediction problems. The results appear to favor the use of such self-adaptive methods. ---------------------------------- 3. Analysis and Comparisons of Genetic Algorithm, Simulated Annealing, TABU Search, and Evolutionary Combination Algorithm Takashi Kido, Kazuo Takagi and Masakazu Nakanishi, Faculty of Science and Technology, Keio University, 3-14-1, Hiyoshi, Kohoku-ku, Yokohama, 223, Japan, E-mail: kido@math.keio.ac.jp, takagi@math.keio.ac.jp, czl@math.keio.ac.jp pp. 399-410 Keywords: genetic algorithms, hybrid search Abstract: This paper describes a hybrid search scheme for genetic algorithms (GAs). Since GA's weakness in local search is well-known, many GA applications combine genetic algorithms with a local search scheme. We have discovered that solution quality and stability can be improved further by using multiple local search strategies with GAs. In particular, we have combined GAs with two major local search mechanisms: TABU search and simulated annealing (SA). We have tested our approach (GA+SA+TABU) using a 100-city traveling salesman problem (TSP). The results indicate that solution quality and stability are superior than those of the GA, SA, or TABU alone. ---------------------------------- 4. Sacrificial Acts in Single Round Prisoner's Dilemma Masaru Tomita, Department of Enviromental Information, Keio University, 5322, Endo Fujisawa, 252 Japan, E-mail: mt@sfc.keio.ac.jp and Takashi Kido, Faculty of Science and Technology, Keio University, 3-14-1, Hiyoshi, Kohoku-ku, Yokohama, 223, Japan, E-mail: kido@math.keio.ac.jp pp. 411-416 Keywords: prisoner's dilemma, suicide acts Abstract: In this paper, we say an act is sacrificial if it hurts the actor as an individual but benefits his species as a whole. We will present two situations in single round prisoner's dilemma where such sacrificial acts are so important that species cannot survive without them. Those two cases are: Cooperate with Justice (CWJ) and Cooperate with Suicide (CWS). The former is an act to punish defectors. The latter is more counter-intuituve; an act to hurt himself for nothing. We will show by computer simulation that those two strategies survive in population dynamics, while the simple Cooperate (C) strategies cannot survive in the same situations. ---------------------------------- 5. From Evolutionary Computation to Computational Evolution Jari Vaario, Evolutionary Systems Department, ATR Human Information Processing Research Laboratories, 2-2 Hikari-dai, Seika-cho, Soraku-gun, Kyoto 619-02, Japan, Phone: +81 7749 5 1004, Fax: +81 7749 5 1008, E-mail: jari@hip.atr.co.jp pp. 417-434 Keywords: evolutionary computation, growing neural networks, adaptive behavior Abstract: This paper proposes that evolutionary computation be understood more like computational evolution, ie, to use the evolutionary process for construction, rather than for optimization. For this purpose simulation of the evolutionary process should include a non-linear developmental process from genotype to phenotype. In this developmental process the environment has an important role. In order to model the developmental process under the influence of the environment, a new modeling language is introduced. The focus of this language is on the interactions, which are considered to be the basic elements for environmental adaptation. The developed modeling method provides a complete simulation environment for the construction of organisms. The developed system aims to construct intelligence as adaptive behavior based on artificial neural networks. ---------------------------------- 6. An Experimental Study of N-Person Iterated Prisoner's Dilemma Games Xin Yao and Paul J. Darwen, Department of Computer Science, University College, The University of New South Wales, Australian Defence Force Academy, Canberra, ACT, Australia 2600 pp. 435-450 Keywords: genetic algorithms, prisoner's dilemma, learning, generalisatisation Abstract: The Iterated Prisoner's Dilemma game has been used extensively in the study of the evolution of cooperative behaviours in social and biological systems. There have been a lot of experimental studies on evolving strategies for 2-player Iterated Prisoner's Dilemma games (2IPD). However, there are many real world problems, especially many social and economic ones, which cannot be modelled by the 2IPD. The n-player Iterated Prisoner's Dilemma (NIPD) is a more realistic and general game which can model those problems. This paper presents two sets of experiments on evolving strategies for the NIPD. The first set of experiments examine the impact of the number of players in the NIPD on the evolution of cooperation in the group. Our experiments show that cooperation is less likely to emerge in a large group than in a small group. The second set of experiments study the generalisation ability of evolved strategies from the point of view of machine learning. Our experiments reveal the effect of changing the evolutionary environment of evolution on the generalisation ability of evolved strategies. ---------------------------------- 7. Benchmarking Indicates Relevance of Multiple Knowledge Matjaz Gams, Jozef Stefan Institute, Jamova 39, 61000 Ljubljana, Slovenia, Phone: +386 61 17 73 644, Fax: +386 61 219 677, E-mail: matjaz.gams@ijs.si pp. 451-466 Keywords: artificial intelligence, multiple knowledge, multistrategy learning Abstract: Over the last 7 years, detailed measurements of available learning systems were performed on two real-life medical domains with the purpose to verify the importance of multiple knowledge. The performance of the combined system GINESYS, consisting of an artificial intelligence and a statistical method, was analysed with and without multiple knowledge and by varying the number of learning examples, the amount of artificially added noise, the impurity and the error estimate functions. These measurements and those of other researchers indicate that multiple knowledge can provide essential improvements. Measurements also indicate that improvements over ``one-level'' or monostrategy knowledge representation representations are quite common in real-life noisy and incomplete domains. ---------------------------------- 8. Object Migration in Temporal Object-oriented Databases Angelo Montanari and Elisa Peressi, Dipartimento di Matematica e Informatica, Universita di Udine, Via Zanon, 6 - 33100 Udine, Italy, E-mail: [montana,peressi]@dimi.uniud.it and Barbara Pernici, Dipartimento di Elettronica e Informazione, Politecnico di Milano, Piazza Leonardo da Vinci, 32 - 20133 Milano, Italy, E-mail: pernici@elet.polimi.it pp. 467-484 Keywords: object-oriented databases, temporal databases, query languages, roles Abstract: The paper presents T-ORM (Temporal Objects with Roles Model), an object-oriented data model based on the concepts of class and role. In order to represent the evolution of real-world entities, T-ORM allows objects to change state, roles and class in their lifetime. In particular, it handles structural and behavioral changes that occur in objects when they migrate from a given class to another. First, the paper introduces the basic features of the T-ORM data model, emphasizing those related to object migration. Then, it presents the query and manipulation languages associated with T-ORM, focusing on the treatment of the temporal aspects of object evolution.} ---------------------------------- 9. A Novel Approach to Text Compression H. U. Khan, A. Mahmood and H. A. Fatmi, Dept. of Electronic and Electrical Engineering, King's College London, The Strand, London WC2R 2LS, U.K. E-mail: udee795@bay.cc.kcl.ac.uk pp. 485-490 Keywords: data compression, Lempel-Ziv coding, text compression Abstract: A novel algorithm for universal text compression is presented. The proposed algorithm is based on the concept that text compression may be regarded as a pattern recognition problem to which several non-analytical techniques, succh as Zadeh's fuzzy theories, could then be applied. The algorithm is compared with the well known Welch algorithm, and results are presented to demonstrate its superiority. ---------------------------------- 10. Recovering 3-D Motion and Structure Tarek M. Sobh, Department of Computer Science, University of Utah, Salt Lake City, UT 84112, U.S.A., E-mail: sobh@cs.utah.edu pp. 491-500 Keywords: computer vision, robotics, motion recovery, filtering, estimation, image flow Abstract: We discuss the problem of recovering the 3-D motion and structure. An algorithm for computing the camera motion and the orientation of planar surface is developed. It solves for the 3-D motion and structure iteratively given two successive image frames. We improve the solution by solving the ordinary differential equations which describe the evolution of motion and structure over time. The solution is further improved by exploiting the temporal coherence of 3-D motion. We develop the ordinary differential equations which describe the evolution of the parameters in terms of the current parameters and the measurements. The extended Kalman filter is then used to update the solution of the differential equations. The robustness of the entire process is demonstrated by the experiment with a moving camera which ``flies'' over a terrain model. This work also examines the possibilities for errors, mistakes and uncertainties in visual sensing systems. We suggest techniques for recovering these 3-D uncertainties, and present examples for determining the parametric evolution of a scene under uncertainty.