The Travel Salesman Problem Computer Science Essay

Published:

The Ant colony optimization algorithms can be applied directly to the travel salesman problem. An undirected graph of the form is used. In this graph N are the nodes (cities) and A are the arcs (paths) where they are connecting the cities. The restriction is that the total path is closed which means that every ant, will complete the tour returning to the first city. All the tours represent a possible solution for the problem.

In ACO algorithms for TSP, the pheromone path depends on the arcs (paths) and for this reason the amount of pheromone refers to the possibility of an ant to visit the node (city) j after the city i. This heuristic information is:

Equation

more specifically is the heuristic need for an ant to go from the city i, to the city j and it is inversely of distance between these cities.

Lady using a tablet
Lady using a tablet

Professional

Essay Writers

Lady Using Tablet

Get your grade
or your money back

using our Essay Writing Service!

Essay Writing Service

The routes are created from ants by using the following process: Firstly, the ant is placed in the city from where it will start the tour. Secondly, the use of the pheromone and the use of the heuristic values for the formation of a new tour, according to the probability rule, adding in every repetition the cities which the ant has not visited yet until the time that the ant will visit all cities. Finally, the ant will go to the city which has started its tour.

In order to understand how ants are working, it is needed first to identify the behaviour of the real ants. Generally the ants have the ability to find:

The shortest path from the food source to the nest (Beckers, 1992) without using optical instruments ( Halldobler and Wilson,1990).

One new shortest path when the old one is not available because on the path there is an obstacle, so the ants the have to change their direction.

Figure : ants are going from nest to food source

Figure : obstacle in the path

Figure : ants returning from the shortest path to the nest

The ants are moving in a path which connects the nest with the food source. In figure (1) the ants go from the nest to the food source, while they are leaving pheromone in the path. In figure (2) there is an obstacle in the path. The moment that the ants reach the obstacle, half of them go to the right and other half of them to the left in order to continue their travel to the food source, again they are leaving pheromone in the path like the previous situation. In this step, we have to mention that the pheromone evaporates while time is passing. This means, figure (3), that when the ants go back to their nest will choose the shortest path and not the largest. Again, the ants are leaving an amount of pheromone on the paths and because the probability to follow the shortest path is bigger (shortest path has smaller amount of pheromone than the larger one). From the above, it can be easily understood that most of the ants will follow the shortest path. The interesting side of auto-catalyst procedure is the finding the shortest path around the obstacle is the property which comes from interaction of the shape of the obstacle. More time is needed for the ants to go from the biggest path than from shortest, so the trace of the pheromone is maintained more in the shortest path.

To conclude, the highest pheromone level in the shortest path makes the ants choose it rather than the longest. This process is takes place until all the ants choose the shortest path.

Figure

1.1 Ant System

The algorithm Ant System is the first algorithm of research effort which is dealing with ant colony algorithms. The As introduced first on travel salesman problem (TSP) from Dorigo and his colleagues in 1992. The algorithms which are using the AS as base and they were presented as heuristic methods, they are helping in solving combinatorial optimization problems.

In AS the artificial ants are co-operated in order to solve a problem, while they exchange information with the use of pheromone, which is left on the path. The main characteristics of AS are: the ants following the positive feedback, based on distributed computing, AS uses an heuristic function, which helps to find solutions for the problem, and it is based in a population approach.

Lady using a tablet
Lady using a tablet

Comprehensive

Writing Services

Lady Using Tablet

Plagiarism-free
Always on Time

Marked to Standard

Order Now

In the artificial ants there are some possibilities which they are not found in physical ants, but they have tested that they work for TSP: the artificial ants the can see how far the cities will be (visibility) , they have a memory N which is used to remember the cities that they have already visited. This memory is 'cleaned' at the start of a new tour and it is adjusted for each time step, adding the city which they have visited.

Every TSP solution is created with the movement of the ants from a city to another with a probabilistic rule. The tour is completed when the artificial ant comes back in the city where started. It has to be mentioned that one completed cycle solution is completed when each ants go back to the cities that have started their tour.

The ant is placed randomly to the cities and every city has at least one ant which is starting the tour from there. Each ant has k during the repeat t and when it is in the city i is choosing the next city j according to the following rule

Equation

Where:

: are the cities that the ant k has already visited, when it is in the city i,

: is the amount of pheromone on the path which connects the cities i and j and represents the preference of the choice of the city j when the ant is in the city i.

