Description of the CIAC algorithm
A New Ant Colony Algorithm Using the Heterarchical Concept Aimed at Optimization of Multiminima Continuous Functions
par nojhan le 6 mars 2003
Congrès : ANTS’2002
Abstract
Ant colony algorithms are a class of metaheuristics which are inspired from the behaviour of real ants. The original idea consisted in simulating the stigmergic communication, therefore these algorithms are considered as a form of adaptive memory programming. A new formalization is proposed for the design of ant colony algorithms, introducing the biological notions of heterarchy and communication channels. We are interested in the way ant colonies handle the information. According to these issues, an heterarchical algorithm called "Continuous Interacting Ant Colony" (CIAC) is designed for the optimization of multiminima continuous functions. CIAC uses two communication channels showing the properties of stigmergic and direct communications. CIAC presents interesting emergent properties as it was shown through some analytical test functions.
Introduction
Having recently given raise to a new metaheuristic method, the ant colony metaphor proved to be a successful approach to solve "difficult" optimization problems. The first algorithm inspired from the ant colony functioning is the "ant system" ([Colorni91]), which has been applied to many combinatorial problems. Until now, there are few adaptations of such algorithms to continuous optimization problems. The first algorithm designed for continuous function optimization was CACO (for Continuous Ant Colony Optimization) ([Bilchev95]) which comprises two levels : global and local. CACO uses the ant colony framework to perform local searches, whereas global search is handled by a genetic algorithm. Indeed, the "global" ants perform a simple evaluation of some regions defined in the search space, in order to update the regions fitness. The creation of some new regions is handled by a process very similar to a genetic algorithm, using common operators that are assimilated by the authors to some real ants colonies behaviour like "random walk" (playing the part of crossovers and mutations). The local level is handled by ants that explore more systematically the regions with a simple descending behaviour, in order to move regions closer to the optimum. The algorithm sends some local ants on regions, these ants lay down some pheromonal spots when they find an improvement of the objective function and the spots are attractive for all the ants of the colony. This process is close to the original metaphor, but unfortunately, the use of two different processes inside the CACO algorithm leads to a delicate setting of parameters.
All of these algorithms use a particular trait of real ants behaviour : the pheromonal trail laying (Fig. [Mobilization]a). Indeed, ants colonies are often viewed as distributed systems capable of solving complex problems by the way of stigmergy, which is a form of indirect communication mediated by modifications of environment. But the trail-laying behaviour is also a part of the recruitment process, as the recruitment is defined by biologists as "a special form of assembly in which members of a society are directed to some point in space where work is required" ([Holldobler90, , p.642]). According to this definition, another optimization method has been developed for continuous optimization. The API algorithm is inspired by primitive ants behaviour ([Monmarché00]). API uses a "tandem-running" which involves two ants and leads to gather the individuals on a same hunting site. The authors use this particular recruitment to make the population proceed towards the optimum, by selecting the best point among those evaluated by the ants. This procedure seems to be very similar to an enhanced random search as this algorithm makes a poor use of memory that generally characterizes ant colony systems ([Taillard98] ).
Our point of view is that ant colony metaphor can be defined as a model using stigmergy or, more widely, as a recruitment process. According to this idea, pheromonal trail laying may not be the only way to comprehend the ant colony metaphor for optimization problems. Our recent research on modelling ants behaviour ([Dreo01]) has shown that it is possible to start a recruitment sequence without taking pheromonal trails into account. In this model, the stigmergic processes are deliberately ignored and we focus on the inter-individuals relationships. The model tried to reproduce the flow of ants exiting the nest after the entry of a scout who has discovered a new food source. To differentiate this process from the stigmergic recruitment, we called it mobilization (Fig. [Mobilization]b). The mobilization is also a form of recruitment process : a scout comes back into the nest after having located a food source and induces the outing of several ants. We have shown that, through a simple modelization of trophallaxies (an exchange of liquid food between two individuals), a colony of ants can solve problems, like adapting the amplitude and the speed of the exiting flow to the scout’s state. The main mechanisms involved in the response are the ants state distribution and the propagation of the mobilization information. Such a model suggests that the importance of inter-individuals communication may be underestimated, and that including it into an ant colony system may improve performances by accelerating the diffusion of information.
Two views of the recruitment process
We were interested by these various ways of approaching the same idea and we thought that it would be useful to gather them in a single formalism. Indeed, there is another interesting way of approaching the social insects behaviour : the notion of dense heterarchy, developed in Sect. [DenseHeterarchy]. As it is explained in Sect. [DenseHeterarchy_BioDefinition], this is originally a description of the way the ant colony works from the point of view of communication, but we propose in Sect. [DenseHeterarchy_Algorithms] a simple formalization in order to use this notion to design an optimization algorithm. An heterarchical algorithm takes advantages from a flow of information passing through a population of agents. These informations are exchanged using communication channels and permit that a form of description of the objective function emerges from the system. The new heterarchical algorithm that we have implemented is called CIAC, for Continuous Interacting Ant Colony. This paper comprises six more sections. In Sect.[DenseHeterarchy], we describe the notion of dense heterarchy. The communications channels used in CIAC are discussed in Sect. [CIAC]. The subsequent Sect. [CIAC_algo] is devoted to the presentation of the CIAC algorithm. Then we discuss in Sect. [CIACTuning] the tuning of CIAC parameters. In Sect. [Results], we present some experimental results. Conclusion makes up the last section.
The Notion of Dense Heterarchy
A Biological Definition
This notion was firstly introduced by Wilson in 1988 to describe the information flow inside an ant colony ([Wilson88]) :
"[An] ant colony is a special kind of hierarchy, which can usefully be called a heterarchy. This means that the properties of the higher levels affect the lower levels to some degree, but induced activity in the lower units feeds back to influence the higher levels."
In this idea, the two communication channels that we have evoked in the introduction are present, the stigmergic channel as well as the direct communication between individuals. Indeed, these two channels are relatively important for the ants and thus are good examples to comprehend the notion of heterarchy. One of the important issues here is that informations flow through the colony, each of the ants can communicate with any other (which makes the heterarchy being dense).
This process constructs a kind of densely connected network which is not set up in a hierarchical but in a heterarchical manner. A good metaphor consists in emphasizing the opposite behaviour of an ant colony in comparison with that of a human army, where a general gives orders to a colonel who commands a group of lieutenants and so on... In the ant colony, contrary to a popular belief, the "queen" doesn’t tell to the workers what to do, but is only a part of the network (cf. Fig. [HierarchyVSHeterarchy] ).
Such a system has emergent properties, indeed if each agent operates with elementary rules and a limited accuracy, the whole population organized in heterarchy with mass communication can show an emergent pattern. These findings are well known in the study of self-organization ([Camazine00]).
To summarize, the notion of dense heterarchy describes the way the ant colony handles the informations that it receives from the environment. Each ant can communicate with any other at any time and the informations flow through the colony.
Heterarchical Algorithms
We propose here a simple formalization in order to apply the notion of dense heterarchy to an optimization problem. The main concept for implementing such an heterarchical algorithm is the idea of communication channel (cf. Fig. [CommunicationChannel]). A communication channel may be, to take an example in the "ant metaphor", the lay of pheromonal trail. These channels transmit an information, here the localization of a food source, and have some properties, like stigmergy and memory.
For example, some basic properties of the channels are listed below :
Scope : the way the information goes through the population. A sub-group of the population (from one to n agents) can exchange informations with another group of agents.
Memory : the way the information persists in the system. The information can be stored during some period of time or be transitory.
Integrity : the way the information is evolving in the system. The information can be modified, by one or more agents, by an external process, or not.
These properties can be combined in the same channel, so that a large variety of different channels can be built.
The information transmitted during the communication can take many forms, from a simple value to a complex "object" , therefore it is difficult to describe some particular classes. The more intuitive ones are for example the vector coordinates of a point and the value of the objective function at this location.
As an example, lets take a look at the properties of the "trail laying" channel. Basically, the scope is potentially the whole population, as each ant can perceive the trail pheromone. There is also a form of memory, as this is a stigmergic process, the trail persists in the environment during a certain period of time. Finally, the integrity of the channel permits that the informations are damaged by the time, as the pheromones evaporate.
The CIAC communication channels
The design of the CIAC algorithm is quite simple, under the look of the heterarchical concept. We have implemented three versions, each one defined by the type of communication channel it uses. As we will see in next sections, this is very useful to comprehend the way the algorithm works.
The Stigmergic Channel
The first version of CIAC algorithm is trying to be as close as possible to a continuous version of the original ACO (Ant Colony Optimization) algorithm ([Colorni91]) which was designed for combinatorial problems. Due to this assumption, it has somewhat the same design as the local search part of the CACO algorithm ([Bilchev95]), which was also inspired by the first Ant System.
This implementation uses only one communication channel which is inspired from the trail laying behaviour of ants. Here, each ant can deposit a certain amount of pheromone as a spot on the search space, proportionally to the amelioration of the objective function she founds on her way. These pheromonal spots can be perceived by all the members of the population, and diffuse into the environment. The ants are attracted by each spot according to its distance and to the amount of pheromone it contains (cf. ). The agents are moving towards the gravity center $G_j$ of the pheromonal spots cloud. The position of the gravity center depends on the interest $\omega _ij$ of the $j^th$ ant for the $i^th$ spot. \beginequation G_j=\sum _i=1^n\left(\fracx_i\cdot \omega _ij\sum _i=1^n\left(\omega _ij\right)\right)\quad \mbox with\quad \omega _ij=\frac\overline\delta2\cdot e^\left(-\theta _i\cdot \delta _ij\right)\labelEquation_CentreGravite\endequation
Here, $n$ is the number of spots and $x_i$ the position of the $i^th$ spot. The variables involved in the calculation of the interest $\omega _ij$ are : $\overline\delta $ the mean distance between two agents in the population, $\theta _i$ the amount of pheromone laid on the spot and $\delta _ij$ the distance between the $j^th$ ant and the $i^th$ spot. It is important to notice that at this point each ant doesn’t go directly on the gravity center. Indeed, each artificial ant has a "range" parameter (noted $\phi _j$) that is normally distributed over the population. Each artificial ant draws a random distance, under the limit of her range parameter, and then jumps of this length in the direction of her weighted gravity center, some noise modifying the final position.
To summarize this behaviour under the vision of the heterarchical concept, this stigmergic communication channel shows the following properties, underlined in Sect. [DenseHeterarchy_Algorithms] :
Scope : When one ant lays a pheromonal spot, all the
ants can subsequently perceive it.
Memory : The information persists in the system during a
certain period of time, independently of the agents.
Integrity : The information is modified by time, to
reproduce the pheromone evaporation.
There is some similarity between this algorithm and the " path-relinking" algorithm introduced by Glover ([Glover97]), as the ants are moving through a set of informative points.
Using the Direct Inter-individual Communication
As we have said in Sect. [Introduction], some biological works have led us to take an interest out of the common vision of the "stigmergic" ant colony optimization. Indeed, we have implemented another communication channel which possesses the properties of the direct inter-individual interactions that can be observed in societies of some social insects as ants.
In concrete terms, each ant can send "messages" to another one, this means that the scope of this communication channel is from "peer to peer". An ant receiving a message stores it in a stack with other incoming messages. In a second time, a message is read randomly in the stack. This process is also inspired from the works on communication problems in large multi-agents systems ([Hewitt77]), more particulary on the implementation of parallel programs. Here, the information sent is the position of the sender — an artificial ant — and the value of the objective function. The receiver compares the sender’s value with its own value and decides if it moves near the sender’s position. The final position is drawn randomly in a hyper-sphere which has the sender for center and the receiver’s range for radius. But if the receiver’s value is better than the sender’s one, then the receiver sends a message to another ant randomly chosen, and suppresses the read message. One can notice that the system needs to be "activated", so that an important parameter is the number of messages initially set.
This communication channel shows the following properties :
Scope : When an ant sends a message, only one ant can
perceive it.
Memory : The information persists in the system during a
certain period of time, under the form of ant’s memory.
Integrity : The informations stored are static.
The Final Algorithm
Finally, the two simple algorithms previously described (Sect. [CIAC_first] and [CIAC_second]) are designed to be quite different. We have approached in Sect. [DenseHeterarchy_BioDefinition] the notion of self-organization where a system made of simple units can show emergent properties at a high level. According to this idea, we have implemented in the same system the two simple communication channels, in order to study if they work in synergy or not. This combination is quite simple to do, as the communication channels have no concurrent process.
The CIAC Algorithm
The algorithm comprises three main steps (Fig. [Algo_Schema]). In
the first one, the parameters are set up, notably the
ants ranges are distributed over the agents population
and they are put randomly within the search space. Then
the algorithm starts and the ants until a stopping
criterion is reached : CIAC is stopped if the difference
between two consecutive best points is lower than $\varepsilon $ (see
below) or if a maximum number of objective function
evaluations has been reached. Ants are moving according
to their own perception of the system, which is handled
by the communication channels.
There is four parameters which need to be set manually. These parameters have the following functions :
$\eta \in \left[0,+\infty \right[$ : the number of agents in the system.
$\sigma \in \left[0,1\right]$ : a percentage of the search space amplitude. Used to define the standard deviation of the normal distribution of ants moves ranges.
$\rho \in \left[0,1\right]$ : defines the pheromonal spots persistence.
$\mu \in \left[0,+\infty \right[$ : sets the initial number of messages.
The setting of those four parameters is discussed hereafter.
In addition, there are some other parameters which are included in the algorithm or deduced from the chosen parameters :
the distribution of the ants starting points. The ants are distributed randomly within the search space.
$\varepsilon $ : under this value of pheromone quantity, a spot disappears. It is set to the minimum value handled by the programming language.
$\varsigma $ : the noise quantity added to the ant position when she moves according to the stigmergic channel. This is a percentage of the ants move range. It is set according to (cf. Sect. [CIAC_first] for variables names) \beginequation \begincases \frac\overline\delta \phi _j & \text if\quad \overline\delta \lid \phi _j\\ 1 & \text else\endcases\labelEquation_NoisePosition\endequation
Tuning of CIAC Parameters
After several trials using a set of 11 classical analytical test functions of 2 to 5 variables, default values for parameters that are not automatically set were fixed as follows : $\eta =100$, $\sigma =0.5$, $\rho =0.1$ and $\mu =10$. These settings represent a compromise over all the test functions used and thus are not necessarily the best ones for a specific function.
The number of ants $\eta $ is not a critical parameter as it doesn’t influence critically the overall convergence of the algorithm. With only 10 ants, the algorithm performs well but the need for more ants increases with the dimension of the objective function. In fact, a set of 100 ants permits to the algorithm to be flexible enough over all the functions as well for 2 than for 100 dimensions. On the other hand, the ranges distribution ratio $\sigma $ influences the efficiency of the algorithm. Indeed, it defines the way the search space will be explored, a too little value will lead to an insufficiently explored search space and a too high value will lead to random movements. But with experiments, it is easy to show that a relatively low value of $\sigma $ is recommended. The two other parameters are interesting because they are specific to the two communication channels implemented. The first one, the persistence of the pheromonal spots $\rho $, is quite sensitive, because a high value can easily lead the ants to be trapped into a local optimum. Here also, the experience tells us to use a small value to avoid this issue on the largest set of functions. The last parameter is $\mu $, the initial messages number, that is specific to the direct inter-individual communication channel. It is also relatively critical because a too high value will induce a reduction of the stigmergic channel influence. The good setting for this parameter is generally under the half of the number of ants. To summarize, the two most sensitive parameters are those which are specific to the communication channels implemented in the algorithm, and generally the algorithm is efficient when there is a "balance" between $\rho $ and $\mu $ : the settings proposed above achieved such a balance. More research is still necessary to better understand the influence of both parameters. In an improved version of CIAC algorithm, under preparation, $\rho $ and $\mu $ will be automatically set, as well as $\sigma $.
Experimental Results
To illustrate the behaviour of CIAC, we have applied it on the $B_2$ function (see ), which has two dimensions and some local minima. The global optimum is $B_2=0$ at $(0,0)$. We use a search interval of $[-50,100]$. We also use 10 ants to make the figures more readable, all the other parameters values are those described above. \beginequation B_2(x_1,x_2)=x_1^2+2x_2^2-0.3\cos \left(3\pi x_1\right)-0.4\cos \left(4\pi x_2\right)+0.7\labelEquation_B2\endequation
The two channels play complementary parts. Indeed, the
direct channel leads to a form of intensification,
because it gives more importance to the best points
without taking into account the previously encountered
regions. On the contrary, the stigmergic channel —with
its memory property— permits to perform a kind of
diversification, by taking into account the previously
evaluated points. Figure [B2_both] shows how the algorithm works
with both channels. Globally, the ants gather at the
global optimum. However some of them are kept during
some iterations near local optima by some pheromonal
spots still persisting within the search space,
afterwards evaporation and direct communications
prevent them from being trapped.
The way the stigmergic channel permits a form of diversification is pointed out with more difficulties. Figure [B2_stigm] shows CIAC using only this communication channel. These four consecutive snapshots are taken after 101, 102, 103 and 104 evaluations of the objective function. The ants are moving around a gravity center that is the global optimum, but continue to explore the search space, as they are attracted by local minima.
One interesting issue is the way the two channels works
in synergy. Indeed, on the simple $B_2$ function, the direct
channel seems to be more appropriate as it allows CIAC
to converge more rapidly (Fig. [B2_values]a). But if we take a
look to the variation of the standard deviation for the
algorithm using the two communication channels (Fig. [B2_values]
b), we notice that there is a kind of periodicity. This
means that the population tends to gather near a value
at one time and then tends to disperse. In other words,
there is an alternation of short intensification phases
(low deviation) and diversification phases (high
deviation). This behaviour of the CIAC algorithm is an
emergent pattern, which cannot be observed when only
one of the two channels is used. Thus CIAC regulates
itself the way the two channels are working, until a
stable state is found.
We are testing the CIAC algorithm over a set of analytical test functions found in the literature. In order to compare CIAC firstly with other ant colony optimization algorithms, we have chosen a first set of test functions mainly in the related articles ([Bilchev95], [Mathur00] and Monmarch\’e & al. 2000). Our numerical results will be presented in a paper under preparation.
Conclusion
We have shown that the heterarchical concept can be interesting to design new ant colony algorithms, in particular aimed at the optimization of continuous multiminima functions. Such a biological concept was’nt exploited until now for the design of optimization algorithms, using only stigmergic processes. We propose to extend the ant colony metaphor to take into account several communication processes. CIAC is an heterarchical algorithm implementing two complementary communication channels. It shows interesting emergent properties, like a self-management of the relative influence of the two channels.
Regarding the future, one important issue consists in improving the automatic tuning of parameters, before testing CIAC through a large set of analytical test functions, and comparing its efficiency to that of competing metaheuristics.
