Coevolution, Memory and Balance

1 Introduction

In nature, organisms undergo selective pressures from other organisms - belonging to the same or to other species. Predator-prey interactions are a common example of selec­ tive pressure between organisms. These interactions are characterized by an inverse fitness interaction: success on one side is felt by the other side as failure to which must be responded in order to maintain one's chances of survival. This typically results in an arms race in which the com­ plexity of both predator and prey increases stepwise. It is a challenge to integrate this mechanism into an evolutionary algorithm in order to further improve its performance.

Pared is [ 1999] provides an overview of the use of co­ evolution for computational purposes starting from the early days of computing. Here, only work directly relevant to the issues of the current paper is discussed. Hillis [ 1992] co­ evolved networks for sorting lists of sixteen numbers. Such a sorting network consists of comparisons between two numbers (and the possibility of swapping both numbers). The goal was to find a network, which correctly sorts all possible lists of sixteen numbers, with as few comparisons as possible. Hillis used two populations. The first popula-

Coevolution, Memory and Balance

Jan Paredis

MATRIKS

Universiteit Maastricht P.O. Box 616, NL-6200 AL Maastricht The Netherlands e-mail: jan@riks.nl

tion consisted of sorting networks. The individuals in the second population were sets of test-lists. These lists contain numbers to be sorted. Both populations were geographically distributed over a grid with each location containing one set of test-lists and one sorting network. At each generation a sorting network was tested on the set of test-lists at the same location. The fitness of a sorting network was defined as the percentage of correctly sorted test-lists. The fitness of the set of test-lists, on the other hand, was equal to the per­ centage of test-lists incorrectly .sorted by the network. This is similar to the inverse fitness interaction between predator and prey.

Hillis has shown that - in comparison with traditional non-coevolutionary single population GAs - better sorting networks can be obtained. Inspired by this work, Paredis [1994a] introduced a Coevolutionary Genetic Algorithm (CGA) which uses a partial but continuous fitness evalua­ tion resulting from encounters between individuals belong­ ing to different species. The first CGA was used to train a Neural Network (NN) on a classification task. Next, an ab­ stract class of problems which can be solved by CGAs was defined: so-called test-solution problems [Paredis 1996]. This large class of problems in Artificial Intelligence and Computer Science in general, involves the search for a solu­ tion which satisfies a given set of tests.

A CGA uses two populations to solve test-solution problems. One contains the tests which a solution should satisfy. The other consists of potential solutions to the problem. CGAs have been applied to various other test-so­ lution problems, such as: constraint satisfaction [Paredis 1994b ], process control [Pared is, 1998], path planning [Pared is and Westra, 1997], and the evolution of cellular au­ tomata (CA) for density classification [Paredis, 1997]. The main purpose of the applications described above is to help us understand, explore, and illustrate the operation of CGAs. Recently, researchers have been using CGAs in real­ world applications such as object motion estimation from video images [Dixon et a/., 1997] and time tabling for an emergency service [Kragelund, 1997].

Some CGA applications used a test population whose contents remained fixed over time [Kragelund, 1997; Pared is, 1994a; 1994b]. In others, both populations fully evolved [Dixon et al., 1997; Paredis, 1997; 1998; Paredis and Westra, 1997]. In the latter case, there is pressure on both populations to improve, i.e. the solutions "try" to cor­ rectly satisfy as many individuals as possible in the test population. At the same time the tests "try" to make life hard for the solutions. It is not in their "interest" that the problem be solved. Especially if there is no solution satis­ fying all possible tests then the tests might keep the solu­ tions under constant attack. Even if there exists a solution satisfying all tests, it might be virtually unreachable given the coevolutionary dynamics. This might be caused by the high degree of epistasis in the linkages between both popu­ lations. Due to such linkages a small change to the individ­ uals in one population might require extensive changes in the other population. This was exactly what happened in the CA application [Pared is, 1997]: the tests were able to keep ahead of the solutions by "jumping" back and forth between two regions - in close proximity of each other - in the space of all tests. After each such jump of the test population, ex­ tensive changes to the "genes" of the solutions, i.e. CAs, were required in order to satisfy the tests. Paredis [ 1997] provides a simple diversity preserving scheme which pre­ vents the tests from keeping ahead of the solutions. In fact, it achieves this by randomly inserting and deleting individ­ uals from the test population. It also suggests other mecha­ nisms, such as fitness sharing or the use of different repro­ duction rates in both populations. The latter approach is in­ vestigated here. The goal is to obtain a good balance such that there is a steady progress in both populations. This is to avoid the tests from "out-evolving" the solutions and to ensure that there is sufficient variation in the fitness of the members of a population. The latter is necessary to guide (co )evolution.

