next up previous contents index
Next: Realization of a Multicellular Up: The Multicellular Program Previous: The Multicellular Program   Contents   Index

Subsections

The Object-Oriented Ontogenetic Programming Paradigm

We want the computer to be our tool for breeding programs that control the behaviour and communication of many autonomous units which work together for solving problems that could not be solved by single units or with a centralized system. In this chapter, a new communication and control paradigm will be introduced, that seems to have the power for enabling very complex cooperative interactions of elaborate autonomous units but still is suited for automatic evolution of the unit control programs. This paradigm is called Object-Oriented Ontogenetic Programming (OOOP), because on the one hand it uses object-oriented programming techniques but on the other hand it expands these techniques with a form of communication and cooperation between the objects that is inspired by the interactions between cells in natural ontogeny (i.e. growth and differentiation processes in multicellular creatures). Before we will see how OOOP actually works and what are its pros and cons, we will take a short look at the evolution of its basic ideas.


How and why did the idea for the new paradigm evolve?

In the beginning, there was a lecture about genetic programming and a seminar about artificial life held by Wolfgang Banzhaf. I studied his great book [Banzhaf et al., 1998] and wrote a paper about the works of Peter Eggenberger on artificial embryology [Schmutter, 2000a]. Before, I had learned about gene regulation in genetics lectures for my subsidiary subject medicine. In the works of Peter Eggenberger, I read about how he simulated that mechanism on the computer. But I asked myself, why this was not used for problem solving. It looked as if it was a very powerful idea. In the lecture about GP, I got the idea to improve the existing modularization techniques for genetic programming. Then I thought about doing this by combining ontogeny like the one modeled by Peter Eggenberger with GA and GP for developing programs out of DNA-like representations with ontogenetic growth processes instead of a simple genotype-phenotype mapping. I thought that this would perhaps enable using tricks from nature like homology for improving crossover performance and that it might enable the evolution of more complex programs in general. I also thought that it would perhaps make the schema theorem1 apply for this approach to GP because it would be possible to develop a variable length program out of a fixed length representation.

My first idea was that the cells could grow in one dimension only and then develop into different parts of the program by gene regulation. The one-dimensionality would naturally induce an order of execution. But then, I had the idea that an object-oriented approach would be much smarter. The cells would be objects that could grow in a three-dimensional space and build much more sophisticated interactions. I named this "Object-oriented Genetic Program Development". Unfortunately, I then confused the objects with genes and planned to use as representation a set of arrays each of which corresponded to a gene and described one class. I thought that it would be a good idea to use these classes as predefined building blocks and let crossover only mix classes and mutation only vary the code in theses classes. When I thought about what I would do with the resulting objects, I noticed that I had confused something and started a new definition.

Now, objects were cells again and there was only one class for all the interacting objects. The genes were represented through member functions of the class. The activation of a gene corresponded to the call to a member function. This was an interesting new way of modularizing programs: There were modules that described different functions (the genes), but there also was a different level of modularization where all the modules consisted of the same program code (the cells). But as in the natural example, their function was not homogeneous because of different called functions depending on different concentration of messages at their location in the three-dimensional space. Also, the objects were able to have different internal states like different concentrations needed for activation of genes or temporal memory used by the evolved code. This definition was already the birth of OOOP, even though I did not yet see the really interesting field of applications that opened up. Those ideas evolved much later when I read about amorphous computing [Abelson et al., 1999]. The application to mobile entities even did not come to my mind until I read about the work of David Evans [Evans, 2000]. And that was after I had already finished implementing the Object-Oriented Ontogenetic Programming System (OOOPS) described in section 3.2. Now I have already introduced some key features of OOOP, but how does it really work?


How does it work?

Object-Oriented Programming is a great way of structuring programs and it has many other strengths, too. This is the reason why most computer programming of complex systems now is done with the object-oriented approach and most of the recent programming languages (e.g. C++, Java, Visual Basic) are object-oriented languages. In these languages, objects are units with internal functions and memory2 of which some functions can be called from other objects or from the main program and usually build the only interface to the object's abilities and internal state. The structure of these objects is based on templates called classes. It is only possible to create an object by instantiating it from a class, but from one class you can instantiate as many equal objects as you want. The functions defined in a class can only be used and the variables can only store something in an object of the class. So the object is the working unit and the class is the information base that defines the structure and the possible functions of the working unit. This is the same relationship as that between the genome and the cell in nature. The genome is the informational basis but cannot execute any function itself. On the basis of its information has to be constructed a cell that then is the working unit.


