The Seventh International Conference on Genetic Algorithms

Preliminary Program & List of abstracts

Sunday, July 20

10:30 - 12:10, Room I. Theory I

Bit Representations with a Twist
Soraya B. Rana, and L. Darrell Whitley
When a function is mapped onto a bit representation, the structure of the fitness landscape can change dramatically. Techniques such as Delta Coding have tried to dynamically adapt the representation during the search process in hopes of making the problem easier for a genetic algorithm to solve. We introduce a new technique for changing between a restricted set of Gray representations during search; the method involves little overhead but can offer a significant performance improvement for a variety of search algorithms.

Predicting Speedups of Ideal Bounding Cases of Parallel Genetic Algorithms
Erick Cantu-Paz and David E. Goldberg
This paper presents models that predict the speedup of two cases that bound the possible topologies and migration rates of parallel genetic algorithms (GAs). The first bounding case is a parallel GA with completely isolated demes or subpopulations and for this case the model and the experiments show that the speedup is not very significant when more demes are used. The second model predicts the speedup when each deme communicates with every other deme using a maximal migration rate. For this case, we show that when the communication time is not constant there is a combination of number of demes and deme size that maximizes the speedup. The models are validated with computational experiments using functions of varying difficulty.

Tackling the Representation Problem by Stochastic Averaging
J. Ludvig, J. Hesser, and R. Männer
Not Yet Available

A Two-Dimensional Embedding of Graphs for Genetic Algorithms
Byung-Ro Moon and Chun-Kyung Kim
In graph problems, it is known that the performance of a genetic algorithm is affected by the chromosomal encoding of vertices. Although a number of linear encodings and two-dimensional encodings are known, linear encodings are believed to loose significant information contained in input graphs, and most existing two-dimensional encodings assume one-dimensional orderings as an intermediate step, which we suspect will still cause information loss in input graphs. This paper suggests a sophisticated two-dimensional chromosomal encoding heuristic which embeds the vertices directly in a two-dimensional matrix to better exploit the clustering information of graphs. For the heuristic, we devised a two-dimensional depth-first search where the chromosomal location is decided in parallel with a vertex selection based on the geographical attraction of the vertex-location pair relative to other vertices. Experimental results showed a visible improvement by the suggested heuristic.

10:30 - 12:10, Room II. Algorithmic Techniques I


A Continuous Genetic Algorithm for Global Optimization
Jinn-Moon Yang, Jorng-Tzong Horng, and Cheng-Yan Kao
Not Yet Available

A Real Coded Genetic Algorithm with an Explorer and an Exploiter Populations
Shigeyoshi Tsutsui, Ashish Ghosh, David Corne and Yoshiji Fujimoto
We introduce the concept of a bi-population scheme for real-coded GAs (bGAs) consisting of an explorer sub-GA and an exploiter sub-GA. The explorer sub-GA mainly performs global exploration of the search space, and incorporates a restart mechanism to help avoid being trapped at local optima. The exploiter sub-GA performs exploitation of fit local areas of the search space around the neighborhood of the best-so-far solution. Two types of bGA are presented, aimed at addressing different classes of problems. We also explore a method for adaptive load balancing between the two sub-GAs within a bGA, which uses knowledge of the number of restarts occurring in the explorer sub-GA. The proposed technique exhibits performance significantly superior to standard GAs on two complex highly multimodal problems.

A Real Coded Genetic Algorithm for Function Optimization Using Unimodal Normal Distributed Crossover
Isao Ono and Shigenobu Kobuyashi
This paper presents a new genetic algorithm for function optimization. In function optimization, it is said to be difficult to optimize functions that have strong epistasis among parameters. This is because many of the conventional genetic algorithms work without adapting to the landscape of functions. In this paper, we employ the real number vector representation and propose a new crossover named the unimodal normal distribution crossover (UNDX), considering epistasis among parameters. The UNDX can optimize functions efficiently by adapting the distribution of children to the landscape of functions. By applying the proposed method to several benchmark problems, we show its effectiveness.

An Extended Framework for Overcoming Premature Convergence
Kazuhiro Ohkura and Kanji Ueda
An approach to extending genetic algorithms for overcoming premature convergence, which is the source of GA-difficulties, is presented. The proposed method is based on the consideration that premature convergence cannot be avoided as long as a GA employs neo-Darwinism as its framework, due to a dilemma between the diversity maintenance in the population and the building block collection by crossovers. The proposed GA, which is named operon-GA, has new genetic mechanisms for growing building blocks in its evolutionary process. The diversity is maintained by the adaptive genetic changes due to the same genetic mechanisms. This extension is inspired by the neutral theory of molecular evolution and the genetic mechanisms in microbial organisms. Several computer simulations are conducted to discuss the evolving behaviors and the optimization performance for different GA-difficulties.

10:30 - 12:10, Room III. Biological Modeling

Effects of Contest Length and Noise on Reciprocal Altruism, Cooperation, and Payoffs in the Iterated Prisoner's Dilemma
Bryant A. Julstrom
The Iterated Prisoner's Dilemma (IPD) is a model of competition and cooperation in biological systems, including human societies. The tit-for-tat strategy for the IPD, which responds in kind to cooperation and to defection, is a model of reciprocal altruism in such systems. A genetic algorithm whose population consists of strategies for the IPD was run with various IPD contest lengths and levels of noise. In each generation, every strategy plays every other strategy in a round-robin tournament. The number of moves identical to those tit-for-tat would make and the number of cooperative moves indicate the levels of reciprocal altruism and of cooperation, respectively. The average payoff per play indicates each strategy's success. More interaction, in the form of longer IPD contests, results in higher levels of reciprocal altruism and cooperation as well as higher payoffs, though cooperating populations can be invaded by non-cooperating strategies. Noise, in the form of mistaken plays in the IPD, reduces the levels of reciprocal altruism and cooperation in the population and the average payoff per play of its strategies.

The Emergence of Emergence Distributions: Using Genetic Algorithms to Test Biological Theories
Keith Downing
We develop three different genetic-algorithm-based models for insect protandry, a natural phenomena wherein male larvae emerge into the pupal stage prior to females in order to maximize mating success. The distribution of male emergence times over the mating season often exhibits an ideal free distribution (IFD) such that each male mates with approximately the same number of females. Biological research indicates that (a) emergence times are genetically controlled, and (b) protandrous emergence distributions arise via natural selection. Using a simple binary encoding of emergence times, and assuming the basic prerequisite biological mechanisms for protandry, we combine individual-based population models with genetic algorithms to (a) show that IFDs are a natural consequence of fitness-proportionate selection in negative-frequency-dependent domains, and (b) provide numerical support to biomathematical theories of protandry.

DNA To Protein: Transformations And Their Possible Role In Linkage Learning
Hillol Kargupta and Brian Stafford
This paper first presents an extended perspective of linkage using basic concepts developed in the SEARCH framework (Kargupta, 1995, Kargupta and Goldberg, 1996) and identifies detection of ``appropriate'' patterns or relations among the search space members as the fundamental and broader objective of linkage learning. It then explores the computational role of gene-expression (DNA-->RNA-->Protein transformations) in evolutionary search for relations, using an algebraic approach. It offers strong evidence to support the hypothesis that the transformations in gene-expression form fitness invariant symmetry groups over alphabet tuples that may be used to capture patterns or relations among the search space members.

Toward Civilized Evolution: Developing Inhibitions
M. Sebag, M. Schoenauer, and C. Ravise
Most evolutionary algorithms concerned with a memory of evolution aim at memorizing and reusing the recipes of past successes (e.g. fruitful operators or fruitful mutation directions). The scheme proposed here follows the opposite track, and memorizes the past failures of evolution (unfit offspring) through a virtual individual termed the virtual loser. The underlying metaphor is that offspring should attempt to get further away from the virtual l oser than their parents. This is done by a new evolution operator, termed flee-mutation, as an alternative to standard recombination and mutation. Special attention is paid to adjusting the flee-mutation step size. Experiments on large sized problems validate this approach, and unexpectedly show that a constant flee-mutation step size over a population is desirable.

1:30 - 3:10, Room I. Theory II (Schemata & Building Blocks)

Cross-competition between Building Blocks - propagating information to subsequent generations
Cees H.M. van Kemenade
The building block hypothesis states that a genetic algorithm does optimization by combining low order building blocks. Cross-competition between building blocks can disturb this process. In this paper we give formal models of a canonical genetic algorithm, a generational genetic algorithm using tournament selection and elitist recombination. These models are compared by tracing their behavior on a sequence of problem instances where the cross-competition between building blocks increases. Cross-competition is shown to have a strong influence on the reliability of the canonical GA and the generational GA using tournament selection.

Conjugate Schema in Genetic Search
S. Kazadi
Functional optimization is profoundly affected by the use of specific encodings. In one encoding, a particular problem may be simple to undertake, while in another encoding, the problem may be intractible. Genetic algorithms solve optimization problems by making use of schema. By locating schema in a solution vector, the paradigm can settle on a solution that makes use of several schema and combines them via crossover.
We propose a generalization of this idea, the conjugate schema. Conjugate schema are disjoint subsets of the basis over which the fitness function may be wriiten as a sum of smaller dimensional functions. We find that if conjugate schema exist, this lowering of dimensionality is a direct consequence, yielding the motivation for finding bases containing a maximum number of conjugate schema. We find that in continuous problems, local conjugate schema are the eigenvectors of the absolute Hessian operator. We give several examples, and discuss the possible implications.

