ГЛОБАЛЬНАЯ ОПТИМИЗАЦИЯ:… > Тестовые задачи глобальной…

Тестовые задачи глобальной оптимизации без ограничений

Ackley’s Problem

$f(x) = -20 \exp(-0.02 \sqrt{\frac{\sum_{i=1}^n x_i^2}{n}}) - \exp(\frac{\sum_{i=1}^n \cos(2 \pi x_i)}{n}) + 20 + e.$

Размерность: $n = 1, 2, \ldots, 32$ .
Область поиска: $-30 \leq x_i \leq 30$ , $i \in \{1, 2, \ldots, n\}$ .
Глобальный минимум: $f(0, 0, \ldots, 0) = 0$ .
Количество локальных минимумов: неизвестно.
Источники: [1, 2, 4, 5, 6, 7, 10, 11, 13, 14, 15]

Camel Back — 3 (Three Hump) Problem

$f(x) = 2 x_1^2 - 1.05x_1^4 + \frac 1 6 x_1^6 +x_1 x_2 + x_2^2.$

Размерность: $n = 2$ .
Область поиска: $-5 \leq x_i \leq 5$ , $i \in \{1, 2\}$ .
Глобальный минимум: $f(0, 0) = 0$ .
Количество локальных минимумов: $3$ .
Источники: [1, 4, 9, 10, 11, 12, 13, 14, 16]

Camel Back — 6 (Six Hump) Problem

$f(x) = 4 x_1^2 - 2.1 x_1^4 + \frac 1 3 x_1^6 + x_1 x_2 - 4 x_2^2 + 4 x_2^4.$

Размерность: $n = 2$ .
Область поиска: $-5 \leq x_i \leq 5$ , $i \in \{1, 2\}$ .
Глобальный минимум: $f(0.089842, -0.712656) = f(-0.089842, 0.712656) = -1.0316$ .
Количество локальных минимумов: $6$ .
Источники: [1, 2, 4, 6, 7, 9, 10, 12, 13, 14, 16]

Griewank Problem

$f(x) = 1 + \frac 1 {4000}\sum_{i=1}^n x_1^2 - \prod_{i=1}^{n} \cos(\frac{x_i}{\sqrt{i}}).$

Размерность: $n = 1, 2, \ldots, 32$ .
Область поиска: $-600 \leq x_i \leq 600$ , $i \in \{1, 2, \ldots, n\}$ .
Глобальный минимум: $f(0, 0, \ldots, 0) = 0$ .
Количество локальных минимумов: неизвестно; при $n = 2$ около $500$ .
Источники: [1, 2, 4, 5, 6, 7, 10, 11, 13, 14, 16]

Levy and Montavlo 1 Problem

$f(x) = \frac{\pi}{n}\Bigl(10\sin^2(\pi y_1) + \sum_{i=1}^{n-1}(y_i-1)^2[1+10\sin^2(\pi y_{i+1})] + (y_n-1)^2\Bigr),$

где $y_i = 1 + \frac 1 4 (x_i+1)$ .

Размерность: $n = 1, 2, \ldots, 32$ .
Область поиска: $-10 \leq x_i \leq 10$ , $i \in \{1, 2, \ldots, n\}$ .
Глобальный минимум: $f(-1, -1, \ldots, -1) = 0$ .
Количество локальных минимумов: $\approx 5^n$ .
Источники: [1, 10, 13, 14, 15]

McCormick Problem

$f(x) = \sin(x_1+x_2) + (x_1-x_2)^2 - \frac 3 2 x_1 + \frac 5 2 x_2 + 1.$

Размерность: $n = 2$ .
Область поиска: $-1.5 \leq x_1 \leq 4$ , $-3 \leq x_2 \leq 3$ .
Глобальный минимум: $f(-0.547, -1.547) \approx -1.9133$ .
Количество локальных минимумов: $2$ .
Источники: [1, 4, 10, 13, 14]

Modified Langerman Problem

$f(x) = - \sum_{j=1}^{5}c_j \cos(\frac{d_j}{\pi})\exp(-\pi d_j),$

где $d_j = \sum_{i=1}^n (x_i - a_{ji})^2$ и значения $c_j$ и $a_{ji}$ приведены в Таблице 1.

Размерность: $n = 5, 10$ .
Область поиска: $0 \leq x_1 \leq 10$ , $i \in \{1, 2, \ldots, n\}$ .
Глобальный минимум:
- $f(8.074, 8.777, 3.467, 1.867, 6.708) = -0.965$ для $n = 5$ ;
- $f(8.074, 8.777, 3.467, 1.867, 6.708, 6.349, 4.534, 0.276, 7.633, 1.567) = -0.965$ для $n = 10$ .
Количество локальных минимумов: неизвестно.
Источники: [1, 4, 9, 10]

Таблица 1. Данные для задачи Modified Langerman Problem

