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

КЛАСТЕРНЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ СИНТЕЗА ОПТИМАЛЬНЫХ РЕШЕНИЙ ЗАДАЧИ ИНВЕСТИЦИОННОГО ПЛАНИРОВАНИЯ


Казаков П.В., к.т.н., доцент

Брянский государственный технический университет

e-mail: pvk_mail@list.ru


1. ВВЕДЕНИЕ

Генетический алгоритм (ГА) известен как высокоэффективный адаптивный метод поиска оптимальных решений для математических моделей любой сложности. Однако отсутствие в нем эффективных средств поддержания разнообразия в популяции на протяжении всего процесса поиска приводит к ее преждевременному вырождению. Следствием этого является возможность ГА локализовать за один запуск лишь одно экстремальное решение, что существенно снижает эффективность его использования при решении многоэкстремальных задач. В тоже время, используя врожденное свойство параллелизма, ГА в сочетании с интегрированными в него дополнительными средствами поддержания разнообразия популяции на протяжении всего генетического поиска, позволяет расширить функциональность для решения задач многоэкстремальной оптимизации. Одной из таких реализаций ГА, показавшей высокую эффективность при решении тестовых задач в сочетании с несложной настройкой дополнительных управляющих параметров, является кластерная модификация генетического алгоритма (КГА) [1].

Среди важных задач экономики и бизнеса, которые часто возникают на практике, является оптимизации инвестиционного планирования средств для их размещения в ценных бумагах. Частным случаем, с которым сталкиваются как организации, так и физические лица, занимающие активную позицию в стремлении увеличить свои капиталы, является формирование инвестиционного портфеля (ИП) [2]. Его целью является повышение качества инвестирования в виде надежного сбережения капитала или получения максимального дохода. При этом предполагается наличие у инвестора определенной суммы денег, которую необходимо распределить по различным альтернативным вложениям (акциям, облигациям, иностранной валюте и др.), вместе обладающим такими инвестиционными характеристиками, которые недостижимы с позиций отдельно взятой ценной бумаги.

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

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

^ 2. ОСОБЕННОСТИ ОРГАНИЗАЦИИ И ПРИНЦИПЫ ФУНКЦИОНИРОВАНИЯ КГА

Кластерная модификация ГА частично наследует в себе принципы поддержки разнообразия популяции в процессе генетического поиска, реализованные в некоторых модификациях ГА [4, 5]. А именно разбиение пространства поиска с помощью нишевых механизмов на участки в зависимости от границ значений fitness-функции.

В КГА используется единственная подпопуляция, содержащая кластеры хромосом, формируемых по принципу фенотипического отличия друг от друга.

Под кластером хромосом понимается группа решений, имеющих похожие свойства, то есть кодирующие их хромосомы с похожим фенотипом Для определения меры близости могут быть использованы как вещественная (Евклидова), так и бинарная (Хемминга) метрика d. Число кластеров зависит от задаваемого в качестве дополнительного управляющего параметра ГА радиуса гиперсферы кластера Rc. Хромосомы, располагающиеся в пределах Rc до центроида кластера Zi рассматриваются как похожие и принадлежащие Zi.

Множество центроидов кластеров Zc образуют отдельную подпопуляцию хромосом. Для кластеризации элементов популяции используется принцип доминирования. Пусть Z1, Z2, …, Zk – k фрагментов популяции Pn, представляющих собой кластеры. Хромосома C* Î Ziявляется доминируюшей в кластере, если для . Здесь предполагается, что решается задача минимизации. Знак нестрого неравенства означает, что в кластере может быть более одного доминирующего решения. Поэтому хромосома C* является центроидом кластера Zi тогда и только тогда, если для . Важно, что отдельные хромосомы, соответствующие этому неравенству, могут принадлежать одновременно и другим кластерам, а также доминировать сразу в нескольких кластерах.

Подпопуляция найденных центроидов кластеров представляет собой механизм поддержания разнообразия популяции для параллельного исследования всех областей поискового пространства. С ее обработкой связаны две дополнительные вычислительные процедуры – выделения и копирования кластеров (рис.1).

Р
ис. 1. Структура кластерной модификации генетического алгоритма.


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

Центроиды найденных кластеров сохраняются в отдельной подпопуляции. Основная популяция подвергается применению генетических операторов и следовательно претерпевает изменения, поэтому найденные кластеры теряются. Для предотвращения этого предварительно сохраненные центроиды по специальному алгоритму копируются в новую популяцию, тем самым, восстанавливая «присутствие» ГА в соответствующих участках поискового пространства.

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

Выполнение в КГА указанных вычислительных процедур увеличивает общую временную сложность генетического алгоритма и требует настройки дополнительного управляющего параметра Rc [1].

^ 3. ПОСТАНОВКА И МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ ОПТИМИЗАЦИИ ИП

Наиболее распространенная математическая модель задачи поиска оптимального ИП предполагает наличие финансовых средств в объеме U , которые могут быть использованы для приобретения n видов ценных бумаг в объемах . Известны начальная стоимость одной единицы ценных бумаг вида i, а также ее прогнозируемая стоимость к моменту времени t. Предполагается, что (i = 1,…,n). Необходимо определить такой состав ценных бумаг, чтобы полученная прибыль после их продажи в момент времени t была максимальна. Данная задача является задачей целочисленного программирования с булевыми переменными. Решением описанной задачи оптимизации ИП является бинарный вектор X размером n и содержащий единицу в номерах позиций, совпадающих с номером содержащейся в ИП ценной бумаги. Согласно [6] данная задача оптимизации относится к классу задач о рюкзаке с NP-сложностью. Однако, принимая во внимание тот факт, что рекомендацией к объему ИП является не превышение 15 активов, появляется возможность точного определения f*, используя последний из отмеченных методов для упорядочения по предполагаемому доходу всевозможных комбинаций наличия/отсутствия активов в ИП (всего вариант).

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