An Experimental Analysis of Schema Creation, Propagation and Disruption in Genetic Programming
Riccardo Poli and W.B. Langdon
In this paper we first review the main results in the theory of schemata in Genetic Programming (GP) and summarise a new GP schema theory which is based on a new definition of schema. Then we study the creation, propagation and disruption of this new form of schemata in real runs, for standard crossover, one-point crossover and selection only. Finally, we discuss these results in the light our GP schema theorem.

Phenotypical Building Blocks for Genetic Programming
Thomas Haynes
The theoretical foundations of genetic algorithms (GA) rest on the shoulders of the Schema Theorem, which states that the building blocks, highly fit compact subsets of the chromosome, are more likely to survive from one generation to the next. The theory of genetic programming (GP) is tenuous, borrowing heavily from that of GA. As the GP can be considered to be a GA operating on a tree structure, this borrowing is adequate for most. Part of the problem of tying GP theory to the schema theorem is in the identification of building blocks. We discuss how a building block can be represented in a GP chromosome and the characteristics of building blocks in GP chromosomes. We also present the clique detection domain for which the detection of building blocks is easier than in previous domains utilized in GP research. We illustrate how the clique detection domain facilitates the construction of fitness landscapes similar to those of the Royal Road functions in GA research.

1:30 - 3:10, Room II. Applications I

Edge Assembly Crossover: A High-power Genetic Algorithm for the Travelling Salesman Problem
Yuichi Nagata and Shigenobu Kobayashi
In this paper, we propose a powerful GA using the Edge Assembly Crossover (EAX) for the Traveling Salesman Problems (TSP). The EAX has two steps. First, under a relaxed constraint of the TSP that is the assignment relaxation, the EAX generates intermediate individuals by assembling only edges of parents. Second, intermediate individuals are modified so that the original constraints of the TSP are satisfied. The EAX has the following features. First, the EAX is excellent in characteristic preservation, because intermediate individuals are made of only edges of parents. Second, the EAX can generate a wide variety of children. Therefore, the EAX does not fall into the premature convergence. Third, the EAX incorporate heuristic information into its procedure. Applying the proposed GA to 21 symmetric TSPs (101-3,038 cities) and 9 asymmetric TSPs (48-443 cities) on the TSPLIB95, the GA succeeded in finding optimal solutions for all problems very efficiently.

Improving Heuristic Algorithms for the Travelling Salesman Problem by using a Genetic Algorithm to Perturb the Cities
Christine L. Valenzuela and L. P. Williams
Standard heuristic algorithms for the travelling salesman problem (TSP) frequently produce poor solutions in excess of 20% above the true optimum. In this paper we present some results which demonstrate the potential of genetic algorithms (GAs) to perturb city coordinates in such a way that standard heuristic algorithms are `fooled' into producing excellent solutions to the TSP. Initial results for our GA show that by using the greedy tour construction heuristic on perturbed coordinate sets it is possible to reliably obtain solutions to within two percent of the optimum for problems of several hundred cities.

A Genetic Local Search Approach to the Quadratic Assignment Problem
Peter Merz and Bernd Freisleben
Augmenting genetic algorithms with local search heuristics is a promising approach to the solution of combinatorial optimization problems. In this paper, a genetic local search approach to the quadratic assignment problem (QAP) is presented. New genetic operators for realizing the approach are described, and its performance is tested on various QAP instances containing between 30 and 256 facilities/locations. The results indicate that the proposed algorithm is able to arrive at high quality solutions in a relatively short time limit: for the largest publicly known problem instance, a new best solution could be found.

Optimization of Large Scale Parcel Distribution Systems by the Breeder Genetic Algorithm
Ulrich Bartling, Heinz Müehlenbein
The routing and scheduling of vehicles and their crews is an area of increasing importance. In this paper, we describe a large scale vehicle scheduling and routing problem which is of great importance to parcel distribution companies. We devise a Breeder Genetic Algorithm capable of dealing with up to 10,000 transportation requests to be serviced by an inhomogeneous fleet of vehicles within a 24 hour time interval. Each transportation request describes the task to move a loaded container from one depot to another. Since the depots do not send out the same number of containers than they receive, the amount of empty containers available at the depots has to be balanced. The optimization task, therefore, is twofold: determine appropriate balance tours and find a low cost schedule for the fleet of vehicles.

1:30 - 3:10, Room III. Applications II (Scheduling)

A Genetic Algorithm Approach to Dynamic Job Shop Scheduling Problems
Shyh-Chang Lin, Erik D. Goodman, and William F. Punch
This paper describes a genetic algorithm approach to the dynamic job shop scheduling problem with jobs arriving continually. Both deterministic and stochastic models of the dynamic problem were investigated. The objective functions examined were weighted flow time, maximum tardiness, weighted tardiness, weighted lateness, weighted number of tardy jobs, and weighted earliness plus weighted tardiness. In the stochastic model, we further tested the approach under various manufacturing environments with respect to the machine workload, imbalance of machine workload, and due date tightness. The results indicate that the approach performs well and is robust with regard to the objective function and the manufacturing environment in comparison with priority rule approaches.

Solving the Multiple Resource Constrained Project Scheduling Problem with Hybrid Genetic Algorithm
E. Ramat, G. Venturini, C. Lente, and M. Slimane
We present in this paper a new hybrid genetic approach for dealing with an NP-Hard problem, the multiple resource-constrained project scheduling problem (MRCPSP), where one must schedule activities of a project in order to minimize the project duration while avoiding conflict due to the limited resources. We introduce a new hybrid GA for this problem. Individuals are represented as matrix of precedence relations between activities. Genetic operators are based on Syswerda BSC (Syswerda 1993), where genes in the offsprings are set according to genes frequencies in the population, and on standard crossover where common genes to the parents are transmitted to the offsprings. Mutation is viewed in this context as a random pertubation of the genes frequencies. Heuristic rules for the MRCPSP are used to repair solutions that would not be feasible, and to seed the initial population. The efficiency of these rules is recorded and used in order to determine which rule to apply to repair a not feasible individual. In the experimental tests on artificial data, we show that our hybrid GA outperforms heuristic rules, and obtains even better results and in a shorter time than an efficient simulated annealing algorithm (Boctor 1996) for this problem.

A Genetic Algorithm Hybrid for Hierarchical Reactive Scheduling
Kwang Ryel Ryu, Junha Hwang, Hyung Rim Choi, and Kyu Kab Cho
This paper shows that a simple hybrid of genetic algorithm and local heuristic search provides a powerful means for solving a complex scheduling problem, by exploiting the global perspective of the genetic algorithm and the rapid convergence of the heuristic search. Unlike most other approaches where the hybridization is built into the genetic operations, our hybridization is built into the framework of our iterative improvement search method which works with hierarchical problem decomposition. The hierarchical problem decomposition enhances efficiency by significantly reducing the search, and thus compromising the optimality of the solution. However, the possible suboptimality induced by such a reduction is overcome by the iterative improvement search which is in fact a reactive process of repeated schedule modification using the genetic algorithm hybrid as an internal search engine. This added iteration demands little extra processing time because the genetic algorithm hybrid takes only a few iterations to converge to a schedule of excellent quality. Test results using real world data show that our approach clearly outperforms various other search schemes.

Effectiveness of Genetic Local Search Algorithms
Hisao Ishibuchi, Tadahiko Murata and Shigemitsu Tomioka
In this paper, we examine the performance of a genetic local search algorithm (GLS), which is a hybrid algorithm of a local search (LS) and a genetic algorithm (GA). We modify the local search procedure in order to improve the performance of the GLS. In the modified local search procedure, all the neighborhood solutions are not examined. We show two advantages of the GLS by computer simulations on flowshop scheduling problems. One is its high performance: the GLS outperforms the GA and a multi-start local search procedure (i.e., a multi-start hill-climbing algorithm). The other is the insensitivility of the performance with respect to parameter specifications: the performance of the GLS is not sensitive to the choice of parameter values such as the crossover probability and the mutation probability. By computer simulations, we also demonstrate the effectiveness of the modification of the local search procedure in the GLS.

3:40 - 5:20, Room I. Theory III (Landscape Analysis)

A Walsh Analysis of NK-Landscapes
Robert B. Heckendorn, and Darrell Whitley
We use Walsh analysis to show NK-Landscapes form an extremely restricted set of functions out of the set of N bit functions that have interactions between K+1 or fewer bits. Several upper bounds on the extent of the coverage by NK-Landscapes are created based on theory developed in the paper.

An Information Measure of Landscapes
Vesselin Vassilev
This paper introduces a novel method for analysis of fitness landscapes. The underlying idea is to consider a fitness landscape as an ensemble of objects with different information characteristics. The method employs the Shannon's formula for measuring the information characteristics of the landscapes, namely the information content and the information stability. The information content is the entropy of the ensemble, and the information stability is obtained by filtering the information content out. The information characteristics of a range of landscapes with known correlation features are analyzed in an attempt to determine the influence of the landscape ruggedness on the information characteristics of the landscape. The experiments reveal that this approach is especially suitable for investigating the fitness landscape structure and has the following advantages: first, it introduces highly accurate measure of landscape ruggedness; second, it can be used to explore the modality of the landscape, and third, it can be effortlessly implemented.

Fitness Distance Correlation: An Instructive Counterexample
Lee Altenberg
Fitness distance correlation (FDC) has been offered as a summary statistic with apparent success in predicting the performance of genetic algorithms for global optimization. Here, a counterexample to Hamming-distance based FDC is examined for what it reveals about how GAs work. The counterexample is a fitness function that is `GA-easy' for global optimization, but which shows no relationship between fitness and Hamming distance from the global optimum. Fitness is a function that declines with the number of switches between 0 and 1 along the bitstring. The test function is `GA-easy', in that a GA using only single-point crossover can find the global optimum with a sample on the order of 10^-3 to 10^-9 of the points in the search space, an efficiency which increases with the size of the search space. This result confirms the suspicion that predictors for genetic algorithm performance are vulnerable if they are based on arbitrary properties of the search space, and not the actual dynamics of the genetic algorithm. The test function's solvability by a GA is accurately predicted, however, by another property---its evolvability, the probability that the genetic operator produces offspring that are fitter than their parents. It is also accurately predicted by FDC that uses not Hamming distance, but a distance measure defined by the crossover operator itself. A comparison is made between Hamming-distance based FDC analysis, crossover-distance based FDC analysis, evolvability analysis, and other methods of predicting GA performance.