The data of pheromone is changing during the solution of the problem in order to show the experience that the ants have during the process. The ants are leaving pheromone according to the quality of the solutions that they have produced, which means as shortest is the path the more pheromone are leaving on the paths that the ant has visited.

: is the visibility and is defined as the inverse of the distance between the cities i and j:

Equation

The visibility expresses the heuristic preference of the city j, as the next ant k visited the city when it is in the city I. The information is local.

: is the visibility of the ant k if it is in city i and wants to go to city j.

: refers to pheromone and based on the positive feedback of the optimal solution.

and are constants which have to be chosen in appropriate way in order to give an optimal solution.

Figure :text

Pheromone update rule

The pheromone update rule on time t applied as follows: when the ant finishes its tour, during the repetition t+1, the pheromone which is located in the paths is given by formula:

Equation

Where ρ is 0<ρ<1 and is called the evaporation coefficient with:

Equation

: is the amount of the pheromone in the path (i,j) which ant is leaving between the time t and t+1 and is given by the formula:

Equation

Where :

: is the number of the ants

: is the tour of the ant k during the repetition t

is the total length of the tour

: is a parameter which is chosen from the user and does not change the efficiency of the algorithm.

From this equation it can be easily understood that the amount of the added pheromone is inversely of the cover distance. So the shortest are the routes the more attractive are for the ants.

The Ant System is flexible and adaptive and it used in problems where the heuristic information is changing.

1.2 Ant Colony System (ACS)

The Ant colony is an optimal version of Ant System. As the Ant system is referred in Dorigo articles, the same is happened with the Ant colony system. It has to be mentioned that the ACS provides better results for the TSP problem than the other algorithms.

The procedure of choosing the next city which is used in ACS algorithm has been changed from the procedure which is used in AS algorithm. The ant in time t will choose a random city in the same way as AS. Instead at this point, the ants will choose only the best available city, depending in the visibility and the trace of the pheromone. The choice of the next city is made by the use of a random number q, which is selected by the ants before they choose the next city of their tour. If this number is smaller than the q0 , then the ant will choose the best city, otherwise will choose a random city.

1.2.1 Differences between AS and ACS

Lady using a tablet
Lady using a tablet

This Essay is

a Student's Work

Lady Using Tablet

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Examples of our work

Firstly, the transition rule (from one node to another) uses equally the exploration of new paths as well as the already the collected data of the problem. Secondly, the total update of pheromone is used only in path that belong to the route which is used by the 'best' ant. Finally the local update of pheromone is done while the ants are completing their tour.

1.2.2 Transition rule

An artificial ant k when it is in the city i, it will choose the city j because the city does not belong in the sample by using the following possibility rule:

Equation

Where:

: is the amount of pheromone at path (i,u)

: is the reverse of the distance between the cities i and u

: is a possibility equation which gives the possibility that an ant k at city i is choosing the city j.

1.2.3 Global update rule

The amount of pheromone is changing both locally and globally. The global update pheromone aims to the supply of pheromone to the shortest paths.

When the artificial ants finish their routes, only the ant which has done the best route emits pheromone. This is different from AS, as in AS every ant emits pheromone in every path. The amount of pheromone where emits the best ant in every path (i,j) which was visited, it is inversely of the length of the route. From this, it can be understood that as the shortest is the path the more pheromone the ant emits at the paths of the tour which has visited.

The rule of total update pheromone is given by:

Equation

Where:

Equation

is the length of the route, at time t and is the sequence of cities visited. The evaporation coefficient of pheromone can take values between [0,1). In addition the total pheromone equation shows that only the paths belonging in the best tour will have more pheromone than before.

1.2.4 Local update rule

During the creation of the route the ant updates the amount of pheromone of paths which has already used according to the local update pheromone rule:

Equation

Where:

: is the initial pheromone level

Dorigo and Gambarella on 1997 proved experimentally that for a given number of cities n and , a length of route is created by using the nearest heuristic algorithm . The purpose of local update rule is to make the decision of the cities to change dynamically in order to reassess the route. If the ants explore different paths, then there is a greater chance for one of them to find an optimum solution instead of all the trying to find a solution based on an area close to the best solution of the last iteration. Each time an ant creates a path, the local update rule reduces the amount of pheromone of the cities which has already visited so that each path becomes less attractive. Because of this, the nodes used in a path of an ant are less like to be chosen during the creation of path other ants. As a result, the ants exploit the cities that they have not visited yet, so that not only one route is used by the ants.

