IEEE ©2001 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

Return to Table of Contents


An Educational Genetic Algorithms Learning Tool

Ying-Hong Liao, and Chuen-Tsai Sun, Member, IEEE


Abstract - During the last thirty years there has been a rapidly growing interest in a field called Genetic Algorithms (GAs). The field is at a stage of tremendous growth as evidenced by the increasing number of conferences, workshops, and papers concerning it, as well as the emergence of a central journal for the field. With their great robustness, genetic algorithms  have proven to be a promising technique for many optimization, design, control, and machine learning applications. Students who take a GAs course study and implement a wide range of difference techniques of GAs. And practical implementation experience plays a very important role in learning computer relative courses. Herein, an educational genetic algorithm learning tool (EGALT) has been developed to help students facilitate GAs course. With the readily avaiailable tool students can reduce the mechanical programming aspect of learning and concentrate on principles alone. A friendly graphic user interface was established to help students operate and control not only the structural identification but also the parametric identification of GAs. It outlines how to implemented genetic algorithms, how to set parameters of different kinds of problems, and recommends a set of genetic algorithms, which were suggested in previous studies.


I. Introduction and Motivation

A. Introduction

During the last thirty years many optimization algorithms that imitate certain principles of nature have proven useful in various application domains. For example, the physical processes of material inspire simulated annealing [31]. Artificial neural networks [25] model the human nervous system. Ant systems take ant's pheromone as the communication system. Cellular automata simulate the emergence of cell interaction. There has also a rapidly growing field called Evolutionary Computation (EC) [29]. Three well-defined paradigms are included in the field: evolutionary strategies (ECs), introduced by Rechenberg [39], [40] and was further developed by Schwefel [44], [45]; evolutionary programming, developed by Fogel, Owens, and Walsh [12]; genetic algorithms, invented by John Holland [24]. The evolutionary computation community uses evolutionary algorithms (EAs) as a general term for describing those paradigms that use computational models to simulate evolutionary process. The paradigms all share the common conceptual base of simulating individual evolution via processes of selection, and certain genetic operators.

In detail, EAs maintain a population of individuals that evolve according to rules of selection and manipulation by genetic operators - crossover and mutation. The fitness of each individual is calculated, and selection focuses on high-fitness individuals, thus exploiting available fitness information. In addition, genetic crossover and mutation operators make changes of individual keeping the exploration actively. Although simplistic from a biologist's viewpoint, EAs are robust in solving very diverse and complex optimization and adaptation tasks.

This work focuses on the GA paradigm and tries to abstract essence of GAs. Since genetic algorithms have been applied in many diverse areas, such as function optimization [27], the traveling salesman problem [22], [18], scheduling [9], [48], evolving neural network design [23], [37], evolving computer programs [12], [10], [13], [33], [34], data analysis and predicting [38], fuzzy rule base design, system identification [32], computer vision [6], computer control [30], and machine learning [28], [20], [11]. Goldberg's book [14], Back's book[3], and Melanie Mitchell's book [36] provides detailed review of these applications.

B. Motivation

In the pursuit of machine intelligence, it makes sense to study the two natural archetypes of learning: the brain and evolution [2]. A genetic algorithm is as accurate a model of evolution as an artificial neural network is a model of the brain. The reason why we choose genetic algorithms as our research topic is twofold. First, the processes of natural evolution and natural genetics have been illuminated by a century of enormous progress in biology and molecular biology [17]. Second, with their great robustness, genetic algorithms have proven to be a promising technique for many optimization, design, control, and machine learning application.

As mentioned above, John Holland's simple GA provide only the abstract and the core of GA. When one wants to apply the GA to a particular problem, one faces a huge number of choices about how to proceed. In [36] Mitchell wrote:

Instructor introduces kinds of implementations and issues in GA courses. On account of limitation of time and the load on students, it's almost impossible for students to implement and test all kinds of implementations. Traditionally, teachers give only a couple of assignments. However, practical work experience plays a very important role in learning. But it is often difficult for students to practice all kinds of various implementations in GAs. Due to those collide, compromise must be taken to obtain best educational result. Herein, we consider developing a training (or simulation) tool to help students exercise as many studying cases as possible in short time. This tool must be simple for the sake of easy operations. Moreover, the tool must be general enough to cover as many typical problems as possible. By this tool students select system identifications (structural identification and parametric identification) they want to simulate, and start the simulation. During the simulation the program returns information about the running status immediately and students learns in the reaction between they and computer. The tool presented in this paper has been developed to allow students to practice with a good simulator.


II. An Overview of Genetic Algorithms

The original ideas of genetic algorithm (GAs) [24], which inspired by biological evolution are efficient domain independent search methods. That is, these methods could help us in effectively solving problem in different application domain. The goals of Holland's research have been twofold: First, to abstract and rigorously explain the adaptive processes of nature systems. Second, to design artificial systems software that retains the important mechanisms of nature system. These methods are capable of applying in many fields and perform well. From the viewpoint of AI research, Holland's method provides a good mechanism of learning.