$j$	$c_j$	$a_{ji}$
$j$	$c_j$	$i=1$	2	3	4	5	6	7	8	9	10
1	0.806	9.681	0.667	4.783	9.095	3.517	9.325	6.544	0.211	5.122	2.020
2	0.517	9.400	2.041	3.788	7.931	2.882	2.672	3.568	1.284	7.033	7.374
3	0.100	8.025	9.152	5.114	7.621	4.564	4.711	2.996	6.126	0.734	4.982
4	0.908	2.196	0.415	5.649	6.979	9.510	9.166	6.304	6.054	9.377	1.426
5	0.965	8.074	8.777	3.467	1.867	6.708	6.349	4.534	0.276	7.633	1.567

Neumaier 2 Problem

$f(x) = \sum_{k=1}^{n}\Bigl(b_k - \sum_{i=1}^n x_i^k\Bigr)^2,$

где $b = (8, 18, 44, 114)$ .

Размерность: $n = 4$ .
Область поиска: $0 \leq x_i \leq i$ , $i \in \{1, 2, \ldots, n\}$ .
Глобальный минимум: $f(1, 2, 2, 3) = 0$ .
Количество локальных минимумов: неизвестно.
Источники: [1, 10, 13, 14, 15, 16]

Neumaier 3 Problem

$f(x) = \sum_{i=1}^{n}(x_i-1)^2 - \sum_{i=2}^n x_i x_{i-1}.$

Размерность: $n = 2, 3, \ldots, 32$ .
Область поиска: $-n^2 \leq x_i \leq n^2$ , $i \in \{1, 2, \ldots, n\}$ .
Глобальный минимум: $f(x^*) = - \frac{n(n+4)(n-1)}{6}$ , $x^*_i = i(n+1-i)$ .
Количество локальных минимумов: неизвестно.
Источники: [1, 10, 13, 16]

Paviani Problem

$f(x) = \sum_{i=1}^{10}[\ln^2(x_i-2) + \ln^2(10-x_i)] - (\prod_{i=1}^{10}x_i)^{0.2}.$

Размерность: $n = 10$ .
Область поиска: $2 \leq x_i \leq 10$ , $i \in \{1, 2, \ldots, 10\}$ .
Глобальный минимум: $f(x^*) \approx - 45.778$ , $x^*_i \approx 9.351$ .
Количество локальных минимумов: неизвестно.
Источники: [1, 4, 10, 12, 13, 14]

Rosenbrock Problem

$f(x) = \sum_{i=1}^{n-1}\Bigl(100(x_{i+1}-x_i^2)^2 + (x_i-1)^2\Bigr).$

Размерность: $n = 2, 3, \ldots, 32$ .
Область поиска: $-30 \leq x_i \leq 30$ , $i \in \{1, 2, \ldots, n\}$ .
Глобальный минимум: $f(1, 1, \ldots, 1) = 0$ .
Количество локальных минимумов: $1$ .
Источники: [1, 2, 4, 5, 6, 7, 8, 9, 10, 13, 14, 15, 16]

Salomon Problem

$f(x) = 1 - \cos(2\pi \|x\|) + 0.1 \|x\|,$

где $\|x\| = \sqrt{\sum_{i=1}^n x_i^2}$ .

Размерность: $n = 1, 2, \ldots, 32$ .
Область поиска: $-100 \leq x_i \leq 100$ , $i \in \{1, 2, \ldots, n\}$ .
Глобальный минимум: $f(x^*) = 0$ , $x^*_i = 0$ .
Количество локальных минимумов: неизвестно.
Источники: [1, 4, 10, 11, 12, 13, 14]

Schwefel Problem

$f(x) = - \sum_{i=1}^n x_i \sin(\sqrt{|x_i|}).$

Размерность: $n = 1, 2, \ldots, 32$ .
Область поиска: $-500 \leq x_i \leq 500$ , $i \in \{1, 2, \ldots, n\}$ .
Глобальный минимум: $f(x^*) = -418.9829n$ , где $x^*_i \approx 420.97$ .
Количество локальных минимумов: неизвестно.
Источники: [1, 2, 4, 5, 7, 10, 12]

Shekel 5 Problem

$f(x) = - \sum_{i=1}^{5}\frac{1}{\sum_{j=1}^4(x_j-a_{ij})^2+c_i},$

где величины $a_{ij}$ и $c_i$ приведены в Таблице 2.

Размерность: $n = 4$ .
Область поиска: $0 \leq x_i \leq 10$ , $i \in \{1, 2, 3, 4\}$ .
Глобальный минимум: $f(4, 4, 4, 4) \approx -10.1499$ .
Количество локальных минимумов: $5$ .
Источники: [1, 2, 4, 6, 8, 10, 12, 13, 14, 16]

Таблица 2. Данные для задач Shekel Problems

$i$	$a_{ij}$				$c_{ij}$
$i$	$j = 1$	$j = 2$	$j = 3$	$j = 4$	$c_{ij}$
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

Shekel 7 Problem

$f(x) = - \sum_{i=1}^{7}\frac{1}{\sum_{j=1}^4(x_j-a_{ij})^2+c_i},$

где величины $a_{ij}$ и $c_i$ приведены в Таблице 2.

Размерность: $n = 4$ .
Область поиска: $0 \leq x_i \leq 10$ , $i \in \{1, 2, 3, 4\}$ .
Глобальный минимум: $f(4, 4, 4, 4) \approx -10.3999$ .
Количество локальных минимумов: $7$ .
Источники: [1, 2, 4, 6, 8, 10, 12, 13, 14, 16]