1.2.5 Candidate List

A candidate list is a list of cities that the ant has to visit starting from a given city. The cities are shorted according the inverse of the distance. Initially an ant has visited all the nearest cities which are belonging to the list for a given city i, the next city j is chosen from the nearest cities tha the ant has not visited yet.

1.3 Max-Min Ant System (MMAS)

The research along the years has shown that improved results than ACO algorithm solution can be created, if there is a more efficient method for searching the food in algorithms. But, in this point, the problem of early stagnation should be considered. In order to avoid this situation, it has to be created a combination of finding better solutions, which they will be found during the search of an effective mechanism to prevent the premature stagnation. The Max and Min algorithm was created to cover these requirements [from Stutzle and Hoos,2000] and the main differences to AS are:

In order to produce better solutions, during an iteration or during of the algorithm process, only one ant adds pheromone in the path (the ant which has found the best tour Lbest ) : the ant that have the best solution during the iteration (iteration best ant ) or the ant which found the best solution found since the start of algorithm process (global best ant ).

To prevent the research stagnation, the values of pheromone are placed in a space [Ï„max, Ï„min]. The use of Ï„max prevents the stagnation because none of the tours is concentrating huge amount of pheromone to attract all ants. The value of Ï„min ensures that none of the routes will have zero possibility of choice from the ants.

The traces of pheromone initialized in Ï„max, achieving a greater exploration of the solution at the beginning of algorithm.

In the MMAS algorithm the transition rule, which represents the movement of the ant k , during the iteration t, from the city i to the city j is given by the formula:

Equation

Where:

: are the cities that the ant k has already visited, when it is in the city i,

In MMAS, algorithm only one ant is used in order to update the pheromone at the end of each cycle. So the rule of the updating pheromone is given by:

Equation

Where:

Equation

Where:

L*(t): is the length of the global best tour until the time t (Lbest(t)) or is the length of the best ant tour in iteration until the time t (Liter(t))

T*(t): is the row of the cities.

Lbest(t) and Liter(t) can represent the cost of the total best solution and the best solution in every iteration. The use of only one solution (the global best solution or the best solution in every iteration), for updating of the pheromone is the most important part of the Max and Min Ant system algorithm. For this reason a judicious choice has to be done, between the best iteration solution and the global best solution. When Lbest is used, the research of the solution may end early and as a result may not have the ideal solution. In this case there is the danger that the algorithm may produce not the best quality solution for the problem.

In order to avoid this problem, the danger can be minimised if the best solution in every iteration chosen and moreover if in every iteration the pheromone of the path is updated.

Moreover in order to archive better results, combined techniques can be used. An example is to update the pheromone level after a completed cycle. In travel salesman problem, the best technique is the use of a dynamic combined technique which increases the frequency of the best solution used for updating the pheromone during the search of the best path.

It has to be mentioned in this point, that regardless the global best solution and the best solution in every iteration, for the renewal of pheromone, stagnation of the search may exists. This could happen if in a choice point; the amount of the pheromone is significant bigger than in others. In travel salesman problem case that means, in every city one of the paths has bigger amount of pheromone than in others. More specifically, the ant will prefer this path for the solution which could prefer and as a result the amount of pheromone in the path will be increased more and more. In this situation the ants are producing the same solution continuously and the search for new paths stops. So, stagnation in the solution is created.

This stagnation in the solution has to be prevented. One way to avoid this stagnation is that the possibilities for the choice of the next part of the solution can be affected, because it is known that they are dependant of the amount of the pheromone and from the heuristic information. The heuristic information is dependant of the nature of the problem and it is static during the process of the algorithm. With the restriction of the pheromone amount, the stagnation can be prevented ( the differences between the amounts of pheromone can produce great differences on the results during the algorithm process). In order to succeed this target, the Max and Min Ant system has clear limits (tmin and tmax ) on the low and high limits of pheromone in order to apply that:

At the end of each iteration has to be ensured that the pheromone is between the limits.

If that means , and if then .

If and for all solution components then there is no possibility of specified part of the solution to zero. The appropriate values of pheromone's limits should be chosen from the user.

1.3.1 Finding Min and Max values

1.3.1.1 Finding Max Values

