2012 International Workshop on Nonlinear Circuits,Communications and Signal Processing
NCSP'12, Honolulu, Hawaii, USA. March 4-6, 2012

Combinatorial Optimization
by Cooperative Mechanism of Ant Colony and Aphid
Naoto Hara, Yudai Shirasaki, Sho Shimomura, Yoko Uwate and Yoshifumi Nishio
Tokushima University
Tokushima 770-8506, JAPAN
Phone/FAX: +81-88-656-7470 / +81-88-656-7471
Email: {naoto, shirasaki, s-sho, uwate, nishio}@ee.tokushima-u.ac.jp

Abstract
In this study, we propose an optimization method by thecooperative mechanism of ant and aphid as a new Ant ColonyOptimization (ACO). This algorithm is named Ant Colony
Optimization with Cooperative Aphid (ACOCA). In ACOCA
algorithm, the aphid searches neighborhood solutions. Thissolution information is treated as a honey obtained from theaphid and the honey affects the search of ACO. Moreover, theaphid shares a solution information with the ant. We apply
ACOCA to three Traveling Salesman Problems (TSPs) andconfirm its effectiveness.
1. Introduction
The ant takes communication with other ants at feeding
action by using a pheromone and find the shortest path fromfeeds to a nest. Ant Colony Optimization (ACO) was developed by this mechanism [1]. ACO is applied to various
combination optimization problems, for example, Traveling
Salesman Problem (TSP) [2], vehicle routing problem, graphcoloring problem, and so on. In these problems, TSP is solved
by various optimization algorithms. We provide a simple
explanation about TSP. City coordinates are given and thesalesman leaves first city, visits all cities, and returns to thefirst city. TSP is the problem which finds the shortest tour inthe combination of the tours.
In ACO algorithm for solving TSP, a number of ants exist
and they find a number of solutions. Ants trail a pheromone
on the path between cities. The pheromone is updated depending on behavior of ants, and the ants find tours according to the strength of the pheromone trail on the path. In
other words, when the ants take communication with otherants through the pheromone trail on the path, ACO can findthe optimal solution. However, ACO has a problem of being
easy to fall into a local minimum solution. Therefore, it is important to adjust the diversity of the algorithm and to improve
performance.
By the way, there are ants which live in cooperation withaphids [3]. The aphid has a number of natural enemies and iseasily attacked because it has little defensive power. Therefore, in order to accommodate with natural enemies, the aphid
has an interesting mechanism. The mechanism is a cooperative relation with the ant. The aphid sucks at nutrients from aplant and discharges them from the anus as honey. The aphid
gives honey to ants. Since honey is a favorite food of ants,
the ants obtain much honey in return for defend aphid fromnatural enemies [4]. In this way, there is cooperative relation in an ant and an aphid. Moreover, although the aphid iseaten by a lot of natural enemies, it has tremendous procreative power. If the number of the aphids increases too much,it sucks all nutrients of the plant. Because the plant which
sucked all nutrients withers, the aphid cannot survive. Therefore, if a number of the aphid increases too much, it is carried
to another plant by the ant and begins to propagate on newplant. The aphid repeats this step and propagates.
In this study, we propose Ant Colony Optimization with
Cooperative Aphid (ACOCA) and we apply the feature of theaphid and this cooperative relation to optimization algorithm.
In ACOCA algorithm, ant and aphid operate in parallel andgive solution. The solution information obtained from aphid
is treated as a honey and the honey affects the search solutionsof ant. We apply ACOCA which have the cooperative relationof ant and aphid to three TSPs and confirm its effectiveness.
2. ACO [5]ACO finds the solutions by repeating the following processes.
1. Ants are set on the cities at random.
2. Each ant choose a path by the probability based onpheromone and heuristic information.
3. Pheromone is updated depending on obtained solutions.
Figure 1 shows the choosing method of the path by the ant.
In this figure, the ant tends to choose the path which is nearand has many quantity of pheromone.

- 477 -

will be moved by an ant. Movement of the aphid means receiving the solution of ant. At this time, the number of aphids
decreases.

bpab (t ) = 30%
k3.2. Algorithm of ACOCA
apac (t ) = 20%
kpad (t ) = 50%
kcdFigure 1: The ant tends to choose the path which is near and has many
quantity of pheromone.

0

