Keywords

1 Introduction

Ant Colony Optimization (ACO) [1] is an important bio-inspired optimizations technique that has notified its presence over the decade for solving different complex problems. Ant System (AS) [2] is the first of its kind in this domain. It models the ant foraging behavior and also, optimizes globally. It posses’ features like robustness, positive feedback, distributed computing and can be easily implemented with other algorithms. A lot of simulation work has been carried out on the Ant algorithms and their variants in different application domain. However, not much of related work on the theoretical analysis of ant dynamics has been explored in literature. Graph-based Ant System [3] was framed by Gutjahr where an analytical analysis on convergence has been studied. Also the author carried out a meticulous analysis on the finite-time dynamics of ACO and its convergence speed [4]. A convergence analysis has been established by Stutzle and Dorigo [5] for ACO algorithm. A differential equation approach using extended difference operator has been used by Abraham et al. [6] to study deterministic Ant System dynamics and ensure its stability and convergence.

Ant System dynamics is governed by the pheromone trail intensity update rule given in (1). The performance of the Ant System depends on the choice of values determined by the trail persistence, \( \uprho \) in (1) and the values in general lie within \( 0 <\uprho < 1 \) [2]. The values proposed in literature for the trail persistence are random in nature that suits the algorithm with best optimal result. So, there is a need to corroborate the range of values taken by the trail persistence and establish stability of the Ant dynamics. This article presents a deterministic model of basic AS based on transfer function model. Henceforth, frequency domain analysis helps us to find out the range of values taken by the trail persistence that ensure the stability of this linear ant system model. Also this paper focuses on the substantiation made to the consolidated range of trail persistence, \( \uprho \) which establishes the effectiveness in characterization of the Ant dynamics. Also it is conformed in this paper that for a stable ant dynamics, the uncontrolled pheromone deposition growth is not seen and the explosion of pheromone concentration is resolved. Moreover, the study does not violate the stochastic behavior of the ant dynamics, as the selection process of ants’ path is based on probability. Results of computer simulation have been provided in order to support the analytical claims made in this paper.

This paper is further organized as: Sect. 2 gives the deterministic modeling of the Ant Dynamics and its transfer function. Stability and convergence criterion of the Ant System using ROC is established in Sect. 3. Section 4 depicts the simulation results on TSP that validates the stability of the Ant System using ROC. Also the Frequency domain analysis is used to validate the range of values of the pheromone trail persistence, ρ that ensure stability of the Ant System. And finally the paper concludes in Sect. 5.

2 Modeling the Deterministic Framework of the Ant System

Ant System being stochastic in nature, it is hard to establish the nature of the system and to derive its stability. On such a ground, this paper is a humble effort towards the development of transfer function based model of ant dynamics and subsequently frequency domain analysis is made to establish the convergence of this system. The consolidated range of the trail persistence factor, ρ is validated in this paper which pledge in finding the optimal solution.

2.1 Basic Ant System

Ant-System (AS) [2] is the first successful technique to emphasize the swarm nature of the real ants. The pheromone updation formula of the system in any path segment is defined as,

$$ \uptau({\text{t}} + 1) = \left( {1 -\uprho} \right)\uptau({\text{t}}) +\Delta \tau ({\text{t}} + 1) $$
(1)

where, \( \tau ({\text{t}}) \) is the intensity of trail in any path segment at time t and \( \Delta \tau \) is the incremental contribution in intensity of trail in that path segment.

\( \uprho \) (0 ≤ ρ < 1) is the pheromone evaporation (decay) parameter; (1 − ρ) is the pheromone residual parameter. Also the path selection of the ant system is governed by a probability factor which is again controlled by \( \tau ({\text{t}}) \).

2.2 Formulation of Transfer Function

In this section we will try to model the ant dynamics using transfer function based approach by linearization method. This approach is helpful to find out the local stability around equilibrium point of a system as the local behavior of the system can be approximated using linear model.

