genetic algorithms are fun

genetic1.py

#!/usr/bin/env pypy
"""
See https://news.ycombinator.com/item?id=3789904

Google Cache'd version of article: https://webcache.googleusercontent.com/search?q=cache:JBfk95WBF2kJ:www.generation5.org/content/2003/gahelloworld.asp+&cd=1&hl=en&ct=clnk&gl=us

Port of C++ code in that: https://webcache.googleusercontent.com/search?q=cache:MurkRHQVoO0J:www.generation5.org/content/2003/data/gahelloworld.cpp&hl=en&gl=us&strip=1
"""
import random
import string

TARGET = "Hello world!"
TARGETLEN = len(TARGET)
POPSIZE = 2048
MAXITER = 16384
ELITRATE = 0.01
MUTATIONRATE = 0.5

CHARS = tuple(string.letters + string.digits + string.punctuation + string.whitespace)

def init_population():
    return [
        dict(
            fitness=None,
            item=''.join([random.choice(CHARS) for __ in range(TARGETLEN)])
        ) for _ in range(POPSIZE)
    ]

def calc_fitness(population):
    """
    Calculate the fitness of each member of the population, storing it
    in the `fitness` key of the member dictionary.

    `fitness` in our case is the cumulative 'distance' between the string
    and the target string (sum of how far each char is in ASCII code points
    from the target string's char at that position)
    """
    for member in population:
        member['fitness'] = sum(map(lambda a,b: abs(ord(a) - ord(b)), member['item'], TARGET))

def mutate(child):
    """
    Given a member object, replace one char (selected at random) with a new
    random char.
    """
    random_pos = random.randint(0, TARGETLEN-1)
    new_chr = random.choice(CHARS)

    new_str = child['item']
    new_str = list(new_str)
    new_str[random_pos] = new_chr
    new_str = ''.join(new_str)

    child['item'] = new_str
    return child

def mate(population):
    """
    Everything above ELITERATE will breed (default top 10%) and the others (90%)
    will be replaced with children of the "elite" members.
    """
    elitism_size = int(POPSIZE * ELITRATE)
    for i, member in enumerate(population[elitism_size:]):
        i1 = random.choice(population[:elitism_size])
        i2 = random.choice(population[:elitism_size])
        splitat = random.randint(0, TARGETLEN-1)

        # Child will be i1[:splitat] + i2[splitat:]
        child = dict(
            fitness=None,
            item="%s%s" % (
                i1['item'][:splitat],
                i2['item'][splitat:]
            )
        )

        # (1 / MUTATIONRATE) children will get a random char mutation
        if (random.random() < MUTATIONRATE):
            child = mutate(child)

        # Actually replace member in the population list. Remember to use
        # i+elitism_size since we are starting to count from the 10% index
        # onward. (Otherwise, we accidentally nuke the top 10% good stuff.)
        population[i+elitism_size] = child


def main():
    population = init_population()
    for i in range(MAXITER):
        # Calculate fitness for each member of the population and sort from
        # most fit to least.
        calc_fitness(population)
        population.sort(
            key=lambda item: item['fitness'],
            reverse=False
        )

        # Print current population's best member.
        print "%4d: %3d\t%s" % (
            i,
            population[0]['fitness'],
            population[0]['item'].replace("\n", "\\n")
        )

        if population[0]['item'] == TARGET:
            print population[0]['item']
            break

        # Not done yet, so breed the top 10% into the other 90% (with mutation)
        # and we'll try again.
        mate(population)


if __name__ == "__main__":
    main()

mtigas % ./1.py
   0: 189   GuhP{p^ovnq%
   1: 124   Jgbxt'iEdaa#
   2:  75   C^ikm-|r]t]!
   3:  63   J^biw!vewaa#
   4:  50   Bfiim!|n~lr#
   5:  44   Dbjno&zljo["
   6:  29   Jgskm!ynykb"
   7:  24   Hbllw!voqma'
   8:  24   Hbllw!voqma'
   9:  17   Hblls!vqpmf"
  10:  17   Hblls!vqpmf"
  11:  12   Hemkm wsrlf#
  12:  11   Hello$vnskf"
  13:  11   Hello$vnskf"
  14:   9   Jfjlo worlf#
  15:   9   Jfjlo worlf#
  16:   8   Hcmlm wopld"
  17:   7   Gemlo workf#
  18:   6   Gelln!vosld"
  19:   6   Gelln!vosld"
  20:   4   Hello!voslc!
  21:   3   Gello!wprld!
  22:   3   Gello!wprld!
  23:   3   Gello!wprld!
  24:   2   Hello vorkd!
  25:   2   Hello vorkd!
  26:   2   Hello vorkd!
  27:   2   Hello vorkd!
  28:   2   Hello vorkd!
  29:   2   Hello vorkd!
  30:   1   Hello!world!
  31:   1   Hello!world!
  32:   1   Hello!world!
  33:   1   Hello!world!
  34:   1   Hello!world!
  35:   0   Hello world!