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

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

Рубрика Экономико-математическое моделирование
Вид статья
Язык русский
Дата добавления 18.01.2018
Размер файла 90,7 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

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

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

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

Введение

генетический алгоритм решение экспертный

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

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

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

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

1. Особенности организации и принципы функционирования КГА

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

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

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

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

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

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

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

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

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

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

2. Постановка и математическая модель задачи оптимизации ИП

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

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

,

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

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

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

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

3. Применение алгоритма для многоэкстремальной задачи оптимизации

Каждый вариант инвестиционного портфеля кодируется отдельной хромосомой из 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

Заключение

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

Литература

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

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

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

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

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

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

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

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

...

Подобные документы

  • Классическая теория оптимизации. Функция скаляризации Чебышева. Критерий Парето-оптимальность. Марковские процессы принятия решений. Метод изменения ограничений. Алгоритм нахождения кратчайшего пути. Процесс построения минимального остовного дерева сети.

    контрольная работа [182,8 K], добавлен 18.01.2015

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

    контрольная работа [57,1 K], добавлен 04.10.2010

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

    учебное пособие [2,0 M], добавлен 15.06.2015

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

    контрольная работа [1,2 M], добавлен 11.06.2011

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

    курсовая работа [5,2 M], добавлен 22.06.2019

  • Понятия и определения теории генетических алгоритмов. Математический базис изобретательской физики. Генетический алгоритм изобретательской задачи. Описание операторов генетических алгоритмов. Система мысленного поиска и слежения в сознании изобретателя.

    курсовая работа [723,2 K], добавлен 22.05.2012

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

    контрольная работа [99,9 K], добавлен 21.03.2014

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

    курсовая работа [505,9 K], добавлен 27.06.2017

  • Принятие решений в условиях неопределенности. Критерий Лапласа и принцип недостаточного основания. Критерий крайнего пессимизма. Требования критерия Гурвица. Нахождение минимального риска по Сэвиджу. Выбор оптимальной стратегии при принятии решения.

    контрольная работа [34,3 K], добавлен 01.02.2012

  • Содержание и построение экономико-математических методов. Роль оптимальных методов в планировании и управлении производством. Экономико-математические модели оптимальной загрузки производственных мощностей. Отраслевое прогнозирование и регулирование.

    контрольная работа [62,1 K], добавлен 30.08.2010

  • Теоретические основы экономико-математических методов. Этапы принятия решений. Классификация задач оптимизации. Задачи линейного, нелинейного, выпуклого, квадратичного, целочисленного, параметрического, динамического и стохастического программирования.

    курсовая работа [2,3 M], добавлен 07.05.2013

  • Количественное обоснование управленческих решений по улучшению состояния экономических процессов методом математических моделей. Анализ оптимального решения задачи линейного программирования на чувствительность. Понятие многопараметрической оптимизации.

    курсовая работа [4,2 M], добавлен 20.04.2015

  • Моделирование экономических процессов методами планирования и управления. Построение сетевой модели. Оптимизация сетевого графика при помощи табличного редактора Microsoft Excel и среды программирования Visual Basic. Методы принятия оптимальных решений.

    курсовая работа [217,2 K], добавлен 22.11.2013

  • Сущность общей методики формирования критериев. Расчет показателя эффективности стратегии, средневзвешенного выигрыша, цены игры, оптимальности стратегии по критериям Байеса, Лапласа, Вальда, Ходжа-Лемана, Гермейера, максимаксному, критерию произведений.

    реферат [67,3 K], добавлен 23.05.2010

  • Построение модели управления запасами в условиях детерминированного спроса. Методы и приемы определения оптимальных партий поставки для однопродуктовых и многопродуктовых моделей. Определение оптимальных параметров системы управления движением запасов.

    реферат [64,5 K], добавлен 11.02.2011

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

    контрольная работа [591,3 K], добавлен 27.10.2013

  • Характеристика ипотечного кредитования на примере Брянской области. Обзор математических методов принятия решений: экспертных оценок, последовательных и парных сравнений, анализа иерархий. Разработка программы поиска оптимального ипотечного кредита.

    курсовая работа [1,7 M], добавлен 29.11.2012

  • Задачи оптимизации сложных систем и подходы к их решению. Программная реализация анализа сравнительной эффективности метода изменяющихся вероятностей и генетического алгоритма с бинарным представлением решений. Метод решения задачи символьной регрессии.

    диссертация [7,0 M], добавлен 02.06.2011

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

    реферат [392,7 K], добавлен 20.03.2016

  • Статистические модели принятия решений. Описание моделей с известным распределением вероятностей состояния среды. Рассмотрение простейшей схемы динамического процесса принятия решений. Проведение расчета вероятности произведенной модификации предприятия.

    контрольная работа [383,0 K], добавлен 07.11.2011

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.