Let us consider the pheromone updation equation of basic Ant System given in (1) as a first order linear closed loop system and we try to recast the equation as follows.

$$ \tau ({\text{t}} + 1) = \left( {1 -\uprho} \right)\tau ({\text{t}}) +\Delta \tau ({\text{t}} + 1) $$
(2)
$$ \Rightarrow \tau ({\text{t}}) - \tau ({\text{t}} - 1) = -\uprho\tau ({\text{t}} - 1) +\Delta \tau ({\text{t}}); $$
$$ \Rightarrow \frac{{{\text{d}}\tau }}{\text{dt}} = -\uprho\tau ({\text{t}} - 1) +\Delta \tau ({\text{t}}); $$
(3)

Taking Laplace Transform of the above equation we get,

$$ {\text{s}}{\rm T}({\text{s}}) - \tau (0) = -\uprho{\text{e}}^{{ - {\text{s}}}} {\text{T}}({\text{s}}) +\Delta {\text{T}}({\text{s}}); $$
(4)

where, T(s) and \( \Delta {\text{T}}({\text{s}}) \) are the Laplace transform of \( \tau ({\text{t}}) \) and \( \Delta \tau ({\text{t}}) \) respectively.

Now, to study the system response and establish its stability, we further simplify and consider the system as a causal system, i.e., \( \tau (0) = 0 \) and for\( {\text{t}} < 0 \). Here, we expand\( {\text{e}}^{{ - {\text{s}}}} \), and taking up to first order term the Eq. (4) is represented as,

$$ {\text{s}}{\rm T}({\text{s}}) +\uprho(1 - {\text{s}}){\text{T}}({\text{s}}) =\Delta {\text{T}}({\text{s}}); $$
$$ \Rightarrow \left( {{\text{s}}\left( {1 -\uprho} \right) +\uprho} \right){\text{T}}({\text{s}}) =\Delta {\text{T}}({\text{s}}); $$
$$ \Rightarrow \frac{{{\text{T}}({\text{s}})}}{{\Delta {\text{T}}({\text{s}})}} = \frac{1}{{{\text{s}}\left( {1 -\uprho} \right) +\uprho}} = {\text{F}}({\text{s}}) = {\text{Transfer Function of the deterministic Ant System}}. $$
(5)

The characteristics equation of the deterministic ant system is given by,

$$ {\text{s}}(1 -\uprho) +\uprho = 0 $$
(6)
$$ \Rightarrow {\text{s}} = \frac{{ -\uprho}}{{(1 -\uprho)}} $$
(7)

In the next section we perform the characteristics analysis of the system using ROC.

3 ROC Analysis of Ant Dynamics

In this section we analyze the ant dynamics given in (7) using ROC, and establish the stable operating zone. In this paper, we take the help of Region of Convergence (ROC) to study the characteristics of the ant system and further explore the stability of the system. The stability of the system is ensured from different range of values of ROC which also validates the range of value of the pheromone factor, ρ for ants’ successful operation.

3.1 ROC and Stability Analysis of Ant System Dynamics

The range of values for which, ‘s’ converges for a given signal is known as Region of Convergence (ROC). The ROC gives an idea of the stability of a system and by property it does not contain any poles. The stability of a close loop system can be easily analyzed from its characteristic equation using ROC. Tables 1 and 2 shows the characterization of the Ant system for different values of ρ.

Table 1 Characterization of the deterministic Ant System for \( 0 <\uprho < 1 \) using ROC
Full size table
Table 2 Characterization of the deterministic Ant System for \( 0 <\uprho \), \( \uprho > 1 \), and \( \uprho = 0,1 \) using ROC
Full size table

