log of research progress 1999

Nov 7th
here's abstracts for a few papers I'm working on:

1 - (POTs) "Coevolutionary dynamics in a minimal substrate". There are many supposed benefits of coevolutionary techniques but researchers are becoming increasingly aware that coevolution can sometimes introduce as many problems as it solves. Speculation about the causes of failure are common but often the particulars of the application domain make these proposals impossible to verify. This paper uses a minimal substrate to study coevolutionary dynamics. Specifically, we simply evolve scalars, and vectors of scalars, playing simple number games using various coevolutionary set-ups. This substrate enables us to exemplify several coevolutionary phenomena that may be involved in the failure of coevolutionary experiments. In particular, we  elucidate the concept of non-transitive superiority and show how this is involved in several types of failure.

2 - (HIFF theory) "Analysis of Hierarchical Building Block Functions". Hierarchical building block functions can be analysed as a layer-wise separable function. We combine the analysis of a strict hill-climbing GA and an 'Idealised GA' to provide an upper-bound on time to converge on global optima. Whereas in previous analyses on separable functions a non-population based deterministic algorithm could outperform the GA using the same assumptions, these hierarchical functions exemplify the utility of poulation based recombinative algorithms."

3 - (Perverse Xover) "Combining schemata and Preserving Schemata in Recombination". All binary recombination operators have one feature in common: if both parents agree on an allele value then the offspring will take that value at that locus. Generally, the difference between recombination operators is in how they treat the allele values that disagree. For example, uniform xover is equivalent to random assignment of allele values to those loci where the parents disagree. And one-point xover takes genes from one parent up to a crossover point and from the other parent after the crossover point. Uniform xover thus merely preserves the similarity between parents, whereas one-point preserves similarity and combines remaining schemata. Our research has investigated these two roles of recombination. We show that for some problems preserving similarity is not sufficient for successful search and schemata combination is required. Moreover we introduce a somewhat counter intuitive recombination operator that does not preserve similarity but does provide combination and with this we show that schemata combination is sufficient and that preserving similarity is not required.

4 - (Symbiosis) "Nature is repleat with symbiotic organisms. Yet, in general, symbiosis is treated as a curio - worse, an aberration on the otherwise relentless path of mutually exclusive competition between species. Ultimately, it seems that symbiotic relationships, though they may come and go, are not part of the explanation for how complex individual organisms came to be. Here we illustrate one mechanism by which symbiosis may play an integral role in evolutionary innovation. We show how the formation of mutually benefitial groups can change the shape of the reward landscape in which individual species evolve such that the characteristics of a symbiont become induced into an organisms own genotype. Our simple model shows how the induction of symbiont characteristics is involved in an adaptive progression from independent organisms, to dependent mutualists, and finally to a complex independent organism with a simple dependent parasite."

5 - (Group HIFF) "Group evaluation as a method for schemata processing in GAs" One method by which to make schemata explicit is to utilise partially specified genotypes that each stand for a single schemata. This makes the combination of schemata in recombination more effective and enables recombination operators that are not sensitive to gene ordering. However, this method has two disadvantages; we need to be able to evaluate partially specified individuals and we have lost the implicit paralellism supposed to be important in the operation of a GA. This paper introduces the use of group evaluation to overcome these problems. Individuals are temporarily assembled into groups that together create a fully specified set of genes, this is evaluated, the fitness score is distributed to the group members and then the group is dispersed. In this way partial evaluation is not required and paralellism is regained. The method also has the advantage of 'priming' individuals for recombination; because they are co-adapted they are more likely to create successful offspring when they are joined permanently by a recombination event. The results show a considerable improvement over both the regular GA and the GA using partial individuals but no group evaluation.

5b - (Group HIFF version 2) "Utilising Symbiogenesis in EAs". In nature, the process of symbiogenesis - the origin of new species via the genetic integration of symbionts - is a fundemental source of adaptive innovation. Basically, the idea translates into taking two separate organisms of different species and joinging them together. This process seems somewhat unlikely - how could we expect to arbitrary organisms to join together and create something useful? However, it should be pointed out that the organisms involved in symbiogenesis are not arbitrary but are co-adapted in close symbiotic relationship. In this paper we investigate the use of a 'joining' recombination operator together with 'group evaluation'. The latter promotes co-adapted organisms and the former creates composites by joining them together. The process now continues creating groups of composities and joining them into meta-composities, and so on. We show the performance of this method on a multi-level building-block problem.

Oct 28th 99
Been a bit distracted I suppose: not achieved much recently, bit here, bit there.
Desperately need to do an overhaul on my GA code so that I can try out some experiments on HIFF, ICGA with deterministic crowding, and group evaluation.

July 28th 99
Many new and exciting things are underway :)
I've been to SFI summer school, CEC and GECCO in the last two months and got lots of ideas to try out.
The two most exciting are:
1) I have an example of symbiotic scaffolding in nature (cf Torsten Reil).
2) I have an off-the-shelf diversity maintenance method that works on HIFF - deterministic crowding
In addition,
3) I implemented a radical xover operator that has interesting theoretical properties - cf Sevan and Stephen Chen.

And there are many other ideas and potential pieces of joint work too. Not least:
- Martin Oates has been examining 'energy barriers' in the mutation rate of a GA on HIFF, and properties of HIFF in constrast to 'unstructred' problems wrt xover, mutation and population size.
- Joshua Knowles is examining the potential to use HIFF as a multi criteria optimisation test problem.
- Marc Ebner has proposed some work on dynamic fitness landscapes/ coevolutionary dynamics.

May 1999
ECAL accepted too! that's four out of five this year :)
No time for research recently - too busy getting camera readies ready.
The obvious next step is to bring together the work on decomposable problems [PPSN and CEC], with the EA modifications that use combination of partial solutions [GECCO], and the evaluation of groups [ECAL]. This will bring me closer to an integrated model of symbiogenesis. But first I have to find a way around the hacks in the GECCO experiments: group evaluation will get around partial evaluation/ competitive templates, but I still have the resource-based fitness-sharing, and the size-penalty fiddle-factor to prevent string growth. Maybe the latter will be relieved by group evaluation - if there are always enough neighbors to complete partially specified strings then there'll be no pressure to fill strings with garbage bits. Maybe not. Anyway, I still need to do some method of diversity maintenance that uses less domain knowledge than the resources.... stay tuned.

Mar1 1999
make that five :)

Feb 2 1999
Just did 4 papers for recent submission.
2 on Embodied Evolution
2 on HIFF
See publications