Happy New Year with a simple Genetic Algorithm

ga_naive.py

import numpy as np
import random
import sys

goal = 'All work and no play makes Jack a dull boy.'
idx2c = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890,. '
c2idx = { c : i for i,c in enumerate(idx2c) }

def encode(seq):
    return np.array([c2idx[c] for c in seq ])

def decode(seq):
    assert len(seq) == len(goal)
    try:
        decoded = ''.join( [idx2c[idx] for idx in seq] )
    except:
        return seq

    return decoded

def fitness(phrase):
    return (encode(goal) == phrase).sum()

def goal_test(phrase):
    return True if fitness(phrase) == len(goal) else False

def crossover(p0, p1):
    len_ = len(p1)
    l1, l2 = (len_//3) , 2*(len_//3) 
    # pieces
    p0, p1 = list(p0), list(p1)
    p0_ = [ p0[:l1], p0[l1:l2], p0[l2:] ]
    p1_ = [ p1[:l1], p1[l1:l2], p1[l2:] ]

    children = []
    children.append(p0_[0] + p0_[1] + p1_[2])
    children.append(p0_[0] + p1_[1] + p0_[2])
    children.append(p0_[0] + p1_[1] + p1_[2])
    children.append(p1_[0] + p0_[1] + p0_[2])
    children.append(p1_[0] + p0_[1] + p1_[2])
    children.append(p1_[0] + p1_[1] + p0_[2])

    return children

def new_pop(fit_parents):
    new_parents = []
    for i in range(len(fit_parents)):
        for j in range(len(fit_parents)):
            if i != j:
                new_parents.extend(crossover(fit_parents[i], fit_parents[j]))

    # add mutation here
    return np.array(mutate(new_parents))


def top_parents(pop):
    # calculate fitness
    pop_fitness = [ fitness(phrase) for phrase in pop ]
    # pick the top 1%
    best_parents_idx = np.array(pop_fitness).argsort()
    fit_parents = pop[best_parents_idx[::-1]][:20]

    return fit_parents

def mutate(pop, mut_num=2):
    mutated_pop = []
    for phrase in pop:
        idxs = [ random.choice(range(len(phrase))) for i in range(mut_num) ]
        chidxs  = [ random.choice(range(len(idx2c))) for i in range(mut_num) ]
        for i in range(mut_num):
            phrase[idxs[i]] = chidxs[i]
        mutated_pop.append(phrase)
    return mutated_pop



def create_population(n, seq_len):
    return np.random.randint(0,len(idx2c),[n, seq_len])

if __name__ == '__main__':
    # create a population of 10 phrases
    pop = create_population(1000, len(goal))
    # loop till goal
    i=0
    while True:
        i += 1
        # find top 1% fit parents
        fit_parents = top_parents(pop)
        sys.stdout.write('\rGeneration #' + str(i) + '\t' + decode(fit_parents[0]) )
        # goal test
        if goal_test(fit_parents[0]):
            print('\n______________________')
            print(':: Evolution complete!')
            print('::  Final product')
            print('\n' + decode(fit_parents[0]))
            print('______________________')
            break
        # find new population, using crossover
        pop = new_pop(fit_parents)