A Comprehensive Overview of the Applications of Artificial Life Kyung-Joong Kim Sung-Bae Cho*
Department of Computer Science Yonsei University 134 Shinchon-dong, Sudaemoon-ku Seoul 120-749 Korea kjkim@cs.yonsei.ac.kr sbcho@cs.yonsei.ac.kr Abstract We review the applications of artificial life (ALife), the creation of synthetic life on computers to study, simulate, and understand living systems. The definition and features of ALife are shown by application studies. ALife application fields treated include robot control, robot manufacturing, practical robots, computer graphics, natural phenomenon modeling, entertainment, games, music, economics, Internet, information processing, industrial design, simulation software, electronics, security, data mining, and telecommunications. In order to show the status of ALife application research, this review primarily features a survey of about 180 ALife application articles rather than a selected representation of a few articles. Evolutionary computation is the most popular method for designing such applications, but recently swarm intelligence, artificial immune network, and agent-based modeling have also produced results. Applications were initially restricted to the robotics and computer graphics, but presently, many different applications in engineering areas are of interest. Keywords Artificial life, perspective, simulation, software, hardware, evolution 1 Introduction There are two types of modeling approaches for studying natural phenomena: the top-down approach (involving a complicated, centralized controller that makes decisions based on access to all aspects of the global state), and the bottom-up approach, which is based on parallel, distributed networks of relatively simple, low-level agents that simultaneously interact with each other. Most traditional artificial intelligence (AI) research focuses on the former approach. However, to obtain the most adaptive and complex behaviors from intelligent applications that assist humans, such behaviors might be designed using the bottom-up approach. It is difficult, or even impossible, to model lifelike behaviors using the traditional AI approach. Usually, complex behaviors such as schooling of fishes, detection of unknown attack patterns, and evolution of economic markets can be modeled as the local interaction of agents whose decisions are based on the information about, and that directly affect, only their own local environment. There are many complex applications, not only in the robotics, computer graphics, and engineering fields, but also in the educational and artistic fields. It is too tedious and sometimes impossible to design such applications using the top-down approach. Artificial life (also known as ALife) is an interdisciplinary study of life and lifelike processes that uses a synthetic methodolog y [1]. It complements traditional biological sciences concerned with the analysis of living organisms and finds the mechanisms of evolutionary processes for automatic
*Corresponding author. n 2006 Massachusetts Institute of Technolog y Artificial Life 12: 153 ­ 182 (2006) K.-J. Kim and S.-B. Cho A Comprehensive Overview of the Applications of Artificial Life design and creation of artifacts. A general property of ALife is that the whole system's behavior is represented only indirectly, and arises out of interactions of individuals with each other. In this context, known as the philosophy of decentralized architecture, we can say that ALife shares important similarities with some new trends in AI, including connectionism [2], multi-agent AI [3], and evolutionary computation [4]. According to Bedau [1], there are three branches of ALife. Soft ALife creates simulations or other purely digital constructions that exhibit lifelike behavior, hard ALife produces hardware implementations of lifelike systems, and wet ALife synthesizes living systems out of biochemical substances. For this overview, ALife articles of the soft and hard branches were surveyed, because most articles that apply to ALife fall under one of those two rubrics. Scientific terms used in this review include the following. Evolutionary computation ( EC ) is a biologically inspired general computational concept that uses genetic algorithms (GAs), evolutionary strategies (ESs), genetic programming (GP), and evolutionary programming (EP). Interactive evolutionary computation (IEC) is the technolog y in which EC optimizes the target systems according to subjective human evaluation expressed as fitness values for system outputs. Agent-based modeling (AM) uses multiple agents whose decisions are entirely based on local information in order to simulate real-world situations. Cellular automata (CAs) are discrete dynamical systems that specify behavior in terms of a local relation. Ant colony optimization (ACO) is a meta-heuristic that uses artificial ants to find solutions to difficult combinatorial optimization problems. The methodologies of ALife are described in Section 2, and an ALife application survey follows in Section 3. Finally, we discuss the future of ALife application research. 2 Basic Methodologies of ALife Recently, the concept of emergence has arisen in research that involves nonlinear dynamics, ALife, complex systems, and behavior-based robotics. Emergence in a system, broadly, is said to refer to properties or behaviors that cannot easily be predicted from internal properties. Examples of this are flocking behaviors in simulated birds from a set of three simple steering behaviors [5], patterns in the game of life [6, pp. 817 ­850], and the highway pattern displayed by the artificial ant [7]. It is this concept of emergence that highlights the nature of ALife research. Emergence is exhibited by a collection of interacting entities whose global behaviors cannot be reduced to a simple aggregate of the individual contributions of the entities. Conventional methods in AI have to struggle to reveal and explain emergence, because they are generally reductionist. That is, they reduce systems to constituent subsystems and then study them in isolation (the top-down approach). In contrast, ALife adopts the bottom-up approach which starts with a collection of entities exhibiting simple and well-understood behavior and then synthesizes more complex systems. Technologies in ALife research include CAs, the Lindenmayer system (L-system), GAs, and neural networks. Their relations are diagrammed in Figure 1. EC is a model of machine learning derived from the evolution process in nature. There are several different types of evolutionary computations: GAs, EP, and ESs. They are all populationbased search algorithms. Different representation or encoding schemes and search operators differentiate ECs. For example, GAs normally use crossover and mutation as search operators, while EP only uses mutation [8]. GAs, the most popular method, are executed by creating a population of individuals that are represented by strings. The individuals in the population go through an evolutionary process in which individuals compete for resources in the environment. Stronger individuals are more likely to survive and propagate their genetic material to offspring. Interactive EC is such a technique whose fitness function is replaced by a human user [9]. EC is used for learning, adaptation, and searching, and there are many hybrid methodologies for synergism. In agent-based modeling, global behaviors emerge from the local interaction of agents, and the states of the agents change in response to their neighborhoods' states. It is assumed that each agent can decide to learn a new skill and to cooperate with other agents.
154 Artificial Life Volume 12, Number 1 K. J. Kim and S. B. Cho A Comprehensive Overview of the Applications of Artificial Life Figure 1. Relations of the ALife methodologies (CA = cellular automata, IEC = interactive evolutionary computation, EC = evolutionary computation, NN = neural network, ACO = ant colony optimization). Multi-agent systems include methodologies derived from the behavior of insects. More recently, scientists have been turning to insects for ideas that can be used for heuristics. Ant colony optimization (ACO) is a meta-heuristic that uses artificial ants to find solutions to difficult combinatorial optimization problems [13]. Particle swarm optimization is based on the behavior of bees. Each agent has its own advantages, and a colony of agents produces the optimal solution. The direction of movement of each agent is determined as the vector sum of directional vectors for the personal best, global best, and current motion. ACO is a popular method, and has many applications, including electronics, industrial design, chemical process design, and data mining. Particle swarm optimization has relatively few applications. A new swarm intelligence algorithm has been developed by Abbass, based on the haploid-diploid genetic breeding of honeybees and known as honeybees optimization (HBO), for solving combinatorial optimization problems [14 ­17]. The L-system is frequently used to model trees, flowers, feathers, and roots of plants in computer graphics. It is a set of simple grammar rules, which generates complex sentences from primitive components. Although the rules are simple, the generated objects are very similar to the real structures. An NN can be considered as a mapping device between input and output sets. Considerable literature has described NN-fuzzy, fuzzy-GA, GA-NN, and NN-fuzzy-GA mappings. When trying to solve a real-world problem with NNs, we are faced with a large variety of learning algorithms and a vast selection of possible network architectures. Recent theoretical and experimental studies indicate that we can improve the performance of NNs by considering methods for combining them. CAs' basic function is computation --there is no autonomy. A CA is a population of interacting cells, each of which is itself a computer (automaton) that can be made to represent many kinds of complex behaviors by building appropriate rules into it [10 ­ 12]. CAs can model ecological systems or the behavior of insects, and can also be used for image processing and neural network construction [12]. CAs can consist of a 1D string of cells, a 2D grid, or a 3D solid. Usually the cells are arranged in a simple rectangular grid. CAs have three essential features: state, neighborhood, and program. The state is a variable that takes a discrete value for each cell. It can be either a number or a property. A cell's neighborhood is the set of cells that it interacts with. In a grid these are normally the closest cells. The program is the set of rules that define how the state changes in response to the current state and those of the neighborhood cells [10].
Artificial Life Volume 12, Number 1 155 K.-J. Kim and S.-B. Cho A Comprehensive Overview of the Applications of Artificial Life Figure 2. Statistics of application articles in artificial life by field and year: robotics. 3 ALife Applications The first conference on artificial life, in 1989, where the term ``artificial life'' was coined, gave recognition to ALife as a field in its own right [18]. Statistics on application articles of ALife are shown in Figures 2, 3, 4, and 5. In general, two major research streams developed during the 1990s from the interdisciplinary cooperation of researchers interested in bio-inspired computing. A practical goal of ALife can be defined as finding a mechanism for an evolutionary process to be used in the automatic design and creation of artifacts [19], and there are many contributions by computer science researchers to implement artifacts. Drawing upon some of the computing techniques inspired by social insects such as ants [20], several mobile-agent-based paradigms were designed to solve control and routing problems in telecommunications and networking [21]. The natural immune system is also a source of inspiration for developing intelligent methodologies Figure 3. Statistics of application articles in artificial life by field and year: graphics. 156 Artificial Life Volume 12, Number 1 K. J. Kim and S. B. Cho A Comprehensive Overview of the Applications of Artificial Life Figure 4. Statistics of application articles in artificial life by field and year: social. toward problem solving [22]. Neural networks have been widely used in optimization, regression, and prediction problems. Figure 6 describes the increase of the number of application articles. This recent rapid increase is related to similar publications in mechanics, product design, and chemical processes. Figure 7 shows the proportion of each application area. Robot control is the most active research area in ALife. The robotics, graphics, social, and engineering areas are 22%, 21%, 21%, and 36%, respectively. Statistics on application articles about ALife by methodolog y are shown in Figure 8. Some of the articles are not counted for the statistics because they are surveys or introductory articles without technical depth. Also, if the amount of research is relatively small for the specific methodolog y, the research is ignored. The figure shows the percentages of methodolog y usage. EC-related methodologies (EC, EC with NN, EC with L-system, and interactive EC) occupy about 50% of the research. Figure 9 shows the portion of the methodologies by categories. Of the robotics research, Figure 5. Statistics of application articles in artificial life by field and year: engineering. Artificial Life Volume 12, Number 1 157 K.-J. Kim and S.-B. Cho A Comprehensive Overview of the Applications of Artificial Life Figure 6. The number of application articles by year and application category. EC-related methodologies occupy about 80%. Most notably, EC with NNs comprises 50% of all the research. This means that the hybrid method is the most popular approach for designing controllers for robots. In graphics, the proportion of EC-related methods is about 50%. It is remarkable that the methodologies related to L-systems comprise about 43% of the research. The L-system is the most popular representation for researchers who model natural phenomena such as growth of plants, feathers, and forests. In the social field (including social science and human-related applications such as entertainment and music), the agent-based model is dominant, because most articles in economics use agent-based modeling to simulate real-world economic phenomena. In engineering, the proportion of EC-related methods is relatively small. Swarm intelligence comprises 34% of the research because of the popularity of ACO. Statistics on application articles about ALife by methodolog y and year are shown in Figures 10 and 11. Figure 12 shows that EC-related methods are being used continually, with minor increases, and that methods other than EC have recently gained interest among researchers. 3.1 Robot Control Recently, the robotics area has relied heavily on EC for designing controllers. EC with NNs is especially dominant. This subsection includes evolving controllers, the combination of EC and NNs, Figure 7. The proportion of each application area. 158 Artificial Life Volume 12, Number 1 K. J. Kim and S. B. Cho
AS 4% IN 7% CA 4% A Comprehensive Overview of the Applications of Artificial Life
L-System 5% EC 20% SI 14% EC+NN 17% Agent-based 16% IEC 9% EC+ L-System 4% Figure 8. The percentage of each methodology usage (EC = evolutionary computation, NN = neural networks, IEC = interactive evolutionary computation, SI = swarm intelligence, CA = cellular automata, IN = artificial immune networks, and AS = action selection). coevolution, collective robotics, and CAs for robotics. Basically, designing controllers for robots is the main interest, but there are many other interesting issues in robotics. These include map building, planning, and human-robot interaction (HRI). CAs can be used for planning, and coevolution with humans can be the solution for HRI. Another issue of evolutionary robotics is how to minimize the difference between simulation results and results in the real world. Evolutionary robotics can be categorized by the method of evaluation, as depicted in Figure 13. Most ALife researchers try to obtain synthetic forms of organization inspired by biological principles of life [23]. Evolutionary robotics is the attempt to develop robots through a selforganized process based on artificial evolution [24 ­27]. An initial population of strings, each encoding the control system (and sometimes the morpholog y) of a robot, is randomly created and put in the environment. Each robot is then allowed to act according to a genetically specified controller, and its performance on various tasks is automatically evaluated. The fittest robots are allowed to reproduce by generating copies of their genotypes with the addition of changes introduced by some genetic operators. This process is repeated until a satisfactory specimen is born. From an engineering point of view, the main advantage of relying on self-organization is that the designer does not need to divide the desired behavior into simple basic behaviors to be implemented in separate layers of the robot control system [28]. In fact, it has been demonstrated that training or evolving robots in the real world is possible, but the number of trials needed to test the system discourages the use of physical robots during the training period. Miglino et al. proposed an accurate model of particular robot-environment dynamics by continuing the evolutionary process in the real-world environment for a few generations [29]. Meanwhile, embodied evolution (EE) avoids the pitfalls of the simulate-and-transfer method and allows the speedup of evaluation by utilizing parallelism [30]. Mataric and Cliff focused on the problems of evolving controllers for physically embodied and embedded systems that deal with the noise and uncertainty present in the world [31]. Brooks proposed GP to evolve programs to control physically embodied mobile robots [32]. Many researchers think that evolving NNs is the most promising approach, for a number of reasons [33 ­35]. NNs can easily exploit various forms of learning during their lifetime, and this learning process may speed up the evolutionary process. The whole evolutionary process may not be implemented in the real world, due to the high time complexity of the simulation, which causes a serious gap between simulated and real environments. Kondo et al. tried to overcome the problem
Artificial Life Volume 12, Number 1 159 K.-J. Kim and S.-B. Cho A Comprehensive Overview of the Applications of Artificial Life Figure 9. The proportion of each methodology for each category. by incorporating the concept of a dynamic rearrangement function of biological neural networks into evolutionary robotics [36]. Floreano et al. employed a different approach where synaptic strengths are not genetically specified and adaptation during life consists of Hebbian synaptic changes. For each synapse, the genetic string encodes four Hebbian rules, a learning rate, the sign, and the postsynaptic effect of the traveling signal [37]. Nelson et al. proposed evolutionary training of artificial NN controllers for competitive team game-playing behaviors by teams of real mobile robots [38, 39]. Lee and Cho developed a fuzzy logic controller for a mobile robot with a genetic algorithm in simulation environments [40], which analyzes the behavior of the controller from the perspective of observational emergence [41] and evolvability [42]. Coevolution (that is, the evolution of two or more competing populations with coupled fitness) has several features that may potentially enhance the power of adaptation of artificial evolution [43 ­ 46]. By using a combination of commercial off-the-shelf CAD/CAM simulation software and physical simulators constrained to correspond to real physical devices, Pollack et al. have been developing technolog y for the coevolution of body and brain [47]. A hybrid GP-GA framework is presented to evolve complete robot systems, including controllers and bodies, to achieve fitness-specified tasks [48]. Collective behavior as demonstrated by social insects is a form of decentralized control that may prove useful in controlling multiple robots [49, 50]. In some species of ants, workers cooperate to
160 Artificial Life Volume 12, Number 1 K. J. Kim and S. B. Cho A Comprehensive Overview of the Applications of Artificial Life Figure 10. Statistics on application articles in artificial life by methodology and year: EC-related methods. retrieve large prey. Usually, one ant finds prey, tries to move it, and, when unsuccessful, recruits friends through direct contact or chemical marking ( pheromone). When a group of ants tries to move large prey, the ants change position and alignment until the prey can be moved toward the nest. A robotic implementation of this phenomenon is described in [51]. Groups of robots using ant-inspired algorithms of decentralized control techniques foraged more efficiently and maintained higher levels of group energ y than single robots [52]. The CA model is a powerful instrument in many applications. Marchese proposed a reactive path-planning algorithm for a non-holonomic mobile robot on multilayered cellular automata [53]. CAM-Brain is a model to create neural networks based on CA, and finally aims at developing an artificial brain. The original CAM-Brain model has been modified to solve problems caused by evolving the model to control a mobile robot [54]. The biological immune system has features such as self-organization and learning ability. Based on these facts, researchers have been trying to construct engineering models of the immune system, and apply these to robotics [55, 56]. Meyer has Figure 11. Statistics on application articles in artificial life by methodologies and year: methods other than EC. Artificial Life Volume 12, Number 1 161 K.-J. Kim and S.-B. Cho
25
EC A Comprehensive Overview of the Applications of Artificial Life Methods with the exception of EC 20 The number of papers 15 10 5 0 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 Figure 12. The number of application articles by methodologies and year. proposed an integration of several specific mechanisms that underlie the adaptive behaviors of animals into a coherent function model using biological knowledge [57]. 3.2 Robot Manufacturing: Practical Robot Because most research in the robot control area is conducted in the laboratory, many unsolved problems have appeared in commercial application. The GOLEM project is the most interesting example of solving such problems in using a 3D solid printing tool for rapid manufacturing. The GOLEM project is an attempt to extend evolutionary techniques into the physical world by evolving diverse electromechanical machines (robots) that can be fabricated automatically [58 ­ 60]. To date, robots are still designed laboriously and constructed by teams of human engineers at great cost. Few robots are available, because these costs must be absorbed through mass production that is currently Figure 13. The categorization of evolutionary robotics. The basic idea is from [30]. 162 Artificial Life Volume 12, Number 1 K. J. Kim and S. B. Cho A Comprehensive Overview of the Applications of Artificial Life justified only for toys, weapons, and industrial systems like automatic teller machines. Lipson and Pollack reported a set of experiments in which simple electromechanical systems evolve to yield physical locomoting machines [59]. They achieve autonomy of design and construction using evolution in a limited-universe physical simulation coupled to off-the-shelf rapid manufacturing technolog y. Using 3D solid printing, the evolved creatures then replicate automatically into reality, where they faithfully reproduce the performance of their virtual ancestors [60]. Also, they use a generative representation, which can reuse components in regular and hierarchical ways, providing a systematic way to create more complex modules from simpler ones [61]. Some researchers tackle more practical problems. It is still not clear if the evolutionary approach for building autonomous robots is adequate for real-life problems. A mobile robot has been successfully trained to keep clear an arena surrounded by walls by locating, recognizing, and grasping garbage objects and taking them outside the arena. The controller of the robot was evolved in simulation and then downloaded and tested on the real robot [62]. A decentralized method is proposed for controlling a homogeneous swarm of autonomous mobile robots that collectively transport a single palletized load [63]. Mondada et al. have proposed a new robotic concept, called SWARM-BOT, based on a swarm of small and simple autonomous mobile robots called S-BOTs [64]. S-BOTs have a particular assembling capability that allows them to connect physically to other S-BOTs and form a bigger robot entity, the SWARM-BOT. By taking advantage of the collective and distributed approaches, this concept achieves resistance to failure even in challenging environment conditions such as rough terrain. 3.3 Computer Graphics This subsection deals with designing virtual characters, 2D image generation, and animation. Because these products are difficult to evaluate objectively, interactive evolutionary computation is used to design them. However, subjective evaluation by each user leads to practical problems such as fatigue, difficulty in maintaining large populations, and small numbers of generations. To solve these problems, Lee et al. proposed the direct manipulation method [65]. This allows the user to manipulate individuals directly instead of using evolutionary operators as an interface to each individual. In the interactive evolutionary system, the cost of evaluating each individual is relatively high, and it is difficult to maintain large populations. To solve this problem, Kim and Cho propose a hybrid genetic algorithm based on clustering, which considerably reduces the number of evaluations without any loss of performance [66]. The algorithm divides the whole population into several clusters and evaluates only one representative from each cluster. The fitness values of other individuals are estimated indirectly from the representative fitness values. Knowledge-based encoding includes removing impractical solutions, using partial information about the final solution, focusing on a specific search space, and encoding in a modular manner [67]. Figure 14 shows a Figure 14. A framework for improving interactive evolutionary computation. Artificial Life Volume 12, Number 1 163 K.-J. Kim and S.-B. Cho A Comprehensive Overview of the Applications of Artificial Life framework for improving interactive evolutionary computation. Cho and Lee have developed an image retrieval system based on human preference and emotion by using an interactive GA [83, 84]. It searches the images not only with explicit queries, but also with implicit queries such as ``cheerful expression'' and ``gloomy expression.'' Gritz and Hahn used interactive genetic programming to automatically derive control programs for the agents [85, 86]. ALife concepts play a central role in the construction of advanced graphics models for image synthesis, animation, multimedia, and virtual reality [68]. Virtual creatures play an increasingly important role in computer graphics as special effects and background characters. The artificial evolution of such creatures potentially offers some relief from the difficult and time-consuming task of specifying morphologies and behaviors. Additionally, a hybrid of the L-system and evolution is widely used in computer graphics. Hornby and Pollack have proposed a system that uses L-systems to encode an EA for creating virtual creatures [69]. Karl Sims has developed a novel system for creating virtual creatures that move and behave in simulated 3D physical worlds. When simulated evolutions are performed with populations of competing creatures, interesting and diverse strategies and counter-strategies emerge [70, 71]. The work of Sims has been extended by many authors [74 ­ 76]. Teo and Abbass investigated the use of a self-adaptive Pareto evolutionary multi-objective approach for evolving the controllers of virtual embodied organisms [72] and the underlying fitness landscape of the controller's search space [73]. Gentropy is a genetic programming system that evolves into 2D procedural textures [80]. It synthesizes textures by combining mathematical and image manipulation functions into formulas. Most evolutionary art programs are interactive, and require the user to repeatedly choose the best images from a displayed generation. Gentropy uses an unsupervised approach, where one or more target texture images are supplied to the system. Hornby and Pollack have demonstrated the ability of evolving L-systems to design tables [81]. Kato et al. proposed a novel method that enables automatic modeling of virtual cities [82]. The method makes use of the L-system to generate road networks, and the genetic algorithm to generate building layouts. The tradeoff between control and automation is a well-known problem in computer-assisted character animation. It has been the goal of many researchers to allow the automation of agents while still allowing the developer to change the actions of the agents. Despite this, most professionals still use key framing, because the automatic motion control schemes have not allowed for sufficiently specific control over the agents. Miranda et al. have proposed evolving finite state machines for the behavioral control of characters [87]. Lim and Thalmann have argued that tinkering with existing models may be a more practical approach than starting from scratch in some applications of evolutionary techniques, and they validate this point with respect to setting parameters of a humanwalk model for computer animation [88]. Animation through the numerical simulation of physicsbased graphics models offers unsurpassed realism, but it can be computationally demanding. While the dynamic nature of typical movie stunts makes them dangerous to perform, it also makes them attractive candidates for the application of physics-based animation. Faloutsos et al. created an autonomous virtual stuntman [77]. A comprehensive ALife approach to the realistic modeling of animals for virtual reality is emerging [78]. An extensive survey of synthetic actors can be found in [79]. Grzeszczuk et al. proposed the NeuroAnimator, a novel approach to creating physically realistic animation that exploits NNs [89]. A rich environment from which interesting strategies can be extracted by evolved creatures is needed, and Parisy and Schlick have proposed a simulation framework that can be used as a starting point for the development of dynamic behavioral systems [90]. 3.4 Natural Phenomenon Modeling This subsection deals with CA-based modeling, ecological modeling such as that of fish behavior, flock behavior modeling and its applications, and applications of L-systems. The usage of L-systems is relatively large in this area. It has been extended to agricultural modeling such as that of cotton and
164 Artificial Life Volume 12, Number 1 K. J. Kim and S. B. Cho A Comprehensive Overview of the Applications of Artificial Life plant-eating insects, and to explaining the evolution of fossils. Because Reynolds' flocking algorithm [5] generates realistic simulations of thousands of animals, it is frequently used in movies. A hybrid of the EA and the L-system, and a hybrid of the EA and Reynolds' flocking algorithm, are examples of synergism. Simple CA models offer methods of incorporating computer modeling in the study of natural phenomena. Malamud and Turcotte proposed three different CA models: the forest fire, slider block, and sandpile models [91]. Each of these three models is associated with an important natural hazard that exhibits similar behavior. The forest-fire model is associated with actual forest fires and wildfires, the slider-block model with earthquakes, and the sandpile model with landslides. Computational plant models, or virtual plants, are increasingly seen as useful tools for comprehending complex relationships between gene function, plant physiolog y, plant development, and the resulting plant forms [92]. Artificial fish are autonomous agents whose appearance and complicated group interactions are as faithful as possible to nature's own. Terzopoulos et al. proposed a bottom-up, computational approach in which they modeled not just form and superficial appearance, but also the basic physics of the animal and its environment, the means of locomotion, the perception of its world, and its behavior [93, 94]. Stephens et al. created artificial fish for real-time interactive virtual worlds aimed at desktop environments with hardware 3D support [95]. The artificial fish can move, sense, and think. A high-performance computer simulation of Europe's largest aquarium lets its human visitors interact with 25 species and about 1,000 individual creatures and plants [96]. Miller has modeled legless figures such as snakes and worms as mass-spring systems [97]. The aggregate motion of a flock of birds, a herd of land animals, or a school of fish is a beautiful and familiar part of the natural world. But this type of complex motion was rarely seen in computer animation in 1987. Reynolds developed an approach based on simulation as an alternative to scripting the path of each bird individually [98]. The aggregate motion of the simulated flock is created by a distributed behavioral model; the birds choose their own courses. Behavioral animation techniques that are similar to Reynolds' have been used to create special effects in movies like Batman Returns (animated flocks of bats), The Lion King (herds of wildebeests), and Mulan (crowd scenes). Oboshi et al. [99] and Birt and Shaw [100] designed the mechanism of fish-school behavior using EC. Production systems and L-grammars, as introduced by Prusinkiewicz and Lindenmayer, are very popular tools for creating images [101, 102]. The theory of L-systems has been mainly used for the visualization of the development and growth of living organisms like plants, trees, and cells. Jacob uses evolutionary algorithms for inferring L-systems encoding structures with specified characteristics [103, 104]. In the Wildwood project, genetic algorithms are applied to a simplified L-system representation in order to generate ALife-style plants for virtual worlds [105]. Chen et al. used L-systems for realistic modeling and rendering of feathers and birds [106]. Prusinkiewicz et al. proposed a combined discrete-continuous model of plant development that integrates L-system-style productions and differential equations [107]. L-Cotton, an architectural model, captures morphological development and the emergent pyramidal shape of a cotton plant by expressing the process using the L-system formalism [108]. Interaction with the environment is a key factor affecting the development of plants and plant ecosystems. Mech and Prusinkiewicz extended the formalism of L-systems with the constructs needed to model bidirectional information exchanges between plants and their environment [109]. Hanan et al. modeled insect movement and development of 3D structures of a plant, allowing physiological processes associated with responses to being damaged by insects [110]. The form of trace fossils results from complex interactions among the organism's morpholog y. Computer-based study of morphologies utilizes L-systems and related methods for the generation of branching and 3D theoretical morphologies [111]. 3.5 Entertainment and Games Designing AI of computer game players is tedious and knowledge-oriented work. ALife can reduce the worker's load by allowing an evolutionary strateg y search and realistic modeling of human
Artificial Life Volume 12, Number 1 165 K.-J. Kim and S.-B. Cho A Comprehensive Overview of the Applications of Artificial Life behavior. Top-level computer programs that are developed by humans need expert knowledge to tune themselves, but a modern master-level checkers program can design its strateg y by coevolving with other computer programs. Rule-based AI cannot provide users with unexpected behavior patterns, and thus have trouble keeping their interest. Basically, an evolutionary strateg y search does not use much knowledge. It can also provide unexpected behavior patterns and continuously upgrade itself. Also, emergent properties of evolutionary algorithms allow game users to play creatively. From the perspective of optimization, evolutionary algorithms optimize multiple parameters of games. Recently, commercially available game software has used evolutionary algorithms for tuning the software's performance, and Evolutionary Checkers is now on sale. The goal of building an autonomous agent is as old as the field of AI itself. The ALife community initiated a radically different approach to this goal, which focuses on fast, reactive behavior rather than on knowledge and reasoning, as well as on adaptation and learning. One potential application area of agent research that has received surprisingly little interest so far is entertainment [112]. Artificial Life Interactive Video Environment (ALIVE) is a virtual environment that allows wireless full-body interaction between a human participant and a virtual world inhabited by animated autonomous agents. One of the goals of the ALIVE project is to demonstrate that virtual environments can offer a more emotional and evocative experience by allowing the participant to interact with animated characters [113]. An evolutionary algorithm is used to evolve the gait of the Sony entertainment robot AIBO [114 ­ 116]. The aim of the MICROB project (Making Intelligent Collective Robotics) is to investigate collective phenomena of organization in societies of robots. The application of a robot soccer team was chosen to investigate the design of robots that can organize themselves to achieve a collective task [117]. ALife technologies offer a way to build a better and more believable environment for computer games [118, 119]. Flocking has found its way into some of the more recent game releases. Half-life and Unreal both use flocking to control the movement of groups of fish, birds, and monsters to create a more realistic and natural environment. Creatures makes heavy use of a combination of chemistry-based GAs and NNs to control virtual pets, which learn how to speak, feed themselves, and interact with the player in a variety of ways [120]. Oidian Systems' Cloak, Dagger, and DNA is another game that uses genetic algorithms to produce smarter opponents. Recently, coevolution has been used to evolve a NN (called Anaconda) that, when coupled with a min-max search, can evaluate checkerboard positions and play at the level of a human expert [121]. 3.6 Music Music is also difficult to evaluate objectively, so interactive evolutionary computation is frequently used. This subsection shows how to represent music as gene code and how to automate the subjective evaluation procedure. It examines an interactive evolutionary system without any automatic evaluation effort, a system with automated evaluation, and a CA-based music system. The difference with the interactive evolutionary system, as applied to music, is that there are some attempts to develop an automated evaluator. The key methodologies for ALife music are interactive evolutionary computation and cellular automata. As with most problem-solving activities, musical tasks like composing, arranging, and improvising involve a great deal of searching. The evolutionary algorithm provides a powerful technique for searching large, often ill-behaved problem spaces. Interactive evolutionary computation, that is, evolutionary computation whose fitness function is provided by users, has been applied to music, art, and design. It is difficult to define the fitness function explicitly in these areas. GenJam is an interactive genetic algorithm-based model of a novice jazz musician learning to improvise [122]. Tokui and Iba proposed a new approach to music composition, more precisely the composition of rhythms, by means of interactive evolutionary computation [123]. The main feature of this method is combining GAs and GP. Unemi designed a support system for musical composition, named SBEAT3, based on simulated breeding [124, 125]. Each individual in the population is a short musical section of 16 beats, including 23 parts, 13 solos, 2 chords, and 8 percussions. Jacob used an
166 Artificial Life Volume 12, Number 1 K. J. Kim and S. B. Cho A Comprehensive Overview of the Applications of Artificial Life interactive genetic algorithm to produce a set of data filters that identify acceptable material from the output of a stochastic music generator [126]. Cho applied an interactive genetic algorithm to music information retrieval [127]. The Vox Populi system is designed to perform a series of sound experiments and eventually to be used as a tool for algorithmic composition [128]. Objectively defined criteria are used to evaluate the system's musical fitness, and a user may interfere in the fitness function through interface controls. Burton and Vladimirova proposed a means by which NN fitness evaluation can be applied to a GA that is applied to musical rhythm composition [129]. The GP-MUSIC system [130] is an interactive system that allows a user to evolve short musical sequences using interactive GP, and its extensions aim at making the system fully automated. Using this interactive technique, it was possible to generate pleasant tunes for runs of 20 individuals over 10 generations. As the user is the bottleneck in these kinds of interactive systems, the system takes rating data from a user's runs and uses it to train an NN-based automatic rater, or ``auto rater,'' which can replace the user in bigger runs. De la Puente et al. describe how grammatical evolution may be applied to the domain of automatic composition [131]. Alander compiled an indexed bibliography of GAs in arts and music [132]. Miranda employed cyclic, self-organizing CAs to control a sound synthesizer and used a patternpropagation CA to generate musical structures [133, 134]. Wada et al. proposed a novel method of producing a compressive and completely reproducible description of digital sound data by rule dynamics of CAs [135]. 3.7 Economics Decentralized market economies are complex adaptive systems, consisting of large numbers of adaptive agents involved in parallel local interactions. Agent-based computational economics (ACE) is the study of economies modeled as evolving systems of autonomous interacting agents [136 ­ 139]. Tassier and Menczer modeled a labor market that included referral networks using an agent-based simulation [140]. Agents could maximize their employment satisfaction by allocating resources to build friendship networks and to adjust search intensity. The multi-agent simulation system SWARM is employed to simulate and analyze economic concepts [141, 142]. Jennings et al. argued that agent technolog y can improve a company's efficiency by ensuring that businesses' activities are better scheduled, executed, monitored, and coordinated [143, 144]. Agent-based design and implementation philosophy has been used as a prototype for a business process management system for British Telecom ( BT ) [145]. Tsvetovatyy et al. proposed architecture for an agent-based virtual market that includes all the elements required to simulate a real market [146]. Kephart et al. investigated brokering agents' dynamic behavior, such as their price-setting mechanisms, in the context of a simple information filtering economy [147, 148]. An agent-based system simulates changes in predominant coordination mechanisms [149]. Inoue et al. optimized SCM (supply chain management) with HAL ( hyperartificial-life) middleware [150], which supports sequential GAs, asynchronous colony GAs, autonomous immigration GAs, and hyper-ALife algorithms for cluster computing. 3.8 Internet and Information Processing ALife might come to play an important role in the World Wide Web, both as a source of new algorithmic paradigms and as a source of inspiration for its future development [151]. Menczer et al. [152] proposed a model, inspired by evolving agents, and applied it to the problem of retrieving information from a large, distributed collection of documents. By competing for relevant documents, agents robustly adapted to their environment and were allocated to efficiently exploit shared resources. Sheth and Maes evolved a population of personalized information filtering agents to make a personalized selection of Usenet news messages for a particular user [153]. If an adaptive pool of antibodies can produce ``intelligent'' behavior, the power of computation can tackle the problem of preference matching and recommendation [154, 155]. Chao and Forrest proposed an approach to building an information immune system that eliminates undesirable information before it reaches the
Artificial Life Volume 12, Number 1 167 K.-J. Kim and S.-B. Cho A Comprehensive Overview of the Applications of Artificial Life user [156]. An artificial immune system detects different user access patterns on Web sites [157]. Ibanez et al. propose applying emergent collective behavior ideas to automatically program Internet multi-channel radio stations [158]. The proposed model simulates n virtual DJs (one per channel) playing songs at the same time. Every virtual DJ takes into account the songs played by the other ones, programming a sequence of songs whose order is also coherent. 3.9 Industrial Design This subsection is divided into two paragraphs, describing the colony-based approach and the others. Lucic and Teodorovic proposed applications of artificial bee and fuzzy ant systems in the field of traffic and transportation engineering [159]. The single-row machine layout problem concerns one of the most commonly used layout patterns, especially in flexible manufacturing systems. Solimanpur et al. used an ant algorithm to solve the problem [160]. Traffic congestion has become a major concern for many cities throughout the world. A colony-based traffic simulation system can provide helpful tools for engineers to plan traffic systems [161]. In order to solve the problem of the arrangement of letters on a computer keyboard, an algorithm based on ACO has been developed and applied [162]. Successful implementation of just-in-time ( JIT ) production systems is very important to modern manufacturing firms. McMullen used an ACO approach to solve multipleobjective JIT sequencing problems [163]. Batch processes have always been of considerable importance in chemical manufacturing due to their flexibility in processing multiple products and their ability to accommodate diverse operating conditions. Jayaraman et al. used the ACO approach for the optimal design of batch chemical processes [164]. Abbass et al. proposed a new technique for constructing programs through ACO using the tree adjunct grammar ( TAG) formalism [165]. Kim and Cho developed a more realistic design aid system for women's clothes by incorporating domain-specific knowledge into an interactive genetic algorithm [166]. Nishino et al. adopted interactive evolutionary computation to create 3D geometric models [167]. Yang et al. used a new emergent colonization algorithm for optimum design of short bearings [168]. In the design of engine mounts, after specifying the amount of shock-absorber fluid, design parameters can be varied in order to obtain a desired notch frequency and notch depth. Ahn et al. used a hybrid of a conventional ALife algorithm with a random taboo search (R-taboo) algorithm to solve that problem [169]. 3.10 Simulation Software Echo is a model of complex adaptive systems formulated by John Holland. It eliminates virtually all of the physical details of real systems and concentrates on a small set of primitive agent-agent and agent-environment interactions [170 ­ 172]. LEE ( Latent Energ y Environment ) is both an ALife model and a software tool to be used for simulations within the framework of that model [173, 174]. Yaeger developed a computer model of living organisms and ecolog y in PolyWorld [175], which attempts to bring together all the principal components of real living systems into a single artificial living system. It synthesizes genetics, physiologies and metabolisms, Hebbian learning in arbitrary neural networks, visual perception, and primitive behavior. PolyWorld can be downloaded from http://homepage.mac.com/larryy/larryy/PolyWorld.html. There have been a number of ecolog y models based on discrete lattices, but the Gecko system uses no lattice [176]. Agents have free range in two dimensions, and they co