Minimal Criterion Coevolution

Quality Diversity algorithms like MAP-Elites diverge from nature in a couple of different ways: explicit behavior characterization, finite descriptor space and the need to maintain an explicit archive.

There remain limits to any analogy between QD and open-endedness in the spirit of nature. First, to date QD algorithms generally require defining a behavior characterization (BC), which is a descriptor of the phenotype behavior (and sometimes physical properties) of individuals in the search space. This requirement diverges from nature, where there is no need for anyone to develop a formalism for describing organism behavior simply to allow evolution to proceed. Second, though it may be vast, the descriptor space of BCs is intrinsically finite.

Finally, QD algorithms generally require an archive of some sort.

A main practical criticism of novelty and QD algorithms is they spend a lot of resources searching for "unimportant" areas of search space.

By design, novelty search and QD tend to spread the search to anywhere novel. A side effect and common criticism of this dynamic is the algorithm’s consequent susceptibility to expending resources exploring unimportant areas of vast behavior spaces.

Nature doesn't have this complexity and scaffolding, and is guided by a simple principle — survive long enough to reproduce. This is what is referred to as Minimum Criterion (MC).

Rather than measuring novelty explicitly, nature is guided by a single, fundamental constraint: survive long enough to reproduce. Surprisingly, this simple constraint produces both complexity and diversity in a continual process unparalleled by any algorithm to date.

It's not clear how to operationalize an MC to force diversity, the paper proposes the core idea of "coevolution" of two populations with constraints with respect to each other called Minimal Criteria Coevolution (MCC).

The main contribution of this paper is to show that coevolution may help to address this problem by forcing the MCs of two interlocking populations to satisfy minimal criteria with respect to each other, even as both populations are gradually shifting simultaneously. This idea, called minimal criterion coevolution (MCC), is tested by coevolving a population of mazes with a population of maze navigating neural networks, where the MC is that each maze must be solved by at least one neural network, and each neural network must solve at least one maze. Anyone who satisfies that constraint can reproduce.

MCC shows open-endedness can be approached without hand-picked components and purely through survival.

MCC in the present paper preserves the concept of the MC, but demonstrates how the MC alone (i.e. without a BC, without narrowing viability boundaries, and without the need for an archive) can efficiently produce open-ended evolutionary artifacts, even in non-alife domains.

Coevolution

Coevolution is a promising approach when fitness evaluation is difficult. It also holds promise for a never-ending arms race, an aspiration for Open-Endedness.

Coevolution in the field of EC has a rich history [20] focused on aributing fitness when it is prohibitive to evaluate individuals on their own through an extrinsic absolute measure of performance.

Traditionally it is either competitive or cooperative.

These types of scenarios are traditionally divided between competitive coevolution, where individuals are rewarded according to their performance against other individuals in a competition [ 3], and cooperative coevolution, where instead fitness is a measure of how well an individual performs in a cooperative team with other evolving individuals [ 30 ].

This paper introduces a new kind of coevolution that is not exactly competitive or cooperative, with no need for an archive or ranking.

An important contribution of the present work is to introduce a new kind of coevolution (minimal criterion coevolution) that does not fit neatly into the traditional competitive versus cooperative dichotomy. Instead, the idea is to provoke a Chromaria-like diver- gent search dynamic through the interaction of individuals under a MC, but in a more general context that is independent from any overarching alife world.

a key distinction is that it does not require an archive for non-dominated learners, nor does it impose a ranking among solutions.

Minimal Criterion Coevolution

Ranking individual, while pretty great, comes with biases. MC is better because its just a binary evaluation — does the individual meet the criterion or not. Just maintain a queue of "fit" individuals so that each of them gets to reproduce at least once.

A notable characteristic of this process is that it imposes no ranking among individuals (that is, they either satisfy the MC or not), necessitating a selection method that is free of bias.

MCC requires seed population that meets a non-trivial MC, so random initialization doesn't work well. Therefore it uses Novelty Search to "bootstrap" its seed population.

Most evolutionary algorithms begin evolution with a randomly generated population; however, the requirement that queue membership be predicated on satisfying the MC necessitates special consideration for MCC initialization. In particular, it is unlikely that a randomly generated individual will be capable of meeting a non-trivial MC, thereby denying admiŠance to any of the popu- lation queues. Therefore, each population queue must undergo a bootstrap process wherein the requisite number of seed genomes required by the applicable population queue are pre-evolved (novelty search serves as the bootstrap in this paper).