Epistasis as a Basic Concept in Formal Landscape Analysis
B. Naudts, D. Suys and A. Verschoren
In this note we measure the interdependency of bits in the encoding of a fitness function using two different invariants. The first invariant, normalized epistasis, features a strong correlation with GA-hardness, as we illustrate here with generalized Royal Road functions. The second one, bit decidability, imitates epistasis, but has the avantage of being less difficult to calculate and approximate. Although it seems less powerful than epistasis, it is equally able to rank fitness functions according to their GA-hardness. We prove that the function class E3, which is similar to the class of NK(.,2) landscapes, is NP-equivalent. This class is based on a generalization of the concept of epistasis, and, because of the latter theorem, its structure is believed to be important in landscape analysis.

3:40 - 5:20, Room II. Applications III (Eng. Design)

Using Case Based Learning to Improve Genetic Algorithm Based Design Optimization
Khaled Rasheed and Haym Hirsh
In this paper we describe a method for improving genetic-algorithm-based optimization using case-based learning. The idea is to utilize the sequence of points explored during a search to guide further exploration. The proposed method is particularly suitable for continuous spaces with expensive evaluation functions, such as arise in engineering design. Empirical results in two engineering design domains and across different representations demonstrate that the proposed method can significantly improve the efficiency and reliability of the GA optimizer. Moreover, the results suggest that the modification makes the genetic algorithm less sensitive to poor choices of tuning parameters such as mutation rate.

Optimizing Engineering Designs Using a Combined Genetic Search
Kalyanmoy Deb and Mayank Goyal
In the optimization of engineering designs, traditional search and optimization methods face at least two difficulties: (i) since each is specialized in solving a particular type of problem, one method does not work well on different types of problems (ii) most of them are designed to work on continuous search spaces. Since different optimal engineering design problems give rise to objective and constraint functions of varying degree of nonlinearity and since most engineering design problems involve mixed variables (zero-one, discrete, and continuous), designers often face difficulty in using the traditional methods. In this paper, a combined genetic search technique (GeneAS) is suggested to solve mixed-integer programming problems often encountered in engineering design activities. GeneAS uses a combination of binary-coded and discrete variables, GeneAS restricts its search only to the permissible values of the variables. Thus, minimal search effort is required in converging to the optimum solution. The efficiency and ease of application of the proposed method are demonstrated by solving four different engineering design problems. Successful application of GeneAS in these problems suggests its use to other more complex engineering design problems.

Co-operative Evolutionary Strategies for Single Component Design
Ian C. Parmee and Harish D. Vekeria
The paper introduces the preliminary development of co-operative strategies that will enable the machine-based design of a single engineering component from initial configuration definition through to product realisation. The initial utilisation and comparison of basic evolutionary approaches leads to the introduction of high-performance evolutionary and adaptive search algorithms in order to improve performance within the high dimensional space that describes the component topology. A requirement for computationally expensive finite element analysis provokes the development of a sequential method for Dynamic Shape Refinement (DSR)[1] in an attempt to minimise calls to the fitness function and further improve solution performance. This leads to the utilisation of distributed, co-operative injection island strategies [2,3] and the development of strategies both for the dynamic refinement of component representation and the introduction / removal of differing search algorithms within the injection island architecture.

Using Genetic Algorithms with Local Search for Thin Film Metrology
Mark Land, John J. SiDorowich, and Richard K. Belew
Nondestructively determining the essential parameters that describe the structure of a semiconductor wafer is a challenging inverse problem. We describe use of an optical inspection technology and show that it can be used effectively in conjunction with genetic algorithms (GAs) and local optimization methods. We also use this concrete application to investigate GA/local search hybrids, compare them to simulated annealing, and investigate the value of the recombination operator relative to the ``random crossover'' variant suggested by T. Jones.

3:40 - 5:20, Room III. Applications IV

A Coevolutionary Genetic Algorithm for a Game Approach to Structural Optimization
Helio J.C. Barbosa
A coevolutionary genetic algorithm(GA) is proposed for solving structural optimization problems which are posed as antagonistic games between ``designer" and ``nature". The resulting min-max problem for the chosen payoff function f(x,y) is solved by evolving two populations each one using an independent GA. The GA running in population A(resp. B) is a minimization(resp. maximization) one and the individuals in this population encode values of the variable x(resp. y) belonging to the corresponding set X(resp. Y). The GA evolves for a certain number of generations on population A while the other population is kept ``frozen". Then the process is applied to population B and the cycle is repeated. The fitness computation is based on the payoff function f(x,y) and the fitness of each individual in one population depends on all individuals of the other population. The results of some numerical experiments are presented.

A Genetic Algorithm for Weight Selection in H-Infinity Control
D. C. Donha, D. S. Desanj, M. R. Katebi
This paper is concerned with the development of a procedure to calculate the parameters of the weighting functions used in H-infinity controller designs in order to achieve a desired system performance. A Genetic Algorithm is employed to search for suitable solutions. To cope with the imprecision and vagueness that arises in the description of objective functions and problem constraints concepts of the fuzzy logic are incorporated to the solution. A multi-objective fuzzy optimisation is stated and fuzzy convex decision-making is established. To evaluate the potentiality of the proposed method the tuning of an autopilot of a ship is investigated and compared to results obtained after a traditional design stage. Validation includes non-linear simulations of the ship dynamics.

Simultanous Feature Extraction and Selection Using a Masking Genetic Algorithm
Michael L. Raymer, William F. Punch, Eric D. Goodman, Paul C. Sanschagrin, and Leslie A. Kuhn
Statistical pattern recognition techniques classify objects in terms of a representative set of features. The selection of features to measure and include can have a significant effect on the cost and accuracy of an automated classifier. Our previous research has shown that a hybrid between a k-nearest-neighbors (knn) classifier and a genetic algorithm (GA) can achieve greater classification accuracy than a knn alone by weighting features during knn classification. Here we describe an extension to this approach which further enhances feature selection through the simultaneous optimization of feature weights and selection of key features by including a masking vector on the GA chromosome. We present the results of our GA/knn feature selection method on two important problems from biochemistry and medicine: identification of conserved water molecules bound to protein surfaces, and diagnosis of thyroid deficiency. By allowing the GA to explore the effect of eliminating a feature from the classification without losing the weight knowledge already learned, the feature masking technique allows the GA/knn to efficiently examine noisy, complex, and high-dimensionality datasets to find combinations of features which classify the data more accurately. In both biomedical applications, use of the feature masking technique resulted in equivalent or better accuracy than feature weighting alone, while using fewer features for the classification.

Messy Genetic Algorithms for Subset Feature Selection
D. Whitley, J.R. Beveridge, C. Guerra-Salcedo, and C. Graves
Not Yet Available

Monday, July 21st

10:30 - 12:10, Room I. Theory IV (Landscape Analysis)

A Condition for the Genotype-Phenotype Mapping: Causality
Bernhard Sendhoff, Martin Kreutz and Werner von Seelen
The appropriate choice of the genotype -> phenotype mapping in combination with the mutation operator is important for a successful evolutionary search process. We suggest a measure to quantify the quality of this combination by addressing the question whether the relation among distances is carried over from one space to the other. Search processes which do not destroy the neighbourhood structure are termed strongly causal. We apply the proposed measure to parameter and structure optimisation problems in order to assess the combination (mapping, mutation operator) and at the same time to be able to propose improved settings.

