[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
IlliGAL New Technical Reports Announcement
The Illinois Genetic Algorithms Laboratory (IlliGAL) is pleased to
announce the publication of the following new technical reports
and software. Most IlliGAL technical reports, as well as reprints
of other publications, are available in hardcopy and can be
ordered from the IlliGAL librarian, (see below for ordering
information). The technical reports in this announcement are also
available electronically on our ftp and WWW servers (see the end
of this announcement for ftp and WWW access instructions).
--------------------------
IlliGAL Report No 2000037
Genetic Algorithms: A Bibliography
Goldberg, D.E., Borgerson, J., Vaughn, A., Hawley, K., Cunningham,
C., Milner, J., Zacarias, K., Wagus, B., Gadient, R., Sutton, B.,
Pelikan, M., Roth
Abstract:
--------------------------
IlliGAL Report No 2001001
Prüfer Numbers: A Poor Representation of Spanning Trees for
Evolutionary Search
Gottlieb, J., Julstrom, B. A., Raidl, G. R., Rothlauf, F.
Abstract:
The most important element in the design of a decoder-based
evolutionary algorithm is its genotypic representation. The
genotype-decoder pair must exhibit efficiency, locality, and
heritability to enable effective evolutionary search. Pruefer
numbers have been proposed to represent spanning trees in
evolutionary algorithms. Several researchers have made extravagant
claims for the usefulness of this coding, but others have pointed
out that Pruefer numbers, though concise and easy to decode, lack
the essential properties of locality and heritability. This
conflict motivates our study. We examine the properties of Pruefer
numbers and compare Pruefer numbers with other codings in
evolutionary algorithms for four problems that involve spanning
trees. Our conclusion is definite: Pruefer numbers cause poor
performance in evolutionary algorithms and should be avoided.
--------------------------
IlliGAL Report No 2001002
Genetic Algorithms at the University of Illinois Fall 2000
Goldberg, D.E. (ed.)
Abstract:
--------------------------
IlliGAL Report No 2001003
Escaping Hierarchical Traps with Competent Genetic Algorithms
Pelikan, M., Goldberg, D.E.
Abstract:
To solve hierarchical problems, one must be able to learn the
linkage, represent partial solutions efficiently, and assure
effective niching. Linkage learning results in a good problem
solver on a single level. Niching and efficient representation of
partial solutions ensure that the algorithm maintains enough
alternative solutions on each level to compose the solutions on a
higher level. We combine the Bayesian optimization algorithm,
which has been shown to solve problems on a single level
efficiently, with a powerful niching technique based on crowding
and restricted tournament selection. Decision graphs are used as
local structures to encode information about the relationships
among the variables in a problem. The proposed algorithm is called
the hierarchical Bayesian optimization algorithm. Additionally, we
propose a new class of hierarchically decomposable problems that
are deceptive on each level and show that the proposed algorithm
scales up subquadratically on all test problems. The proposed
class of problems is called hierarchical traps. Empirical results
are in agreement with our recent convergence and population sizing
theory.
--------------------------
IlliGAL Report No 2001004
Human Based Genetic Algorithm
Kosorukoff, A.
Abstract:
In this paper, a new class of genetic algorithms (GA) is
presented. It is based on the idea of outsourcing, which is a
popular trend in business today. In human based genetic algorithm
(HBGA), all primary genetic operators are outsourced, i.e.
delegated to outside human agents. The totally outsourced genetic
algorithm uses both human evaluation and human ability of
innovation. It is a multi-agent environment and the mediator of
communication between multiple heterogenous agents. The advantage
of this approach is its ability to address complex problems in
which it is hard not only to evaluate individuals, but even find a
good representation for them. This allows GA to process flows of
information without knowledge of its particular structure and
representation. Suggested conceptual approach can also be used as
a general model and a way of thinking about different kinds of
genetic algorithms.
--------------------------
IlliGAL Report No 2001005
Genetic Algorithms for Social Innovation and Creativity
Kosorukoff, A., Goldberg, D.E.
Abstract:
Since their invention, genetic algorithms have been used primarily
for solving problems in different areas of engineering and
technology. In most of these areas genetic algorithms were applied
successfully and shifted the frontier between what is possible and
what is impossible, solving problems that were even hard to
approach with conventional deterministic methods. Recent social
applications of genetic algorithms challenge our usual way of
thinking about social systems. Instead of old concepts of social
engineering, based on deterministic mechanical constructivism,
genetic algorithms and other methods of evolutionary computation
open new approaches to the same issue. These methods allow us to
substitute fixed structures of our organizations with free forms
which are soft and evolving. This paper contains two examples, and
some conclusions from this case study. The main conclusion is that
GAs have already passed beyond only their technical applications
to artificial systems, they are ready to come into the real world
of living systems and even have made the first steps in this
direction.
--------------------------
IlliGAL Report No 2001006
Modeling of evolution of signaling networks in living cells by
evolutionary computation
Kosorukoff, A., Mittenthal, J., Goldberg, D.E.
Abstract:
This work is an attempt to model the evolution of signaling
pathways in living cells with evolutionary computation under
different selection criteria and to compare pathways evolved in
such a way with those we encounter in nature. It proposes 5-level
evolutionary procedure for this purpose, that can be thought as
several co-operating genetic algorithms working in parallel on
different levels of an abstraction hierarchy corresponding to the
conceptual structure of an evolving object. On one hand, this work
allows to get some insight into the process of emergence of
signaling networks within cells. On the other hand, this is an
example of application of genetic algorithm for redesign of a
system that was already designed by natural selection. It allows
to compare the results produced by computational model of
evolution (GA) with the results of natural evolutionary process,
which may lead to better understanding of relationship between
natural and computational evolution. We can see how close our GAs
are to their natural prototype and can get some new understanding
of GAs and ideas on their improvement.
--------------------------
IlliGAL Report No 2001007
Verification of the Theory of Genetic and Evolutionary
Continuation
Srivastava, R.P., Goldberg, D.E.
Abstract:
This paper makes a first attempt to study and verify empirically
the theory of proposed continuation operators through systematic
formulation of experiments. Both the basic, and in a sense
bounding, cases of building block salience, as encountered in
difficult problems, are dealt with individually. Experimental
results closely match theory and assure us of the usefulness of an
apt blend of continuation operators with epoch-wise runs.
--------------------------
IlliGAL Report No 2001008
How XCS Evolves Accurate Classifiers
Butz, M.V., Kovacs, T., Lanzi, P.L., Wilson, S.W.
Abstract:
Due to the accuracy based fitness approach, the ultimate goal for
XCS is the evolution of a compact, complete, and accurate payoff
mapping of an environment. This paper investigates what causes the
XCS classifier system to evolve accurate classifiers. The
investigation leads to two challenges for XCS, the covering
challenge and the schema challenge. Both challenges are revealed
theoretically and experimentally. Furthermore, the paper provides
suggestions for overcoming the challenges as well as investigates
environmental properties that can help XCS to overcome the
challenges autonomously. Along those lines, a deeper insight into
how to set the initial parameter values in XCS is provided.
--------------------------
IlliGAL Report No 2001009
Analyzing the Evolutionary Pressures in XCS
Butz, M.V., Pelikan, M.
Abstract:
After an increasing interest in learning classifier systems and
the XCS classifier system in particular, this paper locates and
analyzes the distinct evolutionary pressures in XCS. Combining
several of the pressures, an equation is derived that validates
the generalization hypothesis which was stated by Wilson(1995). A
detailed experimental study of the equation exhibits its
applicability in predicting the change in specificity in XCS as
well as reveals several other specificity influences.
--------------------------
IlliGAL Report No 2001010
Verification and Extension of the Theory of Global-Local Hybrids
Sinha, A., Goldberg, D.E.
Abstract:
This work is an extension of the framework for optimizing
global-local hybrids. The existing theory idealizes the search
problem as a search by a global searcher for acceptable targets or
for basins of attractions which lead to acceptable target by
invoking a local searcher. The two key parameters of this theory
are---the probabilities of successfully hitting targets and basins
and time-to-criterion values for different basins. First the
existing theory is tested with variation in time-to-criterion
values for the local searcher across several basins and is then
extended to handle variations within individual basins. As a first
step towards applying this theory to genetic algorithms (as the
global searcher), selection dominated performance has also been
studied in the context of this theory. The results are promising
and make a strong case for further work in this direction.
--------------------------
IlliGAL Report No 2001011
The Link and Node Biased Encoding Revisited: Bias and Adjustment
of Parameters
Gaube, T., Rothlauf, F.
Abstract:
When using genetic and evolutionary algorithms (GEAs) for the
optimal communication spanning tree problem, the design of a
suitable tree network encoding is crucial for finding good
solutions. The link and node biased (LNB) encoding represents the
structure of a tree network using a weighted vector and allows the
GEA to distinguish between the importance of the nodes and links
in the network. This paper investigates whether the encoding is
unbiased in the sense that all trees are equally represented, and
how the parameters of the encoding influence the bias. If the
optimal solution is underrepresented in the population, a
reduction in the GEA performance is unavoidable. The investigation
reveals that the commonly used simpler version of the encoding is
biased towards star networks, and that the initial population is
dominated by only a few individuals. The more costly
link-and-node-biased encoding uses not only a node-specific bias,
but also a link-specific bias. Similarly to the node-biased
encoding, the link-and-node-biased encoding is also biased towards
star networks, especially when using a low weighting for the
link-specific bias. The results show that by increasing the
link-specific bias, that the overall bias of the encoding is
reduced. If researchers want to use the LNB encoding, and they are
interested in having an unbiased representation, they should use
higher values for the weight of the link-specific bias.
Nevertheless, they should also be aware of the limitations of the
LNB encoding when using it for encoding tree problems. The
encoding could be a good choice for the optimal communication
spanning tree problem as the optimal solutions tend to be more
star-like. However, for general tree problems the encoding should
be used carefully.
--------------------------
IlliGAL Report No 2001012
Tackling Multimodal Problems in Hybrid Genetic Algorithms
Parthasarathy, P.V., David E. Goldberg, D.E., Burns, S.A.
Abstract:
A method is proposed to address the issue of multimodality while
using hybrid genetic algorithms (GAs). The hybrid GA framework
that is used is one in which a local searcher is employed during a
Baldwinian fitness evaluation. The proposed method, besides
offering capability of handling multimodality, also comes with an
added bonus of facilitating evaluation relaxation. The method has
been used on a structural design problem with promising results.
--------------------------
IlliGAL Report No 2001013
Don't Evaluate, Inherit
Sastry, K., Goldberg, D.E., Pelikan, M.
Abstract:
This paper studies fitness inheritance as an efficiency
enhancement technique for genetic and evolutionary algorithms.
Convergence and population sizing models are derived and compared
with experimental results. These models are optimized for greatest
speed-up and the optimal inheritance proportion to obtain such a
speed-up is derived. Results also show that when the inheritance
effects are considered in the population sizing model, the number
of function evaluations are reduced by 20\% with the use of
fitness inheritance. Results indicate that for a fixed population
size, the number of function evaluations can be reduced by 70\%
using a simple fitness inheritance technique.
--------------------------
IlliGAL Report No 2001014
Modeling Tournament With Replacement Using Apparent Added Noise
Sastry, K., Goldberg, D.E.
Abstract:
This paper analyzes the effects of tournament selection with
replacement on the convergence time and population sizing for
selectorecombinative genetic algorithms. This paper empirically
demonstrates that the run duration remains the same and is not
affected whether the tournament selection is performed with or
without replacement. However, the population size required is more
if tournament selection is performed with replacement rather than
without replacement to attain the same level of accuracy. An
approximate population sizing model is derived based on apparent
added noise for the case of tournament selection with replacement.
The proposed model is verified with experimental results.
--------------------------
IlliGAL Report No 2001015
On the Supply of Building Blocks
Goldberg, D.E., Sastry, K., Latoza, T.
Abstract:
This study addresses the issue of building block supply in the
initial population. Facetwise models for supply of a single
building block as well as for supply of all schemata in a
partition have been developed. An estimate for the population size
required to ensure the presence of all raw building blocks has
been derived using these facetwise models. The facetwise models
and the population sizing estimate are verified with computational
results.
--------------------------
IlliGAL Report No 2001016
Cluster Optimization Using Extended Compact Genetic Algorithm
Sastry, K., Xiao, G.
Abstract:
This paper presents an efficient cluster optimization algorithm.
The proposed algorithm uses extended compact genetic algorithm
(ECGA), one of the competent genetic algorithms (GAs) coupled with
Nelder-Mead simplex local search. The lowest energy structures of
silicon clusters with 4-11 atoms have been successfully predicted.
The minimum population size and total number of function
(potential energy of the cluster) evaluations required to converge
to the global optimum with a reliability of 96\% have been
empirically determined and are ${\mathcal{O}}\left(n^{4.2}\right)$
and ${\mathcal{O}}\left(n^{8.2}\right)$ respectively. The results
obtained indicate that the proposed algorithm is highly reliable
in predicting globally optimal structures. However, certain
efficiency techniques have to be employed for predicting
structures of larger clusters to reduce the high computational
cost due to function evaluation.
--------------------------
IlliGAL Report No 2001017
A Practical Schema Theorem For Genetic Algorithm Design and Tuning
Goldberg, D.E., Sastry, K.
Abstract:
This paper develops the theory that can enable the design of
genetic algorithms and choose the parameters such that the
proportion of the best building blocks grow. A practical schema
theorem has been used for this purpose and its ramification for
the choice of selection operator and parameterization of the
algorithm is explored. In particular stochastic universal
selection, tournament selection, and truncation selection schemes
are employed to verify the results. Results agree with the schema
theorem and indicate that it must be obeyed in order to ascertain
sustained growth of good building blocks. The analysis suggests
that schema theorem alone is insufficient to guarantee the success
of a selectorecombinative genetic algorithm.
--------------------------
IlliGAL Report No 2001018
Efficient Atomic Cluster Optimization Using A Hybrid Extended
Compact Genetic Algorithm With Seeded Population
Sastry, K.
Abstract:
A recent study Sastry and Xiao (2001) proposed a highly reliable
cluster optimization algorithm which employed extended compact
genetic algorithm (ECGA) along with Nelder-Mead simplex search.
This study utilizes an efficiency enhancement technique for the
ECGA based cluster optimizer to reduce the population size and the
number of function evaluation requirements, yet retaining the high
reliability of predicting the lowest energy structure. Seeding of
initial population with lowest energy structures of smaller
cluster has been employed as the efficiency enhancement technique.
Empirical results indicate that the population size and total
number of function evaluations scale up with the cluster size are
reduced from O(n^4.2) and O(n^8.2) to O(n^0.83) to O(n^2.45)
respectively.
--------------------------
IlliGAL Report No 2001019
Evolutionary Algorithm Using Marginal Histogram Models in
Continuous Domain
Tsutsui, S., Pelikan, M., Goldberg, D.E.
Abstract:
Recently, there has been a growing interest in developing
evolutionary algorithms based on probabilistic modeling. In this
scheme, the offspring population is generated according to the
estimated probability density model of the parents instead of
using recombination and mutation operators. In this paper, we
propose an evolutionary algorithm using a marginal histogram to
model the parent population in a continuous domain. We propose two
types of marginal histogram models: the fixed-width histogram
(FWH) and the fixed-height histogram (FHH). The results showed
that both models worked fairly well on test functions with no or
weak interactions among variables. Especially, FHH could find the
global optimum with very high accuracy effectively and showed good
scale-up with the problem size.
--------------------------
IlliGAL Report No 2001020
Building Block Superiority, Multimodality and Synchronization
Problems
Van Hoyweghen, C., Goldberg, D. E., Naudts, B.
Abstract:
The working of a genetic algorithm is usually explained by the
search for superior building blocks. Building blocks with above
average fitness are combined to construct higher order building
blocks. This paper shows that this mechanism is not sufficient to
solve problems where multimodality is ubiquitous. For this class
of problems niching becomes a necessity.The paper analyzes the
Ising model as an archetypal problem where multimodality is
ubiquitous and niching is essential. The analysis introduces an
important difference between searching for superior building
blocks and searching for non-inferior building blocks.
-------------------------------------------------------------
RETRIEVAL/ORDERING:
The above IlliGAL reports and publications, along with other
publications and source code, are available electronically via FTP or
WWW, or as hardcopy directly from us:
FTP: ftp ftp-illigal.ge.uiuc.edu
login: anonymous
password: (your email address)
cd /pub/papers/IlliGALs (for reports) or
cd /pub/papers/Publications (for preprints) or
cd /pub/src (for GA and classifier system source code)
binary
get 99022.ps.Z (for example)
Please look at the README files for explanations of what the file
names mean. IlliGAL reports are all compressed postscript files.
WWW: To access the IlliGAL home page, open
http://www-illigal.ge.uiuc.edu/
HARDCOPY:
You can also order hardcopy versions of most IlliGAL publications
Use the order form in the web or request them directly
(by IlliGAL number or title) from the IlliGAL librarian:
Internet: library@illigal.ge.uiuc.edu Phone: 217/333-2346
Fax: 217/244-5705
Surface mail: IlliGAL Librarian
Department of General Engineering
117 Transportation Building
104 South Mathews Avenue
Urbana, IL 61801-2996 USA
When ordering hardcopy, please include your surface mail address!
----------------------------------------------
Martin Pelikan
Illinois Genetic Algorithms Laboratory
University of Illinois at Urbana Champaign
117 Transportation Building
104 S. Mathews Avenue, Urbana, IL 61801
tel: (217) 333-2346, fax: (217) 244-5705
----------------------------------------------