Thomas Stutzle and Holgel H.Hoos in 2000 at their article for Max and Min Ant system explained exactly the way to find and values of pheromone in paths. They introduced the 'meaning' of convergence for Max and Min Ant system, which is used in each point, where one of the solution components has as pheromone path while all solution components have a pheromone path . In this case, if MMAs has converged for the solution constructed by choosing the solution component with the maximum pheromone path, which is referred to the best solution found by the algorithm. The difference between the convergence of MMAs and the stagnation is that while the stagnation means all ants follow the same path, in convergence situations of MMAs this is not happened because the use of the pheromone path limits.

Thomas Stutzle and Holgel H.Hoos have shown that for any exists:

Equation

The maximum level added after each iteration is where the ideal value of the solution for a specific problem is. So from equation for updating pheromone in MMAs has showed that:

Equation

Moreover because ρ<1 the sum converges to:

Equation

In order to have more appropriate results, the global best solution is used in the equation than the best solution in every iteration. With the use of Lbest moment every time a new best solution is produced and as a result is updated, producing a dynamically changing of .

1.3.1.2 Finding Min values

In order to determine reasonable values for some assumptions have to be made. First of all, the best solutions are found before search stagnation is starting to exist during the solution. Generally, more accurate results can be found close to the best solution found. Secondly, the difference in the solution of the algorithm is caused, mainly, because of the upper and lower pheromone path limits and not by the relative differences of the heuristic information.

It can be understood from these assumptions that the best values of can be found by relating the convergence of the algorithm to the minimum path limit. When convergence takes place in MMAs, the best solution created with a probability pbest which has high value (significant bigger than zero). Generally, the probability pdec that an ant chooses the right solution depends values. Thomas Stutzle and Holgel H.Hoos, for simplicity reasons, assumed that pdec is constant at all decision points. Because of this, an ant will choose n times the right path and the best solution will constructed with the probability of pndec.

By setting

It can be determined

By setting a value for pbest, it can be found the appropriate setting value for . For sightseeing equal to one and number of paths avg=n/2, which are connecting current city of ant with the other cities, the possibility rule exists:

Equation

and by solving for ,the equation becomes

Equation

2. The Travel Salesman Problem

One of the most simply distribution problems is the Travel Salesman Problem (TSP). In this problem, a salesman has to vista number N of cities by satisfying two basic rules:

The salesman has to visit every city for once before the end of his tour.

This should happen by using the smaller possible distance.

When the salesman satisfies these rules, he has to go back to the city, where he started his tour.

The first reference in travel salesman problem can be found from Voight in 1981, but the first observations with the term 'The Travel Salesman Problem' were found in 1932 in an article from Menger. The TSP is an NP-hard problem which means that its complexity increases exponentially as the number of points ( cities which the salesman has to visit in TSP case) increased.

It is assumed that there is a network with nodes 0,1,2…N with edges (i,j) and the length of each edge can be characterised from the constant cij. The node 0 represents the city from where the salesman will start his route and where the salesman is finishing his route. It has to be mentioned in this point, that the salesman has unlimited time to complete the solution of algorithm. This finding has been made from Boldin et al. in 1983.

Figure

In the most simply case of the travel salesman problem, there is no difference between the nodes when the travel salesman starts his route, meaning that there are no restrictions on how the travel salesman man will visit the city, but he has to visit each city once.

The TSP algorithms are classified in three basic categories:

Local search methods (Johnson et al. 1997)

Tour Construction Heuristics methods ( Golden and Asssad,1998)

Metaheuristic methods.

Moreover, in the solution of previous methods, optimisation routes improvements can be applied. In the following section , some of the most well-known heuristics algorithms will be presented.

2.1 Nearest Neighbour

The most simple and the most well-known algorithm for solving the TSP is called the Nearest Neighbour algorithm. The characteristic of this algorithm is that the-next-to-visit node (city in TSP case) is the one with the smaller distance from the current node (concluding also the first node- the city where the salesman started his travel), by satisfying the restriction which is that the nearest city has not visited yet. This procedure comes to an end when the salesman goes back to the city where he started his tour. An analysis of this algorithm can be found from Rosenkrantz et al (1977), Bentley (1990), Frieze (1979) and Golden Stewart (1981).

Figure : Nearest method graph

2.2 Insertion method

