[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 2001021
On the importance of the second largest eigenvalue on the convergence
rate of genetic algorithms
Schmitt, F., Rothlauf, F.
Abstract:
Genetic algorithms are sometimes disparagingly denoted as just a
fancier form of a plain, stupid heuristic. One of the main reasons
for this kind of critique is that users believed a GA could not
guarantee global convergence in a certain amount of time. Because the
proof of global convergence of GAs using elitism has been performed
elsewhere , in this work we want to extend previous work by J. Suzuki
and focus on the identification of the determinants that influence
the convergence rate of genetic algorithms. The convergence rate of
genetic algorithms is addressed using Markov chain analysis.
Therefore, we could describe an elitist GA using mutation,
recombination and selection as a discrete stochastic process.
Evaluating the eigenvalues of the transition matrix of the Markov
chain we can prove that the convergence rate of a GA is determined by
the second largest eigenvalue of the transition matrix. The proof is
first performed for diagonalizable transition matrices and then
transferred to matrices in Jordan normal form. The presented proof
allows a more detailed and deeper understanding of the principles of
evolutionary search. As an extension to this work we want to
encourage researchers to work on proper estimations of the second
largest eigenvalue of the transition matrix. With a good
approximation, the convergence behavior of GAs could be described
more exactly and GAs would be one step ahead on the road to a fast,
reliable and widely accepted optimization method.
--------------------------
IlliGAL Report No 2001022
The parameter-less genetic algorithm in practice
Lobo, F.G. and Goldberg, D.E.
Abstract:
The parameter-less genetic algorithm (Harik & Lobo, 1999), (Lobo,
2000), was recently introduced as a technique that makes genetic
algorithms easier to use. This paper shows how that technique can be
used in practice by applying it to a network expansion problem. The
existence of the parameter-less genetic algorithm stresses the fact
that some problems need more processing power than others. Such
observation lead to the development of a problem difficulty measure
which is also introduced in this paper. The measure can be very
useful for comparing the difficulty of real-world problems.
--------------------------
IlliGAL Report No 2001023
Combining the Strengths of the Bayesian Optimization Algorithm and
Adaptive Evolution Strategies
Pelikan, M., Goldberg, D.E., Tsutsui, S.
Abstract:
A method which combines competent genetic algorithms working in
discrete domains with adaptive evolution strategies working in
continuous domains is described. Discretization is used to transform
solutions between the two domains. Experiments with Bayesian
optimization algorithm, sigma-self-adaptive mutation, and three
different discretization methods are presented. The results suggest
that the algorithm scales up well on all tested problems.
-------------------------------------------------------------
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
----------------------------------------------