Table 1 shows the Region of Convergence for \( 0 <\uprho < 1 \). It is seen that the values of pheromone trail within this range give favorable results by including the imaginary axis in its area of convergence. Whereas, for \( \uprho < 0 \) and \( \uprho > 1 \), system does not include the imaginary axis and this make the system unstable. The supportive results are present in Table 2. Again for \( \uprho = 0 \), the pole lie on the origin. Hence ROC does not include the imaginary axis, and it leads to unstable system. But for \( \uprho = 1 \), the poles are located at infinity. Hence the system behavior is unstable. It is clear from Tables 1 and 2 that the value of pheromone trail ρ within \( 0 <\uprho < 1 \) will give successful modeling of the ant system.

So, it is proved that the Ant System is stable for \( 0 <\uprho < 1 \) using ROC. In the next section, we simulate the Ant System on TSP for various values of \( \uprho \) to validate the range of parameters which will ensure the stability of ant system.

4 Simulation Results and Analysis of the Ant System Dynamics

The simulation study is done on TSP to prove the effectiveness of our deterministic modeling of the Ant System, and validates the range of value of the pheromone factor, ρ for ants’ successful operation. The simulation is made in MATLAB-R2010a, ver. 7.10.0.499, in a Windows 7 environment, running on INTEL CORE 2DUO, 2.20 GHz processor, and 3 GB RAM. The efficacy of our proposed algorithm has been tested using Ulysses16.tsp, Ulysses22.tsp and Oliver30.tsp problems (Euclidean 2D distance TSP problems). For simplicity, we have adopted number of ants equal to number of cities (here, the number of ants = 30, for a 30-city problem). Experiments were carried out for 6,000 iterations and were averaged over 20 successive trials for different values of pheromone trail, ρ.

Table 3 analyses the outcome of the Ulysses16.tsp for different values of pheromone trail. Similarly Tables 4 and 5 gives the same outcome for Ulysses22.tsp and Oliver30.tsp problems. From Tables 1, 2 and 3 we find that ant system algorithm behaves successfully when the pheromone trail is \( 0 <\uprho < 1 \). This is the best fit range of ρ for Ant System. This is also been proved from the below figures of simulation. Figure 1a shows the iterative best cost and average node branching of Ulysses16.tsp problem for ρ > 0. Figure 1b shows the same of Oliver30.tsp for ρ < 0, and Fig. 1c of Ulysses22.tsp for ρ = 1. It is found that the system shows premature convergence for all the above values of rho, ρ. Hence, the ant system is unstable for the values of rho, ρ depicted in figures. But, the system converges at high value for ρ = 0 (in Fig. 1d) for Ulysses16.tsp problem.

Table 3 Analysis of Ant System for different values of \( \rho \) for ULYSSES16 problem
Full size table
Table 4 Analysis of Ant System for different values of \( \uprho \) for ULYSSES22 problem
Full size table
Table 5 Analysis of Ant System for different values of \( \uprho \) for OLIVER30 problem
Full size table
Fig. 1
figure 1

The iterative best cost and average node branching of a Ulysses16.tsp problem for ρ = 1.4 (ρ > 1). b Oliver30.tsp problem for ρ = −0.4 (ρ < 1). c Ulysses22.tsp problem for ρ = 1 and d Ulysses16.tsp for ρ = 0. The figures show premature convergence except Fig. 1d

Full size image

Hence it is proved that trail persistence, \( \uprho \) should be \( 0 \le\uprho \le 1 \) for successful operation of Ant System algorithm. The algorithm is unstable for \( \uprho < 0 \), \( \uprho > 1 \). So, we have proved and validated the consolidate range of trail persistence, \( \uprho \) where the Ant System will be stable and will find its optimal solution more effectively.

5 Conclusion

This paper satisfactorily depicts a novel deterministic framework of the linear model of the Ant System and also validated the effective range of trail persistence, ρ where the Ant System will optimize better. This article is the first step in modeling deterministic platform of the ant system. The stability of this closed loop Ant dynamics is confirmed using Region of convergence for an effectual range of pheromone persistence and that is validated with the theoretical values as proposed in literature.