 Open Access
 Total Downloads : 168
 Authors : Falak Singhal, Amrit Pal Singh
 Paper ID : IJERTV3IS030837
 Volume & Issue : Volume 03, Issue 03 (March 2014)
 Published (First Online): 21032014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Optimization of Ant Algorithms: A MetaHeuristic Approach to Complex Problems
Falak Singhal
Student, Dept. of Computer Science,
Guru TeghBahadur Institute of Technology, GGSIPU Delhi, India
Amrit Pal Singh
Asst. Professor, Dept. of Computer Science Guru TeghBahadur Institute of Technology, GGSIPU
Delhi, India
Abstractthis paper studies three algorithms Ant system, Ant Colony System and MinMax Ant System that are applied to travelling salesman problem Berlin52 benchmark function. Three comprehensive experimental studies that involve simulations of algorithms at authors machine have been carried out that investigates the behavior of these algorithms & compare their relative strengths and weaknesses. The first study establishes the optimal number of computational agents which will result in best solution of the benchmark function. The second study emphasizes on finding the minimum number of tours allowed for each ant such that number of iteration required for that solution are minimum. The experiments also verify the established optimal relationship between alpha and beta parameter of the Ant System given by Marco Dorigo.
KeywordsAnt System,Ant Colony System,MinMax Ant System, Travelling Salesman Problem, optimization

INTRODUCTION
Meta heuristics can be efficiently used in order to provide a sufficiently good solution to an optimization problem. Swarm Intelligence, which is a subcategory of metaheuristics, refers to the behavior of decentralized and selforganized systems that may be artificial or natural. Ant algorithms come under swarm intelligence.
These algorithms use probabilistic techniques to solve computation problems that can be applied to finding optimal paths through graphs. The first of this class of algorithms The Ant System (AS) was proposed by Marco Dorigo in his research paper in 1991[1].This algorithm introduces the basic foraging behavior of ants that uses branching factor to choose between various paths. This technique has seen many variants since its inception.
The main disadvantage of AS is its high run time [2,3]. Thus a new algorithm was introduced called Ant Colony System (ACS). The main differences between ACS and AS are the
trail update schemes and choice of next node. In ACS only the global best ant is allowed to update the trails.
Experiments with AS indicated that a more greedy approach improves the performance of the algorithm and hence lead to the development of MinMax Ant System (MMAS) which differs from AS in three major aspects: only a single ant is allowed to update the trail in each iteration, the trail intensities are bounded in between and and the trails are initialized in a specific way giving the solution space a specific interpretation.
The vehicle routing problem is a classic combinatorial optimization problem, which is NPhard. It addresses the problem of a salesman who has to travel n cities and return back to the starting city and should cover minimum total distance while doing so.
TSP has to comply with certain constraints that are, the salesman has to start at an initial city and he must visit each city exactly once and must return back to the starting city . The resulting route should be optimal that is it should incur minimum cost.

METHEDOLOGY USED
A. The Ant System
Ant System [2,3,4] algorithm uses a combination of both a priori and post priori information while computing an optimal solution. Here an ant is a computational agent whose behavior is stochastic. The ant inherently wanders randomly in search of food. Upon finding the food it returns to the colony laying down a pheromone trail in the path. Once other ants find this trail they are more likely to follow the path instead of wandering and will reinforce the trail in the process. But the pheromone evaporates with time and the trail become fainter over time.
The idea is that a shorter path will get marched upon by more ants than a longer one and hence balances the deposition and evaporation of pheromone trail and persists. The longer paths on the other hand vanish over time. So in principle the system should converge to a shortest possible route speaking in the terms of graph [13].
=1
1) Construction of Tour
The Key aspect of difference is the pheromone update heuristics in which only the global best ant is allowed to update the tail. So equation (2) is modified and the trail is chosen with the probability of (1) and the selection is made as the equation (1).

Trail Update in ACS
Defining the system in mathematical terms let an ant move
(1). +
(3)
from state to in each iteration corresponding to a partial solution. Each ant then contributes to its set of partial solution given as Ak (x). Then the probability , of ant, moving from state to is a function of two values :

The attractiveness of the route as computed using some heuristics indicating the a priori information

And the trail level of the move indicating the pheromone level on the path, a post priori information.

In generalth ant move from sate to state with the probability [14]
This rule results allows for a balance between exploration and exploitation strategies.
C. The MinMax Ant System
MinMax Ant System [7] is a greedier approach than both of the above algorithms. It was observed that for larger systems without a greedy approach the above algorithms degrades rapidly in performance and converge to a less optimal solution. To limit the stagnation of search the trail update rule is modified and the trail level is bounded in interval ( , )[3,12].

