Fitting of an ant colony approach to dynamic optimization through a new set of test functions.

Abstract: Real world problems are often of dynamic nature. They form a class of difficult problems that metaheuristics aim to solve. The goal is not only to attempt to find near-to optimal solutions for a defined objective function, but also to track them in the search space. We will discuss in this article the dynamic optimization in the continuous case. Then we will present the experimentation on a battery of test functions, specially tuned for that purpose, of our ant colony algorithm, DHCIAC (Dynamic Hybrid Continuous Interacting Ant Colony).

Keywords: Dynamic optimization, ant colony, Nelder-Mead, particle swarm optimization, simplex, genetic algorithm.

I. Introduction

Metaheuristics are a class of stochastic methods that proved to be interesting for their versatility [17] [11]. They are generally used to solve combinatorial discrete NP-hard problems, but real world problems are often defined with real, or mixed integer/real parameters.

In the last few years, the literature shows an increasing interest for dynamic problems. Most commonly used metaheuristics are evolutionary algorithms, that can be applied to combinatorial problems. One promising approach in this field is embodied by the Ant Colony Optimization algorithms.

Our concern in this paper is continuous dynamic hard optimization problems, solved by using an ant colony algorithm. In section II, we will shortly expose the related works. Our DHCIAC algorithm is described in detail in section III. In section IV-A the performance measurements found in the literature and used in this paper are listed. Results and comparison with other approaches are presented in section V using a new set of dynamic test functions. Then we conclude in section VI.

II. Metaheuristics for dynamic optimization

Most metaheuristics are sophisticated Monte-Carlo methods. The basic Monte-Carlo method is a random search algorithm which seeks the function optimum by generating a sample of solutions according to an uniform law. At the beginning of 90's, a new research domain in distributed artificial intelligence has emerged, called swarm intelligence. It concerns the study of the utility of mimicing social insects for conceiving new algorithms. Computer science has used the concept of auto-organization and emergence, found in social insects societies, to define what is called swarm intelligence. The ant colony algorithm (based on the deposit and the evaporation of pheromone) and the particle swarm optimization algorithm (PSO) are only two methods among others inspired by nature. One of the major advantages of swarm intelligence algorithms, such as the ant colony algorithms, is their flexibility in dynamic environments. Nevertheless, few works deal with applications of ant colony algorithms to dynamic continuous problems.

Daniel Parrott and Xiaodong Li present in [25] a particle swarm optimization algorithm for multi-modal optimization. T. M. Blackwell uses in [5, 4] a technique to solve dynamic problems, which consists in maintaining diversification, by attributing to particles a repulsion charge, in analogy with the electrostatic charges. The PSO method proposed in [25] is a model dedicated to dynamic continuous environments containing several optima.

Genetic algorithms were largely applied to the dynamic landscapes, but mostly in the discrete case. Jurgen Branke (refer to [6], [7]) classifies the dynamic methods found in the literature as follows:

* The reactive methods (refer to [18], [28]), which react to changes (i.e.: by triggering the diversity). The general idea of these methods is to do an external action when a change occurs. The goal of this action is to increase the diversity. In general the reactive methods based on a population loose their diversity when the solution converges to the optimum; this last point causes a problem when the optimum changes. So by increasing the diversity the diversity is regenerated.

* The methods that maintain the diversity (refer to [19], [9], [22], [23]). These methods maintain the diversity in the population, hoping that, when the objective function changes, the distribution of individuals in the search space permits to find quickly the new optimum (see also [16], [26], [15], [1] and [27]).

* The methods that keep in memory "old" optima. These methods keep in memory the evolution of different optima, to use them later. These methods are especially effective when the evolution is periodic (refer to [2], [29] and [3]).

* The methods that use a group of sub-populations distributed on different optima (refer to [31], [24], [8] and [30]), this way the probability to find new optima is increased.

III. Dynamic Hybrid Continuous Interacting Ant Colony algorithm

A. CIAC:

Anew method introduced by Johann Dreo et al., called CIAC [12], focuses on the principles of communication channels, used in a multi-agent ant colony approach. Thus, a formalization of information exchanges is proposed. Indeed, there are several ways to communicate information between two groups of individuals. From a metaheuristic point of view, there are three characteristics for these communication channels:

1. Perception: the number of individuals concerned by information exchange. Information can be sent, for example, by an individual and received by many others, and vice versa.

2. Memory: the information persistence in the system. Information can remain a certain time in the system or can be just transitory.

3. Integrity: the use of a communication channel can cause modifications. Information can change over time.

Information passing through a communication channel can be any information of interest, such as the value and/or the position of a point in the search space.

CIAC proposes to add to the stigmergic process (which uses the "pheromones") a direct information exchange, inspired from the heterarchy concept.

B. DHCIAC

