close

Вход

Забыли?

вход по аккаунту

?

Модели и алгоритмы для поддержки принятия решений инвестиционного аналитика.

код для вставкиСкачать
УДК 519.866:330.322
Е.С. Семенкин, А.В. Медведев, А.Ю. Ворожейкин
МОДЕЛИ И АЛГОРИТМЫ ДЛЯ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ
ИНВЕСТИЦИОННОГО АНАЛИТИКА
Целью работы является повышение обоснованности принятия решений при управлении инвестициями. Рассматриваются задачи реального и портфельного инвестирования. Приводятся математические модели оценки венчурных проектов, формирования портфеля реальных инвестиций промышленного предприятия и формирования кредитного портфеля. Для решения возникающих оптимизационных задач предлагается использовать вероятностный генетический алгоритм. Приводится анализ эффективности алгоритма и результаты решения практических задач.
Современное многономенклатурное производство в условиях конкуренции характеризуется действием множества
факторов, влияющих на результат деятельности предприятия
и возможностью выбора из множества допустимых вариантов
инвестиционных стратегий. Поэтому часто бывает трудно
оценить обоснованность и последствия того или иного инвестиционного решения, основываясь лишь на личном опыте и
интуиции. В этой связи существенное значение имеют формализованные подходы к управлению инвестиционными
программами. Вопросы теории управления реальными инвестициями в современных условиях на настоящий момент не
получили окончательного решения. Это, в свою очередь,
влечет недостаточность современных инструментов поддержки принятия решений в данной области.
Современные исследователи теории и практики анализа
реальных инвестиций идут по пути совершенствования формальных моделей и инструментальных средств, разрабатывая
все более и более приближенные к реальности подходы. Однако на этом пути появляется проблема противоречия между
совершенствованием моделей и наличием средств для их
исследования. Попытка приблизить модели к реальности
приводит к их усложнению с точки зрения формальной математики – появляются нелинейные зависимости, вычислительно сложные выражения, возникают сложные оптимизационные задачи, не решаемые средствами классической теории оптимизации, с которой обычно знакомы экономисты. В
то же время привлечение более мощных средств затруднено
недостаточным знакомством специалистов с соответствующими разделами математики и интеллектуальными информационными технологиями. На разрешение данной проблемы и
ориентирована данная работа. Отличительной чертой предлагаемого подхода является его значительный потенциал для
дальнейшего развития – примененные методы эволюционной
оптимизации в состоянии решить задачи любой сложности,
как бы в дальнейшем не усложнялся формальный аппарат
анализа реальных инвестиций. Появление нелинейных, динамических, многокритериальных, стохастических постановок,
которое будет сопровождать дальнейшее совершенствование
теории анализа реальных инвестиций, не отменяет полученных результатов. Более того, эволюционные алгоритмы могут даже самонастраиваться на решаемую задачу, что позволяет практически автоматизировать решение сложных оптимизационных задач. Первые результаты разработки данного
подхода представлены в статье.
ПОСТАНОВКИ ЗАДАЧ
Задача венчурных инвестиций
Имеется план производства нескольких видов продукции на одном основном производственном фонде
(ОПФ) с известными прогнозными значениями спроса
по каждому виду. Кроме того, известны технико-
экономические показатели ОПФ и здания цеха (ЗЦ):
нормативный срок службы и стоимость, производительность оборудования и стоимость единицы производимой на нем продукции. Требуется определить объемы внешних инвестиций, осуществляемые инвестором в заданный период времени, платежей поставщику
за ОПФ и ЗЦ, а также объемы продаж по каждому виду
продукции в период производства, при которых стоимость ИП за определенный интервал времени будет
наибольшей. При этом сумма всех инвестиций не
должна превышать некоторой заданной величины, а
сумма всех платежей должна быть не меньше стоимости оборудования и ЗЦ.
Динамическая модель венчурного инвестирования
выглядит следующим образом [1].
Уравнения движения
x(t + 1) = A(t ) ⋅ x(t ) + B(t ) ⋅ u (t ) − s(t ),
x(0) = a.
Ограничения
C (t ) ⋅ x(t ) + D(t ) ⋅ u (t ) ≤ h(t ),
u (t ) ≥ 0; (t = 0, …, T − 1).
Целевая функция
T −1
J = ∑ [(a (t ), x(t ) ) + (b(t ), u (t ) )] + (a(T ), x(T ) ) → max .
t =0
Здесь
u (t ) = ( u1 (t ), u2 (t ) )
τ
–
управляющий
вектор,
u1 (t), u2 (t) – инвестиции и платежи за ОПФ и ЗЦ в момент
t+1, (t=0,…, T1–1). T1 – момент завершения инвестирования и начала производства; u(t ) = ( u1 (t ), …, um (t ) ) –
τ
объемы продаж по каждому из m видов производимой
продукции (t=T1, …, T–1), T – момент завершения инвестиционного проекта; x(t ) = ( x1 (t ), x2 (t ) ) – фазовый векτ
тор, x1 (t ), x2 (t ) – накопленные до момента t суммы инвестиций и выплат соответственно. Символом τ обозначено транспонирование.
Заметим, что качественной особенностью данной
модели является переменность размерности вектора
управления и содержательного смысла его компонент;
A(t), B(t), C(t), D(t) – вещественные матрицы, s(t), h(t) –
вещественные векторы, размерности которых также
могут меняться во времени.
63
Таким образом, для предварительного оценивания
проекта реальных инвестиций необходимо решать многошаговую задачу линейного программирования
(МЗЛП) (а в общем случае – нелинейного, так как зависимости не будут такими простыми) с переменной длиной вектора управлений. Если для МЗЛП дискретный
принцип максимума (ДПМ) является достаточным условием и поэтому можно использовать метод последовательных приближений (хотя бы для задач небольшой
размерности), то в нелинейном случае ДПМ не является даже необходимым условием оптимальности, а это
значит, что методы решения таких задач на настоящий
момент не разработаны.
Тогда для повышения обоснованности принятия
решений при формировании оптимального портфеля
инвестиционных проектов, необходимо решить следующую задачу условной оптимизации:
i =1 j =1
После того как для каждого инвестиционного проекта рассчитаны ожидаемые прибыли, среди них выбирают эффективные проекты и приступают к формированию оптимального инвестиционного портфеля.
Рассмотрим задачу формирования оптимального
инвестиционного портфеля производственного предприятия, проводящего реструктуризацию, т.е. выделяющего в своем составе так называемые центры финансовой ответственности (ЦФО), которым дано право
самостоятельного планирования инвестиций из собственных средств (при поддержке материнского предприятия) [2]. Задача состоит в формировании оптимального портфеля инвестиционных проектов при наличии ограничений по выделяемым средствам, норме
прибыли и общей рискованности портфеля.
Для формализованной записи критерия получения
максимальной доходности от инвестиционных проектов,
при соблюдении всех ограничений, введем следующие
обозначения [3]: m – количество ЦФО на предприятии;
N i – количество инвестиционных проектов на i-м ЦФО,
m
1
m
Ni
∑∑ x
i =1 j =1
m
Ni
ij ij
≤C+M ,
m
Ni
∑∑ c x
i =1 j =1
i =1 j =1
ij
1
m
Ni
⋅ ∑∑ Rij xij ≤ ρ ,
∑∑ c x
i =1 j =1
Задача формирования оптимального портфеля
реальных инвестиций производственного
предприятия
Ni
m
f ( X ) = ∑∑ Π ij xij → max, xij ∈ {0,1} ,
Ni
⋅ ∑∑ Π ij xij ≤ r .
i =1 j =1
ij ij
Это задача условной оптимизации с бинарными переменными, которая и в приведенной постановке является достаточно сложной для решения известными методами, особенно при больших размерностях. В более
реальной постановке оценки ожидаемых прибылей и
рисков являются функциями от размеров выделенных
средств. Более того, для задачи реальных инвестиций
производственного предприятия необходимо учитывать ограничения не только на финансовые, но и на
другие ресурсы (энергия, тепло, кадры и т.п.) [3]. В
этом случае будет получена задача с алгоритмически
(а не аналитически) заданными функциями, решение
которой классическими методами целочисленной оптимизации невозможно.
Задача формирования оптимального
кредитного портфеля банка
мый параметр, показывающий, планируется ли к внедрению на i-м ЦФО j-e нововведение (если xij = 1 , то
Во многих случаях для реализации инвестиционной
программы необходимо получить заемные финансовые
средства, что заставляет инвестиционного аналитика
планировать кредитную стратегию предприятия, для
чего необходимо делать предварительные расчеты кредитного портфеля с точки зрения коммерческого банка
для прогнозирования финансовых потоков. Поэтому
рассмотрим задачу формирования оптимального кредитного портфеля банка [4]. Она состоит в формировании оптимального кредитного портфеля при наличии
жестких ограничений по суммам имеющихся в наличии свободных кредитных ресурсов, их стоимости,
процентным ставкам на выдаваемые кредиты, срокам
привлечения ресурсов, максимальному размеру кредита на одного заемщика.
Для формализованной записи критерия получения
максимальной доходности от проводимых банком кредитных операций при соблюдении требования минимизации риска невозврата вводятся следующие обозначения: N – количество заемщиков; F – сумма свободных
пассивов, которыми располагает банк в данный момент
времени; k ij – сумма кредита, запрашиваемая j-м заем-
планируется; если xij = 0 , то не планируется).
щиком, j = 1, N ; t j – срок, на который j-й заемщик бе-
i = 1, m ; Π ij – плановый годовой объем прибыли, получаемый i-м ЦФО от внедрения j-го нововведения,
j = 1, N i ; Rij – экспертная оценка рискованности соот-
ветствующего инновационного проекта; cij – плановые
годовые затраты финансовых средств i-го ЦФО на j-е
нововведение, способствующее увеличению мощности
ЦФО; Ci – плановые годовые объемы финансовых
средств, выделяемые ЦФО в план нововведений;
m
C = ∑ Ci – сумма средств, выделяемых всеми ЦФО на
i =1
реализацию их инвестиционных программ; M – плановый годовой объем финансовых средств, выделяемый
центральной компанией в планы нововведений ЦФО; r –
допустимая средняя прибыль на 1 руб. затрат (норма
прибыли на капитал); ρ – ограничение на суммарную
рискованность инвестиционного портфеля; xij – иско-
64
рет кредит; x j – булева переменная, принимающая значения: 1, если кредит k j выдается, и 0, если заявка на
получение кредита отклоняется банком; d j – проценты
за пользование k j -м кредитом (предполагается, что d j
выплачиваются единовременно с возвратом самого кредита); Pj – вероятность невыполнения заемщиком обязательств по возврату кредита и процентов по нему
k j ⋅ 1 + d j . В предлагаемой постановке задачи предпо-
(
)
лагается два варианта обслуживания долга заемщиком:
100%-й возврат суммы кредита и процентов по нему в
установленный срок либо полное отсутствие платежей в
погашение кредита и процентов по нему; ρ – ограничение на суммарную рискованность кредитной заявки.
Ожидаемые проценты от комбинации кредитных
заявок будут определяться по следующей формуле:
N
(
)
E( X ) = ∑ k j ⋅ 1 + d j ⋅ t j ⋅ x j .
j =1
Таким образом, целевая функция задачи максимизации дохода может быть представлена в следующем
виде:
E ( X ) → max .
Ограничение, накладываемое на объем выдаваемых
кредитов,
N
∑k j ⋅ xj
≤F.
j =1
Ограничение, накладываемое на рискованность рассматриваемой кредитной заявки,
N
1
⋅
Pj ⋅ x j ≤ ρ .
∑
N
j =1
x
∑ j
j =1
Таким образом, в данном случае получаем задачу условной оптимизации с бинарными переменными.
В более адекватной модели, когда рассматривается не
только сам факт выдачи (невыдачи) кредита, но и возможные варианты кредитования, переменные могут
быть разнотипными – бинарными и целочисленными.
Из рассмотренных формальных моделей инвестиционного анализа видно, что для поддержки принятия инвестиционных решений необходимо решать достаточно
сложные задачи условной оптимизации с дискретными
или смешанными переменными и алгоритмически заданными линейными и нелинейными функциями. Кроме
того, данные задачи естественным образом обобщаются
до многокритериальных постановок. Классические методы статической и динамической оптимизации для таких задач не могут быть применены, поэтому необходимы более мощные и универсальные подходы.
ставляют собой стохастическую оптимизационную
процедуру, основанную на имитации процессов естественной эволюции. Возможные решения в этих алгоритмах называются индивидами, алгоритмы работают
одновременно с их группами (популяциями), применяя к индивидам и популяциям стохастические операторы преобразования (так называемые генетические
операторы – селекция, скрещивание, мутация, клонирование и т.п.).
Одними из наиболее эффективных эволюционных
алгоритмов в настоящее время являются стандартный
генетический алгоритм (ГА) и его модификация – вероятностный генетический алгоритм (ВГА) [6], основной особенностью которых является то, что они работают с бинарными переменными, т.е. решение задачи
должно быть предварительно бинаризовано.
В общем виде работу стандартного ГА можно представить следующим образом:
1. Инициализировать случайным образом популяцию решений.
2. С помощью оператора селекции выбрать наиболее пригодную часть популяции (родителей) для порождения потомков.
3. Применить оператор скрещивания (сгенерировать
новые решения).
4. Новые решения (потомков) подвергнуть мутации.
5. Из популяции родителей и потомков сформировать новую рабочую популяцию.
6. Повторять шаги 2–5, пока не выполнится условие
остановки.
По ходу работы ГА генерирует все более и более
пригодных индивидов, т.е. решения задачи, все более
близкие к оптимальным. Показано [5], что генетический алгоритм обладает сходимостью по вероятности к
оптимальному решению.
При анализе работы ГА становится ясно, что он, по
сути, в ходе работы накапливает и обрабатывает статистическую информацию о поверхности отклика целевой функции, что приводит к повышению вероятности
сгенерировать оптимальное решение. Однако такая
информация накапливается в популяции в неявном виде и используется опосредованно. Идея использовать в
явном виде статистическую информацию, накапливаемую в ГА, привела к созданию вероятностного генетического алгоритма [6].
Работу ВГА в общем виде можно представить следующим образом:
1. Инициализировать случайным образом популяцию решений.
2. С помощью оператора селекции выбрать наиболее пригодную часть популяции (родителей). Вычислить распределение вероятностей P = { p1 , …, pn } ,
{
ЭВОЛЮЦИОННЫЕ АЛГОРИТМЫ
Обзор эволюционных алгоритмов
В последние десятилетия получили развитие и
продемонстрировали свою универсальность и применимость в сложных практических задачах так называемые эволюционные алгоритмы [5], которые пред-
}
p j = P x j = 1 , j = 1, n , где n – длина хромосомы.
3. В соответствии с полученным распределением
P = { p1 , …, pn } сформировать популяцию потомков.
4. Новые решения (потомков) подвергнуть мутации.
5. Из популяции родителей и потомков сформировать новую рабочую популяцию.
6. Повторять шаги 2–5, пока не выполнится условие
остановки.
65
В ходе работы ВГА компоненты вектора вероятностей целенаправленно изменяются – стремятся к единице, если соответствующая компонента оптимального
решения равна единице, и к нулю – в противном случае. Такое поведение может быть использовано для
повышения эффективности алгоритма.
Прогнозирование оптимального решения
Накапливаемая в ходе решения задачи информация
и целенаправленное изменение компонент вектора вероятностей могут быть использованы для прогнозирования оптимального решения – если на определенной
стадии работы алгоритма становится ясно, к какому
именно значению стремятся определенные компоненты, то их будущее значение можно зафиксировать и
оценить получаемого индивида. Это может дать решение, пригодность которого значительно лучше, чем
текущая, что позволит сэкономить ресурсы, которые
должны быть затрачены на поиск такого решения в
ходе обычной работы алгоритма. Алгоритм прогноза
может быть реализован многими способами, но с учетом того, что он должен быть достаточно простым, так
как будет использован многократно в ходе работы
ВГА. После проведенных численных экспериментов
была предложена следующая процедура:
1. Для данной задачи выбрать определенную схему
ГА, определить шаг прогноза K.
2. Через каждые K поколений по набранной статистике ( p j ) , j = 1, n, i = 1, NK , NK = t ⋅ K , t ∈ N рассчитать
i
изменения
компонент
(Δp j )i = ( p j )i − ( p j )i−1 .
вектора
вероятности
3. Каждому поколению придать вес в зависимости
i
от его номера: σi = N K .
∑n
n =1
4.
Рассчитать
NK
( p ) = ∑ σ ⋅ ( Δp )
j
i =1
i
j i
прогнозируемый
вектор
.
⎧⎪1, p j ≥ 0,
=⎨
5. Считать x opt
j
⎪⎩0, p j < 0.
Вероятностный ГА с предложенным алгоритмом
прогноза был апробирован на ряде тестовых задач и
показал более высокую эффективность, чем ВГА без
прогноза. Данный алгоритм прогноза может быть также использован и для стандартного ГА.
Учет ограничений в генетических алгоритмах
На шагах 2 и 5 (селекция родителей и формирование новой популяции) обоих алгоритмов выбор индивида из популяции происходит в зависимости от его
степени пригодности. В общем случае, чем более пригоден индивид, тем у него больше шансов быть отобранным. Степень пригодности вычисляется через
функцию пригодности. Если при безусловной оптими66
зации вычисление пригодности через значение целевой
функции достаточно очевидно, то при наличии ограничений требуются специальные подходы. Известно
большое число таких подходов [7], ниже описаны те из
них, которые были выбраны после численных экспериментов на тестовых задачах.
Пусть решается следующая задача условной оптимизации:
f ( x) → extr,
⎧⎪ g j ( x) ≤ 0, j = 1, r ,
⎨
⎪⎩h j ( x) = 0, j = r + 1, m.
В общем случае пригодность индивида xi вычисляется по формуле [7]:
m
fitness( xi ) = f ( xi ) + δ ⋅ λ(t ) ⋅ ∑ f jβ ( xi ) ,
j =1
где t – номер текущего поколения, δ = 1 , если решается
задача минимизации, δ = −1 , если решается задача
максимизации, f j ( xi ) – штраф за нарушение j-го ограничения i-м индивидом, λ(t), β – параметры.
В частности, при использовании метода динамических штрафов [7]:
m
fitness( xi ) = f ( xi ) + δ ⋅ ( C ⋅ t ) ⋅ ∑ f jβ ( xi ),
α
j =1
⎧max {0, g j ( x)} , j = 1, r ,
⎪
f j ( x) = ⎨
⎪⎩ h j ( x) , j = r + 1, m.
Параметры α, β часто на практике принимаются
равными 2. Параметр C для каждой задачи подбирается
индивидуально (если же это не удается, то зачастую
полагается C = 0,5 ). Данный метод был выбран после
проверки и сравнения с другими методами как наиболее эффективный в рассматриваемых задачах.
В некоторых задачах условной оптимизации бывает
достаточно трудно получить даже допустимое решение. Зачастую это происходит из-за того, что в задаче
большое количество ограничений и/или допустимая
область является достаточной малой по отношению ко
всему поисковому пространству. В случае использования стохастических алгоритмов в сложных задачах оптимизации это тем более актуально. Для преодоления
данной трудности существует метод поведенческой
памяти [7]:
1. Генерация начальной популяции (допустимые и
недопустимые индивиды).
2. Счетчик учитываемых ограничений j = 1.
3. Текущая популяция является стартовой точкой
для следующей фазы эволюции, в течение которой все
точки, не удовлетворяющие хотя бы одному из j–1 учитываемых ограничений, отбрасываются. Критерий остановки – удовлетворение всем j–1 ограничениям заданной части популяции.
4. j = j+1; повторять два последних шага, пока j не
равно числу m +1.
Для данного алгоритма очень важен порядок добавления учитываемых ограничений.
Во многих случаях этот метод работает лучше
штрафных методов, так как зачастую небольшое по
сравнению со значением целевой функции значение
штрафа оставляет допустимую область скрытой среди
пиков «оштрафованной» целевой функции, находящихся в недопустимых областях.
С другой стороны, как показали эксперименты, для
данного метода не составляет труда быстро локализовать популяцию в рамках допустимой области при условии удачного выбора последовательности учета ограничений.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ
Рассматриваемые алгоритмы решения сложных задач оптимизации являются стохастическими, поэтому в
условиях, когда невозможно теоретически оценить их
эффективность, необходимо провести их тщательное
экспериментальное исследование на представительном
наборе тестовых задач.
Предварительное тестирование было проведено с использованием специально разработанной программной
системы [8], решающей задачи условной и безусловной
оптимизации с помощью стандартного и вероятностного
генетических алгоритмов. С помощью этой программной системы была исследована эффективность алгоритмов и выбраны наиболее эффективные установки. Затем
с помощью данной программной системы были решены
описанные выше задачи инвестиционного планирования. В дальнейшем на основе построенных моделей и
разработанных алгоритмов была реализована система
поддержки принятия решений инвестиционного аналитика [9], которая в настоящее время проходит апробацию в организациях и на производственных предприятиях Красноярского края и Кемеровской области. Примеры решения реальных задач приведены ниже.
Решение задачи венчурных инвестиций
Исходные данные для задачи венчурных инвестиций представлены в табл. 1.
В ходе решения задачи венчурных инвестиций было установлено, что допустимая область является довольно «узкой». В периоды времени t = 0, T 1 − 1 она
представляет собой отрезки прямых. Это связано с
тем, что в неравенствах-ограничениях присутствуют
фазовые переменные, которые выражаются через фазовые и управляющие переменные на всех предыдущих шагах времени. В моменты времени t = T 1 ,T − 1
допустимая область представляет собой прямоугольники. Из-за ограничений в моменты времени
t = 0, T 1 − 1 оказалось нелегко получить допустимые
решения. Ограничения в остальные моменты времени
легко удовлетворить за счет кодирования решения в
виде бинарной строки.
Для поиска допустимых точек предварительно решалась задача минимизации штрафной функции (степень нарушенности ограничений) с помощью стандартного ГА. Для этой цели в программе есть опция
«Поиск допустимого решения». Найденные допустимые решения подставлялись в стартовую популяцию
для исходной задачи, после чего удавалось найти точное решение исходной задачи.
Кроме того, решая задачу «как есть» (без предварительного поиска допустимых точек) и используя накопленную статистику о распределении 0 и 1 в бинарном
представлении решения, с помощью вероятностного
ГА удавалось спрогнозировать ответ, очень близкий к
точному решению. Более того, при подключении алгоритма поведенческой памяти (описанного выше) допустимые решения стали появляться уже на ранней
стадии работы алгоритма (в среднем на 40-м поколении). Окончательно было получено оптимальное решение, представленное в табл. 2.
Таблица 1
Исходные данные для задачи венчурных инвестиций
c0 = 5400 ⋅ 10 руб.
Стоимость здания цеха (ЗЦ)
T0 = 50 лет = 200 кварталов
Срок службы ЗЦ
c1 = 62850 ⋅ 10 руб.
Стоимость ОПФ
T1 = 10 лет = 40 кварталов
Срок службы ОПФ
b0 = 6285 ⋅ 10 руб.
Минимальный начальный платеж
I 0 = 68250 ⋅ 10 руб.
Максимальная сумма инвестиций
m=2
r=25% в год = 0,0625 в квартал
Количество видов продукции
Ставка доходности ИП
Налог на имущество
3
3
3
3
α 2 = 0,02 в год = 0,005 в квартал
α 3 = 0,24
Налог на прибыль
σ = 0,7
Доля себестоимости от цены
Период сборки ОПФ
1
T = 1 год = 4 квартала
T= 5 лет = 20 кварталов
q1 (t + 1) = 20778, 4 ⋅ 10 руб. в квартал; q2 (t + 1) = 18426,1 ⋅ 10 руб. в квартал
3
3
Период ИП
Спрос по каждому виду продукции
67
Таблица 2
Решение задачи оптимизации венчурных инвестиций
T
0
1
2
3
4 … 19
u1 (t )
11685
0
0
56565
20778,4
u 2 (t )
6285
0
0
56565
18426,1
x1 (t )
0
11685
11685
11685
68250
x 2 (t )
0
6285
6285
6285
68250
Количество разрешённых вычислений целевой функции составило 30000, что составило 0,09% мощности
допустимого множества (мощность допустимого множества 2 25 точек). Усреднение проводилось по 20 независимым прогонам алгоритма при каждом выборе
параметров.
Результаты работы стандартного ГА представлены
в табл. 4.
Таблица 4
Результаты оценки эффективности стандартного ГА
Решение задачи формирования оптимального
инвестиционного портфеля предприятия
Скрещивание
Мутация
Для решения задачи формирования портфеля реальных инвестиций предприятия использовались данные о конкретных инвестиционных проектах, взятые из
практики работы машиностроительного предприятия
оборонно-промышленного комплекса [2]. В табл. 3
приведен фрагмент списка ЦФО и инвестиционных
проектов, планируемых для внедрения, а также соответствующие им числовые данные: планируемые прибыльность, затраты и рискованность внедрения. Остальные параметры задачи: M = 40, r = 0,5, ρ = 1,98 .
Таблица 3
Исходные данные для задачи формирования
инвестиционного портфеля
Пij,
млн
руб.
ЦФО
Rij
Ci,
млн
руб.
cij,
млн
руб.
Ответ
1. ПТНП
Производство форточных
вентиляторов из УВС
Организация совместной
деятельности по производству посуды из полимеров
3,5
2,2
2,5
+
5,0
3,0
3,0
–
.................
Производство из УВС нагревателей воздуха для
автокарбюраторов
6,7
2,4
Производство тепловентиляторов из УВС
7,5
2,3
Всего по ЦФО 1
47,6
17,8
9,4
70,0
15,1
+
15,5
+
3,1
22,0
+
%
Равномерное
№
%
№
Турнирная селекция
100
6,9
95
6,21
100
5,4
Средняя
100
6,8
100
5,75
100
5,6
Сильная
100
9,2
100
8,15
100
7,95
Пропорциональная селекция
Слабая
0
0
0
0
0
0
Средняя
0
0
0
0
5
27
Сильная
0
0
0
0
0
0
Слабая
100
17,55
100
14,95
100
14,6
Средняя
100
19,1
100
18,2
100
18,05
Сильная
15
26
20
26
20
29,25
Ранговая селекция
Из табл. 4 видно, что наилучшие параметры для
стандартного ГА, дающие 100%-ю надежность и наименьшие затраты (средний номер поколения, на котором находится оптимальное решение), следующие:
селекция – турнирная (размер турнира – 10), мутация –
слабая, скрещивание – равномерное.
Результаты работы ВГА представлены в табл. 5.
Мутация
%
№
100
3,8
100
20,85
Средняя
%
Сильная
№
%
№
100
5,5
Турнирная селекция
100
4
Пропорциональная селекция
3,0
3,5
3,0
–
2,5
4,0
3,5
–
Комплектация ГБО ГИГ
1,0
1,5
0,5
+
Всего по ЦФО 5
6,5
9,0
12,0
7,0
137,8
55,6
221,0
260,9
Для того чтобы оценить эффективность алгоритмов
и определить наилучшие настройки генетических операторов, были выбраны следующие параметры: количество поколений – 30, размер популяции – 1000 индивидов, размер популяции родителей – 500 индивидов.
68
Двухточечное
Слабая
85,6
5. Цех 40
Итого
№
Слабая
.................
Производство дифференциального редуктора
Производство электромагнитного инжектора
%
Таблица 5
Результаты оценки эффективности ВГА
2. ПЭП
Трубы полиэтиленовые с
радиационной обработкой
Одноточечное
45
23,22
0
0
100
17,75
Ранговая селекция
100
8,35
100
10,2
Из табл. 5 видно, что наилучшие параметры для
ВГА, дающие 100%-ю надежность и наименьшие затраты на поиск, следующие: селекция – турнирная (размер
турнира – 10), мутация – слабая. Оператор скрещивания
ВГА не использует, заменяя его генерированием решений в соответствии с распределением вероятностей.
Сравнение табл. 4 и 5 показывает, что ВГА в целом заметно эффективнее стандартного ГА и получает точное
решение задачи раньше, чем стандартный ГА.
Точное решение задачи (полученное также и полным перебором) имеет вид
1011111111111111110110001.
При этом оценка прибыли принимает значение
117,7, а рискованность портфеля равна 1,98. Интерпретация данного ответа представлена в столбце «Ответ» (табл. 3), где знак «+» означает, что проект включается в портфель, а знак «–» – что не включается.
Решение задачи формирования оптимального
кредитного портфеля банка
Перейдем теперь к решению задачи формирования
оптимального кредитного портфеля банка. Исходные
данные предоставлены В.А. Пуртиковым (Красноярский филиал банка Москвы). Фрагмент данных представлен в табл. 6.
Таблица 6
Исходные данные для задачи формирования
кредитного портфеля
№
1
2
3
Сумма
кредита
10 000 000
5 300 000
2 400 000
24
25
26
950 000
580 000
640 000
49
50
Итого
Ставка
%
25
28
25
..........
26
27
24
..........
29
27
Период
Риск
75
80
91
0,042
0,039
0,029
83
90
91
0,034
0,038
0,042
22 000 000
91
350 000
69
256 695 000
Свободные ресурсы – 188 500 000
Таблица 7
Результаты работы стандартного ГА
Скрещивание
Мутация
Одноточечное
%
№
Двухточечное
%
Равномерное
№
%
№
Турнирная селекция
Слабая
72
26,78
80
29,58
78
27,03
Средняя
100
21,48
100
21,64
100
21,06
Сильная
100
20,72
100
19,78
100
20,2
Слабая
100
36,08
100
35,06
100
32,98
Средняя
96
50,38
100
44,86
100
40,88
Сильная
6
61
10
74,6
14
44,29
24,26
Пропорциональная селекция
Ранговая селекция
Слабая
88
25,43
86
25,7
94
Средняя
100
22,7
100
23,2
100
22,28
Сильная
100
36,88
100
36,06
100
33,34
Таблица 8
Результаты работы ВГА
Мутация
Слабая
%
Средняя
№
%
Сильная
№
%
№
100
19,36
100
22,38
100
18,64
Турнирная селекция
2
39
86
53,37
Пропорциональная селекция
0,016
0,026
Анализ эффективности ГА и ВГА проводился для
случая, когда объём кредитных заявок был равен 25,
так как в этом случае ответ может быть проверен полным перебором. Для того чтобы ГА смог проявить себя
в наибольшей степени, были выбраны следующие параметры: количество поколений – 100, размер популяции – 1000 индивидов, размер популяции родителей –
500 индивидов. Количество разрешённых вычислений
целевой функции – 100000, что составило 0,3% мощности допустимого множества (мощность допустимого
множества 2 25 точек). Усреднение проводилось по 50
независимым прогонам алгоритмов при каждом выборе
настроек.
Результаты исследования эффективности работы
стандартного ГА представлены в табл. 7.
Из таблицы видно, что наилучшие настройки для
стандартного ГА, дающие 100%-ю надежность и наименьшие затраты, – турнирная селекция (размер турнира – 10), сильная мутация, двухточечное или равномерное скрещивание.
Результаты исследования эффективности работы
ВГА представлены в табл. 8.
Из табл. 8 видно, что наилучшие настройки для
ВГА, дающие 100%-ю надежность и наименьшие затраты, – сильная мутация и ранговая или турнирная
селекция (размер турнира – 10).
0
0
22
39,55
100
43,62
Ранговая селекция
80
62,95
На последнем этапе исследования решалась исходная задача формирования кредитного портфеля банка,
когда объём кредитных заявок равен 50 (мощность допустимого множества 2 50 точек), т.е. количество разрешенных вычислений целевой функции составляло
8 ⋅ 10 −9 % мощности допустимого множества. Настройки ГА и ВГА были выбраны оптимальными, как это
было установлено выше.
Анализ решений задачи, получаемых стандартным
ГА и ВГА по многим независимым прогонам, показывает, что ВГА находит решения в среднем лучшие, чем
решения стандартного ГА, и разброс значений целевой
функции у ВГА гораздо меньше, чем у стандартного
ГА. Это свидетельствует о том, что ВГА не только более эффективен в данной задаче, но и более устойчив,
чем стандартный ГА.
ЗАКЛЮЧЕНИЕ
Результаты решения практических задач инвестиционного планирования оказались лучше, чем у специалистов соответствующих организаций [2, 4], и получили их одобрение.
Полученный в ходе выполнения работы опыт был использован при реализации системы поддержки принятия
69
решений инвестиционного аналитика [9], где по умолчанию установлены параметры алгоритмов в соответствии с
результатами данного исследования (в частности алгоритмом решения задач является ВГА), хотя при желании
пользователь может и поэкспериментировать с ними.
Таким образом, в ходе выполнения данной работы
создана система поддержки принятия решений для
анализа и планирования реальных инвестиций, осно-
ванная на современных математических моделях, по
возможности приближенных к реальности, и адаптивных алгоритмах, эффективно решающих получаемые
задачи оптимизации. Разработанная система не требует
от практических работников дополнительных знаний за
пределами их повседневного опыта, прошла тщательную проверку на реальных задачах и передана аналитикам-практикам для апробации.
ЛИТЕРАТУРА
1. Медведев А.В. Анализ модели реальных инвестиций с учетом целей производителя, инвестора и поставщика оборудования / А.В. Медведев,
П.Н. Победаш // Материалы IX Международной научной конференции «Решетневские чтения». Красноярск: СибГАУ, 2005. С. 199–200.
2. Хайниш С.В. Российское предприятие ВПК: выжить и развиваться / С.В. Хайниш, В.М. Клешков, А.Н. Бородин. М.: Рохос, 2003. 240 с.
3. Семенкин Е.С. Модели и алгоритмы распределения общих ресурсов при управлении инновациями реструктурированного машиностроительного предприятия / Е.С. Семенкин, В.М. Клешков // Проблемы машиностроения и автоматизации. 2006. № 3.
4. Пуртиков В.А. Оптимизация управления формированием кредитного портфеля банка: Дис. … канд. техн. наук. Красноярск: САА, 2001.
148 с.
5. Goldberg D. Genetic algorithms in search, optimization and machine learning. Reading, MA, Addison-Wesly, 1989.
6. Семенкин Е.С. Вероятностные эволюционные алгоритмы оптимизации сложных систем / Е.С. Семенкин, Е.А. Сопов // Труды Международных научно-технических конференций «Интеллектуальные системы» (AIS’05) и «Интеллектуальные САПР» (CAD-2005): В 3 т. М.:
ФИЗМАТЛИТ, 2005. Т. 1. 452 с.
7. Michalewicz Z. Genetic algorithms, numerical optimization and constraints // Proc. of the 6th Int. Conf. on Genetic Algorithms and their Applications.
Pittsburg: PA, 1995.
8. Ворожейкин А.Ю., Семенкин Е.С. Вероятностный генетический алгоритм решения задач условной оптимизации. М.: ВНТИЦ, 2006. № гос.
рег. 50200600371.
9. Ворожейкин А.Ю., Медведев А.В., Семенкин Е.С. Автоматизированное рабочее место инвестиционного аналитика. М.: ВНТИЦ, 2006. № гос.
рег. 50200600629.
Статья представлена кафедрой механики и процессов управления факультета математики и информатики Красноярского государственного
университета, поступила в научную редакцию «Кибернетика» 6 июня 2006 г.
70
Документ
Категория
Без категории
Просмотров
7
Размер файла
394 Кб
Теги
решение, алгоритм, поддержка, принятие, инвестиционная, модель, аналитика
1/--страниц
Пожаловаться на содержимое документа