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

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

ВВЕДЕНИЕ

Сложность современных систем и множество противоречивых целей при их проектировании требуют разработки методов, способных учитывать несколько критериев в процессе принятия решений [1–7]. В работе представлен подход, основанный на аппроксимации границы Парето. Предлагается модификация непрерывной версии метода муравьиных колоний для решения задачи однокритериальной оптимизации [8–10]. Он относится к группе метаэвристических алгоритмов глобальной оптимизации, которые позволяют найти решения хорошего качества за приемлемое время [10]. В разработанном алгоритме предлагается использовать метод недоминируемой сортировки [6,7,11] с учетом возможного незначительного нарушения заданных ограничений типа равенств и неравенств [12–16]. Эффективность алгоритма продемонстрирована на типовых модельных примерах с разной структурой множества Парето. В результате сформированы рекомендации по выбору гиперпараметров алгоритма, что позволило поставить и решить задачу оптимизации инвестиционного портфеля [17–19].

 ПОСТАНОВКА ЗАДАЧИ

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

.           (1)

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

                                                                     ,

где  – заданные непрерывные функции, .

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

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

            Определение 1. Вектор называется векторной оценкой решения .

            Определение 2. Вектор оценок ,  доминирует вектор , , если  и .

Определение 3. Вектор решений  доминирует вектор , если .

            Определение 4. Множество  является множеством решений, оптимальных по Парето, если .

            Определение 5. Множество векторных оценок  называется фронтом Парето.

Требуется найти аппроксимации множества векторных оценок (фронта Парето) и множества решений, оптимальных по Парето.

3. СТРАТЕГИЯ ПОИСКА РЕШЕНИЯ

Для решения задачи предлагается модифицировать метод муравьиных колоний, применяемый в однокритериальных задачах оптимизации [8–10], дополнив его механизмами            недоминируемой сортировки решений [6,7,11] и способом учета выполнения ограничений [12,13]. Базовый метод муравьиных колоний моделирует действия колонии муравьёв при поиске оптимального маршрута в изменяющейся среде обитания. При прохождении по какому-либо участку пути муравей откладывает особое пахучее вещество, называемое феромоном. Чем сильнее концентрация феромонов на тропе, тем более привлекательна она для других муравьёв. Таким образом, муравьи узнают, какие маршруты чаще всего используются колонией.

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

На каждой -й итерации муравей с номером  по данным из архива решений, должен получить новое решение . При этом реализуется вероятностный выбор на основе известной плотности вероятности. Для -й координаты произвольной точки  она имеет вид:

где , ; , , – весовой коэффициент,  – гауссовская плотность вероятности, определяемая математическим ожиданием  и среднеквадратическим отклонением .

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

Рассмотрим недоминируемую сортировку подробнее: пусть  – множество решений на текущей итерации, где . Результатом сортировки является разбиение множества  на  непересекающихся подмножеств , , , – номер последнего подмножества в разбиении:

                          (2)

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

В недоминируемую сортировку включается метод -ограничений. Его основная идея заключается в том, что для всех решений , , вычисляется степень ошибки (Constraint Violation, CV):

                             ,            (3)

где – параметр, задающийся в алгоритме. Решения, у которых , считаются приоритетнее решений, у которых .

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

             Для выбранной муравьем с номером  плотности вероятности  вектор математического ожидания  принимается равным координатам точки с номером :

а среднеквадратическое отклонение вычисляется следующим образом:

где среднее расстояние от точки  до значений соответствующих координат других решений умножается на параметр . Плохие решения забываются, а поиск перемещается к новым точкам множества , отличным от хранящихся в архиве.

Каждой плотности вероятности , , ставится в соответствие весовой коэффициент

где  – параметр алгоритма.

             На практике генерирование новой координаты  происходит в два этапа. На первом выбирается случайным образом плотность вероятности  при помощи метода рулетки с вероятностью выбора

             На втором этапе генерируется значение  в соответствии с выбранной гауссовской плотностью , определяемой параметрами , . Здесь  – номер плотности вероятности, выбранной муравьем с номером .

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

АЛГОРИТМ  РЕШЕНИЯ  ЗАДАЧИ

               Шаг 1. Генерация начальных позиций.

Шаг 1.1.  Задать число муравьев , размер архива , максимальное число поколений , параметры , и . Положить номер поколения .

Шаг 1.2. Сгенерировать  точек  на множестве , используя равномерное распределение.

               Шаг 2. Расчет весов и вероятностей выбора решений. 

      Шаг 2.1. Для каждого решения , , подсчитать вес :

Шаг 2.2. Вычислить вероятность  выбора -й гауссовской плотности вероятности:

               Шаг 3. Выбор плотности вероятности.

                  Шаг 3.1. Положить .

                  Шаг 3.2. Методом рулетки выбрать номер муравья .

               Шаг 4. Генерация вектора .

                  Шаг 4.1. Положить .

