Введение
Метод брянских партизан (МБП) предназначен для поиска наибольших и/или наименьших экстремумов функции одной или нескольких переменных при многомерной оптимизации. Он основан на принципе дихотомии и методе Монте-Карло, относится к интеллектуальным методам поиска оптимальных параметров управления и может быть использован в автоматизированных и интеллектуальных автоматизированных системах управления технологическими процессами, для которых характерен непрерывный в режиме реального времени расчёт глобального оптимума по целевой функции (ЦФ) процесса при различных, варьирующихся во времени входных данных (параметров управления и внешних воздействий).
Название МБП связано с тактикой брянских партизан, которые во время Второй мировой войны вначале небольшими силами проводили разведку и находили объект нападения, а потом осуществляли диверсию: большими силами и в разных местах одновременно, «цепочечными» взрывами подрывали автоколонны, вражеские штабы, железнодорожные составы, мосты и т.п.
МБП действует аналогично: сначала производит «разведку» в области определения функции – находит зону с наилучшим экстремумом (объектом нападения), а потом выполняет «диверсию» – определяет в выделенной зоне позицию глобального экстремума функции.
Задача для параметрической оптимизации в общем случае имеет вид: cуществует n параметров управления, которые образуют вектор Х (х1, х2, …, хi, …, хn), задающий область определения (ОО) ЦФ F(Х). Требуется найти экстремум F(Х) и параметры вектора Х(х1, х2, …, хi, …, хn), которые экстремум обеспечивают.
Алгоритм МБП для поиска экстремума
Общий алгоритм содержит два этапа:
• этап разведки, при котором выполняется локализация позиции наилучшего экстремума в ОО функции небольшими силами, для чего:
- для каждого аргумента хi функции ОО делится пополам, в итоге образуется несколько зон m = 2n, где n – количество аргументов функции, при этом ОО функции с одной переменной разбивается на две зоны, функция с двумя переменными – на четыре, с тремя – на восемь и т.д.;
- в каждой полученной зоне посредством генератора случайных чисел (ГСЧ) инициируются позиции нескольких точек со случайными координатами – агентов зоны ki;
- рассчитываются значения ЦФ для полученных позиций агентов ki;
- из полученных значений ЦФ выбирается локальный экстремум и выделяется зона ОО, которая его содержит. Тем самым первоначальная ОО становится меньше в 2n раз;
• этап диверсии, при котором производится массированное, большими силами «нападение» на объект:
- для найденной на этапе разведки зоны ОО выполняется через ГСЧ генерация большого числа, до 100–200 и выше новых позиций агентов ki;
- рассчитываются величины ЦФ для всех новых позиций агентов ki;
- выбирается агент с наилучшим экстремумом ЦФ и находятся координаты его позиции – аргументы агента. Таким образом, определяется глобальный оптимум всей ЦФ и его параметры – координаты ОО функции.
Примечания
- На первом этапе во время деления ОО ЦФ на зоны и инициализации в зонах малого числа агентов (рис. 1) возможен вариант, когда в зоне 1, содержащей истинный экстремум ЦФextr, найденный для неё оптимум ЦФ1 будет меньше значения ЦФ2 в зоне 2, которая не содержит глобальный экстремум всей функции.
Для повышения надёжности выделения зоны ОО с глобальным экстремумом возможно использование двух вариантов:
• в каждой зоне следует активировать минимум 30 агентов (так как в соответствии с теорией математической статистики проведение 30 и более испытаний становится статистически значимым для достоверности полученных результатов [1]). Поэтому нужно инициировать в каждой зоне по 30 агентов, а поскольку ГСЧ, используемый в компьютерах, инициирует псевдослучайные числа по равномерному закону распределения [2], то агенты будут равномерно располагаться в зоне, а не сосредотачиваться в одной её части;
• для уменьшения на первом этапе зоны с глобальным экстремумом следует для каждого параметра разбивать ОО не пополам, а на три, четыре и более части, и в каждой зоне активировать минимум 30 агентов. Количество зон разбиения и позиций агентов зависит как от величины ОО, так и от степени крутизны функции на разных интервалах ОО и уточняется проверочными запусками алгоритма МБП. - Повышение точности достижения глобального экстремума в зоне диверсии обеспечивается увеличением числа агентов ki до 300–500.
- Чтобы уменьшить количество агентов на этапе диверсии (например, до статистически значимых 50–100), следует над выделенной зоной ещё один или несколько раз повторить операции первого этапа.
Работа МБП для функции двух переменных F(x, y) =3–(x–2) 2–0,5(y–2)2 проиллюстрирована на рис. 2…4.
Разбиение исходной ОО функции на четыре зоны показано на рис. 2.
На рис. 3 в зонах активировано по одному случайному агенту, рассчитаны их экстремумы, и по величине лучшего локального оптимума выделена ОО, уменьшенная в 4 раза.
В выделенной зоне активировано большое число позиций агентов, для каждого по ЦФ вычислены их экстремумы и определён наилучший из них: глобальный экстремум F(x,y)extr.
На рис. 4 приведена ОО, уменьшенная в 8 раз при повторном выполнении первого этапа МБП над выделенной зоной, и глобальный экстремум всей функции F(x,y)extr.
Алгоритм МБП имеет вид.
- Задать целевую функцию F(x1, x2, …, xn) и её область определения.
- Для каждого параметра хi разделить интервал его изменения пополам или на 3–6 частей, т.е. разбить область определения функции на несколько зон.
- В каждой зоне инициировать посредством ГСЧ до 30 случайных позиций агентов.
- Рассчитать значения ЦФ для позиции каждого агента в каждой зоне.
- Определить величину наилучшего локального экстремума ЦФ в каждой зоне (см. рис. 2).
- Определить зону его расположения.
- В найденной зоне ОО инициировать посредством ГСЧ от 100 до 500 позиций агентов.
- Вычислить значения ЦФ для позиций всех агентов.
- Найти наилучшее значение экстремума ЦФ F(x1, x2, …, xn)extr – глобальный оптимум функции и координаты позиции его агента.
Анализ работы программы МБП
Для проверки работы метода на языке Python разработана программа, определяющая как глобальный минимум, так и глобальный максимум функции. Интерфейс программы позволяет вводить функцию, аргументы функции с интервалами их изменения, задавать количество разбиений исходной ОО, число агентов на первом и втором этапах, а также запускать программу для вывода значений максимальных и минимальных оптимумов с их координатами и временем выполнения программы.
На рис. 5 показаны интерфейс программы и окно результатов расчёта.
Работа программы проверялась для функций разного вида с числом переменных от 1 до 3, среди которых тестовые функции Де Джонга и Розенброка и две производственные функции механической скорости бурения скважины (с одной переменной – для бурового автомата и с тремя переменными – для АСУ бурения).
Результаты приведены в таблице.
-
Тестовая функция Де Джонга («сфера») является непрерывной, выпуклой и унимодальной, показана на рис. 6 и имеет вид:
Функция имеет глобальный минимум f(x) = 0 в точке xi = 0 при i = 1..., n.
Программа МБП запускалась для функции Де Джонга с двумя переменными (интервалы изменения аргументов [–5; 5]) и с тремя переменными (интервалы изменения [–2; 2] и [–5; 5]) с разным числом повторений 1-го этапа и числом агентов на обоих этапах. Результаты приведены в таблице. -
Тестовая функция Розенброка («банан») показана на рис. 7 и имеет вид:
Функция имеет большое убывающее плато с одним минимумом, поэтому конвергенция к нему трудна, что используется для оценки работы алгоритмов оптимизации. Глобальный минимум f(x) = 0 в точке xi = 1 при i = 1, ,,,, n. -
Функция механической скорости бурения для АСУ бурением нефтегазовой скважины с тремя параметрами управления G, n, Q.
-
Функция механической скорости бурения для бурового автомата нефтегазовой скважины с одним параметром управления G.
Заключение
Разработан интеллектуальный метод брянских партизан, позволяющий определять глобальный экстремум (минимум и максимум) многомерной функции при оптимальном управлении технологическими процессами. Анализ работы МБП показал следующие результаты:
- время работы программы составляет десятки – сотни миллисекунд;
- длительность вычислений в большей степени зависит от числа разбиения ОО на зоны, чем от числа агентов на 1-м и 2-м этапах;
- для функций с глобальным минимумом один и тот же максимум может наступать при разных позициях агентов и наоборот;
- длительность расчёта управляющих параметров с помощью МБП имеет порядок десятых/сотых долей секунды, что практически не оказывает влияния на скорость работы систем управления производственным процессом, так как реальные исполнительные механизмы управляемых объектов обычно являются инерционными и имеют минимальное время реакции порядка нескольких секунд;
- получение гарантированно достоверного значения глобального оптимума обеспечивается также повторным (от 3 до 5 раз) выполнением поиска экстремума методом брянских партизан.
Литература
- Гмурман В.Е. Теория вероятностей и математическая статистика: учеб. пособие для вузов. 9-е изд. стер. М.: Высш. шк., 2003. 479 с.
- Пантелеев А.В. Методы глобальной оптимизации. Метаэвристические стратегии и алгоритмы / А.В. Пантелеев, Д.В. Метлицкая, Е.А. Алешина. М.: Вузовская книга, 2013. 244 с.
Если вам понравился материал, кликните значок - вы поможете нам узнать, каким статьям и новостям следует отдавать предпочтение. Если вы хотите обсудить материал - не стесняйтесь оставлять свои комментарии : возможно, они будут полезны другим нашим читателям!