Некоторые эвристические алгоритмы для решения задачи формирования инвестиционного портфеля

Рациональное инвестирование средств является важной задачей, стоящей перед инвесторами. Она важна как для инвесторов, так и для народного хозяйства в целом. Задачи формирования оптимальных (в том или ином смысле) портфелей из инвестиционных проектов рассматривались многими исследователями [1, с.21; 2, с.235; 3, с.17; 4, с.48; 5,с.230; 6,с.800]. В данной статье рассматривается проблема формирования оптимального инвестиционного портфеля, состоящего из инвестиционных проектов, с учетом групповых платежей.

Задача формирования портфеля

Имеется набор проектов С₁, С₂ , …, С_m (C_i=(c_i0, c_i1, …, c_in )), из которых инвестору необходимо выбрать некоторые инвестиционные проекты (потоки платежей) для финансирования. Инвестиционный проект С_i= (c_i0 , c_i1 , … , c_in) это вектор, у которого первая ненулевая компонента, если такие существуют, отрицательная, а последняя ненулевая компонента положительная. Компонент вектора c_ij– сумма платежа или возврата средств по проекту iв момент времени j. Будем считать, что все проекты сосредоточены на общем временном интервале, для этого, при необходимости, можно дополнить проекты нулевыми платежами. При этом предполагается возможная зависимость между некоторыми проектами, т.е. выбор проекта для включения в портфель зависит от того, с какими проектами он связан. Зависимость можно представить в виде ориентированного графа, где вершинам соответствуют проекты, а ребра определяют зависимость между проектами таким образом, что для включения в портфель некоторого проекта необходимо включение и его предшественников. После ряда преобразований [12,c.56;13,c.174;14,c.108] задача сводится к частично целочисленной задаче линейного программирования.

Найти числа

х₁,…, х_mÎ{0,1};

y₁,…,y_sÎ{0,1};

F₁,…,F_nÎR

такие, что

y_j³x_i при iÎU_j;

х_i≥ х_k

для зависимых проектов;

F _k+1£qF_k при k=0,1,…,n-1;

F_k+1£rF_k при k=0,1,…,n-1;

F_n® max

Приближенные методы решения

Для решения задачи применялись следующие эвристические методы:.

Модифицированный метод ветвей и границ

Применялся следующий эвристический прием, адекватный структуре задачи. Применим метод ветвей и границ к множеству проектов U1, в результате получим портфель П1. Затем применим тот же метод к множеству проектов U2  при условии, что в портфель уже вошли проекты из П1. В результате получим портфель П2ÉП1. Продолжая этот процесс, после (s+1) шагов получим портфель П (проекты, не входящие ни в одно из множеств Uj, анализируются на последнем шаге) . Такой прием достаточно эффективен, если множества Uj не являются ни слишком большими, ни слишком малыми непересекающихся множествах Uj  равного размера сложность вычислений можно оценить числом , где s – число множеств.

Алгортм решения

Шаг 1. Для j от 1 до s выполнять:

1.1 Вход: C_i, U_j, q, r, m, k. Проверка: если U_jПj, то рассматриваются для включения в портфель только те проекты, из множества U_j, которых нет в множестве Пj.  Применяется стандартный метод ветвей и границ ко множеству U_j.

Выход:  Портфель П_j, капитал инвестора Rbest.Если j=s, то переход к шагу 2, иначе →шаг 1.2.

1.2 Вход:П_j, П_j+1. П_j+1+П_j →шаг 1.1.

Выход: П_j+1.

Шаг 2. Если есть CiUj, то применяется стандартный метод ветвей и границ к оставшемуся множеству проектов. Конец алгоритма [7,с.36; 8,с.85; 11, с.253].

Эволюционный алгоритм (1+1)-ЕА [9, с.57; 10, с. 182; 12, с.56]

Для описания этого алгоритма рассмотрим следующие термины.

·                    Особь (индивидуум) – инвестиционный портфель.

·                    Хромосома – приоритетный список проектов .

·                    Популяция – в данном алгоритме состоит из одной особи.

·                    Воспроизведение (оператор репродукции) –  репродукция особи, т.е. формирование портфеля на основе текущего приоритетного списка.

·                    Отбор (оператор селекции). Применяется так называемый элитный отбор, то есть из всех особей отбираются особи с наибольшим возможным капиталом на конец временного горизонта.

·                    Оператор мутации. Проекты в приоритетном списке меняются местами случайным образом. В результате получается новая хромосома.

