Evolution of Emergent Behavior using Genetic Programming

[Jochen Fromm-2]

A big problem in engineering self-organising systems
with "emergent properties" is the lack of a systematic
approach to build a solution that meets the requirements.
The only standard approach is named "Genetic Programming".
In this approach the "requirements" are specified by a
fitness function. With genetic algorithms, you can find
rules that produce certain forms of emergent behavior.
John R. Koza devotes the entire chapter 12 "Evolution of
Emergent Behavior" of his book "Genetic Programming" [1]
to the construction of self-organizing systems with
emergent properties through genetic algorithms.
He says correctly "if it is true that complex overall behavior
can be produced from sets of relatively simple rules, it
should be possible to evolve such sets of rules by means of
genetic programming" (p.329)

One of the fathers of genetic algorithms besides Koza
is John H. Holland [2]. Koza *and* Holland are (or have been)
affiliated with the SFI, which was since the beginning
interested in self-organization and emergence.
Why are there nearly no papers and articles about
the use of genetic algorithms to create self-organizing systems ?
Beside one paper and the book-chapter from John R. Koza, I have
found nearly nothing about the construction of self-organizing system
through genetic algorithms. There seem to be a lack of papers
on this topic. A google search for "genetic algorithm" combined with
"neural networks" gives roughly 300,000 results, a google search for
"genetic algorithm" combined with "emergent behavior" or
"self-organizing systems" only about 7,000 results.

J.

[1]
John R. Koza, "Genetic Programming:
On the Programming of Computers by Means of Natural Selection"
The MIT Press, 1992

[2]
John H. Holland
"Adaptation in Natural and Artificial Systems:
An Introductory Analysis with Applications to Biology, Control, and
Artificial Intelligence"
University of Michigan Press (1975)
The MIT Press; Reprint edition (1992)

[Russell Standish]

Maybe its a matter of terminology. I have reviewed dozens of
papers for things like the GECCO conference dealing with evolving
rules for swarms of robots to perform some kind of task. This would
count as evolving self-organised behaviour.

I'm surprised you haven't seen any of this literature. Its not really
my field, but if you still have trouble finding stuff, I'll dig up a
few references for you.

Cheers


On Mon, Mar 14, 2005 at 04:29:43PM +0100, Jochen Fromm wrote:

>
> A big problem in engineering self-organising systems
> with "emergent properties" is the lack of a systematic
> approach to build a solution that meets the requirements.
> The only standard approach is named "Genetic Programming".
> In this approach the "requirements" are specified by a
> fitness function. With genetic algorithms, you can find
> rules that produce certain forms of emergent behavior.
> John R. Koza devotes the entire chapter 12 "Evolution of
> Emergent Behavior" of his book "Genetic Programming" [1]
> to the construction of self-organizing systems with
> emergent properties through genetic algorithms.
> He says correctly "if it is true that complex overall behavior
> can be produced from sets of relatively simple rules, it
> should be possible to evolve such sets of rules by means of
> genetic programming" (p.329)
>
> One of the fathers of genetic algorithms besides Koza
> is John H. Holland [2]. Koza *and* Holland are (or have been)
> affiliated with the SFI, which was since the beginning
> interested in self-organization and emergence.
> Why are there nearly no papers and articles about
> the use of genetic algorithms to create self-organizing systems ?
> Beside one paper and the book-chapter from John R. Koza, I have
> found nearly nothing about the construction of self-organizing system
> through genetic algorithms. There seem to be a lack of papers
> on this topic. A google search for "genetic algorithm" combined with
> "neural networks" gives roughly 300,000 results, a google search for
> "genetic algorithm" combined with "emergent behavior" or
> "self-organizing systems" only about 7,000 results.
>
> J.
>
> [1]
> John R. Koza, "Genetic Programming:
> On the Programming of Computers by Means of Natural Selection"
> The MIT Press, 1992
>
> [2]
> John H. Holland
> "Adaptation in Natural and Artificial Systems:
> An Introductory Analysis with Applications to Biology, Control, and
> Artificial Intelligence"
> University of Michigan Press (1975)
> The MIT Press; Reprint edition (1992)
>
>
>
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9AM @ Jane's Cafe
> Lecture schedule, archives, unsubscribe, etc.:
> http://www.friam.org

