• Learn about using Lisp for genetic algorithms
• Learn about the famous Traveling Salesman Problem

Genetic Algorithms

First pioneered by John Holland in the 60s, Genetic Algorithms have been widely studied and applied in many fields. GAs provide an alternative method to solving problems, and often outperforms other traditional methods for problems that have time complexities that are polynomial or worse. In practice, genetic algorithms have been widely applied in optimization problems such as scheduling and circuit layout. In this assignment, we will explore another application.

The Travelling Salesman Problem

Many TSP's are symmetric - that is, for any two cities A and B, the distance from A to B is the same as that from B to A. In this case you will get exactly the same tour length if you reverse the order in which they are visited - so there is no need to distinguish between a tour and its reverse.

If there are only 2 cities then the TSP problem is trivial, since only one tour is possible. For the symmetric case a 3 city TSP is also trivial. If all roads are present then there are (n-1)! different tours for an n city asymmetric TSP. To see why this is so, pick any city as the first - then there are n-1 choices for the second city visited, n-2 choices for the third, and so on. Thus, for the symmetric case there are half as many distinct solutions - (n-1)!/2 for an n city TSP. In either case the number of solutions becomes extremely large for large n, so that an exhaustive search is impractible for large n. For example, testing every possibility for an n city tour would require n! math additions just to compute each path. Thus, a 30 city tour would require 2.65 X 10³² additions. Assuming 1 billion additions per second, this would take over 8,000,000,000,000,000 years. Adding one more city would cause the number of additions to increase by a factor of 31. Obviously, exhaustive search is an impossible solution.

For these reasons, the TSP problem has some importance to computer scientists and appliued mathematicians, since many practical applications can be put in this form. It also has a theoretical importance in the field of complexity theory, since the TSP is one of the class of "NP Complete" combinatorial problems. NP Complete problems have intractable in the sense that no one has found any really efficient way of solving them for large n. They are also known to be essentially equivalent to each other; if you figure out how to solve one kind of NP Complete problem with an efficient algorithm you could solve all of them that way.

A genetic algorithm can be used to find a solution is much less time than the exhastive search. Although the GA may not find the best solution, it can find a good solution in less than a minute. In GAs a "fitness function" or "strength function" is used to measure how good a solution has been obtained. There are two basic steps to solving the travelling salesman problem using a GA. First, you create a group of many random tours in what is called a population of tours. Second, you pick two of the better tours as parents in the population and combine them, using a teachnique called crossover, to create a new solution child in the hope that it is an even better solution to the TSP problem than the parents were.

1. Download the Lisp code in GENETIC.txt and run it at least 5 times using the command (TEST) to find a minimum length tour that visits n = 4 selected cities in Kentucky. Note that due to the use of pseudo-random numbers, the results will vary from run to run, so document and discuss the results of each run in your text document.

2. Adjust each of the three parameters of the EVOLVE function one at a time, trying at least 5 runs with each set of values. What can you determine about the influence of each of these values on the search when they are varied one at a time?

3. Using what you have just learned to adjust all three of the parameters of the EVOLVE function to optimize the solution. Run at least 5 runs with your set of values and discuss your results.

4. Add Covington and Owensboro so that all of the cities on the following map are included in the TSP:
   
   Note that the actual driving distances to and from the additional cities can be found at http://www.mapquest.com/directions/. Include the modified portions of the code in your text document and document your results.

5. Next adjust all three of the parameters of the EVOLVE function to optimize the solution to your modified TSP with all of the Kentucky cities on the map. Run at least 5 runs with your set of values and discuss your results.

6. The way each genetic algorithms is written to create children will determine how quickly you might reach a good solution. Explain in words exactly how this GENETIC code combines the parent's genetic information.

7. Create a modification to how the GENETIC code combines the parent's genetic information and run at least 5 test runs with your modification. Include both your modification and an analysis of whether or not you believe you have created an improvement in your text document.

8. Genetic algorithms are often classified as learning algorithms, rather than search algorithms. Discuss your thoughts on this.

   Drop the text document named yourlastname(s)A14 in "A14 Genetic" when you are finished.

   ---

   Back to Introduction to Computer Programming with C++