fine-grained model named parallel ant to solve the traveling salesman problem (TSP). This algorithm has most difficulty in
handling the synchronous refreshment of the pheromone matrix on the master-slave structure. Michel and Middendorf [27]
embedded the idea of island model in the ACO and set up a coarse-grained ant system with the best solution exchanged at a
fixed frequency.
In recent study, the multi-colony PACO gradually wins over the other two types of PACO because of its more proper com-
munication manner and better adaptability to different problems. However, the ants’ migration among different colonies re-
mains a major problem [28]. Actually, this problem widely exists in all kinds of parallel algorithms with multiple populations
[6–10]. Many researches have been conducted on the timing and the contents of the migration. The timing of migration is
critical to the parallel algorithms. Either over-frequent or too few migration will do harm to the efficiency of the paralleliza-
tion. Frequent migration disseminates information in time but also increases the communication cost devastatingly. Sparse
migration isolates the colonies and weakens their cooperation. The contents of the migration are important for balancing the
exploration and the exploitation [7,8]. Moreover, the size of the contents also influences the communication cost.
Based on the multi-colony model, this paper proposes a pseudo PACO in the continuous domain. The aforementioned
multi-colony PACO optimizes the same object with different colonies. Thus, each colony still faces the same difficulty with
the sequential ACO (SACO) when solving large-scale problems. However, the proposed PACO drives different colonies to opti-
mize different parts of the objective function, which directly reduces the scale of the optimized object for each colony. There-
fore, the proposed PACO is especially suitable for the problems of large scale and high dimension.
In order to solve the problem of migration, this paper introduces a stagnation-based asynchronous migration controller
(SAMC). The SAMC analyzes the degree of the stagnation in each colony, then adjusts the colony’s migration frequency and
migration contents accordantly.
Finally, the proposed PACO with the SAMC is testified on a set of benchmark functions of different dimensions. The exper-
iments will carefully examine the efficiency of the proposed method in high dimensional space.
The rest of the paper is organized as follows: Section 2 briefly introduces the continuous ACO as the basis of the proposed
parallel strategy; Section 3 implements the proposed PACO with the SAMC; Section 4 displays the numerical experiments
and related discussions; Section 5 draws a conclusion for the whole paper.
2. A brief introduction to the ACO in the continuous domain
To testify the proposed parallel strategy and the SAMC, this paper uses an improved version of the continuous ACO from
literature [21]. The following paragraphs explain the operating process of this algorithm.
2.1. Initialization
As for a continuous problem of n dimensions, the algorithm assigns a random vector X(x
1
,x
2
,...,x
n
) to each ant. For every
variable in every ant, a pheromone weighting
s
0
is attached to it.
After evaluating each ant and sorting them from best to worst, the pheromone
s
i
j
on variable j(j =1,2,...,n) of ant
i(i =1,2,...,N) is modified according to the ant’s rank k
i
like (1). Thus those pheromones on the variables of the best GN solu-
tions are enhanced according to the emphasized rate
a
and their ranks.
s
i
j
¼
s
i
j
þ
a
ðGN þ 1 k
i
Þ
s
0
; k 6 GN ð1Þ
2.2. Selection
After the initialization, the colony obtains a set of values on each variable. If the random number p
1
is larger than the first
selection probability q
1
, the ant is directly copied into the next iteration. Otherwise, the ant is reconstructed by selecting
values for each variable from the corresponding set. The selection follows the pseudo random rule of the ant colony system
[11]. The pseudo random rule includes exploitation and exploration, the proportion of whom is determined by the second
selection probability q
2
. Suppose x
i
j
ði ¼ 1; 2; ...; N; j ¼ 1; 2; ...; nÞ represents the value on the jth dimension of the solution
in ant i. As it is shown in (2), if the random number p
2
is no bigger than q
2
, exploration selects the value with the largest
pheromone; otherwise, the algorithm will execute the exploitation. J in (2) is the value picked out by the roulette wheel
selection according to the probability of (3). Fig. 1 describes the selection, where ant 2 is reconstructed. The thickness of
the color in the circles corresponds to the amount of pheromones. As it can be seen, the values with more pheromones have
better chances to be selected.
x
i
j
¼
arg maxð
s
k
j
Þ
x
k
j
ðl6k6NÞ
; p
2
6 q
2
J; otherwise
8
>
<
>
:
ð2Þ
pðx
i
j
Þ¼
s
i
j
P
N
l¼1
s
l
j
ð3Þ
678 Y. Lin et al. / Applied Mathematics and Computation 205 (2008) 677–687