Genetic_Algorithm
Abstract
With our final project in CIS 678 - Machine Learning, we implement a genetic algorithm (GA) to find the global min of two complex functions: Rosenbrock's Banana function and Goldstein-Price function. Using concepts similar to natural biology, we construct an algorithm that pinpoints with high accuracy the minimum values of various functions. Modeling the inputs to the functions as chromosomes, we select the most fit chromosomes. Using the most fit chromosomes, we breed a new population of children organisms using crossover. We then recursively repeat this strategy of choosing the most fit organisms, and breeding until our population converges to the most fit.
Implementation
Our program is written in Python 2.7 and bash scripting in Unix. These programs were executed locally on each member’s respective Macbook Pro (2012), testing on eos23 and okami. We implemented our program as a modular and highly parameterized Genetic Algorithm class. The genetic algorithm can be modified from the command line to any population size, number of chromosome bits, range values of the function of interest, number of inputs the function will receive, number of generations to evolve for, percent of parents to keep each generation, and any function. Using these inputs, we implement the following methods synonymous with natural evolution: populationEvaluation, populationSelection, populationVariation, populationUpdate, termination, evolveUntilTermination. Each organism in our initial population is a list of bits where the first number of bits represent the first input, the second portion of bits represent the second input etc. In order to encode each real number, input as a bit string, we first shift our real numbers to be all positive. Next, we scale our inputs based on the number of bits we have. Using this process, we can approximately represent the real numbers in our function range. Once we have encoded our initial population, we use the function passed to evaluate our population. Using the roulette wheel methodology, we select probabilistically choose the most fit chromosomes (bit strings). We then use crossover at random locations on all the encoded inputs of the bit string to produce children. Finally, we update our population with a percent of children and a percent of parents - then repeat a new generation. We continue to evolve until the number of generations we specified to evolve for has been reached.