[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

New IlliGAL Reports Announcement (March, 2000)



The Illinois Genetic Algorithms Laboratory (IlliGAL) is pleased to
announce the publication of the following new technical reports.
 
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 2000008

First Cognitive Capabilities in the Anticipatory Classifier System 

Wolfgang Stolzmann, Martin V. Butz, Joachim Hoffmann, and David E.
Goldberg 

Abstract:
This paper adds a new viewpoint to the Anticipatory Classifier System
(ACS). It approaches the system from a psychological perspective and
thus provides new insights to the current system. The main learning
mechanism in the ACS, the Anticipatory Learning Process (ALP), evolved
out of the psychological learning theory of anticipatory behavioral
control. The paper compares the ALP directly to this theory and reveals
the similarities. Moreover, it investigates the behavior of the ACS. By
simulating previously published rat experiments, the paper compares the
behavior of the ACS with the behavior of the rats. Finally, two further
cognitive mechanisms are introduced to the ACS. These two mechanisms
result in an animal-like behavior of the ACS in the simulations.
Furthermore, they prove the usability of the internal environmental
model for reward-learning tasks for the first time. 

==========================

IlliGAL Report No 2000009

Some Reflections on Learning Classifier Systems 

David E. Goldberg 

Abstract:

I appreciate the editors' invitation to contribute to this important
volume marking what must be called a renaissance of learning classifier
systems (LCSs). Although I have kept my finger in the LCS pie through
occasional papers on LCS subjects, the main body of my work shifted
following my 1983 dissertation applying genetic algorithms (GAs) and
LCSs to gas pipeline control; in recent years, I have largely focused my
efforts to develop (1) an effective methodology for the design of GAs,
(2) an integrated design theory for selectorecombinative GA design, (3)
competent genetic algorithms-GAs that solve hard problems, quickly,
reliably, and accurately, and (4) efficiency enhancement technologies
(EETs) for faster solutions. In this short essay, I'd like to give some
personal reflections on why I shifted my work away from learning
classifier systems, what I learned from those efforts, and why I am
renewing a more active program in LCS research. I start by reflecting on
my involvement in classifier systems back in the eighties. 

==========================

IlliGAL Report No 2000010

Research on the Bayesian Optimization Algorithm 

Martin Pelikan and David E. Goldberg 

Abstract:

This paper summarizes our recent research on the Bayesian optimization
algorithm (BOA) and outlines the directions our research in this area
has been following. It settles the algorithm in the problem
decomposition framework used often to understand the complex behavior of
genetic algorithms. It provides the most important research issues to
tackle and reviews our recent progress in each of these areas. 

==========================

IlliGAL Report No 2000011

Pruefernumbers and Genetic Algorithms: A lesson how the low locality of
an encoding can harm the performance of GAs 

Franz Rothlauf and David Goldberg 

Abstract:
When handling tree networks, researchers have sometimes tried using the
pruefernumber representation for encoding networks, but GAs often
degraded or broke down when used on this encoding. This paper
investigates the locality of the pruefernumber and its effect on the
performance of a Genetic Algorithm (GA). The locality describes how the
neighborhood of the genotype is preserved, when constructing the
phenotype (the tree) from the genotype (the pruefernumber). It is shown
that the locality of the pruefernumber is highly irregular on the entire
solution space and that the performance of a GA depends on the structure
of the optimal solution. A GA is able to perform well only for networks
that have a good locality (stars). For all other types of networks
(lists, trees) the locality is low and a GA fails to find the best list
or tree. Using a GA with the pruefernumber encoding can be useful, when
the good solutions tend to be a star. The locality of an encoding could
have a strong influence on the performance of a GA. When choosing
encodings for optimization problems, researchers should be aware of this
and be careful with low locality encodings. If the locality of the
encoding is low, a failure of the GA is often inescapable.

==========================

IlliGAL Report No 2000012

Large-Scale Permutation Optimization with the Ordering Messy Genetic
Algorithm 

Dimitri Knjazew and David E. Goldberg 

Abstract:

This paper presents a scaling analysis of the ordering messy genetic
algorithm (OmeGA), a fast messy genetic algorithm that uses random keys
to represent solutions. In experiments with hard permutation problems -
so-called ordering deceptive problems - it is shown that the algorithm
scales up as O(l^1.4) with the problem length l ranging from 32 to 512.
Moreover, the OmeGA performs efficiently with small populations thereby
consuming little memory. Since the algorithm is independent of the
structure of the building blocks, it outperforms the random key-based
simple genetic algorithm (RKGA) for loosely coded problems. 

==========================

IlliGAL Report No 2000013

Genetic Algorithms, Clustering, and the Breaking of Symmetry 

Martin Pelikan and David E. Goldberg 

Abstract:

This paper introduces clustering as a tool to improve the effects of
recombination and incorporate niching in evolutionary algorithms.
Instead of processing the entire set of parent solutions, the set is
first clustered and the solutions in each of the clusters are processed
separately. This alleviates the problem of symmetry which is often a
major difficulty of many evolutionary algorithms in combinatorial
optimization. Furthermore, it incorporates niching into genetic
algorithms and, for the first time, the probabilistic model-building
genetic algorithms. The dynamics and performance of the proposed method
are illustrated on example problems. 

==========================

IlliGAL Report No 2000014

Investigating Generalization in the Anticipatory Classifier System 

Martin V. Butz, David E. Goldberg, and Wolfgang Stolzmann 

Abstract:
Recently, a genetic algorithm (GA) was introduced to the Anticipatory
Classifier System (ACS) which surmounted the occasional problem of
over-specification of rules. This paper investigates the resulting
generalization capabilities further by monitoring in detail the
performance of the ACS in the highly challenging multiplexer task.
Moreover, by comparing the ACS to XCS in this task it is shown that the
ACS generates accurate, maximally general rules and its population
converges to those rules. Besides the observed ability of latent
learning and the formation of an internal environmental representation,
this ability of generalization adds a new advantage to the ACS in
comparison with similar approaches. 

-------------------------------------------------------------

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
----------------------------------------------