The DHCIAC algorithm (Dynamic Hybrid Continuous Interacting Ant Colony) [13] is a multi-agent algorithm, based on the exploitation of several communication channels and has two variants, DHCIAC track and DHCIAC find. We use in this work only the DHCIAC track algorithm, that uses the method of the ant colony [10] for global search, and the dynamic simplex method [32] for local search. The ants have two ways of communication, as in the CIAC algorithm. They can deposit pheromone spots in the search space, or use a direct communication channel:

1. the stigmergic channel uses pheromone spots, deposited on the search space, which will be more or less attractive for the artificial ants, according to their concentration and their distance. The characteristics of the stigmergic channel are the following: the range is set at its maximum (every ant has a visibility range), all ants can potentially receive information; there is use of memory, since the spots persist within the search space; finally information changes over time, since the spots evaporate. The information included in the spots implicitly contains the position of a point and explicitly the value of evolution by the ant having deposited the spot.

2. the direct channel is implemented as a form of exchange of messages between two individuals. An artificial ant has a set of received messages and can send messages to another ant. The range of this channel is set to one, since only one ant receives the message; the memory is implemented in the messages set that ants keep in memory; finally information (in our case the position and the value of a point) does not change over time.

Each ant chooses between these two channels according to a threshold value. The motivation is a numerical value which Fitting of an Ant Colony approach to Dynamic Optimization 205 changes during the execution. We note that ants perceive only a small region of their environment, called the visible zone.

The first step of the algorithm presented in figure 1 is to randomly put the ants over the search space according to an uniform distribution and to initialize all parameters. Then the pheromonal spots evaporate. At this step, a decision is taken, according to a threshold choice function: the ant chooses to handle one of the two communication channels. Here the two parameters of the stimulus-response function, for the threshold and for the power, are set for the whole population, as each ant i has a particular stimulus parameter initialized at the first step according to a normal distribution. If the ant chooses the stigmergic channel, it looks for pheromonal spots in the visible zone. If there is some spots, it moves towards the weighted gravity center of the visible spots, else it goes on the step of motivation decision. On the contrary, if the ant chooses the direct channel, it looks for messages in its message queue. If there is some messages, it moves towards the location indicated by the message and then adds some noise to its new location, else it goes on the step of motivation decision. If there is no spot and no message, the ant takes a decision based on its motivation. The choice is made according to a stimulus-response function. The first choice leads to the direct channel, with message handling.

[FIGURE 1 OMITTED]

At this step, another decision is taken according to a stimulus-response function with the same parameter as the previous step, except that the stimulus is (1--motivation). If the choice is made to handle messages, a message is sent to a random ant and the motivation is increased of a small amount. The second choice is to avoid messages, then the ant goes to the step of random move. If the motivation choice is to handle local search, a dynamic simplex search algorithm [32] is launched with the location of the ant as base point and the radius of the visible zone as initial step length. The local search is limited to a number of evaluations of the objective function. After this local search, the ant looks for visible spots. If there is a spot, it reinforces it and the radius of the visible zone is reduced to the distance to the farthest visible spot. Else if there is no spot, the ant deposits a new one, with a concentration set to the value of the objective function at this ant's current location. After the handling of the stigmergic channel, the motivation is set to zero.

C. Parameter tuning

After a series of preliminary tests on the whole set of test functions described in section IV-B and in Appendix A, the different parameters of the algorithm were fixed as follows. The dimension of the search space is 2D, and the search interval is [-100,+100]. The number of ants was taken equal to 10, 20, 40, 80 for each function, this parameter is critical when the number of dimensions of the problem increases. The agents must choose between answering to messages from other ants or doing a local search; the probability of this choice was fixed at 0.5, with a standard deviation of 0.2.

The pheromone persistence value [rho], if selected high, will trap ants into local optima. The selected value of [rho] is 0.9. The threshold under which the pheromone disappears is set to 0.0001.

Every simple move of the ants has a value of 0.5. For the dynamic simplex the maximum number of iterations is set to 100, and for DHCIAC 50000.

[sigma] is the percentage of the size of the search space which will be explored, to determine the standard deviation of the normal distribution of ant ranges. This value allows to determine how the search space will be explored. A "small" value means a bad diversification or exploration, and a "very high" value means an useless dispersion, since ants will be dispersed and search will be random.

The simplex method that we used is the dynamic simplex which uses the reflection coefficient only.

IV. Tools used in dynamic optimization

A. Performance metrics

The performance measurement of a metaheuristic is much more difficult in the dynamic case than in the static case. Despite the growing interest concerning the evolutionary algorithms in the dynamic case, there is no uniform vision of performance measurement in the dynamic optimization. The majority of the papers dealing with the dynamic case do not describe the test problems or the method used for performance measurement. In [21] the methods are classified as follows:

* A measurement of the difference between the found value of the optimum (the better individual in the population) and the true value of the optimum, just after a change took place in the objective function.

* A measurement of the average of the Euclidean distance to the optimum at each generation.

* The average of the best generations, over several executions of an algorithm on a precise problem.

* Or the difference between the best and the worst generation in a small set of recent generations.

We will use the following performance measurement metric hereafter:

Error for value = mean{| [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] |}

