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 2000015
Time complexity of genetic algorithms on exponentially scaled
problems
Fernando Lobo, David E. Goldberg, Martin Pelikan
Abstract:
This paper gives a theoretical and empirical analysis of the time
complexity of genetic algorithms (GAs) on problems with
exponentially scaled building blocks. It is important to study GA
performance on this type of problems because one of the
difficulties that GAs are generally faced with is due to the low
scaling or low salience of some building blocks. The paper is an
extension of the model introduced by Thierens, Goldberg, and
Pereira (1998) for the case of building blocks rather than single
genes, and the main result is that under the assumption of perfect
building block mixing, both population size and time to
convergence grow linearly with the problem length, giving an
overall quadratic time complexity in terms of fitness function
evaluations. With traditional simple GAs, the assumption of perfect
mixing only occurs when the user has knowledge about the structure
of the problem (which is usually not true). However, the assumption
is well approximated for advanced GAs that are able to
automatically learn gene linkage.
--------------------------
IlliGAL Report No 2000016
Probability-Enhanced Predictions in the Anticipatory Classifier
System
Martin V. Butz, David E. Goldberg, Wolfgang Stolzmann
Abstract:
The Anticipatory Classifier System (ACS) recently showed many
capabilities new to the Learning Classifier System field. Due to
its enhanced rule structure with an effect part, it forms an
internal environmental representation, learns latently besides the
common reward learning, and can use many cognitive processes. This
paper introduces a probability-enhancement in the predictions of
the ACS which enables the system to handle different kinds of
non-determinism in an environment. Experiments in two different
mazes will show that the ACS is now able to handle action-noise and
irrelevant random attributes in the perceptions. Furthermore,
applications with a recently introduced GA will reveal the general
independence of the two new mechanism as well as the ability of the
GA to substantially decrease the population size.
--------------------------
IlliGAL Report No 2000017
An Algorithmic Description of XCS
Martin V. Butz, Stewart W. Wilson
A concise description of the XCS classifier system's parameters,
structures, and algorithms is presented as an aid to research. The
algorithms are written in modularly structured pseudo code with
accompanying explanations.
--------------------------
IlliGAL Report No 2000018
A Hydroinformatician's Approach to Computational Innovation and the
Design of Genetic Algorithms
David E. Goldberg
Abstract: not available
--------------------------
IlliGAL Report No 2000019
A Meditation on Computational Intelligence and Its Future
David E. Goldberg
Abstract: not available
--------------------------
IlliGAL Report No 2000020
Bayesian Optimization Algorithm, Decision Graphs, and Occam's Razor
Martin Pelikan, David E. Goldberg, Kumara Sastry
Abstract:
This paper discusses the use of various scoring metrics in the
Bayesian optimization algorithm (BOA) which uses Bayesian networks
to model promising solutions and generate the new ones. The use of
decision graphs in Bayesian networks to improve the performance of
the BOA is proposed. To favor simple models, a complexity measure
is incorporated into the Bayesian-Dirichlet metric for Bayesian
networks with decision graphs. The presented algorithms are
compared on a number of interesting problems.
--------------------------
IlliGAL Report No 2000021
You Know You're anExcellent Senior Design Team If You...
Abstract: not available
--------------------------
IlliGAL Report No 2000022
Application of the Fast Messy Genetic Algorithm to Permutation and
Scheduling Problems
Knjazew, D.
(A master thesis from the University of Dortmund)
Abstract:
Various genetic and evolutionary algorithms (GEAs) have been
developed for solving permutation problems over the past few
years. Research in this area is very interesting, since there is a
great variety of permutation-based commercially important
applications including the traveling salesman problem, vehicle
route planning, integrated circuit design, timetabling, and
scheduling. Unfortunately, most of the methods use either
problem-specific or ad-hoc representation codings and
operators. Also, only little research has been done to investigate
the scalability of permutation-solving GEAs. This thesis focuses on
an advanced genetic algorithm with a good scale-up behavior the
fast messy genetic algorithm (fmGA). It is specialized for solving
permutation problems and uses random keys to represent
solutions. The purpose of the thesis is to demonstrate its
applicability to real world permutation problems. First, we develop
the algorithm and analyze its performance and scalability on
artificial permutation problems. Finally, we apply the GA to a
scheduling benchmark from the German company SAP.
--------------------------
IlliGAL Report No 2000023
Genetic Algorithms at the University of Illinois Spring 2000
David E. Goldberg (ed.)
Abstract: not available (this report is a collection of a number
of papers from the course GE485 at the Department of General
Engineering, from the term Spring 2000).
--------------------------
IlliGAL Report No 2000024
Search Space Boundary Extension Method in Real-Coded Genetic
Algorithms
Tsutsui, S., David E. Goldberg
Abstract:
In real-coded genetic algorithms, some crossover operators do not
work well on functions which have their optimum at the corner of
the search space. To cope with this problem, we have a proposed
boundary extension methods which allows individuals to be located
within a limited space beyond the boundary of the search space. In
this paper, we give an analysis of the boundary extension methods
from the view point of sampling bias and perform a comparative
study on the effect of applying two boundary extension methods,
namely the BEM (boundary extension by mirroring) and the BES
(boundary extension with extended selection). We were able to
confirm that to use sampling methods which have smaller sampling
bias had good performance on both functions which have their
optimum at or near the boundaries of the search space, and
functions which have their optimum at the center of the search
space. The BES/SD/A (BES by shortest distance selection with aging)
had good performance on functions which have their optimum at or
near the boundaries of the search space. We also confirmed that
applying the BES/SD/A did not cause any performance degradation on
functions which have their optimum at the center of the search
space.
--------------------------
IlliGAL Report No 2000025
A C++ Implementation of the Bayesian Optimization Algorithm (BOA)
with Decision Graphs
Martin Pelikan
Abstract:
The paper explains how to download, compile, and use the C++
implementation of the Bayesian optimization algorithm (BOA) with
decision graphs (Pelikan, Goldberg, & Sastry, 2000). It provides
the instructions for creating input files for the BOA to solve
various problems with various parameter settings and for adding new
test functions into the existing code. Outputs of an example
experiment are discussed.
--------------------------
IlliGAL Report No 2000026
On Extended Compact Genetic Algorithm
Kumara Sastry, David E. Goldberg
Abstract:
In this study we present a detailed analysis of the extended
compact genetic algorithm (ECGA). Based on the analysis,
empirical relations for population sizing and convergence time
have been derived and are compared with the existing
relations. We then apply ECGA to a non-azeotropic binary
working fluid power cycle optimization problem. The optimal
power cycle obtained improved the cycle efficiency by 2.5%
over that existing cycles, thus illustrating the capabilities
of ECGA in solving real-world problems.
---------------------------
IlliGAL Report No 2000027
XCSJava 1.0: An implementation of the XCS classifier system
in Java
Martin V. Butz
Abstract:
The XCSJava 1.0 implementation of the XCS classifier system
in Java is freely available from the IlliGAL anonymous
ftp-site. The implementation covers the basic features of the
XCS classifier system and provides a multiplexer and maze
environment for testing purposes. This paper explains how to
download, compile, and run the code. Moreover, it explains
the object oriented approach in the implementation and the
possible parameter manipulation as well as the environmental
interface to hook in other test environments. Additionally to
the source code, an executable package of the version as well
as an XCSJava 1.0 API documentation is provided.
-------------------------------------------------------------
(2) NEW SOFTWARE:
1. C++ Implementation of the Bayesian Optimization Algorithm
(BOA) with Decision Graphs
version 1.0
Martin Pelikan
Available at
ftp://ftp-illigal.ge.uiuc.edu/pub/src/decisionGraphBOA/dBOA.tar.Z
2. Java Implementation of the XCS Classifier System (XCSJava)
version 1.0
Martin V. Butz
Available at
ftp://ftp-illigal.ge.uiuc.edu/pub/src/XCSJava/XCSJava1.0.tar.Z
3. XCS classifier system implementation
version 1.1
Martin V. Butz
Available at
ftp://ftp-illigal.ge.uiuc.edu/pub/src/XCS/XCS-C1.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
----------------------------------------------
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
