Some Thoughts on Evolvability

Thomas S. Ray
ATR Human Information Processing Research Laboratories
2-2 Hikaridai, Seika-cho, Soraku-gun, Kyoto, 619-02, Japan
ray@hip.atr.co.jp, ray@santafe.edu, tray@ou.edu
June 17, 1999


This is a seed for a manuscript that I hope will eventually develop into something worth publishing on the subject of evolvability. However, at this point, I don't know enough about the subject to make a solid contribution. I am still a student of evolvability. Yet I intend to develop a research program in this area. Towards that end, I am currently (Summer 1999) conducting empirical studies of evolvability in the Tierra system at ATR in Japan. I am also co-organizing (with Paul Marrow, Mark Shackleton, and Jose-Luis Fernandez-Villacanas of British Telecom) a Workshop on Evolvability at the GECCO '99 conference, and co-organizing with Paul Marrow a "Working Group on Evolvability" at the Santa Fe Institute.

I have long been deeply concerned with the issue of "evolvability". In building artificial evolving systems, we find that some of these systems exhibit rich evolution, and others don't. When making modifications to systems that do exhibit rich evolution, we find that subtle changes may have a large impact on various properties of the evolutionary process.

I conducted a study comparing the patterns of evolution in four different (but very similar) machine languages: Ray, T. S. 1994. Evolution, complexity, entropy, and artificial reality. Physica D 75: 239-263. It was found that two of the four showed a much greater magnitude of evolution than the others (measured as optimization through size decrease). Also, the two that showed relatively little evolution, showed a pattern of strict gradualism of evolution, whereas the other two showed abrupt jumps in evolution (punctuations). Of the two showing punctuations, one demonstrated gradual evolution between the punctuations, while the other showed strict stasis between the punctuations.

It is evident that many aspects of the evolutionary process depend on the structure of the underlying genetic language. Yet, there exists no body of theory to guide in the design of enhanced evolvability in evolving systems. This now presents a serious problem for the many engineers who work with evolution as a tool in design or optimization.

In every case, the engineer creates a genetic system to describe the solution space, and then evolves that language. Some of these languages will be highly evolvable, while others will not. There is no theory to guide the design of these languages to enhance their evolvability. This represents a hole in our evolutionary theory which was not evident before the advent of synthetic evolution.

Conventional and Unconventional Evolvability

Factors influencing evolvability could be divided into two groups: conventional and unconventional. By conventional I mean the kinds of things that have been thoroughly analyzed in the field of population biology (population size, mutation rates, gene flow, sub-division of the population into demes, etc.). The field of genetic algorithms has also done a lot of work on these kind of factors, as they have searched for the best sets of conditions for finding the global optima (e.g., the relative value of cross-over as opposed to mutation).

By unconventional I mean things that are not variable in biology, but can be varied in the design of artificial systems, such as the structure of the genetic language, and its interactions with the genetic operators.

Because the fields of population genetics and genetic algorithms have already provided a good understanding of the influence of the conventional factors, I am personally more interested in understanding the influence of the unconventional factors.

Finally, I wonder if there are any general principles of evolvability, or can we only be guided by the analytical or empirical results of studies about each class of factor that might influence evolvability.

Beyond the Global Optimum

There has been a large amount of work in the GA/GP area on how to configure a system to most efficiently find the global optima. This work can be considered to inform us about evolvability.

However, there are evolvability issues that go beyond, or are in direct conflict with finding the global optima. Many evolving ALife systems strive to avoid becoming trapped in a global optima. Evolvability in these systems can mean creating conditions in which there is no global optima, but rather there exists a rich fitness landscape in which there are always more paths "uphill" from currently occupied regions of the genotype space.

This might seem an unrealistic goal at first glance, but it is probably possible to achieve. The GA/GP community strives to evolve an application whose optimal function is known in advance. The approach aims to have the entire population converge on a single optima. In contrast the ALife approach does not have a clear definition of the form of the target evolved system, but certainly aims for a divergent rather than a convergent population. The theory is that co-evolution between different "species" in a divergent population can continue to create new evolutionary pathways indefinetly, or at least for a long time. This seems to have been the case in organic evolution.

Another angle on this same issue is understanding (and being able to set up, or engineer) the conditions under which "major transitions" can occur. My own primitive thinking on this issue views the task as providing an evolving system with a set of tools, or elementary components, from which a higher hierarchical level of organization can be constructed.

At this point there are two approaches. The most popular is to stir the system and hope for the higher level of organization to emerge spontaneously from the elementary components. The less popular approach is to seed the system with a very primitive instance of the higher level of organization, constructed by hand from the elementary components.

This second approach is based on the idea that in major transitions (at least in organic evolution), the emergence of the first instance of the higher level of organization is really the starting point for a very rich evolutionary exploration of the diversity of forms that are possible at this new level. The richest (if not the most interesting) part of the evolution is the diversification of new forms at the new level of organization, rather that the emergence of the first individual at that level.

Using either of these two approaches to studying major transitions, we can only hope realistically to study a single transition at most. If the geologic record is any guide, major transitions in evolution (J. Maynard Smith and E. Szathmary, The Major Transitions in Evolution, Oxford: Freeman, 1995. Pp. 346) are rare, and are separated by vast spans of evolutinary time. It would be a great achievement if any artificial system could be engineered to exhibit such a transition. But it could not reasonably be expected to go on spontaneously to the transition to the next hierarchical level. That would involve at least an equally difficult re-engineering in preparation for the next transition. But much could be learned from experimental studies and observations of any evolving system in the midst of such a transition.