Modifications of the ant colonies method for solving a discrete-valued parametric problem

Full Text

Введение. В настоящее время с развитием вычислительных кластеров и систем возможно перенести множество расчетных и оптимизационных задач с человека-эксперта на вычислительные машины. Программное обеспечение, такое как Ansys и CATIA и др., обеспечивает автоматизацию расчетов, которые ранее выполнялись вручную инженерами. Дальнейшее развитие систем позволяет решать больший спектр задач и проводить параллельные вычисления. Обычно оптимизационную задачу по определению оптимальных параметров системы выполняет инженер, используя итеративный процесс: задание параметров системы, расчеты на вычислительном устройстве, получение значений критериев от программы. Если критерии не удовлетворяют требованиям, то производится эмпирический анализ зависимостей и повторные расчеты. Данный циклический процесс происходит до тех пор, пока значения критериев не удовлетворят инженера.

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

Оптимизация системы с использованием параллельных вычислений может быть автоматизирована при помощи вычислительных кластеров и суперкомпьютеров. Для этого задача оптимизации перекладывается на программное обеспечение, которое перебирает варианты параметров системы методом грубой силы. При этом порядок наборов значений параметров неважен, а оптимизация проводится после рассмотрения всех наборов. Подобные задачи нахождения рациональных значений параметров для решения расчетной задачи называются оптимизацией гиперпараметров [ 1, 2]. Одним из алгоритмов оптимизации гиперпараметров является Байесовский оптимизатор, который позволяет находить закономерности влияния значений отдельных параметров на критерии эффективности. IBM (international business machines) разработала систему BOA (bayesian optimization accelerator), использующую искусственный интеллект на базе Байесовской оптимизации для быстрого нахождения рациональных решений [3–5]. BOA работает как прослойка между вычислительной программой и хранилищем входных параметров. В случае неверной работы BOA результат будет таким же, как и при применении метода грубой силы. Для решения задачи переупорядочивания наборов гиперпараметров перед отправкой на вычислительную систему может быть использован метод муравьиных колоний.

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

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

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

Метод муравьиных колоний ACO (ant colony optimization), предложенный M. Dorigo, решал задачу коммивояжера и позже был расширен на большой класс оптимизационных задач [7, 8]. Элитный, ранжированный и Min-Max алгоритмы описаны давно и применяются во множестве задач [8]. В работе описывается задача параметрической оптимизации: поиск оптимальных значений параметров с последующим продолжением поиска рациональных решений. Задача поиска оптимальных значений параметров методом муравьиных колоний рассматривалась в публикациях многих авторов: комбинаторная оптимизация [9, 10], решения задачи составления расписаний [11], составления заявки на поставки [12], задачи о назначении [13], классификации [14] и других параметрических задач [15, 16]. Отдельно следует отметить оптимизацию гиперпараметров для нейронных сетей [17], управления дискретными детерминированными системами [18, 19], непрерывную [6, 19–23] и многоэкстремальную модификации метода муравьиных колоний [24, 25]. Также широко применяются различные гибридные методы, в составе которых имеется метод муравьиных колоний или роевой вероятностный выбор решения [26].

В статье представлена задача, когда метод муравьиных колоний осуществляет поиск рациональных решений параметрической задачи, но не сходится к ним, а продолжает поиск новых решений. Данный подход основан на работе метода муравьиных колоний совместно с вычислительно сложными аналитическими и имитационными моделями, в которых вычисляются значения функций. Важно, чтобы каждое решение рассматривалось один раз. В результате требуется хранение уже вычисленных решений. Необходима модификация метода муравьиных колоний, позволяющая не сходиться к одному решению, как в оригинальном алгоритме, а продолжить поиск новых решений [15]. Для выборки решений с помощью метода муравьиных колоний пользователь (инженер) задает границы изменения значений и шаг изменения значения параметров системы. Возможно и непосредственное задание качественных значений параметров. На основе информации от пользователя создается структура данных, в которой содержатся параметры и их дискретные значения для каждого параметра системы [15, 16]. Метод муравьиных колоний определяет конкретные значения для каждого параметра (решение), которое отправляется на вычислительный кластер для определения значения критерия. Полученные значения используются методом муравьиных колоний для решения задачи оптимизации. Вычислительный кластер и его целевая функция для исследуемой системы являются черным ящиком (black box). Вычисление может быть ресурсоемко, требовать существенного времени. Поэтому для повышения производительности требуется хранить значения критерия, которые уже были вычислены для заданных значений параметров, в хэш-таблице для минимизации запросов к вычислительному кластеру. Перед отправкой на кластер решение ищется в хэш-таблице, из-за этого не требуется сходимость всех муравьев к одному решению, так как возможен поиск оптимума (путем сравнения значений критерия) в конечном множестве рассмотренных методом муравьиных колоний решений [15]. В статье описывается подход, позволяющий для каждого агента-муравья находить новое, еще не рассмотренное на кластере решение [27].

