Source Code Discussion
The following listings will illustrate the ant algorithm to find good to optimal solutions for the Traveling Salesman Problem.
First we'll look at the data structures for both the cities on the plane and the ants that will traverse the cities. Listing 4.1 contains the types and symbolic constants used to represent the cities and ants .
 |
#define MAX_CITIES 30 #define MAX_DISTANCE 100 #define MAX_TOUR (MAX_CITIES * MAX_DISTANCE) typedef struct { int x; int y; } cityType; #define MAX_ANTS 30 typedef struct { int curCity; int nextCity; unsigned char tabu[MAX_CITIES]; int pathIndex; unsigned char path[MAX_CITIES]; double tourLength; } antType; | |
Type cityType is used to represent a city within the MAX_DISTANCE by MAX_DISTANCE grid. antType represents a single ant within the simulation. In addition to keeping track of the current and next city on the tour ( curCity and nextCity ), each ant must also keep track of the cities that have already been visited via the tabu array and the actual tour that was taken through path. Finally, the total length of the tour is stored within tourLength .
For a given size TSP, it's sometimes important to change the parameters of the equations. Here are the defaults for a 30 city TSP (see Listing 4.2). Adjusting the parameters will be discussed in a later section.
| |
#define ALPHA 1.0 #define BETA 5.0 /* Favor Distance over Pheromone */ #define RHO 0.5 /* Intensity / Evaporation */ #define QVAL 100 #define MAX_TOURS 20 #define MAX_TIME (MAX_TOURS * MAX_CITIES) #define INIT_PHEROMONE (1.0 / MAX_CITIES)
| |
The ALPHA parameter ( ± ) defines the relative importance of the trail (pheromone level on the trail). BETA ( ² ) defines the relative importance of visibility (reciprocal of distance). RHO ( ) is used as a coefficient of the amount of pheromone an ant deposits on the trail ( otherwise known as trail persistence), where ( 1.0- ) specifies the rate of evaporation of the trail after a tour is complete. QVAL (or simply Q in Equation 4.2) is a constant related to the quantity of pheromone deposited on the trail. The remaining constants will be reviewed in the source.
The data structures used by the algorithm include the array of cities and ants . Another special structure, distance , pre-calculates the distance of each city to every other. The pheromone levels are stored within the pheromone array. Each two-dimensional array within the simulation uses the first dimension as the departure city and the second dimension as the destination. See Listing 4.3 for all globals used in the simulation, and Listing 4.4 for the initialization function.
| |
cityType cities[MAX_CITIES]; antType ants[MAX_ANTS]; /* From To */ double distance[MAX_CITIES][MAX_CITIES]; /* From To */ double pheromone[MAX_CITIES][MAX_CITIES]; double best=(double)MAX_TOUR; int bestIndex;
| |
| |
void init( void ) { int from, to, ant; /* Create the cities and their locations */ for (from = 0 ; from < MAX_CITIES ; from++) { /* Randomly place cities around the grid */ cities[from].x = getRand( MAX_DISTANCE ); cities[from].y = getRand( MAX_DISTANCE ); for (to = 0 ; to < MAX_CITIES ; to++) { distance[from][to] = 0.0; pheromone[from][to] = INIT_PHEROMONE; } } /* Compute the distances for each of the cities on the map */ for ( from = 0 ; from < MAX_CITIES ; from++) { for ( to = 0 ; to < MAX_CITIES ; to++) { if ((to != from) && (distance[from][to] == 0.0)) { int xd = abs(cities[from].x - cities[to].x); int yd = abs(cities[from].y - cities[to].y); distance[from][to] = sqrt( (xd * xd) + (yd * yd) ); distance[to][from] = distance[from][to]; } } } /* Initialize the ants */ to = 0; for ( ant = 0 ; ant < MAX_ANTS ; ant++ ) { /* Distribute the ants to each of the cities uniformly */ if (to == MAX_CITIES) to = 0; ants[ant].curCity = to++; for ( from = 0 ; from < MAX_CITIES ; from++ ) { ants[ant].tabu[from] = 0; ants[ant].path[from] = -1; } ants[ant].pathIndex = 1; ants[ant].path[0] = ants[ant].curCity; ants[ant].nextCity = -1; ants[ant].tourLength = 0.0; /* Load the ant's current city into tabu<au: Should this be tabu? Yes> */ ants[ant].tabu[ants[ant].curCity] = 1; } } | |
The first function to review is initialization (init) as shown in Listing 4.4.
Function init performs three basic functions to prepare for execution of the ant algorithm. The first is creation of the cities. For each city that must be created (defined by MAX_CITIES ), we generate a random number for the two x,y coordinates and store them into the current city record. Additionally, while in the loop of initializing cities , we use the opportunity to clear out the distance and pheromone arrays at the same time.
Next, as an optimization step, we pre-calculate the distances between all cities created within the cities structure. The distance measure is calculated using simple 2-dimensional coordinate geometry (Pythagorean theorem).
Finally, the ant structure is initialized . Recall that the ants must be uniformly distributed across all of the cities. To do this, the to variable is initialized and simply cycles through each city as an ant is associated with it. Once to reaches the end of the cities, it restarts to the first city (city 0) and the process begins again. The curCity field within the ant structure is loaded with the current city (the starting city for the ant). The tabu and path lists are cleared next. A zero within the tabu array denotes that the city has not yet been visited; otherwise, a one identifies it as a city already in the ant's path. The path is loaded with the current city for the ant and the tourLength is cleared.
Once a tour is complete, each ant must be reinitialized and then distributed across the graph. This is provided by the restartAnts function (see Listing 4.5).
| |
void restartAnts( void ) { int ant, i, to=0; for ( ant = 0 ; ant < MAX_ANTS ; ant++ ) { if (ants[ant].tourLength < best) { best = ants[ant].tourLength; bestIndex = ant; } ants[ant].nextCity = -1; ants[ant].tourLength = 0.0; for (i = 0 ; i < MAX_CITIES ; i++) { ants[ant].tabu[i] = 0; ants[ant].path[i] = -1; } if (to == MAX_CITIES) to = 0; ants[ant].curCity = to++; ants[ant].pathIndex = 1; ants[ant].path[0] = ants[ant].curCity; ants[ant].tabu[ants[ant].curCity] = 1; } } | |
During reinitialization, the best tour length is stored so that we can keep track of the progress of the ants. The ant structure is then cleared and reinitialized to begin the next tour.
The selectNextCity function provides for selection of the next city to visit in the tour. Also included is the function antProduct , which is used in Equation 4.1. See Listing 4.6. The pow function (power, x y ) is part of standard math libraries.
| |
double antProduct( int from, int to ) { return (( pow( pheromone[from][to], ALPHA ) * pow( (1.0 / distance[from][to]), BETA ) )); } int selectNextCity( int ant ) { int from, to; double denom=0.0; /* Choose the next city to visit */ from = ants[ant].curCity; /* Compute denom */ for (to = 0 ; to < MAX_CITIES ; to++) { if (ants[ant].tabu[to] == 0) { denom += antProduct( from, to ); } } assert(denom != 0.0); do { double p; to++; if (to >= MAX_CITIES) to = 0; if ( ants[ant].tabu[to] == 0 ) { p = antProduct(from, to)/denom; if (getSRand() < p ) break; } } while (1); return to; } | |
Function selectNextCity is called for a given ant to identify which particular edge to take given the tabu list. The edge to take is based upon the probability Equation 4.1. This equation is essentially a ratio of a given path over the sum of the other paths. The first part of selectNextcity is to calculate the denominator of the function. Upon doing this, all edges not yet taken are checked using Equation 4.1 to identify which path to choose. When this edge is found, the city to which the ant will move is returned by the function.
The next higher function within the simulation is simulateAnts . This function provides the ant movement simulation over the graph (see Listing 4.7).
| |
int simulateAnts( void ) { int k; int moving = 0; for (k = 0 ; k < MAX_ANTS ; k++) { /* Ensure this ant still has cities to visit */ if (ants[k].pathIndex < MAX_CITIES) { ants[k].nextCity = selectNextCity( k ); ants[k].tabu[ants[k].nextCity] = 1; ants[k].path[ants[k].pathIndex++] = ants[k].nextCity; ants[k].tourLength += distance[ants[k].curCity][ants[k].nextCity]; /* Handle the final case (last city to first) */ if (ants[k].pathIndex == MAX_CITIES) { ants[k].tourLength += distance[ants[k].path[MAX_CITIES-1]][ants[k].path[0]]; } ants[k].curCity = ants[k].nextCity; moving++; } } return moving; } | |
Function simulateAnts walks through the ant structure and moves ants from their current city to a new city given probability Equation 4.1. The pathIndex field is checked to ensure that the ant has not yet completed its tour, and upon confirming this, a call is made to selectNextCity to choose the next edge. The next city selected is then loaded into the ant structure ( nextCity field) as well as the path and tabu . The tourLength is also calculated to keep a running total thus far in the tour. Finally, if we've reached the end of the path, we add into the tourLength the distance to the initial city. This completes the path from the initial city through all other cities and back.
One call to simulateAnts allows each ant to move from one city to the next. Function simulateAnts returns zero when the tour is complete, otherwise a non-zero value is returned.
Once a tour is complete, the process of updating the trails is performed. This includes not only updating the trails for pheromone deposited by ants, but also existing pheromone that has evaporated in time. Function updateTrails provides this part of the simulation (see Listing 4.8).
| |
void updateTrails( void ) { int from, to, i, ant; /* Pheromone Evaporation */ for (from = 0 ; from < MAX_CITIES ; from++) { for (to = 0 ; to < MAX_CITIES ; to++) { if (from != to) { pheromone[from][to] *= (1.0 - RHO); if (pheromone[from][to] < 0.0) pheromone[from][to] = INIT_PHEROMONE; } } } /* Add new pheromone to the trails */ /* Look at the tours of each ant */ for (ant = 0 ; ant < MAX_ANTS ; ant++) { /* Update each leg of the tour given the tour length */ for (i = 0 ; i < MAX_CITIES ; i++) { if (i < MAX_CITIES-1) { from = ants[ant].path[i]; to = ants[ant].path[i+1]; } else { from = ants[ant].path[i]; to = ants[ant].path[0]; } pheromone[from][to] += (QVAL / ants[ant].tourLength); pheromone[to][from] = pheromone[from][to]; } } for (from = 0 ; from < MAX_CITIES ; from++) { for (to = 0 ; to < MAX_CITIES ; to++) { pheromone[from][to] *= RHO; } } } | |
The first task of updateTrails is to evaporate some portion of the pheromone that already exists on the trail. This is performed on all edges using Equation 4.4. The next step is accumulation of new pheromone on the trails from the last tours of all ants. For this step, we walk through each ant and utilize the path array to identify which edge to accumulate the pheromone on as defined by Equation 4.2. Once the accumulation is complete, we apply the _ parameter to reduce the intensity of the pheromone deposited by all ants.
Finally, the main function is very simple, acting as a simulator loop (see Listing 4.9). After seeding the random number generator and initializing the simulation, we run the simulator for the number of steps defined by MAX_TIME . As the ants complete a tour (through the simulateAnts function), the updateTrails function is called to modify the environment.
| |
int main() { int curTime = 0; srand( time(NULL) ); init(); while (curTime++ < MAX_TIME) { if ( simulateAnts() == 0 ) { updateTrails(); if (curTime != MAX_TIME) restartAnts(); printf("Time is %d (%g)\n", curTime, best); } } printf("best tour %g\n", best); printf("\n\n"); emitDataFile( bestIndex ); return 0; } | |
Note also that each time a tour is completed, the restartAnts function is called to make ready for the next tour through the graph. Only if we're at the end of the simulation do we not call restartAnts . This is because the function destroys the path information for the ant, which we want to retain at the end to emit the best path.
| On the CD | Not shown here is function emitDataFile , used to generate the plots shown in "Sample Runs." Please see the source on the CD-ROM for more information on this function. |
EAN: 2147483647
Pages: 175