.. _genetic_algorithm-py: #################### 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() # doctest: +ELLIPSIS +NORMALIZE_WHITESPACE Called OMatrix.analyze_data( , >) True >>> ga.set_data(0) # doctest: +ELLIPSIS +NORMALIZE_WHITESPACE 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() # doctest: +ELLIPSIS 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(.getvalue())) ====================================================================== FAIL: Doctest: optimizer-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 optimizer-py.rst File "/Users/Jussi/Firma/SIMO/src/simo/optimization/test/optimizer-py.rst", line 0 ---------------------------------------------------------------------- File "/Users/Jussi/Firma/SIMO/src/simo/optimization/test/optimizer-py.rst", line 136, in optimizer-py.rst Failed example: 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 "", line 1, in opt._generate_random_solution(2) +ELLIPSIS NameError: name 'ELLIPSIS' is not defined >> raise self.failureException(self.format_failure(.getvalue())) ---------------------------------------------------------------------- Ran 2 tests in 0.622s 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 ---------------------------------------------------------------------- File "/Users/Jussi/Firma/SIMO/src/simo/optimization/test/genetic_algorithm-py.rst", line 111, in genetic_algorithm-py.rst Failed example: 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') ---------------------------------------------------------------------- File "/Users/Jussi/Firma/SIMO/src/simo/optimization/test/genetic_algorithm-py.rst", line 301, in genetic_algorithm-py.rst Failed example: 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) # doctest: +ELLIPSIS Called OMatrix.solution_feasibility(array(...)) >>> sum(mutated != individual) 1 >>> mutated = ga._mutate(0.5, individual) # doctest: +ELLIPSIS 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) # doctest: +ELLIPSIS 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) # doctest: +ELLIPSIS 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) # doctest: +ELLIPSIS 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) # doctest: +ELLIPSIS 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) # doctest: +ELLIPSIS +NORMALIZE_WHITESPACE 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() # doctest: +ELLIPSIS +NORMALIZE_WHITESPACE 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')