--
*PS: A number of people ask me about the attachment to my email, which
is of type "application/pgp-signature". Don't worry, it is not a
virus. It is an electronic signature, that may be used to verify this
email came from me if you have PGP or GPG installed. Otherwise, you
may safely ignore this attachment.

----------------------------------------------------------------------------
A/Prof Russell Standish             Director
High Performance Computing Support Unit, Phone [phone] (mobile)
UNSW SYDNEY 2052                     Fax   [phone] (")
Australia             [hidden email]            
Room 2075, Red Centre                    http://parallel.hpc.unsw.edu.au/rks
            International prefix  +612, Interstate prefix 02
----------------------------------------------------------------------------

[Dan Kunkle]

I tried the Google searches you mentioned and my web page comes up  
first when searching for 'genetic algorithm self-organizing systems',  
so I guess I'll throw my opinion in ;-) (note, this probably just means  
I like to use those words a lot).

First, a few definitions to make explicit. Genetic algorithms are a  
search mechanism. Genetic programming is a closely related mechanism  
that searches over the space of programs. These search methods can be  
considered self-organizing systems. However, not all optimized systems  
(or programs) found by these search methods are themselves  
self-organizing. For example, Koza uses genetic programming to find  
novel designs for electronic circuits. As far as I recall, these  
circuits would not be considered self-organizing under most  
definitions.