,

где   ожидаемая доходность по i-му активу;

  удельный вес стоимости i-го актива;

  нижняя и верхняя граница объемов ценной бумаги вида i.

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

^ 4. ПРИМЕНЕНИЕ АЛГОРИТМА ДЛЯ МНОГОЭКСТРЕМАЛЬНОЙ ЗАДАЧИ ОПТИМИЗАЦИИ

Каждый вариант инвестиционного портфеля кодируется отдельной хромосомой из 15 двоичных генов фиксированной разрядности (рис.2). Декодированное значения гена представляет собой нормализованное в интервале [0, 1] вещественное число, поэтому при определении реального числа акций актива i выполняется масштабирование в соответствующий этому активу интервал [] с последующим округлением до целого.

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

Для определения оптимальности хромосомы была сконструирована fitness-функция, учитывающая специфику решаемой задачи, а именно: получение максимальной итоговой доходности по ИП, желание ЛПР «вложить» в ИП всю сумму или получить некоторый остаток денежных средств после формирования ИП, а также строгий или нет контроль объемов выделенных средств для формирования ИП. Последнее предполагает возможность увеличения начальных размеров капиталовложений для приобретения дополнительного числа акций по перспективному с точки зрения доходности активу. В результате fitness-функция получила следующий вид Fitness-function(FF) = f + R. Здесь первое слагаемое представляет собой исходную целевую функцию математической модели задачи, второе функцию штрафа за нарушении ранее описанных ограничений. Для представления штрафной составляющей может быть использована компенсирующая сумма вида [7].





Рис. 2. Закодированный в виде хромосомы вариант инвестиционного портфеля.


,

где U(Ci) – стоимость инвестиционного портфеля, соответствующего хромосоме Ci.

При U(Ci) = U значение R = 0, если U(Ci) > U, то назначается двойной штраф, так как нарушение этого ограничения является несовместимым с исходной математической моделью задачи. Если же U(Ci) < U, то R присваивается значение штрафа за неполное расходование средств на формирование ИП. Следствием этого может стать невозможность получения самого лучшего ИП, хотя и с сохранением для потребителя ИП некоторых исходных денежных средств.

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



В качестве основы эволюционной модели для данной задачи применялся кластерный ГА с турнирным отбором. С целью получения наилучших результатов при поиске решения в сочетании в высоким быстродействием выполнялась настройка КГА. Для этого проводилась серия экспериментальных запусков с варьированием значений управляющих параметров (табл. 1). Для каждой конфигурации задавалось максимальное число поколений Ng = 300 и размер популяции Np = 200.

Анализ результатов настройки КГА позволяет сделать вывод о локализации различного числа оптимальных решений в зависимости от конфигурации КГА. Большое влияние на эффективность поиска оказало соотношение параметров Np и Rc, важным является определение таких их значений, чтобы сохранялся баланс между разнообразием популяции и направленным характером генетического поиска. Максимальное количество найденных оптимальных ИП составило семь и было получено для следующих значений управляющих параметров Ng = 300, Np = 200, Pc = 0,9, Pm = 0,01,
Rc = 0,3. Полученные результаты далее должны быть предъявлены эксперту, который учитывая вероятности рисков для каждого из найденных ИП, выработает окончательную рекомендацию для потребителя инвестиционного портфеля.

Таблица 1

Rc

Pc, %

Pm, %

,

%

Число оптимальных решений

Число вычислений fitness-функции

0,5

0,9

0,01

18,8

5

60127

0,02

18,65

4

56732

0,03

17,7

7

58243

0,8

0,01

18,3

5

57454

0,02

17,5

3

51235

























0,03

17,1

8

51326

0,7

0,01

18,6

6

60137

0,02

17,6

4

57482

0,03

17,2

5

49200

0,3

0,9

0,01

18,8

7

42231

0,02

17,75

8

41314

0,03

17,4

11

41225

0,8

0,01

18,3

6

42143

0,02

17,25

10

39214

0,03

17,1

13

39365

0,7

0,01

17,8

8

39876

0,02

17,1

9

37622

0,03

16,9

15

37432

0,1

0,9

0,01

18,3

3

24125

0,02

17,4

4

23311

0,03

17,2

4

22822

0,8

0,01

17,9

3

23133

0,02

17,3

4

21314

0,03

17,1

7

20122

0,7

0,01

17,9

3

22353

0,02

17,2

4

21254

0,03

16,7

8

19563



5. ЗАКЛЮЧЕНИЕ

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

Литература

Казаков П.В. Оптимизация многоэкстремальных функций на основе кластерной модификации генетического алгоритма // Одиннадцатая национальная конференция по искусственному интеллекту КИИ-08: Труды конференции. В 3-х т. Т.3. – М.: ЛЕНАНД, 2008. – С. 26-32.

Боди З., Кейн А., Маркус А. Принципы инвестиций. – 4-е изд. –М.: Издательский дом «Вильямс», 2002.

Мищенко А.В. Попов А.А. Некоторые подходы к оптимизации инвестиционного портфеля // Менеджмент в России и за рубежом. – 2002.   №2.

Bäck T, Fogel D., Michalewicz Z. Evolutionary computations 2. Advanced algorithms and operators.   IOP Publishing, 2000.

Chambers L. Practical handbook of genetic algorithms : new frontiers. – CRC Press, Inc., 1995.

Макконнелл Дж. Основы современных алгоритмов: [пер. с англ.]. – М.: Техносфера, 2004.

Michalewicz, Z. Genetic Algorithms + Data Structures = Evolution Programs / Z. Michalewicz.   Springer, 1996.