^

Genetic Algorithms

Genetic Algorithm

  1. GA(Fitness, Fitness-threshold, $p, r, m$)
  2. Initialize: $P \leftarrow p$ random hypotheses.
  3. Evaluate: for each $h$ in $P$, compute $Fitness(h)$
  4. While [$max_{h}$ Fitness(h)] < Fitness-threshold do
    1. Select: Probabilistically select $(1-r)p$ members of $P$ to add to $P_{S}$, select each $h_i$ with probability \[ \Pr(h_{i}) = \frac{Fitness(h_{i})}{\sum_{j=1}^{p} Fitness(h_{j})} \]
    2. Crossover: Probabilistically select $\frac{r \cdot p}{2}$ pairs of hypotheses from $P$. For each pair, $\langle h_{1}, h_{2} \rangle$, produce two offspring by applying the Crossover operator. Add all offspring to $P_{s}$.
    3. Mutate: Invert a randomly selected bit in $m\cdot p$ random members of $P_{s}$. $m$ is the mutation rate.
    4. Update: $P \leftarrow P_{s}$
    5. Evaluate: for each $h$ in $P$, compute $Fitness(h)$
  5. Return the hypothesis from $P$ that has the highest fitness.

José M. Vidal .

2 of 18