Now, we may want to use search methods to specifically find  
self-organizing systems that solve some problem or satisfy some  
constraints (instead of any general system that solves the problem).  
Side note: there are two reasons this might be useful: 1) For the study  
of self-organizing systems in general. If we can automatically search  
for self-organizing systems of a specific type we may be better able to  
study them; 2) Self-organizing systems have certain properties that  
would be desirable to include in the solution to a specific problem (a  
list of such features appears at  
http://www.calresco.org/sos/sosfaq.htm#2.6).

I see two methods of specifically searching for self-organizing systems:

** Method 1: Restrict the search space to only those solutions that are  
self-organizing. (This is what I've normally seen in the existing  
literature).

It seems this is the case in chapter 12 of Koza. He defines the  
primitive operations of an ant-like food foraging system and then uses  
genetic programming to develop a near-optimal version of the system. In  
this case, Koza has restricted his search space in such a way that all  
solutions are self-organizing solutions.

As another example, consider using genetic algorithms to find cellular  
automata that exhibit some specific behavior. Because we're using CA,  
pretty much any behavior is going to be emergent behavior and any  
organization will arise through self-organization. For some details see  
the SFI EvCA group (http://www.santafe.edu/projects/evca/). For some  
additional analysis along the same lines, see "Evolutionary Methods for  
2-D Cellular Automata Computation"  
(http://www.redfish.com/dkunkle/mypapers/gacaProj.pdf).

You can do this with pretty much any self-organizing system. Basically,  
build the system as far as you can, then fill in the gaps (i.e.  
optimize the parameter settings) with a search. The self-organizing  
nature doesn't arise from the search (GA/GP), it was built-in by the  
definer of the search space.

** Method 2: Include a quantitative measure of self-organization in the  
fitness function. (I haven't seen this done yet).

Here the search is focused on not only finding a solution, but  
specifically a self-organizing solution (out of a space of solutions  
that contains some non-self-organizing solutions). This is similar to  
other "side conditions" that are sometimes included in fitness  
functions. For example, genetic programming usually includes program  
size as a fitness measure: smaller programs are better than larger  
programs that do the same thing. Unfortunately, a quantitative measure  
of the level of self-organization a system displays is not as easy as  
determining the size of a program.

The above two methods of searching for self-organizing solutions bring  
up two corresponding questions.

** Question 1: Is there a general model of self-organizing computation?  
Here, I'm thinking along the lines of the following analogy: A  
self-organizing machine is a model of self-organizing computation in  
the same way that a Turing machine is a model of generalized  
computation.

We then should be able to use genetic programming over the  
self-organizing machine to solve general problems.

** Question 2: Is there a function that given a general system can  
determine its level of "self-organizing nature". In other words, can we  
quantify self-organization?

If so, we can use this function as part of our search's fitness  
function.

I think a formal definition of "self-organizing computation" is key to  
the above issues.

See the following reference for some related discussion.

Gambhir, M., Guerin, S., Kauffman,  S., Kunkle, D. (2004) Steps  toward  
a possible theory of organization. In: Proceedings  of International  
Conference on Complex Systems 2004.  Boston, MA.  
(http://www.redfish.com/research/ 
NECSI_StepsTowardPossibleOrganization_v0_8.pdf)

-Dan

On Mar 14, 2005, at 10:29, Jochen Fromm wrote:

> A big problem in engineering self-organising systems
> with "emergent properties" is the lack of a systematic
> approach to build a solution that meets the requirements.
> The only standard approach is named "Genetic Programming".
> In this approach the "requirements" are specified by a
> fitness function. With genetic algorithms, you can find
> rules that produce certain forms of emergent behavior.
> John R. Koza devotes the entire chapter 12 "Evolution of
> Emergent Behavior" of his book "Genetic Programming" [1]
> to the construction of self-organizing systems with
> emergent properties through genetic algorithms.
> He says correctly "if it is true that complex overall behavior
> can be produced from sets of relatively simple rules, it
> should be possible to evolve such sets of rules by means of
> genetic programming" (p.329)
>
> One of the fathers of genetic algorithms besides Koza
> is John H. Holland [2]. Koza *and* Holland are (or have been)
> affiliated with the SFI, which was since the beginning
> interested in self-organization and emergence.
> Why are there nearly no papers and articles about
> the use of genetic algorithms to create self-organizing systems ?
> Beside one paper and the book-chapter from John R. Koza, I have
> found nearly nothing about the construction of self-organizing system
> through genetic algorithms. There seem to be a lack of papers
> on this topic. A google search for "genetic algorithm" combined with
> "neural networks" gives roughly 300,000 results, a google search for
> "genetic algorithm" combined with "emergent behavior" or
> "self-organizing systems" only about 7,000 results.
>
> J.
>
> [1]
> John R. Koza, "Genetic Programming:
> On the Programming of Computers by Means of Natural Selection"
> The MIT Press, 1992
>
> [2]
> John H. Holland
> "Adaptation in Natural and Artificial Systems:
> An Introductory Analysis with Applications to Biology, Control, and
> Artificial Intelligence"
> University of Michigan Press (1975)
> The MIT Press; Reprint edition (1992)

[Robert Holmes]

 

> -----Original Message-----
> From: Daniel Kunkle [mailto:[hidden email]]
> Sent: Monday, March 14, 2005 6:10 PM
> To: The Friday Morning Applied Complexity Coffee Group
> Subject: Re: [FRIAM] Evolution of Emergent Behavior using
> Genetic Programming
>
> I tried the Google searches you mentioned and my web page
> comes up first when searching for 'genetic algorithm
> self-organizing systems', so I guess I'll throw my opinion in
> ;-) (note, this probably just means I like to use those words a lot).
>
> First, a few definitions to make explicit. Genetic algorithms
> are a search mechanism. Genetic programming is a closely
> related mechanism that searches over the space of programs.
> These search methods can be considered self-organizing
> systems.

OK, I'm being dumb as a rock. Can other search techniques be considered
self-organizing? If not, what is that makes a GA self-organizing but (say)
gradient descent not?

[Russell Standish]

On Mon, Mar 14, 2005 at 06:42:12PM -0700, Robert Holmes wrote:

>  
>
> > -----Original Message-----
> > From: Daniel Kunkle [mailto:[hidden email]]
> > Sent: Monday, March 14, 2005 6:10 PM
> > To: The Friday Morning Applied Complexity Coffee Group
> > Subject: Re: [FRIAM] Evolution of Emergent Behavior using
> > Genetic Programming
> >
> > I tried the Google searches you mentioned and my web page
> > comes up first when searching for 'genetic algorithm
> > self-organizing systems', so I guess I'll throw my opinion in
> > ;-) (note, this probably just means I like to use those words a lot).
> >
> > First, a few definitions to make explicit. Genetic algorithms
> > are a search mechanism. Genetic programming is a closely
> > related mechanism that searches over the space of programs.
> > These search methods can be considered self-organizing
> > systems.
>
> OK, I'm being dumb as a rock. Can other search techniques be considered
> self-organizing? If not, what is that makes a GA self-organizing but (say)
> gradient descent not?
>

There has to be a confusion of terminology here. The Evolutionary
Algorithm is not self-organising per se, but can be applied to a
self-organising system. The aim is to find a set of microscopic rules
of the self-organising system that can reproduce the target
macroscopic behaviour. The optimisation function is a distance measure
of the system's behavious from the target behaviour.

Of course, gradient descent can also be applied to a parametrised
self-organising system - unfortunately it is typically not successful
because of the rugged nature of the optimisation function.

Cheers

--
*PS: A number of people ask me about the attachment to my email, which
is of type "application/pgp-signature". Don't worry, it is not a
virus. It is an electronic signature, that may be used to verify this
email came from me if you have PGP or GPG installed. Otherwise, you
may safely ignore this attachment.

----------------------------------------------------------------------------
A/Prof Russell Standish             Director
High Performance Computing Support Unit, Phone [phone] (mobile)
UNSW SYDNEY 2052                     Fax   [phone] (")
Australia             [hidden email]            
Room 2075, Red Centre                    http://parallel.hpc.unsw.edu.au/rks
            International prefix  +612, Interstate prefix 02
----------------------------------------------------------------------------

[Jochen Fromm-2]

 
> Is there a function that given a general system can
> determine its level of "self-organizing nature". In
> other words, can we quantify self-organization?
> If so, we can use this function as part of our search's
> fitness function.


Can you quantify self-organization or emergence ? Interesting
question. Perhaps you would have to measure the complexity
of macropscopic patterns/structures/behavior divided through
the complexity of local, microscopic rules (through
some kind of "Kolmogorov Complexity" measure). True or
genuine emergent behavior is certainly reached if
combinatorial explosion makes the control of macroscopic
behavior through low-level laws impossible, see
http://groups.yahoo.com/group/CAS-Group/message/456
(according to Paul Davies, the "Landauer-Wheeler-Lloyd limit"
for the onset of true emergent behaviour)
 
The question was originally why there is a lack of papers on
the topic. A project like EvMAS (Evolving self-organized MAS)
similar to EvCA (Evolving Cellular Automata) does not
seem to exist. As Russell said, it is maybe a matter of
terminology, and I searched for the wrong terms.

Other reasons are:
* all interesting rules have already been found,
  for flocking, ant foraging, termites heap building, etc.
  (see http://ccl.northwestern.edu/netlogo/models/)
* there are some technical difficulties with finding
  a suitable fitness meaure, a formal specification of
  agent behavior, or a useful "genetic representation"
  of the problem

What we would like to find are system where each agent
follows a set of very simple rules (and where the set of
rules is as small as possible), although the system as
a whole acts in a sophisticated or complex way.

The individual decision of each agent which task to
perform can depend on pheromone fields (environment-agent
constraints as in ant based systems) and on the average type
of interaction with other agents (agent-agent or group-constraints
as in flocking systems), or combinations of both. Have we
found already all interesting solutions ?

Consider for example a transport system at a large warehouse,
for instance Amazon.com. Many autonomous vehicles have to
pick packets at certain places, transport them over some
kind of space or network, and drop them at particular
destinations - all this of course in an optimal way.
Do you think it is possible to create a self-organizing
system with GP or GA which solves this problem ?

J.