Example:  GHSAMPLE.XLS, TSP worksheet

Solution Type:  Enumerated Chromosomes

This example is located in a tab labeled TSP in the GHSAMPLE.XLS worksheet that was installed in the C:\GENEHUNTER\EXAMPLES\EXCEL subdirectory if you chose the default directory during GeneHunter installation. (If you install the entire AI Trilogy set of programs, the GeneHunter folder is a subfolder of the C:\AI Trilogy folder.)

The Traveling Salesman Problem is a well known problem which has become a comparison benchmark test for different computational methods.  Its solution is computationally difficult, although the problem is easily expressed.  A salesperson must make a closed complete tour of a given number of cities.  All cities are connected by roads, and each city can be visited only once.  GeneHunter solves this problem by minimizing the value in cell D23, the total tour length, and by changing the order of the city numbers in cells B7:B21, the adjustable cells.  Each city is assigned an ordinal number from 1 to N, where N is the number of cities.  The city names and numbers are listed in a range called Map in Cells B26:E40.  The tour is represented as the entire sequence of city numbers.

The tour length is computed using a look-up table located in cells H26:V40, in a range named Distances.  The example uses Excel’s Index function for arrays in cells D7:D21 to compute the distance between each city pair listed in Column B.  For example, the distance between the two city numbers currently listed in cells B7 and B8 is computed with the following function:

Index(Distances,B7,B8) in cell D7

The distance between the next two cities would be computed in cell D8 with the function:

Index(Distances,B8,B9) in cell D8

Once the distances between all of the city pairs are computed (the distance between the last city and the first is also computed to close the loop), the entire tour distance is summed in cell D23, the fitness function cell that is minimized.

Figure 5.10  View of Traveling Salesman Problem worksheet

Figure 5.11  TSP worksheet includes range called Map on right and range called Distances on left.

Figure 5.12  View of GeneHunter main dialog screen for TSP

GeneHunter uses enumerated chromosomes and unique genes to solve this problem.  The problem employs enumerated chromosomes rather than continuous chromosomes because the list of cities is finite:  from 1 to 15.  Selecting unique genes insures that each city appears only once in the ordered list of cities to be visited.  Constraints are not required to solve the problem.