Table 2.1: Some analogies between nature and OOOP.
Nature OOOP
Genome = Description of all possible cell functions Class = Description of all possible object functions
Gene = Description of one cell function Member function = Description of one object function
Cell = Instance of working unit described by genome Object = Instance of working unit described by class
Individual = Multiple cells with same genome, interacting by proteins Program = Multiple objects of same class, interacting by messages
Cells behave differently depending on active genes Objects behave differently depending on executed functions
A gene is activated if the concentration of proteins at the cell's position meets the requirements A function is executed if the concentration of messages at the object's position meets the requirements


To extend the analogy, the whole program should be made of many objects which are all instantiations of the same class like the body of an individual creature is made of many cells that all contain (and base on) the same genome. This already is a big difference to traditional object-oriented programming because normally the objects take on different functions in the program by being based on different classes. But as in nature, the objects in the multicellular program, which are all instantiations of the same "genome" class, can also take over different roles in the program by activating different "gene" functions. As a class contains several member functions which hold the executable code, these are great counterparts to the genes. A member function is activated (which means that it is executed) if its activation conditions are met. As we have seen in section 1.2.3, the activation of genes depends on the concentration of proteins at the cell's position. In analogy to that, the execution of a member function in OOOP depends on the concentration of messages at the object's position. The big advantage of this approach to classical object-oriented design is that all objects can adaptively change their roles while interacting and a very complex cooperation of the objects can emerge or grow automatically without having to be planned beforehand. Only the genome (that is: the class) has to provide all the possibilities and preconditions so that the useful cooperation can arise3.

There are three important preconditions, that distinguish OOOP decisively from traditional object-oriented programming: Firstly, there is a topology which means that the objects have specified locations in a virtual space4 (which does not have to be three-dimensional), secondly, all the objects are instantiations of the the same class which contains all possible functions, and thirdly, the interaction between the objects does not rely on calls to specific functions but on the production of "broadcast" messages that diffuse into the space and fade with growing distance to the producing object. As in nature, the behaviour of an object depends on the concentrations of messages at its location. It seems to be a good idea to design an Object-Oriented Ontogenetic Programming Language (OOOPL) that offers these mechanisms directly5, but this was not the goal of the here presented research. Instead, the mechanisms were modeled using the possibilities of current object-oriented languages.


Advantages

Though we have already seen some advantages of the object-oriented ontogenetic programming approach, we will look at them and several others in more detail now. It really has to be stressed what a great problem solving ability the use of gene regulation in computer science can provide. OOOP is a natural and promising way to use these opportunities. Table 2.2 lists several benefits of object-oriented ontogenetic programming. These benefits will be explained in the following.


Table 2.2: Advantages of object-oriented ontogenetic programming.
Advantages of OOOP
Robust and fault tolerant
Adaptive and dynamic
Modular
Powerful interactions / communication
Evolvable
Emergent differentiation
Combines advantages of homogeneous and heterogeneous teams
For centralized and distributed problem solving
Close to nature
Open and easily extendable


Robust and fault tolerant

The interactions in a gene regulation network have a strong implicit robustness as well against disturbances in the communication path as against faults or breakdown of individual acting members. In his work about the dynamics of gene expression [Reil, 1999] Torsten Reil finds:

Furthermore, the experiments suggest that a high degree of robustness is possible without selection. This is manifested in two ways: a) transient disturbances of gene expression (carried out manually in the model) do in the majority of cases not result in altered expression patterns, and b) loss of gene function (achieved by manually knocking out genes) does in most cases not affect the overall pattern of gene expression ...Traditionally, such robustness is thought to have arisen from evolution [Gilbert, 1994]; it was shown here that this need not be the case.
More generally, Cefn Hoile and Richard Tateson compare the interactions between cells in a multicellular creature with traditionally designed artificial systems [Hoile and Tateson, 2000]:

