Об использовании эвристических алгоритмов в задачах оптимального параметрического синтеза

Размещено на http://www.allbest.ru/

Институт автоматики и процессов управления ДВО РАН, Владивосток

Об использовании эвристических алгоритмов в задачах оптимального параметрического синтеза

О.В. Абрамов, д-р техн. наук,

А.Д. Лагунова

Аннотация

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

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

Введение

Проблема оптимального параметрического синтеза (ОПС) технических устройств и систем с учетом стохастических закономерностей отклонений их параметров от расчетных и требований надежности связана с необходимостью решения задач высокой вычислительной сложности. Суть ОПС состоит в поиске таких начальных (номинальных) значений параметров элементов системы (внутренних параметров), при которых обеспечивается максимальная вероятность выполнения условий работоспособности в течение заданного времени эксплуатации. При этом предполагается, что структура (топология) проектируемой системы и ее математическая модель известны [1, 2]. Функции, описывающие проектируемую систему, обычно имеют сложный нелинейный характер, что не позволяет получить оптимальное решение в аналитической форме с помощью классических методов дифференциального и вариационного исчисления. Поэтому для решения задачи ОПС необходимо использовать алгоритмические поисковые методы. Стохастический характер критерия оптимальности, многомерность пространства поиска, необходимость решения задачи глобальной оптимизации заставляют искать пути создания эффективных численных методов решения задач ОПС. Одним из наиболее радикальных путей решения задач высокой вычислительной сложности является использование технологии параллельных (распределенных) вычислений [2, 3]. Однако большинство методов поисковой оптимизации имеют принципиально последовательный характер. Свойством потенциального параллелизма обладает разве что метод сканирования (полного перебора) [4, 5]. Вместе с тем в последнее время все большее внимание привлекают эвристические методы оптимизации, которые в большинстве своем поддаются распараллеливанию. Идея создания эффективных эвристических алгоритмов поисковой оптимизации, ориентированных на решение задач ОПС, рассматривается в данной работе. Основное внимание уделяется алгоритму летучих мышей и созданию его параллельной модификации. Проведен анализ алгоритма летучих мышей, а также исследовано влияние увеличения количества стай, популяции и итераций на примере задачи выбора номинальных значений параметров электронной схемы. Для реализации алгоритма был разработан программный модуль на языке Python.

Эвристический роевой алгоритм летучих мышей

Роевой интеллект, описывающий коллективное поведение децентрализованной самоорганизующейся системы, является наиболее известным представителем эвристических методов. На данный момент существует большое количество роевых алгоритмов - , например, метод роя частиц, алгоритм стаи серых волков, алгоритм кукушки, муравьиный алгоритм и пр. [6].

Одним из последних разработанных поисковых алгоритмов этого типа является алгоритм летучих мышей. Алгоритм летучих мышей (Bat Algorithm, BA) - метаэвристический алгоритм, разработанный Янгом (Xin-She Yang) в 2010 г. [7], имитирующий свойство эхолокации летучих мышей [8]. Являясь несколько более сложным, чем большинство других роевых алгоритмов, он обеспечивает достаточно высокую эффективность при меньших временных затратах.

В основу алгоритма BA положены следующие правила:

благодаря эхолокации мыши определяют расстояние до добычи;

передвижение мышей хаотично. Текущее положение и скорость і-й

мыши равны соответственно Xi = (X1, xd) и Vi = (vi, vd), i = 1, ..., N; N - размерность популяции; D - размерность пространства поиска. Для поиска добычи мыши генерируют сигналы с частотой ia и громкостью ai. В процессе поиска мыши могут менять частоту сигнала, а также частоту повторения излучаемых импульсов r Є [0;1];

3) частота сигналов изменяется в диапазоне [wmn, wmax] wmax> wmn > 0, а громкость сигналов - в пределах [0;1].

На этапе инициализации алгоритма начальные значения частот ю0, громкостей ai0 и частот повторения импульсов ri0, i = 1, ..., N полагаются равномерно распределенными в соответствующих интервалах [wmm, wmax], [amm, amax], [0, 1]. Миграция летучей мыши bi, i = 1, ..., N описывается следующими соотношениями [7, 9]:

где xi ', xi - новые и старые координаты i-й мыши; vi ', vi - новое и старое значения скорости i-й мыши; R(0;1) - случайное число из интервала (0;1). Случайный локальный поиск выполняется по следующей схеме:

