Evolution of Complex Systems

Evolution of Complex Systems - Self Organization

by Umur Ozkul, email: Umur@WriteMe.Com , 1996

A system based on evolution might be able to generate smart designs (i.e. Nature). In the future, when the greedy random number needs of the genetic algorithms can be satisfied by chaotic series via quantum properties of micro design, the speed of evolutionary systems will be beyond our imagination, far surpassing the speed that can be possible by massive parallelism only. Here we briefly examine the Nature's tools to make smart designs. And examine how can we adapt them to computers. The challenge is to trigger self-organization, evolution of complexity.

1 Table of Contents

2 Motivation

Complexity in human-made programs is increasing very fast since the adaptation of object oriented paradigm. Encapsulation and reusability allow us to build higher levels of programs all the time. Encapsulated object classes evolve and mature trough correction and use in many projects. Objects are very similar to cellular organisms. Can they evolve and mature as cellular organisms do? This is what we are trying to accomplish.

2.1 Challenges

As diversity requires abundant resources, hierarchical symbiotic evolution is requesting massively parallel computers. However, evolution exploits the concurrency very well. Moreover hierarchical symbiotic evolution is promising to generate well-designed parallel programs. Functional or logic programs that naturally take advantage of concurrency can be the product of evolution. Well, evolution can even answer the optimization of massively parallel algorithms.

Human engineered systems are modular and reusable. Evolution is promising to generate competently elaborate systems. Furthermore, you can think of an ecosystem as an intelligence, which is gaining experience, generalizing and specializing.

Yet we are faced with the problem of generating diversity and optimizing the search for symbiosis.

As our evolutionary system will not be merely a simulation of life, we are faced with the selection of proper building blocks (this tends to be a never ending quest). During the symbiosis of the mitochondria and the host cell, the DNA had already developed an elaborate machinery. Similarly, if we miss some of the tools, we can wait for the system to get elaborate enough gaining expertise for the next million years. Nevertheless, we do not know yet if such a system can give results in a feasible duration.

I personally prefer to base an evolutionary system on a pure functional language. Functional languages are so elegant that:

Currently, genetic programming, genetic algorithms, artificial life is massively making use of random number generators. Unfortunately, to generate every single random number, I am using up the 5 million transistors in my computer for a considerable fraction of a second. However sometimes nature seems to use, instead of random numbers, chaotic series that emerge as a naive property of dimensions at which you are faced with quantum effects. I hope that someday we will be able to use tiny molecules, atoms or properties of light to generate flash speed chaotic series instead of expensive random number generators. Thus, a hardware optimized for evolutionary systems can be beyond our imagination in speed and efficiency. Think of the seeming adaptation power and intelligence of ecosystems coupled with such speed. In "2001 Space Odyssey" Arthur C. Clark imagined the self conscious computer HAL covering the walls of the control room of the shape ship Discovery with huge modules. I thing HAL will be a pocket computer.

2.2 Hierarchical Life Units (Symbiotic Hierarchical Evolution)

Evolution has progressed from simple proteins up to human societies. Simple cells have become complex cells with autonomous internal elements. Cells have formed animal and plant bodies. Animals have formed societies. Ecological structures have emerged.

There are simple steps leading into cooperation and hierarchy formation [1].

Stage I. Independent units compete for maximum fitness. Without regard to their elaboration, this is what state of the art genetic programs and algorithms seem to do.

Stage III. Some competitors begin to cooperate. This is never accomplished in genetic algorithms

Stage IV. Cooperation continues inside a border to protect resources from parasites.

Stage V. The higher hierarchical units continue to evolve. We are back to a usual genetic algorithm.

This process repeats itself into higher hierarchies whenever it as enough resources. Real life indicates that whenever resources are scarce, competition is beneficial. What is striking in life is the evolution of reusable and modular lower level units. Life uses the same components again and again in different designs.

2.3 Mitochondria

The symbiotic relationship between the cells forming our body and their mitochondria is the first example of the process described above. As proven by Lynn Margulis (then at Boston University) in 1967, mitochondria of eukaryotic cell today were independent cells (Stage I). Bodies of all living things are build of eukaryotic cells. They all include mitochondria.

The mitochondrion processes O2 and the host cell process the output of the mitochondria (ATP). Moreover O2 is poisonous for the host cell! This is very usual; at the beginning of life, there were no O2 in the air. Procaryotic cells (cells without nucleus) were then producing O2 as an output. Thus they set the necessary conditions for the evolution of mitochondria.

By then, the first eukaryotic cells (cells with nucleus) had formed. They needed the symbiosis of the mitochondria (State III) not to die of O2.

Those bigger eukaryotic cells had the necessary genetic material to devour and gain the genetic material of the mitochondria. Thus they increased their fitness, by guaranteeing the sole use of their mitochondria (Stage IV). They avoided parasitic relationships.

2.4 Complexity of Eukaryotic Cells

Eukaryotic Cell FormationAs I said, eukaryotic cells had the necessary genetic material to devour and gain the genetic material of other Procaryotic cells. And they did use this power. Christian De Duve [2] proved that all the inner structures of current eukaryotic cells are thus gained. It seems that increasing complexity in nature is always generated by the same simple rules. Yet we are not to tackle the problems later complexity stages -- embriogenesis and tissue differentiation, societies and ecosystems. The evolution of eukaryotic cells seems to be a good candidate for modeling evolution of reusable units and modular structures in a computer. Remember that when humans engineer, they thinker and reuse old modules and attack the problem in hierarchic parts.

