Возможности генетических алгоритмов для решения задачи многокритериальной оптимизации инвестиционного портфеля
Автор: Казаков П.В.
Источник: Казаков П.В. Возможности генетических алгоритмов для решения задачи многокритериальной оптимизации инвестиционного портфеля / П.В. Казаков // Конференция по искусственному интеллекту: материалы 12-ой национальная конференция по искусственному интеллекту КИИ-2010. – Тверь: РАИИ – 2010. – Режим доступа: http://www.raai.org/resurs/papers/kii-2010/seminar/seminar1/Kazakov.pdf.
Аннотация
Рассматривается возможность решения задачи многокритериальной оптимизации (МО) инвестиционного портфеля с помощью многокритериальных генетических алгоритмов (МГА) «первого поколения». Представлены экспериментальные результаты применения МГА для поиска множества вариантов оптимальных инвестиционных портфелей с различными соотношениями доходность/риск.
Введение
Оптимизация инвестиционного портфеля (ИП) [3, 4, 5] является одной из важных экономических задач, направленной на повышение качества инвестирования финансовых средств в виде надежного сбережения капитала или получения максимального дохода при допустимом риске. Известно, что особенностью ИП является наличие у него инвестиционных свойств, недостижимых с позиций отдельно взятой ценной бумаги, а именно возможность формирования разных ИП с собственным балансом между предполагаемым риском и ожидаемой доходностью в определенный период времени. Одной из главных рекомендаций при формировании ИП является наличие в нем различных слабокоррелирующих активов [4, 5]. Такой инвестиционный портфель называется диверсифицированным. Установлено, что максимальное снижение риска достигается, если в портфель отобраны от 10 до 15 различных ценных бумаг [4, 5].
В настоящее время существуют различные модели оптимизации ИП, ориентированные как на статически, фиксировано заданные значения инвестиционных параметров, так и на динамически изменяющиесяусловия инвестиционного планирования, в том числе и в нечеткой среде [2, 9]. Однако независимо от типа моделей портфельной оптимизации в ее основе лежит модель, предложенная Г. Марковицем [3, 5]. В общем случае эта модель предполагает наличие множества Парето-оптимальных решений при оценке соотношения «доходность-риск», расположенных на так называемой границе ффективности инвестиционных портфелей. Однако эта модель характеризуется высокой вычислительной трудоемкостью, в плане применения численных методов оптимизации. Из-за наличия комбинаторных свойств задача оптимизации ИП на основе модели Г. Марковица относится к NP-сложным - варьируя доли финансовых активов в ИП, можно сформировать их бесконечное множество с собственным балансом между ожидаемой доходностью и риском. Анализ традиционных численных методов многокритериальной комбинаторной оптимизации в многомерных поисковых пространствах и, в частности применительно к решению задачи оптимизации ИП в постановке Г. Марковица, показал их ограниченность, как по точности, так и по времени поиска. Поэтому перспективным здесь является применение специального класса генетических алгоритмов для решения задач многокритериальной оптимизации. Их использование позволяет с высокой точностью и за приемлемое время определять не одно, а множество оптимальных решений задачи оптимизации ИП по соотношению доходность/риск.
Постановка задачи и генетические алгоритмы для многокритериальной оптимизации ИП
Рассматриваемая задача оптимизации ИП основывается на двухкритериальной модели Г. Марковица с незначительной корректировкой (вместо поиска долей каждого из видов финансовых активов в ИП определяется их количество), учитывающей доступные фактические данные [6] по финансовым активам, предлагаемым на рынке ценных бумаг. Основными параметрами модели являются:
U – объем финансовых средств для формирования инвестиционного портфеля;
αi – начальная стоимость одной единицы ценных бумаг вида i (i= 1..n, далее n = 15);
xi – объем приобретаемых финансовых активов вида i;
xi∈[xi–,xi+] – нижняя и верхняя граница объемов ценной бумаги вида i;
γi – ожидаемая средняя доходность по i-му активу;
f1=γ → max – оптимизируемый критерий «доходность инвестиционного портфеля»
f2=σR → min – оптимизируемый критерий «риск инвестиционного портфеля».
Для оценки найденных ИП используются соответствующие принципы Парето-доминирования и Парето-оптимальности.
В отличие от ряда других в данной модели оптимизации ИП не требуется изначального задания ЛПР желаемых значений доходности и допустимого риска, сильно зависящих от стохастически изменяющихся инвестиционных возможностей. Основное участие ЛПР предполагается непосредственно на стадии выбора решений из множества найденных альтернатив, что, в целом, снижает психологическую нагрузку ответственности на эксперта. Таким образом, результат решения рассматриваемой задачи зависит от числа и точности найденных Парето-оптимальных решений. В качестве численных методов для получения таких решений применялись различные модели многокритериальных генетических алгоритмов.
В настоящее время МГА условно разделены на два поколения, причем второе поколение является развитием соответствующих алгоритмов первого за счет использования средств реализации в МГА стратегии элитизма, вторичной популяции (Парето-архива) и специальных методов ее обработки. В данной статье рассматриваются МГА первого поколения [7], включающие Nondominated Sorting Genetic Algorithm (NSGA), Niched-Pareto Genetic Algorithm (NPGA), Multi-Objective Genetic Algorithm (MOGA) и относящиеся к группе МГА «рекомендованных к применению» [8]. В сравнении с другими генетическими алгоритмами с возможностями решения задач МО (Vector Evaluated Genetic Algorithm [8], Weighting-based Genetic Algorithm [8]) эти алгоритмы позволяют решать задачи многокритериальной оптимизации в естественной многокритериальной постановке, используют необходимые технологии поддержания разнообразия популяции (niching, fitness sharing), имеют приемлемую вычислительную сложность. Анализ результатов применения МГА первого поколения для решения различных тестовых задач многокритериальной оптимизации показал их высокую эффективность и быстродействие, что является достаточным обоснованием их применения для решения задачи многокритериальной оптимизации инвестиционного портфеля.
Тестовые данные для задачи оптимизации ИП
В качестве тестового примера использовались следующие входные данные [Социальная сеть инвесторов, 2009] математической модели оптимизации ИП (табл. 1).
Таблица 1 – Выходные данные
| № | Название актива | Начальная стоимость(руб.) | Ожидаемая доходность | Минимальное число ЦБ в портфеле | Максимальное число ЦБ в портфеле |
|---|---|---|---|---|---|
| 1 | Газпром | 104 | 7 | 100 | 1000 |
| 2 | Роснефть | 108 | 8 | 200 | 600 |
| 3 | Аэрофлот | 24 | 3 | 100 | 500 |
| 4 | Объединенные машиностроительные заводы | 150 | 12 | 100 | 500 |
| 5 | Заволжский моторный завод | 62 | 15 | 100 | 500 |
| 6 | Новолипецкий металлургический комбинат | 30 | 5 | 200 | 700 |
| 7 | Приволжское морское пароходство | 5 | 15 | 100 | 500 |
| 8 | Брянская сбытовая компания | 12 | 10 | 300 | 700 |
| 9 | Калужская сбытовая компания | 13 | 10 | 200 | 600 |
| 10 | Мобильные Теле-Системы | 114 | 5 | 200 | 500 |
| 11 | РБК информационные системы | 13 | 12 | 300 | 800 |
| 12 | ДИКСИ | 56 | 11 | 100 | 500 |
| 13 | Сбербанк | 18 | 5 | 100 | 600 |
| 14 | М.Видео | 26 | 6 | 100 | 200 |
| 15 | Иностранная валюта | 39 | 7 | 500 | 2000 |
Предварительно, на основе анализа динамики за определенный период индексов и котировок ценных бумаг, выбирались активы-кандидаты в инвестиционный портфель. В данном случае проверялось выполнение условия наличия положительной доходности активов в течение одного месяца, а также учитывался коэффициент корреляции доходности активов. Для оценки риска брались результаты торгов ценными бумагами в течение трех месяцев.
Каждый вариант инвестиционного портфеля кодировался отдельной хромосомой из 15-ти двоичных генов фиксированной разрядности. Декодированное значение гена представляет собой нормализованное в интервале [0, 1] вещественное число. Поэтому при определении реального числа ценных бумаг актива i выполнялось масштабирование в соответствующий этому активу интервал [xi–,xi+] с последующим округлением до целого. Для контроля за расходованием средств, выделенных на формирование ИП (желание ЛПР «вложить» в ИП всю сумму или получить некоторый остаток денежных средств после формирования ИП, возможность превышения объема выделенных средств для формирования более лучшего ИП) к каждому критерию добавлялась специальная штрафная функция [1].
Результаты применения МГА для оптимизации ИП
Все генетические алгоритмы участвовали в двух группах тестов. В каждой группе исследовались различные наборы значений управляющих параметров МГА: вероятность кроссинговера (Pc), вероятность мутации (Pm), радиус ниши ( σshare ) (табл. 2). Значения размера популяции (Np =100) и числа поколений (Ng = 300) не изменялись, U = 700 000 руб. Важно, что в отличие от первой группы тестов во второй - использовался Парето-архив. Он позволяет накапливать и упорядочивать недоминируемые решения за все поколения работы МГА. В итоге достигается более мощное итоговое множество и высокая протяженность границы Парето. Не использование Парето-архива в МГА удобно при их настройке, так как позволяет легче контролировать количество и качество найденных решений для разных конфигураций алгоритмов.
Результаты работы МГА могут быть оценены по трем основным показателям: точности найденных решений (их близость к глобально оптимальным), количеству найденных решений и степени равномерности их распределения по границе Парето. Для решаемой задачи глобально оптимальные решения неизвестны, поэтому качество работы МГА определялось как визуально, так и с помощью специальной метрики для количественной оценки равномерности заполнения точками границы Парето. Значения этой метрики вычисляются по следующей формуле [7]:
где di – Евклидово расстояние между i-ой точкой и ближайшей к ней на границе Парето;
d – среднее значение расстояний;
NP – число точек на границе Парето.
На рис.1 показаны границы Парето, соответствующие лучшим конфигурациям МГА в каждой группе тестов.
Рисунок 1 – Результаты многокритериальной оптимизации ИП различными МГА
В табл. 2 приведены результаты тестов МГА (с использованием Парето-архива), а также соответствующие значения управляющих параметров.
Таблица 2 – Результаты тестов МГА
| Параметр МГА и оценочные показатели его работы | MOGA | NPGA | NSGA |
|---|---|---|---|
| Pc | 0,9 | 0,9 | 0,9 |
| Pm | 0,001 | 0,003 | 0,003 |
| σshare | 0,23 | 0,32 | 0,14 |
| NP | 51 | 45 | 39 |
| Δ | 0,762 | 0,683 | 0,467 |
Анализ полученных тремя МГА (при использовании Парето-архива) границ Парето позволяет сделать вывод о достаточной похожести по точности найденных решений. Больше всего различных точек Парето было определено с помощью MOGA (51), на втором мести NPGA (45) и на третьем NSGA (39). Однако у NSGA по сравнению с двумя другими МГА оказалась наиболее равномерно заполненная граница Парето (D = min). Поэтому, несмотря на меньшее число найденных решений результаты, полученные NSGA являются более предпочтительными для последующих обработки и выбора ЛПР окончательного решения. Точки, найденные MOGA и NPGA, располагаются достаточно плотно друг к другу, но с относительно большой фрагментацией вдоль границы Парето. В итоге для ЛПР может быть потерян целый ряд решений с достаточно отличающимся соотношением доходность/риск.
Время поиска всеми МГА было существенно ниже времени, потраченного на их настройку, что позволяет применять рассматриваемые алгоритмы в реальных экономических условиях с динамически изменяющимися входными данными.
Заключение
С помощью специальных генетических алгоритмов (NSGA, NPGA, MOGA) была решена задача многокритериальной оптимизации инвестиционного портфеля. Каждый из трех рассмотренных МГА сумел найти множество Парето для этой задачи, но разной мощности и разбросом границы Парето. Полученные результаты могут быть улучшены посредством применения МГА «второго поколения» (SPEA, SPEA2, NSGA2 [7]), что является перспективой дальнейших исследований.
Список литературы
1. Аверченков В.И., Казаков П.В. Эволюционное
моделирование и его применение: монография. - Брянск: БГТУ, 2009.
2. Батыршин И.З., Недосекин А.О., Стецко А.А., Тарасов
В.Б., Язенин А.В., Ярушкина Н.Г. Нечеткие гибридные системы. Теория и
практика / Под. ред. Н. Г. Ярушкиной. – М.:ФИЗМАТЛИТ, 2007.
3. Дубровин В.И., Юськив О.И. Модели и методы
оптимизации выбора инвестиционного портфеля // Радiоелекторонiка.
Iнформатика. Управлiния. 2008. №1.
4. Мищенко А.В., Попов А.А. Некоторые подходы к
оптимизации инвестиционного портфеля // Менеджмент в России и за
рубежом. 2002. №2.
5. Серов В.М. Инвестиционный менеджмент. – М.: ИНФРА-М, 2000.
6. Социальная сеть инвесторов. – http://tikr.ru.
7. Deb K. Multi-objective optimization using evolutionary algorithms. –
Wiley, 2009.
8. Van Veldhuizen D. and Lamount G. Multiobjective
evolutionary algorithms: analyzing the state-of-the art. // Evolutionary computation.
2000. № 8(2).
9. Yazenin A.V. Optimization with Fuzzy Random Data and its
Application in Financial Analysis // In Proceedings of the International Conference
on Fuzzy Sets and Soft Computing in Economics and Finance, 2004.