Genetic Algorithm in Python

Genetic Algorithm in Python Data mining lab 6 When to use genetic algorithms John Holland (1975) ● Optimization: minimize (maximize) some function f(x) over all possible values of variables x in X ● A brute force: examining every possible combination of x in X in order to determine the element for which f is optimal: infeasible ● Optimization techniques are heuristic. ● The problem of local maximum (minimum). Mutation introduces randomness in the method to get out of trap Evolution ● There is a population of individuals with randomly chosen values of variables (features) ● There are some environmental conditions which demand from an individual to have certain features ● The individuals which have the features which are best suited

for these conditions have advantage over other individuals, they survive till the reproductive age and reproduce Variation – the pool for the evolution ● The best suited individuals (the fittest) survive, reproduce and mix their features with other surviving individuals ● In the simplest model, they contribute part of the features to a new individual in the next generation, and another part comes from a second parent ● The new individual can undergo the process of mutation – random change of one of his features. This occurs rarely. Genetic algorithm: the main steps I 1. Create population of random individuals 2. Choose fitness function: to evaluate how good is a particular individual for a specific purpose defined by a specific problem 3. Run several iterations (generations) elite Genetic algorithm: the main steps II 5. The next generation consists of: Unchanged elite (parthenogenesis) Individuals which combine features of 2 elite parents (recombinant) Small part of elite individuals changed by random mutation 6. Repeat steps 4, 5 until no more significant improvement in the fitness of elite is observed "Hello World" program for genetic algorithms ● Simple example: random population of strings evolves into a predefined template “Hello World” ● For simplicity: ● random strings have the same length as the target string ● Fitness function is calculated as the closeness of the given string to the target string Fitness function def string_fitness (individual): fitness=0 for ipos in range (0,target_length): fitness+=abs( ord(individual[ipos]) - ord (TARGET_STRING[ipos]) ) return fitness Basically, all this does it goes through each member of the population and compares it with the target string. It adds up the differences between the characters and uses the cumulative sum as the fitness value (therefore, the lower the value, the better). For comparison: random optimizer ● Random searching isn't a very good optimization method, but it makes it easy to understand exactly what all the algorithms are trying to do, and it also serves as a baseline so you can see if the other algorithms are doing a good job. ● The random optimizer in random_optimize.py randomly generates 202,800 random guesses and applies a fitness function for each guess. It keeps track of the best guess (the one with the lowest cost) and returns it. from ga_helloworld import * string_population=init_strings_population(204800) best_rand=randomoptimize( string_population, string_fitness ) print best_rand[1] print " score = %d" % best_rand[0] Mutation operation for GA def mutate_string(individual): ipos=random.randint(0,target_length-1) #mutation changes...

Website: webhome.cs.uvic.ca | Filesize: -
No of Page(s): 25
Download Genetic Algorithm in Python - This personal web page is new and ....pdf