Error for position = mean{| [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] |}

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are the true value of the optimum and the best found value of the optimum at time [t.sub.j] respectively, and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are the true position of the optimum and the best found position of the optimum at time [t.sub.j] respectively (with j [member of] {0, ..., N}). To reduce the fluctuation in the result output due to random initialization, every presented result is the average of 100 executions of the algorithm.

Fitting of an Ant Colony approach to Dynamic Optimization 206

B. Benchmark functions

Many test functions were defined in the literature like in [20]. To carry out comparisons between different approaches, it is necessary to consider the same set of problems or functions. Therefore we describe in this section a set of test functions (see on Table 1), which includes several types of dynamic functions [14], from a simple function with a single optimum to functions having a large number of local optima. We point out here that we are dealing with dynamic continuous functions only.

[TABLE 1 OMITTED]

Suppose that f([??], T(t)) is the general form of a dynamic objective function. We can then distinguish two main categories of dynamic optimization functions: the first one concerns a change in the structure itself of the objective function f, and the second concerns the evolution of T(t), called the "time function", where t represents time. A simple example of two dynamic functions, based on traditional static functions, Easom and B2 respectively, is given below:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where the position of the optimum is the only element that changes, and:

f([??], T(t)) = [([x.sub.1] - T(t)).sup.2] + 2 x [([x.sub.2] - T(t)).sup.2] + 0.7 -0.3 x cos(3[pi]-([x.sub.1] -T(t)))-0.4 x cos(4.[pi]-([x.sub.2] -T(t))),

where the whole function changes. The most commonly used variations in dynamic functions are the following: a variation in the objective function and its optimum, a variation in the optimum only, and a variation in the objective function but not its optimum.

We can also mention other more complex variations, like dimensions, constraints, phase (i.e. rotation around an axis) or a complete change (for example, a shift from a convex to a concave form).

The time function T(t) can be linear, periodic (for example T(t) = 2 x cos(t)) or non linear.

Eight dynamic test functions are built based on traditional static functions:

AbPoP based on the Morrison function: all the structure of f, except the position, changes periodically.

AbVP based on the Morrison function: all the structure, except the value, changes periodically.

ADL based on the Rosenbrock function: all dimensions change linearly.

APhL based on the MartinGady function: the phase changes linearly.

APoL based on the B2 function: the position changes linearly.

AVP based on the Shekel function: the value changes periodically.

OPoL based on the Easom function: the position of the optimum changes linearly.

OVP based on the Morrison function: the value of the optimum changes periodically.

The first letters mean A: for All, Ab: for All but, Po: for Position, V: for value, Ph: for Phase. The last letter means P: for periodical, L: for linear.

The exact definition of each test function is given in Appendix A.

V. Results and discussion

A. Tests problems

To test the DHCIAC algorithm described in section III-B, we used the set of dynamic test functions described in section IV-B, and listed in Appendix A.

1) Problem 1: AbPoP

The tested function is AbPoP All but Position Periodic (Appendix A) based on the static Morrison function.

On figure 2 (a) the relative error on the value of the optimum decreases after 25 iterations and is stabilized on the value -2.7. The figure 2 (b) shows the relative error on position of the optimum, that changes periodically over time. We can observe oscillations until the iteration 25, then the value of error is stabilized on a value close to zero. In Table 2 the best error for the value corresponds to 80 agents with a 3.86 standard deviation. And for the position (Tables 3 & 4), the best value corresponds also to 80 agents, with a standard deviation of (3.99, 2.56), best values are in bold character. The first observation concerning the AbPoP function is that DHCIAC could detect the value of the optimum after a small number of iterations. Nevertheless the tracking is less performing. DHCIAC keeps an approximately fixed distance to the value of the optimum.

[FIGURE 2 OMITTED]

2) Problem 2: AbVP

The tested function is AbVPAll but Value Periodic (Appendix A) based on the static Morrison function. The figure 3 (a) shows the relative error on the position of the optimum, which changes periodically over time. The figure shows some oscillations on the error between the values 1 and 3 until the iteration 75, where the error increases to reach the value 13. On figure 3 (b), every curve represents the relative error on the position on different dimensions. The error oscillates between -60 et 100 until the iteration 10, then it is stabilized on the value 0. In Table 2 the best value corresponds to 40 ants with a standard deviation of 3.49. And for the position (Tables 3 & 4) the best value corresponds again to 40 agents, with a standard deviation of (2.54, 2.62). For the test function AbVP, DHCIAC succeeds to find the position of the optimum after a small number of iterations, and succeeds as well to track it at a close distance. Nevertheless, for the value of the optimum, the relative error changes periodically, which means that DHCIAC succeeds in detecting the optimum, but not in tracking it.

[FIGURE 3 OMITTED]

3) Problem 3: APhL

The tested function is APhL All Phase Linear (Appendix A) based on the static Martin-Gady function. The APhL function represents a discontinuity on the optimum position.

