Copy Link
Add to Bookmark
Report
Alife Digest Number 012
Artificial Life Digest, Number 12
Wednesday, April 4th 1990
Issue's Topics:
measures of entropy in alife models (ComMet)
GAs and binary coding
----------------------------------------------------------------------
Date: Mon, 2 Apr 90 15:37:19 -0500
From: Marek Lugowski <marek@iuvax.cs.indiana.edu>
Subject: measures of entropy in alife models (ComMet)
I am aware of measures of entropy in cellular automata work.
Question to the list membership: are these measures sufficient to
characterize the relevant change in disorder in life simulations?
Would you happen to have a candidate measure of entropy that significantly
differs from those used in cellular automata to share with us?
A more focused question:
For those of you who recall our Computational Metabolism (ComMet) from
the Santa Fe alife2 workshop -- what do you think would be a good
entropy measure for us? We are interested in identifying the phase
transitions between the Chris Langton-stipulated fluid and solid
states of information.
For us this appears to translate into the geometric transitions in the
aggregation of individual tiles that comprise ComMet. These
transitions are the deterministic global consequences of strictly
local rules that allow random choice.
We define the workings of ComMet in such a way that tiles sharing the
same description migrate into a contiguous area of the tiling -- and
form patches of same color we can examine by eye. We have found this
to happen both on the torus and, much more managably humane on the
human perception, the square. The interesting part is the partial
emergence of order which features twisted shapes and curved surfaces and
displacement from one contained blob to another.
Phase transitions may also occur over different classes of ComMet
instances as well as over meta-sequences. Meta-sequences are lists of
snapshots from the various points in the development of possible-world
ComMets: e.g.,la list of snapshots from one start-up state undergoing
development in one geometry (torus) for a variable number of
generations, then run for a fixed time in another geometry (square).
We call these sifting-color-patch instances of ComMet "emergent
mosaics". We thought at first that the "emergent" was to mean the
ex nihilo generation of Mondrian-like images (not really ex nihilo,
since tehy are expressed locally and implicitly as swap preferences;
each tile of a given color shares the same set). Now, however we
realize that the interesting emergence lies in the in-between land
when the hashed-looking tiles precipitate into swirls of color patches
on the way to the Mondrian-like rectilinear "solid". It is this in-between
state that we would like to first characterize and later manipulate,
pssibly to eefect development, possibly to effect abstract computation.
We are still attempting to understand what has a bearing on the
transitions of in-betweenness (possibly a modest example of the edge
of chaos Chris Langton advances), which is why a measure (or measures)
of entropy on various levels of ComMet order are a priority now.
The emergence in emergent mosaics, and other ComMet instances, is on
the level of partial (not-yet-solid) states of information and we are
attempting to find an entropy measure that would allows us to run
large numbers of instances of ComMet, picking out only those where a
suspected interesting phase transition might have taken place -- by
looking for telltale spikes in this measure over long histories and
separate configurations. Right now we are experimenting with (a) and
soon maybe with (b) below (both suggested by Eric Freeman).
The instances of Computational Metabolism whose tiles attempt to swap
places with their neighbors in the 5-neighborhood tiling are fluids in
the intuitive sense of what a fluid is. In fact, they are "ideal
fluids" for the molecules (tiles) never undergo state changes or
non-edge-local attractive or field forces, only displacement within
the tiling, and volume conserving at that. It would thus seem that
we could entertain the following entropy measures as functions defined on:
(a) individual swap requests, count of or some monotonic f(count of).
(b) actual swaps that happened (requited requests), count of or etc.
(c) textual monte carlo-like counts of color (species) densities
within a fixed sampled area of tiling, or some monotonic f(c).
Computational Metabolism is described in _Artificial Life_, Christopher
Langton, ed., pp. 343-368, Addison-Wesley, 1989, "Computational
Metabolism: Towards Biological Geometries for Computing", M. Lugowski.
-- Marek Lugowski
Artificial Life Research Group
Computer Science Department
Lindley Hall 101
Indiana University
Bloomington, Indiana 47405
U.S.A.
marek@iuvax.cs.indiana.edu
------------------------------
Date: Wed, 4 Apr 90 10:52:30 EDT
From: ds1@philabs.philips.com (Dave Schaffer)
Subject: GAs and binary coding
On the issue of using binary coding with genetic algorithms (GAs).
In the GA community, the use of binary representations has become
almost sacred. The original arguments put forward by Holland
(ANAS 1975, p71) are simple and compelling. Suppose we compare
a decimal representation and a binary one for a space with about
a million instances. We would need a string length of 6 in the
decimal case and 20 in the binary (2**20 ~ 10**6).
Now, the implicit parallelism of GAs works by propagating in
the gene pool, the schemata sampled in the more fit individuals.
The number of schemata instantiated in an individual is 2**L,
where L is the string length. Clearly there are many more schemata
instantiated in the individuals using the binary representation.
Hence there is a much richer set of schemata for exploration/exploitation.
The "empirical evidence" I referred to was one small experiment I
conducted with a classifier system that was trying to learn a
pattern discrimination task. I was using Steve Smith's KS1
Knowledge Structure [Smith, Ph.D. Dissertation, Pitt, 1980]
which codes the classifier IF strings in binary. Now these
IF strings are naturally ternary {0,1,#}, so we have the problem
Christer Ericson mentions, what to do with the extra bit patterns?
Smith used a redundant mapping:
00 -> 0
11 -> 1
01,10 -> #
When my system had difficulty learning its task, I focused in
on this redundancy. There are many different genotypes that
represent the same phenotype. Furthermore, two parents with
"#" at some position may produce offspring with either of the
other alleles giving crossover a mutating effect. These bad
effects had to be weighed against the richer schema sampling
available to the binary representation, but after all, 3 is not
THAT much larger than 2, so why not try it? In my experiments,
the binary representation consistently outperformed the ternary.
I would hardly claim that this evidence is very compelling. It was
only a single case, and involved the additional complexities of
classifier systems to boot. Still, it's the only evidence I know.
BTW Dave Davis is also fond of non-binary representations and gets
good results [see for example Coombs & Davis ICGA-87 or Davis ICGA-89
p61].
An alternative to using redundant codings (which I tend to favor) is
to assign the unused codes a NOP, as Ericson suggests. The question
of how to handle these in the evaluation then must be addressed. If
they render a chromosome non-viable, then some form of penalty must
be used which opens another can of worms.
[see for instance, Richardson, Palmer, Liepins and Hilliard, ICGA-89]
It may make the job of finding feasible solutions so difficult,
that the GA is unable to effectively search for good solutions.
In a population of infeasible cousins, a feasible solution may look
so fit that it quickly takes over, rapidly reducing the genetic
variance in the pool.
There have been opinions expressed in favor of non-binary representations.
[see Antonisse, ICGA-89] but a schema sampling theorem for them,
I have not yet seen. And another thing, there are obviously important
differences among binary schemes [see Caruana and Schaffer, Machine
Learning Conf 88, Caruana Schaffer & Eshelman MLC-89].
On the whole, I think of this issue as one component of the art of
designing a representation. The GA cannot work well if it cannot
find building blocks, but designing representations for non-trivial
problems is still largely a black art, as far as I can see.
Dave Schaffer
------------------------------
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
********************************