2.5 Comparison of Hierarchical Genetic Algorithms

The stages described above end up with an increase in DNA length. The more complex a cell, the more information the DNA stores. However, there is another method of increasing DNA length: Just increase the length of it as needed without introducing new functionality. Do not limit its size. Evolving LISP programs generated the hierarchical genetic algorithms of Koza [3] is good example of increasing DNA length. Complicated and lengthy LISP expressions evolve successfully. Similarly, biological cells sometimes increase their DNA length randomly by copying and appending its portions. Initially the DNA is functionally equivalent but has prospects for extra complication due to extra bits in the DNA. However autonomous evolution of lower level units and reuse of units for different fitness functions is not possible in this biologically cheaper strategy. Yet symbiotic hierarchic evolution (Stages I-V) seems to allow reusability and autonomy of lower level units.

2.6 Making most of parallel computing

Thinking again the example of mitochondria, note evolving eukaryotic cells are not simple constant data. They are processing their environment -- the chemicals, the food around them. Thus hierarchical symbiotic evolution does not seem to be good for the evolution static data. Rather we have an intelligent ecosystem gaining expertise, making generalizations.

Thus computer counterpart of cells can be programs (functional, logic or imperative). The food can be data. Of course, data can be functions or predicates. This feature is well exploited in functional or logic programming languages. (Think of an evolving computer language translator. The food is the source language, the cells are translator programs written even in the source language?)

Functional and logic programs are natural candidates for parallel computing. So are the genetic systems. Hence, the hierarchical evolution system itself and its products can make use of parallel computing well.

2.7 Hierarchic Fitness

Yet there are challenging problems to solve. We can think that the genetic algorithm can be independent of the hierarchical evolution system. So the genetic algorithm used is not the main concern (however, as it's better, we will get quicker results).

What is the fitness function of the lower level units? Similar to genetic systems, we will present an ultimate fitness function to the whole system (Or set of fitness functions, to see the working of reusabilty. Opposed to current genetic systems this system must have the ability to diversify and develop genetic incompatibility among sub populations. Thus such a system has the ability to strive for a set of different fitness functions). In object oriented programming, the number of projects a class is used indicates its maturity. Similarly, the demand for their products can be the fitness criteria of lower level units. (Here we get more into artificial life as in real evolution there is no well defined fitness or requirements or destiny of living creatures. Yet the evolution produces elaborated machinery.)

The challenge is

2.8 The Diversity Problem

Remembering stages I-V, prerequisite of symbiosis is diversity. First of all genetically incompatible populations must emerge to diversify and they must meet in the same place to develop symbiosis.

This is a paradox of biology:

In [4], Terborgh argues the diversity in ecosystem of tropical forests:

Yet in a computer based evolution, we have to solve that very paradox.

3 Scope

This study involves the application of current model of self-organization in biology and cybernetics to an artificial life environment. To induce steps III-IV, a hierarchical fitness scheme will be applied so that instead of solving a human-induced problem, being useful to another one increases fitness. We will model the evolution of eukaryots from prokaryotes through the use of hierarchical fitness schemes.

The objective is to set off a digital analog to the Cambrian explosion of diversity, in which multi-cellular digital organisms (parallel MIMD processes) will spontaneously increase in diversity and complexity. If possible, we will try to support and breed the programs useful for us.

4 Methodology

The environment will be an inter-connected region of cyberspace that will be inoculated with digital organisms that will be allowed to evolve freely through natural selection.

Although the nature has developed its tools before the Cambrian explosion, we will try to introduce the necessary tools ready made at this stage. Tools such as reproduction strategies, genetic search algorithms will be encapsulated as objects so that later advances in genetic programming can be easily adopted in the project. Moreover our main focus is not genetic search itself but evolution of complexity and self-organization through hierarchical fitness evaluation.

We will take the following steps towards validating or revising the current model:

  1. Select the language used. The computer language used should be modular, multi-threaded (parallelism), and networkable. Currently Java is the cheapest and most easily accessible one that fits the definition. Later, we can devise an evolving population distributed on the network using Java.
  2. Define the implementation of the environment. Some parts of the environment are subject to change: The means of introducing problems to solve to the environment, underlying genetic algorithms, definition of hierarchical fitness. To cope with changes, we should rely on an object oriented model. We provide the elasticity to make the environment a broadminded test-bed. Otherwise, the modeling of hierarchical fitness is the main concern. We will keep the other parts simple and sufficient. Adaptation of a specific genetic algorithm should only consider efficiency of the implementation.
  3. Define the probes for measurement, for example, family trees, layout of interaction between life units, reusability, complexity, fitness.
  4. Define the most simple set of problems to solve yet allow for reuse and organization. Here computational resource at hand severely limits the experiments whereas according to the current model the resources must be abundant for organization to occur.

5 References

[1] P. Schuster; How does Complexity Arise in Evolution, via Internet

[2] C. De Duv; The Birth of Complex Cells; Scientific American; April 1996

[3] J. Koza; Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems; Report No. STAN-CS-90-1914; June 1990; Stanford University

[4] J. Terborgh; Diversity and the Tropical Rain Forest; Scientific American Library; 1992; ISSN 140-3213-5026-0

This page hosted by GeoCities. Get your own Free Home Page

Go to the Research Triangle Home Page.