Figure 4 (a) shows the error on the optimum value (the real optimum value is a constant function). The relative error decreases from 6 to 1, then reaches the value 0.5 after 8 iterations. Figure 4 (b) shows found optimum position variation in a 2D space versus the real optimum position. The real optimum position changes linearly, and the found position converges towards this position. In Table 2 the best value of the error corresponds to 40 agents with a standard deviation of 9.14. And for the optimum position (Tables 3 & 4) the best error value corresponds again to 40 agents, with standard deviations on X1 and X2 of 52.76 and 31.36 respectively. For the APhL function the convergence towards the optimum position is slow, with large values of standard deviation for the optimum value and position errors. On the other hand the distance between the real and the found optimum is large, which means a dispersion around the optimum. This is due to the discontinuity in the position of the optimum and to the absence of an attraction pool around the optimum.

[FIGURE 4 OMITTED]

4) Problem 4: OVP

The tested function is OVP Optimum Value Periodic (Appendix A) based on the static Morrison function.

Figure 5 (a) shows the variation of the real and found optimum values over time. The value of the optimum changes periodically (see Table 1), the algorithm tracks the optimum value until the iteration 110, then the distance between found and real optima increases. Figure 5 (b) represents the error on the position for each dimension. The error oscillates between 0 and 100, then it is stabilized at 0 after 60 iterations. In Table 2 the best value of the error corresponds to 80 agents with a standard deviation of 4.17. And for the optimum position (Tables 3 & 4) the best error value corresponds again to 80 agents, with a standard deviation of (1.59, 1.63). For the test function OVP, DHCIAC succeeds in detecting and tracking periodically the optimum value and positions [X.sub.1] and [X.sub.2]. The variations at the beginning of the curve are due to the fact that a local optimum of the OVP function changes and becomes a global optimum.

[FIGURE 5 OMITTED]

5) Problem 5: OPoL

The tested function is OPoL Optimum Position Linear (Appendix A) based on the static Easom function.

Figure 6 represents the tracking of the optimum position (which changes linearly over time) in function of the ants number (10, 20, 40, 80 ants). The starting point as well as the real optimum variations are indicated. The optimum position moves away directly after the starting point, then gets back and follows linearly the optimum. The convergence is faster with 10 ants, but the tracking is not at a fixed distance. With 80 ants, convergence is slower, but the tracking is closer. In Table 2 the smaller error corresponds to 10 agents with a standard deviation of 0. And for the optimum position (Tables 3 & 4) the best error value corresponds to 80 agents, with a standard deviation of (15.54, 16.34). For the OPoL function, the test results are promising, and the tracking is done after several oscillations at the beginning of the curve.

[FIGURE 6 OMITTED]

6) Problem 6: AVP

The tested function is AVP All Value Periodic (Appendix A) based on the static Shekel function. On figure 7 the curve shows the error on value for the function AVP. The error oscillates between -9.5 and -11.5. In Table 2 the best value of the error corresponds to 10 agents with a standard deviation of 0.14. And for the optimum position (Tables 3 & 4) the best error value corresponds to 40 agents, with standard deviations on X1 and X2 of 63.26 and 56.5 respectively. For the test function AVP, DHCIAC does not succeed in tracking the optimum value. Nevertheless the standard deviations are small for optimum value and position.

[FIGURE 7 OMITTED]

7) Problem 7: APoL

The tested function is APoL All Position Linear (Appendix A) based on the static B2 function, the optimum position changes linearly over time.

Figure 8 shows the tracking of the optimum position in 3D space. The found value moves away, then gets back at steady intervals. And the distance to the optimum diminishes more and more. In Table 2 the best value of the error corresponds to 10 agents with a standard deviation of 2.05. And for the optimum position (Tables 3 & 4) the best error value corresponds again to 10 agents, with standard deviations on [X.sub.1] and [X.sub.2] of 2.96 and 2.88 respectively. The results of DHCIAC for the APoL test function are promising as shown on figure 8, with small values of standard deviation for the optimum value and position.

[FIGURE 8 OMITTED]

B. Success rates

Table 5 shows all the test functions, with the variations of the value and the position of the global optimum, the associated time function, as well as the success rate. Every success rate is calculated after 100 executions. A success means that the found optimum converges towards the real optimum, and tracks it closely (as shown by the evolution of the curves). The algorithm shows better performances on the APoL function where the optimum position changes linearly, with a success rate of 83 %, and for AbPoP, where the structure of the objective function changes, but not the position, with a success rate of 68 %. Bad performance is observed for the APhL function where the optimum position presents a discontinuity (see on Appendix A): the success rate is only of 13%.

C. Comparison with other algorithms

Despite the growing interest for optimization in dynamic conditions, there exists no common approach on how to compare different algorithms. We mention that almost all results presented in the literature concern discrete problems. We compared our algorithm to the Monte-Carlo method, and to the dynamic simplex method, for all the test functions. Comparisons concern the mean errors on optimum value and position. Our algorithm is also compared to a particle swarm optimization algorithm, on a modified version of the AbPoP function.

