These are projects posted by the students of Dr. Gove Allen at Brigham Young University. These students have taken one semester-long course on VBA and generally have had no prior programming experience

Wednesday, April 11, 2012

Gavin Gee Genetic Algorithm

This project returns to the traveling salesman problem done in class during the semester. In class we solved the problem by calculating the next nearest city. This solution solves the same problem by using a different technic called a genetic algorithm. Genetic algorithms are excellent for solving problems that require too many computations to solve directly. As the Traveling Salesman Problem (TSP) has 36! potential solutions, a genetic algorithm is perfectly situated to solve it. The idea behind the genetic algorithm is to find a solution using natural selection or "survival of the fittest" in a random population of genomes (or potential solutions). In each generation the best genomes are found and selected to perpetuate their characteristics onto the next generation until ultimately the ultimate genome has been created. Since the genetic algorithm by its nature is based on a random sample and the evolution of the genomes is also random the end solution is not always the same. Although the solution has a range of outcomes between 2800 to 5000, over 86% of the outcomes are better than the next nearest city solution. To guarantee a solution that is better than the next nearest city I place the entire algorithm in a loop that is preformed ten times. Then the range of outcome drops to 2800 to 4200 between 500 and 1700 better than the solution we found in class.

No comments:

Post a Comment

Blog Archive