به روز رسانی فرمون (نامتغیر) در دو مرحله با الگوریتم بهینه سازی کلونی مورچه

Ant colony optimization (ACO) is a metaheuristic approach for combinatorial optimization problems. With the introduction of hypercube framework, invariance property of ACO algorithms draws more attention. In this paper, we propose a novel two-stage updating pheromone for invariant ant colony optimization (TSIACO) algorithm. Compared with standard ACO algorithms, TSIACO algorithm uses solution order other than solution itself as independent variable for quality function. In addition, the pheromone trail is updated with two stages: in one stage, the first r iterative optimal solutions are employed to enhance search capability, and in another stage, only optimal solution is used to accelerate the speed of convergence. And besides, the pheromone value is limited to an interval. We prove that TSIACO not only has the property of linear transformational invariance but also has translational invariance. We also prove that the pheromone trail can limit to the interval (0, 1]. Computational results on the traveling salesman problem show the effectiveness of TSIACO algorithm.

Ant colony optimization (ACO) is a cooperative algorithm inspired by the foraging behavior of real ant colonies. The first ACO algorithm, called ant system (AS), was initially proposed in Dorigo, Maniezzo, and Colorni (1996) and applied to the solution of the TSP, but it was not able to compete against the state-of-the art algorithms in the field. In the next years, many ACO algorithms have been developed to improve the performance of AS. The main ACO algorithms presented in the literatures are: Ant-Q system (Gambardella & Dorigo, 1995), ant colony system (ACS) (Dorigo & Gambardella, 1997), max–min ant system (MMAS) (Stützle & Hoos, 2000), rank-based ant system (ASrank) (Bullnheimer, Hartl, & Strauss, 1999). After the initial proof-of-concept application to the traveling salesman problem (TSP) (Ellabib et al., 2007, Favaretto et al., 2006 and Wu et al., 2009), ACO was applied to many other combinatorial optimization problems. Examples are the applications to quadratic assignment problems (QAP) (Gambardella, Taillard, & Dorigo, 1999), job-shop scheduling problems (Heinonen and Pettersson, 2007 and Udomsakdigool and Kachitvichyanukul, 2008), vehicle routing problems (Bell and McMullen, 2004 and Montemanni et al., 2005), and set covering problems (Lessing, Dumitrescu, & Stützle, 2004). With many more novel implementations of ant algorithms being developed, continuous optimization is an example of broad application area for ACO (Socha & Dorigo, 2008). In comparison with the application on ACO algorithms in recent years, the theoretical foundation of this randomized search heuristic is rather weak. Up to now, convergence results (Gutjahr, 2000 and Stützle and Dorigo, 2002) have been achieved showing that optimal solutions can be obtained in finite time with probability one. Recently, Neumann and Witt (2009) presented runtime analysis of an ACO algorithm called the 1-ANT with specific lower and upper pheromone bounds on the pseudo-Boolean function and One-Max function. Runtime analysis of ACO algorithm is attracting more attention (Gutjahr, 2008, Gutjahr and Sebastiani, 2008 and Zhou, 2009). Invariance property of ACO algorithms has also been studied by a few authors. This property is definitely desirable for at least two main reasons: first, it reduces possible numerical problems in the implementations and contributes therefore to enhance the stability of the algorithm; second, it greatly improves the readability of the solution process (Birattari, Pellegrini, & Dorigo, 2007). As ACO algorithms using the pheromone model belong to the class of model-based search (MBS) algorithms (Zlochin, Birattari, Meuleau, & Dorigo, 2004). The model does not change but the value of pheromone trail update by using the previously generated solutions to generate high-quality solutions increases over time at runtime. It is undesirable property that the pheromone values strongly depend on the scale of the problem. Blum and Dorigo introduced the hypercube framework (HCF) and were first to raise the issue on the invariance of ACO algorithms to transformation of units (Blum & Dorigo, 2004). In order to achieve the strong invariant property, the quality function is employed to normalize the added amount of pheromone in HCF. Birattari has shown the performance of standard ACO algorithms is independent of the scale of the problem under some conditions (Birattari et al., 2007). That is, the sequence of solutions of ACO algorithms finding is independent of the scale of the problem. The strongly invariant ACO algorithms were also introduced to compare with hypercube framework. In this paper, we introduce two-stage updating pheromone for invariant ant colony optimization (TSIACO) algorithm. In TSIACO algorithm, ordinal update rule is introduced, the pheromone update by two stages and the range of values of the pheromone trail is limited to the interval. Compared with standard ACO algorithms, the quality function uses the solution order as its independent variable in one iteration. The benefit of using order is that the pheromone values can independent to objective function values, so the ACO algorithms equipped with it have the invariance naturally. The bound and added pheromone trail is independent to the function values. To make this novel work more useful in practice, two specific algorithms are given in following section. The rest of this paper is organized as follows. In Section 2, we review the AS based on construction graph and introduce some preliminary concepts used in following section. We propose two stages invariance ant colony algorithm and prove its invariance property in Section 3. Section 4 presents some computational results which take the example of TSP. In Section 5, we conclude this paper and outline future work.

In this paper, we have proposed an invariance ACO algorithm, called TSIACO algorithm. Compared with other ACO algorithm, its main feature is using the solution order as quality function independent variable. The pheromone trail updates by solution order, called ordinal update rule. The pheromone tail limits to the interval of subset (0, 1] and the amount of added pheromone trail has nothing with functional value. So, the novel algorithm is invariance algorithm inherently. To make the novel algorithm more practical, we use two stages update rule for updating pheromone trail. In first stage of algorithm, the first r iterative optimal solutions are employed for updating pheromone to enhance search capability. Then, in the second stage of algorithm, only iteration-best optimal solution or global-best optimal solution is used to accelerate the speed of convergence. We prove the linear transformation invariance and translational invariance property for TSIACO algorithm under the condition of initializing the pheromone as the same way for two instances. We also give two methods to determine the update stage. One is hard partition and another is soft partition. The major work of this paper is given another choice to construct invariance ant colony algorithm compared with the hyper cube frame work. One of benefits of using solution order is that it can avoid inconvenience of setting the bounder of pheromone trail compared with MMAS. This is similar to implement MMAS with HCF. Computation results show the feasibility of this work. From the practical view, there is also much work of improving the efficiency and setting parameters for TSIACO algorithm to do in future.