ACODA is a truly distributed framework for Ant Colony Optimization. ACODA is heavily using message passing, so communication costs are quite high. In this paper we formulate the optimization of communication costs in ACODA as a mathematical optimization problem. We analyze the feasibility of its solution using Simulated Annealing.
Ant Colony Optimization on a Distributed Architecture – known
as ACODA is a multi-agent distributed framework for Ant Colony
Optimization (ACO hereafter) [
In fact, with our proposal we identify and exploit fine-grained
parallelism that is inherently present in collective natural
bio-systems, in particular in colonies of natural ants that is the metaphor
behind ACO. According to this view, ACODA can be
conceptualized as a network of computational nodes that are exchanging ant
information according to ACO rules. So, using parallel
computing as source of inspiration, we observed that by defining a
suitable partitioning of the nodes of this network and its mapping to a
high-speed computer network, we can efficiently divide the
communication and computation costs of ACODA among the available
network machines, thus leading to the improvement of the overall
execution time of an ACO algorithm. The problem of defining a
suitable partition of the network of ACODA computational nodes
is an instance of the Graph Partitioning problem (GP hereafter) – a
well-known NP-hard computational problem [
In this paper we propose the use of Simulated Annealing (SA
hereafter) for defining a suitable partition of ACODA
computational nodes. SA is a probabilistic mathematical optimization
method inspired by the physical process of slowly cooling a metal until
its internal structure is frozen to an equilibrium state that represents
the optimal solution of the problem [
Note however that there are various approaches for defining the
optimization criteria of GP [
It is interesting to note that there is an important difference between the standard application of GP to parallel computing problems and its application to optimization of communication costs in ACODA. The standard application assumes that the optimization graph and the partitioning are defined and computed before the execution of the parallel problem solving process. On the other hand, ACODA can be described as a probabilistic search algorithm, so it is impossible to define the graph and the partitioning before the algorithm is run. With our approach the partitioning should be done during rather than before the execution of the parallel problem solving process. 2.
Following [
The cost of exchanging messages between two nodes located on different physical machines is obviously significantly higher than the cost of exchanging messages between two nodes located on the same physical machine. Intuitively, if two nodes exchange a large number of messages they should be located on the same machines, while if they exchange a reduced number of messages they can be safely located on different machines. Therefore the optimal partitioning of the set of nodes should take into account the specific interaction pattern between the nodes that is defined by the execution of ACODA.
We model ACODA as a network of n computational nodes that are mapped onto a high-speed computer network consisting of k physical machines (or processors). The mapping of nodes to machines can be described by a partition p of the set {1, 2, . . . , n} into k sets. For each i ∈ {1, 2, . . . , k} let pi be the set of nodes mapped onto machine i.
During the execution of ACODA we record the number of messages (or ants) mi j exchanged by any two nodes i and j. m is an n × n symmetric matrix. The nodes of the set pi that are mapped to machine i will exchange messages with the rest of nodes, i.e. p¯i = {1, 2, . . . , n} \ pi, so the associated cost can be computed as:
The total communication cost incurred during the execution of ACODA can be estimated as the total number of messages exchanged by the machines, as follows:
Ci(p) =
X j∈pi,l∈p¯i
m jl k C(p) = X Ci(p)
i=1
Let 0 < d < n be a natural number and let q = ⌊n/k⌋, i.e. q is the quotient of the integer division of n by k. A partition p is called d-balanced if for each i ∈ {1, 2, . . . , k} the number of elements of the set pi is bounded as follows: ||pi| − q| ≤ d. This means that the number of elements of pi cannot be larger than q + d and it cannot be smaller than q − d. For example, if d = 1 then each set of a 1-balanced partition can contain either q − 1, q or q + 1 elements.
The GP problem asks for computing a d-balanced partition p such that the total communication cost C(p) is minimum.
SA is a probabilistic mathematical optimization method inspired
by the physical process of slowly cooling a metal until its internal
structure is frozen to an equilibrium state that represents the
optimal solution of the problem [
The key ingredients of the SA algorithm are as follows: • The set S of feasible solutions also known as “problem states”.
In our case this is given by the set p of d-balanced partitions. • For each x ∈ S the set S (x) of its “neighbors”. In our case a neighbor is defined by choosing two distinct sets pi and p j of the partition such that |pi| > q − d and |p j| < q + d and moving one arbitrary element from pi to p j. It is easy to see that the neighbor is correctly defined, i.e. it is a dbalanced partition. Moreover we can always choose pi as the set with the largest number of elements and p j as the set with the smallest number of elements that shows that in our formulation of the GP problem each state has at least one neighbor. • A nondecreasing “temperature” function T : N → R+ also known as “cooling schedule”.
SA starts from a given initial state. It proceeds through an iterative search process without backtracking by randomly choosing in each iteration a neighbor of the current state. SA seeks to improve (i.e. to decrease the value of the cost of) the currently best solution. So most of the time SA will prefer downhill moves. However, in order to avoid being trapped to local minima, sometimes SA allows uphill moves. The selection of uphill moves is controlled by the cooling schedule. SA stops when the improvement of the currently best solution seems highly unlikely (the standard term is that the state is “frozen”).
The SA algorithm is illustrated in Fig. 1. The main source of
inspiration for this algorithm is [
The SA algorithm is using several functions as follows: • neigh_size() that determines an estimation of the number of neighbors of a problem state; • successor that randomly picks up a neighbor q ∈ S (p) of p • cost that determines the value of the current state • random that determines a uniformly distributed random number.
The SA algorithm can also be externally configured using the following three parameters: • S IZ EFACT OR is a real number between 0 and 1 that represents the proportion of neighboring states from the estimated number of neighbors that will be handled in the current iteration • MAX_CNT that represents the maximum number of times the algorithm tries to improve the currently best solution during the current iteration before declaring that the state is frozen • MIN_PERCENT that determines the minimum proportion of moves that must be accepted during the current iteration in order to consider that the further improvement of the currently best solution is still possible, i.e. the state is not frozen.
A crucial aspect of any SA algorithm is the cooling schedule. There are several proposals in the literature: • Linear cooling schedule, defined as: • Logarithmic or Boltzman cooling schedule, defined as: • Exponential cooling schedule, defined as:
Tlin(i) = T0/i
Tboltz(i) = T0/(1 + log i) Texp(i) = T0 ∗ γi, 0 < γ < 1 SIMULATED-ANNEALING(p) 1. C ← cost(p), Cmin ← C, pmin ← p, cnt ← 0 2. i ← 1, trials ← S IZ EFACT OR ∗ neigh_size() 3. while cnt < MAX_CNT do 4. T ← temp(i) 5. acc_moves ← 0 6. for i = 1, trials do 7. q ← succesor(p), C1 ← cost(q), Δ ← C1 − C 8. if Δ < 0 then 9. p ← q, C ← C1, acc_moves ← acc_moves + 1 10. if C < Cmin then 11. pmin ← p, Cmin ← C, cnt ← 0 12. else 13. prob ← exp(−Δ/T ) 14. r ← random() 15. if r ≤ prob then 16. C ← C1, p ← q 17. acc_moves ← acc_moves + 1 18. if acc_moves ≤ trials ∗ MIN_PERCENT then 19. cnt ← cnt + 1 20. i ← i + 1 21. return pmin
Before usage, the cooling schedules must be calibrated by determining a suitable value for the initial temperature T0 (parameter gamma is set in advance to a value smaller than and close to 1, for example 0.95). The calibration process can be achieved by choosing an initial state p and estimating the difference between C(p) and the average value of the neighboring states q of p, i.e.: Δ = ( X
C(q))/|S (p)| − C(p) q∈S (p)
Then, given an initial value for the probability r of accepting uphill moves (used in steps 13-17 of SA algorithm from Fig. 1; usually this is taken as 0.2), Δ can be used to compute T0 by solving the following equation:
r = exp(−Δ/T (1)) for each of the cooling schedules: Tlin, Tboltz and Texp.
Finally, we can provide an estimation of the size of the neighborhood of a given partition p (the value returned by the function neigh_size()) for the GP problem. A neighbor can be in principle determined by choosing an element x of one of the sets of the partition and transferring it to one of the other k − 1 sets of the partition. Taking into account that there are n elements then we can estimate the size of the neighborhood for the GP problem as n ∗ (k − 1). 5.
We have presented our approach and work-in-progress for optimizing communication costs in ACODA – a multi-agent distributed framework for Ant Colony Optimization. We are now in the process of performing an experimental evaluation of this approach. We shall report on our progress in subsequent papers. 6.
This work was partially supported by the multilateral agreement on academic cooperation in 2012 between Serbia (Novi Sad), Romania (Craiova), and Poland (Warsaw and Gdansk) on “Agent Technologies, Tools, Environments, Applications”. 7.