The use of fitness sharing to preserve diversity in a competitive coevolutionary context has been investigated by a number of researchers. The Othello application of Smith and Gray [ 1994] is probably one of the earliest. Rosin and Belew [ 1995] combine competitive fitness sharing and shared sampling. The latter ensures that representative oppo­ nents are selected for the "competition duels". Juille and Pollack [ 1996] proposed another way to ensure population diversity: in a classification application, a solution receives a larger reward when it correctly classifies a test which is classified correctly by none (or only a few) of the other so­ lutions. More recently, Rosin [ 1997] has identified the causes why coevolutionary progress can come to a halt: the loss of important niches, coevolutionary cycles, or a lack of balance. He observed that, even with fitness sharing, solu­ tions might "forget" how to compete against old extinct types of individuals which might be difficult to rediscover. For this reason he introduces a "Hall of Fame", containing the best individuals of previous generations which are used for testing new individuals. This introduces some kind of memory in the system. In order to keep the progress in both population balanced, Rosin [ 1997] introduces a "phantom parasite" which provides a niche for "interesting" individu­ als.

The final goal of a CGA solving a test-solution prob­ lem is to find a solution which satisfies all possible tests.

Any other "victory" of the solution population is only a Pyrrhic victory. A solution population whose members sat­ isfy all members in the test-population, but who do not sat­ isfy tests which are unlikely to make their way in the test­ population, is useless. This is another reason why it is im­ portant to preserve the genetic diversity of the test popula­ tion for long enough a period.

The structure of this paper is as follows. The next sec­ tion describes the use of CGAs for test-solution problems in more detail. Section three describes how to obtain a bal­ anced coevolution within a CGA and how the memory can be increased. The fifth section evaluates the impact of these mechanisms when solving multimodal problems described in section four. Finally, the paper closes with a discussion and conclusions.

2 CGAs For Test-Solution Problems

As a first step in applying CGAs to test-solution problems, both initial populations are filled with randomly generated individuals. Their fitness is calculated by pairing them up with 20 randomly selected members of the other popula­ tion. In order to calculate the fitness of an initial solution, one counts the number of tests it satisfies. Similarly, the fitness of a test is the number of solutions (out of a ran­ domly chosen set of twenty solutions) which violate the test. As a matter of fact, each individual - test or solution - has a history which stores the fitness feedback - or pay-off­ resulting from such an encounter. A solution receives a pay­ off of one if it satisfies the test. Otherwise it receives a zero. The opposite is true for tests: they get a pay-off of one if the solution encountered does not satisfy a test. The fitness of an individual is equal to the sum of the pay-offs in its history. It is also good to note that the populations are sorted on fitness: the fitter the individual the higher its rank in the population.

The pseudo-code below describes the basic cycle the CGA executes after the initial populations are generated. First, 20 encounters are executed in which a test and solu­ tion are paired up. The SELECTion of these individuals is biased towards highly ranked individuals, i.e. the fitter in­ dividuals are more likely to be SELECTed. In a CGA, the most fit individual is I .5 times more likely to be selected than the individual with median fitness . Next, the actual ENCOUNTER happens during which it is tested whether the solution satisfies the test it encounters. The result of the encounter is one if it does. Otherwise it is zero. This result is also the pay-off received by the solution. The test re­ ceives the "inverse" pay-off. The function TOGGLE in the basic cycle implements this inverse fitness interaction be­ tween tests and solutions. It changes a one into a zero and vice versa. Again, each individual stores the pay-off it re­ ceives in its history. At the same time, the pay-off that the individual received least recently is removed from the his­ tory. This guarantees that the history will always contain the 20 most recently received pay-offs. This UPDATE of the HISTORY of an individual , is followed by an UPDATE of the FITNESS of the individual: it is set equal to the sum of the pay-offs in its history. Because both pop­ ulations are kept sorted on fitness , an individual might move up and down in its population as a result of the up­ date of its fitness.

After the execution of the encounters, one offspring is generated in each population. This happens as follows . First, two parents are SELECTED from the population, again with the same bias towards fitter individuals as ex­ plained above. Next, (2-point reduced surrogate) CROSSOVER and (adaptive) MUTATion are used in order to generate the child from the bit-string of each of its par­ ents. Then the FITNESS of the CHILD is calculated as the sum of the pay-off received from encounters with 20 SELECTed individuals from the other population. If this fi tness is higher than the min imum fitness in the popula­ tion to which its parents belong then the child is INSERTED at the appropriate rank location in this popula­ tion. At the same time, the individual with the minimum fitness is removed. In this way, both populations remain sorted on fitness .

