Coevolutionary Algorithm

A Coevolutionary Algorithm (CEA) is a natural extension of an EC where each individual is evaluated based on its interactions with other individuals. For standard EC algorithms, an individual is evolved among its population in a fixed environment.

In contrary, CEA proposes that the environment is simultaneously influenced by all populations which interact with one another independently. Hence, each population, in addition to local adaptation within its own population, takes turn to evolve in response to the ever-changing environment, caused by the evolving populations.

Unlike standard EC algorithms in which each individual is evaluated according

to an explicit fitness function, a CEA uses the performance comparison between populations as an evaluation measure. The performance comparison measures the interaction success of an individual in relation to other individuals of the same population. This interaction measure is also called a relative fitness. With a CEA, we can search for the solutions without prior knowledge of the problem domain or an explicit fitness function of the population. Thanks to the interactions, the relative performance comparison drives the coevolution process between interacting populations [15].

One of the significant features of a CEA is to allow the individuals to escape from stagnation in local optima. When the environment is gradually altering over time, the algorithm perturbs the fitness landscape in such a way that some individuals are able to migrate from the local optima [5].

In a CEA, different populations normally play different roles. We categorize a CEA into two major groups: (1) competitive CEA and (2) cooperative CEA.

On the one hand, a competitive CEA establishes an arm race condition where an advantage of a population implies a disadvantage of the other. Each population focuses on outperforming the other. On the other hand, a cooperative CEA set ups a symbiotic conditionwhere all populations mutually benefit from their collaboration.

Both groups of CEAs contain different concepts of population interactions as well as controlling policies. In the following subsections, we describe the generic algorithm of coevolution, then explain the characteristics of both competitive and cooperative CEAs. We focus on a competitive CEA because it is the basic mechanism for our proposed methodology.

2.1.5.1 General CEA Algorithm

The algorithm 2 shows the idea of how coevolution works in general. For each gen-eration, we first calculate the relative fitness of each individual in every population group and then evolve each population group afterward. We can use any EC algo-rithms to evolve each population group distinctively. To calculate relative fitness of an individual, we select some individuals from the opponent groups as the com-petitors/collaborators and use the competition/collaboration results to compute the relative fitness.

Algorithm 2 Generic Coevolutionary Algorithm

1: Initialize generation counter: g = 0.

2: Initialize all populations P.

3: do

4: foreach population P_i ∈P do . calculate relative fitness

5: Sample opponent individuals S from each populations {P−P_i}.

6: foreach invidiual C_i ∈P_i do

7: Evaluate relative fitness ofC_i with respect to sampling populations S

8: end

9: end

10: foreach population P_i ∈P do .evolve using EC

11: Evolve population P_i to the next generation.

12: end

13: Advance to the next generation: g =g+ 1.

14: while (stop condition is not true)

15: Select the best individual as the solution.

2.1.5.2 Competitive Coevolution

In this algorithm, we reward an individual when it works well against the other populations. In this case, each population tries to compete with one another and become better and better at its defensive and offensive strategies in each generation.

This is similar to a predator-prey model in biological systems, where a predator keeps developing its attacking tactics while its prey keeps improving its escaping strategies. Another analogy to the method is a host-parasite model, where a host represents a solution to solve a problem with data sets defined by a parasite. A solution host evolves to solve as many problems as possible, which, in turns, become more and more difficult due to the adapting data sets [21].

Controlling Policies: In a competitive CEA, there are several controlling policies to accelerate the coevolution. Two major concerns are of interest: (1) how to evaluate a relative fitness of an individual in one population from the performance comparison between several population groups, and (2) how to sample individuals from one population to coevolve with the others.

Relative Fitness Evaluating Policies: A CEA supports interactions be-tween different types of populations. The fitness evaluation is a relative measure of each individual’s performance in the whole interacting environment. We can measure this fitness in several ways. Below is the list of commonly used policies

[15]:

1. Simple fitness: For a given individual, we directly count the number of defeated opponent individuals, as a relative fitness score. In this case, the most winning individual is the fittest individual in the population.