GAs are population-based search techniques that maintain populations of potential solutions during searches. A string with a fixed bit-length usually represents a potential solution. In order to evaluate each potential solution, GAs need a payoff (or reward, objective) function that assigns scalar payoff to any particular solution. Once the representation scheme and evaluation function is determined, a GA can start searching. Initially, often at random, GAs create a certain number, called the population size, of strings to form the first generation. Next, the payoff function is used to evaluate each solution in this first generation. Better solutions obtain higher payoffs. Then, on the basis of these evaluations, some genetic operations are employed to generate the next generation. The procedures of evaluation and generation are iteratively performed until the optimal solution(s) is (are) found or the time allotted for computation ends [24], [19], [16]. Figure 1 represents the GA evolution flow.
 

Figure 1. Evolution flow of genetic algorithm (click graphic for animation demo)

To gain a general understanding of genetic algorithms, it is useful to examine its components. Before a GA can be run, it must have the following five components:

  1. A chromosomal representation of solutions to the problem.
  2. A function that evaluates the performances of solutions.
  3. A population of initialized solutions.
  4. Genetic operators that evolve the population.
  5. Parameters that specify the probabilities by which these genetic operators are applied.
The components are described below.

A. Representation

Usually, only two components of GA are problem dependent: the representation and evaluation functions. Representation is a key genetic algorithm issue because genetic algorithms directly manipulate coded representations of problems. In principle, any character set and coding scheme can be used. However, binary character set is preferred because it yield the largest number of schemata for any given parameter resolution, thereby enhancing the implicit parallelism of genetic searches. Note that, in most GAs, the individuals are represented by fixed-length binary strings that express a schema as a pattern defined over alphabet {0, 1, *}, and describe a set of binary strings in the search space. Thus, each string belongs to 2L schemata (L is the length of binary string). In [24] Holland wrote:

"Six detectors with a range of 10 values can yield approximately the same number of distinct representations as 20 detectors with a range of 2 values, since 10 6  2 20 =1.05 * 10 6 (cf. Decimal encoding vs. binary encoding). However the numbers of schemata in the two cases are vastly different: 11 6 =1.77*10 7 vs. 3 20 =3.48*10 9. Moreover in the first case each 'individual' is an instance of only 2 6 =64, whereas in the second case each 'individual' is an instance of 2 20 =1.05*10 6 schemata." But, binary coding can make the search difficult because the Hamming distance between adjacent values is not constant. The usual method of applying genetic algorithms to real-parameter problems is to encode each parameter as a bit string using either a standard binary coding, Gray coding or naive programming language coding. A table of 3-bit Gray codes is shown as Table I, where we notice that adjacent integers differ by a single bit (a Hamming distance of 1). This adjacency property is a general characteristic of the Gray codes. Conversions between standard and Gray code and vice versa for a standard-coded bitstring and its Gray-coded counterpart can be defined on the basis of an bit exclusive-or operator that denotes addition modulo 2 on a bit, i.e. 00=0, 01=1, 10=1, 11=0, as follows [49]: : Standard to Gray

: Gray to standard.

For example, if there are two parameters x1 and x2 with ranges , and it is assumed that three bits are used to represent each parameter. Then the point (x1, x2)=(4/7, 1) would be represented by the bit string 100 111 using binary coding and 110 100 using Gray coding and two floating points with values 0.5714286 and 1.0 on Win32 TM platform, which represents a floating point in 32-bit string using naive coding. Caruana [8] suggested that Gray coding is generally superior to binary coding for function optimization using the genetic algorithm. His analysis showed that Gray coding eliminates the "Hamming cliff" problem that make some transitions difficult when using a binary representation. Schaffer [43] conducted a comparison between binary coding and Gray coding on a specific class of optimization problems and also concluded that Gray coding should be used.

Although the binary alphabet offers the maximum number of schemata per bit of information in a coding, a genetic algorithm's power does not depend on using bit strings and it may be worthwhile to experiment with large alphabets and new genetic operators [26]. In floating point implementations, each individual is coded as a vector of floating point numbers of the same length as the solution vector. Although the precision of such an approach depends on the underlying machine, it is generally much better than that of binary representation.
 

TABLE I
Comparison of Binary-Coded and Gray-Coded Integers
Integer
Binary
Gray
0 000 000
1 001 001
2 010 011
3 011 010
4 100 110
5 101 111
6 110 101
7 111 100
 
B. Evaluation Function

