func_evolution.py

# evolutionary algorithm vs algorithm with a first derivative

from math import *
import random

"""
1. Generate the initial population of individuals randomly. (First generation)

2. Evaluate the fitness of each individual in the population (time limit, sufficient fitness achieved, etc.)
3. Select the fittest individuals for reproduction. (Parents)
4. Breed new individuals through crossover and mutation operations to give birth to offspring.
5. Replace the least-fit individuals of the population with new individuals.
6. goto 2
"""

# we optimize simple data points towards a coordinate by random walks

VSIZE = 6
seed = random.seed
random = random.random
def nrandom():
    return random()*2.0 - 1.0

def nrandomvec():
    return [nrandom() for i in range(VSIZE)]

seed(12)
#target = nrandomvec()

def compute_fitness(v):
    err = 0.0
    for i in range(64):
        x = i / 63.0 * 2.0 - 1.0
        y = exp(x)
        t = v[0]
        for k in range(1, VSIZE):
            t = x * t + v[k]
        err += (y - t) ** 2.0
    return err
    # evaluate fitness - lower is better
    #return sum([(v[i] - target[i])**2.0 for i in range(VSIZE)])

def mix(a, b, x):
    return a * (1 - x) + b * x

def mixmut(a, b, d, best_err):
    # weighed center between points
    c = mix(a, b, d)
    r = abs(a - b)
    # pick a point
    return c + r * 2.0 * nrandom()

def citizen(v):
    return (v, compute_fitness(v))

def breed(a, b, d):
    f_a = a[1]
    f_b = b[1]
    best = min(f_a, f_b)
    return citizen([mixmut(a[0][i], b[0][i], d, best) for i in range(VSIZE)])

POPSIZE = 128 # size of total population
CHILDSIZE = 1 # how many children per pairing
REPOPSIZE = int(0.5*((4.0*POPSIZE + 1.0)**0.5 + 1.0) / CHILDSIZE) # how many to breed with; we get N*(N-1)/2 new versions
CHILDCOUNT = CHILDSIZE * REPOPSIZE * (REPOPSIZE - 1) // 2 # how many children we'll get
assert(CHILDCOUNT <= POPSIZE)

population = [citizen(nrandomvec()) for i in range(POPSIZE)]
def print_stats():
    # assuming population has been sorted
    print("best specimen:",population[0][1],"worst specimen:",population[-1][1])

population.sort(key = lambda c: c[1])
print_stats()

for stp in range(1000):
    # cross breed
    newpop = []
    for i in range(REPOPSIZE):
        for j in range(i+1,REPOPSIZE):
            newpop.append(breed(population[i], population[j], 0.5))
            #newpop.append(breed(population[i], population[j], 0.0 - 1.5))
            #newpop.append(breed(population[i], population[j], 1.0 + 1.5))
    # append previous fittest solutions
    assert(len(newpop) <= len(population))
    newpop = newpop + population[:len(population) - len(newpop)]
    population = newpop
    assert(len(population) == POPSIZE)
    population.sort(key = lambda c: c[1])
    if stp % 1000 == 0:
        print_stats()
print_stats()
print("population size:",POPSIZE,"top fittest:",REPOPSIZE,"replaced:",CHILDCOUNT)
print("winner precision:",population[0][1])
print("winner solution:",population[0][0])
f = population[0][0]
s = str(f[0])
for k in range(1, VSIZE):
    s = "(x*" + s + "+" + str(f[k]) + ")"
print(s)