Genetic Algorithm Hardness Measures Applied to the Maximum Clique Problem
Terence Soule, and James A. Foster
We evaluated the effectiveness of five hardness measures (Davidor's epistasis measure [Davis 91], Jones and Forrest's fitness distance correlation [Jones and Forrest 95], graph size, graph density, and relative clique size) on 52 instances of the maximum clique problem. Although the results clearly showed that different graph characteristics greatly influenced the difficulty of the problem, none of the hardness measures effectively predicted the difficulty. For the epistasis and fitness distance correlation measures this is likely due to the nature and size of the sample population used to predict hardness. However, this raises the practical question of how samples should be chosen for larger problems.

A Wave Analysis of the Subset Sum Problem
Mark Jelasity
This paper introduces the wave model, a novel approach on analyzing the behavior of GAs. Our aim is to give techniques that have practical relevance and provide tools for improving the performance of the GA or for discovering simple and effective heuristics on certain problem classes. The wave analysis is the process of building wave models of problem instances of a problem class and extracting common features that characterize the problem class in question. A wave model is made of paths which are composed of subsets of the search space (features) that are relevant from the viewpoint of the search. The GA is described as a basicly sequential process; a wave motion along the paths that form the wave model. The method is demonstrated via an analysis of the NP-complete subset sum problem. Based on the analysis, problem specific GA modifications and a new heuristic will be suggested that outperform the original GA.

Genetic-Entropic Algorithm: An Application to NK-model and Statistical Analysis
Chang-Yong Lee and Seung Kee Han
We propose a new combinatorial optimization algorithm, genetic-entropic algorithm. This algorithm is based on the entropic sampling and the genetic algorithms. We, in particular, test the algorithm to minimize the fitness of the NK-model and compare the performance of the algorithm with the conventional genetic algorithms. The higher the K value, the better this algorithm performs. The characteristics of the proposed algorithm were analyzed in terms of the power spectrum analysis and a long range correlation was found.

10:30 - 12:10, Room II. Applications V

A Genetic Approach to Stable Matching
Brian Aldershof, and Olivia M. Carducci
We apply genetic algorithms to solve stable matching problems. In the simplest stable matching problem, we are given $n$ men and $n$ women and a ranking of the men by the women and of the women by the men. We seek to pair the men and women up so that no man and woman have an incentive to switch partners. A more difficult stable matching problem occurs when couples are allowed to express preferences over pairs of positions. Determining whether a stable match exists in this case is known to be $NP$-complete. We present a new class of genetic operators to find stable matches in both these cases. Our technique can be extended to a wide variety of similar stable matching problems.

Optimal Placements of Flexible Objects: An Evolutionary Programming Approach
S.K. Cheung, K.S. Leung, A. Albrecht, and C.K. Wong
This paper deals with the computation of equilibrium states for the placement of flexible objects within rigid boundaries. The problem is formulated on a grid structure with a fixed step size and for disks of a fixed diameter and the same material. The equilibrium states have to be calculated from uniformly distributed random initial placements. The final placements must ensure that any particular object is deformed only within the limit of elasticity of the material. A simulated annealing approach has been proposed and implemented in [2] to solve the problem. In this study, an alternative, novel hybrid two-phase algorithm with automatic detection of phase-change is proposed. The first phase is based on the evolutionary programming technique. Its main function is to produce an outline placement pattern of the final solution. The second phase further improves the outline pattern to reach the final equilibrium states by local optimization with adaptive step size based on the convergence of the sum of forces. The results are compared with those obtained in [2].

A Genetic Algorithm for Packing Three-Dimensional Non-Convex Objects Having Cavities and Holes
Ilkka Ikonen, William E. Biles, Anup Kumar, John C. Wissel, and Rammohan K. Ragade
In this paper we describe a unique three-dimensional bin-packing problem with non-convex parts having holes and cavities. Parts can be arranged in any orientation and location in the packing cylinder, where parts float like in a weightless environment. The solution approach utilizes a genetic algorithm (GA) which represents a solution for the problem as a three-dimensional chromosome. Each dimension in the chromosome is an ordered list of integers. As a function evaluator we have developed a packing simulator, which utilizes actual CAD file of parts, when packing parts. Part intersection calculations are based on methods common in computational geometry.

Car Suspension Design for Comfort Using Genetic Algorithm
Kalyanmoy Deb and Vikas Saxena
The primary function of a suspension system in a car is to isolate the road excitations experienced by the wheels from being transferred to the passengers. In this paper, we formulate the optimal car suspension design problem as two and three-dimensional dynamic models resulting in a number of differential equations governing the motion of the car. A number of objectives such as maximum bouncing, pitching, and rolling amplitude of the sprung mass are minimized subject to satisfying a number of constraints. The constraints mainly arise from comfort considerations, such as limiting the maximum vertical jerk experienced by the sprung mass, front and rear natural frequencies, and others. Even for a single constraint restricting the maximum vertical jerk, the feasible search space is found to be complex and multimodal. In solving this problem, a sequential quadratic programming technique fails to find a consistent solution. On the contrary, genetic algorithms (GAs) have consistently found near-optimal solutions for different objectives. The solutions obtained by GAs are also found to be better than a design used in one automobile industry. An optimal design formulation is also presented for ride comfort considerations as per the ISO standard and the suspension system found by GAs is an order of magnitude more comfortable compared to the existing design.

10:30 - 12:10, Room III. Applications VI (Network Design & Routing)

Robust Design of Multicommodity Integral Flow Networks
Stanislaw Kozdrowski, Michal Pioro, Jaroslaw Arabas, and Michal Szczesniak
The paper formulates a set of robust design tasks for uncapacitated multicommodity integral flow networks and discusses two stochastic discrete optimisation techniques for solving the problems: Evolutionary Algorithms and Simulated Allocation. In general, the tasks consist in finding the cheapest configuration of integral link capacities and integral flows, realising a fixed set of demands in the nominal state and in failure situations. The tasks and the proposed methods are illustrated by means of numerical examples of the telecommunication network design. The efficiency of the methods is compared with the mixed integer programming solution found by CPLEX.

Performance of Diploid Dominance with Genetically Synthesized Signal Processing Networks
F. Francis Greene
A methodology is described for synthesizing signal processing networks, which are used to solve a low- cost medical signal processing problem. The approach makes use of genetic algorithms and a new approach to diploid/dominance, which is tested using clinical patient data. Two reasons for an observed diploid efficiency increase are proposed: 1) Improvements due to the retention of relatively low-fitness, recessive building blocks and 2) Improvements due to the increased proportion and fast evaluation of non-viable, recessive genotypes.

A Genetic Algorithm Approach To Planning The Telecommunications Access Network
David Brittain, Jon Sims Williams, Chris McMahon
This paper describes an application of genetic algorithms to telecommunications network planning. A description is given of passive optical networks (PONs), a form of optical fibre network. These networks increase the difficulty of the network planning task as their topology is more complex than that of traditional copper cable based networks. Computer tools for network planning are increasingly becoming a requirement. A description is given of what is required of a network planning system. The planning problem is then formulated as an optimisation, and a representation described so that a genetic algorithm can be used as an optimiser. The performance of two operators, the edge recombination operator and the partial match crossover, are compared on the problem.

Wireless LAN Design using Hierarchical Genetic Algorithm
K. S. Tang, K. F. Man, and K. T. Ko
A new methodology for designing a Wireless Local Area Network(WLAN) is proposed in this paper. It is based on a Hierarchical Genetic Algorithm(HGA) formulation, which has the capability to solve multiobjective functions and discrete constraints. The Pareto ranking technique is applied to classify multiobjective functions which can be contradictory at times. Because of the uniqueness of this genetic approach, no mathematical guided routine is required for the optimization. It has been found from this study that HGA is ideally suited for WLAN design in that it not only satisfies the optimization of the skewed multiobjective functions and constraints, but also a precise number of minimum required base-stations can be identified. This added feature provides a design trade-off between cost and performance without requiring any extra efforts.

1:30 - 3:10, Room I. Algorithmic Techniques II

Alternative Random Initialization in Genetic Algorithms
Leila Kallel and Marc Schoenauer
Though unanimously recognized as a crucial step in Evolutionary Algorithms, initialization procedures have not been paid much attention so far. In bitstring Genetic Algorithms, for instance, the standard 0/1 equiprobable choice for every bit is rarely discussed, as the resulting distribution probability over the whole bitstring space is uniform. However, uniformity is relative to a measure on the search space. First, considering the measure given by the density of 1's, the Uniform Covering initialization procedure is naturally designed. Second, taking into account the probability of appearance of sequences of identical bits leads to design another alternative initialization procedure, the Homogeneous Block procedure. These procedures are compared with the standard initialization procedure on several problems. A priori comparison is achieved using Fitness-Distance Correlation. Actual experiments demonstrate the accuracy of these FDC-based comparisons, and emphasize the usefulness of the two proposed procedure.