Shekel 10 Problem

$f(x) = - \sum_{i=1}^{10}\frac{1}{\sum_{j=1}^4(x_j-a_{ij})^2+c_i},$

где величины $a_{ij}$ и $c_i$ приведены в Таблице 2.

Размерность: $n = 4$ .
Область поиска: $0 \leq x_i \leq 10$ , $i \in \{1, 2, 3, 4\}$ .
Глобальный минимум: $f(4, 4, 4, 4) \approx -10.5319$ .
Количество локальных минимумов: $10$ .
Источники: [1, 2, 4, 6, 8, 10, 12, 13, 14, 16]

Shubert Problem

$f(x) = \prod_{i=1}^n(\sum_{j=1}^5 j \cos((j+1)x_i + j)).$

Размерность: $n = 2$ .
Область поиска: $-10 \leq x_i \leq 10$ , $i \in \{1, 2\}$ .
Глобальный минимум: 18 точек глобального минимума, $f^* \approx -186.7309$ .
Точки глобального минимума приведены в Таблице 3.
Количество локальных минимумов: $760$ .
Источники: [1, 2, 4, 6, 8, 10, 12, 13]

Таблица 3. Точки глобального минимума для задачи Shubert Problem

(-7.0835, 4.8580)	(-7.0835, -7.7083)	(-1.4251, -7.0835)	(5.4828, 4.8580)	(-1.4251, -0.8003)	(4.8580, 5.4828)
(-7.7083, -7.0835)	(-7.0835, -1.4251)	(-7.7083, -0.8003)	(-7.7083, 5.4828)	(-0.8003, -7.7083)	(-0.8003, -1.4251)
(-0.8003, 4.8580)	(-1.4251, 5.4828)	(5.4828, -7.7083)	(4.8580, -7.0835)	(5.4828, -1.4251)	(4.8580, -0.8003)

Использованные источники

M.M. Ali, C. Khompatraporn, Z.B. Zabinsky. A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems. Journal of Global Optimization, 31(4), 635-672. (2005)
M. Laguna, R. Marti. Experimental Testing of Advanced Scatter Search Designs for Global Optimization of Multimodal Functions, Journal of Global Optimization, V. 33, 235-255. (2005)
H.E. Romeijn, R.L. Smith. Simulated annealing for constrained global optimization. Journal of Global Optimization 5(2): 101-126. (1994)
M. Jamil and X.S. Yang. A literature survey of benchmark functions for global optimization problems, Int. Journal of Mathematical Modelling and Numerical Optimization, Vol. 4, №2, 150-194. (2013)
J. Teo. Global Optimization Accuracy and Evolutionary Dynamics of the Generalized Generation Gap Algorithm with Adaptive Mutation. Malaysian Journal of Computer Science, 19(2): 159-167. (2006)
Q. Tao, X. Huang, S. Wang, L. Li. Adaptive block coordinate DIRECT algorithm. Journal of Global Optimization. 69:4, 797-822. (2017)
X.S. Yang. Test Problems in Optimization. Engineering Optimization: An Introduction with Metaheuristic Applications, John Wiley & Sons. (2010)
R. Paulavicius, J. Zilinskas, A. Grothey. Investigation of selection strategies in branch and bound algorithm with simplicial partitions and combination of Lipschitz bounds. Optimization Letters, 4:173-183. (2010)
Z. Nedelkova, P. Lindroth, M. Patriksson, A.B. Stromberg. Efficient solution of many instances of a simulation-based optimization problem utilizing a partition of the decision space. Annals of Operation Research, 1-26. (2017)
K. M. Mullen. Continuous Global Optimization in R. Journal of Statistical Software, 60:6, 1-45. (2014)
N.S. Teng, M.H.A. Hijazi and J. Teo. Self-adaptive Scaling Factor in Differential Evolution. Regional Conference on Computational Science and Technologies (RCCST 2007), 112-116. (2007)
Y. Alipouri, J. Poshtan, H. Alipouri. Improvement of Classical Evolutionary Programming using State Feedback Controller. Int. J. of Innovative Computing, Information and Control, Vol.10, № 4, 1413-1433. (2014)
N. Henderson, M. Sa Rego, W.F. Sacco, R.A. Rodrigues. A new look at the topographical global optimization method and its application to the phase stability analysis of mixtures. Chemical Engineering Science. 127: 151-174. (2015)
F. Shahzad, S. Masood, N. K. Khan. Probabilistic opposition-based particle swarm optimization with velocity clamping, Knowledge and Information Systems, Vol. 39, Issue 3, 703-737. (2014)
Q. Abbas, J. Ahmad, H. Jabeen. A novel tournament selection based differential evolution variant for continuous optimization problems. Mathematical Problems in Engineering, Article ID 205709, 21pp. (2015)
L. G. Casado, I. Garcia, T. Csendes, V.G. Ruiz. Heuristic Rejection in Interval Global Optimization. Journal of Optimization Theory and Applications, Vol. 118, №1, 27-43. (2003)