Алгоритм решения

Вход:

·                Множество проектов С1, С2, С3…Сn;

·                Начальный капитал инвестора F_-1;

·                Подмножества Uj;

·                Множество векторов платежей Pj;

·                Ставки q и r;

·                Приоритетный список проектов П;

·                Port – инвестиционный портфель;

·                F-итоговый капитал текущего портфеля;

·                FBest – лучший итоговый капитал;

Шаг 1.1: для i=1 до n выполнять:  рассчитывается NPV каждого проекта по формуле NPV= +∑(()/ N(Uj) )

Шаг1. 2: для i=1 до n выполнять: в приоритетный список П записываются номера проектов в порядке убывания их NPV.

Шаг 2:  Воспроизведение

2.1 для i=1 до n выполнять:  Port:=П[i] \\ в текущий портфель помещается проект из приоритетного списка П.

2.2 рассчитывается F для этого портфеля по формуле:

Шаг 3:  Селекция

3.1 если F> FBest, то  FBest:=F и переход к шагу 2,

3.2 если F≤ FBest, то  последний проект из портфеля Port возвращаем в конец списка П и переход к шагу 2,

3.3 если F≤ FBest два или более раз, то переход к шагу 4.

3.4 если F≤ FBest больше Z раз, то конец алгоритма.

Шаг 4: Мутация - случайная перестановка элементов в списке П с помощью наивного алгоритма: Из приоритетного списка П оператор random случайным образом выбирает 1 элемент, он ставится в начало списка П_new, эта процедура повторяется до тех пор, пока в список П не станет пустым. Переход к шагу 2.

Выход: FBest - лучший итоговый капитал,  Port - инвестиционный портфель.

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

Работа выполнена при поддержке РФФИ (проект 07-06-00021).

Литература:

1.                  Виленский П.Л., Лившиц В.Н., Смоляк С.А. (2002): Оценка эффективности инвестиционных проектов. М.: Дело.

2.                  Lorie J.H., Savage I.J. (1955): Three Problems in Rationing Capital // Journal of Business. v.XXVIII. №4.

3.                  Weingartner H.M. (1967): Mathematical Programming and the Analysis of Capital Budgeting Problems. Chicago: Markham publ.

4.                  Бронштейн Е.М. (2004): Оптимальные инвестиционные портфели // Системное моделирование социально – экономических процессов. М.: ЦЭМИ РАН.

5.                  Balinski M.L. (1970): On a Selection Problem // Management Science. v.17. №11.

6.                  Mamer J.W., Shogan A.W. (1987): A Constrained Capital Budgeting Problem with Applications to Repair Kit Selection // Management Science. v.33. №6.

7.                  Корбут А.А., Сигал И.Х., Финкельштейн Ю.Ю., Об эффективности комбинаторных методов в дискретном программировании. М.: Наука,1979.

8.                  Сигал И.Х., Иванова А.П., Введение в прикладное дискретное программирование. М.:Физматлит, 2007.

9.                  Батищев Д.Ю. Генетические алгоритмы решения экстремальных задач // учебное пособие под ред. Я.Е.Львовича. Воронеж: Воронежский гос. техн. ун-т; Нижегородский ун-т. 1995.

10.              Борисовский П.А., Еремеев А.В. О сравнении некоторых эволюционных алгоритмов // Автоматика и телемеханика, №2, 2004.

11.              Корбут А.А., Сигал И.Х., Финкельштейн Ю.Ю. Метод ветвей и границ. Обзор теории, алгоритмов, программ и приложений // Math. Operation Forsch. Statist. Ser. Optimization. 1977. V.8, №2.

12.              Муслимова, Г. Р. Дополнительные условия при формировании оптимальных портфелей, состоящих из инвестиционных проектов // Молодой ученый. 2010.  №6.

13.              Муслимова Г.Р. Задача формирования оптимального инвестиционного портфеля из инвестиционных проектов с дополнительными условиями. Системное моделирование социально – экономических процессов :  материалы международной научной школы – семинара им. академика С.С. Шаталина. ЦЭМИ РАН, Воронеж, 2008.

14.              Муслимова Г.Р. Методы решения задачи формирования оптимальных инвестиционных портфелей  с учетом групповых выплат. Актуальные задачи математического моделирования и информационных технологий: материалы 6-й всероссийской открытой научно – практической конференции. Сочи, 2010.