evolvelab

Evolutionary computing lab. For evolutionary computing stuff and experiments.

The evolutionary algorithm

The algorithm is based on the evolution strategy framework, so there is only three main rules:

1. change all current solutions by adding a normally distributed random vector (variation operator).
2. merge the changed solutions with the original ones (offspring recruitment).
3. select only the set of best solutions (elitism).

Solutions are encoded in the integer format (i.e., a fixed searching grid). There is two options :

1. coarse grid: uint8 8 bit encoding, varying from 0 to 255.
2. fine grid: uint16 16 bit encoding, varying from 0 to 65535.

Solution decoding from gene to fenotype is performed by the following formula:

f = (g * (f_hi - f_lo) / g_hi) + f_lo

Where f in the fenotype (real number), g is the genotype (integer number), f_lo and f_hi are the lower and upper bounds of the searching range of the fenotype (real numbers), respectively; and g_hi is the upper value of the searching grid (255 or 65535).

The strength of the variation operator is defined by the standard deviation STD of the normally distributed random vector. The vector is computed in the genetype domain (i.e., in integer values). So the STD is computed from a rate parameter:

STD = integer(R_STD * N_GRID)

Where R_STD is a rate value (0 to 1) and N_GRID is the grid resolution, so N_GRID = g_hi.

The algorithm is designed both for optimization and exploration. When EXPLORE = TRUE, the procedure is set to find solutions within a certain range of the fitness score. When EXPLORE = FALSE, the procedure is set to find solution that maximize (or minimize) the fitness score.

The algoritm lives in the evolve() function of the evolution.py file. It is designed to optimize any number of decision variables. Custom objective functions can be further used.

The pseudo-code:

start
    get EXPLORE as boolean
    get N_POPSIZE as integer
    get N_GENERATIONS as integer
    get N_GRID as integer
    get R_STD as real
    set STD = R_STD * N_GRID as integer
    generate PARENTS as integer with POPSIZE
    evaluate PARENTS using FITNESS() function
    set g = 0
    repeat until g > GENERATIONS:
        set DELTA = NORMAL(mean=0, standard=STD) as integer
        set OFFSPRING = PARENTS + DELTA
        evaluate OFFSPRING using FITNESS() function
        merge OFFSPRING with PARENTS in POOL
        if EXPLORE == TRUE:
            sort POOL by exploration criteria
        else:
            sort POOL by fitness score
        select from POOL the best POPSIZE SAMPLE
        set PARENTS = SAMPLE
        set g = g + 1
    return PARENTS
end

Spoilers of the package - exploration in the Himmelblaus function:

benchmark 2d functions

the paraboloid function

Equation:

f(x, y) = level - (square(x - x0) + square(y - y0))

where level, x0 and y0 are pre-set parameters

Example of level=100, x0=5, y0=5:

the rastrigin 2d function

Equation:

f(x, y) = level - (20 + (square(x - x0) - 10 * cos(2 * pi * (x - x0))) + (square(y - y0) - 10 * cos(2 * pi * (y - y0))))

where level, x0 and y0 are pre-set parameters

Example of level=100, x0=5, y0=5:

the himmelblaus function

Equation:

f(x, y) = level - (square(square(x - x0) + (y - y0) - 11) + square((x - x0) + square(y - y0) - 7))

where level, x0 and y0 are pre-set parameters

Example of level=1000, x0=5, y0=5:

the griewank function

Equation:

f(x, y) = level - 100 * (((square(x) + square(y)) / 4000) - (cos(x) * cos(y / sqrt(2))) + 1)

where level, x0 and y0 are pre-set parameters

Example of level=100, x0=5, y0=5:

Results of fitting the 2D benchmark functions

Some experimental outputs for 2D (two decision variables).

Himmelblaus

Parameters: N_GEN=100, N_POPSIZE=100, R_STD=0.7

Convergence plot:

Retrieved scattergram (useful for uncertainty estimation)

Rastrigin

Parameters: N_GEN=100, N_POPSIZE=200, R_STD=0.4

Convergence plot:

Retrieved scattergram (useful for uncertainty estimation)

Parabola

Retrieved scattergram (useful for uncertainty estimation)

Griewank

Retrieved scattergram (useful for uncertainty estimation)

Results of fitting 8 decision variables

In this experiment, all four benchmark function where merged so the objective function was the average of each benchmark.

References

Beyer, HG., Schwefel, HP. Evolution strategies – A comprehensive introduction. Natural Computing 1, 3–52 (2002). https://doi.org/10.1023/A:1015059928466