Abstract-The non-linear complexity of evolutionary algorithms (EAs) make them a challenge to understand. The difficulty in performing detailed analyses of an EA is in sorting through the large amount of of data that can be generated in a single run. This paper describes a visualization tool that facilitates navigation through the details of an EA run. The visualization tool organizes and displays EA data at various levels of detail and allows for easy transitions between related pieces of data. The large numbers of complex, non-linear interactions that compose evolutionary algorithms (EAs) make them difficult to analyze and a challenge to understand. The most common methods of evaluating EAs, which include evolutionary programming, evolutionary strategies, and genetic algorithms (GAS), focus on overall performance and gross population statistics. Such methods include comparing the number of function evaluations required to find an acceptable solution, the quality of the solution found, or the rate of increase of the population fitness. The effectiveness of specific mechanisms such as crossover may be estimated by comparing the overall performance of an EA with and without that mechanism turned on. While such measurements are important and provide useful top-down information about EA runs, focusing only on this information could cause us to miss other important details. For example, several studies have investigated the effects of non-coding regions on GA performance. These regions were expected to improve performance by providing a buffer against the disruptive effects of crossover; however, comparisons revealed little difference in overall C A performance (Forrest & Mitchell, 1992; Wu & Lindsay, 1995) . A later study which examined the details of reproduction events found that non-coding regions did indeed reduce the disruptive effects of crossover in building blocks (Wu, Lindsay & Riolo, 1997). In fact, non-coding regions reduced crossover's total activity within building block regions, including crossover's ability to construct new building blocks. This decrease in construction appeared to cancel out any advantage gained from the expected decrease in disruption, resulting in little noticeable improvement in overall performance. Such complex, non-linear interactions exist in all types of EAs and suggest that, to fully understand how EAs work, we must examine not only the end result of EA runs but also the means to the end. The difficulty in performing such analyses lies in sorting through the large amount of data that can be generated in a single EA run. While all of the data from an EA run can easily be saved into files, accessing and interpreting such a large amount of information is no trivial task. The development of tools for sorting, organizing and displaying such databases could greatly facilitate the access and analysis of such data. Desirable capabilities of such tools include the ability to do the following: to examine individuals and their encodings in detail to trace the source and survival of building blocks or partial solutions to trace family trees to examine the effects of genetic operators to examine populations for convergence, speciation, etc. to trace gross population statistics and trends to move freely in time and through populations. One approach to this problem is off-line visualization. We have developed such a system, called VIS, to facilitate analysis of data from the Virtual Virus (VIV) project (Burke, De Jong, Grefenstette, Ramsey & Wu, 1999) . VIS takes advantage of the effectiveness of graphical representations and the flexibility of a "clickable" links to provide a navigation tool for accessing and displaying data. In the rest of this paper, we will summarize previous approaches to visualizing EAs and describe the VIS system and how it addresses some of the desired capabilities listed above. Though the examples shown in this paper are primarily from the VIV project which is based on a GA, the VIS program can easily be extended to support other EA data. Graphical visualization techniques are some of the simplest and at the same time most powerful methods for analyzing and communicating information (Tufte, 1983) . Well designed 0-7803-5536-9/99/$10.00 0 1999 IEEE 1419 graphical elements can convey large amounts of information in very concise and compact formats. In addition, the human vision system is extremely sensitive to graphical patterns, making graphical representations an extremely useful analysis tool. Visualization techniques have been used to study EAs both on-line and off-line. On-line systems allow users to closely follow and evaluate the progress of an EA and, in some cases, may allow users to interactively influence or guide the direction of evolution of the system (Collins, 1998; Jones, 1993) . Off-line systems use visualization techniques to display information about an EA run after it is complete and may allow the display of data from multiple times of a run and movement both forwards and backwards in the evolutionary process (Shine & Eick, 1997). The most basic displays that have been used include population data matrices which simply present an entire population in raw text format and two-dimensional plots of individual aspects of the population (such as best or average fitness) with respect to time. More complex techniques have focused on how to display more substantial information about entire populations. Examples include methods for displaying the distribution of the population in the solution space (Collins, 1997; Collins, 1998; Nassersharif, Ence & Au, 1994; Shine & Eick, 1997), allele frequencies (Collins, 1997; Wu & Lindsay, 1996) , the formation and variation of species (Spears, 1994) , and the ancestry of individuals (Spears, 1994 ) from generation to generation. The multi-dimensional nature of EA systems makes this a balancing act between the clarity of the display and the amount of information that can be included. VIS is an off-line visualization program developed to facilitate the examination and analysis of GA runs. This system was designed with two main goals in mind. Provide users with a tool with which they can examine the details of a C A run. The tool should provide easy access to desired information and easy transitions between related pieces of information. Develop novel methods and representations for displaying multi-dimensional data in a coherent and informative manner. VIS is organized as a collection of windows that display data at varying levels of resolution. Within these windows, VIS combines graphical and textual displays to allow users to view "snapshots" in time from a C A run, to examine specific individuals and populations from a run, and to navigate forwards and backwards through a run. "Clickable" elements in the displays link related pieces of information and allow users to easily move through time and among the populations of a GA run. Whereas most of the systems described in section 2 focus on ways to display the contents and evolution of entire populations and an EA'S progress in the solution space, the goal of the VIS tool is to make the data from individual GA runs available and easily accessible for observation and analysis. As a result, VIS focuses less on developing abstract representations which may average, interpolate, or otherwise lose details, and more on displaying complete information and providing navigation capabilities for moving from one part of a run to another. Because VIS is an off-line system, it is used only after a GA run is complete. Any C A run that is to be analyzed must generate a set of data files containing all of the information necessary for VIS to completely reconstruct the run. Details about files and formats are given in (Grefenstette, Burke, De Jong, Ramsey & Wu, 1997). The most important elements of a GA are the individuals from the C A populations. These individuals represent potential solutions to the problem to be solved and are typically encoded as strings of characters or values. The ability to examine the formation and structure of individuals in a C A is one of the main purposes for developing the VIS tool. As a result, how we represent or display individuals is very important. VIS is able to display the individuals of a C A run in both textual and graphical representations. Graphical representations can enhance analysis of textual information for several reasons. Color blocks or strips are both easier to distinguish and require less space than individual characters or letters (allowing display of longer individuals). In addition, similarities and differences in color strip patterns are very easy for human vision system to detect, facilitating the comparison of multiple individuals. VIS allows users to select from several different methods of representing individuals. While current representations focus on discrete alphabets -binary and multi-character -VIS can easily be extended to support floating-point representations and other problem-specific representations as needed. Table 1 shows examples of the currently available representations. The Genotype representation displays each individual as a string of characters. For binary alphabets, the characters will be either zero (0) or one (1). Alternative representations that use more than two values may be composed of other characters. This representation can be used for all alphabets. The Zebra representation works with binary alphabets and displays individuaIs as a series of black and white stripes. A black stripe represents a 0; a white stripe represents a 1. The Neopolitan representation also works with binary alphabets. This representation assigns one color to each pair of characters. There are four possible pairs of characters; an example color coding scheme would be: 0 0 = black, 11 = white, stripes. For example, the following color coding scheme was used for the VIV alphabet: A = blue, C = red, G = yellow, T = green. The Gene location works with problems in which groups of characters together compose building blocks or partial solutions. Each building block is displayed in a unique color on an individual. This representation is especially useful for tracing the construction, propagation, and disruption of building blocks. One of the most basic capabilities needed for studying GAS is easy and direct access to any individual of a run. Because individuals are the most basic elements of a CA, the ability to examine them in detail, in effect, gives us the ability to reconstruct events from any portion or all of a run. Because solutions are encoded as individuals, examining the fitness and composition of an individual essentially allows us to evaluate a GAS progress at a particular moment of a run. Parent and offspring comparisons can reveal the dynamics about reproduction events and how effectively information is constructed, propagated, and disrupted by various genetic operators. Easy access to the "family members" of an individual gives us the ability to trace the discovery and inheritance of information from generation to generation. VIS provides some of these capabilities with its Individual window. An Individual window displays all relevant data associated with a given individual. Two formats are available: the Data format displays the vital statistics for an individual and the Family format displays a graphical representation of a complete family (an individual, its parents, and its offspring). Figure 1 shows an example of the Data format. The following information is included in this display.  In addition to examining individuals in isolation, it is also important to understand how individuals relate to other individuals in the population. Well designed graphical displays of a population can facilitate the detection of patterns or trends in the population that may suggest convergence or speciation. Overall characteristics such as diversity, convergence, and level of speciation can be important indicators of a CA's progress.  window for that generation. The Consensus format, shown --in Figure 7 , displays statistics and a "consensus" individual for each generation of a run. The consensus individual shows the most common ordering of genes in a population. In addition to providing access to very specific details from a run, VIS also displays data relating to an entire run. Tracking gross population and run statistics provide a general idea of The VIS tool is an off-line visualization program developed to facilitate the examination and analysis of GAS. Instead of focusing solely on methods for displaying a GA's progress in a solution space, VIS concentrates on ways to make all of the details of a run available and easily accessible. This tool allows users to examine snapshots of a CA run and investigate questions such as how were the pieces of a solution assembled, when and why did a population converge, and what are the immediate effects of variation of parameters such as population size or selection method. We have found VIS to be an extremely useful tool for examining details of a C A run beyond the average and best fitness for each population. VIS allows us to f0cu.s in on specific details of interest, keeping related data easily accessible and all other data available. It has been especially useful in situations where we would otherwise need to print out unmanageable amounts of data just to find or examine a few specific examples. The VIS tool played an integral role in our analyses of experiments from the VIV project. Using VIS, we were able to find specific examples to verify that, given the opportunity, a CA will retain backup copies of useful information and use this backup information if primary information is disrupted. In addition, we were able to examine the convergence of populations and the effects of genetic operators in detail. Full descriptions of these studies can be found in (Burke, De Jong, Grefenstette, Ramsey & Wu, 1999; . We have also found the VIS tool to be extremely useful for developmental and verification purposes. In the development of new CA programs and applications, using a visualization tool to verify new representations and methods can be significantly easier and less time consuming than the alternative of printing out and verifying information on paper or on screen. In essence, VIS can be thought of as a debugger, but at the algorithmic level rather than the code level. Future work on this project includes the continued development of effective displays of individual and population data and interactive sorting capabilities. We would like to extend graphical representations of individuals to support additional problem representations, including floating point values and possibly two-dimensional structural representations. In addition, we also plan to add automated data collection and statistical analysis options to collect, calculate, and plot data such as the number of offspring generated or the discovery and loss of partial solutions over entire runs or populations. Acknowledgment
A tool developed by Wu et al. REF ) called VIS to analyze the details of an Evolutionary Algorithm (EA) run.
Visual analysis of evolutionary algorithms
Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406)
Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406)
Computer Science