individual colored pheromone in the form of cyan, magenta, and
yellow. Through introducing a novel objective function on a
three-dimensional parameter space, better solutions are reinforced
by adding a given amount of colored pheromone and exploited by
the following ants. With the process of iteration evolving, some
tracks are extracted in the form of nearly straight lines in cyan,
magenta, or yellow. Because our three primary colors based ant
system is developed under the framework of the generic ACO algo-
rithm, the following characteristics should be addressed when
implementation.
An appropriate search space description, so that it lends itself to
incrementally building a solution to the problem.
A stochastic selection behavior based on the value of the heuris-
tic function and on the pheromone information.
A problem-dependent heuristic function that measures the
quality of items that would be added the current partial
solutions.
A rule for pheromone update, which represents how to modify
the pheromone trail like the natural pheromone changes in the
real world.
A clear specification of solution convergence.
3.1. Ant stochastic selection behavior
For a multi-sensor multi-target bearings-only tracking system,
the sampling data from the first four scans are in general utilized
to initiate tracks, thus we obtain four spaces, denoted by
X
1
,
X
2
,
X
3
and
X
4
, respectively, and each is formed through intersecting
bearing measurements (or Line of sights) of the same scan, as
shown in Fig. 2. Suppose that all ants are required to walk from
the first space
X
1
, then to
X
2
,
X
3
, and
X
4
step by step, which
means a complete track should be composed of four position can-
didates sequentially from the four spaces.
Since our algorithm is based on the three primary colors, we
consider three groups of equal number of ants accordingly. Ini-
tially, three groups of ants are mixed together and placed randomly
on position candidates in the first search space
X
1
. Afterwards,
each ant will visit the position candidates in the next search space
probabilistically. In the traditional ACO algorithm, such decision
depends on two parameters, i.e., pheromone amount and prob-
lem-dependent heuristic function. However, in our algorithm, the
pheromone is indicated and replaced by the pheromone color sim-
ilarity. In other words, in the generic ACO algorithm each ant is
able to detect the amount of pheromone on each path, while in
the current version each ant can discriminate the color difference
between the candidates and itself. Besides, compared to the ant
system with different tasks (Xu et al., 2008), this assumption seems
more feasible and reasonable, since ants prefer detecting the
results (e.g., the resulting color on path) to storing the exact
information on the path such as the proportions of pheromone
corresponding to each task.
Suppose that an ant with s
1
pheromone is now located at posi-
tion i in
X
k
(k = 1, 2,3), then the ant will visit position j in the next
search space by applying the following probabilistic formula:
P
ðsÞ
i;j
¼
e
a
D
Eðw
s
;w
j
Þ
g
i;j
P
l2X
kþ1
e
a
D
Eðw
s
;w
l
Þ
g
i;l
; ð4Þ
where e
a
D
Eðw
s
;w
j
Þ
denotes the pheromone color similarity between
the current ant and the path from i to j
2
;
g
i,j
denotes the problem
dependent heuristic function; while
a
is an adjustable positive
parameter whose value determines the degree of pheromone color
similarity among candidates.
It is noted that the smaller the pheromone color similarity
e
a
D
Eðw
s
;w
j
Þ
, the bigger the color difference
D
E(w
s
,w
j
), and moreover,
each ant tends to select a similar color path as its destination. To
eliminate the effect of outliers and simplify the computation of
each ant,
g
i,j
is defined as below
g
i;j
¼
1ifr
1
6 D
i;j
6 r
2
; j 2
c
;
j
otherwise;
ð5Þ
where
j
is a constant and takes a value between 0 and 1, D
i,j
is the
distance between i and j, and
c
is denotes an annular gate region
whose inner and outer radiuses are determined respectively by
r
1
= k
v
min
kT and r
2
= k
v
max
kT with sampling interval T, as shown
in Fig. 3.
It is observed that, according to Eqs. (4) and (5), each ant should
be capable of calculating the color similarity between other candi-
dates and itself before its decision is made. Even though some can-
didate does not lie in the range of
c
, the ant will probabilistically
visit it for a big color similarity value. On the other hand, although
there exists a big color difference between two candidates, which
leads to a small value of color similarity, there is a possibility for
the ant to visit the candidates in or out of range
c
. It is observed
that, therefore, such strategy is to increase the searching ability
of each ant and avoid the negative effect of local optimal solution.
While walking from i to j, the ant with s pheromone deposits its
corresponding color pheromone with a given amount
s
s
0
as
s
i;j
s
i;j
þ
s
s
0
; ð6Þ
where
s
s
0
is the added local pheromone amount with color s, and
s
i,j
is the resulting pheromone through mixing three primary colors
with their individual amounts.
Remarks:
(1) In the generic ACO, the pheromone evaporation is consid-
ered (denoted by
a
in Dorigo & Gambardella (1997)); while
in our proposed ant system, the evaporation term is ignored
Table 1
Color difference for various color pairs.
A Pair of Colors in CMY Space
D
E(w
1
,w
2
) in CIE LAB Space A Pair of Colors in CMY Space
D
E(w
1
,w
2
) in CIE LAB Space
(C =1,M =0,Y =0)
156.6501
(C =0,M =0,Y =1)
10.6768
(C =0,M =1,Y =0)
(C = 0.2,M = 0.2, Y =1)
(C =1,M =0,Y =0)
111.9828
(C =0,M =1,Y =0)
28.5771
(C =0,M =0,Y =1)
(C = 0.5,M =1,Y = 0.5)
(C =0,M =1,Y =0)
199.5695
(C =1,M =0,Y =0)
24.3943
(C =0,M =0,Y =1)
(C =1,M = 0.5,Y = 0.5)
1
Without loss of generality, s = 1, 2, 3 represents cyan, magenta, and yellow,
respectively.
2
Note that the color on path ij is represented by the color of position j.
B. Xu et al. / Expert Systems with Applications 38 (2011) 9809–9820
9811