Along with the representation scheme, the evaluation function is problem dependent. GAs are search techniques based on feedback received from their exploration of solutions. The judge of the GA's exploration is called an evaluation function. The notion of evaluation and fitness are sometimes used interchangeably. However, it is important to distinguish between the evaluation function and the fitness function. While evaluation functions provide a measure of an individual's performance, fitness functions provide a measure of an individual's reproduction opportunities. In fact, evaluation of an individual is independent of other individuals, while an individual's fitness is always dependent of other individuals.

C. Initial Population

Choosing an appropriate population size for a genetic algorithm is a necessary but difficult task for all GA users. On the one hand, if the population size is too small, the genetic algorithm will converge too quickly to find the optimal solution. On the other hand, if the population size is too large, the computation cost may be prohibitive. One theoretical investigation into optimal population size was conducted by Goldberg [15]. He reported which suggests population sizes of 130, 557, and 10244 for strings of lengths 30, 40, 50 and 60 respectively. Reeves [42] described an approach to specifying a minimal population size for the application of GAs. Smith [46] suggested an algorithm for adaptively resizing GA populations. Robertson's investigation of population size on parallel machines found that performance increased monotonically with population size [42]. The initial population for a genetic algorithm is usually chosen at random.

D. Operators

From a mechanistic point of view, a GA is an iterative process in which each iteration has two steps, evaluation and generation. In the evaluation step, domain information is used to evaluate the quality of an individual. The generation step includes a selection phase and a recombination phase. In the selection phase, fitness is used to guide the reproduction of new candidates for following iterations. The fitness function maps an individual to a real number that is used to indicate how many offspring that individual is expected to breed. High-fitness individuals are given more emphasis in subsequent generations because they are selected more often. In the recombination phase, crossover and mutation perform mixing. Crossover reconstructs a pair of selected individuals to create two new offspring. Mutation is responsible for re-introduction inadvertently "lost" gene values.

Most research has focussed on the three primary operators: selection, crossover, and mutation. While selection according to fitness is an exploitative resource, the crossover and mutation operators are exploratory resources. The GA combines the exploitation of past results with the exploration of new areas of the search space. The effectiveness of a GA depends on an appropriate mix of exploration and exploitation. The following describe these three operators in detail.

Selection: The selection phase plays an important role in driving the search towards better individuals and in maintaining a high genotypic diversity in the population. Grefenstette and Back [21] noted that the selection phase could be divided into the selection algorithm and the sampling algorithm. The selection algorithm assigns each individual x a real number, called the target sampling rate, tsr(x,t), to indicate the expected number of offspring x will reproduce by time t. The sampling algorithm actually reproduces, based on the target sampling rate, copies of individuals to form the intermediate population. In fact, there is some difference between an individual's actual sampling probability and its expected value. This difference is called bias.

There are two types of selection algorithms: explicit fitness remapping, and implicit fitness remapping [5]. The first one re-maps the fitness onto a new scale, which is then used by the sampling algorithm. Proportional selection and fitness ranking belongs to this category. The second one fills the mating pool without passing through the intermediate step of remapping. Tournament selection belongs to this category. Tournaments are often held between pairs of individuals since using larger tournament has the effect of increasing selective pressure.

There are also several classification criteria, and selection schemes can be classified with respect to the following [4]:

Crossover: In order to explore other points in the search space, variation is introduced into the intermediate population by means of some idealized genetic recombination operators. The most important recombination operator is called crossover. A commonly used method, called one-point crossover, selects two individuals in the intermediate population which then exchange portions of their representation. Take on-point crossover as example. Assume that the individuals are represented as binary strings. In one-point crossover, a point, called the crossover point, is chosen at random and the segments to the right of this point are exchanged. For example, let x1=101010 and x2=010100, and suppose that the crossover point is between bits 4 and 5 (where the bits are numbered from left to right starting at 1). Then the children are y1=101000 and y2=010110. Figure 2 illustrates this example.
 
Figure 2. Crossover (click for animation demo)

Crossover serves two complementary search abilities. First, it provides new points for further testing upon hyperplanes already represented in the population. Second, crossover introduces representatives of new hyperplanes into the population.

Crossover is, in effect, a method for sharing information between two successful individuals. In addition to one-point crossover there are several kinds of crossover operator such as two-point crossover, multi-point crossover, and uniform crossover  [1], [47]. In two-point crossover, rather than linear strings, chromosomes are regarded as a ring formed by joining the ends together. Two unique points are selected at random, breaking the ring into two segments. A segment from one ring is exchanged with one from another ring to produce two offspring. From this view, exchanging a single segment, two-point crossover performs the same task as one-point crossover. Multi-point crossover is an extension of two-point crossover [27]. Like two-point crossover, multi-point crossover treats the chromosome as a ring, which the crossover points cut into segments. Uniform crossover was suggested by Ackley [1]. For each position in the offspring the element copied from one or the other parent, according to a randomly generated crossover mask. The rule is easy to understand. Figure 3 represents how uniform crossover work. In this example x1=001011 and x2=111001, and suppose that the crossover mask is 100010. Then the children are y1=101001 and y2=011011.
 

