1 15-Co-evolutionarySystems

2 Co-Evolutionary Systems

Motivation

Cooperative vs Competitive co-evolution

Approaches

3 Motivation

• So far: problems with easy to measure fitness
• More difficult: fitness depending on context :
  • Solution represents a strategy that works in opposition to some competitor (chess)
  • Solution being evolved does not represent a complete solution (set of traffic-light controllers)
• In nature: adaptation of a biological species
  • Adaptive value is determined by the evolutionary niche which is determined by the other organisms:
    • Positive effect (mutualism /symbiosis ), e.g . plants and insects
    • Negative effect (predation/parasitism ), e.g . foxes and rabbits
  • Co-evolution: the landscape “seen” by each species is affected by the configuration of all other interacting species and will move

4 Co-evolution

• Applications:
  • Co-evolution of a population of partial models in Michigan-style LCS
  • Evolution of game playing strategies
  • Implementations:
  • Both cooperative and competitive
  • Using both single and multiple species models

5 Cooperative Co-evolution

• Models in which a number of different species, each representing part of a problem, cooperate in order to solve a larger problem
  • High dimensional function optimization
  • Job shop scheduling
• Advantage: effective function decomposition
• Disadvantage: relies on user to subdivide problem
• Difficulty: how to pair the populations to gain a fitness value

6 Competitive Co-evolution

• Model where individuals compete against each other to gain fitness at each others expense
  • Iterated prisoner’s dilemma

7 Algorithmic Adaptations

• Choice of context can significantly influence the EA performance
• Adaptations include:
  • Averaging over more contexts
  • Include history (archive of past solutions) to avoid “cycling”