Belgium-Netherlands Conference on Artificial Intelligence BNAIC'99, 3-4 November 1999, Vaeshartelt, Maastricht

Evolutionary Computation 1 was the first session in which technical papers from the conference were presented. It took place in parallel with two other session but never-the-less both presentations were well attended. They took place in the Koning Willem II room. However despite its attractiveness, including views of the beautiful grounds of the castle, both presenters kept their audience's attention.

David van Bragt of the CWI (David.van.Bragt@cwi.nl) presented his work on the importance of difference selection techniques on the evolution of co-operation when using Genetic Algorithms (GAs) with the Prisoner's Dilemma, a non-zero sum game.

This was a re-submission of a paper he presented at the 5th International Conference of the Society for Computational Economics on Computing in Economics and Finance (CEF'99), Boston College, USA, 24-26 June. An extended version (with the same title and authors) appeared (17 (2-3): 253-263, June 2001) in the "Computational Economics" journal.

Iterated Prisoner's Dilemma (IPD) is a game which, following Robert Axelrod's work, has often been taken as a simple model of economics and psychology. In particular the IPD is a suitable model for investigating the emergence of co-operative behaviour in spite of immediate rewards to both parties to cheat on the other. David showed the selection scheme is crucial to the evolution of populations of co-operative agents which are stable to invasion by more selfish behaviour. Several selection schemes were investigated. Each can be taken as a model of different economies. For example "Fitness Proportionate" requires global knowledge while "Tournament Selection" uses only local information. In these simulations each agent's score is obtained by pairing it with 12 other agents from the same population (60) and playing IPD with each. Thus the agents' behaviours coevolve, unlike in Axelrod's early work experiments where several hand coded opponents were provided.

David showed that using the measured fitness of the agent directly in roulette wheel (or fitness proportionate) selection gives too little selective advantage and co-operative behaviour does not evolve. However if selection pressure is increased (eg by using binary tournament selection or rescaling the fitness measure to give more children to slightly better parents) good behaviour arises which is reasonably stable.

However if the selection pressure is increased (eg tournament size of 8), co-operative behaviour arises quickly but the population is randomly invaded by cheats who rapidly increase in number and take over the whole population. Surprisingly co-operative behavior can evolve again in a population of cheats. David also showed as this varies between runs, averaging across many (25) runs yields smooth graphs but conceals the true random behaviour. Thus large tournament sizes appear to give rise to populations that on average score only marginly lower than with small tournament sizes.

David also investigated Thierens' elitist recombination (ER). This gaurentees high scoring agents or their successful children will be carried into the next generation. This was found to be the most successful at evolving co-operation and at providing protection against cheats in small tournament sizes. If the selection pressure was again increase, by increasing the tournament size, the population again became unstable. So that high scoring cheats could evolve and multiply. However co-operative behaviour was not displaced and quickly re-asserted itself (thus there is only a small drop in average performance with ER and large tournament sizes).

Even in "good" populations there are some cheats. Weak selection and ER prevent their numbers growing. However very strong selection promotes the occasionally high scoring cheat rapidly. If ER is not used they can take over the population. With lower selection pressure, co-operating agents have more time to spot and punish cheats. If they were not punished they would have scores even higher than the co-operating agents and so eventually take over the population. It might also be that the co-operating agents evolved with weak and strong selection are different. It would be interesting to know if different stratgies evolve and how they change over time.

One conclusion to be drawn is it is vital in multi-agent simulations that all the relevant parameters are included in published descriptions.

Bart Craenen (bcraenen@cs.vu.nl formally of LIACS, Leiden University but now at the Vrije University, Amsterdam) presented his comparison of heuristic-based Evolutionary Algorithms using solving randomly generated binary constraint satisfaction problems (CSPs) as example problems.

This is work compliments recent work by his co-authors on CSPs (for example Parallel Problem Solving from Nature, Amsterdam, PPSN 1998, LNCS 1498, pp196-205). They used an adaptive performance measure combined with a genetic algorithm. Here Bart looked at the other class of evolutionary algorithms used to solve CSPs. Ie the class where heuristics are combined with genetic algorithms using an integer representation. By systematically changing two probability parameters (tightness and density) 250 random CSPs were generated of different difficulties. The idea was for the heuristic+GA to find any solution which satisfied all the constraints. The CSPs ranged from the very easy (where all approaches found a solution) to very difficult (where none found any). Indeed it is possible there are no solutions to these. Bart highlighted the most interesting "mushy" region where performance between GAs and other approaches varies.

He tried three heuristic+GA approaches, which were chosen to represent most of the heuristic field. They include genetic repair after traditional crossover/mutation (ESP-GA), heuristic based genetic operators (H-GA) and a sophisticated constraint-network method (Arc-GA). The same population size (10) was used with each. The three Heuristic+GA approaches had similar performance. He gives data (Table 5) from a different GA approach (Dozier, WCCI-94) which gives much better performance in the mushy region. Bart suggests this is because Dozier's MID GA both uses a heuristic within the mutation operator and adaptively changes the fitness function. Ie spans both classes of CSP solvers. In the future Bart intends to investigate several mechanism which adapt the GA's fitness measure.