In Tables 6, 7 and 8, the three methods DHCIAC, Monte-Carlo and dynamic simplex are compared. The maximal iteration number is set to 5000 for the three methods, and the ant number for DHCIAC is set to 80. For the AbPoP test function, DHCIAC shows better performances than the two competing methods, the errors are in value 4.09(3.86) and in position 0.04(3.99), -0.8(2.56). For the AbVP test function, the ant number for DHCIAC is set to 40 and DHCIAC shows better performances than the two other methods, the errors are in value 9.73(3.49) and in position -0.21(2.54), -0.27(2.62). For the OVP test function the ant number for DHCIAC is set to 80 and DHCIAC shows better performances than the two other methods. The errors are in value 0.38(4.18) and in position -3.29(1.7), -3.18(1.79). For the APhL test function the ant number for DHCIAC is set to 40 and DHCIAC shows again better performances, the errors are in value 1.97(9.17) and in position -1.16(98.41), -9.98(13.14). For the AVP test function, the ant number for DHCIAC is set to 40 and DHCIAC shows better performances than the two other methods in the value of the optimum 10.62 (0.14). Monte-Carlo has better performance in position 35.84, 22.88, but with an higher value of standard deviation. DHCIAC presents the smallest standard deviation in position. For the OPoL test function, the ant number for DHCIAC is set to 80 and DHCIAC shows better performances for optimum value than the two other methods 6.54E-005(0). Monte-Carlo has better performances for the optimum position 1.03(0.81), 0.82(0.72). For the APoL test function, the ant number for DHCIAC is set to 10 and DHCIAC shows better performances for optimum value 2.42(2.05) and for optimum position -5.8(2.96), -5.9(2.88).

A comparison with a classical PSO and a variant of PSO is performed. The test function used is based on the static Morrison function with the following time function: [Y.sub.i] = A.[Y.sub.(i-1)]x(1 - [Y.sub.i-1]). To be able to compare our method to the PSO methods, we have modified the AbPoP test function, the newly defined function is the following (refer to [20]):

