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).
(1) NEW TECHNICAL REPORTS
--------------------------
IlliGAL Report No 2000028
Mining Oblique Data with XCS
Stewart W. Wilson
Abstract:
The classifier system XCS was investigated for data mining
applications
where the dataset discrimination surface (DS) is generally oblique
to
the attribute axes. Despite the classifiers' hyper-rectangular
predicates, XCS reached 100% performance on synthetic problems with
diagonal DS's and, in a train/test experiment, competitive
performance
on the Wisconsin Breast Cancer dataset. Final classifiers in an
extended WBC learning run were interpretable to suggest dependencies
on
one or a few attributes. For data mining of numeric datasets with
partially oblique discrimination surfaces, XCS shows promise from
both
performance and pattern discovery viewpoints.
--------------------------
IlliGAL Report No 2000029
A note on using genetic and evolutionary algorithms for
multi-periodcommunication network optimisation
Franz Rothlauf, Christian Grasser
This paper addresses the optimization of telecommunication networks
for a multi-period horizon. Four heuristics are presented to cope
with
the problem to minimize the overall costs for the network over
several
periods. For the minimization of cost we use a simple genetic
algorithm
(GA). It is adapted in different ways to the special structure of
the
network problem. Even in the single-period case, the stated problem
is
hard to solve. For solving the multi-period problem we have two
possible choices: Firstly, all periods could be solved synchronously
(in parallel). Secondly, the different periods are optimized step by
step (serially). With serial optimization, the algorithm could fail
in
finding the global minimum, but the computational effort for the
parallel optimization is so much higher that it can hardly be used
other than in small test problems. In addition to this, the
solutions
for the periods are very similar, meaning that the parallel
optimization has to detect a lot of redundant information. To
optimize
the overall costs serially we present four different approaches. The
first, and most simple optimizes the structure of the network for
each
period independently of the solutions for other periods. The second
approach optimizes only the structure for the first period, and the
structure of the network is not changed for the following periods.
Only
the capacities of the links are scaled up according to the necessary
demands. The third approach optimizes serially the structure of the
networks for the different time periods starting from the first. For
the fitness of the individuals, the overall cost of the network,
including the cost for changing the lines between the periods, is
used. Finally we propose an extension of the third approach. In an
initial step, all time periods are optimized sequentially and
independently from each other. After the first run over the whole
planning horizon, we will pick out periods randomly and optimize
this
period with respect to the previous and next periods. We believe
that
this extension leads to a more stable and robust solution of the
network design problem. We present some results for the first three
approaches for a specific real-world problem. A short investigation
of
the performance shows that we gain the best results by using the
third
approach.
--------------------------
IlliGAL Report No 2000030
The parameter-less genetic algorithm: Rational and automated
parameter
selection for simplified genetic algorithm operation
Fernando G. Lobo
Abstract:
Genetic algorithms (GAs) have been used to solve difficult
optimization
problems in a number of fields. One of the advantages of these
algorithms is that they operate well even in domains where little is
known, thus giving the GA the flavor of a general purpose problem
solver. However, in order to solve a problem with the GA, the user
usually has to specify a number of parameters that have little to do
with the user's problem, and have more to do with the way the GA
operates. This dissertation presents a technique that greatly
simplifies the GA operation by relieving the user from having to set
these parameters. Instead, the parameters are set automatically by
the
algorithm itself. The validity of the approach is illustrated with
artificial problems often used to test GA techniques, and also with
a
simplified version of a network expansion problem.
--------------------------
IlliGAL Report No 2000031
Network random keys - a tree network representation scheme for
genetic
and evolutionary algorithms
Franz Rothlauf, David E. Goldberg, Armin Heinzl
Abstract:
When using genetic and evolutionary algorithms for the design of
network structures, a good choice of the representation scheme for
the
construction of the genotype is important for the performance of the
algorithm. One of the most common representation schemes for
networks
is the characteristic vector representation. However, with encoding
tree networks, and using crossover and mutation, invalid individuals
occur that are either under- or over-specified.% and need some kind
of
repair mechanism. When constructing the offspring, or repairing the
invalid individuals that do not represent a tree, it is not possible
to
distinguish between the importance of the links which should be
used. These problems can be overcome by transferring the concept of
random keys from scheduling and ordering problems, to the encoding
of
tree networks. This paper investigates the performance of a simple
genetic algorithm (SGA) using network random keys (NetKeys) for a
One-Max-Tree and a real-world problem. The comparison between the
network random keys and the characteristic vector encoding shows
that
despite the effects of stealth mutation that favors the
characteristic
vector representation a selectorecombinative GA with NetKeys has
some
advantages for small and easy optimization problems. As soon as it
comes to more complex problems, a GA with network random keys
outperforms significantly a GA using characteristic vectors. The
paper
shows that random keys can be used for the encoding of tree
networks,
and that GAs using network random keys are able to solve complex
tree
network problems much faster than when using the characteristic
vector. Users should be encouraged to use network random keys for
the
representation of tree networks.
--------------------------
IlliGAL Report No 2000032
The Anticipatory Classifier System and Genetic Generalization
Martin Butz, David E. Goldberg, Wolfgang Stolzmann
Abstract:
The anticipatory classifier system (ACS) combines the learning
classifier system framework with the learning theory of anticipatory
behavioral control. The result is an evolutionary system that builds
an
environmental model and further applies reinforcement learning
techniques to form an optimal behavioral policy in the model. After
providing some background as well as outlining the objectives of the
system, we explain in detail all involved current
processes. Furthermore, we analyze the deficiency of
over-specialization in the anticipatory learning process (ALP), the
main learning mechanism in the ACS. Consequently, we introduce a
genetic algorithm (GA) to the ACS that is meant for generalization
of
over-specialized classifiers. We show that it is possible to form a
symbiosis between a directed specialization and a genetic
generalization mechanism achieving a learning mechanism that evolves
a
complete, accurate, and compact description of a perceived
environment. Results in three different environmental settings
confirm
the usefulness of the genetic algorithm in the ACS. Finally, we
discuss
future research directions with the ACS and anticipatory systems in
general.
--------------------------
IlliGAL Report No 2000033
Progress Toward Linkage Learning in Real-Coded GAs with Simplex
Crossover
Shigeyoshi Tsutsui, David E. Goldberg, Kumara Sastry
In recent years, many researchers have concentrated on using
real-valued genes in genetic and evolutionary algorithms
(GEAs). Previous studies have proposed simplex crossover (SPX) for
real-coded GAs. SPX has several good characteristics and works well
on
various test functions. However, SPX fails on functions that consist
of
tightly linked sub-functions. On those functions, SPX should be
applied
on each tightly linked group of parameters. In this paper, we
propose a
method of linkage identification in real-coded GAs with SPX and
evaluate it using several test functions. The mechanism works well
on
many of the test functions used. We also discuss difficulties with
the
proposed method on more complex test functions and show possible
solutions to the problems.
--------------------------
IlliGAL Report No 2000034
Ordering messy genetic algorithm in C++
Dimitri Knjazew
The OmeGA 1.0 implementation of the ordering messy genetic algorithm
in
C++ is freely available from the IlliGAL anonymous ftp-site. The
implementation covers the basic features of the OmeGA and provides
three permutation problems for testing purposes. This paper explains
how to download, compile, and run the code.
-------------------------------------------------------------
(2) NEW SOFTWARE:
1. C++ implementation of the Ordering Messy Genetic Algorithm
(OMEGA)
Dimitri Knjazew
Available at
ftp://ftp-illigal.ge.uiuc.edu/pub/src/OmeGA/omega.tar.gz
2. New version 1.1 of the BOA with decision graphs
Martin Pelikan
Available at
ftp://ftp-illigal.ge.uiuc.edu/pub/src/decisionGraphBOA/dBOA1-1.tar.Z
-------------------------------------------------------------
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: [log in to unmask] 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
----------------------------------------------
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