Figure 3. Uniform crossover

Mutation: When individuals are represented as bit strings, mutation consists of reversing a randomly chosen bit. For example, assume that the individuals are represented as binary strings. In bit complement, once a bit is selected to mutate that bit will be flipped to be the complement of the original bit value. For example, let x1=101010 and suppose that the mutational bit is bits 4 (where the bits are numbered from left to right starting at 1). Then the child is y1=101110. Figure 4 demonstrates this example. Another mutation called noising mutation applies only to naive encoding gene. This mutation adds a white noise to the gene selected for mutation.
 

Figure 4. Mutation (click for animation demo)
If a number is represented by a group of bits in the string, small changes in the number's value are unlikely to follow from such mutation [7]. This prevents the genetic algorithm from refining solutions to find an optimal solution after discovering good solutions in its neighborhood.

The GA community usually views mutation as a background operator. Conversely, biologists view mutation as the main source of evolution.

E. Parameters

Running a genetic algorithm entails setting a number of parameter values. However, finding good settings that work well on one's problem is not a trivial task. There are two primary parameters concern the behavior of genetic algorithms: Crossover Rate(Cr) and Mutation Rate(Mr). The crossover rate controls the frequency with which the crossover the crossover operator is applied. If there are N individuals (population size=N) in each generation then in each generation N*Cr individuals undergo crossover. The higher crossover rate, the more quickly new individuals are added to the population. If the crossover is too high, high-performance individuals are discarded faster than selection can produce improvements. However, a low crossover rate may stagnate the search due to loss of exploration power. Mutation is the operator that maintains diversity in the population. A genetic algorithm with a too high mutation rate will become a random search. After the selection phase, each bit position of each individual in the intermediate population undergoes a random change with a probability equal to the mutation rate Mr. Consequently, approximately Mr*N*L mutations occur per generation, where L is the length of the chromosome. A genetic algorithm with a too high mutation rate will become a random search.


III. Running the Tool

The EGALT has been written in C++ and developed on a PC running Windows NT TM operating system. At this stage it is a platform dependent program that requires Win32 TM platform to run, but a natural evolution path is porting it to a platform independent program (for example, java) suitable for all platforms.

There is only one file need to run EGALT, the EGALT.EXE file. It can be triggered by "double clicking" the file EGALT.EXE in Windows File Manager. One window will pop up as the user interface of EGALT. Figure 5 shows the initial window user interface of EGALT. All the relevant parameters (function, encoding, problem size, population size, three major operators, and operators' parameters) are represented on the front panel of the window and intuitively operable by the user, giving real-time feedback.
 

Figure 5. Initial window of EGALT.

The upper region of the front panel represents runtime information about the GAs. There are six components in the area and are described below:

The bottom region of the front panel is control part of the tool. In control region students can change system identifications of GAs such as testing function, encoding method (representation), gene number, population size, selection, crossover, mutation, crossover rate, mutation rate, mutation range, and delay. They are described detail in following subsections.

A. Function

EGALT contains eleven testing functions that will have to be minimized. These testing functions cover a wider class of application domain.

First of all is the unary function whose function formula is:

    F0: = Numbers of zero in with 0,1}, value to reach: 0
            Function F0 C code is downloadable.

For example if is a 4 dimensional vector with elements 0,1,0, and 0. Then will be 1. The optimal value of is 0 for all dimensional versions of .