The Effect of the Quality of Pseudo-Random Number Generators on the Performance of a Simple Genetic Algorithm
Mark M. Meysenburg, and James A. Foster
Genetic Algorithms (GAs) rely heavily on pseudorandom number generators (PRNGs). It is generally accepted that GA performance is not terribly sensitive to the quality of the PRNG used to drive it; however, this is not the case for all stochastic algorithms. Furthermore, this assumption has not been tested empirically for GAs. This paper reports the results of the first such tests we are aware of. We study the relationship between the relative quality of several PRNGs and the performance of a simple GA. Specifically, we examine the quality of twelve PRNGs, and compare the resulting performance of the SGA-C GA using an eleven function real-valued test suite. We conclude that PRNGs differ greatly in quality and speed, but that this does not significantly affect the ability of a simple GA optimizer. Selection strategies have a far greater impact.

Solving Similar Problems using Genetic Algorithms and Case-Based Memory
Sushil J. Louis, and J. Johnson
This paper uses genetic algorithms augmented with a case-based memory of past problem solving attempts to obtain better performance over time on sets of similar problems. When confronted with a problem we seed a genetic algorithm's initial population with solutions to similar, previously solved problems and the genetic algorithm then adapts its seeded population toward solving the current problem. We address the issue of selecting ``appropriate'' cases for injection and introduce a methodology for solving similar problems using genetic algorithms combined with case-based memory. Combinational circuit design serves as a structured testbed and provides insight that is used to validate the feasibility of our approach on other problems. Results indicate that seeding a small percentage of the population with ``appropriate'' cases improves performance on similar problems and that the combined system usually takes less time to provide a solution to a new problem as it gains experience (memory) from solving other similar problems.

Using Software Visualisation Technology to Help Evolutionary Algorithm Users Validate Their Solutions
Trevor D. Collins
Evolutionary Computation (EC) offers a variety of robust search techniques, each of which operate by means of an evolutionary-based search algorithm. In order to assess the quality of any solutions found, the user must understand the search path taken to discover them. Software Visualization is recommended as a useful technique for aiding such understanding. This paper gives an introduction to Software Visualization, reviews five existing techniques for presenting EC output data and presents a new technique suitable for visualizing EC search space. To conclude a summary table of all six visualization techniques, including comments and criticisms of each is given and the selection of appropriate visualization techniques is discussed. By presenting EC output data in a format that is easy to understand software visualization makes EC validation much simpler for the user.

1:30 - 3:10, Room II. Applications VII (Network Design & Routing)

Genetic Algorithm For Restrictive Channel Routing Problem
Vladimir N. Davidenko, Victor M. Kureichik, and Victor V. Miagkikh
This paper presents a genetic algorithm for to the restrictive channel routing problem. The major advance of this algorithm over other GA approaches to this problem is the use of horizontal and vertical constraints in the chromosome encoding which eliminates unfeasible solutions. This representation leads to lower complexity, because repairing procedures become unnecessary; in addition the search space is reduced greatly. Competitive experimental results proving the consistency of the approach were obtained.

An Adaptive Network Routing Algorithm Employing Path Genetic Operators
Masaharu Munetomo, Yoshiaki Takai, and Yoshiharu Sato
This paper presents a network routing algorithm employing genetic operators to create alternative routes in a routing table. Conventional routing algorithms send broadcast messages to exchange information on routing tables or link status in a network, which yields much communication overhead when the network becomes large. In the Genetic-Based Routing(GBR) algorithm we propose, we only manage a list of routes which is frequently used, and the alternative routes are generated by path genetic operators. The genetic operators generate alternative routes based on topological information of the network. The GBR algorithm distributes communication packets among the alternative routes in order to balance loads of links. We show the effectiveness of the routing algorithm through simulation experiments from viewpoints of mean arrival time and load of links in the network.

Local Search Genetic Algorithm for Optimization of Highly Reliable Communications Networks
Alice E. Smith, Berna Dengiz, Fulya Altiparmak
This paper presents a genetic algorithm (GA) with specialized encoding, initialization and local search genetic operators to optimize communication network topologies. This NP-hard problem is often highly constrained so that random initialization and standard genetic operators usually generate infeasible network architectures. Compounding this infeasibility issue is that the fitness function involves calculating the all-terminal reliability of the network, a calculation which is computationally expensive. Therefore, it is imperative that the search balances the need to thoroughly explore the boundary between feasible and infeasible networks, along with calculating fitness on only the most promising candidate networks. The algorithm results are compared to optimum results found by branch and bound and also to GA results without local search operators on a suite of 79 test problems. This GA strategy of employing bounds, simple heuristic checks and problem specific repair and local search operators can be used on other highly constrained combinatorial applications where numerous fitness calculations are prohibitive.

On-line Adaptation of Neural Networks with Evolvable Hardware
Masahiro Murakawa, Shuji Yoshizawa, Isamu Kajitani, and Tetsuya Higuchi This paper describes an evolvable hardware (EHW) system for generalized neural network learning. We have developed an ASIC VLSI chip, which is a building block to configure a scalable neural network hardware system. In our system, both the topology and the hidden layer node functions of a neural network mapped on the chips are dynamically changed using a genetic algorithm. Thus, the most desirable network topology and choice of node function (e.g. Gaussian or sigmoid) for a given application can be determined adaptively. This approach is particularly suited to applications requiring ability to cope with time-varying problems and real-time timing constraints. The chip consists of 15 Digital Signal Processors (DSPs), whose functions and interconnections are reconfigured dynamically according to the chromosomes of the genetic algorithm. Incorporation of local learning hardware increases the learning speed significantly. Simulation results on the prediction of chaotic data and adaptive equalization in digital mobile communication are also given. Our system is two orders of magnitude faster than a Sun SS20 on the corresponding problem.

1:30 - 3:10, Room III. Applications VIII (Multiple Criteria Decision Making)

A Non-Generational Genetic Algorithm for Multiobjective Optimization
Manuel Valenzuela-Rendon, and Eduardo Uresti-Charre
This paper describes a non-generational genetic algorithm for multiobjective optimization. The fitness of each individual in the population is calculated incrementally based on the degree in which it is dominated in the Pareto sense, or close to other individuals. The closeness of individuals is measured using a sharing function. The performance of the algorithm presented is compared to previous efforts on three multiobjective optimization problems of growing difficulty. The behavior of each algorithm is analyzed with regard to the visited search space, the quality of the final population attained, and the percentage of non-dominated individuals in the population through time. According to all these performance measures, the algorithm presented clearly outperforms previous efforts based on generational genetic algorithms.

The Neighborhood Constraint Method: A Genetic Algorithm-Based Multiobjective Optimization Technique
Daniel H. Loughlin and S. Ranjithan
Multiobjective genetic algorithms (MOGAs), including VEGA, Pareto optimal ranking, and niched-Pareto, allow the tradeoffs among design objectives to be estimated in a single optimization model run. This paper presents a new MOGA technique called the neighborhood constraint method (NCM) that uses a combination of a neighborhood selection technique and location-dependent constraints. NCM is demonstrated for a complex, real-world problem, where it is compared with an integer programming (IP) procedure, an iterative procedure using a single-objective (SO) GA, and implementations of a Pareto and hybrid niched-Pareto MOGA technique. Preliminary results suggest that NCM is computationally more efficient than the SO approach and may perform better than the other MOGA techniques at promoting and maintaining population diversity over the entire tradeoff curve, using relatively small population sizes. These results show that further evaluation and comparisons of NCM are warranted.

A Multiple Criteria Genetic Algorithm For Containership Loading
David S. Todd and P. Sen
Containership loading has commonly been tackled by skilled personnel drawing on many years of experience. More recently attempts have been made to aid the job of the stevedore by storing the details of containers loaded on board and calculating the current ship status. However, most attempts at automation have been restricted to purely heuristic methods producing a feasible, and not necessarily optimal, configuration under the supervision of a human planner. This paper outlines the development of a Multiple Criteria Genetic Algorithm (MCGA) and its application, with heuristic operators, to this large scale combinatorial problem. The results obtained from the MCGA software offer a choice of near optimal configurations and provide diagrams of the layout and associated data from which the most suitable loading for the vessel can be determined.

Using of Genetic Algorithms in Multicriteria Optimization to solve Industrial Problems
A. Gaspar Cunha, Pedro Oliveira, and Jose A. Covas
Not Yet Available

Tuesday, July 22nd

10:30 - 12:10, Room I. EC for Neural Networks

Culling and Teaching in Neuro-Evolution
Paul McQuesten and Risto Miikkulainen
The evolving population of neural nets contains information not only in terms of genes, but also in the collection of behaviors of the population members. Such information can be thought of as a kind of "culture" of the population. Two ways of exploiting that culture are explored in this paper: (1) Culling overlarge litters: Generate a large number of offspring with different crossovers, quickly evaluate them by comparing their performance to the population, and throw away those that appear poor. (2) Teaching: Use backpropagation to train offspring toward the performance of the population. Both techniques result in faster, more effective neuro-evolution, and they can be effectively combined, as is demonstrated on the inverted pendulum problem. Additional methods of cultural exploitation are possible and will be studied in future work. These results suggest that cultural exploitation is a powerful idea that allows leveraging several aspects of the genetic algorithm.

