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

IlliGAL New Technical Reports Announcement (March 2002)



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 2002001

Simplex crossover and linkage identification: Single-stage evolution
vs. multi-stage evolution

Tsutsui, S., Goldberg, D.E.

Abstract:
Previous studies have proposed simplex crossover (SPX) for
real-coded GAs. In this paper, we propose two types of linkage
identification for simplex crossover; linkage identification with
single-stage evolution (LISS) and linkage identification with
multi-stage evolution (LIMS), and perform their comparative study.
Results showed LIMS has more stable performance than LISS.

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

IlliGAL Report No 2002002

Genetic Algorithms, Efficiency Enhancement, and Deciding Well with
Differing Fitness Variances

Sastry, K., and Goldberg, D. E.

Abstract:
This study investigates the decision making between fitness function
with differing variance and computational-cost values. The objective
of this decision making is to provide evaluation relaxation and thus
enhance the efficiency of the genetic search. A decision-making
strategy has been developed to maximize speed-up using facetwise
models for the convergence time and population sizing. Results
indicate that using this decision making, significant speed-up can
be obtained.

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

IlliGAL Report No 2002003

Genetic Algorithms, Efficiency Enhancement, and Deciding Well with
Differing Fitness Bias Values

Sastry, K., Goldberg, D. E.

Abstract:
This study develops a decision-making strategy for deciding between
fitness functions with differing bias values. Simple, yet practical
facetwise models are derived to aid the decision-making process. The
decision making strategy is designed to provide maximum speed-up and
thereby enhance the efficiency of GA search processes. Results
indicate that bias can be handled temporally and that significant
speed-up values can be obtained.

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

IlliGAL Report No 2002004

Evaluation-Relaxation Schemes for Genetic and Evolutionary
Algorithms

Sastry, K.

Abstract:
Genetic and evolutionary algorithms have been increasingly applied
to solve complex, large scale search problems with mixed success.
Competent genetic algorithms have been proposed to solve hard
problems quickly, reliably and accurately. They have rendered
problems that were difficult to solve by the earlier GAs to be
solvable, requiring only a subquadratic number of function
evaluations. To facilitate solving large-scale complex problems, and
to further enhance the performance of competent GAs, various
efficiency-enhancement techniques have been developed. This study
investigates one such class of efficiency-enhancement technique
called evaluation relaxation.
Evaluation-relaxation schemes replace a high-cost, low-error fitness
function with a low-cost, high-error fitness function. The error in
fitness functions comes in two flavors: Bias and variance. The
presence of bias and variance in fitness functions is considered in
isolation and strategies for increasing efficiency in both cases are
developed. Specifically, approaches for choosing between two fitness
functions with either differing variance or differing bias values
have been developed. This thesis also investigates fitness
inheritance as an evaluation-relaxation scheme. In fitness
inheritance, the fitness values of some individuals are inherited
from their parents rather than through a costly evaluation function,
thereby reducing the total function-evaluation cost.
Simple facetwise models have been derived to capture the dynamics in
each case and have been verified with simple but illustrating
empirical results. These models are also used to develop analytical
framework to tune algorithm parameters to obtain maximum speed-up. 

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

IlliGAL Report No 2002005

Efficient Genetic Algorithms using Discretization Scheduling

Albert, L.A.

Abstract:
In many applications of genetic algorithms, there is a tradeoff
between speed and accuracy in fitness evaluations when evaluations
are relaxed from using numerical methods such as numerical
integration. In these types of applications, the cost and accuracy
vary from discretization errors when implicit or explicit quadrature
is used to estimate the function evaluations. There may be several
functions with different grid sizing to obtain a given solution
quality. This thesis examines discretization scheduling, or how to
vary the discretization within the genetic algorithm in order to use
the least amount of computation time for a solution of a desired
quality. The effectiveness of discretization scheduling can be
determined by comparing its computation time to the computation time
of a GA using a constant discretization. Time budgeting is used to
estimate the computational resources needed, and there are three
ingredients for the discretization scheduling: population sizing,
estimated time for each function evaluation and predicted
convergence time analysis. Idealized one- and two-dimensional
experiments and an inverse groundwater application illustrate the
computational savings to be achieved from using discretization
scheduling.

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

IlliGAL Report No 2002006

Efficient Discretization Scheduling in Multiple Dimensions

Albert, L.A., Goldberg, D.E.

Abstract:
There is a tradeoff between speed and accuracy in fitness
evaluations when various discretization sizes are used to estimate
the fitness. This paper introduces discretization scheduling, which
varies the size of the discretization within the GA, and compares
this method to using a constant discretization. It will be shown
that when scheduling the discretization, less computation time is
used without sacrificing solution quality. Fitness functions whose
cost and accuracy vary because of discretization errors from
numerical integration are considered, and the speedup achieved from
using efficient discretizations is predicted and shown empirically. 

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

IlliGAL Report No 2002007

Introducing Start Expression Genes to the Linkage Learning Genetic
Algorithm

Chen, Y.-P., Goldberg, D.E.

Abstract:
This paper discusses the use of start expression genes and a
modified exchange crossover operator in the linkage learning genetic
algorithm (LLGA) that enables the genetic algorithm to learn the
linkage of building blocks (BBs) through probabilistic expression
(PE). The difficulty that the original LLGA encounters is shown with
empirical results. Based on the observation, start expression genes
and a modified exchange crossover operator are proposed to enhance
the ability of the original LLGA to separate BBs and to improve
LLGA's performance on uniformly scaled problems. The effect of the
modifications is also presented in the paper.

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

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

----------------------------------------------
 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
 E-mail: pelikan@illigal.ge.uiuc.edu
 WWW: http://www-illigal.ge.uiuc.edu/~pelikan/
----------------------------------------------