©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. |
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.
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:
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.
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:
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:
: Gray to standard.
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.
|
|
|
0 | 000 | 000 |
1 | 001 | 001 |
2 | 010 | 011 |
3 | 011 | 010 |
4 | 100 | 110 |
5 | 101 | 111 |
6 | 110 | 101 |
7 | 111 | 100 |
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]:
Left versus right extinctive selection: In case of extinctive selection there is a major special case where the worst performing individuals have zero reproduction rates, i.e. they do not reproduce. This situation is referred to as right extinctive selection. Similarly, the best individuals are also prevented from reproducing in order to avoid premature convergence due to the existence of super-individuals. This is referred to as left extinctive selection.
Elitist versus pure: A selection scheme that enforces a lifetime of just one generation on each individual regardless of its fitness is referred to as pure selection. In an elitist selection scheme some parents are allowed to undergo selection with their offspring [27].
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.
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.
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.
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.
The upper region of the front panel represents runtime information about the GAs. There are six components in the area and are described below:
Timer: How much time spent in running GA.
Speed: How many generations the program can evaluate in a second.
Best: The minimum function value found till now.
Average: The average function value of the late evaluated generation.
Object: The object function value of the testing function for GAs to reach.
Best chromosome: The gene map of the best individual found till now. A mapping between gene value and its color is represented at Gene map. Users can click on a gene to see the exact value of that gene.
Gene map: Show a mapping between color and gene value. The more lighter in red the larger the value is.
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:
F4: "Michalewicz's function" whose function formula is:
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.
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.
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.
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.
B. Case 1 : Basic Setting
At first we conducted ten experiments using the default parameters:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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:
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]
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
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.