Случайным образом варьируется текущее положение i-й летучей мыши bi:

где xi', xi - новые и старые координаты i-й мыши, i = 1, ..., N; a - текущее среднее значение громкостей всех летучих мышей в популяции, такое что

R (-1, 1) - величина, равномерно распределенная на интервале от -1 до 1.

Вычисляется значение целевой функции в новой точке: f(xi') = fi. Если оно лучше предыдущего значения, т.е. fi'< fi, то процедура локального поиска завершается, в противном случае фиксированное число раз осуществляется возврат к шагу 1.

Эволюция параметров ai и ri осуществляется по правилам:

где ait+1, ait - громкости i-й мыши соответственно на (t + 1)-й и t-й итерациях, i = 1, ..., N; rP - частота повторения импульсов i-й мышью при инициализации; rit+1- частота повторения импульсов i-й мышью на (t + 1)-й итерации; t -номер поколения (итерации); ba (0, 1), br > 0 - заданные константы (свободные параметры), значения которых равны 0.9 [7, 9].

Параллельная реализация алгоритма летучих мышей

Алгоритм ВА достаточно эффективен для задач оптимизации, однако средняя погрешность на некоторых функциях может оказаться достаточно большой [10]. Для ее уменьшения требуется значительное увеличение времени и количества расчетов целевой функции, что, в свою очередь, не всегда гарантирует высокой вероятности нахождения точного экстремума.

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

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

Рис.1. Разделение пространства поиска для функции Химмельблау: а) 1 процесс; б) 2 процесса; в) 3 процесса; г) 4 процесса.

Для удобства обозначим BA(N) - алгоритм летучих мышей, запущенный для N - различных стай, каждая из которых выполняет поиск на отдельной «территории», и результаты поиска обрабатываются в отдельном процессе.

Для реализации параллельных вычислений можно использовать библиотеку MPI (mpi4py) языка Python.

В общем виде реализуется следующий алгоритм:

задается число процессов N и начальные данные (целевая функция, границы области поиска, количество итераций, количество летучих мышей в стае, начальные параметры алгоритма);

нулевой процесс делит область поиска на n равных частей и передает их всем процессам (в том числе себе);

все процессы выполняют алгоритм BA на заданных интервалах, после чего передают результаты в нулевой процесс;

нулевой процесс обрабатывает полученные данные и выдает результат.

Исследование эффективности алгоритма

В ходе исследований алгоритм BA был реализован в классическом виде. Также была реализована возможность задать такие параметры работы алгоритма как: максимальное количество итераций, размер популяции, количество варьируемых параметров для нахождения оптимального значения целевой функции и их области допустимости, ограничения на входные характеристики. Для оценки эффективности алгоритма использовались: наименьшее время работы алгоритма в секундах (time); наибольшие найденные значения целевой функции (запаса работоспособности) - F(W*). Значение целевой функции вычисляется с точностью 1*10-7.

Для проверки эффективности алгоритма решим задачу выбора номинальных значений параметров схемы транзисторно-транзисторной логики [11]. Пусть требуется рассчитать оптимальные значения параметров резисторов R1, R2, R3, R4 (варьируемые параметры) в ИС ТТЛ, принципиальная схема которой изображена на рис. 2.

Единицы измерения, интервалы допуска на варьируемые параметры и выходные характеристики даны в табл. 1, 2.

Таблица 1

Таблица 2

Условия работоспособности связаны с параметрами элементов схемы следующими соотношениями [12]:

Целевую функцию будем искать согласно предложенным в [12] формулам. При оптимизации схемы нужно найти такой вектор W*, который обеспечивает максимум минимального запаса работоспособности схемы в допустимой области пространства управляемых параметров, т.е.

где F - целевая функция; W - вектор управляемых параметров; Zj - оценка запаса работоспособности.

Оценку запаса работоспособности целесообразно нормировать с учетом технологического разброса значений параметров [13]:

где Sj - величина, характеризующая разброс j-го параметра; щ - весовой коэффициент; TTj - граница поля допуска для j-го входного параметра; yjnom - вычисленное фактическое значение j-го входного параметра.