The second, third, fourth, fifth, and sixth functions come from "First International Contest on Evolutionary Optimization". The first contest of evolutionary optimization was held during the 1996 IEEE International conference on Evolutionary Computation (ICEC'96), May 20-22, 1996, Nagoya, Japan conference. Its aim was to allow researchers in the field to compare their algorithms on a common test bed. The contest provided two different categories, the real functions and the combinatorial problems. Herein we choose five functions in the real functions category since the combinatorial problems need domain knowledge of each problem to solve them well. The five functions are:

    F1: "The sphere model" whose function formula is:

    F2: "Griewank's function" whose function formula is:     F3: "Shekel's foxholes" whose function formula is:         For the value of A(i) and c, please look at the C code
        Function F3 C code is downloadable.

    F4: "Michalewicz's function" whose function formula is:

    F5: "Langerman's function" whose function formula is: The seventh, eighth, ninth, tenth, and eleventh testing functions come from De Jong's study, "An Analysis of the Behavior of a Class of Genetic Adaptive Systems." [27], stands as a milestone in the development of genetic algorithms. He constructed a test suite, which cover a wider class of application domain [27] [14]. The five functions are:

    F6: , with [-5.12, 5.12], value to reach: 1E-4
        Function F6 C code is downloadable.

    F7: , with [-2.048, 2.048], value to reach 1E-4
        Function F7 C code is downloadable.

    F8: , with [-5.12, 5.12], value to reach: 0
        Function F8 C code is downloadable.

    F9: , with [-1.28, 1.28], value to reach: 1E-4
        Function F9 C code is downloadable.

    F10: , with [-65.536, 65,536], value to reach: 0.9980
        For the value of a(i,j), please look at the C code
        Function F10 C code is downloadable.

Figure 6 shows the testing function selector and functions that are available in EGALT. The testing function is unary function initially.
 

Figure 6. Testing function selector and available options

B. Encoding method

All the encoding methods described in subsection 2.A are provided in EGALT: binary encoding, Gray encoding, and Naive encoding. Block encoding implies the double type in C programming language, which is a 64-bit string on the Win32 TM platform. Figure 7 shows the representation selector and options that are available in EGALT. Binary coding is the initial coding methods.
 

Figure 7. Representation selector and available options

C. Gene number

"Gene number" implies the numbers of the genes in a chromosome. In most cases the larger the number of the genes is, the harder the problem is for GAs to solve. Because the numbers of the genes means the numbers of the dimension in the problem, and vast dimension means huge search space. Gene number ranges from 1 to 100 in EGALT, and maybe fixed at specified numbers for some testing functions. For example if the testing function you selected is De Jong's testing function 2, F7, then the gene number will be fixed at 2. Since the function needs only two elements, and . Initial number of the genes depends on what test function is.

D. Population size

"Population size" implies the numbers of the individuals in a generation. Population size ranges from 1 to 1000 in EGALT. The population size affects both the effectiveness and the efficiency of a GA. Genetic algorithms with small populations generally perform poorly, because the population provides an insufficient sample size for most hyperplanes. A large population is more likely to contain representatives from a large number of hyperplanes. Furthermore, a large population can prevent genetic algorithms from premature convergence, On the other hand; however, it requires more evaluations per generation. Initially, population size is 50.

E. Selection

We divided options of each selection operator into two parts, the major part and the minor part. In major part there are three options available: proportional selection, ranking selection, and binary tournament selection. And the minor part is intended to provide additional selection characteristics. In EGALT we provide pure preservative, elitist preservative, right extinctive, and left extinctive selection characteristics. A complete selection operator must contain both minor and major options. For example, A pure preservative proportional selection operator combines option "pure preservative" and option "proportional". And three major selections combined with four minor selections characteristic results in twelve types of selection operators. Pure preservative proportional selection is the initial selection operator.

F. Crossover

There are four crossover operators available in GATT. They are one-point crossover, two-point crossover, multi-point crossover, and uniform crossover. Students can disable crossover operator by setting the crossover rate to zero. One-point crossover is the default crossover operator.

G. Mutation

Mutation operator will be set automatically according to gene encoding. If genes are encoded in binary encoding or Gray encoding then the mutation operator will be set to "bit complement". On the other hand, if naive encoding is the encoding method then "noise" mutation will be applied. Students can disable mutation operator by setting the mutation rate to zero.

H. Crossover rate

Crossover rate controls the frequency with which the crossover operator is applied. In each generation, Cr*N individuals undergo crossover. Students can set the crossover rate in the range between 0 and 1 in GATT. Default crossover rate is 0.6.

I. Mutation rate

When bit string encoded methods (binary encoding and Gray encoding) are applied there are approximately Mr*N*L mutations occur per generation. But when naive encoded method is applied then there is approximately Mr*N noise mutations occur per generation. Students can set the mutation rate in the range between 0 and 1 in GATT. Default mutation rate is 0.01.

J. Mutation range

Mutation range applies only when naive encoding is used. Mutation range controls the range of the white noise range added to genes, which are selected to be mutated. If the range is large then the population will gain large bias after mutation.

K. Delay

This is a speed control option. In less complex cases the program may run too fast for students to observe the behaviors of GAs. Students could add some delay in each generation.


IV. Case Studies

In this section, we present simple case studies in which EGALT has been employed for teaching GAs. The experience gained from those case studies acted as the foundation for the introduction of the computer assistant learning tool described above. Those case studies try to optimize parameters of the simple testing function, "The Sphere Model" testing function, by adjusting GAs parameters. Sphere model is simple in function formula thus make clear view about how GAs find the feasible solutions with suitable parameters or why GAs can not find feasible solutions with unsuitable parameters. The hardware configuration of the test platform is Pentium Pro with 200Mhz internal clock rate and 256KB level 2 cache. A 128MB EDO RAM main memory is installed. And the operating system is Microsoft Windows NT Workstation version 4.0.

A. The Sphere Model

The sphere model as an example of a continuous, strongly convex, unimodal function. Its function formula, as stated in subsection 2.1, is:
 
It servers as a test case for convergence velocity and is well know and widely used in all fields of Genetic Algorithms. The three-dimensional (i.e., N=2) topology of the sphere model is shown in Figure 8. Derive from the function formula we know that the optimal parameters for sphere model is =1, =1, ..., N.
 

Figure 8. Three-dimensional plot of the sphere model

B. Case 1 :  Basic Setting

At first we conducted ten experiments using  the default parameters:

The experimental result is represent in  Figure 9. Here the performance is measured by averaging the ten runs. Here we found that GAs can't find a feasible solution in this case. GA converge at value 0.376007 (log (0.376007) = -0.424804) started at the 1459th generation, but the objective function value is 0.000001 (log(0.000001)=-6). And the average time in runing 3000 generations is 8 seconds. Why can't GA solve this problem? We found the problem is the representation method we chose in this case after observed gene values of the best chromosome. The gene values, binary encoding bitstrings and Hamming distances to optimal value are listed at Table II. Notice that the Hamming distance between gene values and optimal gene value are about half of length. Three types of genes occur (1010000..., 1001011..., and 1001101000...) and the Hamming distance between these genes and optimal gene are so large in this experiment. An optimal point is found, but it is a local minimum, rather than a global minimum. In binary encoding, Hamming distance between adjacent values is not constant. Once GAs found a local minimum the population will be trapped at a local minimum.
 
Figure 9. Performance chart with parameters: function=sphere model, gene encoding=binary encoding, selection=pure preservative proportional selection, crossover=one-point crossover, mutation=bit complement, crossover rate=0.6, mutation rate=0.01. Note that the Y axis is the logarithmic of function value.

 

TABLE II
The best chromosome in case1 and optimal gene
 
Decoded value
Binary encoding bit string
Hamming distance to optimal
Gene 1
1.25
10100000000000000000000000000000
16
Gene 2
1.01563
10011010000000000000000000000000
14
Gene 3
0.9375
10010111111111111111111111111111
14
Gene 4
0.9375
10010111111111111111111111111111
14
Gene 5
1.25
10100000000000000000000000000000
16
Optimal
1.0
10011001100110011001100110011001
0
 
C. Case 2 : Gray Encoding

In case 1 we found the problem may occurs in binary encoding representation. We choose Gray encoding and run ten experiments using  the following parameters:

And successfully solve the problem with average 1168th generations and best function value 7.08E-7. And the average time to find a suitable solution is 3.6 seconds.  Figure 10 shows one performance chart of these ten experiments.
 
Figure 10. Performance chart with parameters: function=sphere model, gene encoding=Gray encoding, selection=pure preservative proportional selection, crossover=one-point crossover, mutation=bit complement, crossover rate=0.6, mutation rate=0.01. Note that the Y axis is the logarithmic of function value.
 

V. Conclusions and Current Status

The EGALT is an easy operating yet versatile tools for learning genetic algorithms. The combination of the ability of vast online parameters tuning and ready to run program can be used in a complementary way to provide computer-aided instructions in the teaching of genetic algorithms. With the readily available genetic algorithms tool students can reduce the mechanical programming aspect of learning and concentrate on principles alone. For example, by using the EGALT described in this paper, more attention can be devoted to understanding the physical significance of parameters and little time wasted on teaching the tricks to solve problem.

We are currently investigating two enhancements to EGALT. First, we are adding options to the tool; thus the tool will cover wider class of problem domains and will increase the flexibility of the tool. Second, we are porting this tool to a platform independent program (the java TM programming language) suitable for interaction via the de-facto standard interface of the World Wide Web [35]


References

[1] D. H. Ackley. A Connectionist Machine for Genetic Hillclimbing. Kluwer Academic Publishers, Boston, MA, 1987.
[2] A. S. Austin. Genetic solution to xor problems. AI EXPERT, pages 52-57, December 1990.
[3] T. Back. Evolutionary Algorithms in Theory and Practice,  Oxford, New York, 1996.
[4] T. Back, F. Hoffmeister, and H.-P. Schwefel. A survey of evolution strategies. In R. K. Belew and L. B. Booker, editors, Proceedings of the Fourth International Conference on Genetic Algorithms and Their Applications, pages 2-9, San Mateo, CA, July 1991.
[5] D. Beasley, D. R. Bull, and r. R. Martin. An overview of genetic algorithms: Part 1, fundamentals. University Computing, 15(2):58-69, 1993.
[6] B. Bhanu, S. Lee, and J. Ming. Self-optimizing image segmentation system using a genetic algorithm. In R. K. Belew and L. B. Booker, editors, Proceedings of the Fourth International Conference on Genetic Algorithms and Their Applications, pages 362-369, San Mateo, CA, July 1991. Morgan Kaufmann.
[7] M. F. Bramlette. Initializatin, mutation and selection methods in genetic algorithms for function optimization. In R. K. Belew and L. B. Booker, editors, Proceedings of the Fourth International Conference on Genetic Algorithms and Their Applications, pages 100-107, San Mateo, CA, July 1991. Morgan Kaufmann.
[8] R. A. Caruana and J. D. Schaffer. Representation and hidden bias: Gray v.s. binary coding for genetic algorithms. In M. B. Morgan, editor, Proceedings of the Fifth International Workshop on Machine Learning, pages 153-161, San Mateo, CA, June 1988. Morgan Kaufmann.
[9] G. A. Cleveland and S. F. Smith. Using genetic algorithms to schedule flow shop releases. In J. D. Schaffer, editor, Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, pages 160-169, San Mateo, CA, June 1989. Morgan Kaufmann.
[10] N. L. Cramer, A representation for the adaptive generation of simple sequential programs. In J. J, Grefenstette, ed., Proceedings of the First International Conference on Genetic Algorithms and Their Applications. Erlbaum, 1985.
[11] M. Dorigo and U. Schnepf. Genetic-based machine learning and behavior-based robotics: a new syndissertation. IEEE Transactions on System, Man, and Cybernetics, SMC-23(1):144-154, 1993.
[12] L. J. Fogel, A. J. Owens, and M. J. Walsh. Artificial Intelligence Through Simulated Evolution. John Wiley & Sons, New York, 1966.
[13] C. Fujiki, and J. Dickinson, Using the genetic algorithm to generate Lisp source code to solve the Prisoner's dilemma. In J. J. Grefenstette, ed., Proceedings of the First International Conference on Genetic Algorithms and Their Applications. Erlbaum, 1987.
[14] D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Weley, Reading, MA, 1989.
[15] D. E. Goldberg. Optimal initial population size for binary-coded genetic algorithms. Technical Report TCGA Report No. 85001, University of Alabama, 1989.
[16] D. E. Goldberg. Sizing populations for serial and parallel genetic algorithms. In J. David Schaffer, editor, Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, pages 70-79, San Mateo, CA, June 1989. Morgan Kaufmann.
[17] D. E. Goldberg and J. H. Holland. Genetic algorithms and machine learning. Machine Learning, 3(2/3):95-99, 1988.
[18] D. E. Goldberg and J. Richardson. Genetic algorithms with sharing for multimodal function optimization. In J. J. Grefenstette, editor, Proceedings of the Second International Conference on Genetic Algorithms and Their Applications, pages 41-49, Hillsdale, NJ, July 1987. Lawrence Erlbaum Associates.
[19] J. J. Grefenstette. Optimization of control parameters for genetic algorithms. IEEE Transactions on System, Man, and Cybernetics, SMC-16(1):122-128, 1986.
[20] J. J. Grefenstette. Credit assignment in rule discovery systems based on genetic algorithms. Machine Learning, 3(2/3):225-245, 1988.
[21] J. J. Grefenstette and J. E. Baker. How genetic algorithms work: A critical look at implicit parallelism. In J. D. Schaffer, editor, Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, pages 20-27, San Mateo, CA, June 1989. Morgan Kaufmann.
[22] J. J. Grefenstettte, R. Gopal, B. J. Rosmaita, and D. V. Gucht. Genetic algorithm for the traveling salesman problem. In J. J. Grefenstette, editor, Proceeding of the First International Conference on Genetic Algorithms and Their Applications, pages 160-168, Hillsdale, NJ, July 1985. Lawrence Erlbaum Associates.
[23] S. A. Harp, T. Samad, and A. Guha. Towards the genetic syndissertation of neural networks. In J. D. Schaffer, editor, Proceedings of the Third International Conference on Genetic Algorithms and Their Applicatins, pages 360-369, San Mateo, CA , June 1989. Morgan Kaufmann.
[24] J. H. Holland. Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, MI, 1975.
[25] J. J. Hopfield. Neural networks and physical systems with emergent collective computational abilities. In Proceedings of the National Academy of Sciences, pages 2554-2558, 1982.
[26] C. Z. Janikow and Z. Michalewicz. An experimental comparison of binary and floating point representation in genetic algorithms. In R. K. Belew and L. B. Booker, editors, Proceedings of the Fourth International Conference on Genetic Algorithms and Their Applications, pages 31-36, San Mateo, CA, July 1991. Morgan Kaufmann.
[27] K. A. De Jong. An Analysis of the Behavior of a Class of Genetic Adaptive Systems. Ph.D. dissertation, University of Michigan, 1975.
[28] K. A. De Jong. Learning with genetic algorithms: an overview. Machine Learning, 3(2/3:121-138, 1988.
[29] K. A. De Jong and W. M. Spears. On the state of evolutionary computation. In S. Forrest, editor, Proceedings of the Fifth International Conference on Genetic Algorithms, pages 618-623, San Mateo, CA, June 1993. Morgan Kaufmann.
[30] C. L. Karr. Design of an adaptive fuzzy logic controller using a genetic algorithm. In R. K. Belew and L. B. Booker, editors, Proceedings of the Fourth International Conference on Genetic Algorithms and Their Applications, pages 450-457, San Mateo, CA, July 1991. Morgan Kaufmann.
[31] S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi. Optimization by simulated annealing. Science, 220:671-680, 1983.
[32] K. Kristinsson and G. A. Dumont. System identification and control using genetic algorithms. IEEE Transactions on System, Man, and Cybernetics, SMC-22(5):1033-1046, 1992.
[33] J. R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, 1992.
[34] J. R. Koza, Genetic Programming II: Automatic Discovery of Reusable Programs. MIT Press, 1994.
[35] K. Mitchell, G. Kerdoncuff, and G. S. May, Microelectronics processing education using the Internet, Proceedings - Frontiers in Education Conference v 1, IEEE, Piscataway, NJ, USA, pages 114-122, 1995.
[36] M. Mitchell, An Introduction to Genetic Algorithms. MIT Press, 1997.
[37] G. G. Miller, P. M. Todd, and S. U. Hegde. Designing neural networks using genetic algorithms. In J. D. Schaffer, editor, Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, pages 379-384, San Mateo, CA, June 1989. Morgan Kaufmann.
[38] N. H. Packard, A genetic learning algorithm for the analysis of complex data Complex Systems 4, no. 5:543-572, 1990.
[39] I. Rechenberg. Cybernetic solution path of an experimental problem. Roy. Aircr. Establ., libr. Transl. 1122. Hants, U. K.:Farnboough, 1965.
[40] I. Rechenberg. Evolutionstrategie: Optimierung Technischer System nach Prinzipien der Biologischen Evolution. Frommann-Holzboog, Verlag, Stuttgart, 1973.
[41] C. R. Reeves. Using genetic algorithms with small populations. In S. Forrest, editor, Proceeding of the Fifth International Conference on Genetic Algorithms, pages 92-99, San Mateo, CA, June 1993. Morgan Kaufmann.
[42] G. G. Robertson. Population size in classifier systems. In M. B. Morgan, editor, Proceedings of the Fifth International Workshop on Machine Learning, pages 142-152, San Mateo, CA, June 1988. Morgan Kaufmann.
[43] J. D. Schaffer. Some Experiments in Machine Learning using Vector Evaluated Genetic Algorithms. Ph.D.dissertation, Vanderbilt University, 1980.
[44] H.-P. Schwefel. Evolutionsstrategie und numberische Optimierung.Ph.D. thesis, Technische Universitat Berlin, 1975.
[45] H.-P. Schwefel. Numerische Optimierung von Computer-Modellen mittels der Evolutionsstrategie. Basel: Birkhauser, 1977.
[46] R. E. Smith. Adaptively resizing populations: An algorithm and analysis. In S. Forrest, editor, Proceedings of the Fifth International Conference on Genetic Algorithms, page 653, San Mateo, CA, June 1993. Morgan Kaufmann.
[47] G. Syswerda. Uniform crossover in genetic algorthms. In J. D. Schaffer, editor, Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, pages 2-9, San Mateo, CA, June 1989. Morgan Kaufmann.
[48] G. Syswerda and J. Palmucci. The application of genetic algorithms to resource scheduling. In R. K. Belew and L. B. Booker, editors, Proceedings of the Fourth International Conference on Genetic Algorithms and Their Applications, pages 502-508, San Mateo, CA, July 1991. Morgan Kaufmann.
[49] A. H. Wright. Genetic algorithms for real parameter optimization. In Rawlins, pages 205-218, 1991.

Author Contact Information

Ying-Hong Liao
Department of Computer and Information Science
National Chiao Tung University
Hsinchu, Taiwan 30050
Phone: +886-3-5712121-59284
Fax: +886-3-5721490
E-mail: liao@cindy.cis.nctu.edu.tw

Chuen-Tsai Sun
Department of Computer and Information Science
National Chiao Tung University
Hsinchu, Taiwan 30050
Phone: +886-3-5712121-56612
Fax: +886-3-5721490
E-mail: ctsun@cis.nctu.edu.tw


Author Biographies

Ying-Hong Liao  was born in Taiwan, 1972. He  received his degree in Computer and Information Science from the National Chiao Tung University. His research interests are in the field of machine learning and evolutionary computation. He is currently working for his Ph.D. in National Chiao Tung University.

Chun-Tsai Sun is an assistant professor of Computer and Information Science at National Chiao Tung University in Taiwan. He received his degree in Electric Engineering  from National Taiwan University, and received the Ph.D. in Computer Science from Berkley University. His research interests are in the field of evolutionary computation, fuzzy systems, neural networks, artificial intelligence, computer aided instruction, and distant cooperative learning.
 


Return to Table of Contents