A more complicated method is the Insertion method, in which the choice of the starting place of the node in the route depends on how the cost of route is increasing. The solution method is based in the sequential introduction of nodes in a defined route. It has to be mentioned in this point that if there is a need of adding an new node (city ) in the route, this node should not cause any new cyclic routes. The equation which gives the cost for introducing a new node between the nodes i and j is given from the following formula:

as the following figure shows:

Figure : Insertion method

This method is repeated until the time that the procedure cannot be continued further. Moreover, this type of algorithm can be used as an optimisation algorithm for routes generally. This algorithm has been analysed in the past from Rosengrantz (1977) , Bentley (1990), Frieze (1979), Golden & Stewart (1981)

2.3 Clark and Wright Savings

An equal well known method is introduced from Clark and Wright, as Clark and Wright Savings at 1964.

In this method, firstly, from a sample of customers n is chosen randomly a point which will be the start and finish of the route and it is characterized from value 1. In second step, the algorithm is creating n-1 routes (1-j-1) with i=2,3,….,n. For points pairs ( i,j) with i,j=2,3….,n (idiaforo, j), a cost metric transition rule variant (sij) is calculated (from i to j) as the difference between the cost of transition rule from point i to the point j, if between the two points an starting/ ending point is inserted minus the cost of the directly transition, cij, from i to j.

As a result, the variant sij comes from the equation:

The values of sij are classified in descending order. In the next step, from a list of profits, the point with the highest profit is chosen and then this point is added to the route. This step is repeated until all customers are included to the route. According to Boldin et all. In 1983, in this case it has to be avoided the creation of cycle in the route. This method represented from number of researchers such as Clarke and Wright (1964), Golden and Assad (1998) and Golden & Stewart (1981).

2.4 New Heuristic Methods and 2-opt Method

The heuristic information which proposed from Christofides (1976, 1979) is creating a very good solution by using some steps. In the first step, as given a set of n customers, a minimum panning tree is constructed. In the second step, the nodes that link an odd number of sector are chosen and it is created the so-called perfect matching M. In the third step, the branches of T and M are combined in such way in order to create a multiple graph (multigraph) G. Finally, in the last step, from the multiple graph G those sides that create a cycle of Euler are selected ( Johnson et al, 1997).

Figure :Euler Method

Moreover, the researchers have investigated methods which have got as target to improve the already found solution. The methods are based in the idea of replacing the internal paths with other in order to minimize the total length of the route. These methods are replacing each time k arcs, so that the feasible route which will be created is better than the previous one (and Lin, S 1965, Lin and Kenighan, 1973). This happens usually when k=2 or k=3. The most well know method is when k=2 and it is called 2-opt.This method examines the replacement of a pair of arcs with two other arcs in order to achieve a better result. The process continues until the total cost of the route cannot decrease with the changing of arc pairs.

2.5 Metaheuristics Algorithms

Finally for solving for solving travel salesman problem and for solving distribution problems, metaheuristics algorithms were developed (Osmin and Laporte, 1995). These algorithms can usually characterized as high level strategies, which they can used for the development of heuristic methods in a wide range of problem. The basic target of the metaheuristic algorithms is to avoid the disadvantages which are caused from continued optimization of the already existing solution, preventing the solution from being restricted to local optimum rout. (Osman and Laporte,1996). This is possible either by allowing the choice of the worst solution or by creating a new optimal solution.

Examples of metaheuristic algorithms

Some of the most important metaheuristic algorithms, besides the ant colony optimization algorithm, are referred below.

Simulated Annealing (SA)

The method of Simulated Annealing (SA) is udes for the solution of TSP from Kirkpatrick et al (1983) and from Cerny (1985). The basic concept of of this method is that the solutions which are worst that the current maybe checked.

Tabu Search (TS)

Another metaheuristic method is the Tabu Search (TS) which has used as solving technique of the TSP problem from Glover (1989, 1990,1991), Lin and Kernighan (1973), Rosier et al. (1986), Malek et al. (1989) , Knox and Glover (1989) Knox (1994). The Ts method is meta-heuristic and shares the same capability with Simulated Annealing to avoid the local optimal solutions. The Tabu Search is using deterministic rather than stochastic criteria.

Genetic Algorithms

Genetic Algorithms is another type of algorithm that can be used for solving the travel salesman problem. Some of the researchers that referred to this method are Golberg (1998), Holland (1975) Valenzuela et al. (1994) and Muchlenbein & Voight (1995). The basic concept of this algorithm is that through a selection process, the more appropriate solutions are chosen from the available solutions.