Multi-cellular organisms have a number of features which are desirable in artificial systems. They can adapt to changing circumstances, through learning or evolution. "Faults" arising from internal errors or injury can often be rectified. Irredeemable faults are seldom the cause of catastrophic failure because the redundancy of the system allows most or all functions to continue.

This contrasts markedly with most current artificial systems. Here the human designer takes on the burden of solving all these problems. The designer must gather a large amount of information about the operating conditions and specification of the system to be designed. Having described the problem, the designer must provide an explicit, practical and comprehensible solution.

This design process usually results in a system which only operates under previously anticipated conditions, and which employs a centralized, hierarchical, non-redundant control system. Such control systems are applauded as transparent and efficient. However, many solutions are unavailable to human designers not because they are poor solutions in terms of performance in the system of interest but merely because they are not comprehensible by humans.
These are already good reasons for trying to use the organizational principles of natural cell clusters for artificial systems. Hoile and Tateson also mentioned already a second (more general) advantage of OOOP: a great power of adaptation.

Adaptive and dynamic

The ability of systems designed with object-oriented ontogenetic programming to adapt to dynamic environments and changing problems is one of the main features that this new paradigm promises to provide. All practically usable approaches to introducing development into automatic systems design (especially evolutionary computation) until now have focused on an extension of the genotype-phenotype mapping. They enrich this mapping by introducing developmental principles from nature or at least more complex mapping functions6. But the organizational strengths of ontogenetic processes are only used for developing a "mature" solution before using it. They do not remain in the final developed system. So the solutions produced by these approaches do not have the adaptive qualities of multicellularity. In contrast, the processes providing these qualities are an essential part of the solutions that base on OOOP. Previous developmental approaches do not provide a real analogy to nature because in nature there is no "mature" solution (creature) which does not depend on ontogenetic processes any more. If the varied representation of an evolutionary algorithm is the genotype (the genome) and the executed solution is the phenotype (the living creature) this means that "usage of a solution" in nature denotes the life of a creature. But ontogenetic (and embryonic) development in nature happens within the lifespan of a create and not before the beginning of its being7. There is one work that recognizes this difference and introduces many exciting ideas for automatic programming. This work has also had some influence on the choice of name for OOOP8, even though the used processes are very different9. It has been invented by Lee Spector and Kilian Stoffel in 1996 [Spector and Stoffel, 1996] and in my opinion deserves much more attention than it apparently has received. The important similarity between ontogenetic programming and OOOP is that in both cases the ontogenetic development is a constituting property of the produced solution. This attribute is in my opinion the heart of "ontogenetic" programming. Ontogenetic programs have a dynamic execution structure which interacts with the environment and allows growth and adaptation. Lee Spector and Kilian Stoffel describe this important difference to other developmental approaches as follows:

These sorts of morphological mechanisms ...are simplifications of biological ontogeny ...they operate only prior to runtime; in contrast, biological ontogeny continues throughout the life span of an individual.
About the use of the real ontogeny for computer programs, they write:

...generally, developmental control of an arbitrary feature f of an individual is likely to be useful in two cases: 1) when there is an adaptive advantage to having an f value at maturity that differs significantly from the f values of new individuals, or 2) when there is an adaptive advantage to having different f values at different stages of an individual's life. The second case applies to features of computer programs for many domains.

Modular

Object-oriented ontogenetic programming is also a new modularization technique. Even if you do not want to create a system of autonomous interacting units, OOOP might enhance the power of GP in finding good building blocks for reuse in the created program and provide a new way of enabling the evolution of more complex programs. There exist already several modularization techniques in genetic programming that try to reach this goal. Automatically defined functions and automatically defined macros have already been mentioned. Justinian P. Rosca and Dana H. Ballard describe a different technique for discovering reusable subroutines in [Rosca and Ballard, 1994]. All these recent modularization techniques have enhanced the power of GP, but they also have different limitations and problems. In a later paper about an extension of the ontogenetic programming idea [Spector, 2001] Lee Spector writes:

The more traditional approaches to the evolution of programs with subroutines (automatically defined functions ...) and macros (automatically defined macros ...) require that one specify in advance how many such modules are to be used and how many arguments they will receive. Syntax restrictions are also imposed by the definitions of the modules, complicating the expression of genetic operators and in some cases limiting the possibilities of crossover. A more refined approach using architecture altering operations eliminates the need for prespecification of the numbers of modules and arguments, but it does so at the expense of additional complexity [Koza et al., 1999].
OOOP does not have these problems, because the modules do not have to be prespecified (genes can be added to or removed from a genome without any problems, which in fact happens all the time) and the approach is very easy to understand and use if one knows the object-oriented programming concepts. The only "complexity" that the approach implies is that not all code of an individual is evolvable code. You have to use string search operators to find the appropriate positions for varying the program code. The power of using OOOP for modularization has not yet been tested, but as nature successfully uses a similar approach, it is probable that object-oriented ontogenetic programming will also enhance the modularization capabilities of GP. Easy and flexible exchange of evolved modules between individuals is surely provided by the approach. One more step towards the goal of fast emergence of good building blocks is the introduction of a second level of evolution by also computing fitness values for single genes, not only for whole individuals and favouring fitter genes for conjugation. This will be described in more detail in sections 3.2.1 and 3.2.2.

Powerful interactions / communication

The gene regulation mechanism and diffusion of messages provide a basis for very complex interactions and interdependencies. We have seen already in section 1.2.3 that these mechanisms enable the elaborate interactions between cells and between genes in one cell. Torsten Reil shows in [Reil, 1999] that already the gene regulation in one cell can produce extremely complex interactions. Even though the messages in OOOP are very simple (the only information they contain is a message type and the intensity of the message), they suffice for creating an extremely powerful communication. In a multiagent environment many problems can only be solved by heavily communicating units. Also for modularization of a single problem solving program, a powerful communication between the subcomponents is often necessary. As Mitchell A. Potter and Kenneth A. De Jong put it in [Potter and De Jong, 2000]:

...many problems can only be decomposed into subcomponents exhibiting complex interdependencies.
But a sophisticated communication usually makes high demands both on development and on (transmission-) hardware. This is not the case for the OOOP communication paradigm10. You do not have to develop a complex communication protocol or a specific information exchange language and you do not need a very strong transmission hardware, because the messages are so simple that they can perhaps even get coded in analog attributes of the transmitted medium (e.g. wavelength and amplitude for immobile11 units communicating via radio). The presented paradigm therefore is a promising approach to communication in environments with autonomous interacting units or for creating solutions with a modular program architecture.


Evolvable

Potter and De Jong also write in [Potter and De Jong, 2000]:

To successfully apply evolutionary algorithms to the solution of increasingly complex problems, we must develop effective techniques for evolving solutions in the form of interacting coadapted subcomponents. One of the major difficulties is finding computational extensions to our current evolutionary paradigms that will enable such subcomponents to "emerge" rather than being hand designed.
Evolutionary computation gets most of its inspirations from biology. So we should have a look at what made cooperation evolve in nature. In other words: How has evolution built cooperative organizations out of self-interested components? John Stewart gives in [Stewart, 2000] a general answer to this question:

A mechanism that ensures individuals capture all the effects of their actions would completely overcome the barrier to the evolution of cooperation. If individuals capture the effects of their actions on others, self-interest would no longer stop an individual from helping another. Helping the other would be as profitable to the individual as helping itself.
In nature, this condition is very often ensured by depriving the individuals of their capability to reproduce individually. Such individuals have a clear evolutionary advantage if they cooperate because that makes the reproducing compound fitter. This makes organelles like Mitochondria, which once seem to have been separate organisms [Margulis, 1981], cooperate in a single cell. It makes the cells in a multicellular creature cooperate. And it makes bees, ants and termites cooperate. John Maynard Smith and Eörs Szathmáry write in [Maynard Smith and Szathmáry, 1995]:

To the extent that individual ants, bees or termites have lost the capacity to reproduce, they can propagate their genes only by ensuring the success of the colony, just as somatic cells can propagate theirs only by ensuring the success of the organism. Hence, the colony can be expected to have features adapted to ensure its success, and it is reasonable to apply concepts of optimization to it, rather than to the individual ...
This concept is also used for allowing the evolution of cooperation with object-oriented ontogenetic programming. The OOOP units (the objects) can only reproduce together (as they are all based on the same genome which is used for reproduction) and they are not assigned separate fitness values. Their fitness is determined by the fitness of the team. If you consider genes as the units this also holds even though they have separate fitness values in OOOPS and can migrate to other genomes. One reason for this is that their fitness is based on the fitness values of the genomes that contain them. This will be described in more detail in section 3.2. Hassan Masum and Franz Oppacher also saw that gene regulation is a great method for evolving cooperative units12. They write in [Masum and Oppacher, 2001]:

With embryogenetic mechanisms, regulatory networks ...provide a simple distributed coordination method - the same overall program is being run in different ways, and since only one program is evolving, it will implicitly evolve to perform well when instantiated in multiple cooperating cells.
Masum and Oppacher also make another important point here: Even though the resulting problem solution consists of many different units (concerning their actions), the evolutionary computation system only has to handle one single genome. This allows the evolution of heterogeneous teams13.

Perhaps, the flexibility and adaptivity of gene regulation as a coordination method can even compensate to some extent the ruggedness of the GP fitness landscape by choosing which genes to use. This influence can perhaps be supported by making the gene fitness also depend on how often or whether the gene has been used. These issues are interesting questions for further research.

As we will see in section 3.2, the object-oriented ontogenetic programming system even allows meta-evolution like evolving the type of cell update (e.g. fixed order, random order or random update) or the environment model.

Emergent differentiation

Differentiation of cells can be seen as emergent division of labour for the good of the creature. In terms of computational problem solving, this means that the interactions between cells that are used in OOOP can produce emergent problem decomposition and task assignment. John Maynard Smith and Eörs Szathmáry write in [Maynard Smith and Szathmáry, 1995] about cell differentiation in nature:

The development of a multicellular organism, with differentiated cells, requires that three problems be solved:

Gene regulation ...

Cell heredity, and the dual inheritance system. Not only are different genes switched on in different cells, but the states of differentiation are heritable through cell division ...

Spacial patterns. Differentiated cells are arranged in space in a specific and repeatable pattern. How does this come about? There are two possibilities, which we will call 'self-organization' and 'external specification'.
All these preconditions are given in OOOP. As we know, gene regulation is the basis of object-oriented ontogenetic programming. We also know that an important feature of OOOP is the virtual space in which the cells are located and in which they build spacial patterns. Both possibilities for their formation exist in OOOP: self-organization14 is allowed by a random influence on cell growth. When a cell divides, the newly created cell takes a random free position around the original cell. External specification is given by special message sources, that can be arbitrarily located in the environment. This is also already implemented in OOOPS. Also the second precondition for cell differentiation is realized in OOOP. Because of its object-oriented approach to modelling cells, the internal state of a cell is naturally heritable through cell division by just copying the cell object.

Combines advantages of homogeneous and heterogeneous teams

Sean Luke and Lee Spector try in [Luke and Spector, 1996] to evolve coordination in teams of interacting agents and describe the following two approaches:

In one commonly used scheme, teams consist of clones of single individuals; these individuals breed in the normal way and are cloned to form teams during fitness evaluation. In contrast, teams could also consist of distinct individuals ...
...heterogeneous tasks can only be solved (or solved easily or effectively) with multiple individuals each of which uses a distinct specialized algorithm.
With object-oriented ontogenetic programming, this contrast does not exist any more. It combines the benefits of both approaches: It can easily be handled with the usual breeding strategies because as there is only one genome, all the agents are homogeneous concerning variation (i.e. in genotype). But in the evaluated program, the agents (i.e. the objects) differentiate to perform specialized actions which makes them heterogeneous concerning execution (i.e. in phenotype). So the ontogenetic processes used in OOOP allow to combine the easy evolution of homogeneous teams with the problem solving power of heterogeneous teams.


For centralized and distributed problem solving