DO 20 TIMES sol:= SELECT (so l -pop) test:= SELECT(test-pop) res:= ENCOUNTER(sol,test) UPDATE-HISTORY-AND-FITNESS(so l ,res ) UPDATE-HISTORY-AND- FITNESS(test,TOGGLE (res )) END DO s-parentl:= SELECT (so l -pop) s-parent2:= SELECT (sol - pop) s-child : = MUTATE-CROSSOVER(s-parentl,s-parent2 ) f:= FITNESS(sol-child) INSERT(sol-child,f ,sol-pop) t-parentl:= SELECT(test-pop) t-parent2:= SELECT (test-pop) t-child:= MUTATE-CROSSOVER(t-parentl,t - par ent2 ) f:= FITNESS(test-child) INSERT(test-child , f,test-pop)

A couple of remarks are in place here. First, note that in or­ der to avoid unreliable pay-off from poss ible mediocre off­ spring, the encounters with new offspring do only result in pay-off for the child, not for the individuals it is encounter­ mg.

Second, the partial but continuous fitness feedback re­ sulting from the encounters is called life-time fitness evalu­ ation (L TFE). Two parameters are associated with it. The first is the size of the histories. The second is the number of encounters per cyc le. In all previous CGA applications, both parameters are set - quite arbitrarily - to 20. Except when mentioned explicitly, this will be the case here too.

3 Increasing the Memory and Keeping the Balance

This paper investigates whether an increase of the memory of the individuals prevents the two species (solutions and tests) from performing a cyclical dance of changes without really improving their quality. By increasing the memory, individuals which learn new things at the expense of things learned earlier are penalized. The balancing mechanism pro­ posed here is devised to prevent the tests from outperforming too much the solutions. It also ensures that as the solu­ tions get better, more effort is put into finding tests which are not satisfied by the solutions.

3.1 Memory

The steady-state character of the CGA together with the con­ tinuous nature of L TFE provides memory to the individu­ als. An individual's fitness reflects its performance against members of the opposite population over a period of time. The variant proposed here accumulates the pay-offs received during the entire lifetime of an individual. In this case, the fitness is defined as the number oftimes a pay-off of one is received divided by the total number of encounters the indi­ vidual was involved in. This alternative for L TFE is called lifelong fitness evaluation (LLFE). With LLFE, the fitness of an individual reflects its performance against the mem­ bers of the opposite population it encountered during its en­ tire lifetime. In this way, there is a selective advantage for individuals to also "beat" members of less recent genera­ tions of the opposite population. Hence, in comparison with LTFE, LLFE increases the memory of the individuals.

3.2 Balance

The need for a balanced evolution immediately raises two questions: 1) How can the CGA recognise that the evolu­ tion is getting unbalanced? 2) Once an imbalance is recog­ nised, how can the balance be restored?

The answer to the first question is relatively simple: if both populations evolve in a balanced manner then they will receive roughly the same amount of pay-off during the encounters. Conversely, the evolution is getting more im­ balanced as the pay-off received by both populations is more unequal.

Now, the second question can be addressed. What should be done when one population gets considerably more pay-off than the other? Somehow the weaker popula­ tion has to be given a helping hand. Its efforts to counter the increasing opposition should be increased. This is done by allowing different reproduction rates in both popula­ tions. In the standard CGA, two offspring are generated per cycle, one in each population. Now, only one offspring will be generated per cycle. The percentage of successes in the last twenty encounters is used to stochastically determine which population evolves. If none of the 20 encounters is successful then the tests may well be too good, i.e. diffi­ cult, for the solutions currently in the solution population. Hence, the probability that the solution-population evolves (i .e. two parents are SELECTED from it, and if their off­ spring is fit enough, it is INSERTed in the solution popu­ lation) is equal to one. As the percentage of successes in­ creases this probability linearly decreases (see figure 1 ). It becomes zero when all encounters are successful. In this case, the probability that the test population reproduces is equal to one.

4 Testing the CGA on the P-Model

DeJong eta!., [1997] introduce a simple multimodal prob­ lem generator which allows to perform controlled experi­ ments testing the mechanisms described above. As a first step, a set of P random bit-strings of length N is generated. These represent the location of P peaks in a N-dimensional boolean hypercube. The strength I of an individual is equal to the proportion of bits the string has in common with the nearest peak. When P is equal to one, a single peaked strength-landscape is obtained. For larger P, the modality, as well as the degree of epistasis, increases.

