Differential Evolution (short teach version without comments)

de.py

#!/usr/bin/env python
import numpy.random as random

def de_population(pmin,pmax,np):
    """Create a population of np randomly distributed sets of floating point
    parameters whose elements are uniformly distributed between the values
    in the array pmin and the values in pmax. Return a list of np of these
    arrays.

    pmin - minimum parameter values
    pmax - maximum parameter values
    np - population size

    returns a list of np sets of parameters each with the same number of
    elements as pmin and pmax."""
    if len(pmin)!=len(pmax):
        raise IndexError('Minimum and maximum parameter ranges have differing lengths.')

    result = []
    for i in range(np):
        params = [l+random.random_sample()*(h-l) for l,h in zip(pmin,pmax)]
        result.append(params)

    return result

def de_iterate(hfunc,population,f,cr,iterations,args=()):
    """Iterate through the differential evolution algorithm for "iterations"
    generations using the population of parameters given by "population". The
    optimization function hfunc should accept a list of parameters as the first
    argument and may accept other arguments as well which will be passed from
    the optional argument args. After all the iterations the function will
    return a tuple of length two. The first element of the tuple will be the
    updated population of parameters, the second will be a list containing the
    value returned by hfunc for the corresponding parameter set.

    hfunc - optimization function which should return a value to be minimized
    for each set of parameters. It can also accept other arguments which will
    be passed from the args tuple.

    population - a list of np lists of parameters.

    f - The weighting factor f in the differential evolution algorithm.

    cr - The crossover constant in the differential evolution algorithmm.

    iterations - The number of iterations to perform. One iteration involves a
    single pass through every member of the population.

    args - A tuple containing additional arguments to pass to hfunc."""

    nextpopulation = [sol for sol in population]

    heval = [hfunc(sol,*args) for sol in population]
    nextheval = [eva for eva in heval]

    np = len(population)
    d = len(population[0])

    for i in range(iterations):
        for j in range(np):
            a=b=c=j
            while a==j:
                a = random.randint(np)
            while b==j or b==a:
                b = random.randint(np)
            while c==j or c==a or c==b:
                c = random.randint(np)

            s = random.randint(d)
            l = 1
            r = random.random_sample()
            while r<cr and l<d:
                l+=1
                r = random.random_sample()

            newsol = population[j][:]
            for k in range(s,s+l):
                newsol[k%d] = population[a][k%d]+f*(population[b][k%d]-population[c][k%d])

            hfunc_result = hfunc(newsol,*args)
            if hfunc_result<heval[j]:
                nextpopulation[j] = newsol
                nextheval[j] = hfunc_result
            else:
                nextpopulation[j] = population[j]
                nextheval[j] = heval[j]

        temp = population
        population = nextpopulation
        nextpopulation = temp

        temp = heval
        heval = nextheval
        nextheval = temp

    return (population,heval)

def f(p):
    return (5.0-p[0])**2+(2.0-p[1])**2

if __name__=='__main__':
    print "Testing Differential Evolution"
    print "Sould get 5.0,2.0 back."

    pmin = [0.0,0.0]
    pmax = [10.0,10.0]

    initial_population = de_population(pmin,pmax,20)

    res_population, hvalues = de_iterate(f,initial_population,0.8,0.9,100)

    all_yall = zip(res_population,hvalues)

    for t in all_yall:
        print t[0],t[1]