Evolving Neural Networks to Play Go
Norman Richards, David E. Moriarty, Paul McQuesten and Risto Miikulainen
Go is a difficult game for computers to master, and the best go programs are still weaker than the average human player. Since the traditional game playing techniques have proven inadequate, new approaches to computer go need to be studied. This paper presents a new approach to learning to play go. The SANE (Symbiotic, Adaptive Neuro-Evolution) method was used to evolve networks capable of playing go on small boards with no pre-programmed go knowledge. On a 9x9 go board, networks that were able to defeat a simple computer opponent were evolved within a few hundred generations. Most significantly, the networks exhibited several aspects of general go playing, which suggests the approach could scale up well.

Fitness Functions for the Optimization of Self-Organizing Maps
Daniel Polani
Kohonen's Self-Organizing Maps do not possess a canonical criterion that characterizes their organization state. Therefore, to be able to optimize e.g. their topology, adequate fitness criteria have to be found. The paper introduces, analyzes and discusses three criteria, a criterion derived from the quantization error, a Hebbian and a hybrid measure incorporating favourable properties of both mentioned criteria.

Evolution of Hopfield Model of Associative Memory by the Breeder Genetic Algorithm
Akira Imada and Keijiro Araki
We apply some variants of evolutionary computations to the Hopfield model of associative memory.In this paper, we use the Breeder Genetic Algorithm (BGA) to explore the optimal set of synaptic weights with respect to the storage capacity.We present the BGA has tremendous ability to search a solution in the massively multi-modal landscape of the synaptic weight space.The main goal of this study is to shed new light on the analysis of the Hopfield model of associative memory.We also expect the model to be used as a new test function of evolutionary computations.

10:30 - 12:10, Room II. Applications IX

Resolving Social Dilemmas using Genetic Algorithms: Initial Results
Neeraj Arora, Sandip Sen and Maria Gordin
A challenging problem for designers of agent societies is the problem of providing for public goods [Hardin 68]. Public goods are social benefits that can be accessed by individuals irrespective of their personal contributions. The dilemma for an individual agent is whether to be a contributor or to be an exploiter (enjoy benefits without contributing proportionately). It has been shown that selfish actions on the part of agents in a society can lead to ineffective social systems. In this paper, we evolve agent societies which are able to ``solve'' the dilemma. In one set of experiments, a genetic algorithm (GA) based approach is used to evolve agent societies that are faced with the Braess' paradox [Irvine 93]. In another scenario, agent groups adapt to effectively utilize a pair of resources. Encouraged by this initial explorations, we plan to investigate another variation of the GA that uses less global information than the current approach.

On Using Interactive Genetic Algorithms for Knowledge Discovery in Databases
G. Venturini, M. Slimane, F. Morin, and J.-P. Asselin de Beauville
This paper presents an new interactive algorithm for exploring numerical databases and discovering regularities, called Genetic Interactive Data Explorer (GIDE). GIDE, which is based on the specifications of a previous prototype (Venturini et al. 1996), uses the principles of interactive genetic algorithms to evolve, in cooperation with the domain expert, 2D graphical representations of the data. These 2D representations are encoded by two new variables represented as Lisp functions using the genetic programming paradigm. The domain expert selects interesting representations which can be further improved by the genetic algorithm. The interaction between the expert and the knowledge discovery tool has been greatly improved. Results are presented on several standard databases.

Option Pricing with Genetic Algorithms
Shu-Heng Chen and Woh-Chiang Lee
Not Yet Available

The Cryptanalysis of a Three Rotor Machine Using a Genetic Algorithm
Tony Bagnall, G.P. McKeown and V.J. Rayward-Smith
This paper describes a method of deciphering messages encrypted with rotor machines utilising a Genetic Algorithm to search the keyspace. A fitness measure based on the phi test for non randomness of text is described and the results show that an unknown three rotor machine can generally be cryptanalysed with about 4000 letters of ciphertext. The results are compared to those given using a previously published technique and found to be superior.

10:30 - 12:10, Room III. Applications X

Adaptive Combustion Balancing in Multiple Burner Boiling Using a Genetic Algorithm with Variable Range of Local Search
F. Vavak, K. Jukes and T.C. Fogarty
The automatic and continuous optimisation of combustion in large steam raising boilers using oxygen trim techniques is essential for energy efficient operation, as an optimal air-to-fuel ratio balance when energy losses are minimal is quickly lost in the harsh conditions found close to the combustion zone. However, in multiple burner systems this method is less effective since the waste gas in the flue reflects only the overall air-to-fuel ratio and not that of individual burners. The genetic algorithm based control system enables the air flow to each of the four burners of the installation to be continuously trimmed in order to achieve an optimal setting of the burners relative to each other using a single waste gas analyser. The control system implements a new genetic algorithm operator, the variable local search operator, which was designed with the aim of enabling the control systems to track the optima of the time-varying dynamic systems, whilst not being detrimental to their ability to provide sound results for the stationary environments. Results obtained so far from off-line tests, as well as from on-line experiments, suggest that the genetic algorithm based optimiser can significantly improve energy efficiency in real multiple burner systems.

Prediction of Nonlinear and Nonstationary Time-Series using Self-Adaptive Evolution Strategies with Individual Memory
Andre Neubauer
This paper presents the application of Evolutionary Computation techniques to the prediction of nonlinear and nonstationary stochastic signals - a task that arises e.g. in digital signal processing and time series analysis. Especially, the online adaptation of bilinear predictors with the help of a multi-membered (mu,lambda)-Evolution Strategy with self-adaptation of strategy parameters is treated. Special emphasis is given to the tracking capabilities of this specific Evolutionary Algorithm in nonstationary environments. The novel modifications of the standard (mu,lambda)-Evolution Strategy including the use of an individual memory component are detailed that are necessary to obtain a computationally efficient algorithm. Using the evolutionary adapted bilinear predictor as part of a bilinear prediction error filter, the proposed methodology is applied to the estimation of bilinear stochastic signal models. Experimental results are given that demonstrate the robustness and efficiency of the (mu,lambda)-Evolution Strategy in this digital signal processing application.

Evolutionary Statistics: Using a Genetic Algorithm and Model Reduction to Isolate Alternate Statistical Hypotheses of Experimental Data
David Rogers
Not Yet Available

Genetic Programming Estimates of Kolmogorov Complexity
I. De Falco, M. Conte, A. Della Cioppa, E. Tarantino and G. Tautteur
In this paper the problem of the Kolmogorov complexity related to binary strings is faced. We propose a Genetic Programming approach which consists in evolving a population of Lisp programs looking for the optimal program that generates a given string. This evolutionary approach has permited to overcome the intractable space and time difficulties occurring in methods which perform an approximation of the Kolmogorov complexity function. The experimental results are quite significant and also show interesting computational strategies so proving the effectiveness of the implemented technique.

1:30 - 3:10, Room I. Classifier Systems

A Study of the Generalization Capabilities of XCS
Pier Luca Lanzi
We analyze the generalization behavior of the XCS classifier system in environments in which only a few generalizations can be done. Experimental results presented in the paper evidence that the generalization mechanism of XCS can prevent it from learning even simple tasks in such environments. We present a new operator, named Specify, which contributes to the solution of this problem. XCS with the Specify operator, named XCSS, is compared to XCS in terms of performance and generalization capabilities in different types of environments. Experimental results show that XCSS can deal with a greater variety of environments and that it is more robust than XCS with respect to population size.

Discovering Risk of Disease with a Learning Classifier System
John H. Holmes
A learning classifier system, EpiCS, was used to derive a continuous measure of disease risk in a series of 250 individuals. Using the area under the receiver-operating characteristic curve, this measure was compared with the risk estimate derived for the same individuals by logistic regression. Over 20 training-testing trials, risk estimates derived by EpiCS were consistently more accurate (mean area=0.97, SD=0.01) than that derived by logistic regression (mean area=0.89, SD=0.02). The areas for the trials with minimum and maximum classification performance on testing were significantly greater (p=0.019 and p<0.001, respectively) than the area for the logistic regression curve. This investigation demonstrated the ability of a learning classifier system to produce output that is clinically meaningful in diagnostic classification.

A Network Genetic Algorithm for Concept Learning
C. Anglano, A. Giordana, G. Lo Bello L. Saitta
This paper presents a highly parallel genetic algorithm, designed for concept induction in propositional and First Order logics. The system exploits niches and species for learning multimodal concepts; it deeply differs from other systems because of the distributed architecture, which totally eliminates the concept of common memory. A first implementation of the system, designed for checking the possibility of exploiting parallel processing in network computer, is evaluated on standard benchmarks. The experimental results show that the system reaches good performance both with respect to the quality of the learned knowledge and with respect to the speed up on a workstation cluster.

Information Theory and NEXTPITCH: A Learning Classifier System
Francine Federman, Susan Fife Dorchak
NEXTPITCH, a learning classifier system using genetic algorithms, inductively learns to predict the next note in a childhood melody. Just as a listener develops expectations of what is to follow based on what has been heard, NEXTPITCH models human music learning by developing the rules that represent actual pitch transitions in the melody. This paper introduces our representation of music and our description of classifier formats. Our results are correlated by analyses of variance statistical routines. Information theory is used to partition melodies into classes so that we may examine the applicability of the results from one set of melodies to another.

1:30 - 3:10, Room II. Selection I