Trail Update in MinMax Ant System
=
(1)
In MMAS two types of updates can be considered. One, in which after each iteration the best ant updates the trail level
Where 0 and 1 are constants that control the influence of
and respectively.
and second, in which the global best found solution is used to update the trails. Both of these approaches differ in greediness.
The desirability of the move is typically 1
where
is
The modified trail update rule as per second approach is given as
the distance between states and .The larger the the smaller the attractiveness of the route.
() (1). ( 1)+ (4)

Trail Update in AS
Where = 1
,
is the tour corresponding
Once the ant has completed its tour the trail strengths are updated as
to global best found solution in ithiteration.


TRAVELLING SALESMAN PROBLEM
=1
. +
(2)
The traveling salesman problem is the problem faced by a salesman who, starting from his home town, wants to find the
Where is the pheromone persistence coefficient, is the pheromone deposited for the transition and is amount of pheromone deposited by th and typically given by
= if th ant uses the curve (,), 0 otherwise.
shortest possible trip through a given set of customer cities, visiting each city once before finally returning home. The TSP is a NPhard in combinatorial optimization [8].
The traveling salesman problem (TSP) is then te general
problem of finding a minimum cost Hamiltonian circuit in a weighted graph, where a Hamiltonian circuit is a closed walk
Where Q is a constant quantity of pheromone laid and
is the cost of th ant tour.
B. The Ant Colony System
The AS was shown as an exemplary approach to solve the TSP which gave satisfactory results. However due to high computational time, modifications to the original algorithms were proposed. Based on such variant called AntQ algorithm

some authors proposed Ant Colony System [2].
(a tour) visiting each node of graph G(V,E) exactly once.
In order to solve the TSP, one needs to find a route such that the total distance travelled by the salesman is minimum. Hence the input needed to solve such a problem is

A matrix of 2d coordinates of various locations in a map.

Thenumber of cities.

The Starting city can be selected randomly or can be provided as input.
After taking the input, the distance matrix is calculated that gives the Distance, dijbetween the ith and the jth city. This is provided by the value corresponding to the ith row and jth column.
The optimal solution then to the TSP is a permutation of the node indices {1, 2..n} such that the length f() is minimal

, where f() is given by
=1
f()= 1 [d (i) (i+1)] + d (n) (1) (5)
Travelling Salesman problem has been classified in two categories namely Symmetric and Asymmetric. In the symmetric TSP, the distance between two cities is the same in each opposite direction, forming an undirected graph. This symmetry halves the number of the possible solutions of the graph [11].
In asymmetric TSP, given two nodes (or cities) path may not exist in both the directions or may have different values (or weights) hence forming a directed weighted graph.


EXPERIMENTAL STUDY
The author implemented the three ant algorithms (Ant System, Ant Colony Optimization, MinMax Ant) and investigated their relative strengths and weaknesses by experimentation. Simulations were run to collect statistical data for this purpose.

Variation of optimal solution as a function of polpulation size
The parameters considered here are those that affect directly or indirectly the computation of the best tour resulted by these two algorithms include

n: The number of computational agents (Ants) that simultaneously explore the problem space and yield their respective partial solution sets.

k: The number of tours each agent is allowed to perform for completing its own set of optimal solution.
The number n of the ants is varied in an increasing fashion up to the close proximity of number of cities used in the TSP problem space. During this time the number if iterations (k) are kept to a constant value of 100. In this study author considered berlin52 benchmark function from TSP Library for our experimentation.
To compare the two models simulations were run to yield the optimal number of computational agent for a fixed number of iterations.
TABLE I. VARIATION OF OPTIMAL SOLUTION AS A FUNCTION OF POPULATION SIZE
Algorithm
Ant System
Ant Colony System
Min Max Ant System
S.no.
Population Size
Best Solution
Best Solution
Best Solution
1
5
9380
8423
8132
2
10
8621
7734
8077
3
20
8325
7657
8038
4
30
8307
7542
7662
5
40
8203
7542
7662
6
45
8043
7542
7689
7
50
7895
7542
7662
8
51
7938
7542
7596
9
52
7663
7542
7859
10
55
7790
7547
7910
Figure 1Number of Ants vs. Optimal Solution
The graphical plots clearly show that the algorithms perform better and yield a more optimal solution when the number of computational agents reaches the number of nodes in the problem domain.


