Coevolution In Artificial Intelligence
Normally, when the word coevolution is heard, biology is the first thing we think.
The term coevolution is used to describe cases where two (or more) species mutually affect each other’s evolution. For example, a change in the morphology of a plant might affect the morphology of an herbivore that eats the plant, which in turn might affect again the plant, which might affect the evolution of the herbivore…and so on[0]. In concrete words, let us consider the relation between the acacia ants and acacia plants. In this relationship, the plant and ants have coevolved to have a symbiotic relationship in which the ants provide the plant with protection against other potentially damaging insects, as well as other plants which may compete for nutrients and sunlight. In return, the plant provides the ants with shelter and essential nutrients for the ants and their growing larvae.
The same setting works also in Computational Intelligence (the branch of Artificial Intelligence assigned to theory, design, application and development of biologically and linguistically motivated computational paradigms), where this idea is merged with the traditional idea of evolutionary algorithms: use the Darwinian notions of heredity and survival of the fittest for simulation or problem-solving purposes.
Evolutionary Algorithms
Evolutionary Algorithms (EAs) are inspired by Darwin’s theory of evolution. The solution for a given problem can be reached through evolution.
The algorithm starts with a set of solutions (each solution is also called individual or genome) called population. Normally this population is randomly generated (Initialization). Some individuals from the current population are used to form the next population (Parent selection). Ideally, the new population will be better than the old one. Individuals are selected to form new solutions (Offspring) according to their fitness value, better they perform in the environment, more chances they have to reproduce. This step includes two sub-steps: Recombination and Mutation. In the recombination process, the genome of the “parents” is used to create children, meaning the children will have a piece of the genome from each parent. In the mutation step, we introduce a small change in the genome of the children probabilistically, in order to make them slightly different from the parents. Then Survivor Selection is applied, in order to keep the population size the same for the entire evolution
This process is repeated until some end condition (i.e. max number of generation reached, precision on the solution reached) is satisfied.
Coevolutionary Algorithms
The idea of coevolution started to be used around 1990, where this kind of interaction has been added to the standard evolutionary algorithm.
The behavior of a coevolutionary algorithm depends on the interaction between individuals. In this case, the individuals are evaluated not in terms of an explicit fitness function, but rather by direct interactions between individuals taken from the coevolving populations. Traditional EAs assess the fitness of an individual objectively, independently from the population context in which the individual is placed. Coevolutionary algorithms (CEAs) operate much like traditional EAs except that fitness assessment is not objective, but subjective: an individual is evaluated through its interaction with other individuals in the evolutionary system. Two different interactions between populations have been developed: cooperative and competitive.
Cooperative Coevolution
Cooperative Coevolutionary algorithms are often used in situations where a problem can be naturally decomposed into sub-components. Individuals represent such subcomponents and are assessed in a series of collaborations with other individuals in order to form complete solutions. The fitness of a sub-population is an estimate of how well it “cooperates” with other species to produce good solutions. Cooperative Coevolutionary algorithms have had success in a variety of domains, for example, manufacturing scheduling, function optimization, designing artificial neural networks and room painting.
Cooperative Coevolution pseudocode:
FOR each subproblem S DO
initialise a subpopulation Sub_Pop_i(S) with random individual
END FOR
FOR each subproblem S DO
calculate fitness for each individual in Sub_Pop_i(S)
END FOR
WHILE termination criteria not satisfied DO
FOR each subproblem S DO
select individual from Sub_Pop_i(S)
recombine individual
mutate individual
calculate fitness of each member in Sub_Pop_i(S)
END FOR
END WHILECurious to see some real-life example of cooperative coevolution? Check these papers out: Large scale evolutionary optimization using cooperative coevolution, Cooperative Coevolution of Artificial Neural Network Ensembles for Pattern Classification, and Cooperative Coevolution of Multi-Agent Systems.
Competitive Coevolution
Competitive Coevolution either occurs within one population engaged in self-play or between multiple populations. Competitive coevolution has several interactional species. In order to obtain the common resources and space, they compete with each other. Single population competitive Co-evolution has been successfully applied to the Iterated Prisoner’s Dilemma, pursuit, and evasion, and to finding robust game strategies in, for example, Tic-Tac-Toe and backgammon game, etc.
Most popularly competitive Coevolution has been applied to game playing strategies and additionally it demonstrates the effectiveness of competition for evolving better solutions by developing a concept of competitive fitness to provide a more robust training environment than independent fitness functions. Competition played a vital part in attempts to coevolve complex agent behaviors. Finally, competitive approaches have been applied to a variety of machine learning problems.
Competitive Coevolution pseudocode:
FOR each population DO
initialise population Pop_i with random individuals
END FOR
FOR each population DO
calculate fitness Pop_i individuals against all other populations
END FORWHILE termination criteria not satisfied DO
FOR each population DO
select individual from Pop_i
recombine individual
mutate individual
END FOR
FOR each population DO
calculate fitness Pop_i individuals against all other populations
END FOR
FOR each population DO
survivor selection
END FOR
END WHILE
Want to see some real example of competitive coevolution? Check these papers out: New Methods for Competitive Coevolution, Competition, Coevolution and the Game of Tag, and Competitive Coevolutionary Multi-Agent Systems: The Application to Mapping and Scheduling Problems.
Advantages of Coevolution[2]
Intuitively, coevolution promise to be a very good heuristic algorithm in many domains where more traditional evolutionary methods fail. The hope of coevolution is to produce a dynamic typically referred to as an arms race.
In an arms race, a performance increase is generated by each population making incremental improvements over the others in such a way that steady progress is produced. The idea is that the system is driven to better parts of the search space by these reciprocal improvements, each getting better and better over time. Consider the predator-prey example: the prey evolve to run faster; then the predator population is forced into evolving behaviors that overcome this advantage; then the prey evolves better hearing to detect their enemies, and again the predators have to change. The hope is that, in the end, both populations have super attributes.
Common problems
Applications of CEAs (both cooperative and competitive versions) often fail, or the algorithms turn out to be far more difficult to tune than are traditional EAs. The reasons for this lie partially in measurement problems caused by the use of subjective fitness and partially in the often particularly complicated dynamics of coevolutionary systems.
Disengagement problem
Perhaps this is the most common problem, in which one population comes to dominate the others, thus creating an impossible situation in which the other participants do not have enough information from which to learn. For example, think a small child, new to the game of football, attempting to learn to play by playing against Cristiano Ronaldo and Lionel Messi at the same time.
Cyclic behavior
Intransitivities in the reward system can allow one population to adapt slightly to gain an advantage over the others, then the others follow immediately, only for the original population to change again, eventually, back to the original strategy.
Focusing problems
Often, CEAs end to produce good solutions because the coevolutionary search has driven players to over-specialize on their opponent’s weaknesses.
Several solutions have been found to solve these problems, literature is full of paper discussing how to improve the standard setting of CEAs. There are so many of them that it is better to list them in a future article. Hope to have increased your interest in coevolution with this article, I invite you all to try them. It is fun to launch experiments and wait to see what amazing result will appear at the end!
P.S. I am not the author of the paper linked in this post. Searching for the corresponding keyword they appear in Google Scholar on the first page. They are selected randomly just to link to some real-world scenarios.
References
[0] https://evolution.berkeley.edu/evolibrary/article/evo_33
[1] Shi, M. & Gao, S. J Heuristics (2017) 23: 1. https://doi.org/10.1007/s10732-016-9322-9
[2] Rudolf Paul Wiegand. 2004. An Analysis of Cooperative Coevolutionary Algorithms. Ph.D. Dissertation. George Mason Univ., Fairfax, VA, USA. AAI3108645.