Optimization by the ant colony method. ACOR algorithm

ACOR algorithm

Hi, Habra. I want to share the information I have on continuous optimization methods, namely on optimization by the ant colony method, especially there is very little material on this topic in Russian. This article presents the ACOR ( Ant Colony Optimization for continuous domain ) algorithm. In the future I plan to present some more ant colony algorithms. Maybe someone will be useful at the university or at work.

Formulation of the problem

Consider solving a deterministic optimization problem. The deterministic optimal solution problem is formulated as follows.

where R ^ n is the n- dimensional space, D is the range of allowable values ​​of the vector of variable parameters, S is the n- dimensional vector of variable parameters, S * is the optimal value of the vector of variable parameters, F (S) is the objective function (optimality criterion), F (S *) - the optimal value of the optimality criterion.

General information

The ACOR ( Ant Colony Optimization for continuous domain ) algorithm successfully replaces the discrete ACO algorithm without the need to make any changes to its scheme. Other continuous optimization algorithms, though based on the ACO algorithm ( continuous-ACO , API , the algorithm of continuously interacting ant colonies ( CIAC )), but for the most part do not repeat its scheme.
The main idea of ACOR is the increment of the components of the vector of variable parameters, obtained on the dependent (from pheromones) probabilistic choice of components. This is achieved by replacing the discrete probability distribution with a continuous function, called the Probability Density Function ( PDF ), also known as the Gauss distribution.
The ACOR algorithm uses a Gaussian Kernel for the weighted summation of several probability density functions. The “core” of Gauss - G ^ i (S) is determined by the formula

where k is the number of probability density functions, i is the dimension, ωl is the weight function, μl ^ i is the vector of mean values ​​(vector of mathematical expectations), σl ^ i is the vector of dispersions.
')

Figure 1 - An example of the "core" of Gauss, consisting of four Gaussian functions

The ACOR pheromone model is determined by the decision archive ranking T. At each iteration, the resulting set of solutions is added to the archive of solutions T and sorted by the optimality criterion. The archive of solutions T always contains k solutions, as a result of which, at each iteration, the set of worst solutions must be deleted. This procedure simulates the process of updating pheromones in discrete ACO algorithms. The purpose of this process is to shift the search process towards the best solutions found during optimization.

Algorithm diagram

For convenient presentation of solutions, an array of solutions is used, presented in Table 1. In the decision table, solutions are stored according to their rank ( s 1 ^ i is the best), ωl is the weight of each probability density function, ω 1≥ ω 2≥ ⋯ ≥ ωn , “ The Gauss core for the i- th step is G ^ i (S) , which is calculated using only the i -th component of all k solutions in the archive T.

Table 1 - Decision Table


To obtain a solution, the ant at each step i = 1, ..., n , selects the value of the solution S ^ i in the n- dimensional optimization problem.
1) For k -rams, solutions s ^ 1, ..., s ^ n are randomly obtained.
2) Arranged by the value of the objective function, where the rank of the solution l = 1 is the best.
3) Calculate the weight ωl for each solution

where q is a coefficient. For a fixed k , a small value of q (~ 0) means that only the probability density function of the best solution will be used to create a new solution, while with a large value of q , a more uniform probability is obtained. With a large value of q , decreases the rate of obtaining the final result.
4) Calculate the probability of each decision.

5) Using the roulette method , randomly choose one solution - Sl , using the calculated probability.
6) It is assumed that the expectation μl ^ i is equal to sl ^ i .
7) Calculate the variance (deviation from sl ^ i ) in the i-th dimension using the formula

where i ∈ [1: n ], and ξ is the coefficient that determines the evaporation of pheromones (ξ> 0).
8) A solution is obtained using a random number generator and a probability distribution obtained using the Gauss “core”.
9) Calculate the values ​​of the objective function of each solution.
10) Add the resulting solutions to the archive of solutions T.
11) Order the resulting solutions.
12) Save the k solutions in the T archive.
13) If the best solution meets the search criteria, complete the search, otherwise go to the third step.

List of used sources

1. Mohamad, M., Tokhi, M., Omar, OM, Colony Optimization, IEEE International Conference on Mechatronics. Apr., 2011, p. 803-808.
2. Madadgar S., Afshar A. An Improved Continuous Ant Algorithm for Water Resources Problem // Water Resources Management. -2009. - Vol. 23. - NO. 10. - P. 2119-2139.

UPD:
If you have questions, be sure to write, as he himself for a long time penetrated. The next article on the continuous-ACO algorithm will be a little later.