Copy Link
Add to Bookmark
Report
Alife Digest Number 014
Artificial Life Digest, Number 14
Thursday, April 5th 1990
Issue's Topics:
paper drive
Genetic algorithms and (non)-binary alphabets
re: GAs and binary coding
----------------------------------------------------------------------
Date: Thu, 5 Apr 90 22:33:42 -0500
From: Marek Lugowski <marek@iuvax.cs.indiana.edu>
Subject: paper drive
Our public alife is empty. More rigorously, iuvax:~ftp/pub/alife/papers
is empty. Please contribute something of yours or someone else's if it's
cool with them. An obscure paper is a terrific thing to ftp.
Place your generous contributions on ~ftp/pub/alife/public and we will
move them for you. A companion README.thing is requested, if gently:
Do tell what format, how long, other comments, other pointers...
Thank you.
-- Marek
alife-request@iuvax.cs.indiana.edu
------------------------------
Date: Thu, 05 Apr 90 07:50:32 CDT
From: Dave Goldberg <DGOLDBER@ua1vm.ua.edu>
Subject: Genetic algorithms and (non)-binary alphabets
Christer Ericson asks "is it really that important to use a binary
alphabet to represent individuals in genetic algorithms?" The answer is
not as straightforward as might be imagined. For many years, people
have ignored or been unaware of Holland's schema argument and have used
whatever coding they could. The German school of thought following
Rechenberg and Schwefel have always used real genes to directly encode
real decision variables. Current practitioners such as Dave Davis and
others are turning to larger alphabets with some success. On the other
hand, Holland's argument regarding maximizing the number of schemata
available by using smaller alphabets is fairly compelling (see "Zen
and the Art of GAs," ICGA 89). This disparity between practice and
theory poses something of a paradox. Is the schema theorem wrong?
Do we need strange new theories such as Antonisse's that invent new
types of don't care characters that somehow magically classify
characters with specified dissimilarity?
I think not. Just as we can imagine those problems that give a binary
GA difficulty (Bethke, 1981; Goldberg, Complex Systems, 1989, v3,
129-152, 153-171), we may also imagine those problems that cause
additional troubles for GAs coded over large cardinality alphabets. I
am preparing a manuscript that discusses such problems. Simply stated,
reproduction is a powerful force early in a GA and tends to dominate the
other operators. When coding over a large cardinality alphabet (or
"real" genes) highly fit regions are selected dimension by dimension.
Each of these regions may be thought of as a virtual character, and the
collection of them forms a virtual alphabet for each dimension.
With the problem now reduced to a small cardinality alphabet, the GA
goes about its search using building blocks formed over the virtual
alphabet. Nature abhors a vacuum, and GAs seem to abhor large
alphabets and reduce things to a more manageable set almost
immediately (in O(log n) generations, n the pop size).
So far so good, and this mode of convergence can often lead to
interesting points in the space, but it can cause difficulties if in the
vicinity of the optimum there exist barriers (multimodalities) that
prevent progress under the usual creeping mutation assumed in such
systems. This blocking phenomenon is separate from the usual kind of
deception that can cause GAs problems. If the function is not blocked
in this way, it may even be advantageous to use the higher cardinality
coding, because it chunks the problem, allowing possibly speedier
convergence. On the other hand, if the chosen coding is blocked, no
known genetic operators can reliably overcome this handicap, and therein
lies the problem. GAs with appropriate building block formation and
juxtaposition power can overcome binary deceptive problems in polynomial
time (they seem to find global optima in time of order O(l**k), where
where l is length, and k is the order of deception); however, in nonbinary
alphabets, no one has beaten the blocking problem (few people have recognized
that such a problem exists). Thus, if one is concerned with solving most
problems (and one usually turns to GAs for their robustness) without the
use of problem-specific knowledge, then there is a rigorous argument to
be made for using smaller if not smallest alphabets.
This argument will be made more rigorous in my forthcoming manuscript
"Real-coded Genetic Algorithms, Virtual Alphabets, and Kappa-Blocking."
The paper will contain the theory of virtual alphabets, computational
examples, and analytical tools for understanding blocking. The paper
will be presented at the Dortmund workshop, and the availability of
preprints will be posted on this list in a month or two.
Dave Goldberg
Dept. of Engineering Mechanics
University of Alabama
Tuscaloosa, AL 35487
dgoldber@ua1vm.ua.edu or dgoldber@ua1vm.bitnet
------------------------------
Date: Thu, 5 Apr 90 21:26:03 PDT
From: schraudo%cs@ucsd.edu (Nici Schraudolph)
Subject: re: GAs and binary coding
> From: "David M. Chess" <CHESS@ibm.com>
>
> Isn't it just as reasonable to regard a 4-ary individual:
>
> 1 0 3 0 0 2 0
>
> as being, as well as a sample of all individuals beginning with
> "1" and so on, also a sample from the set of all individuals
> whose first position is odd? I think that's just as valid
> as regarding it as a sample from the set of individuals ending
> "0 <something> 0".
>
The problem with this point of view is that unless you cheat and define
a very clever mutation operator there is no systematic way in which a
"1" in the 4-ary genome can be transformed into any other odd allele,
thus making it a very poor representative of the set of odd alleles.
In an n-bit binary representation of a "1", however, there is just such a
systematic transformation, namely crossing over the least significant bit.
> That is, you can trivially rewrite any individual written as an
> n-ary string as a binary string instead, by expanding each position
> to its binary representation. So all representations really -are-
> binary in some sense (modulo roundoff error due to non-power-of-two
> arities).
>
I would agree with that, except that if you expand an n-ary genome
into binary you would have to restrict your crossover operator
to act only at the former (n-ary) digit boundaries in order to get a
truly equivalent representation. Those boundaries, however, are now of
course several bits apart - in other words, you'll end up with less
possible crossover points than if you had started out using binary in
the first place.
It is often overlooked that it is the crossover operator that makes the
difference between representations of different arity (provided you
stick to "dumb" mutation, of course), and that lends credibility to the
schema concept. Appreciating this may help people who find it hard to
accept schema counting arguments at face value (it worked for me :-).
I recommend the following method for deciding on the arity of a GA
representation:
1) write down a binary representation;
2) mark all points where a crossover could possibly be useful;
3) find the smallest distance d between any two marked points;
4) choose (2^d) as your arity.
Unfortunately 2) depends on your exact choice of encoding - for
instance, Smith's (0, 1, #) -> binary encoding works so well because it
uses the additional crossover points to implement the useful primitives
of generalization and specialization (cf my previous posting). Other
coding schemes couldn't have done the trick, and we would have ended up
concluding that classifiers are best represented in ternary.
Since it is extremely difficult to find such clever encodings there is
a natural tendency of people to regard things as "atomic" prematurely
and use representations of above-optimal arity. The other extreme,
using binary for each and every problem, is IMHO also not the best
strategy since there are cases in which the additional crossover points
are a real disadvantage for any possible encoding. Somewhere inbetween
these two positions there is the elusive Optimal Representation (TM)...
Nici Schraudolph, C-014 nschraudolph@ucsd.edu
University of California, San Diego nschraudolph@ucsd.bitnet
La Jolla, CA 92093 ...!ucsd!nschraudolph
------------------------------
End of ALife Digest
********************************
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=---=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
= Artificial Life Distribution List =
= =
= All submissions for distribution to: alife@iuvax.cs.indiana.edu =
= All list subscriber additions, deletions, or administrative details to: =
= alife-request@iuvax.cs.indiana.edu =
= All software, tech reports to Alife depository through =
= anonymous ftp at iuvax.cs.indiana.edu in ~ftp/pub/alife =
= =
= List maintainers: Elisabeth Freeman, Eric Freeman, Marek Lugowski =
= Artificial Life Research Group, Indiana University =
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=---=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
End of Alife Digest
********************************
