Introduction

Definition (Evolution)

Evolution is a process that acts on populations of individuals. Information is stored in the form of chromosomes with each chromosome containing many genes. In an EA

• A population of candidate solutions is formed (randomly)
• Each individual is evaluated (decode their information/chromosomes then evaluated) and assigned a fitness score based on performance.
• New individuals are formed through the process of selection, crossover, and mutation
• Repeat until a new population is formed.
• Once new population is formed we check if we’ve met our termination condition, if not start the whole process again.

Definition (Chromosome)

In a genetic algorithm, a chromosome encodes the information of an individual in a population. These are typically represented using a string of digits usually binary.

Definition (Phenotype)

In Genetic Algorithms, we use to represent information of an individual. This is mapped into the phenotype space to represent the encoded information of the genotype in its functional or physical form. Can think of phenotype as the decoded representation of genotype of chromosome. We evaluate fitness based on phenotype representation.

Definition (Binary Encoding)

In this encoding scheme we define the alphabet or alleles to be $0$ or $1$.

Definition (Messy encoding)

In messy encoding we generate a less position-dependent representation by associating each gene with a number (i.e. its position). For a example a Chromosome or Genotype of length $m$ $$c=((p_{1},g_{p1}),(p_{2},g_{p2}),\ldots,(p_{m},g_{pm}))$$with $p_{j}$ indicating the position in the chromosome and $g_{pj}$ being the corresponding allele.

Definition (Real number encoding)

In this application a gene $g$ holds a floating point number in the range $[0,1]$ from which the corresponding variable is obtained as $x\in[-d,d]$ formed with $$x=-d+2dg$$

Definition (Selection)

Selection is the process that takes in the individuals of a population and based on their fitness selects the individuals to produce offspring.

Definition (Roulette-wheel selection)

Roulette-wheel defines a cumulative relative fitness value, $\phi_{j}$, for each individual $j$ as $$\phi_{j}=\frac{\sum\limits_{i=1}^{j}F_{i}}{\sum\limits_{i=1}^{N}F_{i}}, \ j=1,\ldots,N$$where each $F_{i}$ is the fitness of individual $i$. Next a random number $r$ is drawn and the selected individual is the taken as the one with the smallest $j$ that satisfies $\phi_{j}>r$.

Definition (Tournament selection)

This method consists of picking two individuals randomly (i.e. with equal probability for all individuals) from the population, and then selecting the one with higher fitness with probability $p_{tour}\approx0,7-0.8$, which we define as the tournament selection parameter. We draw a random number $r\in[0,1]$ and if $r<p_{tour}$ we select the better of the two, otherwise we select the worse of the two.

Definition (Fitness ranking)

Here we give the best individual fitness $N$ (the population size) and continue in decreasing order to the worse individual with fitness $1$. Let $R(i)$ denote the ranking of individual $i$, defined such that the best individual $i_{best}$ has ranking $R(i_{best})=1$, the fitness values are obtained like so: $$F_{i}^{rank}=N+1-R(i)$$

Definition (Crossover)

This is where two of selected offspring “breed”. There are two types:

In single-point crossover a single crossover point is selected and the two children are formed from the spliced chromosomes of their parents which are both separated and attached at that point In $k$ point crossover, $k$ crossover points are selected randomly and the the chromosome parts are chosen from either parent with equal probability.

In averaging crossover, a gene $g$ in the offspring taking values $g_{1}$ and $g_{2}$ in two parents takes the values $$g_{1}\leftarrow\alpha g_{1}+(1-\alpha)g_{2}$$ $$g_{2}\leftarrow(1-\alpha)g_{1}+\alpha g_{2}$$ $\alpha\in[0,1]$

Definition (Mutation)

Mutations are carried out on a gene-by-gene basis. Thus, in principle, the number of mutated genes can range from $0$ to $m$. We define the mutation probability as $p_{mut}$ which is typically set as $\frac{c}{m}$ where $c$ is a constant of order $1$ and $m$ is the length.

Definition (Boltzmann Selection)

️️️️️️️In this method we define the notion of temperature $T$ as a tuneable parameter for determining selection pressure. This notion of selection pressure is the extent to which high-fitness individuals are preferred over low-fitness ones.