

![0_image_0.png](0_image_0.png)

## Mmas

The main controlling parameters of MMAS algorithm are α, 
(lower pheromone trail limit) and 
(upper pheromone trail limit). As suggested in [6],
is the length of the best be the probability of choosing a particular solution component at a choice point successive right choices to construct the best solution, then the probability of selecting the best tour In [6], it has been shown that 

## V. Parameter Values In **Mmas**

 **The main controlling parameters of MMAS algorithm are α,** 
β, ρ (evaporation rate), τmin **(lower pheromone trail limit) and** 
τmax **(upper pheromone trail limit). As suggested in [6],**
τmax=1/ρCbs **gives best result where** C
bs **is the length of** 
tour found in current iteration. Also if pdec **be the probability** 
of choosing a particular solution component at a choice point and an ant has to make n **successive right choices to construct** 
the best solution, then the probability of selecting the can be described as pbest= pdec n. **In [6], it has been shown that** 
pbest relates τmin and τmax **through the equation** 

## (1 ) / [( 1) ] N N Min **Max Best Best** Τ =Τ − − **P Avg P**

where avg **is the average number of choices available to an** 
ant at each step while constructing a solution. [6] shows that best performance in context of TSP with traditional MMAS 
algorithm is achieved with α=1.0, β=2.0, ρ=0.02, ants)=N(no of nodes) and pbest **=0.05. Our problem** 
environment is different from TSP and therefore parameters, whose values depend on TSP instances, have to be modified. 

The number of successive right choices n **is assigned** of TSP. But in our problem, optimum solution generated reveals that an ant has to make an average of 20 right decisions to reach its destination. The parameter set at 20. Consequently, value of τmin **gets altered. Value of** 
avg **is set at 10 as it is found empirically that an ant has to**
choose on average of 10 paths at each step. Values of other parameters (α, β, ρ and τmax**) are left unaltered. Also, in first 20** 
iterations, only iteration best solution is reinforced and afterwards reinforcement is given to best-so iteration-best solution in alternate iteration. This strategy allows better exploration of search space as exemplified in [6].

## (1 ) / [( 1) ] (11) N N Max Best Best **P Avg P**

is the average number of choices available to an ant at each step while constructing a solution. [6] shows that best performance in context of TSP with traditional MMAS 
algorithm is achieved with α=1.0, β=2.0, ρ=0.02, m(**no of** 
=0.05. Our problem environment is different from TSP and therefore parameters, whose values depend on TSP instances, have to be modified. 

is assigned N **in case** 
of TSP. But in our problem, optimum solution generated reveals that an ant has to make an average of 20 right decisions to reach its destination. The parameter n is **therefore** 
gets altered. Value of at 10 as it is found empirically that an ant has to choose on average of 10 paths at each step. Values of other 
) are left unaltered. Also, in first 20 iterations, only iteration best solution is reinforced and so-far solution and best solution in alternate iteration. This strategy allows better exploration of search space as exemplified in [6].

## Vi.Simulation R**Esults**

 Max-Min Ant System (MMAS**) model is considered here to** 
study its performance with two kinds of deposition rules. As a problem environment, we take a network of connected cities 
) model is considered here to its performance with two kinds of deposition rules. As a problem environment, we take a network of connected cities where the shortest route between two given cities is to be determined. Now, suppose we have a starting city and a terminal city in a roadmap. Ants begin their tour at the starting city and terminate their journey at the destination city. Ant decides its next position at each intermediate step by a probability based selection approach. Suppose the neighborhood of an ant k currently residing on denoted by Ni k**. Then the ant's choice of a city from its** 
neighborhood Ni k**is governed by (1)**
probability of selecting city j **when the** 
city j∈Ni k if j **has not already been visited by** 
visibility information defined here as dil **is defined as the distance between the cities** 
specifies the distance between cities destination city. α, β **are the weights for pheromone** concentration and visibility as usual. Ants stop moving if either they find a dead end or reach the destination city. Constant deposition is the standard form of pheromone updating approach applied so far in all variants of ant system algorithms. In this approach, deposition of excess pheromone in all links of the tour is kept constant. But in our approach, we gradually increase the pheromone deposition on links as we move closer to the destination city. It implies that the links lying closer to the destination city receive more amount of pheromone as compared to those near the starting city. We now present the results of experiments performed. We divide the simulation strategy in two l level, the two competitive algorithms are run on 20 different city distributions and the range of values of parameters of the proposed algorithm for which it performs best and outperforms its classical counterpart by largest extent is estimated. In section A, we tabulate results for only 3 out of those 20 different distributions. 

where the shortest route between two given cities is to be determined. Now, suppose we have a starting city and a 
. Ants begin their tour at the starting city and terminate their journey at the destination city. Ant decides its next position at each intermediate step by a probability based selection approach. Suppose the neighborhood of an ant k currently residing on i th **city be** 
. Then the ant's choice of a city from its is governed by (1) **with** Pi k(j) **as the** 
when the k th ant is in city i**. A** 
has not already been visited by k th ant. ηil **is the** 
visibility information defined here as ηil =1/(|dil|+|dlg**|) where** 
is defined as the distance between the cities i and l **and** dlg specifies the distance between cities l and g, g **being the** 
are the weights for pheromone concentration and visibility as usual. Ants stop moving if either they find a dead end or reach the destination city. 

Constant deposition is the standard form of pheromone ach applied so far in all variants of ant system algorithms. In this approach, deposition of excess pheromone in all links of the tour is kept constant. But in our approach, we gradually increase the pheromone deposition on links as estination city. It implies that the links lying closer to the destination city receive more amount of pheromone as compared to those near the starting city. 

We now present the results of experiments performed. We divide the simulation strategy in two levels. In the primary level, the two competitive algorithms are run on 20 different city distributions and the range of values of parameters of the proposed algorithm for which it performs best and outperforms its classical counterpart by largest extent is estimated. In section A, we tabulate results for only 3 out of 

![0_image_1.png](0_image_1.png)

Figure 4 : Roadmap for 250 City Distribution
Figure 4 : Roadmap for 250 City Distribution A sufficiently complex roadmap of 250 cities is taken as the first problem environment. Here, 20 ants are employed to move through the graph for 100 iterations to find out the optimal path length between the source and destination cities as highlighted in figure 4. Parameters over the range 0.5 to 5.0 in steps of 0.5 to find out the A sufficiently complex roadmap of 250 cities is taken as the first problem environment. Here, 20 ants are employed to move through the graph for 100 iterations to find out the optimal path length between the source and destination cities figure 4. Parameters α and β **are both varied** 
over the range 0.5 to 5.0 in steps of 0.5 to find out the 