An Island Model based on Stigmergy to solve optimization problems

Island Model (IM) is an alternative often used to parallel Evolutionary Algorithms (EA). In IM, the population is distributed between islands that evolve their solutions in parallel, connected by a topology. Periodically, solutions migrate between islands according to a migration policy. The IM can be seen as an ideal structure to combine different algorithms to be used in an organized and cooperative way to solve a problem. Motivated by the number and distinction of EAs proposed in the last decades, in terms of performance and evolutionary behavior, this work proposes a hybrid configuration for IM, called Stigmergy Island Model (Stgm-IM), inspired by the natural phenomenon of stigmergy. Stigmergy is present in groups of some social species, and, by it, their agents organize themselves and maintain a level of cooperation through indirect communication. The Stgm-IM was evaluated regarding its evolutionary behavior and its performance on a benchmark suite of fifteen optimization problems, showing expected results.

The authors acknowledge the support of Graduate Program in Computational Modeling at Federal University of Juiz de Fora (UFJF) and the Brazilian funding agencies CNPq—Conselho Nacional de Desenvolvimento Científico e Tecnológico (Grant Numbers 306186/2017, 429639/2016 and 306069/2016), FAPEMIG (APQ-00334/18), and CAPES (Coordenação de Aperfeiçoamento de Pessoal de Nível Superior), finance code 001. This research was developed with the support of the Núcleo Avançado de Computação de Alto Desempenho (NACAD) at COPPE, Federal University of Rio de Janeiro (UFRJ). The authors would like to thanks the reviewers for the corrections and suggestions, which helped improve the quality of the paper.

Authors and Affiliations

1. Graduate Program of Computational Modeling, Federal University of Juiz de Fora, Juiz de Fora, Brazil

   Grasiele Regina Duarte

2. Civil Engineering Program, COPPE/Federal University of Rio de Janeiro, Rio de Janeiro, Brazil

   Grasiele Regina Duarte & Beatriz Souza Leite Pires de Lima

3. Department of Applied and Computational Mechanics, Federal University of Juiz de Fora, Juiz de Fora, Brazil

   Afonso Celso de Castro Lemonge & Leonardo Goliatt da Fonseca

Corresponding author

Correspondence to Grasiele Regina Duarte.

Conflict of interest

The authors declare that they have no conflict of interest.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix

Some definitions (Liang et al. 2014):