As we have seen in section 2.1.1, object-oriented ontogenetic programming started as a method for evolving a new sort of modular programs. This new type of modularization was meant to enhance the power of GP in finding good building blocks and it provided a new type of communication between the modules that allowed extremely complex interaction networks and promises good adaptive qualities for the evolved programs. The spacial locations of the objects were only a way to introduce even more possibilities for adaptation and interaction, they did not have any meaning. Therefore it seemed to be sufficient to let the objects take only positions in a regular grid and let them stay there until they die. In this approach, the virtual space is only a tool for making the communication between the modules even more powerful and the programs even more adaptive15 compared to using only the genes of a single cell as modules. It does not model any real space. And the problem environment is not modeled in this space. The space it located in the problem solving program which is located in the environment. This is totally different for the second approach, which evolved much later but seems to be even more interesting: The ideas of OOOP can be extended to evolve control programs for separate cooperating units which interact in an environment on the basis of the OOOP communication paradigm. In this approach, the environment is modeled in the virtual space and the location of the objects in the space corresponds to their location in the real environment. For modelling mobile robots in the real world, the locations of the objects would for example be extended to take arbitrary values and the objects would be enabled to change their position. Because in this approach the environment is in the same space as the objects, the communication between them is directly influenced by the environment. The intensity of messages at an object's position is computed on the basis of the environment model. There is no need for special message sources that give information from the environment into the object space. Moreover, the problem solution is very different to the one of the centralized approach: It is (usually) not the whole evolved program including the virtual space and the functions for ensuring the diffusion of messages in this space, but the problem solution is simply the genome which controls the actions and communication of the objects in the space. In this approach, the space is no more a tool for communicating but a simulation of the real communication medium. This method for evolving control programs for multiagent teams (which I named "Swarm-Programming") will be described in more detail in section 4.2.

Both approaches to using ontogenetic processes for problem solving have their pros and cons, but they both open up new possibilities for evolving intelligent systems. Both approaches should be investigated much further because they seem to have a lot of power and many common advantages compared to traditional approaches to genetic programming. Most advantages discussed in this section apply both to the centralized and the distributed approach to ontogenetic problem solving.

Close to nature

As you have seen, OOOP is quite close to the natural example of growing cell clusters. This is not only an advantage because the great abilities of cell clusters give a hint about the power of this approach also for solving other problems, but this also means that OOOP could be used as a simulation of natural processes. In section 1.5.1, we saw that there have been already several works on simulating the processes used in OOOP, but nevertheless, this object-oriented approach introduces some new possibilities and is very open for extensions, which makes it a good tool for modelling gene interaction networks. More importantly and in contrast to some other approaches, OOOP also provides a good basis for simulating multicellular interactions and growth processes.

Open and easily extendable

One of the major advantages of OOOP both for simulation and for problem solving is that it is not based on a strict mathematical model like most other simulations but on an object-oriented program which can easily be extended to arbitrary levels of detail or to include any interesting new feature. This openness is the last of the here presented advantages of the object-oriented ontogenetic programming paradigm, but that does not mean that it is the least important. Perhaps, it is even one of the most important features of OOOP, because the effect is that you can make out of the OOOP idea what you like and what suits your special needs and interests. This is not to say that good OOOP programs can easily be written. Because of the complex interactions, the genetic parameters like genetic code, activation conditions and message production can not be hand-coded to produce a desired behaviour (except for extremely simple examples). Therefore, these parameters are optimized with evolutionary methods in the Object-Oriented Ontogenetic Programming System described in chapter 3. But as this system and the meta structure of the OOOP program (describing for example the diffusion model or the gene regulation mechanism) are written in the traditional way, these parts (that implement the OOOP model and the breeding mechanisms) can easily be adjusted or extended by hand. There is hardly any feature that cannot be added by simply changing or adding some code at easily locatable parts of the system. This openness and the facility of performing changes are well known advantages of object-oriented programming.

There are many examples of extensions that could easily be introduced and could be important for specific simulation or problem solving goals. Here are some suggestions:


Pitfalls

There are three main problems that come with the OOOP approach. Table 2.3 summarizes these problems which will be discussed in the following.