f(x, y) = [max.sub.i,N] [[H.sub.i] - [R.sub.i] * [square root of ([(X - [X.sub.i]).sup.2] + [(Y - [Y.sup.i]).sup.2]]

with [Y.sub.i] as a time function, N = 3, Hbase = 3, Hrange = 3, Rbase = 2, Rrange = 5, A = 1.2.

[H.sub.i] [member of] [Hbase, Hbase + Hrange]

[R.sub.i] [member of] [Rbase, Rbase + Rrange]

The test environment is a 2D space within an interval [-1.0, 1.0], the maximal number of iterations is 500, and the results shown in Table 9 are obtained by averaging 50 executions. Agents number (particles and ants) is successively set to 30, 60, 90, 120, 150.

VI. Conclusion

The first observation resulting from our experimentation is that DHCIAC could follow the position of the optimum at an almost constant distance, for periodic test functions, for example for the AbPoP function, where the distance to the optimum is almost zero. And when the distance to the optimum increases, the algorithm continues to track the optimum, for example on the AbVP function and the OVP function. This is due to the fact that the distances between optima are constant, and that the dynamic simplex method hybridized with the ant colony algorithm converges rather rapidly to these new optima. For functions with linear variations, the detection and the tracking results of the optimum are good for the value and the position. For the success rate of the algorithm, the best performances concern functions with value and position variations, and bad performances concern the function with phase variations. In fact, if the random initialization occurs on a plane surface, the dynamic simplex method behaves in a chaotic manner, the successive reflections used by the dynamic simplex do not lead to better values. In the literature, few results exist on continuous dynamic environments. To compare our algorithm to other methods, we have undertaken the same tests on the dynamic simplex method, and the Monte-Carlo method. Our algorithm DHCIAC performs better on the whole set of test functions. A comparison was performed with two particle swarm optimization algorithms. DHCIAC performed slightly worse than the variant of PSO and better than the classical PSO.

A. Test functions for dynamic optimization problems

AbPoP

AbPoP All but Position Periodic based on the static Morrison function.

The time function is T(t) = cos(t).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

AbVP

AbVP All but Value Periodic based on the static Morrison function.

The time function is T(t) = cos(t).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

APhL

APhL All Phase Linear based on the static MartinGady function.

The time function is T(t) = t.

[([X.sub.1] - [X.sub.2]).sup.2] + [([X.sub.1] + [X.sub.2] - 10/3).sup.2]

with [X.sub.1] = [Xp.sub.1] - T(t) [X.sub.2] = [Xp.sub.2] - T(t) [Xp.sub.1], [Xp.sub.2] are the polar coordinates

OVP

OVP Optimum Value Periodic based on the static Morrison function.

The time function is T(t) = 8. cos(0.5t).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

OPoL

OPoL Optimum Position Linear based on the static Easom function.

The time function is T(t) = t.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

AVP

AVP All Value Periodic based on the static Shekel function. The time function is T(t) = cos(0.2t).

D(x) = [n.summation over (i=1)] 1/(x - [a.sub.i])T x(x - [a.sub.i]) + [c.sub.i]

with:

x = [([x.sub.1], [x.sub.2], [x.sub.3], [x.sub.4]).sup.T]

[a.sub.i] = [([a.sup.1.sub.i], [a.sup.2.sub.i], [a.sup.3.sub.i], [a.sup.4.sub.i]).sup.T]

and:

[FIGURES 9-14 OMITTED]

APoL APoL All Position Linear based on the static B2 function. The time function is T(t) = t

f([??], T(t)) = [([x.sub.1] - T(t)).sup.2] + 2 x ([x.sub.2] - T(t)).sup.2] + 0.7 -0.3 x cos(3[pi] - ([x.sub.1] - T(t))) - 0.4 x cos(4.[pi] - ([x.sub.2] - T(t)))

References

[1] V. S. Aragon and S. C. Esquivel. An evolutionary algorithm to track changes of optimum value locations in dynamic environments. Journal of Computer Science and Technology, 4(3):127-134, 2004.

[2] C. N. Bendtsen and T. Krink. Dynamic Memory Model for Non-Stationary Optimization. In Congress on Evolutionary Computation, pages 145-150. IEEE, 2002.

[3] C. N. Bendtsen. Optimization of Non-Stationary Problems with Evolutionary Algorithms and Dynamic Memory. PhD thesis, University of Aarhus, Department of Computer Science Ny Munkegade 8000 Aarhus C, 2001.

[4] T. M. Blackwell. Particle Swarms and Population Diversity II: Experiments. In J. Branke, editor, GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization Problems, pages 14-18, 2003.

[5] T. M. Blackwell. Particle Swarms and Population Diversity I: Analysis. In J. Branke, editor, GECCOWorkshop on Evolutionary Algorithms for Dynamic Optimization Problems, pages 9-13, 2003.

[6] J. Branke. Evolutionary Approaches to Dynamic Environments--updated survey. In GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization Problems, pages 27-30, 2001.

[7] J. Branke. Evolutionary Approaches to Dynamic Optimization Problems--Introduction and Recent Trends. In J. Branke, editor, GECCOWorkshop on Evolutionary Algorithms for Dynamic Optimization Problems, pages 2-4, 2003.

[8] W. Cedeno and V. R. Vemuri. On the Use of Niching for Dynamic Landscapes. In International Conference on Evolutionary Computation. IEEE, 1997.

[9] H. G. Cobb and J. J. Grefenstette. Genetic Algorithms for Tracking Changing Environments. In International Conference on Genetic Algorithms, pages 523-530. Morgan Kaufmann, 1993.

[10] M. Dorigo and L. M. Gambardella. Ant Colony System: ACooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1(1):53-66, 1997.

[11] J. Dreo, A. Petrowski, P. Siarry, and E. Taillard. Metaheuristics for Hard Optimization, Methods and Case Studies. Springer, 2005.

[12] J. Dreo and P. Siarry. Anew ant colony algorithm using the heterarchical concept aimed at optimization of multi-minima continuous functions. In M. Dorigo, G. Di Caro, and M. Sampels, editors, Ant Algorithms : Third International Workshop, ANTS 2002, volume 2463 of LNCS, Berlin, Germany, 2002. Springer-Verlag.

[13] J. Dreo and P. Siarry. Dynamic Optimization Through Continuous Interacting Ant Colony. In M. Dorigo and al., editors, ANTS 2004, LNCS 3172, pages 422-423, 2004.

[14] J. Dreo and P. Siarry. An ant colony algorithm aimed at dynamic continuous optimization. Applied Mathematics and Computation, 181(1):457-467, 2006.

[15] S. M. Garrett and J. H. Walker. Genetic Algorithms: Combining Evolutionary and 'Non'-Evolutionary Methods in Tracking Dynamic global optima. In W. B. L. et al., editor, Genetic and Evolutionary Computation Conference, pages 359-374. Morgan Kaufmann, 2002.

[16] A. Gaspar and P. Collard. There isALife beyond Convergence: Using a Dual Sharing to Adapt in Time Dependent Optimization. In Congress on Evolutionary Computation, volume 3, pages 1867-1874. IEEE, 1999.

[17] F. Glover and G. Kochenberger. Handbook of Metaheuristics. International Series in Operations Research & Management Science. Kluwer Academic Publishers, Boston Hardbound, 2003.

[18] J. J. Grefenstette and C. L. Ramsey. An Approach to Anytime Learning. In D. Sleeman and P. Edwards, editors, International conference on Machine Learning, pages 189-195. Morgan Kaufmann, 1992.

[19] J. J. Grefenstette. Genetic algorithms for changing environments. In R. Maenner and B. Manderick, editors, Parallel Problem Solving from Nature 2, pages 137-144. North Holland, 1992.

[20] R.W. Morrison and K.A. De Jong.ATest Problem Generator for Non-Stationary Environments. In Congress on Evolutionary Computation, volume 3, pages 2047-2053. IEEE, 1999.

[21] R. Morrison. Performance Measurement in Dynamic Environments. In J. Branke, editor, GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization Problems, pages 5-8, 2003.

[22] T. Nanayakkara, K. Watanabe, and K. Izumi. Evolving in Dynamic Environments Through Adaptive Chaotic Mutation. In Third International Symposium on Artificial Life and Robotics, volume 2, pages 520-523, 1999.

[23] G. Ochoa, C. Madler-Kron, R. Rodriguez, and K. Jaffe. Assortative mating in genetic algorithms for Dynamic Problems. In F. Rothlauf et al., editors, Applications of Evolutionary Computing, volume 3449 of LNCS, pages 617-622. Springer, 2005.

[24] F. Oppacher and M. Wineberg. The Shifting Balance Genetic Algorithm: Improving the GA in a Dynamic Environment. In W. B. et al., editor, Genetic and Evolutionary Computation Conference (GECCO), volume 1, pages 504-510. Morgan Kaufmann, San Francisco, 1999.

[25] D. Parrott and X. Li. AParticle Swarm Model for tracking Multiple Peaks in a Dynamic Environment using Speciation. In Congress on Evolutionary Computation, pages 98-103. IEEE, 2004.

[26] R. Salomon and P. Eggenberger. Adaptation on the Evolutionary Time Scale: A Working Hypothesis and Basic Experiments. In J.-K. Hao, E. Lutton, E. Ronald, M. Schoenauer, and D. Snyers, editors, 3rd European Conference on Artificial Evolution, number 1363 in LNCS, pages 251-262. Springer, 1997.

[27] A. Simoes and E. Costa. Using biological inspiration to deal with dynamic environments. In Proceedings of the Seventh International Conference on Soft Computing (MENDEL01), Brno, Czech Republic, 2001.

[28] R. Tinos and A. de Carvalho. A genetic algorithm with gene dependent mutation probability for non-stationary optimization problems. In Congress on Evolutionary Computation, volume 2, 2004.

[29] K. Trojanowski and Z. Michalewicz. Evolutionary Optimization in Non-Stationary Environments. Journal of Computer Science and Technology, 1(2):93-124, 2000.

[30] R. K. Ursem. Multinational GA Optimization Techniques in Dynamic Environments. In D. Whitley, D. Goldberg, E. Cantu-Paz, L. Spector, I. Parmee, and H.-G. Beyer, editors, Genetic and Evolutionary Computation Conference, pages 19-26. Morgan Kaufmann, 2000.

[31] M. Wineberg and F. Oppacher. Enhancing the GA's Ability to Cope with Dynamic Environments. In W. et al., editor, Genetic and Evolutionary Computation Conference, pages 3-10. Morgan Kaufmann, 2000.

[32] Q. Xiong and A. Jutan. Continuous optimization using a dynamic simplex method. Chemical Engineering Science, 58(16):3817-3828, 2003.

Walid Tfaili, Johann Dreo and Patrick Siarry

Universite Paris XII Val-de-Marne, LISSI, E.A. 3956,

61 avenue du General de Gaulle, 94010 Creteil, France

{tfaili, dreo, siarry}@univ-paris12.fr

Table 2: Variation of the value in function of the agents (ants)
number.

Agents
number   10              20

AbPoP    4.21 (3.62)     4.15 (3.69)
AbVP     9.99 (3.36)     9.79 (3.52)
APhL     4.61 (52.09)    2.53 (16.51)
OVP      0.6 (4.19)      0.42 (4.25)
OPoL     6.54E-005 (0)   1.33E-004 (0)
AVP      10.62 (0.14)    10.67 (0.19)
APoL     2.42 (2.05)     2.49 (2.08)

Agents
number   40                 80

AbPoP    4.33 (3.78)        4.09 (3.86)
AbVP     9.73 (3.49)        9.89 (3.37)
APhL     1.97 (9.14)        2.041 (4.14)
OVP      0.38 (4.18)        0.37 (4.17)
OPoL     2.23E-004 (0.01)   4.85E-004 (0.01)
AVP      10.68 (0.18)       10.63 (0.12)
APoL     2.54 (2.07)        2.45 (2.08)

Table 3: Variation of the position [X.sub.1] in function of the agents
(ants) number.

Agents
number        10               20

AbPoP      0.15 (3.69)      0.09 (3.76)
AbVP      -0.42 (2.35)     -0.26 (2.55)
APhL      55.51 (57.05)    38.57 (53.75)
OVP       -3.23 (1.56)     -3.27 (1.72)
OPoL        -18 (21.34)   -18.86 (18.24)
AVP      -92.95 (50.1)    -82.37 (61.7)
APoL       -5.8 (2.96)     -5.92 (3.05)

Agents
number        40               80

AbPoP      0.32 (3.85)      0.04 (3.99)
AbVP      -0.21 (2.54)     -0.39 (2.35)
APhL      31.49 (52.76)    32.59 (56.76)
OVP       -3.29 (1.7)      -3.12 (1.59)
OPoL      -15.8 (16.72)   -14.86 (15.54)
AVP      -81.07 (63.26)   -88.34 (56.42)
APoL      -5.94 (2.98)     -5.81 (2.89)

Table 4: Variation of the position [X.sub.2] in function of the agents
(ants) number.

Agents
number         10               20

AbPoP     -0.67 (2.35)     -0.71 (2.45)
AbVP      -0.45 (2.44)     -0.29 (2.61)
APhL      24.44 (38.16)     8.08 (31.99)
OVP       -3.16 (1.64)     -3.15 (1.77)
OPoL     -18.79 (20.15)   -18.66 (18.68)
AVP      -97.91 (40.16)   -90.28 (51.01)
APoL       -5.9 (2.88)     -5.99 (2.93)

Agents
number         40               80

AbPoP     -0.61 (2.42)      -0.8 (2.56)
AbVP      -0.27 (2.62)     -0.43 (2.42)
APhL      15.55 (31.36)    10.80 (29.26)
OVP       -3.18 (1.79)     -3.03 (1.63)
OPoL     -15.86 (17.28)   -14.99 (16.34)
AVP      -86.65 (56.5)     -95.4 (45.33)
APoL      -6.08 (2.95)     -5.91 (2.84)

Table 5: Success rates for all the benchmark functions.

Dynamic                                      Success
function   Position        Value             rate

AbPoP      6+T(t),6        2                 51
AbVP       6,6             2+T(t)            68
APhL       5+T(t),5+T(t)   0                 13
OVP        2.5,-2.5 or     min(1+T(t),3)     53
           -2.5,2.5
OPoL       T(t),T(t)       OPoL(T(t),T(t))   48
AVP        --              T(t)-10.53641     44
APoL       T(t),T(t)       0                 82

Table 6: Comparison related to the optimal value of the objective
function.

           DHCIAC        Monte-Carlo       simplex

AbPoP    4.09 (3.86)     4.38 (4.97)     9.52 (57.39)
AbVP     9.73 (3.49)    25.35 (31.29)   19.23 (57.35)
APhL     0.38 (4.18)     6.18 (6.70)     9.09 (57.38)
OVP      1.97 (9.14)    31.66 (53.35)     2.4 (13.98)
OPoL    10.62 (0.14)    11.38 (0.74)     11.9 (13.77)
AVP     6.54E-005 (0)   410.1 (1451)     8.74 (57.54)
APoL     2.42 (2.05)    30.40 (87.46)    8.33 (75.65)

Table 7: Comparison related to the position [X.sub.1] of the optimum.

           DHCIAC         Monte-Carlo        simplex

AbPoP     0.04 (3.99)     32.51 (40.41)    -4.82 (58.45)
AbVP     -0.21 (2.54)    -14.67 (33.41)       -4 (58.65)
APhL     -3.29 (1.7)       7.55 (31.59)    -4.48 (7.5)
OVP      31.49 (52.76)    40.08 (53.38)    -1.16 (98.41)
OPoL    -92.95 (50.1)     35.84 (71.38)   264.87 (94.57)
AVP        -18 (21.34)     1.03 (0.81)     -4.65 (58.4)
APoL      -5.8 (2.96)    -25.27 (18.61)    -6.22 (33.28)

Table 8: Comparison related to the position [X.sub.2] of the optimum.

            DHCIAC        Monte-Carlo       simplex

AbPoP     -0.8 (2.56)     -2.13 (38.18)    1.14 (30.51)
AbVP     -0.27 (2.62)    0.0048 (30.26)   -2.32 (0.32)
APhL     -3.18 (1.79)     -3.72 (27.07)    58.4 (5)
OVP      15.55 (31.36)    -8.19 (16.73)    9.98 (13.14)
OPoL    -97.91 (40.16)    22.88 (75.89)    1941 (13)
AVP     -18.79 (20.15)     0.82 (0.72)      6.9 (0.5)
APoL      -5.9 (2.88)    -25.22 (18.47)    1057 (1865)

Table 9: Comparison with two PSO algorithms.

Agents      mean & SD        mean & SD       mean & SD
number   (variant of PSO)    (DHCIAC)     (classical PSO)

30          0.1 (0.13)      0.17 (0.32)     0.19 (0.35)
60         0.07 (0.11)      0.14 (0.29)     0.16 (0.30)
90         0.06 (0.09)      0.12 (0.22)     0.14 (0.24)
120        0.05 (0.08)       0.1 (0.13)     0.12 (0.19)
150        0.04 (0.07)      0.06 (0.09)     0.09 (0.13)

i    [a.sup.T.sub.i]     [c.sub.i]

1    4   4     4   4     0.1
2    1   1     1   1     0.2
3    8   8     8   8     0.2
4    6   6     6   6     0.4
5    3   7     3   7     0.4
6    2   9     2   9     0.6
7    5   5     3   3     0.3
8    8   1     8   1     0.7
9    6   2     6   2     0.5
10   7   3.6   7   3.6   0.5