genetic_algorithm.py

SIMO metaheuristic genetic algorithm

>>> epsilon = 0.00001
>>> import numpy as np

class GeneticAlgorithm(Optimizer):

Genetic algorithm heuristic implementation. Example keyword arguments

repeats=10
initial_solutions=100
maximum_iterations=1000
initial_population=100

def __init__(self, logger, logname, optlogger, taskdef, simdbin, opdbin, simdbout, opdbout, **keywords):

Initialize optimizer:

>>> from simo.optimization.genetic_algorithm import GeneticAlgorithm
>>> execfile('optimization/test/mocks4optimizer.py')
>>> chart_path = 'optimization/test'

>>> ga = GeneticAlgorithm(
...     logger, logname, taskdef, simdbin, simdbout, False, False, False,
...     chart_path, True, 'test', True, keyword1='test-kw')
Called Logger.log_message(
    'optimization-test',
    'ERROR',
    'Parameter "repeats" missing!')
Called Logger.log_message(
    'optimization-test',
    'ERROR',
    'Parameter "maximum_iterations" missing!')
Called Logger.log_message(
    'optimization-test',
    'ERROR',
    'Parameter "population_size" missing!')
Called Logger.log_message(
    'optimization-test',
    'ERROR',
    'Parameter "breeding_rate" missing!')
Called Logger.log_message(
    'optimization-test',
    'ERROR',
    'Parameter "mutation_probability" missing!')
Called Logger.log_message(
    'optimization-test',
    'ERROR',
    'Parameter "swapping_probability" missing!')

>>> ga = GeneticAlgorithm(
...     logger, logname, taskdef, simdbin, simdbout, False, False, False,
...     chart_path,
...     True, 'test', True,
...     repeats=2,
...     maximum_iterations=20,
...     population_size=10,
...     breeding_rate=2.0,
...     mutation_probability=0.3,
...     swapping_probability=0.5)
>>> ga._stat_logger = ologger  # replace stat logger with a mock
>>> ga._data = omatrix2  # replace data handler with a mock
>>> ga._analyze_data()  
Called OMatrix.analyze_data(
    <Mock ... SimInputDB>,
    <bound method GeneticAlgorithm._add_info of
    <simo.optimization.genetic_algorithm.GeneticAlgorithm object at ...>>)
True
>>> ga.set_data(0)  
Called OMatrix.construct_data(0)
True

def _sort_by_fitness(self, population):

Sort a population by the fitness of individuals, best first

Parameters

population -- population to be sorted as a list of (fitness, individual)
              tuples, where fitness is given as a float and individual as
              a Numpy array

>>> mypop = [(3,1),(1,9),(7,0),(0,6),(5,2)]
>>> ga._sort_by_fitness(mypop)
>>> mypop
[(7, 0), (5, 2), (3, 1), (1, 9), (0, 6)]

def _populate(self):

Generate a population from scratch

>>> population = ga._populate() 
Called Logger.log_message(
    'optimization-test',
    'INFO',
    '  generating initial population...')
Called OMatrix.get_random_solution()
Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0]))
Called OMatrix.solution_utility(array([0, 0, 0, 0, 0]))
Called OMatrix.get_random_solution()
Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0]))
Called OMatrix.solution_utility(array([0, 0, 0, 0, 0]))
Called OMatrix.get_random_solution()
Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0]))
Called OMatrix.solution_utility(array([0, 0, 0, 0, 0]))
Called OMatrix.get_random_solution()
Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0]))
Called OMatrix.solution_utility(array([0, 0, 0, 0, 0]))
Called OMatrix.get_random_solution()
Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0]))
Called OMatrix.solution_utility(array([0, 0, 0, 0, 0]))
Called OMatrix.get_random_solution()
Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0]))
Called OMatrix.solution_utility(array([0, 0, 0, 0, 0]))
Called OMatrix.get_random_solution()
Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0]))
Called OMatrix.solution_utility(array([0, 0, 0, 0, 0]))
Called OMatrix.get_random_solution()
Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0]))
Called OMatrix.solution_utility(array([0, 0, 0, 0, 0]))
Called OMatrix.get_random_solution()
Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0]))
Called OMatrix.solution_utility(array([0, 0, 0, 0, 0]))
Called OMatrix.get_random_solution()
Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0]))
Called OMatrix.solution_utility(array([0, 0, 0, 0, 0]))
Called Logger.log_message(
    'optimization-test',
    'INFO',
    '  initial population of 10 individuals found in ... secs')

>> raise self.failureException(self.format_failure(<StringIO.StringIO instance at 0x104419b00>.getvalue()))

Traceback (most recent call last):

File “/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/doctest.py”, line 2201, in runTest

raise self.failureException(self.format_failure(new.getvalue()))

AssertionError: Failed doctest test for optimizer-py.rst

File “/Users/Jussi/Firma/SIMO/src/simo/optimization/test/optimizer-py.rst”, line 0

opt._generate_random_solution(2) +ELLIPSIS

Exception raised:

Traceback (most recent call last):

File “/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/doctest.py”, line 1289, in __run

compileflags, 1) in test.globs

File “<doctest optimizer-py.rst[29]>”, line 1, in <module>

opt._generate_random_solution(2) +ELLIPSIS

NameError: name ‘ELLIPSIS’ is not defined

>> raise self.failureException(self.format_failure(<StringIO.StringIO instance at 0x1049ea4d0>.getvalue()))

FAILED (failures=2) Jussi@tilde ~/F/SIMO> bin/test F. ====================================================================== FAIL: Doctest: genetic_algorithm-py.rst ———————————————————————- Traceback (most recent call last):

