Project Euler 461 - Genetic Algorithm

361 views Asked by At

Someone told me that this problem should be easy to solve with a genetic algorithm.

I read some stuff about this topic (I hadn't heard about it before), and wrote (and copied) some code.
The results I get are close to optimum, but not close enough.

I'd like to have some help with it:

import time
import math
import random

def f(n, k):
    return math.exp(k / n) - 1

def individual(length, min, max):
    'Create a member of the population.'
    return [random.randint(min, max) for x in range(length)]

def population(count, length, min, max):
    """
    Create a number of individuals (i.e. a population).

    count: the number of individuals in the population
    length: the number of values per individual
    min: the minimum possible value in an individual's list of values
    max: the maximum possible value in an individual's list of values

    """
    return [individual(length, min, max) for x in range(count)]

def fitness(individual, target):
    def get_best_last_element(a, b, c):
        s = math.pi - f(eu461.BASE, a) - f(eu461.BASE, b) - f(eu461.BASE, c)
        s += 1

        if s > 1:
            return round(math.log(s) * eu461.BASE)
        else:
            return 0

    def getg():
        return get_best_last_element
    """
    Determine the fitness of an individual. Higher is better.

    individual: the individual to evaluate
    target: the target number individuals are aiming for
    """
    l = get_best_last_element(individual[0], individual[1], individual[2])

    return abs(target - sum([f(eu461.BASE, k) for k in individual]) - f(eu461.BASE, l))

def grade(pop, target):
    'Find average fitness for a population.'
    return sum([fitness(x, target) for x in pop]) / (len(pop))

def evolve(pop, target, retain=0.2, random_select=0.05, mutate=0.01):
    graded = [(fitness(x, target), x) for x in pop]
    graded = [x[1] for x in sorted(graded)]

    retain_length = int(len(graded) * retain)
    parents = graded[:retain_length]

    # randomly add other individuals to
    # promote genetic diversity
    for individual in graded[retain_length:]:
        if random_select > random.random():
            parents.append(individual)

    # mutate some individuals
    for individual in parents:
        if mutate > random.random():
            pos_to_mutate = random.randint(0, len(individual) - 1)

            # this mutation is not ideal, because it
            # restricts the range of possible values,
            # but the function is unaware of the min/max
            # values used to create the individuals,
            individual[pos_to_mutate] = random.randint(min(individual), max(individual))

    # crossover parents to create children
    parents_length = len(parents)
    desired_length = len(pop) - parents_length
    children = []
    while len(children) < desired_length:
        male = random.randint(0, parents_length - 1)
        female = random.randint(0, parents_length - 1)
        if male != female:
            male = parents[male]
            female = parents[female]
            half = len(male) // 2
            if random.randint(0, 1):
                child = male[:half] + female[half:]
            else:
                child = female[:half] + male[half:]
            children.append(child)
    parents.extend(children)

    return parents

def get_best_last_element(a, b, c):
    s = math.pi - f(eu461.BASE, a) - f(eu461.BASE, b) - f(eu461.BASE, c)
    s += 1

    if s > 0:
        return round(math.log(s) * eu461.BASE)
    else:
        return 0

def eu461():
    target = math.pi
    p_count = 10000
    i_length = 3
    i_min = 0
    i_max = round(eu461.BASE * math.log(math.pi + 1))

    p = population(p_count, i_length, i_min, i_max)
    fitness_history = [grade(p, target),]

    for i in range(150):
        p = evolve(p, target)
        fitness_history.append(grade(p, target))

    for datum in fitness_history:
        pass #print (datum)

    return p[0], get_best_last_element(p[0][0], p[0][1], p[0][2]), sum([f(eu461.BASE, k) for k in p[0]]) + f(eu461.BASE, get_best_last_element(p[0][0], p[0][1], p[0][2]))
eu461.BASE = 200

if __name__ == "__main__":
    startTime = time.clock()
    print (eu461())
    elapsedTime = time.clock() - startTime
    print ("Time spent in (", __name__, ") is: ", elapsedTime, " sec")
0

There are 0 answers