Вестник НовГУ

Вестник НовГУ > 2015 > №3 (86), часть 2 > Тихомиров А.С. Нижняя оценка трудоемкости одного класса алгоритмов отжига

Тихомиров А.С. Нижняя оценка трудоемкости одного класса алгоритмов отжига

УДК 519.676
Т и х о м и р о в А. С. Нижняя оценка трудоемкости одного класса алгоритмов отжига // Вестн. Новг. гос. ун-та. Сер.: Физико-математические науки. 2015. № 3(86), часть 2. С.32–34. Библиогр. 17 назв.

К л ю ч е в ы е с л о в а: случайный поиск, глобальная оптимизация, стохастическая оптимизация

Исследуется трудоемкость одного класса алгоритмов отжига. Показано, что для рассмотренного класса случайных поисков, обладающих естественным свойством симметрии, число вычислений целевой функции, необходимое для достижения требуемой точности ε решения задачи, не может расти медленнее, чем | lnε | .
-----------------------------------------------------------------------------
UDC 519.676
T i k h o m i r o v A. S. A lower bound on the computational complexity of one class of the simulated annealing algorithms // Vestnik NovSU. Issue: Physico-Mathematical Sciences. 2015. № 3(86), part 2. P.32–34. The reference list 17 items.

K e y w o r d s: random search, global optimization, stochastic optimization

The computational complexity of one class of the simulated annealing algorithms is investigated. It is shown that, for a wide class of random search methods which possess a natural symmetry property, the number of the objective function evaluations needed to find the extremum accurate to ε cannot increase more slowly than | lnε | .

Загрузить (427 КБ)