2.6 Pseudo code example for Travel salesman solution.

This section of the report is dealing with the creation of a new simple algorithm for solving the travel salesman problem. The algorithm was created as a pseudo code by using simple programming commands in order to be easily understood from any user. For this reason, every part of the algorithm is numbered in the left side of the commands.

To start with, let consider a network consisting of N nodes V= {0, 1,…., n} and a set A of arcs connecting the nodes where 1,…, n are the candidates to visit cities for the salesman and zero is the starting point ( starting city) for the algorithm. Every arc (i,j) related to the cost of the algorithm and represents the distance which the salesman made from the node i to the node j. Moreover, every city which is included in the algorithm is characterized from its place in the Cartesian plane.

Below are the presence and the explanation of the algorithm. The data, that they are needed to be fitted by the user to the algorithm, are the location of each city in the Cartesian plane.

The numbers to the left of the algorithm reference to the relevant explanations inside the text.

Input values: co-ordinates of the cities (i,j)

Pseudo code

Begin

For i=1 to n do

For j=1 to n do

d [i,j] = sqrt ( ( A[j,1]-A[i,1]2 + [ A (j,2)]- A[i,2] )2)

End

End

For i=1 to n do

tab[i]=0

End

path[1]=1

tab[1]=1

k=1

s=1

distance=0

Repeat

temp=infinent

For j=1 to n do

If (tab [j] < >1) and d[k,j] < temp) and (d [k,j] < >0)

temptar=j

temp=d[k,j]

End

End

s=s+1

path[s]=temptar

distance=distance+d[k,temptar]

tab[temptar]=1

k=temptar

until s=n

path[n+1]=1

distance=distance+ d [K,1]

For i=1 to n+1 do

disp (path [i])

End

End

The input values are placed from the user into the pseudo code. For a number n of cities , 2x2 matrix is created, where in the first column are placed the x co-ordinates of the cities in the Cartesian level and in the second column are placed the y co-ordinates of the cities in the Cartesian level. The rows of the matrix are characterized from the number n of the cities and they depend of the number n of cities (1, 2,….,3) .

In this step, an nxn matrix is created in order to calculate the distance between the cities. In this case, there are two commands For , for ( i, j).In the second command there is the formoula, which calculates the distances between the points. This procedure ends when all the distances between the points found.

In the third step, a matrix with one row and one column is created. This matrix is called 'taboo list' and it is used in order to memorize the cities that they have already visited by the salesman. If the city has not visited yet, then the value is 0, If the city has already visited, then the value is 1, in order not be visited again by the salesman. This process is taken place in a loop.

The matrix path is also with one column and one row and it contains the number of cities where the salesman has visited. The values that this matrix can take are from 1 to n+1. The value n+1 exists because after the end of the tour, the salesman has to go back to the city where he started his tour (starting point).

This is the starting point of the tour. The city where the salesman starts his tour is defined in the matrix 'tab'. Also this city is the first which is called as 'blacklisted'. Every city that the salesman has visited is called 'blacklisted'.

With the k variable is defined the point where is the salesman, during the process of the algorithm. Otherwise, it is named the current location of the salesman.

With the variable s are defined the number of the cities which have already visited by the salesman. Specifically, the variable s is the 'sum' of visited cities.

The variable 'distance' is used in order to calculate the distance that the salesman has covered. At the starting point (city) this distance is taking the value 0.

In the ninth step, a repeat loop exists. Inside of this there is the variable 'temp' which has an infinite value in the beginning of the algorithm and it is used to compare the distances between the cities. Afterwards, a loop 'for' exists. Inside this loop there is an 'if' command where the temporary choice of the next city is taken place. In this command, of the next city has not visited yet, if the distance is not zero (in order not to choose the same city) and if the distance is smaller than another city, the salesman can choose the next city. This city is added to the variable's' (sum of the cities) , the new distance is added to the existence and the research of the new nearest city can start again. The procedure of the 'Repeat' loop is taken place until the 'sum' of cities becomes n, which means that the salesman has visited all the cities which the user has set in the beginning of the algorithm.

After the end of 'Repeat' loop, the matrix 'path' is updated with the new number of the cities which have visited by the salesman.

As in the previous step, also the distance, which the salesman has covered during his tour, is updated.

