My first genetic algorithm

Chromosome.py

from random import random

def countBits(num):
  result = 0
  while num:
    result += 1
    num &= num - 1
  return result

def likelihood(probability):
  return random() < probability

class Chromosome:
  def __init__(self, numBits, *, genes = 0):
    self.n = numBits
    self.genes = genes

  @property
  def fitness(self):
    return countBits(self.genes)

  def mutate(self, probability = 0.1):
    result = self.genes
    for i in range(self.n):
      if likelihood(probability):
        result ^= 1 << i
    return Chromosome(self.n, genes=result)

  @staticmethod
  def crossover(parentA, parentB):
    mask = 0
    for i in range(parentA.n):
      if likelihood(0.5):
        mask |= 1 << i
    mask &= parentA.genes ^ parentB.genes

    childA = parentA.genes ^ mask
    childB = parentB.genes ^ mask

    return (
      Chromosome(parentA.n, genes=childA),
      Chromosome(parentA.n, genes=childB)
    )

  def __str__(self):
    return f'{self.genes:0{self.n}b}'

  def __lt__(self, other):
    return self.fitness < other.fitness

main.py

from Population import Population

bits = 6
n = 20

p = Population(n, numBits=bits)

print(p)
while True:
  input()
  p.selectAndBreed()
  print(p)

most-bits.md

Most Bits

I have been interested in genetic algorithms for a while, but as my programming chops were not so flash, reading the documentation about them or even knowing what to search was out of my scope. I have been getting better though, learning more algorithms and so I decided to try my hand at a genetic algorithm.

This genetic algorithm is an attempt at learning the basics, so I wanted to keep it farily simple. Each chromosome is just a sequence of bits, and the fitness of a chromosome is defined to be the number of set bits.

Using the quickselect algorithm, each generation is partitioned into (in average linear time):

• The fifth of the population with the lowest fitness;
• The fifth of the population with the highest fitness; and,
• The rest.

The strongest fifth will then breed with each other in pairs (by having their gene sequences spliced) and then their mutated children (doesn't sound very nice!) will then replace the weakest members of society.

This will repeat ad infinitum.

Results

I was very surprised to find that even with statistically small populations (n around 20~50), they still converged to mostly ones relatively quickly (within 50 generations), and the size of the population did not seem to have a large impact on the number of generations to convergence.

The number of bits seemed to make a difference, as populations with more genes were more succeptible to rampant mutation. The way I implemented it meant that each gene had the same probability to mutate, so chromosomes with more genes would mutate more then those with less genes. When the chromosomes were large enough, the mutation introduced enough noise that the population would be quite reluctant to converge.

The random mutation also helped to escape local maximums. I started some populations where every gene was 0; any direct crossover between any pair of chromosomes would not produce anything new, but the mutations would introduce a 1 at some point and it would quickly spread through the population.

Population.py

from Chromosome import Chromosome
from random import randrange

def quickselect(arr, target, left = None, right = None):
  lo = 0 if left == None else left
  hi = len(arr) if right == None else right

  def swap(i, j):
    arr[i], arr[j] = arr[j], arr[i]

  def partition(start, end):
    if start == end - 1:
      return start
    # choose random pivot
    pivot = randrange(start, end)
    swap(start, pivot)
    lo = start + 1
    hi = end - 1
    while lo < hi:
      while lo < hi and arr[lo] < arr[start]:
        lo += 1
      swap(lo, hi)
      while lo < hi and not arr[hi] < arr[start]:
        hi -= 1
      swap(lo, hi)

    pivot = lo - (1 if arr[start] < arr[lo] else 0)
    swap(start, pivot)
    return pivot

  while lo < hi:
    mid = partition(lo, hi)
    if mid < target:
      lo = mid + 1
    else:
      hi = mid - 1

class Population:
  def __init__(self, size, *, numBits = 6):
    self.members = [Chromosome(numBits).mutate(0) for _ in range(size)]

  def kFittest(self, k):
    quickselect(self.members, len(self.members) - k)
    return self.members[-k:]
  
  def selectAndBreed(self):
    n = len(self.members)
    tenth = n // 10
    # remove 1/5th of the members from the bottom
    quickselect(self.members, tenth * 2)
    # replace with offspring from the top 1/5th
    quickselect(self.members, n - 2 * tenth, tenth * 2)

    for i in range(0, 2 * tenth, 2):
      parentA = self.members[n - (i + 1) * 2]
      parantB = self.members[n - (i + 1) * 2 + 1]
      childA, childB = Chromosome.crossover(parentA, parantB)
      self.members[i] = childA.mutate()
      self.members[i + 1] = childB.mutate()
  
  def __str__(self):
    return '\n'.join(map(str, self.members))