1. Постановка задачи. Пусть имеется дискретное множество параметров $P=\{p_1,p_2\dots p_i,\dots p_n\}.$ У каждого i-го параметра существует множество допустимых значений V_i = {v_1,i, v_2,i, ... v_j,i, ... v_mi,i,}, i = $\overline{1, n}$. Количество допустимых значений определяется величиной |V_i| = m_i > 0, зависящей от номера параметра. Так для различных параметров может быть найдено различное количество возможных значений. В результате работы алгоритма оптимизации определяется вектор значений параметров, называемый далее решением: $X_k=(x_{\mathrm{1,}k},x_{\mathrm{2,}k}\dots x_{i,k}, \dots x_{n,k}),$ $\left|X_k\right|=n,$$где \forall i\exists j: (x_{i,k}=v_{j,i})\wedge (v_{j,i}\in V_i)$. Здесь k – номер агента (муравья), который получает решение независимо от других агентов. Всего на итерации метода муравьиных колоний решение задают одновременно K агентов. Таким образом возможно параллельное получение каждого решения X_k. Найденный вектор значений параметров отправляется на вычислитель, который возвращает значение критерия, целевой функции f(X_k). Решения рассматриваются в дискретном пространстве значений параметров, и требований непрерывности и дифференцируемости на f(X_k) не накладывается.