• All test functions are minimization problems given by the form

  $$\begin{aligned} \left\{ \begin{array}{ll} {\text {Minimize }}f({{\mathbf{x }}})\\ {\mathbf{x}} \in {\mathbb {R}}^D \end{array}, \right. \end{aligned}$$

  where \(f({{\mathbf{x }}})\) is the objective function, \({{\mathbf{x }}} \in [-100, 100]^D\) and \(D \in \{10, 30, 50, 100\}\) is the dimension of the problem.

• \({\mathbf{o }}_i \in [-80, 80]^D\), such that \(i \in \{1, 2,\ldots , 15\}\), is the global optimal solution of the problem Fi displacement by rotation.

• \({\mathbf{M }}_i\) is the rotation matrix of the problem Fi produced by the normal orthogonalization process by the method Gram-Schmidt in a random matrix.

• \(Fi^* = Fi({{\mathbf{x }}}^*)\), where \(i \in \{1, 2,\ldots , 15\}\), \({\mathbf{x }}^*\) is the optimal solution of the problem Fi and \(Fi({\mathbf{x }}^*) = i \times 100\).

Definition of the basic functions:

• \(f_1\)

  $$\begin{aligned} f_1({\mathbf{x }}) = \displaystyle \sum _{i = 1}^{i = D}{(10^6)^{\frac{i - 1}{D - 1}}{\text {x}}_i^2} \end{aligned}$$

• \(f_2\)

  $$\begin{aligned} f_2({\mathbf{x }}) = {\text {x}}_1^2 + 10^6 \displaystyle \sum _{i = 2}^{i = D}{{\text {x}}_i^2} \end{aligned}$$

• \(f_3\)

  $$\begin{aligned} f_3({\mathbf{x }}) = 10^6{\text {x}}_1^2 + \displaystyle \sum _{i = 2}^{i = D}{{\text {x}}_i^2} \end{aligned}$$

• \(f_4\)

  $$\begin{aligned} f_4({\mathbf{x }}) = \displaystyle \sum _{i = 1}^{i = D - 1}{(100({\text {x}}_i^2 - {\text {x}}_{i + 1})^2 + ({\text {x}}_i -1)^2)} \end{aligned}$$

• \(f_5\)

  $$\begin{aligned} f_5({\mathbf{x }}) = \displaystyle -20{\text {exp}}\left( -0.2\sqrt{\frac{1}{D}\sum _{i = 1}^{i = D}{{\text {x}}_i^2}}\right) - {\text {exp}}\left( \frac{1}{D}\sum _{i = 1}^{i + D}{{\text {cos}}(2\pi {\text {x}}_i)}\right) + 20 + e \end{aligned}$$

• \(f_6\)

  $$\begin{aligned} f_6({\mathbf{x }}) = \displaystyle \sum _{i = 1}^{i = D}{\left( \sum _{k = 0}^{k = 20}{[0.5^k {\text {cos}}(2 \pi 3^k({\text {x}}_i + 0.5))]}\right) } - D \sum _{k = 0}^{k = 20}{[0.5^k {\text {cos}}(2 \pi 3^k \times 0.5)]} \end{aligned}$$

• \(f_7\)

  $$\begin{aligned} f_7({\mathbf{x }}) = \displaystyle \sum _{i = 1}^{i = D}{\frac{{\text {x}}_i^2}{4000}} - \prod _{i = 1}^{i = D}{{\text {cos}}\left( \frac{{\text {x}}_i}{\sqrt{i}}\right) } + 1 \end{aligned}$$

• \(f_8\)

  $$\begin{aligned} f_8({\mathbf{x }}) = \displaystyle \sum _{i = 1}^{i = D}{({\text {x}}_i^2 - 10 {\text {cos}}(2 \pi {\text {x}}_i) - 10)} \end{aligned}$$

• \(f_9\)

  $$\begin{aligned} f_9({\mathbf{x }}) = 418.9829 \times D - \displaystyle \sum _{i = 1}^{i = D}{g(z_i)}, \end{aligned}$$

  where \(z_i = {\text {x}}_i + 4.209687462275036\)e+002 and

  $$\begin{aligned} g(z_i) = \left\{ \begin{array}{lllllll} z_i {\text {sin}}(|z_i|^{\frac{1}{2}}), {\text { se }} |z_i| \le 500 \\ \\ \displaystyle (500 - {\text {mod}}(z_i, 500)) {\text {sin}}(\sqrt{|500 - {\text {mod}}(z_i, 500)|}) - \\ \displaystyle \frac{(z_i - 500)^2}{10{,}000D}, {\text { se }} z_i > 500 \\ \\ \displaystyle ({\text {mod}}(|z_i| - 500) - 500) {\text {sin}}(\sqrt{|{\text {mod}}(|z_i|, 500) - 500|}) - \\ \displaystyle \frac{(z_i + 500)^2}{10{,}000D}, {\text { se }} z_i < -500 \end{array} \right. \end{aligned}$$

• \(f_{10}\)

  $$\begin{aligned} f_{10}({\mathbf{x }}) = \displaystyle \frac{10}{D^2} \prod _{i = 1}^{i = D}{\left( 1 + i \sum _{j = 1}^{j = 32}{\frac{|2^j {\text {x}}_i - {\text {round}}(2^j {\text {x}}_i)|}{2^j}}\right) ^{\frac{10}{D^{1.2}}}} - \frac{10}{D^2} \end{aligned}$$

• \(f_{11}\)

  $$\begin{aligned} f_{11}({\mathbf{x }}) = \displaystyle \left| \sum _{i = 1}^{i = D}{{\text {x}}_i^2 - D}\right| ^{\frac{1}{4}} + \frac{\left( 0.5 \displaystyle \sum \nolimits _{i = 1}^{i = D}{{\text {x}}_i^2} + \sum \nolimits _{i = 1}^{i = D}{{\text {x}}_i}\right) }{D} + 0.5 \end{aligned}$$

• \(f_{12}\)

  $$\begin{aligned} f_{12}({\mathbf{x }}) = \displaystyle \left| \left( \sum _{i = 1}^{i = D}{{\text {x}}_i^2}\right) ^2 - \left( \sum _{i = 1}^{i = D}{{\text {x}}_i}\right) ^2\right| ^{\frac{1}{2}} + \displaystyle \frac{\left( 0.5 \displaystyle \sum \nolimits _{i = 1}^{i = D}{{\text {x}}_i^2} + \sum \nolimits _{i = 1}^{i = D}{{\text {x}}_i}\right) }{D} + 0.5 \end{aligned}$$

• \(f_{13}\)

  $$\begin{aligned} f_{13}({\mathbf{x }}) = f_7(f_4({\text {x}}_1, {\text {x}}_2)) + f_7(f_4({\text {x}}_2, {\text {x}}_3)) + \cdots + f_7(f_4({\text {x}}_{D - 1}, {\text {x}}_D)) + f_7(f_4({\text {x}}_D, {\text {x}}_1)) \end{aligned}$$

• \(f_{14}\)

  $$\begin{aligned} f_{14}({\mathbf{x }}) = g({\text {x}}_1, {\text {x}}_2) + g({\text {x}}_2, {\text {x}}_3) + \cdots + g({\text {x}}_{D - 1}, {\text {x}}_D) + g({\text {x}}_D, {\text {x}}_1) \end{aligned}$$

  where

  $$\begin{aligned} g({\text {y}}, {\text {z}}) = 0.5 + \displaystyle \frac{(z{sin}^2(\sqrt{{\text {y}}^2 + {\text {z}}^2}) - 0.5)}{(1 + 0.001({\text {y}}^2 + {\text {z}}^2))^2} \end{aligned}$$

Definition of the test functions:

• Unimodal Functions:

  • F1

    $$\begin{aligned} F1({\mathbf{x }}) = f_1({\mathbf{M }}_1({\mathbf{x }} - {\mathbf{o }}_1)) + F1^* \end{aligned}$$

  • F2

    $$\begin{aligned} F2({\mathbf{x }}) = f_2({\mathbf{M }}_2({\mathbf{x }} - {\mathbf{o }}_2)) + F2^* \end{aligned}$$

Simple Multimodal Functions:

• F3

  $$\begin{aligned} F3({\mathbf{x }}) = f_5({\mathbf{M }}_3({\mathbf{x }} - {\mathbf{o }}_3)) + F3^* \end{aligned}$$

• F4

  $$\begin{aligned} F4({\mathbf{x }}) = f_8\left( {\mathbf{M }}_4\left( \displaystyle \frac{5.12({\mathbf{x }} - {\mathbf{o }}_4)}{100}\right) \right) + F4^* \end{aligned}$$

• F5

  $$\begin{aligned} F5({\mathbf{x }}) = f_9\left( {\mathbf{M }}_5\left( \displaystyle \frac{1000({\mathbf{x }} - {\mathbf{o }}_5)}{100}\right) \right) + F5^* \end{aligned}$$

Hybrid Functions:

• For such functions consider:

  $$\begin{aligned} FH({\mathbf{x }}) = g_1({\mathbf{M }}_1{\mathbf{z }}_1) + g_2({\mathbf{M }}_2{\mathbf{z }}_2) + \cdots + g_N({\mathbf{M }}_N{\mathbf{z }}_N) + F^*({\mathbf{x }}), \end{aligned}$$

  where

  • \(FH({\mathbf{x }})\), such that \(H \in \{6, 7, 8\}\) is a Hybrid Function.

  • \(g_i({\mathbf{x }})\) is the ith basic function involved in a Hybrid Function.

  • N is the number of basic functions.

  • \({\mathbf{z }} = [{\mathbf{z }}_1, {\mathbf{z }}_2,\ldots , {\mathbf{z }}_N]\)

  • \({\mathbf{z }}_1 = [{\mathbf{y }}_{S_1}, \mathbf{y} _{S_2},\ldots , {\mathbf{y }}_{S_{n_1}}]\), \({\mathbf{z }}_2 = [{\mathbf{y }}_{S_{n_1 + 1}}, {\mathbf{y }}_{S_{n_1 + 2}},\ldots , {\mathbf{y }}_{S_{n_1 + n_2}}]\),

  • \({\mathbf{z }}_N = [{\mathbf{y }}_{S_{\sum _{i = 1}^{N - 1}{n_i + 1}}}, {\mathbf{y }}_{S_{\sum _{i = 1}^{N - 1}{n_i + 2}}},\ldots , {\mathbf{y }}_{S_{D}}]\)

  • \({\mathbf{y }} = {\mathbf{x }} - {\mathbf{o }}_i\)

  • \(S = {\text {permutacao}}(1:D)\)

  • \(p_i\) is used to control the percentage of \(g_i({\mathbf{x }})\)

  • \(n_i\) is the dimension for each basic function. \(\sum _{i = 1}^{i = N}{n_i} = D\)

  • \(n_1 = \lceil p_1 D \rceil\), \(n_2 = \lceil p_2 D \rceil\),..., \(n_{N - 1} = \lceil p_{N - 1} D \rceil\), \(n_{N} = D - \displaystyle \sum _{i = 1}^{i = N - 1}{n_i}\)

• F6

  • \(N = 3\)

  • \(p = [0.3, 0.3, 0.4]\)

  • \(g_1 = f_9\)

  • \(g_2 = f_8\)

  • \(g_3 = f_1\)

• F7

  • \(N = 4\)

  • \(p = [0.2, 0.2, 0.3, 0.3]\)

  • \(g_1 = f_7\)

  • \(g_2 = f_6\)

  • \(g_3 = f_4\)

  • \(g_4 = f_{14}\)

• F8

  • \(N = 5\)

  • \(p = [0.1, 0.2, 0.2, 0.2, 0.3]\)

  • \(g_1 = f_{14}\)

  • \(g_2 = f_{12}\)

  • \(g_3 = f_4\)

  • \(g_4 = f_9\)

  • \(g_5 = f_1\)

Composed Functions:

• For such functions consider:

  $$\begin{aligned} FC({\mathbf{x }}) = \displaystyle \sum _{i = 1}^{N}{\{\omega _i[\lambda _i g_i({\mathbf{x }}) + bias_i]\} + F^*}, \end{aligned}$$

  where

  • \(FC({\mathbf{x }})\), such that \(C \in \{9, 10, 11, 12, 13, 14, 15\}\) is a Composed Function.

  • N is the number of basic functions.

  • \(g_i({\mathbf{x }})\) is the ith basic function involved in a Composed Function.

  • \(\lambda _i\) is used to control the height of each \(g_i({\mathbf{x }})\).

  • \(bias_i\) define which optimal is the global optimal.

  • \(\omega _i\) is given by

    $$\begin{aligned} \omega _i = \frac{{\text {w}}_i}{\sum \nolimits _{i = 1}^{n}{{\text {w}}_i}} \end{aligned}$$

    where \({\text {w}}_i\) is given by

    $$\begin{aligned} {\text {w}}_i = \frac{1}{\sqrt{\sum \nolimits _{j = 1}^{j = D}{({\text {x}}_j - {\text {o}}_{ij})^2}}} {\text {exp}} \left( -\frac{\sum \nolimits _{j = 1}^{j = D}{({\text {x}}_j - {\text {o}}_{ij})^2}}{2 D \sigma _i^2}\right) , \end{aligned}$$

    where

    • \({\mathbf{o }}_i\) is a new optimal solution defined for each \(g_i({\mathbf{x }})\).

    • \(\sigma _i\) is used to control the range of each \(g_i({\mathbf{x }})\).

• F9

  • \(N = 3\)

  • \(\sigma = [20, 20, 20]\)

  • \(\lambda = [1, 1, 1]\)

  • \(bias = [0, 100, 200]+F9^*\)

  • \(g_1 = F5\)

  • \(g_2 = F4\)

  • \(g_3 = f_{12}\)

• F10

  • \(N = 3\)

  • \(\sigma = [10, 30, 50]\)

  • \(\lambda = [1, 1, 1]\)

  • \(bias = [0, 100, 200]+F{10}^*\)

  • \(g_1 = F6\)

  • \(g_2 = F7\)

  • \(g_3 = F8\)

• F11

  • \(N = 5\)

  • \(\sigma = [10, 10, 10, 20, 20]\)

  • \(\lambda = [10, 10, 2.5, 25, 1\)e−6]

  • \(bias = [0, 100, 200, 300, 400]+F{11}^*\)

  • \(g_1 = f_{12}\)

  • \(g_2 = F4\)

  • \(g_3 = F5\)

  • \(g_4 = f_6\)

  • \(g_5 = F1\)

• F12

  • \(N = 5\)

  • \(\sigma = [10, 20, 20, 30, 30]\)

  • \(\lambda = [0.25, 1, 1\)e−7, 10, 10]

  • \(bias = [0, 100, 100, 200, 200]+F{12}^*\)

  • \(g_1 = F5\)

  • \(g_2 = F4\)

  • \(g_3 = F1\)

  • \(g_4 = f_{14}\)

  • \(g_5 = f_{11}\)

• F13

  • \(N = 5\)

  • \(\sigma = [10, 10, 10, 20, 20]\)

  • \(\lambda = [1, 10, 1, 25, 10]\)

  • \(bias = [0, 100, 200, 300, 400]+F{13}^*\)

  • \(g_1 = F8\)

  • \(g_2 = F4\)

  • \(g_3 = F6\)

  • \(g_4 = F5\)

  • \(g_5 = f_{14}\)

• F14

  • \(N = 7\)

  • \(\sigma = [10, 20, 30, 40, 50, 50, 50]\)

  • \(\lambda = [10, 2.5, 2.5, 10, 1\)e−6, 1e−6, 10]

  • \(bias = [0, 100, 200, 300, 300, 400, 400]+F{14}^*\)

  • \(g_1 = f_{11}\)

  • \(g_2 = f_{13}\)

  • \(g_3 = F5\)

  • \(g_4 = f_{14}\)

  • \(g_5 = F1\)

  • \(g_6 = F2\)

  • \(g_7 = F4\)

• F15

  • \(N = 10\)

  • \(\sigma = [10, 10, 20, 20, 30, 30, 40, 40, 50, 50]\)

  • \(\lambda = [0.1, 2.5\)e−1, 0.1, 2.5e−2, 1e−3, 0.1, 1e−5, 10, 2.5e−2, 1e−3]

  • \(bias = [0, 100, 100, 200, 200, 300, 300, 400, 400, 500]+F{15}^*\)

  • \(g_1 = F4\)

  • \(g_2 = f_{6}\)

  • \(g_3 = f_{11}\)

  • \(g_4 = F5\)

  • \(g_5 = f_4\)

  • \(g_6 = f_{12}\)

  • \(g_7 = f_{10}\)

  • \(g_8 = f_{14}\)

  • \(g_9 = f_{13}\)

  • \(g_{10} = F3\)

Reprints and permissions