A New Selection Operator Dedicated to Speciation
A. Petrowski
Most niching methods create and maintain subpopulations of individuals characterized by some similarities. This paper defines the clearing procedure as a niching method that supplies the available resources of a niche only to the best individuals of each subpopulation: the winners. The clearing is naturally adapted to elitist strategies. Elitist clearing preserves good individuals from the destructive effects of genetic drift and reproduction operators, while maintaining a high level of diversity. These properties can dramatically improve the performance of genetic algorithms used for multimodal optimization. The basic clearing procedure selects the winners for reproduction. A standard selection operator then generates a competition between the winners from every subpopulation. This paper shows, through experiments, that this kind of over-selection is harmful. The concept of clearing based selection operator that ensures an equal number of offspring to every winner, regardless of its fitness is introduced. The experiments involve both easy and difficult multimodal function optimizations. They show that a clearing based selection operator can reduce the premature convergence rate, compared to a clearing procedure associated with an SUS selection.

Selection Schemes, Elitist Recombination, and Selection Intensity
Dirk Thierens
Selection algorithms used in evolutionary computation can be characterized according to two features: pure versus elitist selection schemes, and generational versus steady-state selection schemes. Recently the concept of selection intensity has been shown to be a convenient quantitative measure of the selection pressure of pure generational reproduction methods. Here we will discuss how this measure can also be used for elitist and steady-state selection mechanisms. A second goal of the paper is to generalise the Elitist Recombination genetic algorithm such that its selective pressure can be tuned, and to compute the selection intensity of the proposed method. Finally we conclude by computing the selection intensity of a reproductive scheme where both fitness biased parent selection and fitness biased replacement is used.

Takeover Time in a Noisy Environment
Yuji Sakamoto and David E. Goldberg
This paper discusses the effect of noise on takeover time for a genetic algorithm and proposes models of tournament selection in a noisy environment. The models are shown to predict the proportion of the individuals accurately. The models lead to the derivation of a simplified approximate equation for takeover time, and confirm the validity of the approximation for experiments.

Reflections on Bandit Problems and Selection Methods in Uncertain Environments
Günter Rudolph
The behavior of selection methods used in evolutionary algorithms that operate in uncertain environments is investigated in the framework of parametric two-armed bandit problems. Asymptotically optimal selection strategies are based on the sequential probability ratio test which is proved to perform up to four times better than analogous strategies based on the optimal fixed size sample test. A variant of local binary tournament selection in a spatially structured population is shown to behave like a sequential test provided that the population size is optimally adjusted.

1:30 - 3:10, Room III. Algorithmic Techniques III

Steady State Genetic Programming with Constrained Complexity Crossover Using Species Sub Population
Andrew H. Watson and Ian C. Parmee
This paper introduces an alternative approach to Genetic Programming (GP), which is based upon a steady state population utilising a novel constrained complexity crossover operator. This technique, called "DRAM-GP" (i.e. Distributed, Rapid, Attenuated Memory Genetic Programming), uses node complexity weightings as a basis for speciation. The population is decomposed into smaller sub-populations which communicate with each other through the action of crossover. The effectiveness of this method is demonstrated by successful application to Boolean concept formation and to symbolic regression problems. The results show that improved performance is possible with a dramatic reduction in population size and associated memory requirements.

Adaptation to Changing Environments by Means of the Memory Based Thermodynamical Genetic Algorithm
Naoki Mori, Seiji Imanishi, Hajime Kita, and Yoshikazu Nishikawa
Genetic algorithms (GAs) are the adaptation methods broadly applicable to many classes of problems. Adaptation to changing environments is one of the important class of such problems. Continuous search for the solutions by GA is the fundamental mechanism for adaptation, and therefore to avoid convergence by maintaining the diversity is an intrinsic requirement for successful search. The authors have proposed to utilize the thermodynamical genetic algorithms (TDGA), a genetic algorithm which maintains the diversity of the population by evaluating its entropy, for the problem of adaptation in changing environments. However, if the environmental change has a recurrent nature, a memory-based approach, i.e., to memorize the results of past adaptation and to retrieve them as candidates of the solution will be a smart strategy. K. Mori et al. have proposed such an adaptation algorithm inspired by the immune systems. In the present paper, the authors combine the memory-based approach with TDGA as an adaptation algorithm to changing environments. The adaptation ability of the proposed method is confirmed by computer simulations taking recurrently varying knapsack problems as examples.

Boundary Operators for Constrained Parameter Optimization Problems
Marc Schoenauer and Zbigniew Michalewicz
In this paper we continue an earlier study on boundary operators for constrained parameter optimization problems. The significance of this line of research is based on the observation that usually the global solution for many optimization problems lies on the boundary of the feasible region. Thus, for many constrained numerical optimization problems it might be beneficial to search just the boundary of the search space defined by a set of constraints (some other algorithm might be used for searching the interior of the search space, if activity of a constraint is not certain). We present a few boundary operators for a sphere and provide with their experimental evaluation.

Combining Constraint Processing and Genetic Algorithms for Constraint Satisfaction Problems
Elena Marchiori
This paper proposes a simple technique for solving binary constraint satisfaction problems (CSP's) over finite domains using genetic algorithms (GA's). The idea is to perform a constraint processing phase in order to transform the constraints of the CSP into a form suitable for a GA. The constraints are first manipulated in order to eliminate some variables, and then they are decomposed into constraints of one single form. Next, a suitable genetic algorithm is applied to the resulting CSP, that uses a probabilistic repair rule for dealing with the violation of primitive constraints. This approach is illustrated by means of two examples that are generally used for testing CSP techniques.

Wednesday, July 23rd

9:00 - 9:50, Room I. Theory V

A Random Function Based Framework for Evolutionary Algorithms
Laurence D. Merkle and Gary B. Lamont
Evolutionary algorithms (EAs) are stochastic, population-based algorithms inspired by the natural processes of recombination, mutation, and selection. EAs are often employed as optimum seeking techniques. A formal framework for EAs is proposed, in which evolutionary operators are viewed as mappings from parameter spaces to spaces of random functions. Formal definitions within this framework capture the distinguishing characteristics of the classes of recombination, mutation, and selection operators. A specific EA, the generalized fast messy genetic algorithm, is defined within the proposed framework.

Inductive Genetic Programming and Superposition of Fitness Landscapes
Vanio Slavov and Nikolay I. Nikolaev
This paper presents an approach to improving the performance of evolutionary algorithms. The evolutionary search effort is distributed among cooperating subpopulations that correspond to the substructures of the fitness landscape. The idea is to create such subpopulations that flow easily on the simple substructures of the complex fitness landscape structure. We claim that the search on a complex fitness landscape is facilitated if properly integrated with search on its simple components. This evolutionary structured search is applied for solving hard inductive learning tasks. The performance observed while inducing regular grammars from sets of boolean strings demonstrated that the approach mitigates the search difficulties.

9:00 - 9:50, Room II. Selection II

Double Selection vs. Single Selection in Diffusion Model GAs
Patricia M. White and Chrisila C. Pettey
Diffusion model genetic algorithms (GAs) can be divided into two categories---those with a formal selection step and those without a formal selection step. For those GAs without a formal selection step, survival of the fittest is insured by using a standard GA selection technique to select the parents for crossover. Those GAs that incorporate a formal selection step usually choose parents for crossover without consideration of the individual's fitness. The primary focus of research on diffusion model GAs has centered around comparing a particular diffusion model GA to a sequential GA. However, very little research has been done comparing the two categories of diffusion model GAs. This paper presents a study of the diffusion model GA with and without a formal selection step as well as a comparison of the 8 most common selection strategies found in diffusion model GAs. The experimental results indicate that diffusion model GAs with a formal selection step perform better than those without a formal selection step. Furthermore, the results indicate that a double selection technique---i.e., using a strong selection technique for both the selection step and the recombination step---performs better than a single selection technique. Also, surprisingly, the results indicate that using different selection strategies for the selection step and for choosing each parent in the recombination step performs better than using the same strategy for all three steps.

Formal Analysis of Local Selection Algorithms in a Spatially Structured Evolutionary Algorithm
Jayshree Sarma, and Kenneth De Jong
A critical part of the design of effective EAs is to obtain a proper balance between exploration and exploitation. A key element of this balance is the selection algorithm used. Although we have for some time now understood the relative differences between various selection methods for standard centralized EAs, our understanding of decentralized EAs has been less complete. In this paper we present analysis tools and results which provide considerable insight into the properties of various decentralized selection methods, including the selection pressures they induce. Understanding this permits a more informed choice of selection methods when designing and implementing spatially structured EAs.

9:00 - 9:50, Room III. Comparisons