The P-model allows us to test the mechanisms intro­ duced before on problems with different degrees of diffi­ culty. An additional advantage of the P-model- in compari­ son with, for example, the NK-model [Kaufman, I989] - is that the optimal value of strength is known: it is one. Furthermore, for different P, the variance in strength is not significantly reduced.

In our experiments, the P-model is used as follows. Each population, test and solution, has its own set of op­ tima which might be different in location as well as num­ ber, i.e. they can have a different value of P. During an en­ counter, the individual with the highest strength gets a pay­ off of one, the other receives zero pay-off. These pay-offs are used to calculate the fitness as described in section 2. As was the case for test-solution problems, the pay-offs are re­ stricted to two values, zero and one, instead of just being equal to the respective strengths. This to facilitate the gen­ eralization of the conclusions drawn from the experiments described here to test-solution problems in general. Note that when the individuals involved in an encounter have the same strength, the solution gets the pay-off of one and the test gets zero pay-off. This to ensure that there exists a solu­ tion which beats all tests. Ideally, the CGA should find this individual which has a strength of one.

1 De Jong et al use the term fitness. We use the term strength in order to avoid confusion with the definition of fitness in CGAs.

5 Empirical Results

Just as was the case in earlier CGA applications, both popu­ lations contain I 00 individuals. Also the same genetic op­ erators are used: reduced surrogate two-point crossover and adaptive mutation. Furthermore, N is set equal to 50. In the experiment described here, the degree of epistasis of the test strength landscape is higher than that of the solution land­ scape. Due to space restrictions two other experiments, in which the solution strength landscape has the highest P, or where both populations have the same P value are not re­ ported here. These two additional experiments confirm the conclusions drawn from the experiment discussed here.

In the current paper, the performance of 8 CGA variants is compared. The name of each variant consists of a triplet. The first part indicates whether L TFE or LLFE is used to calculate the fitness of the solutions. The second part repre­ sents the type of fitness calculation used for the test popula­ tion. The third part is either labelled "TRAD" or "BAL". The former indicates that the traditional "unbalanced" algo­ rithm - as described in section 2 - is used, the latter uses the balanced algorithm. L-T-BAL, for example, refers to the BALanced variant which uses lifelong fitness evaluation (LLFE) for the solution population, and lifetime fitness evaluation (LTFE) for the test population.

In order to allow for a fair comparison, all variants gen­ erate 5000 offspring. This means that the variants with a balanced evolution execute 5000 cycles, whereas the "unbal­ anced" variants - which produce two offspring per cycle - execute 2500 cycles. In order to ensure that all variants use the same amount of computing time and fitness feedback, the balanced variants perform I 0 encounters per cycle in­ stead of20.

The experiment repeats the following steps 50 times. First, a solution strength landscape (P= 250) and a test strength landscape (P= 500) are generated. Next, each vari­ ant is run on these landscapes. Finally, the strength of the highest ranking solution individual of each variant is com­ pared. Table I summarizes the results obtained. The first column of this table shows how often a given variant pro­ duces a highest ranking solution with a strength greater (or equal) than the strength of.the highest ranking solution in­ dividuals of the other variants. The second column indicates how often it was the second best, etc. Table I shows, for example, that for 38 out of 50 runs the highest ranking so­ lution individual of T-T-BAL has the highest strength. Note that the total of all numbers in the first column of the table is above 50. This is because the highest ranking solu­ tion of several variants might have the same strength.

A couple of observations can be made from the table. First of all, the upper left quadrant of the table (four left­ most columns of the four top rows) and the bottom right quadrant contain small numbers. The large numbers are lo­ cated mainly in the two other quadrants. Or, in other words, the balanced CGAs consistently outperform the traditional CGAs in which each population evolves at the same rate. The balanced variant without LLFE, T-T-BAL, performs best. It is not only 38 times the best of the eight variants. In 46 (3 8 + 8) out of 50 runs it finds the best or second best strength. Hence, this indicates that LLFE does not bring any improvement, on the contrary.

The same picture emerges from table 2 which compares the variants on the basis of the highest solution strength en­ countered during the entire run. Again, the balanced variants outperform the unbalanced ones considerably. Once more, T-T-BAL is the winner.

A third observation is that, at the end of the run of each balanced variant, the solution population always contains at least one individual with the largest strength encountered during the entire run . For, T-T-TRAD, L-T-TRAD, T-L­ TRAD, and L-L-TRAD, on the other hand, this is only true for 37, 35, 33, and 40 out of 50 runs, respectively. Moreover, at the end of a run with a balanced CGA, this individual with the highest strength can often be found at the top of the solution population. For T-T-BAL, L-T­ BAL T-L-BAL and L-L-BAL this is the case in 27, 27, 19 a~d 30 out of 50 runs, respectively. This is considerably lower for T-T-TRAD (6), L-T-TRAD (12), T-L-TRAD (12), and L-L-TRAD (8). This increased ability of the balanced variants to keep the best individual at the top of the population, explains why the difference between the balanced and unbalanced variants is most outspoken in Table I.

