Ant colony optimization. ACOR algorithm

ACOR algorithm

Hi, habr. I want to share my information on continuous optimization methods, namely on optimization using the ant colony method, especially since 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 introduce several more algorithms for the ant colony. Maybe someone is useful at the university or at work.

Formulation of the problem

We consider the solution of the deterministic optimization problem. The deterministic optimal solution problem is formulated as follows:

where R ^ n is an n- dimensional space, D is the range of admissible 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 target function (optimality criterion), F (S *) - the optimal value of the optimality criterion.

General information

The ACOR algorithm ( Ant Colony Optimization for continuous domain ) successfully replaces the discrete ACO algorithm without the need to make any changes to its scheme. Other continuous optimization algorithms, although based on the ACO algorithm ( continuous-ACO , API , algorithm for 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 a dependent (pheromone) probabilistic choice of components. This is achieved by replacing the discrete probability distribution with a continuous function calledprobability density function ( Probability Density Function ( PDF )), also known as the Gaussian distribution.
The ACOR algorithm uses the Gaussian “kernel” ( Gaussian Kernel ) for a weighted summation of several probability density functions. Gaussian “core” - G ^ i (S) is determined by the formula

where k is the number of probability density functions, i is the measurement, ωl is the weight function, μl ^ i is the vector of mean values ​​(mathematical expectation vector), σl ^ i is the dispersion vector .


Figure 1 - An example of a “core” of Gauss, consisting of four Gauss functions

Model pheromones ACOR determined rankings archive solutions T . At each iteration, the resulting set of solutions is added to the solution archive T and ordered by the optimality criterion. The solution archive T always has k solutions, as a result of which, at each iteration, the set of worst solutions should be deleted. This procedure mimics the process of updating pheromones in discrete ACO algorithms . The goal of this process is to shift the search process towards the best solutions found during optimization.

Algorithm design

For a convenient representation of the solutions, an array of solutions is used, presented in Table 1. In the decision table, the 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 , " core "of Gauss for the i -th step - the G ^ i (the S) , which is calculated using only the i th component of all k -making in the archive T .

Table 1 - The decision table


To obtain a solution, the ant at each step i = 1, ..., n , selects the value of the solution S ^ i inn -dimensional optimization problem.
1) For k- ants, solutions s ^ 1, ..., s ^ n are randomly obtained .
2) Sorted 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 the 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 for a large value of q , a more uniform probability is obtained. With a large q, decreases the speed of obtaining the final result.
4) The probability of each decision is calculated

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

where i ∈ [1: n ], and ξ is the coefficient that determines the evaporation of pheromones (ξ> 0).
8) Get a solution using a random number generator and a probability distribution obtained using the Gaussian “core”.
9) The values ​​of the objective function of each solution are calculated.
10) Add the resulting solutions to the T solutions archive .
11) Streamline the resulting decisions.
12) Save 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 sources used

1. Mohamad M., Tokhi M., Omar OM Continuous Ant Colony Optimization for Active Vibration Control of Flexible Beam Structures // IEEE International Conference on Mechatronics (ICM). Apr., 2011, - P. 803-808.
2. Madadgar S., Afshar A. An Improved Continuous Ant Algorithm for Optimization of 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 delved into it for quite some time. The next article on the continuous-ACO algorithm will be a little later.