3. ACOCA
3.1. Feature of ACOCA
In this study, we adopt the following three cooperative relations.
1. Ant likes honey of aphid.
2. Aphid propagates and increases gradually.
3. Instead of honey, ant carries aphid to feeding area (plant).
In order to take in these three elements to the algorithm, weconsider the following three features on a program.
1. The aphid performs local search, and searches the neighborhood solution of the present solution. There are variousmethods such as simulated annealing [6], hill-climbing [7],and tabu search [8] in a local search. Search of aphid arebased on simulated annealing. The transition probability ofthe solution changes by the number of aphids. When the number of aphids is small, it is equal to random search. When thenumber of them increases, it changes from random search tolocal search. Moreover, the evaluation value of the solution
obtained from the aphid called the honey. This honey affects
the search of ant. When the ant chooses a path, ”honey” isadded as new information and affects choosing path of ant.
Although honey is similar to the pheromone, search of aphid
is unaffected by honey. Moreover, the aphid is unaffected bya pheromone.
2. Express the number of aphids as the search times. Moreover, the number of aphids increases while searching for solution. The ant and aphid operate in parallel and give solution.
Although an ant gives only one solution, an aphid gives pluralsolutions.
3. The number of aphids increases while searching for thesolution, but if it increases to a constant number, the aphid[Step 1 (Initialization)]
Let iteration number t = 0. τij (t) is the quantity ofpheromone trail on the path (ij) between cities i and j attime t, and τij (t) is initially set to τ0 . ij(t) is the quantity ofhoney trail on the path (ij) between cities i and j at time t,and ij (t) is initially set to 0 .
[Step 2 (Find tour)]· Find tour of ACO:
For the k-th ant (k = 1, 2, · · ·, M ), the visiting city is chosen by probability pkij (t). ACOCA uses two kinds of pkij (t)according to conditions. The k-th ant finds a tour according
to the following[τij ]α [ηij ]β [ij ]∑, if La ≥ LA
αβh=Ω [τih ] [ηih ] [ih ]kpij (t) =(1)[ηij ]β [ij ]γ ∑,otherwise,βγh=Ω [ηih ] [ih ]where LA is the best tour length of ants at t, La is the best
tour length of CA at t. Ω is a set of cities which ants are
not visiting yet. τ is quantity of pheromone, η is heuristic
value (inverse the distance between cities) and  is quantityof honey. α, β, and γ are the control parameters of τ , η, and, respectively.
· Find tour of CA:
1: Cities are set at random and tours are created. This tour
length is the present state s.
2: Exchange two of the cities of city permutation at random
and tours are created. This behavior is conducted for the number of cities, and minimum length of tours is the neighborhood state e.
3: Compare e with s and the present state is updated according to the result. CA finds a tour according to the following
equations;sb = s(t),if sb ≥ s(t)s(t) ≥ e,
 e,s(t) < e, : f ollow the prob. pa (t)s(t+1) = e,s(t), s(t) < e, : f ollow the prob. pa (t)

(2)

(3)

where sb is the best state, pa is transition probability and isshown by Eq. (4).

- 478 -pa (t) = exp− lmax,lstart − lmax

(4)

