Аннотация
Развитие теории и практики глобальной оптимизации требует не только улучшать существующие и синтезировать новые эффективные методы и алгоритмы недифференцируемой оптимизации при наличии сравнительно простых ограничениях типа неравенств, но и учитывать реально существующие более сложные ограничения неравенства и общие ограничения равенства. В статье изложен способ конструирования алгоритмов недифференцируемой глобальной оптимизации при наличии ограничений типа равенств. в основе алгоритмов лежит: 1) разнесение во времени пробных и рабочих шагов, 2) селективное усреднение искомых переменных по результатам экспериментальных данных, полученных в пробных точках, 3) учёт ограничений типа равенств в многомерном ядре при выполнении рабочих шагов, 4) адаптивная пошаговая перестройка размеров прямоугольной области пробных движений, 5) использование в алгоритмах только относительных значений всех функций (оптимизируемой и ограничений). При ограничениях типа равенств в базовой схеме глобальной оптимизации нормированные ядра становятся многомерными. Эти ядра построены с использованием произведения одномерных ядер по минимизируемой функции и по всем функциям ограничений равенств. Сжатие всех функций ограничений в одну обобщенную функцию позволило уменьшить размерность ядер до двух. Существенное упрощение структуры алгоритмов и числа настраиваемых параметров достигнуто за счёт перехода в аргументах ядер к безразмерным переменным, лежащим в интервале [0; 1]. На численных примерах продемонстрирована высокая скорость сходимости алгоритмов, высокая точность получаемого решения и близкая к единице оценка вероятности отыскания истинного решения даже при высоком уровне аддитивной помехи для минимизируемой функции.
Ключевые слова: глобальная оптимизация, селективное усреднение, искомая переменная, ограничения типа равенств, пробное движение, рабочий шаг, многомерное ядро, недифференцируемая функция, нормированное ядро, аддитивная помеха
Список литературы
1. Spall J.C. Multivariate Stochastic Approximation Using a Simultaneous Perturbation Gradient Approximation // IEEE Transactions on Automatic Control. – 1992. – Vol. 37, iss. 3. – P. 332–341.
2. Kushner H.J., Yin G.G. Stochastic Approximation Algorithms and Application. – New York: Springer Verlag, 1997. – 415 p.
3. Chin D.C. Comparative Study of Stochastic Algorithms for System Optimization Based on Gradient Approximation // IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics. – 1997. – Vol. 27, iss. 2. – P. 244–249.
4. Красовский А.А. Селективно-усреднительный метод решения многоэкстремальных задач // Автоматика и телемеханика. – 1992. – № 9. – C. 117–128.
5. Каплинский А.И., Пропой А.И. Методы нелокальной оптимизации, использующие теорию потенциала // Автоматика и телемеханика. – 1993. – № 7. – C. 55–65.
6. Пропой А.И. Задачи оптимизации и обучения для нелокального поиска в возбудимых средах // Автоматика и телемеханика. I: 1996. – № 1. – C. 57–66; II: 1997. – № 3. – C. 68–81; III: 1997. – № 4. – С. 54–64.
7. Пропой А.И. Задача обучения для нелокального поиска в волновых средах // Автоматика и телемеханика. I: 1998. – № 1. C. 120–126; II: – 1998. – № 2. – C. 84–90; III: 1998. – № 3. – C. 98–106.
8. Медведев А.В, Цыкунова И.М. Об алгоритмах случайного поиска // Применение вычислительных машин в системах управления непрерывными производствами. – Фрунзе: Илим, 1975. – С. 81–92.
9. Рубан А.И. Метод непараметрической оптимизации стохастических объектов // Системы управления: сб. науч. работ. – Томск: Изд-во ТГУ, 1975. – Вып. 1. – С. 101–107.
10. Экстремальная радионавигация / В.И. Алексеев, А.М. Кориков, Р.И. Полонников, В.П. Тарасенко. – М.: Наука, 1978. – 280 с.
11. Рубан А.И. Метод непараметрической поисковой глобальной оптимизации // Кибернетика и вуз: сб. науч. работ. – Томск: ТПУ, 1994. – Вып. 28. – С. 107–114.
12. Рубан А.И. Метод непараметрической поисковой оптимизации // Известия вузов. Физика. – 1995. – Т. 38, № 9. – С. 65–73.
13. Рубан А.И. Глобальная оптимизация методом усреднения координат. – Красноярск: ИПЦ КГТУ, 2004. – 303 с.
14. Комплекс программ «Global Optimizer v2.0»: свидетельство о государственной регистрации программ для ЭВМ № 2011617970 “Global Optimizer v2.0” / А.В. Кузнецов, А.И. Рубан. – Зарегистрировано Роспатентом в Реестре программ для ЭВМ 12 октября 2011 г.