Table 2.3: Pitfalls of object-oriented ontogenetic programming.
Pitfalls of OOOP
Slow evolution
Slow execution for big cell clusters
Difficult to analyse


Slow evolution

OOOP has the great advantage that it can easily be handled with artificial evolutionary approaches like genetic programming. But it also has some attributes that make the genetic programming runs for its evolution quite slow:

It has to be said, that there is another important approach to tackling the problem of slow evolution. Genetic programming is an optimization technique which can easily be executed in parallel. Because of the foreseeable time problem with OOOP, the object-oriented ontogenetic programming system has been designed so that the population of OOOP individuals can be distributed on many computers. It has also been optimized for creating as little net traffic as possible. Additional individuals and computers can always be added during an evolutionary run. There are many more interesting features of this system, but this is not the right place to list them all. They will be described in sections 3.2.1 and 3.2.2.

Of course, you could also wait for faster computers. This will make OOOP more and more interesting. But faster computers cannot solve the next discussed problem.

Slow execution for big cell clusters

The diffusion of messages in OOOP is very different to that used in cellular automata and many other approaches. It is not based on a definite regular grid (sometimes called reaction-diffusion matrix) where the concentrations at each gridpoint are regularly updated and only depend on the concentrations of the adjacent points. OOOP does not need any regular grid because only the concentrations at the cell positions are computed based on the message sources, their distance and possible influences of the environment modeled in the space. This allows the units to be at arbitrary locations in an unlimited space, it allows to model the influence of environmental local factors on diffusion, and it makes several more extensions possible which have been mentioned in the last section. This is much faster than the matrix approach if there are few acting units irregularly placed in a big space. But if the naive approach for determining the concentrations at a specific location is used, which consists of scanning all message sources and adding their influences on the message concentrations at the current location, this approach leads to a quadratic dependence of execution time on the number of cells or (more general) units. For every cell, all cells have to be scanned for computing the influence of their message production on the actual cell. This results in quite slow execution of OOOP programs with a big number of interacting units, especially if environmental influences on the diffusion have also to be taken into account.

Of course this naive approach to computing the concentration is not the last word spoken on this issue. There are surely many possibilities for speeding up the interactions between cells. For example, cells which are out of reach in any case could be skipped. Finding efficient algorithms for determining the concentration of messages in arbitrary locations of a space with many message sources is a very important step for improving the power of OOOP.

Fortunately, current computers are already quite fast, so that even with the naive algorithm OOOPS already produces good results. Moreover, if OOOP is used for evolving control programs for teams of agents in a real environment, the here discussed influences on execution time do not remain in the final solution. In final usage, nature takes care of producing the right concentrations at the right locations. So in this case, the influence of the diffusion algorithm on execution time only matters for how long the evolution of good solutions will take. In contrast, if the solution consists of the whole program and the diffusion and virtual space are tools for enabling the complex interaction between program modules which are part of the solution, the influences of the diffusion algorithm remain in the final solution and are therefore of greater importance.

Difficult to analyse

Object-oriented ontogenetic programming is not based on a simple mathematical model but on an algorithmic approach that can easily be extended. It is difficult to analyse its dynamics on the one hand because there are many influences on them and on the other hand because these influences can easily change. The paradigm has been constructed with the goal to be powerful, open, easy to use and easy to extend. As it is a heuristic approach anyway who primarily has to work well--no matter how, the weight has not been put on making it easily analyzable. This is an attribute that OOOP shares with most other directions in programming, especially genetic programming. If object-oriented ontogenetic programming was designed to be easily analyzable, that would necessarily limit its other advantages.

Of course, the fact that OOOP is not based on a simple mathematical model does not mean that it makes no sense to analyse its behaviour. A closer look at the dynamics of OOOP programs can help a lot in getting good ideas for improving its performance. Perhaps even because it is not easily analyzable, there are a vast number of possible and interesting subjects for theoretical research.


next up previous contents index
Next: Realization of a Multicellular Up: The Multicellular Program Previous: The Multicellular Program   Contents   Index
 
© 2002 Peter Schmutter (http://www.schmutter.de)