File “/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/doctest.py”, line 2201, in runTest

raise self.failureException(self.format_failure(new.getvalue()))

AssertionError: Failed doctest test for genetic_algorithm-py.rst

File “/Users/Jussi/Firma/SIMO/src/simo/optimization/test/genetic_algorithm-py.rst”, line 0

population = ga._populate()

Expected:

Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0]))

Got:

Called Logger.log_message(

‘optimization-test’, ‘INFO’, ‘ generating initial population...’)

Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called Logger.log_message(

‘optimization-test’, ‘INFO’, ‘ initial population of 10 individuals found in 0.0 secs’)

ga._run_GA() # doctest: +ELLIPSIS +NORMALIZE_WHITESPACE

Expected:

Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() ...

Got:

Called Logger.log_message(

‘optimization-test’, ‘INFO’, ‘ generating initial population...’)

Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called OMatrix.get_random_solution() Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_utility(array([0, 0, 0, 0, 0])) Called Logger.log_message(

‘optimization-test’, ‘INFO’, ‘ initial population of 10 individuals found in 0.0 secs’)

Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0])) Called OMatrix.solution_feasibility(array([0, 0, 0, 1, 0])) Called OMatrix.solution_feasibility(array([0, 0, 1, 0, 0])) Called OMatrix.solution_feasibility(array([0, 0, 0, 1, 0]))

Make sure that the order of the individuals is based on the fitness

>>> for i in range(1, 10): population[i][0] <= population[i-1][0]
True
True
True
True
True
True
True
True
True

def _mutate(self, p, individual):

Mutate (randomly change treatment) a proportion p of the genes of given individual

Parameters:

p -- mutation probability
individual -- individual (solution) as numpy array

>>> individual = population[0][1]
>>> mutated = ga._mutate(0.3, individual)  
Called OMatrix.solution_feasibility(array(...))
>>> sum(mutated != individual)
1
>>> mutated = ga._mutate(0.5, individual)  
Called OMatrix.solution_feasibility(array(...))
>>> sum(mutated != individual)
2

def _np_crossover(self, n, parent1, parent2):

Do n point crossover for two individuals

Parameters:

n -- number of split points
parent1 -- parent individual
parent2 -- parent individual


>>> parent1 = np.ones(ga._num_of_units, dtype=int)
>>> parent2 = np.zeros(ga._num_of_units, dtype=int)

Do a one point crossover

>>> c1, c2 = ga._np_crossover(1, parent1, parent2)  
Called OMatrix.solution_feasibility(array(...))
Called OMatrix.solution_feasibility(array(...))
>>> np.any(c1 == 1) and np.any(c1 == 0)
True
>>> np.any(c2 == 1) and np.any(c2 == 0)
True
>>> c1 != c2
array([ True,  True,  True,  True,  True], dtype=bool)
>>> c1 + c2
array([1, 1, 1, 1, 1])

Do a two point crossover

>>> c1, c2 = ga._np_crossover(2, parent1, parent2)  
Called OMatrix.solution_feasibility(array(...))
Called OMatrix.solution_feasibility(array(...))
>>> np.any(c1 == 1) and np.any(c1 == 0)
True
>>> np.any(c2 == 1) and np.any(c2 == 0)
True
>>> c1 != c2
array([ True,  True,  True,  True,  True], dtype=bool)
>>> c1 + c2
array([1, 1, 1, 1, 1])

Do a three point crossover

>>> c1, c2 = ga._np_crossover(3, parent1, parent2)  
Called OMatrix.solution_feasibility(array(...))
Called OMatrix.solution_feasibility(array(...))
>>> np.any(c1 == 1) and np.any(c1 == 0)
True
>>> np.any(c2 == 1) and np.any(c2 == 0)
True
>>> c1 != c2
array([ True,  True,  True,  True,  True], dtype=bool)
>>> c1 + c2
array([1, 1, 1, 1, 1])

def _unif_crossover(self, p, parent1, parent2):

Do uniform crossover for two individuals

Parameters:

p -- swapping probability
parent1 -- parent individual
parent2 -- parent individual

>>> parent1 = np.ones(ga._num_of_units, dtype=int)
>>> parent2 = np.zeros(ga._num_of_units, dtype=int)
>>> p = 0.5
>>> c1, c2 = ga._unif_crossover(p, parent1, parent2)  
Called OMatrix.solution_feasibility(array([...]))
Called OMatrix.solution_feasibility(array([...]))
>>> c1 != c2
array([ True,  True,  True,  True,  True], dtype=bool)
>>> c1 + c2
array([1, 1, 1, 1, 1])

def _breed(self, population):

Breed a new generation of individuals from a parent population

Parameters:

population -- list of (fitness, individual) pairs

>>> population = ga._breed(population)  
Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0]))
Called OMatrix.solution_feasibility(array([0, 0, 0, 0, 0]))
...
>>> len(population)
30

def optimize(self):

Run genetic algorithm

def _run_GA(self):

Run GA algorithm for a single iteration/repeat

Parameters:

iteration -- current simulated iteration as int

>>> ga._run_GA()  
Called Logger.log_message(
    'optimization-test',
    'INFO',
    '  generating initial population...')
...
Called Logger.log_message(
    'optimization-test',
    'INFO',
    '  initial population of 10 individuals found in ... secs')
...
Called Logger.log_message(
    'optimization-test',
    'INFO',
    '  1. generation bred in ... secs, utility = 1.000')
...
Called Logger.log_message(
    'optimization-test',
    'INFO',
    '  20. generation bred in ... secs, utility = 1.000')