Variation of number of iterations to optimal solution as a function of number of tours
This study involves finding how the algorithms behave when the number of tours allowed for one ant is varied.
Algorithm
AS
ACS
MMAS
S.No.
Tours
No. of iterations
No. of iterations
No. of iterations
1
10
4
3
8
2
20
3
3
10
3
30
2
4
27
4
40
2
2
24
5
50
2
3
47
6
60
9
4
8
7
70
9
10
47
8
80
11
12
19
9
90
12
15
60
10
100
15
16
35
TABLE II. NUMBER OF TOURS VS. NUMBER OF ITERATIONS TILL OPTIMAL SOLUTION

Alpha : the relative importance of the trail, > 0

Beta : the relative importance of the visibility, > 0
To compare the three models we first experimentally determined the parameters best values for each algorithm, and then we ran each algorithm five times using the best parameters set. The results of the study are as follows
TABLE III. VARIATION OF OPTIMAL SOLUTION AS A FUNCTION OF ALPHA AND BETA
Algorithm
Exp. No.
Tour Length
Average Value
Best Value
%
Error
Ant System (Berlin52No. of ants = 52, No. of Tours
=100)
1(=)
3
3
8092
8099.4
8021
7.3
3
3
8058
3
3
8230
3
3
8021
3
3
8096
2(<)
1
5
7872
7748.2
7674
2.6
1
5
7674
1
5
7794
1
p>5 7722
1
5
7679
3(>)
3
1
8837
8939.8
8606
18.4
3
1
9191
3
1
8606
3
1
8782
3
1
9283
Number of Tours Vs Iterations
number of iterations till optimal solution
70
60
50
40
30
20
10
0
um of rs or ed b ne ent x)
1 n 2 ber 3 tou 4 perf 5 m 6 y O 7 ag 8 (10 9 10
Figure 2Number of tours vs. Number of iterations till optimal solution
From this experimental study it was observed that the best number of tours (k) allowed for each computational agent to minimize the number of iteration lies within the close proximity of the number of nodes (n) for Ant System and Ant Colony System. When the number of tours k is increased till the value n, the number of iterations required for optimal solution decreases slowly, attains a minimum value at k=n and then increases sharply.
However the variation of number of iterations with number of tours for Min Max Ant was different. It was observed that for the optimal number of ants, i.e. n=52 , the number of computation till optimal solutions are highest. For the entire variation period the number of iterations fluctuates greatly between minimum and maximum value.


Variation of optimal solution as a function of alpha and beta
The parameters considered here are those that affect directly the computation of the best tour resulted by the Ant System algorithm include


RESULTS OF EXPERIMENTAL STUDIES
ANumber of ants vs. best found solutions
It was observed that as the number of computational agents
n increases both the algorithms converge to an optimal solution. As n approaches to the number of nodes in the problem domain the change in solution (best found tour length) for both the algorithms is abrupt.
However for Ant Colony System optimal solution attains a constant value till number of ants are in proximity of number of nodes (here 52) in the problem. This is in contrast with the Ant System algorithm in which the value for optimal solution decreases till a minimum value. Moreover it was found that the Ant Colony System algorithm gives a better optimal solution for the same number of ants.
For the same set of conditions the reported optimal solution for berlin52 benchmark problem by Ant Colony System was 7542 by the simulation software which is equal to
the established optimal value by TSP Library in comparison to Ant System which reported an optimal solution of 7663 which has +1.604 % error and Min Max Ant solution 7596 with
+0.71 % error.
TABLE IV. ACCURACY OF ALGORITHMS
AS
ACS
MMAS
Calculated Value
7663
7542
7596
Established
Value
7542
7542
7542
% Error
+1.60%
0%
+0.71%
BVariation of number of iterations to optimal solution as a function of number of tours
For the algorithms AS and ACS the number of iterations required to an optimal solution decreases linearly as the number of tours by each agent (k) increases and approaches the number of nodes in the problem domain.
It was observed that the optimal number of tours each agent is allowed to perform such that the iterations are minimum lies within the close proximity of number of nodes in the problem domain for these algorithms.
For Ant System the minimum observed iterations were 2 when the number of tour k approaches n and for the Ant Colony System the minimum number of iterations observed for an optimal solution were 3.
The fact that the Ant System algorithm outperforms the ACS algorithm can be attributed to the accuracy of ACS which demands more computation which is an acceptable tradeoff for ACS as it produces an established optimal solution for berlin52 problem.
For both the algorithms the iterations to optimal solution increases exponentially when the number of tours k is increased beyond n.
However this was not the case with Min Max Ant System. The number of iterations in this scenario fluctuates between a minimum and maximum value of (8, 47).
C. Variation of optimal solution as a function of alpha and beta
For the Ant System algorithm it was observed that the optimal solution occurs when the value of = 1 & = 5. This was in agreement of the results found by M.Dorigo in his empirical study of ant system algorithm. For both the cases (=) & (>), large deviations of + 7.3 % and 18.4 % respectively were observed in the average solution from the established solution of 7547 for berlin52 problem.
The +2.6 % error in (=1,=5) can be attributed to random errors that can be incurred due to runtime environment limitations etc.
Also the graphical study of tour length vs. iterations while conducting the experiments shows that the initial optimal solution for the case (>) are way off the optimal solution. Hence in this case the computations towards an optimal solution are large as compared to other two cases. This effect can be inferred from the steep drop in tour length vs. iterations graph during initial iterations.
Figure 3Iterations of AS when <
Figure 4Iterations of AS when >
The experiment was conclusive of that the best combination of alpha and beta is (=1, =5) for Ant System Algorithm.
The case of (>) is the worst which resulted in not only large computational complexity but a large deviation of result from established value also.

CONCLUSION AND FUTURE WORK
The studies were conclusive of the result that both ACS and MMAS performs better than originally proposed AS algorithm. The optimal solution occurs when the number of computational agents is equal to the number of nodes in the problem domain. Also the number of iterations to optimal solution were minimum when the number of tours performed by each ant are in close proximity of number of nodes for AS and ACS algorithms. The optimal values of alpha and beta
parameters are experimentally found out to be 1 and 5 respectively.
The future work of this study involves the behavior of Eigen ant and more recent algorithms in comparison to the initial algorithms like AS and ACS. Other artificial intelligence and swarm intelligence algorithms like Artificial Bee colony etc. can be studied and further analyzed.
REFERENCES

M.Dorigo,Ant colony optimization: artificial ants as computational intelligence technique,IEEE Computational Intelligence Magazine,2006.

Alberto Colorni, Marco Dorigo,and Vittorio Maniezzo. Distributed optimizationbyant colonies, Elsevier Publishing, 1991.

Marco Dorigo. Optimization, learning,and natural algorithms. PhDthesis,Politecnico di Milano, 1992.

M. Dorigo, T. StÃ¼tzle. The ant colony optimization metaheuristic: algorithms, applications and advances. In F. Glover and G.
Kochenberger, editors, Handbook of Metaheuristics . Kluwer Academic Publishers, 2002

Luca Gambardella and Marco Dorigo. Solving symmetric asymmetric TSPs by ant colonies. In IEEE Conference on Evolutionary Computation (ICEC'96), 1996

Luca M. Gambardella and Marco Dorigo. AntQ: A reinforcement learning approach to the traveling salesman problem. In Proceedings of te Twelfth International Conference on Machine Learning, page 252. Morgan Kaufmann, 1995.

Thomas Stutzle and HolgerHoos, Improvements on antsystem: introducing MAXMIN ant system, Technical University of Darmstadt,2012

M.R.Garey and D.S.Johnson. Computers and intractability: A guide to the theory of NPcompleteness. in Freeman, San Francisco, CA, 1979.

Marco Dorigo&Thomas Stutzle, Ant colony optimization, in Library of Congress Publications,The MIT Press, Cambridge, Massachusetts London, England, 2002

Aardal, K. I., van Hoesel, S. P. M., Koster, A. M. C. A., Mannino, C., &Sassano, A. Models and solution techniques for the frequency assignment problem. Technical report 0140, KonradZuse
Zentrum,2002

Bonabeau, E., Sobkowski, A., Theraulaz, G., &Deneubourg, J. L.Adaptive task allocation inspired by a model of division of labour in social insects. In D. Lundha, B. Olsson, & A. Narayanan (Eds.), Bio computation and emergent computing (pp. 3645). Singapore, World Scientic Publishing, 1997

Clark, P., & Boswell, R. Rule induction with CN2: Some recent improvements. In Proceedings of the European Working Session on Learning (EWSL91), vol. 482 of Lecture Notes in Articial Intelligence Berlin, SpringerVerlag,1991

Deb, K. Multiobjective optimization using evolutionary algorithms.
Chichester, John Wiley & Sons Publications , UK, 2001

Dorigo, M. Optimization, learning and natural algorithms [in Italian]. PhD thesis, Dipartimeno di Elettronica, Politecnico di Milano, Milan,1992.