В частном случае нормального распределения параметра yj под Sj можно понимать утроенное среднее квадратичное отклонение. Тогда оценка Zj равна количеству трехсигмовых допусков на j-й выходной параметр, укладывающийся в интервал [yjnom, TTj]. Значения Sj взяты равными 20% от TTj [13]. Весовой коэффициент aj определяет степень важности параметра и его приоритет при распределении запаса работоспособности. Так, наиболее важные параметры относят к первой группе, а наименее важные - ко второй. Значение коэффициента для параметров первой группы всегда равно 1. Для параметров второй группы значение выбирается в интервале [5; 50], при этом чем больше значение aj, тем меньший запас работоспособности получит j-й параметр. Согласно [11], все входные параметры, кроме S, принадлежат первой группе. Действительно, транзистор Т2 обязательно должен входить в насыщение, но заметное перевыполнение условия работоспособности параметра S нецелесообразно, вследствие чего ему была дана оценка aj =10.

Поскольку мы не знаем вид целевой функции, воспользуемся формулой для функции общего вида [10], согласно которой оптимальное количество популяции и итераций равны 504 и 50-60 соответственно. Для параметров p = 500 и i = 50 алгоритм летучих мышей нашел решение:

F(W*) = 0,643802,

t = 0,613 сек.

Сравним полученные результаты с часто используемой в системах автоматизированного проектирования (САПР) программой расчета параметров компонентов (РПК) [12] и параллельным алгоритмом построения области работоспособности (ОР) с помощью регулярной сетки [16]. Как видно из табл. 3, вычисленный минимальный запас работоспособности оказался в 4,5 раза больше, чем в случае использования алгоритма РПК, и в 4,2 раза больше, чем при использовании алгоритма регулярной сетки.

Таблица 3

Наилучшие значения параметров, заданных интервалами допуска, должны находиться как можно ближе к середине этих интервалов. Если же задана только верхняя или нижняя граница интервала, то оптимальное значение должно находиться как можно дальше от границы. Из рис. 3 и 4 видно, что алгоритм ВА наравне с алгоритмом построения ОР с помощью регулярной сетки справился с этой задачей намного лучше, чем РПК.

Тем не менее, получив достаточно хороший запас для большинства критериев работоспособности, предложенные в [12] и [15] алгоритмы дали слишком малый запас для критерия t (рис. 5). Однако совмещение метода расчета запаса работоспособности из [12] с оптимизационным алгоритмом BA позволило найти решение с большим запасом работоспособности, ускорив при этом время расчетов и повысив точность вычислений, вплоть до 15 знаков после запятой.

Рис.5. Нормированные запасы работоспособности входных параметров.

Теперь проверим работу алгоритма на нескольких процессах. Как видно из табл. 4, при достаточно малом увеличении времени (0,08 сек.) алгоритм ВА (4) нашел решение с несколько большим запасом работоспособности.

Таблица 4

Отметим, что небольшой прирост запаса работоспособности обусловлен размерностью задачи: ведь чем больше количество варьируемых параметров, тем сильнее выражено увеличение эффективности распараллеливания.

Если же в приоритете стоит не увеличение точности, а уменьшение времени расчетов без существенной потери точности, то можно уменьшить количество итераций или сократить популяцию.

Согласно данным, представленным в табл.5, благодаря распараллеливанию алгоритма можно сократить время в 4,8 раза при незначительной потере точности.

Таблица 5 Результаты работы BA(4) с различными значениями популяции и итераций

Более того, сокращение времени даже в 100 раз уменьшило точность всего в 2 раза, что все равно позволяет получить запас работоспособности почти в 2,2 раза больше, чем в расчетах, представленных в работах [12] и [15, 16]. производственный эксплуатационный эвристический

В дополнение к вышеизложенным данным стоит также отметить, что результаты серии тестов для разного количества процессов, итераций и популяций позволяют достаточно точно предположить, что функция имеет выпуклый вид: точность вычислений сохраняется при понижении заданных параметров вплоть до значений, принадлежащих выпуклым функциям [14].

Некоторые возможности повышения эффективности параллельного алгоритма летучих мышей

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

Причем, чем больше стай, тем более вытянутой становится область поиска, что на разных типах функций будет затруднять поиск [17].

Для повышения эффективности будем делить территорию в несколько этапов (рис. 6).

Нулевой процесс запускает стаю №1 на всю территорию с использованием небольшого количества итераций. Решение этой стаи - точка. Далее нулевой процесс выделяет в пространстве поиска окрестность возле найденного решения.

