Genetic Algorithm¶
A genetic algorithm aims to mimic evolutionary processes so as to optimise a particular function on some space of candidate solutions.
The process can be described by assuming that there is a function \(f:V\to \mathbb{R}\), where \(V\) is some vector space. In the case of the Prisoner’s dilemma, the vector space \(V\) corresponds to some representation of a particular archetype (which might not actually be a numeric vector space) and the function \(f\) corresponds to some measure of performance/fitness of the strategy in question.
In this setting a candidate solution \(x\in\mathbb{R}^m\) corresponds to a chromosome with each \(x_i\) corresponding to a gene.
The genetic algorithm has three essential parameters:
- The population size: the algorithm makes use of a number of candidate solutions at each stage.
- The bottle neck parameter: at every stage the candidates in the population are ranked according to their fitness, only a certain number are kept (the best performing ones) from one generation to the next. This number is referred to as the bottle neck.
- The mutation probability: from one stage to the next when new individuals are added to the population (more about this process shortly) there is a probability with which each gene randomly mutates.
New individuals are added to the population (so as to ensure that the population size stays constant from one stage to the next) using a process of “crossover”. Two high performing individuals are paired and according to some predefined procedure, genes from both these individuals are combined to create a new individual.
For each strategy archetype, this library thus defines a process for mutation as well as for crossover.
Finite state machines¶
A finite state machine is made up of the following:
- a mapping from a state/action pair to another target state/action pair
- an initial state/action pair.
(See [Harper2017] for more details.)
The crossover and mutation are implemented in the following way:
- Crossover: this is done by taking a randomly selected number of target state/actions pairs from one individual and the rest from the other.
- Mutation: given a mutation probability \(\delta\) each target state/action has a probability \(\delta\) of being randomly changed to one of the other states or actions. Furthermore the initial action has a probability of being swapped of \(\delta\times 10^{-1}\) and the initial state has a probability of being changed to another random state of \(\delta \times 10^{-1} \times N\) (where \(N\) is the number of states).
Cycler Sequence Calculator¶
A Cycler Sequence is the sequence of C & D actions that are passed to the cycler player to follow when playing their tournament games.
the sequence is found using genetic feature selection:
- Crossover: By working with another cycler player, we take sections of each player and create a new cycler sequence
- from the following formula:
- let our two player being crossed be called p1 and p2 respectively. we then find the midpoint of both the sequences
- and take the first half from p1 and the second half from p2 to combine into the new cycler sequence.
- Mutation: we use a predictor :math:`delta`to determine if we are going to mutate a
single element in the current sequence. The element, or gene, we change in the sequence is uniformly selected using
the random package
.