Implementation of genetic algorithm to solve problem presented here: http://www.ai-junkie.com/ga/intro/gat3.html

geneticalgorithm1.py

#
# Genetic algorithm example from http://www.ai-junkie.com/ga/intro/gat1.html
#
# @author Natesh Narain
# @date July 9 2016

# Rule are encoded in the genes
# Long string of genes make up chromosomes

# Solution must have a way of being encoded into a chromosome

# General
#   1- Randomly generate a population of chromosomes
#   2- Test each chromosome for its ability to solve the given problem
#       - score chromosome with a fitness score
#   3- Select 2 member of the population based fitness score
#   4- Dependent on cross over rate: cross over the 2 chromosomes genes and a random point
#   5- Perform mutation on the chromosomes' genes
#   6- Repeat 3, 4, and 5 until desired population size

# Problem to solve:
# Given the digits 0 through 9 and the operators +, -, * and /,  find a sequence
# that will represent a given target number. The operators will be applied sequentially from left to right as you read.
#
# So, given the target number 23, the sequence 6+5*4/2+1 would be one possible solution.
#

# Encoding: 4 bits per gene
# 0:         0000
# 1:         0001
# 2:         0010
# 3:         0011
# 4:         0100
# 5:         0101
# 6:         0110
# 7:         0111
# 8:         1000
# 9:         1001
# +:         1010
# -:         1011
# *:         1100
# /:         1101

from argparse import ArgumentParser
from random import uniform as randf
from random import randint as randi
from random import seed
from datetime import datetime
from numpy.random import choice

parser = ArgumentParser()
parser.add_argument('-t', '--target', required=True, help='target value')
parser.add_argument('-c', '--crossover', default='0.7', type=float, help='Crossover rate. Defaults to 0.7')
parser.add_argument('-m', '--mutate', default='0.001', type=float, help='Mutation rate. Defaults to 0.001')
parser.add_argument('-p', '--population', default='10', type=int, help='Size of population. Defaults to 10, prefered even number')

args = vars(parser.parse_args())

target         = float(args['target'])
crossover_rate = float(args['crossover'])
mutation_rate  = float(args['mutate'])
population_size = int(args['population'])

genes_per_chromosome = 9

def main():
    print '-- target: %0.5f' % (target)
    print '-- crossover rate: %0.5f' % (crossover_rate)
    print '-- mutation rate: %0.5f' % (mutation_rate)
    print '-- population size: %d' % (population_size)
    print ''

    solution_found = False

    # seed random
    seed(datetime.now())

    # create a random population of size 10
    population = generate_population(10)
    num_generations = 0

    # evolve chromosomes until a solution has been found
    while not solution_found:
        # get the scores of each chromosome
        scores = []
        for chromosome in population:
            score, success = fitness(target, decode(chromosome))
            if success:
                expression = get_expression(chromosome)
                print '-- Found solution %s = %s' % (expression, eval(expression))
                solution_found = True
                break
            else:
                scores.append(score)
                pass

        # exit is solution was found
        if solution_found:
            break

        # evolve the population
        print '-- Evolving generation %d' % (num_generations)
        population = evolve(population, scores)
        num_generations += 1

def evolve(population, scores):
    new_population = []

    for i in range(len(population) / 2):
        # get 2 chromosomes from the population
        first, second = select_two(population, scores)

        # mate the pair
        chromosome1, chromosome2 = crossover(first, second, crossover_rate)

        # apply mutation to the chromosomes
        chromosome1 = mutate(chromosome1, mutation_rate)
        chromosome2 = mutate(chromosome2, mutation_rate)

        # add to the new population
        new_population.append(chromosome1)
        new_population.append(chromosome2)

    return new_population

def decode(chromosome):
    # break the chromosome into token for parsing
    expression = get_expression(chromosome)
    return eval(expression)

def get_expression(chromosome):
    tokens = tokenify(chromosome)
    return parse_expression(tokens)

def parse_expression(tokens):
    STATE_EXPECT_NUMBER = 0
    STATE_EXPECT_OPERATOR = 1

    expression = ''

    state = STATE_EXPECT_NUMBER

    for token in tokens:
        if state == STATE_EXPECT_NUMBER:
            if is_number(token):
                expression += token
                state = STATE_EXPECT_OPERATOR
        elif state == STATE_EXPECT_OPERATOR:
            if token in ['+', '-', '*', '/']:
                expression += token
                state = STATE_EXPECT_NUMBER
        else:
            pass

    # remove last element if it is an operator
    if expression[-1] in ['+', '-', '*', '/']:
        expression = expression[0:-1]

    # prevent devide by zero
    expression = expression.replace('/0', '/0.000001')

    return expression

def tokenify(chromosome):
    # break the chromosome into parsable tokens
    tokens = []
    for i in range(genes_per_chromosome - 1):
        gene = chromosome[(i*4):(i*4)+4]

        if int(gene, 2) <= 9:
            token = str(int(gene, 2))
            tokens.append(token)
        else:
            if gene == '1010':
                tokens.append('+')
            elif gene == '1011':
                tokens.append('-')
            elif gene == '1100':
                tokens.append('*')
            elif gene == '1101':
                tokens.append('/')
            else:
                tokens.append(None)
    return tokens

def generate_population(population_size):
    # Generate a random population by appending 4 bit bitstrings

    population = []
    for i in range(population_size):
        chromosome = ''
        for j in range(genes_per_chromosome):
            gene = format(randi(0,0x0f), '04b')
            chromosome += str(gene)
        population.append(chromosome)
    return population

def select_two(population, scores):
    # preserve the index with the value
    scores2 = []
    for i in range(len(scores)):
        scores2.append((scores[i], i))

    # sort decending by score value. The highest score comes first in list
    scores2 = sorted(scores2, key=lambda score: score[0], reverse=True)

    # list of indices to be selected from
    indices = []
    for score, index in scores2:
        indices.append(index)

    # create a list of weights. The first having the highest, second having half that, and so on
    weights = []
    weight = 0.5
    for i in range(len(scores2) - 2):
        weights.append(weight)
        weight /= 2
    # last 2 need to have the same weight
    weights.append(weight)
    weights.append(weight)

    # select 2 indices of chromosomes in the population, weighted by their score
    # This is so the most fit will be most likely to proceed through generations
    # While allowing less fit chromosomes to add variation
    first = choice(indices, p=weights)
    second = choice(indices, p=weights)

    # return the chromosomes
    return (population[first], population[second])

def mutate(chromosome, rate):
    # iterate through bits in the chromosome and randomly flip them
    c = list(chromosome)
    for i in range(len(c)):
        if rate_pass(rate):
            c[i] = str(int(c[i]) ^ 0x1)
    return "".join(c)

def crossover(chromosome1, chromosome2, rate):
    # swap bits in chromosomes after a randomly selected index

    c1 = list(chromosome1)
    c2 = list(chromosome2)

    if rate_pass(rate):
        # randomly select a point in the chromosome
        idx = randi(0, len(c1))

        # swap bits in the 2 chromosomes after the random index
        for i in range(idx, len(c1)):
            c1[i] = chromosome2[i]
            c2[i] = chromosome1[i]

        return ("".join(c1), "".join(c2))
    else:
        return (chromosome1, chromosome2)

def fitness(target, value):
    # score the value compared to target
    # better score approach infinite
    if value == target:
        return (-1, True)
    else:
        score = 1.0 / abs(value - target)
        return (score, False)

def rate_pass(rate):
    r = randf(0, 1)
    if r <= rate:
        return True
    else:
        return False

def is_number(s):
    try:
        float(s)
        return True
    except:
        return False

if __name__ == '__main__':
    main()