Finally, a loop 'For' exists. In this loop every time that the salesman moves from one city to another, the new covered distance is displayed, in order to have the distance which is covered by the salesman during his tour.

End of algorithm.

3. Solving Travel Salesman Problem with Ant Colony System-Matlab Algorithm

In this section of the report, 'The Travel Salesman Problem' has solved by using the 'Ant Colony System'. The main objective of this section is to be understood how these two methods are combined in a Matlab code. The Matlab code which is used, found in the MatLab Central. After testing the algorithm, the results that has found are reliable to understand how these two methods work together. The explanation of the algorithm would become by using the same manner which is used in the previous section in the explanation of TSP pseudo code.

Explanation of the 'Main part of the code'.

C:\Users\Asvestas\Desktop\main matlab.PNG

1. In the first step of the main file, the variables which are used in the ants information file are placed in the m-file. The ants information file and its variable will be explained later in the report.

2-11. In this part of the algorithm, a loop 'for' exists. For the number of iterations (number of cycles) which has chosen from the user, the algorithm is running for the number of matrices and variables that exist in this loop. The matrix [app] is an nxm matrix in which the function ant primary placing is taken place. Afterwards the comman 'horzcat' is used to connect the rows of the matrix with the columns. This happens because every ant after the tour has to go back to the place (city) where started such as the travel salesman problem. The matrix [cost,if] includes a function where the cost of the total tour is identified in order to know the length of each tour in every iteration. The matrix [t], includes a function which called ant trace updating in order to update the trace with the new information which is available. Finally for each iteration the mean cost is calculated and also the best tour which is found during the process of the algorithm.

12-24. In this part of the algorithm, there are command which will represent the results coming from the algorithm. The first plot which is produced, it reflects the distance versus the number of iterations. From this plot we can see when the algorithm reaches in an optimal solution but also if during the procedure there is stagnation. Then by using a matrix, the minum distance is identified and it is plotted in a second graph. The best tour which is made from the best ant is found by using a 'for' loop which takes place for n+1 values ( the values has become n+1 because every ant has to go back to the city where it started its tour) .

3.2 Expanation of ants information

1. The function which is called ant information is used in order to add the variables into the algorithm.

2-6.These data are added from the user into the algorithm. Specifically, the number of iterations, the number of ants, the position of the cities in the Cartesian level(iterative point for x and y co-ordinates of the cities have to be prevented) and the number n of cities are the input variables of the algorithm which are selected by the user.

7-11. In this part of the algorithm, a double 'for' exists in order to calculate the distances between the cities. This happens for the number n of cities.

12. The evaporation coefficient of pheromone which is also added from the user

13-14. The heuristic information α and β. These values are also added from the user and they are important during the process because either they can drive to optimal results or they can cause stagnation to the algorithm.

15-23. This 'for' loop is used in order to express the heuristic need for an ant to go from one the city to another city and it is inversely of distance between these cities. (Equation 1)

24-25. In these two steps, the user adds another two values which they are referred to the primary tracing ( this value has to be small) and to the coefficient of common cost elimination ( this value has to be almost one).

3.2 Explanation of ant primary placing and ant cycle.

1-5.The function ants primary placing is using a 'for' loop in order to locate the ants in their starting point. Each ant is located randomly in the nodes of the algorithm(which they have been set by the user) in order to start the tour. Also, every time that the user runs the algorithm, the ants are placed in different starting points than the previous one randomly.

1-21. The function ant cycle has a number of 'for' loops in order to express the mathematical model of Ant Colony System. By using the matrix app and a number of variables, this function expresses how the ant will choose the next city of its tour by using the possibility rule which is analysed before (Equation 7). It has to be mentioned, that in this part of algorithm that it is also expressed the heuristic need for an ant to go from one the city to another city (Equation 1) in the first 'for' loop.

3.2 Explanation of ant cost and ant trace updating.

1-11. The function ants cost is used to calculate the ants' tour cost. More specifically two 'for' loops are used to calculate the total distance covered by the ants. Finally the elimination of common cost is calculated in order to get which is the shortest tour that it has been used by the ants.

1-7. The function ant trace updating is used in order to update the amount of pheromone in the paths. In essence, it is an application of pheromone mathematical model which is described in chapter one (Equations 4, Equation 5, Equation 6). In order the mathematical problem to be expressed on double 'for' loop is used for the process of the algorithm.