СИСТЕМЫ АНАЛИЗА И ОБРАБОТКИ ДАННЫХ

Изложена идея конструирования базового алгоритма глобальной оптимизации на множестве непрерывных и дискретных переменных с упорядоченными возможными значениями при наличии ограничений типа неравенств. В основе алгоритма лежит разнесение во времени пробных и рабочих шагов, селективное усреднение искомых переменных по результатам пробных движений, адаптивная перестройка размеров множества возможных пробных движений и учет ограничений типа неравенств.

Основная существующая схема поиска (с селективным усреднением) непрерывных переменных переносится на смешанные переменные, в которых дискретные переменные имеют упорядоченные возможные значения. Для каждой дискретной переменной ставится в соответствие непрерывная вспомогательная безразмерная переменная. Она содержит как номера возможных значений дискретной переменной, так и одинаковые примыкающие друг другу единичные интервалы, охватывающие эти номера. Номера располагаются в центре интервалов. Вспомогательная переменная на каждом рабочем шаге имеет свой фиксированный интервал возможных значений.

При генерировании каждой пробной точки для соответствующей дискретной переменной на непрерывном интервале вспомогательной переменной датчиком равномерно распределенной непрерывной случайной величины вычисляется псевдослучайное число, и оно попадает на один из интервалов, в центре которого находится номер дискретного возможного значения. Далее дискретное значение с этим номером участвует в вычислении минимизируемой функции и функций ограничений типа неравенств. По каждой дискретной переменной расчеты нового центра поисковых движений и размера множества поисковых движений вначале ведется по непрерывной вспомогательной переменной, а затем выполняется переход к дискретным возможным значениям.  Размерность задачи оптимизации при таком подходе не меняется. Сложность расчетов по сравнению с наличием только непрерывных переменных возрастает незначительно. Пример демонстрирует возможность получения близкой к единице оценки вероятности попадания вычисленных переменных в малую окрестность истинного решения даже при высокомуровнеаддитивнойпомехиизмеренияминимизируемойфункции.

1. Стронгин Р.Г. Поиск глобального оптимума. – М.: Знание, 1990. – 48 с.

2. Жиглявский А.А., Жилинскас А.Г. Методы поиска глобального оптимума. – М.: Наука, 1991. – 247 с.

3. Horst R., Tuy H. Global optimization – Deterministic approaches. – 3rd ed. – Berlin: Springer, 1996. – 729 p.

4. Zhigljavsky A., Zilinskas A. Stochastic global optimization. – Berlin: Springer, 2008. – 269 p.

5. Сергеев Я.Д., Квасов Д.Е. Диагональные методы глобальной оптимизации. – М.: Физматлит, 2008. – 352 с.

6. Пантелеев А.В. Метаэвристические алгоритмы поиска глобального экстремума. – М.: МАИ-Принт, 2009. – 159 с.

7. Weise T. Global optimization algorithms. Theory and Application. – 3rd ed. – [S. l.]: University of Science and Technology of China, 2011. – 1217 p.

8. Хансен Э., Уолстер Дж.У. Глобальная оптимизация с помощью методов интервального анализа. – М.; Ижевск: РХД, Институт компьютерных исследований, 2012. – 520 с.

9. Leyffer S. Integrating SQP and branch-and-bound for mixed integer nonlinear programming // Computational Optimization and Applications. – 2001. – Vol. 18. – p. 295–309.

10. Fletcher R., Leyffer S. Solving mixed integer nonlinear programs by outer approximation // Mathematical Programming. – 1994. – Vol. 66. – p. 327–349.

11. Bagajewicz M., Manousiouthakis V. On the Generalized Benders Decomposition // Computers and Chemical Engineering. – 1991. – Vol. 15 (10). – p. 691–700.

12. Westerlund T., Pettersson T. An extended cutting plane method for solving convex MINLP problems // Computers and Chemical Engineering. – 1995. – Vol. 19, suppl. – p. 131–136.

13. Liberti L., Nannicini G., Mladenovic N. A good recipe for solving MINLP // Metaheuristics: Hybridizing Metaheuristics and Mathematical Programming. – New York, Springer, 2009. – p. 231–245. – (Annals of Information Systems; vol. 10).

14. Rouban A.I. Method for global optimization in continuous space // Advances in Modelling & Analysis: Series A. – 2003. – Vol. 40 (4). – p. 9–28.

15. Рубан А.И. Глобальная оптимизация методом усреднения координат. – Красноярск: ИПЦ КГТУ, 2004. – 303 с.

16. Рубан А.И. Метод глобальной оптимизации, основанный на селективном усреднении координат при наличии ограничений // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. – 2013. – Вып. 1 (22). – С. 114–123.

17. Mikhalev A.S., Rouban A.I. Algorithms of global optimization of functions on set of the mixed variables: continuous and discrete with unordered possible values // Advances in Modelling & Analysis: Series D. – 2015. – Vol. 20, N 1. – p. 56–75.

18. Mikhalev A.S., Rouban A.I. Global optimization on set of mixed variables: continuous and discrete with unordered possible values // IOP Conference Series: Materials Science and Engineering. – 2016. – Vol. 122. – Art. 012024. – doi: 10.1088/1757-899X/122/1/012024.

19. Бочаров И.Н., Фельдбаум А.А. Автоматический оптимизатор для поиска минимального из нескольких минимумов (глобальный оптимизатор) // Автоматика и телемеханика. – 1962. – № 3. – С. 289–301.