Finally, let us define a population with a highest fit­ ness smaller or equal to 0.1 as an extinct population. In none of the 50 runs, a balanced CGA variant produced an extinct (test or solution) population. This in contrast with the unbalanced variants. As a matter of fact, extinctions only occurred in populations which used L TFE. Out of 50 runs, the solution population ofT-T-TRAD and T-L-TRAD became extinct 10 and 3 times respectively. Extinction of test populations occurred 20 and 14 times. The former when T-T-TRAD was used. The latter when L-T-TRAD was used. Clearly, such extinctions must be avoided because uniform low fitness values do not provide enough information to guide coevolution.

6 Conclusions and Discussion

As described in the introduction, other researchers have used fitness sharing to preserve genetic diversity in a coevolu­ tionary environment. The balanced CGA deals with the di­ rect cause of the loss of diversity: selection. When selection is too severe, the population rapidly converges to a (sub)optimum. In a CGA, selection occurs through compe­ tition between new offspring and individuals already in the population. The balancing mechanism proposed here makes the reproduction rate (and hence the amount of selection) dependent on the success of the population. In this way, the algorithm avoids that the better population "out-evolves" the weaker one. In fact, once an imbalance occurs, the weaker population is allowed to catch up: more search effort is spent on it. This at the expense of the stronger popula­ tion whose progress - and convergence - is slowed down.

The experiments show that a balanced coevolution re­ sults in an increased performance. Two reasons can be iden­ tified for this success. A first one was already given in the previous paragraph: balanced coevolution maintains genetic diversity. In this way, individuals are confronted with a di­ verse opposition. Secondly, the balancing mechanism, to­ gether with the inverse fitness interaction between both populations, ensures that the fitness variance between mem­ bers of a population is maximal. This because when each population receives about the same amount of pay-off then each population receives roughly as many zero pay-offs as ones. This results in fitness variance which, in its turn, guides (co )evolution. In addition to this, the balanced vari­ ants maintain the best solutions found, in (the top of) the population.

In the experiments above an increase in memory did not result in increased performance. There is not yet a satis­ fying explanation for this. Possibly the steady-state nature of a CGA and the partial and continuous fitness feedback of LTFE provide more than enough memory. Note that al­ though L TFE does not take into account pay-offs received more than 20 encounters ago, the very survival of an old individual indicates that it has been able to withstand nu­ merous opponents. Alternatively, the type of problems used here might preclude the need for memory. In fact, as individuals climb the strength-landscape, the set of opponents which beat them monotonically decreases. Hence, there is no risk of "forgetting" to beat opponents which were beaten by previous, inferior, individuals. The experiments do, however, suggest a possible relationship between memory and balance: in the absence of a balancing mechanism only populations using LLFE could avoid "extinctions". Hence, balance does seem to decrease the need for memory.

It is good to look whether nature also "uses" a balanc­ ing mechanism. When a predator species becomes too suc­ cessful then more prey is killed. In the short term, the pop­ ulation size of the prey decreases while that of the predators increases. This puts a natural brake on the growth of the predator species because food (i.e. prey) becomes more and more scarce2. Similarly, too effective prey will, on one hand, lead to a rapid increase of the prey population size, which, in its tum, provides a larger food resource for the predators. On the other hand, the predator population size decreases, i.e. the selective pressure to improve increases. Hence, in nature, fluctuations in population size keep (co )evolution in balance. This in contrast with the fixed population sizes in CGAs which do not allow for real ex­ tinctions of test or solution species. Hence, an alternative balancing mechanism is introduced here which adapts the selective pressures through a change of reproduction rates.

Recently, Olsson (1998) introduced a balancing mecha­ nism which lets a population evolve until it contains an in­ dividual (a "champion") beating all the individuals in the other population. Next, the other population evolves until it finds an individual beating all members of the first popula­ tion. This process is then repeated but at each stage all the previous champions as well as the current members of the opposite population should be beaten. Such a mechanism could be introduced in a balanced CGA by marking cham­ pions. These marked individuals should always remain in the population.

Although experiments with different degrees of epista­ sis support the conclusions given here, other CGA applica­ tions are needed to confirm their generality. Other balancing mechanisms, for example based on the (difference in) fitness of the individuals instead of oil the number of successes during the encounters, might further improve performance.