where lmax is the maximum number of aphid, lstart is thedefault number of aphid. l is updated by Eq. (5).
{l(t + 1) = l(t) + 1,l(t + 1) = lstart ,if l(t) = lmax ,(5)Startwhere l is the number of aphids at t. When under equation
is applied and t is bigger than te , the best tour of ant at t isgiven to the aphid. It performs local search for the given tour.
[Step 3 (Pheromone update)]
Compute the tour length LA (t) and update the quantity of thepheromone trail between i and j by the following equation;
τij (t + 1) = (1 − ρ)τij (t) +M∑

Parameter initialization
t＝１
Present solution of ｍ-th aphid sets up random city permutation
Ants set up to the city at randomm = m+1k∆τij(t),(6)Search of a neighborhood solution

k=1No{k∆τij(t) =All aphids find the tour

1/Lk ,0,if tour made by antotherwise,

Yes(7)

k-th ant moves to the city j from the city i according to the prob. pijk

where ρ ∈ [0, 1] is the evaporation of pheromone trail coefficient. The pheromone trail of all path evaporates and thepheromone is added to the path.
[Step 4 (Honey update)]
Compute the tour length La (t) and update the quantity of thehoney by the following equation;

NoLa>LAk = k+1

Yes
A path is chosen by τ , m and ηNo

A path is chosen by m and η

All ants find the tour

ij (t + 1) = 1/La ,(8)where  is the quantity of honey.
[Step 5]
Let t = t + 1. Go to [ACOCA 2] and repeat until the maximum time limit t = tmax .

YesCompute the optimal tour of ACO and CAt = t+1

Update of pheromone and honeyl=l+1
l = l max

4. Numerical Simulations

Yesl = l start

In order to confirm the effectiveness of ACOCA, we apply
ACOCA to three TSPs, att48, st70 and kroA100. The numberof simulations of att48, st70 and kroA100 is 100 times.
[Parameter setup]
M (number of ants): 48 (att48), 70 (st70), 100 (kroA100),t (iteration count) = 2200,
α (control parameter of pheromone) = 1,β (control parameter of heuristic value) = 5,γ (control parameter of honey)= 1∼9,
ρ (evaporation coefficient) = 0.3,lstart (the default number of aphid) = 400,lmax (the maximum number of aphid) = 600,
te = 1500.
In order to investigate the effect of honey, γ = 1∼9 are used,and we confirm the optimal value of γ. Moreover, ACOCA
uses the upper equation in Eq. (1) until t= 500. Because thehoney has a bad influence on ACO in the early step.

- 479 -Not > teYes
The best solution of ACO is given to CAt＞ｔmaxNo

Yes
EndFigure 2: Flowchart of ACOCA.

No

Table 1: Results of ACOCA: γ = 1∼9, for att48, st70 andkroA100.

γ

1 AVG
MIN
2 AVG
MIN
3 AVG
MIN
4 AVG
MIN
5 AVG
MIN
6 AVG
MIN
7 AVG
MIN
8 AVG
MIN
9 AVG
MIN

att48
1.60 %0%
1.39 %0%1.40 %0%1.37 %
0%1.53 %
0%1.57 %
0%1.39 %
0%
1.48 %
0.10 %
1.43 %
0%st70 kroA100
4.29 % 11.14 %0.40 % 7.76 %4.98 % 11.07 %1.96 % 8.39 %3.90 % 11.02 %0%
3.16 %
3.78 % 10.62 %0%2.93 %
4.02 % 11.14 %1.00 % 6.45 %4.06 % 10.94 %0.10 % 6.63 %3.95 % 11.22 %0.48 % 7.50 %3.95 % 11.28 %1.25 % 7.02 %4.11 % 11.05 %0.74 % 5.41 %5. Conclusion
In this study, we proposed an optimization method by thecooperative mechanism of ant and aphid as new ACO. Thisalgorithm is named Ant Colony Optimization with Cooperative Aphid (ACOCA) and ACOCA obtained the better results than the standard ACO. From this result, we can say that
ACOCA is more effective algorithm than the standard ACO
for solving TSPs.
References[1] M. Dorigo and T. Stutzle, Ant colony optimization, Bradford books, 2004.
[2] M. Dorigo, G. D. Caro and L. M. Gambardella, “Ant algorithms for discrete optimization,” Artificial life, vol. 5,no. 2, pp. 137-172, 1999.
[3] C. Nielsen, A. A. Agrawal and A. E. Hajek, “Ants defend
aphids against lethal disease,” Biology letters communityecology, vol. 6, no. 2, pp. 205-208, 2009.

Table 2: Results of the standard ACO and ACOCA for att48,
st70 and kroA100.

ACO

AVG
MIN
ACOCA AVG
MIN

att48
st70 kroA100
2.59 % 5.41 % 12.49 %1.65 % 4.25 % 10.36 %1.37 % 3.78 % 10.62 %
0%0%
2.93 %[4] I. D. Phillips and C. K. R. Willis, “Defensive behaviorof ants in a mutualistic relationship with aphids,” Behavioral ecology and sociobiology, vol. 59, no. 2, pp. 321325, 2005.
[5] M. Dorigo and C. Blumb, “Ant colony optimization theory: a survey,” Theoretical computer science, vol. 344,pp. 244-245, 2005.
[6] P. J. M. Laarhoven and E. H. L. Aarts, “Simulated annealing,” Local search in combinatorial optimization, pp.
91-120, 2003.

[Simulation results]
The simulation result of γ = 1∼9 is shown in Table 1. The
numerical value in the Table 1 is the average error and minimum error of solution obtained from simulations. The minimum error is given by Eq. (9).

M IN =and kroA100. Moreover, the simulation result of ACO andACOCA is shown in Table 2. In Table 2, we can confirm
that ACOCA obtains better results than the standard ACO inthree TSPs. From this result, we consider that honey has agood effect on search solution of ACO. Moreover, although
the standard ACO can not find the optimal tour, ACOCA canfind the optimal tour by exchange of solution information.

[7] L. Rueda and V. Vidyadharan, “A hill-climbing approach
for automatic gridding of cDNA microarray images,”
IEEE/ACM Transactions on Computational Biology andBioinformatics, vol. 3, pp. 72-83, 2006.
[8] F. Glover, “Tabu search: a tutorial,” Interfaces, vol. 20,no. 4, pp. 74-79, 1990.

(Best tour in all sims) − (Opt. tour)
×100 (9)Opt. tour

AVG is an average error of all simulations. From Table 1,
it turns out that γ = 4 is the best parameter in att48, st70

- 480 -