Шаг 4.2. Вычислить математическое ожидание  и среднеквадратическое отклонение :

,

,

Шаг 4.3. Генерировать случайную величину  на отрезке  согласно плотности вероятности

Шаг 4.4. Если , сформировать и добавить новое решение к текущему числу поколения , и перейти к шагу 5. Если , положить  и перейти к шагу 4.2.

               Шаг 5. Если , процесс поиска решения поколением муравьев завершить и                   

                  перейти к шагу 6. Если , положить  и перейти к шагу 3.2.

               Шаг 6. Формирование нового поколения.

Шаг 6.1. Для каждого решения ,   из множества  вычислить степень ошибки по формуле (3):

,

где – функции, задающие ограничения типа неравенств,  – функции, задающие ограничения типа равенств.

Шаг 6.2. Разделить множество  на два подмножества:  – решения, у которых , и – решения, у которых .

Шаг 6.3. Реализовать процедуру недоминируемой сортировки согласно (2)  и , где  и  – номера последних подмножеств в разбиениях  и соответственно. Увеличить счетчик числа итераций  .

                  Шаг 6.4. Соединить два подмножества  и  в одно .

                  Шаг 6.5. Найти

Если то  иначе   Если  и  то  все решения попадают в множество

Шаг 6.6. Для каждой точки  подсчитать  – сумму расстояний до остальных точек,  – вероятность выбора решения .

Шаг 6.7. Используя вероятность , случайным образом выбрать из множества  множество точек (решений) в количестве  и добавить их в множество .

Шаг 6.8. Если , то положить  и перейти к шагу 2. Иначе в качестве приближенного решения принять и .

МОДЕЛЬНЫЕ ПРИМЕРЫ

Для тестирования метода были взяты задачи с известным точным решением: ZDT1 (рис. 1), ZDT2 (рис. 2), ZDT3 (рис. 3). Чтобы оценить, насколько полученное решение близко к истинной границе Парето, были использованы метрики IGD (Inverted Generational Distance) и HV (HyperVolume, гиперобъем).

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

,

где  – расстояние от одной точки до другой: .

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

,

где  – мера Лебега,  – опорная точка, .

В процессе тестирования метода для каждого примера при определенных параметрах (табл. 1, 3, 5) были вычислены 10 решений при . В табл. 2, 4, 6 занесены следующие значения:

,               ,

,             ,

,                 ,

где – гиперобъем точной границы Парето.

Пример 1 (ZDT1). Частные целевые функции:

где , при этом  .

Таблица 1. Параметры метода для ZDT1

 Рис. 1. Фронт Парето найденного решения для ZDT1 (тест №5)

Таблица 2. Значения метрик для ZDT1

Пример 2 (ZDT2). Частные целевые функции:

где , при этом  .

Таблица 3. Параметры метода для ZDT2

Рис. 2. Фронт Парето найденного решения для ZDT2 (тест №5)

Таблица 4. Значения метрик для ZDT2

Пример 3 (ZDT3). Частные целевые функции:

где , при этом  .

Таблица 5. Параметры метода для ZDT3

Рис. 3. Фронт Парето найденного решения для ZDT3 (тест №5)

Таблица 6. Значения метрик для ZDT3

ЗАДАЧА  ОПТИМИЗАЦИИ  ИНВЕСТИЦИОННОГО  ПОРТФЕЛЯ

            Будем называть инвестиционным портфелем совокупность купленных инвестором активов. Он задается вектором относительных весов  Каждый инвестор стремится собрать такой портфель ценных бумаг, который обеспечит наибольший доход  при минимальном риске , где – вектор математических ожиданий (вектор средних доходностей),  – ковариационная матрица доходностей.

Тогда многокритериальную задачу оптимизации инвестиционного портфеля можно записать следующим образом:

где .

В качестве примера рассматривается портфель ценных бумаг, состоящий из акций десяти ведущих российских компаний: ВТБ (VTBR), Газпром (GAZP), Лукойл (LKOH), Аэрофлот (AFLT), Сургутнефтегаз (SNGS), Мечел (MTLR), Алроса (ALRS), Яндекс (YNDX), Ютэйр (UTAR), Магнит (MGNT). Информация о средних доходностях (табл. 7) и ковариациях (табл. 8) акций представлена на момент закрытия за период с апреля 2023 года по апрель 2024 года.

                                                                                    Таблица 7

Средние доходности активов

Таблица 8. Ковариации активов

Результаты решения задачи представлены в табл. 10 и на рис. 4. Параметры, при которых было вычислено решение, приведены в табл. 9.

Таблица 9. Параметры метода

 Таблица 10. Веса ценных бумаг, значения дохода и риска

Рис. 4. График зависимости дохода и риска

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

Заключение

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