Genetic Algorithms versus Experimental Methods: a case Study
Colin R. Reeves and Christine C. Wright
In this paper, we describe a case study in which GAs are compared with methods based on experimental design (ED). In a typical designed experiment, a fraction of the Universe of all possible solutions is chosen in a way that is thought to enable the identification of important factors (genes) and the levels (alleles) that these factors should be assigned in a candidate optimal solution.
ED requires a lot of human effort, and for this reason, ED has usually been restricted to fairly small problems. Recently, some suggestions have been made for increasing the range of problems to which ED ideas can be applied by automating some of the decisions customarily made by the experimenter.
Because a GA is also a means for conducting experiments, testing hypotheses and identifying candidate optimal solutions, it seems appropriate to compare the performance of a GA with ED-based approaches. Two versions of the ED-based method, known as Sequential Elimination of Levels (SEL), are implemented, together with a third version that we have developed. While a simple GA is outperformed by the new version of SEL, it is superior to the other two, and appears more robust than any of them.
All methods are tested in the context of a 6-factor, 5-level problem from engineering design. We report on a full analysis of the epistatic nature of this problem, carried out with the aim of gaining greater understanding of the type of problem for which these methods are suitable. We conclude that GAs are suitable for solving these types of problem, and should be considered by statisticians as an alternative to traditional ED methods.

A Comparison of Global and Local Search Methods in Drug Docking
Christopher D. Rosin, R. Scott Halliday, William E. Hart, and Richard K. Belew
Not Yet Available

10:30 - 12:10, Room I. Theory VI

Analysis in a Genetic Model
A. Bertoni, P. Campadelli, M. Carpentieri, and G. Grossi
In this paper a genetic model based on the operations of recombination and mutation is presented and analyzed. The equations of the deterministic dynamics in the thermodynamic limit are derived and, for a sufficiently small mutation rate, the attractors are characterized. The case of quadratic fitness functions is discussed: in this case the attractors are characterized in terms of equilibrium points of the Hopfield's networks with the fitness function as energy function. Experimental results that analyze the effect of small random mutation rate and that compare genetic and neural algorithms for the Max Cut problem are given.

Effective Degrees of Freedom in Genetic Algorithms and the Block Hypothesis
C. R. Stephens and H. Waelbroeck
An evolution equation for a population of strings evolving under the genetic operators: selection, mutation and crossover is derived. The corresponding equation describing the evolution of schematas is found by performing an exact coarse graining of this equation. In particular exact expressions for schemata reconstruction are derived which allows for a critical appraisal of the ``building-block hypothesis'' of genetic algorithms. A further coarse-graining is made by considering the contribution of all length-l schematas to the evolution of population observables such as fitness growth. As a test function for investigating the emergence of structure in the evolution the increase per generation of the in-schemata fitness averaged over all schematas of length l, Delta_l, is introduced. In finding solutions of the evolution equations we concentrate more on the effects of crossover, in particular we consider crossover in the context of Kauffman NK models. Analytic results for K=0 show that crossover gives a net positive contribution to the growth of large, fit schematas.

A Generalized Stationary Point Convergence Theory for Evolutionary Algorithms
William Hart
Not Yet Available

An Optimal Stop Criterion for Genetic Algorithms: A Bayesian Approach
Martin Hulin
It is a difficult and often neglected task to find a good stop criterion for genetic algorithms. This paper suggests a stop criterion based on Bayes' formula. The cost distribution of the last generation, is used as prior distribution, and after creation of the new generation a posterior distribution is derived by Bayes' formula. Based on this distribution the optimal cost value Copt is estimated as well as the number of generations the genetic algorithm will need to find. Given these estimations it is easy to calculate whether it is better to stop or to continue. Circuit partitioning serves as a test problem to compare the new stop criterion with others.

10:30 - 12:10, Room II. Algorithmic Techniques IV

Using Problem Generators to Explore the Effects of Epistasis
Kenneth A. De Jong, Mitchell A. Potter, and William M. Spears
In this paper we develop an empirical methodology for studying the behavior of evolutionary algorithms based on problem generators. We then describe three generators that can be used to study the effects of epistasis on the performance of EAs. Finally, we illustrate the use of these ideas in a preliminary exploration of the effects of epistasis on simple GAs.

Evolution of Graph-like Programs with Parallel Distributed Genetic Programming
Riccardo Poli
Parallel Distributed Genetic Programming (PDGP) is a new form of Genetic Programming (GP) suitable for the development of programs with a high degree of parallelism. Programs are represented in PDGP as graphs with nodes representing functions and terminals, and links representing the flow of control and results. The paper presents the representations, the operators and the interpreters used in PDGP, and describes experiments in which PDGP has been compared to standard GP.

Crossover Operator Biases: Exploiting the Population Distribution
Larry J. Eshelman, Keith E. Mathias and J. David Schaffer
Genetic algorithm (GA) search has been characterized as constructing better solutions by recombining basic building blocks from highly fit mates. However, it can also be characterized as using the variation in the population to constrain the search and bias the distribution of offspring (i.e., sampling bias). How we conceptualize GA search will affect how we design crossover operators. We analyze standard blend crossover (box-BLX) from the point of view of sampling bias and introduce a variant of BLX which implements a diagonally biased sampling (directional-BLX). This operator is designed for problems which require simultaneous directional changes in multiple parameters to make progress, something that traditional crossover operators have difficulty doing. We compare directional-BLX with box-BLX using both pool-wise and pair-wise mating on an array of problems, some known to be highly epistatic. The results show that 1) strong biases in the sampling induced by GA operators can lead to superior performance on identifiable classes of problems and 2) not all epistasis is the same, hinting that further study of the sampling biases among GA operators will lead to methods of characterizing problems.

Empirical Observations on the Roles of Crossover and Mutation
Annie S. Wu
There is a great deal of information to be gained from studying the details within a GA run. This paper investigates the roles of crossover and mutation by observing the actions and effects of individual occurrences of each genetic operation. The observations are compared with some of the common expectations of these operators.

10:30 - 12:10, Room III. Algorithmic Techniques V

Evolutionary Computation in Multi-agent Environments: Partners
Larry Bull
In this paper a key aspect of applying evolutionary computing techniques to multi-agent systems is examined: a comparison in the performance of various strategies for choosing evaluation part ners from coevolving populations is presented. Using the tuneable NKC model of multi-agent evolution and a generational genetic algorithm it is shown that a simple random partner strategy is as robust as more complex strategies over a wide range of system types. Equivalent steady state algorithms are found to perform better using a dis tributed strategy under most conditions. The effects of fitness sharing between the interacting individuals are then examined using the same models. It is shown that for both generational and steady state genetic algorithms a "current best" strategy proves most beneficial. Further it is shown that steady state algorithms perform better than generational algorithms in multi-agent

The Effects and Evolution of Tag-Mediated Selection of Partners in Populations Playing the Iterated Prisoner's Dilemma
Rick Riolo
A simple model of tag-mediated partner selection for agents playing the IPD is described. Experiments show that even very simple tag mechanisms alter the population dynamics dramatically, making it easier for populations to reach reciprocal cooperation, to maintain that cooperation, and to avoid periods of mutual defection. When tag-use was allowed to evolve endogenously, populations of tag-users emerged from non-tag-users at zero or low tag-search costs, but at higher costs tag-use could not be maintained.

Coevolving Cellular Automata: Be Aware of the Red Queen
Jan Paredis
This paper studies the use of coevolution to search for a cellular automaton (CA) solving the well-known density classification task. The Coevolutionary Genetic Algorithm (CGA) coevolves two non-interbreeding populations which interact as predator and prey. The main purpose of this paper is to illustrate some of the intricacies involved in the use of coevolution to solve a given task. Concepts from standard GA theory can be used to understand these problems. A simple modification is proposed to significantly increase the performance.

The Importance of Function Complexity in Regulating the Amount of Information Required to Guide Self-Adaptation in Cultural Algorithm
Robert G. Reynolds and ChanJin Chung
Cultural Algorithms are computational adaptive models which consist of a population and a belief space. Problem solving experience of individuals selected from the population space by the acceptance function is generalized and stored in the belief space. And then this knowledge can control the evolution of the population component by means of the influence function. In previous studies, the best performance was produced using knowledge to decide both step size and direction in most cases. Here we investigate the impact of different acceptance functions on the system's performance. Using a social analogy, this problem is similar to determining individuals who can contribute to build normative criteria in our society. Eight different acceptance functions are tested using a given influence function for solving 28 function optimization problems. Both deterministic and fuzzy acceptance functions were employed. The results, although preliminary, suggest that certain classes of problems require information about more individuals in a generation than others for a given influence function.

Models, Metaphors and Innovation
John Holland, Professor of EECS and of Psychology at UM, Co-chair (with Murray Gell-Mann) of the Santa Fe Institute Steering Committee (and member of the SFI Trustees Executive Committee), and Fellow of the World Economic Forum.
Humans get along in this world by creating models, from the very simple (the best route for driving home) to the very complex (Einstein's equations). The construction of such models requires the instincts of a cartoonist: One must emphasize or exaggerate carefully selected features, while dropping a plethora of details. The most creative models exhibit emergent properties, so that "what comes out is more than what goes in." Chess illustrates the point: It is defined by less than a dozen rules, yet it still rewards us with new insights and strategies after centuries of intensive study. More complicated models, such as axiom systems (Euclid's geometry) and sets of equations (Newton's, Maxwell's, Einstein's), have similar properties and are central to a deeper understanding of the world. This address will concern our ways of developing models and metaphors to innovate and deal with the unanticipated. "When we meane to build, We first survey the Plot, then draw the Modell." -- Shakespeare