Первый процесс получает координаты этой области и запускает на нее стаю №2 (также используя малое число итераций). В это же время нулевой процесс продолжает поиск в своей области. Когда решение будет найдено на первом процессе, вокруг него также выделяется окрестность. Координаты передаются второму процессу для запуска следующей стаи. Вокруг второго решения нулевого процесса строится окрестность для третьего процесса.

Теперь 4 стаи ищут решение в своей области еще раз.

После завершения расчетов все данные снова соберутся в нулевом процессе.

Предложенный метод (scale-BA) позволяет строить квадратные, а не вытянутые области поиска, что должно благоприятно влиять на поиск.

Рис. 6. Деление территории (scale-BA).

Заключение

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

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

Анализ алгоритма BA(N) показал, что:

использование параллельных вычислений и деления пространства поиска на несколько территорий для разных стай повышает эффективность поиска экстремума целевой функции;

использование ВА^) позволяет достаточно точно предположить вид функции в случае серии тестов с разным количеством итераций и популяций;

эффективность алгоритма зависит от «удачно» выбранных территорий; для повышения эффективности алгоритма целесообразно использовать деление пространства поиска методом scale-BA.

Литература

1. Абрамов О.В. Методы и алгоритмы параметрического синтеза стохастических систем // Проблемы управления. - 2006. - № 4. - С. 3-8.

2. Абрамов О.В. Параллельные алгоритмы расчета и оптимизации надежности по постепенным отказам //Автоматика и телемеханика. - 2010. - № 7. - С. 126-135.

3. Абрамов О.В., Катуева Я.В. Параллельные алгоритмы анализа и оптимизации параметрической надежности // Надежность. - 2005. - №4. - С. 19-26.

4. Абрамов О.В. Проектирование технических систем с элементами настройки // Надежность и качество сложных систем. - 2014. - № 2(6). - С. 51-55.

5. Лагунова А.Д., Назаров Д.А. Параллельный алгоритм решения задачи оптимального параметрического синтеза на основе метода сеток // Труды Международного симпозиума "Надежность и качество". - 2018. - Т.1. - С. 255-258.

6. Карпенко А. П. Популяционные алгоритмы глобальной поисковой оптимизации. Обзор новых и малоизвестных алгоритмов // Приложение к журналу «Информационные технологии». - 2012. - №7. - С.1-32.

7. Yang X.S. A new metaheuristic bat-inspired algorithm. Nature Inspired Cooperative Strategies for Optimization // Springer, SCI 284. - 2010. - P. 65-74.

8. Altringham, J.D. Bats: Biology and Behaviour. Oxford University Press, 1996.

9. Частикова В.А., Новикова Е.Ф. Алгоритм летучих мышей для решения задачи глобальной оптимизации // Научные труды КубГТУ. - 2015. - №2. - URL: https://ntk.kubstu.ru/ file/348.

10. Лагунова А.Д. Алгоритм летучих мышей (BA) для задачи безусловной оптимизации // Оригинальные исследования (ОРИС). - 2019. - №6. - С.101-116.

11. Антушев Г.С. Методы параметрического синтеза технических систем. - М.: Наука, 1989.

12. Анисимов Б.В., Белов Б.И., Норенков И.П. Машинный расчет элементов ЭВМ. - М.: Высшая школа, 1976.

13. Микроэлектроника. Сборник статей под ред. Ф.В. Лукина. Вып. 3. - М.: Советское радио, 1969.

14. Лагунова А.Д. Выбор оптимальных параметров алгоритма BA для задач безусловной оптимизации // Оригинальные исследования (ОРИС). - 2020. - Т. 10, №6. - С. 83 - 95.

15. Назаров Д.А. Разработка алгоритмических и программных средств построения и анализа областей работоспособности аналоговых технических систем: Дис... канд. техн. наук.- Владивосток: ИАПУ ДВО, 2011.

16. Катуева Я.В., Назаров Д.А. Аппроксимация и построение областей работоспособности в задаче параметрического синтеза // Труды Международного симпозиума «Надежность и качество». - Пенза: ПГУ, 2005. - Т.1. - С. 130-134.

17. Лагунова А.Д. Параллельные вычисления как способ повышения эффективности алгоритма летучих мышей (BA) // Сборник статей IX Международной научнопрактической конференции «Инновационное развитие науки и образования», 2020. С.78-87.

Размещено на Allbest.ru