Because fitness is not computed or compared, MCC is extremely parallelizable.

Its absolute measure of perform- ance (i.e. the MC) allows large chunks of a population to be evalu- ated in parallel (their fitness never needs to be computed or com- pared). This freedom facilitates a distributed execution paradigm wherein evaluations are spread across multiple nodes.

Diversity with Speciation

Diversity can also be enforced with a concept called "speciation", but no need for behavior categorization. This is done by clustering similar individual and tagging with a species identifier, with the seeds starting off as the centroids. Queue capacity is then distributed evenly among species.

While individuals from a given population remain physically stored in a queue structure, they are clustered into separate logical groups, or species, based on their genetic similarity and tagged with a species identifier. The seed genomes for a given population constitute the centroids of these species clusters. Additionally, the queue capacity is evenly distributed among species.

In the speciated version, instead of simply including the next batch of individuals in the queue order, a proportionate number of individuals are aggregated from each species for reproduction (though queue insertion order still dictates the order of selection). Recall that only individuals who satisfy the MC are in the queue. The offspring of the batch who satisfy the MC are then added to the queue as normal but also assigned to the species that shares the greatest genetic similarity. If any species has exceeded its capacity as a result of speciating the offspring, the oldest individuals assigned to those species are removed from the queue. This process also ensures that the queue remains at or below capacity.

It turns out this diversity maintenance is important in enforcing diversity. MCC alone tends to converge. [[Quality Diversity at it again.

Figure 2 depicts a sample of the mazes evolved by a typical single run of the MCC control. While the mazes often reach maximum complexity with effective agent trajectories, the trajectories that the maze structures permit tend to be similar....the agent and maze populations are converging in control runs to trajectories and maze structures that become standards across the run.

Figure 3 depicts a sample of the mazes evolved by a single run of the MCC speciated variant. Maze structures and agent traject- ories are significantly more diverse in these runs, suggesting that enforcing genetic diversity through maze and agent queue speci- ation is a viable approach to maintaining divergent and functional phenotypic diversity in a minimal criterion coevolutionary system.

Its also observed by the proportion of mazes solved by current agent population. With speciation the solving proportion is significantly less because there isn't a single global strategy possible with speciation.

An interesting side effect of a lack of diversity in the control is a comparatively high proportion of mazes that are navigable by the existing agents at any point in time (figure 5). The speciated variant indicates a significantly lower proportion of mazes that are successfully navigated by each agent at every point in evolution (p < 0.001; Welch’s t-test), a side effect of more diverse maze structures and navigation strategies. An important implication is that the mazes being evolved are nontrivial to solve because there is not a single navigation strategy that can solve more than a small fraction of them.

Experiment Details

The setup is maze and agents. Mazes make deceptive non-optimal trajectories through solution space visually explicit in form of dead ends and wandering paths. The maze has fixed start location and upper-left corner and target location on lower-right, and the complexity and genome is encoded by the number of interior walls. Agents are just simple neural networks. The MC is that the ability to navigate mazes is non-trivial — each agent must solve at least one of the mazes, and each maze must be solved successfully by at least one agent from current agent queue.

Authors use two variation, one with global agent and maze queues as baseline and another with speciation, with species level queues.

Genetic similarity is then based on computing the Euclidean distance between two full maze position vectors. If two vectors have different sizes, the missing genes in the shorter vector are assigned position zero. Individuals in both the agent queue and the maze queue are grouped with genetically similar agents or mazes respectively. Selection and removal processes are then carried out on a per-species basis

Exact parameters:

The novelty search bootstrap is executed with 250 agents and NEAT parameters identical to those in Lehman and Stanley [10] . Agents are evaluated on ten randomly-generated mazes, each with 8 walls of random composition. Execution halts when 20 distinct agents are evolved that can solve one or more mazes, and each of the 10 mazes is solved by at least one agent. The 20 agents and 10 mazes then seed their respective MCC queues. In the speciated variant, the seed genomes are the initial centroids of each species cluster.

Both configurations are executed for 20 runs of 2,000 batches each. The agent queue is seeded with 20 genomes and has a max- imum capacity of 250 with a 0.7 probability of mutating connection weights, 0.1 of adding a connection, 0.01 of adding a neuron, and 0.0001 of deleting a connection. The maze queue is seeded with 10 genomes and has a maximum capacity of 50 with a 0.05 probability of mutating a wall location, 0.05 of mutating a passage location, and 0.7 of adding a wall. These values produced reasonably diverse and complex results in an initial parameter sweep.