Требуется найти множество решений $Y=\{X_1^{*},X_2^{*},\dots X_z^{*}\},$ таких, что $f\left(X_i^{*}\right)\in \psi , \forall i,$ где $\psi$ – область удовлетворительных значений целевой функции. Число решений z не задается ЛПР, достаточно одного решения (z ≥ 1). Их может быть больше одного в случае, если решение ищут несколько агентов k > 1. Агент, нашедший удовлетворительное решение, останавливает поиск, т.е. $1\le z\le K$. Действительно для задачи минимизации достаточно указать только правую границу B для приемлемой области $f\left(X_i^{*}\right)\le B,$ а $\psi =(-\infty ;B].$ Таким образом определяется область приемлемых для ЛПР значений критериев. Данная задача формально относится к классу задач удовлетворения ограничений (constraint satisfaction problems (CSP) [28].

2. Метод решения. В методе муравьиных колоний каждое значение параметра определяется множеством: P, V, $\tau$, $\eta$, где P – множество параметров; V – множество допустимых значений; $\tau$ – вес (количество феромона) для значения параметра; $\eta$ – количество решений, в которых было использовано данное значение параметра. В оригинальном методе муравьиных колоний применялась формула вероятностного перехода (2.1) из вершины i в вершину j, в которой применялась информация о длине дуги $\mu$ и феромоне $\tau$ [7, 8]. В данной задаче вершина графа – это допустимое значение параметра v_j,i, а дуги связывают все значения параметров с соседними номерами i и i + 1 для i = $\overline{1, n – 1}$. Параметры алгоритма $\alpha$, $\beta$ описывают соотношение длины дуги и количества феромона. Так как оригинальный алгоритм должен вычислять путь коммивояжера в графе, то посещенные вершины недоступны для повторного посещения, множество J_i,k – множество доступных вершин для посещения из вершины i для агента k. Ниже P_{i, j, k}(t) определяет вероятность перехода из вершины i в вершину j для агента k на итерации t:

$P_{i,j,k}\left(t\right)=\frac{{\tau }_{i,j}^{\alpha }\left(t\right){\mu }_{i,j}^{\beta }\left(t\right)}{{\displaystyle \sum }_{j\in J_{i,k}}{\tau }_{i,l}^{\alpha }\left(t\right){\mu }_{i,l}^{\beta }\left(t\right)}j\in J_{i,k},$ $P_{i,j,k}\left(t\right)=\mathrm{0,} j\notin J_{i,k}.$ (2.1)

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

$P_{i,j,k}\left(t\right)=\frac{{\tau }_{i,j}^{\alpha }\left(t\right)}{{\displaystyle \sum }_{j\in J_{i,k}}{\tau }_{i,l}^{\alpha }\left(t\right)}j\in J_{i,k},$

$P_{i,j,k}\left(t\right)=\mathrm{0,} j\notin J_{i,k}.$

В таком случае, если в формуле остаются только веса вершин, алгоритм начинает стагнировать, сходиться к первому хорошему решению [6, 29]. Это происходит из-за того, что на начальных итерациях нет никакой информации о графе и все вершины имеют одинаковую вероятность выбора. После нескольких первых итераций вершины рассмотренных решений будут иметь большую вероятность выбора, чем другие вершины.

Предложим новую формулу для расчета вероятности выбора значения j для параметра i:

$P_{i,j,k}\left(t\right)=\frac{z_{i,j}}{{\displaystyle \sum }_{l=1}^{m_i}\left[z_{i,l}\right]},$ $j\notin {\overline{\mathrm{1,}m}}_i ,$ (2.2)

$z_{i,j}={\lambda }_1{\tau }_{norm,i,j}^{\alpha }\left(t\right)+{\lambda }_2{\left(\frac{1}{{\eta }_{i,j}\left(t\right)}\right)}^{\beta }+{\lambda }_3{\left(\frac{{\eta }_{i,j}\left(t\right)}{{\eta }_{\text{max},i}}\right)}^{\gamma }\text{},$ $P_{i,j}\left(t\right)=\mathrm{0,} j\notin {\overline{\mathrm{1,}m}}_i,$

где i – номер параметра p_i ∈ P; j – номер значения параметра v_{j, i} ∈ V_i; t – номер итерации; ${\lambda }_1, {\lambda }_2, {\lambda }_3\in ℝ$ – коэффициенты аддитивной свертки, ${\lambda }_1, {\lambda }_2, {\lambda }_3\in [\mathrm{0,}\infty ),$ $\alpha , \beta , \gamma \in ℝ$ – степени слагаемых аддитивной свертки; ${\tau }_{norm,i,j}\left(t\right)= {\tau }_{i,j}\left(t\right)/\left({\tau }_{i\mathrm{,1}}\right(t)+{\tau }_{i\mathrm{,2}}(t)+\dots +{\tau }_{i,m_i}(t\left)\right)$ – нормированный вес для значения с номером j параметра с номером i для итерации t; h_{i, j}(t) – количество применений в рассмотренных решениях для значения с номером j параметра с номером i для итерации t; $\eta$_{max, i} – максимально возможное количество применений значений для параметра с номером i.

Недостатки линейной свертки, взаимокомпенсация слагаемых, для вероятностной формулы являются достоинством [29]. По результатам взаимокомпенсации на разных итерациях алгоритма разные слагаемые в большей степени влияют на вероятность выбора значения параметра, что позволяет оставаться алгоритму эффективным на любых итерациях. Первое слагаемое ${\tau }_{norm,i,j}^{\alpha }\left(t\right)$ зависит только от нормированного количества весов у параметра с номером i, его значения с номером j. Второе слагаемое ${(1/{\eta }_{i,j}(t\left)\right)}^{\beta }$ зависит от количества посещений значения параметра агентом, т.е. сколько раз значение параметра рассматривалось в решениях. Данное слагаемое позволяет увеличить вероятность выбора значений параметра с наименьшим количество раз посещения. Добавление данного параметра дает возможность избежать стагнации алгоритма. После нескольких итераций алгоритма влияние данного параметра уменьшается из-за возросшего значения $\eta$_{i, j}(t). Третье слагаемое, наоборот, увеличивается, когда количество решений с определенным значением параметра $\eta$_{i, j}(t) приближается к максимальному количеству h_{max, i}. Значение h_{max, i} для дискретной задачи можно точно вычислить по формуле:

${\eta }_{\text{max},i}=\underset{s=1}{\overset{n}{}}{m}_s/m_{i }.$

Данное слагаемое помогает найти последние решения и практически не влияет на работу алгоритма на ранних итерациях.

На каждой итерации метода муравьиных колоний поколение агентов размерностью K находит решения X_k, k ∈ K, которые отправляются на вычислитель для получения значения критерия f (X_k). После получения решений для всех агентов (X_k) из одного поколения определяется новое состояние:

1. Увеличивается номер итерации: $t^{\text{'}}=t+1$.
2. Определяются добавочные веса $∆\tau$_{i, j, k}(t), добавляемые для каждого значения с номером j параметра с номером i агентом k для итерации t (2.3); Q ∈ R – параметр метода муравьиных колоний, определяющий количество весов, добавляемых на единицу значения целевой функции:

$\Delta {\tau }_{i,j,k}\left(t\right)=Q/f\left(X_k\right)для x_{i,k}=v_{j,i}, если f\left(X_k\right)\to \min ,$ (2.3)

$\Delta {\tau }_{i,j,k}\left(t\right)=Qf\left(X_k\right) для x_{i,k}=v_{j,i}, если f\left(X_k\right)\to \max .$

3. Задается количество весов для новой итерации:

${\tau }_{i,j}\left(t^{\text{'}}\right)=\rho {\tau }_{i,j}\left(t\right)+\left(1-\rho \right)\underset{k=1}{\overset{K}{}}\Delta {\tau }_{i,j,k}\left(t\right) ,$ (2.4)

где $\rho$ ∈ [0, 1] – коэффициент испарения – параметр, определяющий скорость “устаревания” информации о предыдущем состоянии.

В (2.4) добавлен коэффициент (1 – $\rho$) для добавленного значения весов. Коэффициент добавлен для аналогичности формуле экспоненциального скользящего среднего. В формуле “прогнозным” значением является предыдущее значение, а “установившимся” – количество добавляемого феромона.

Последующие агенты будут определять решения для итерации t ′. Алгоритм продолжает итеративно находить решения, пока не будет остановлен. Критерием остановки работы алгоритма служит достижение заданного удовлетворительного значения целевой функции f (X_k) ∈ $\psi$.

В оригинальном методе муравьиных колоний в качестве целевой функции используется информация о длине пройденного пути агентом. Данная величина, как и количество феромона, является положительной и в (2.1) вычисление вероятности не приводит к проблемам. Но в задачах с неизвестными значениями целевой функции f (X_k) возможно получение для определенных решений X_k отрицательных значений целевой функции, которая может привести к отрицательным значениям феромона. Для решения проблемы можно применить сдвиг значений целевой функции, но для данного подхода требуется заранее знать $\underset{X_k}{\min }f\left(X_k\right)$. В работе [30] предложен подход, который позволяет осуществлять сдвиг целевой функции итерационно при получении отрицательных значений. Можно пересчитать феромон во всех вершинах, что хоть и требует дополнительной памяти для хранения количества агентов, посетивших вершину на каждой итерации, но позволяет не заботиться о значениях целевой функции:

${\tau }_{i,j}\left(t^{\text{'}}\right)={{\tau }^{\text{'}}}_{i,j}\left(t\right)+\underset{s=1}{\overset{t}{}}\rho {\left(1-\rho \right)}^s{Q}^{s}f{v}^{\text{'}}\left(t\right)k_{i,j,t-s} ,$ (2.5)

где ${{\tau }^{\text{'}}}_{i,j}\left(t\right)$ – значение феромона в вершине для значения с номером j параметра с номером i для итерации t по (2.4); fv′(t + 1) – сдвиг целевой функции на итерации t + 1, $f{v}^{\text{'}}(t+1)=\underset{k}{\max }\left|f\left(X_k\right)+f{v}^{\text{'}}\left(t\right)\right|,$ если $f\left(X_k\right)+f{v}^{\text{'}}\left(t\right)<0; f{v}^{\text{'}}(t+1)=f{v}^{\text{'}}\left(t\right),$ если $f\left(X_k\right)+f{v}^{\text{'}}\left(t\right)\ge 0 ;$ fv′(t ) – величина сдвига целевой функции на предыдущих итерациях, начальное значение fv′(t ) = 0; k_{i, j,t – s} – количество муравьев-агентов в вершине для значения с номером j, параметра с номером i на итерации t – s.

Хранение вычисленных значений целевой функции f (X_k) для набора значений параметров X_k осуществляется в хэш-таблице. Хэш-таблица – это структура данных, которая применяет хэш-функцию для быстрого поиска, вставки и удаления элементов. Хэш-функция принимает значение параметров X_k и преобразует их в уникальное значение фиксированной длины – хэш, в работе используется алгоритм SHA-256. Если значение хэш отсутствует в таблице, то в нее заносятся значения X_k и значение целевой функции f (X_k), иначе возникает коллизия.

Хэш-таблица используется при вычислении значений целевой функции, для разгрузки вычислительного кластера. После нахождения решения X_k оно проверяется на присутствие в хэш-таблице. Если решение найдено, то назовем агента “нулевым” и для него возможно выполнение различных действий: значение критерия f (X_k) определяется из хэш-таблицы (стандартный алгоритм с промежуточным хранением решений); агент не будет добавлять веса для значений параметров $∆\tau$_{i, j, k}(t) = 0; найти новое решение X_k. Среди алгоритмов поиска нового решения рассматривался дальнейший циклический поиск решения, которого нет в хэш-таблице, модифицированным методом муравьиных колоний. По результатам исследований наиболее эффективным является модификация метода муравьиных колоний с циклическим поиском нового решения для нулевого агента (ACO cluster cycle infinity – ACOCCyI) [31]. Отличие такого подхода от обычной работы метода муравьиных колоний в том, что поиск нового решения происходит без изменения состояния. При условии, что все агенты найдут новое решение, можно вычислить необходимое количество итераций алгоритма и определить критерий остановки работы алгоритма – требуемое количество итераций. Если полный поиск всех решений не требуется, то можно остановиться после выполнения определенного процента итераций, например 5–10%. Алгоритм работы модифицированного метода муравьиных колоний приведен на рис. 1.

 

Рис 1. Алгоритм модифицированного метода муравьиных колоний (ACOCCyI).

 

При решении поставленной задачи критерием остановки алгоритма является нахождение решения, удовлетворяющего условию f (X_i^*) ∈ $\psi$. Дополнительным техническим критерием остановки алгоритма выcтупает превышение допустимого времени работы алгоритма. В этом случае нельзя говорить о том, что задача строго решена в поставленной постановке, но тем не менее найденное алгоритмом лучшее решение может быть полезно для ЛПР, если оно близко к области удовлетворительных значений целевой функции.

3. Исследование эффективности метода. Исходными задачами исследования являлись различные параметрические задачи и тесты. Рассматривались функция Розенброка, синусоидальная функция Швефеля, функции Шаффера, Растригина и др. [32–34]. Результаты тестирования будут показаны на функции “Carrom table function”:

$f\left(x\right)=-{\left(\cos x_1\cos x_{2}e\left|{}^{1-\frac{\sqrt{x_1^2+x_2^2}}{\pi }}\right|\right)}^2/30; x_1,x_2\in \left[-\mathrm{10,} 10\right].$ (3.1)

В данном случае рассматривается задача минимизации. Так как представленные тесты – непрерывные функции, то для решения дискретной параметрической задачи необходимо дискретизировать параметры x₁ и x₂. Значения x₁ и x₂ определялись на интервалах [–10,10] с точностью 10^–3. Таким образом, для каждого параметра было определено 20 001 значение от 10 до –10 с шагом 0.001. При решении задачи минимизации целевой функции “Carrom table function” (3.1) имеет четыре оптимальные точки ((x₁; x₂): (9.646; 9.646), (9.646; –9.646), (–9.646; 9.646), (–9.646; –9.646)) с равными значениями целевой функции f (x) = –24.15681551650653 (рис. 2). Рассматривались также аналогичные многоэкстремальные функции с большим количеством оптимальных решений.

 

Рис 2. График функции “Carrom table function” (сверху), “Мультифункции” (посередине) и функции “Шеффеля” (снизу).

 

В данном примере область удовлетворительных значений целевой функции $\psi$ = (–∞; –24.15681]. Другими словами, правая граница интервала – это значение целевой функции, которое немного больше, чем оптимальное значение целевой функции. Таким образом, считается, что мы допускаем нахождение не строгого оптимального решения, а решения, которое может быть немного хуже оптимального. Для работы с отрицательными значениями целевой функции использовался метод динамического сдвига (2.5) [30]. Тестовый пример с заведомо известным оптимумом позволил лучше оценить эффективность предложенного метода.

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

• оценка вероятности найти все попадающее в область $\psi$ значение целевой функции за ограниченное число итераций;атематическое ожидание порядкового номера решения, на котором было определено попадающее в область $\psi$ значение целевой функции;
• математическое ожидание количества дополнительных итераций метода муравьиных колоний;
• математическое ожидание времени поиска агентом одного нового решения.

Результаты исследования модификаций метода муравьиных колоний и оценки других характеристик работы алгоритма имеются в репозитории [35]. https://github.com/kalengul/ACO_Cluster

На рис. 2 приведены графики функций “Carrom table function” (сверху), “Мульти-функции” (посередине) и функции “Шеффеля” (снизу) и оценка (по результатам проведения 3000 прогонов) математического ожидания порядкового номера решения, на котором было рассмотрены данные значения параметров x₁ и x₂. По результатам можно сделать вывод, что предложенные модификации метода муравьиных колоний позволяют осуществить процедуру полного перебора всех комбинаций значений параметров за прогнозируемое число итераций, так как на правых графиках (рис. 2) представлены все точки без пропуска значений. Такой подход гарантирует нахождение оптимального значения даже сложной многоэкстремальной функции без применения процедуры мультистарта. При этом оценка математического ожидания номера итерации повторяет очертания графика функции. В результате перебора значений параметров статистически оптимальные наборы значений параметров определяются на ранних итерациях. После нахождения первого оптимального решения на ранних итерациях алгоритм не прекращает свою работу и позволяет определить все оптимальные решения, например для “Carrom table function” алгоритм рассматривает все четыре решения, попадающие в область $\psi$, менее чем за 500 итераций.

Одной из проблем применения метода муравьиных колоний является большое количество и сложность определения параметров алгоритма [6, 8]. Предложенная вероятностная формула (2.2) добавляет к стандартной формуле еще четыре параметра. Поэтому исследуем поведение алгоритма при различных значениях параметров для выработки рекомендаций.

Изучим эффективность применения всех слагаемых вероятностной формулы (рис. 3) на “Carrom table function” (3.1) (далее – задача малой размерности) с дискретизацией до 10^–1 (201 значение каждого из параметров x₁ и x₂) с 25 агентами на итерации. Так как каждый агент в модификации ACOCCyI находит новое решение, то за 1936 итераций будут рассмотрены все 40 401 решение [31]. Задача большой размерности представлена тестовой задачей, состоящей из 13 параметров и более 10⁷ решений и некоторой авторской одноэкстремальной целевой функцией (подробнее см. [35]). При исследовании зависимости и варьировании параметров метода муравьиных колоний большинство из них оставались неизменными и модифицировался только один параметр метода. Поэтому определим “начальные, стандартные” значения параметров метода муравьиных колоний:

для формулы вычисления вероятности выбора вершины (2.2):

${\lambda }_1=\mathrm{1,} {\lambda }_2=\mathrm{1,} {\lambda }_3=\mathrm{1,} \alpha =\mathrm{1,} \beta =\mathrm{1,} \gamma =1$;

количество агентов на итерации N = 25;

коэффициент испарения $\rho$ = 0.9;

коэффициент Q = 5.

 

Рис 3. Оценки статистических параметров при изменении параметров $\lambda$₁, $\lambda$₂, $\lambda$₃ и ограничения на максимальное количество итераций: а, б – оценка математического ожидания количества дополнительных итераций на одного агента, в – оценка математического ожидания номера решения, на которой были найдены оптимальные значения параметров, г – оценка вероятности найти оптимальное решение.

 

Проведем исследование важности слагаемых в формуле вероятностного выбора значения параметра (2.2) на задаче малой размерности. Первое слагаемое обязательно присутствует в вероятностной формуле, так как это слагаемое является основным для работы метода муравьиных колоний: $\lambda$₃ = 1. Из графиков (рис. 3, светло-серые и темно-серые линии) видно, что без второго слагаемого в формуле (2.2) метод муравьиных колоний стагнирует и плохо находит решения (попадающие в область y значения целевой функции). Оценка вероятности определить решение равна 1 только после рассмотрения 72% решений (1400 итераций из 1936). А третье слагаемое в формуле (2.2) позволяет на последних итерациях быстрее найти последние неэффективные решения, оценка математического ожидания количества дополнительных итераций на одного агента составляет около 11 итераций при $\lambda$₃ = 1 и 13–15 итераций при $\lambda$₃ = 0. Также следует отметить, что резкое возрастание числа дополнительных итераций одного агента происходит только при поиске последней 1000 решений.

Из-за нормировки количества весов для значений параметра $\tau$_{norm,i, j}(t) (2.2) параметр метода муравьиных колоний – Q (2.3) не влияет на эффективность работы алгоритма. Подставив в формулу $\tau$_{norm,i, j}(t ′) значение $\tau$_{i, j}(t ′) из (2.4), получим:

${\tau }_{norm,i,j}\left(t^{\text{'}}\right)=\frac{\rho {\tau }_{i,j}\left(t\right)+{\displaystyle \sum }_{k=1}^K\left(1-\rho \right)\Delta {\tau }_{i,j,k}\left(t\right)}{{\displaystyle \sum }_{l=1}^{m_i}\rho {\tau }_{i,l}\left(t\right)+{\displaystyle \sum }_{k=1}^K\left(1-\rho \right)\Delta {\tau }_{i,j,k}\left(t\right)}.$ (3.2)

Выразив $∆\tau$_{i, j, k}(t) из (2.3) и подставив в (3.2), найдем:

${\tau }_{norm,i,j}\left(t^{\text{'}}\right)=\frac{\rho {\tau }_{i,j}\left(t\right)+{\displaystyle \sum }_{k=1}^K\left(1-\rho \right)\frac{Q}{f\left(X_k\right)}}{{\displaystyle \sum }_{l=1}^{m_i}\rho {\tau }_{i,l}\left(t\right)+{\displaystyle \sum }_{k=1}^K\left(1-\rho \right)\frac{Q}{f\left(X_k\right)}},$

$если f\left(X_k\right)\to \text{min.}$

Параметр Q является постоянным для метода муравьиных колоний, не зависит от номера агента и может быть вынесен из под знака суммы:

${\tau }_{norm,i,j}\left(t^{\text{'}}\right)=\frac{\rho {\tau }_{i,j}\left(t\right)+Q\left(1-\rho \right){\displaystyle \sum }_{k=1}^K\frac{1}{f\left(X_k\right)}}{{\displaystyle \sum }_{l=1}^{m_i}\rho {\tau }_{i,l}\left(t\right)+Q\left(1-\rho \right){\displaystyle \sum }_{k=1}^K\frac{1}{f\left(X_k\right)}}, если f\left(X_k\right)\to \text{min.}$ (3.3)

Подставив в (3.3) вместо $\tau$_{i, j}(t) значение, полученное на предыдущей итерации t ′ из (2.4), получим:

${\tau }_{norm,i,j}\left(t^{\text{'}}\right)=\frac{\rho \left(\rho {\tau }_{i,j}\left(t^{\text{'}}\right)+Q\left(1-\rho \right){\displaystyle \sum }_{k=1}^K\frac{1}{f{\left(X_k\right)}^{\text{'}}}\right)+Q\left(1-\rho \right){\displaystyle \sum }_{k=1}^K\frac{1}{f\left(X_k\right)}}{{\displaystyle \sum }_{l=1}^{m_i}\rho \left(\rho {\tau }_{i,l}\left(t^{\text{'}}\right)+Q\left(1-\rho \right){\displaystyle \sum }_{k=1}^K\frac{1}{f{\left(X_k\right)}^{\text{'}}}\right)+Q\left(1-\rho \right){\displaystyle \sum }_{k=1}^K\frac{1}{f\left(X_k\right)}},$ (3.4)

где f (X_k)′ определяет значение целевой функции для агентов на предыдущей итерации. Единственное значение $\tau$_{i, j}(t), которое не может быть так декомпозировано, – начальное количество весов, которое для всех значений параметров одинаковое. Поделив все значения в формуле (3.4) на Q, запишем:

${\tau }_{norm,i,j}\left(t^{\text{'}}\right)=\left(\rho \left(\frac{\rho {\tau }_{i,j}\left(t^{\text{'}}\right)}{Q}+\left(1-\rho \right)\underset{k=1}{\overset{K}{}}\frac{1}{f{\left(X_k\right)}^{\text{'}}}\right)+\left(1-\rho \right)\underset{k=1}{\overset{K}{}}\frac{1}{f\left(X_k\right)}\right)/Q .$ (3.5)

Формулу (3.5) можно сократить на значение Q (постоянен для любого l ∈ m_i ), оставив только постоянную величину $\rho$ $\tau$_{i, j}(t ′)/Q, при условии, что $\tau$_{i, j}(t ′) – начальный вес у каждого значения каждого параметра.

На рис. 4 показаны результаты исследования влияния различных значений параметра Q в зависимости от ограничения на количество проведенных итераций. Следует отметить статистическую неразличимость оценок, так как все они находятся в пределах доверительного интервала.

 

Рис. 4. Оценки статистических критериев эффективности работы алгоритма при изменении значений параметра Q и ограничения на количества итераций: а – оценка математического ожидания номера решения, на которой были найдены оптимальные значения параметров для графа малой размерности (бенчмарк); б – оценка вероятности найти оптимальное решение для графа большой размерности; в – оценка математического ожидания номера решения, на которой были найдены оптимальные значения параметров для графа большой размерности.

 

Исследования коэффициента испарения $\rho$ (2.4) показали, что для задачи малой размерности только малое значение коэффициента $\rho$ ≤ 0.01 существенно влияет на статистические характеристики. При изучении задачи большой размерности подтвердилось предположение, что большие значения параметра испарения улучшают работу алгоритма. Следует отметить, что при небольшом количестве итераций (первые столбцы нижнего графика рис. 5) значение $\rho$ = 0.95 наиболее эффективно. Рекомендуется выбирать 0.9 ≤ $\rho$ < 1.

 

Рис. 5. Оценки статистических критериев эффективности работы алгоритма при изменении значений параметра r и ограничения на количества итераций: а – оценка вероятности найти оптимальное решение для графа малой размерности (бенчмарк), б – оценка вероятности найти оптимальное решение для графа большой размерности.

 

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

 

Рис. 6. Оценки статистических критериев эффективности работы алгоритма при изменении количества агентов на итерации K и ограничения на количества итераций: а – оценка вероятности найти оптимальное решение для графа большой размерности, б – оценка математического ожидания количества дополнительных итераций на одного агента для графа большой размерности.

 

По результатам исследований выявлено, что при достаточно большом значении количества агентов на итерации K > 35 дальнейшее увеличение статистически не влияет на эффективность работы алгоритма, оценку вероятности найти решение, попадающее в область $\psi$ значения целевой функции (максимизируемый критерий эффективности, верхний график рис. 6) и количества дополнительных итераций (минимизируемый критерий эффективности, нижний график рис.6). При исследовании “Carrom table function” статистически различима эффективность работы алгоритма только при пяти агентах на итерации.

Наиболее сложными для исследования являются коэффициенты и значения параметров степеней в вероятностной формуле (2.2). На рис. 7 приведены результаты исследования взаимовлияния коэффициентов $\lambda$₁, $\lambda$₂, $\lambda$₃ и степеней $\alpha$, $\beta$, $\gamma$. Больше результатов исследований можно найти в работе [35].

 

Рис. 7. Оценки статистических критериев эффективности работы алгоритма при изменении степенней $\alpha , \beta , \gamma$ и коэффициентов $\lambda$₁, $\lambda$₂, $\lambda$₃: а – влияние параметров степени $\alpha , \beta , \gamma$ на оценку вероятности найти оптимальное решение для графа большой размерности, б – влияние коэффициентов $\lambda$₁, $\lambda$₂, $\lambda$₃ на оценку вероятности найти оптимальное решение для графа большой размерности

 

Так как все слагаемые в формуле (2.2) меньше 1, то увеличение степени приводит к уменьшению значения слагаемого, а коэффициент увеличивает значение. Верхний график на рис. 7 показывает влияние коэффициента на оценку вероятности найти решение, попадающее в область $\psi$ значения целевой функции, в задаче большой размерности, для удобства часть линий скрыта. Наиболее эффективными являются значения $\alpha$ = 1, $\beta$ = 1 или $\beta$ = 2, $\gamma$ = 0.5. Таким образом, самый высокий вес будет у третьего слагаемого. Далее по эффективности идут группы, у которых $\alpha$ = 1, $\beta$ = 0.5 и любое значение $\gamma$, потом $\alpha$ = 1, $\beta$ = 1 и другие значения $\gamma$ и $\alpha$ = 1, $\beta$ = 2 или $\beta$ = 10 и $\gamma$ > 1. В случае, когда $\alpha$ ≠ 1 эффективность алгоритма снижается. Рекомендуется не использовать данный параметр, а значение степени принимать равным 1 для $\alpha$, $\beta$, $\gamma$. Такой выбор позволяет получить приемлемые характеристики эффективности работы алгоритма и при этом настройку алгоритма осуществлять с помощью коэффициентов $\lambda$₁, $\lambda$₂, $\lambda$₃.

Из рис. 7 (нижний график) видно, что влияние значений коэффициентов $\lambda$₁, $\lambda$₂, $\lambda$₃ разнообразно и зависит от относительных значений. Наилучшие показатели эффективности (оценка вероятности нахождения оптимального решения) связаны с соотношениями $\lambda$₁ < $\lambda$₂ < $\lambda$₃, причем разница может отличаться на порядок. Такое соотношение позволяет рассмотреть больше различных решений за счет высоких значений у коэффициентов $\lambda$₂ и $\lambda$₃, а далее учитывать распределение феромона.

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

About the authors

E. A. Davydkina

MAI (national research university)

Author for correspondence.
Email: davydkinaelena@yandex.ru
Russian Federation, Moscow

V. A. Nesterov

MAI (national research university)

Email: nesterov46@inbox.ru
Russian Federation, Moscow

V. A. Sudakov

MAI (national research university); Keldysh Institute of Applied Mathematics of RAS

Email: sudakov@ws-dss.com
Russian Federation, Moscow; Moscow

K. I. Sypalo

Central Central Aerohydrodynamic Institute

Email: ksypalo@tsagi.ru
Russian Federation, Zhukovsky

Yu. P. Titov

MAI (national research university)

Email: kalengul@mail.ru
Russian Federation, Moscow

References

Supplementary files