2. Fitness sharing: For a given individual, we calculate a relative fitness score from the simple fitness divided by the sum of its similarities in the winning list. The most winning individuals may win over the same opponents similar to others, and they all share the same amount of fitness rewards. In this case, we oppose the similarity of the winning list and reward unusual individuals containing the uniquely maximum winning list.

3. Competitive fitness sharing: In this policy, we first compute the competitive fitness from the viewpoint of opponent individuals. For each opponent individ-ual, the competitive fitness is inverse proportionally to the number of losses.

The most losing opponent has the lowest competitive fitness, while the least losing opponent (aka the most winning opponent) has the highest competitive fitness. Hence, for a given individual, a relative fitness score represents a sum-mation of the competitive fitness from the opponents it can win. This policy rewards the wins over the opponent that only a few other individuals could beat.

These policies are specifically designed for the competitive CEA, where a loss in one population group is a gain in the other group(s). This is contrary to the nature of the cooperative CEA, where a collaboration is necessary and different measures of relative fitness are required.

In addition to the fitness ranking for the selection process, we also use the rel-ative fitness in the sampling policies to help reduce the computational expense of coevolution process.

Sampling Policy: This is a policy to match an individual from one population group to coevolve with individual(s) from different groups. The followings are the common sampling policies normally used in a CEA [15].

1. No sampling: This is one of the simplest forms of the sampling policy. We match all individuals in a population group to all individuals in the other, in

a round-robin fashion. It is the most time-consuming policy among all, yet it always gives the satisfying results because all possibilities are paired. This policy is good with a small-size population.

2. Random sampling: In this policy, we select a sample uniformly at random.

Thus, the coevolution processes are computationally minimized, yet the quality of the coevolution is somewhat questionable.

3. Fittest sampling: To reduce the amount of coevolution while still preserving the quality results, we select only the fittest individual from the other popu-lation groups for the samples.

4. Tournament sampling: A tournament is a series of pair-wise matches where the winner advances to the next round, until the most winning individual is decided. We emulate a tournament of random matches to determine a sample.

5. Shared sampling: In this method, we select opponent individual(s) with most wins over the opposing population groups as the samples. (see competitive fitness sharing policy in the previous subsection.)

In addition to the competitive CEA, we can apply this sampling policies to the cooperative CEA. The explanation for the cooperative CEA is given in the next subsection.

2.1.5.3 Cooperative Coevolution

We reward an individual when it works well along with the other populations and benefits the whole environment. Meanwhile, we punish an individual when it works poorly with the others and spoils the environment.

Potter and De Jong proposed the cooperation approach of CEA in 1994 [42]. In their approach, each population group represents a component of a solution, and a collection of the best individual from these groups establishes a complete solution to the problem. The cooperative CEA coevolves independent components more efficiently than when the traditional EC evolves an entire solution. Algorithm 2 also shows the main idea of the cooperative coevolution algorithm.

As cooperative CEA focuses on the collaboration between subcomponents, the relative fitness evaluation should measure the effort contributed by an individual col-laborator appropriately. We call this measurement acredit assignment policy. There

are many policies to faithfully evaluate an individual subcomponent corresponding to its contribution. Three of the most often used policies are optimistic, hedge, or pessimistic; in which we assign an individual the value of its best collaboration, average collaborations, or worst collaboration, respectively [61].

2.1.5.4 CEA Implementation Concerns

Although the interactions among the population groups, both competitively and cooperatively, may help the evolution process refrain from local stagnation, there are times when the evolving process faces new dilemmas. Two of the most frequently found CEA dilemmas are losses of gradientsand cycling population dynamics [4].

Losses of gradients occurs when a population group reaches a state that makes other groups lose fitness pressure to keep them from improving. For competitive CEAs, imagine when one population group is much more superior to its component group. In this case, the opponent group always loses and learns nothing from the competition. For cooperative CEAs, if a population group somehow loses its di-versity instantly, the search space of its collaborator groups is suddenly limited in response.

Cycling population dynamics indicates a situation similar to the non-dominant, cyclical wins in the game of rock, paper, scissors, where a population group evolves back to the same state after several generations. There are several techniques to solve this problem. The concept ofhall of famewhere the fittest individuals from the previous generations are also included in the competitions is one of the well-known practical solutions.