Веялко И.А.
Тестирование метода решения невыпуклых релейных задач оптимального управления, основанного на операторе Шепарда
Невыпуклые задачи оптимального управления нередко встречаются на практике, поэтому вопрос поиска глобального экстремума функционала особенно актуален. К настоящему времени имеется не так много инструментов для решения этой задачи. Большинство известных методов глобальной оптимизации основано на идее мультистарта [1] - запуска стандартных локальных алгоритмов из множества стартовых точек, равномерно распределенных на определённом множестве.
В докладе рассматривается метод поиска глобального экстремума в задачах оптимального управления с релейным управлением, основанный на операторе Шепарда, который до настоящего времени практически не применялся при разработке методов глобальной оптимизации. Впервые этот оператор был рассмотрен в качестве средства обработки картографических материалов [2]. Представляется, что возможности данного подхода гораздо шире и к настоящему моменту полностью не раскрыты. В докладе рассматривается метод, основанный на последовательном улучшении аппроксимации поверхности целевого функционала в терминальном фазовом пространстве и сокращении вычислительных затрат путем игнорирования заведомо неэффективных управлений с использованием функции Шепарда - "метод Шепарда".
Целью работы является исследование свойств метода Шепарда на основе вычислительного эксперимента: 1) проверка влияния алгоритмических параметров (число точек дискретизации, число точек переключения управления, стартовое число проб) на полученный результат; 2) сравнение работы метода с методом случайного мультистарта [3] по критериям (точность, надёжность, количество задач Коши); 3) выяснение способности метода решать "сложные" задачи.
В результате проведённого исследования и вычислительных экспериментов можно заключить: а) как правило, лучший набор алгоритмических параметров зависит от конкретной задачи, но для получения лучшего результата лучше использовать минимальное число переключений управления; б) метод Шепарда уступает методу мультистарта в надёжности и точности, но значительно быстрее справляется с поставленной задачей; в) метод решил большинство задач из тестовой коллекции "сложных" задач, но для небольшого промежутка времени.
Работа поддержана грантами РФФИ \No~09-07-00267.
Список литературы
- Жиглявский А.А., Жилинскас А.Г. Методы поиска глобального экстремума. - Москва: Наука, 1991. - 248 с.
- Shepard D. A two-dimensional interpolation function for irregularly-spaced data // Proc. of the 23 ACM National Conference, ACM Press, New York. - 1968. - p. 517--524.
- Горнов А.Ю. Вычислительные технологии решения задач оптимального управления. - Новосибирск: Наука, 2009. - 279 с.
К списку докладов