Портфель инвестиционных проектов в нефтедобывающей компании

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

Портфель инвестиционных проектов в нефтедобывающей компании



Содержание

Введение

Глава 1. Теоретические основы моделирования системы инвестиционной стратегии

1.1 Чистый дисконтированный доход

1.2 Генетический алгоритм

1.3 Объектно-ориентированное программирование

1.4 Основы баз данных

Выводы к главе 1

Глава 2. Инструментальные методы моделирования системы инвестиционной стратегии

2.1 Обоснования выбора инструментов

2.2 Математическая модель оценки инвестиционного портфеля

2.3 Модификация генетического алгоритма

Выводы к главе 2

Глава 3. Реализация системы инвестиционной стратегии

3.1 Схема базы данных

3.2 Программная реализация

Выводы к главе 3

Заключение

Список использованной литературы

Приложение



Введение

Управленческие решения в деятельности нефтяной компании имеют более высокую сложность, масштаб и стоимость, чем в других сегментах. [1] Кроме того, значимой особенностью нефтяной компании является способ ее взаимодействия с банковской системой, а именно возможность взятия кредита на крупную сумму денег. Для эффективной деятельности нефтяной компании важно проведение планирования ее денежных средств. Одной из его основных составляющих является планирование расходования средств на новые инвестиционные проекты. Для того чтобы измерить, насколько проект выгоден, используются такие показатели как NPV, PI, DPP. В 2010 году Moslem Shahsavar, Seyed Taghi, Akhavan Niaki и Amir Abbas Naja был разработан алгоритм оптимизации инвестиционной деятельности для одного проекта, использующий метод максимизации NPV [2]. В данном исследовании были рассмотрены составляющие проекта и построена математическая модель, с помощью которой впоследствии производилось оптимизация.

Одной из главных задач нефтяной компании является максимизация собственной рыночной стоимости. Однако имеется принципиальная сложность управления огромным пулом инвестиционных проектов нефтяной компании. [1] Правильное управление проектами является одним из основных способов достижения данной цели. В случае, если компания не ограничена размером денежных средств, которые она способна вложить в проекты, оптимизация инвестиционного портфеля сводится к задаче нахождения максимального NPV для каждого из проектов; в таком случае суммарная NPV окажется максимально возможной. В реальности, денежные ресурсы, которыми обладает фирма, ограничены. Нахождение оптимальной комбинации вклада денежных средств по годам в проекты является NP полной задачей. В связи с этим в рамках данного проекта была разработана программа, аппроксимирующая решение таких задач с помощью RGA алгоритма [3]. Хотя данный алгоритм не гарантирует нахождения глобального максимума, в результате он находит одно из лучших решений, которое, в свою очередь, может с большой вероятностью оказаться глобальным максимумом [4]. Функция, в которой будет происходить поиск решения, является суммарным NPV по всем проектам.

Объектом исследования является портфель инвестиционных проектов в нефтедобывающей компании.

Предметом исследования является программа для нахождения оптимального портфеля.

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

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

1. Составить базу данных для инвестиционных проектов.

2. Разработать математическую модель для оценки инвестиционного проекта.

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

4. Реализовать программу для автоматического выбора оптимального портфеля.

При этом в ходе построения модели нами были введены следующие ограничения:

1. Проект является не делимым по времени.

2. Проекты не зависимы

3. Проект можно выполнить не более одного раза.

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

5. Кредитная ставка не меняется в течении лет.

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

Структура ВКР

ВКР состоит из введения, трех глав, заключения, списка литературы и приложения. Объем работы составляет 40 страниц машинописного текста, включая рисунки и таблицы.

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

В первой главе ВКР более подробно рассмотрена теоретическая основа исследования: показатель NPV и Генетический алгоритм, которые являются основой для проектирования алгоритма и реализации приложения. Также приведены определения терминов и основы проектирования БД.

Вторая глава ВКР содержит математическую модель и модификацию генетического алгоритма для решения поставленной задачи.

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

В заключении представлены основные результаты реализованного проекта.



Глава 1. Теоретические основы моделирования системы инвестиционной стратегии

1.1 Чистый дисконтированный доход

В современной экономической науке сложилось несколько методов для анализа процесса принятия решений между двумя и более инвестиционными проектами:

1. Метод срока окупаемости (Payback Period, PP)

Суть данного метода состоит в том, что наиболее предпочтительным является тот проект, окупаемость которого наступает раньше, чем у других.

2. Метод средней доходности

В рамках данного метода вычисляется средний доход инвестиций и выбирается проект, чей средний доход больше остальных.

3. Метод чистого дисконтированного дохода

В данном методе считается простое NPV и предпочтение отдается тому проекту, у которого NPV выше.

4. Метод продолженного срока

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

5. Метод эквивалентного ежегодного аннуитета

В данном методе находится денежный поток в виде аннуитета, который обеспечивает то же значение NPV. В результате, нами принимается проект с более высоким аннуитетом. [5,6].

Как отмечалось нами ранее во введении, одним из методов оценки инвестиционных проектов нефтяной компании, основанном на методологии дисконтирования денежных потоков, является NPV ("Net Present Value").

Формула расчета NPV выглядит следующим образом:

, где

n -- количество временных периодов,

CF -- денежный поток (Cash Flow),

d -- стоимость капитала (ставка дисконтирования)

При расчете ставки дисконтирования используется одна из следующих моделей: CAPM модель, WACC (Weighted Average Cost of Capital), Модель Гордона или Hurdle Rate or Rule of Thumb [7].

При расчете денежного потока считаются доходы и из них вычитаются затраты за текущий период времени. Обычно период времени берется равным одному году.

Для стандартного проекта график имеет следующий вид (рис. 1):

Рис. 1 График NPV

На графике мы видим две кривые одного и того же проекта с учетом и без учета дисконтирования.

Некоторые проекты не выходят за рамки окупаемости, то есть находятся только в нижней стороне абсциссы X. Однако в данной работе нами будут рассмотрены исключительно проекты, обладающие положительным NPV. Все проекты с отрицательным NPV были отброшены в результате проведения начальной фильтрации.

Кривую, показанную на Рис. 1, условно можно разделить на три составляющих:

1. Инвестиции в проект превышают ее прибыль (кривая убывает , CF <0).

2. Прибыль начинает превышать периодические затраты на инвестиции. (кривая возрастает, СF>0)

3. Кривая прошла точку окупаемости.

Для подсчета суммарного NPV по проектам можно использовать сумму всех NPV по проектам. Суммарное NPV для N независимых проектов до момента времени T подсчитывается следующим образом:

, где

NPVS - суммарное NPV по всем проектам на момент времени T;

N - количество проектов;

T - момент времени, до которого нужно максимизировать NPV;

- денежный поток одного проекта в момент времени t;

d - стоимость капитала (ставка дисконтирования).

Преимущества метода NPV для оценки инвестиционных проектов нефтяной компании заключаются в том, что данный метод ориентирован на увеличение благосостояния инвесторов и максимизации количества наличных денег. Кроме того, NPV удобен для проведения расчетов, поскольку показатель для принятия решений достаточно четко определен. Кроме того, метод NPV позволяет учитывать временный показатель стоимости денег. Однако данный метод не является универсальным и имеет некоторые недостатки. Во-первых, данный метод не отражает оценку соотношения дохода и затрат. Во-вторых, в рамках данного метода прогнозирование денежных потоков является достаточно сложным. В-третьих, в соотношении с другими показателями NPV иногда может давать противоречивые результаты. [8]

1.2 Генетический алгоритм

1 Понятие генетический алгоритм

Оптимизационные задачи являются задачами нахождения экстремума целевой функции. Существует достаточно большое количество оптимизационных методов, позволяющих решить данный тип задач. Условно их разделяют на два кластера: "градиентные" и "стохастические" методы. С помощью данных методов можно найти экстремум целевой функции, но при этом не всегда удается найти глобальный минимум (максимум). Нахождение локального экстремума, вместо глобального, называется преждевременной сходимостью. Кроме того, такие методы обладают существенным ограничением, обусловленным проблемой времени вычисления необходимого показателя. Как правило, чем дольше работает оптимизационный метод, тем точнее итоговый результат. Одним из оптимизационных методов является генетический алгоритм.

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

Данный алгоритм относится к области мягких вычислений. Мягкие вычисления объединяют такие области, как нейронные сети, нечеткая логика, сети доверия и т.д. Данный метод был предложен в 1975 году Джоном Холландом. Кроме того, в нем используются понятия, заимствованные из биологии, такие как ген, эволюция и хромосома [9].

Код работы генетического алгоритма может быть представлен как последовательное выполнение следующих шагов:

1. Сгенерировать начальную популяцию.

2. Оценить начальную популяцию.

Повторять, пока не выполнится условие остановки.

3. Выбор родителей. Отобрать часть популяции для воспроизводства.

4. Рекомбинация. Выполнить скрещивание "генов" отобранных родителей.

5. Мутация. Случайным образом осуществить мутацию полученной популяции.

6. Оценивание. Оценить пригодность популяции.

7. Отбор. На основе полученной пригодности выбрать выживших индивидов [9].

2 Операторы генетического алгоритма

Выбор родителей

За время существования генетического алгоритма было разработано большое количество способов выбора родительской пары. Наиболее распространенными являются следующие:

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

Инбридинг - в рамках данного метода случайным образом выбирается первый родитель, после чего находится особь, которая наиболее похожа на нее.

Аутбридинг - принцип работы данного метода подобен методу инбридинг. Единственное отличие между ними состоит в том, что в данному случае выбирается наиболее отдаленная хромосома.

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

Турнирный отбор - в рамках данного метода N раз случайным образом выбираются несколько особей. Лучшая из них записывается в промежуточный массив, где N является количеством хромосом в популяции.

Метод рулетки подсчитывает приспособленность каждой особи. На основе приспособленности хромосомы рассчитывается вероятность попадания его в новую популяцию. После чего N раз случайным образом с учетом вероятности выбирается особь и записывается в новую популяцию.

Рекомбинация

Рекомбинация -- это процесс обмена генами между двумя (или более) родительскими особями, в ходе которого получается новые особи, содержащие в себе гены родителей.

Существует много способов проведения рекомбинации. Условно можно разделить все методы на два класса:

1. Дискретная рекомбинация

2. Кроссинговер (бинарная рекомбинация)

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

Рекомбинацию бинарных строк принято называть кроссинговером или скрещиванием.

Основными способами кроссинговера являются:

1. Одноточечный кроссинговер - в данном методе случайным образом выбирается точка внутри хромосомы. Обе хромосомы делятся на две части в соответствии с точкой разрыва и обмениваются частями. Вследствие одноточечного кроссинговера создаются два потомка.

2. Многоточёчный кроссинговер - случайно выбирается несколько точек разреза. Далее массив с точками разреза сортируется и происходит обмен частями генов между родителями.

3. Перетасовочный кроссинговер - в данном алгоритме особи, отобранные для кроссинговера, случайным образом обмениваются генами.

4. Кроссинговер с уменьшением замены - Данный оператор используется, чтобы замедлить сходимость. Данный метод действует аналогично многоточечному кроссинговеру. Разница заключается в том, что вводятся ограничения на выбор точек разреза: точки разреза должны появляться только там, где гены различаются.

Мутация

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

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

Мутация в хромосоме может происходить не только в одной точке, но и в нескольких, а также может применятся как к вещественным, так и к бинарно закодированным хромосомам. В соответствии с этим есть несколько видов проведения мутации.

Основные виды мутации:

1. Мутация для вещественных особей - определяется шаг мутации и в дальнейшем ген изменяется на этот шаг.

2. Двоичная мутация - для двоично закодированных особей работа оператора мутации заключается в случайном изменении гена на инвертированный (0 заменяется на 1 и наоборот).

3. Плотность мутации - способ мутации, в рамках которого ген потомка мутирует с заданной вероятностью [9].

3 Основные понятия

Популяция - это конечное множество особей.

Хромосомы - это упорядоченные последовательности генов.

Ген - это атомарный элемент генотипа, в частности хромосомы.

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

Фенотип - это набор значений, соответствующих данному генотипу, т.е. декодированная структура или множество параметров задачи (решение, точка пространства поиска).

Аллель - это значение конкретного гена.

Локус или позиция- место размещения данного гена в хромосоме (цепочке).

Функция приспособленности (fitness function), иначе называемая функцией оценки - мера приспособленности данной особи в популяции [8].

1.3 Объектно-ориентированное программирование

К концу 1970-х годов, когда использовалась методология структурированного программирования и язык "С", объем многих программ был слишком большим, что затрудняло чтение кода. С целью решения данной проблемы был разработан новый способ построения архитектуры программы. Этот метод называется объектно-ориентированным программированием (ООП). Используя ООП, программист может обрабатывать программы, обладающие гораздо большими объемами. [10]

Объектно-ориентированное программирование является способом создания архитектуры программы, в которой элементами являются объекты и классы. [11]

Объект в объектно-ориентированном программировании -- это модель или абстракция реальной сущности в программной системе. Составными частями объекта являются данные и методы.

В С# класс используется для создания объектов. Объекты -- это экземпляры класса.

Таким образом, класс является набором шаблонных элементов, которые показывают, каким образом построить объект.

Код и данные, из которых состоит класс, называются членами класса. В свою очередь, данные, определенные в классе, называются переменными экземпляра, а код, который оперирует этими данными - методами. "Метод" в данном случае является термином, использующимся для обозначения подпрограммы.

Для поддержки принципов объектно-ориентированного программирования используются три характеристики: инкапсуляция, полиморфизм и наследование. Далее данные характеристики будут рассмотрены нами более подробно.

1. Инкапсуляция

Инкапсуляция -- это механизм связывания кода и данных, который предохраняет их от вмешательства извне и неправильного использования со стороны пользователя или другого программиста. В объектно-ориентированном языке объект представляет собой элемент, который поддерживает инкапсуляцию. Инкапсуляция поддерживает 3 типа защиты: Public, private и protected. Разные элементы внутри одного и того же объекта могут иметь разные типы защиты. К примеру, в объекте animal метод Walk может быть public, а метод Eat - private. Немного подробнее остановимся на каждом из видов.[12]

Закрытый код или закрытые данные известны лишь остальной части этого объекта и доступны только ей. Это означает, что к закрытому коду или данным не может получить доступ никакая другая часть программы, существующая вне этого объекта.

Если код или данные являются открытыми, к ним (несмотря на то, что они определены внутри объекта) могут получить доступ другие части программы. Как правило, открытые части объекта используются для обеспечения управляемого интерфейса с закрытыми элементами.

Основной единицей инкапсуляции в языке С# является класс. Класс определяет форму объекта. Кроме того, он задает как данные, так и код, который будет оперировать этими данными.

2. Полиморфизм

Полиморфизм (от греческого слова polymorphism, означающего "много форм") -- это качество, которое позволяет одному интерфейсу получать доступ к целому классу действий.

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

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

3 Наследование

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

Например, есть класс "Овощ" и есть класс "Брокколи". У всех овощей есть общие свойства и поскольку "Брокколи" является овощем, он также обладает этими свойствами. В данном примере класс "Овощ" является родителем класса "Брокколи".

Если программист не будет использовать наследование, то ему придется в явном виде описывать все свойства родителя для каждого потомка. Благодаря наследованию объекту нужно доопределить только те характеристики, которые делают его уникальным внутри его класса, поскольку он наследует общие характеристики своего родителя. Следовательно, именно механизм наследования позволяет одному объекту представлять конкретный экземпляр более общего класса.[10]

4. Алгоритм сортировки

Благодаря свойству "Полиморфизма", которое пресуше объектно-ориентированным языкам, в библиотеке Microsoft С# реализованы методы, которые могут быть применены к многим типам объектов с помощью внесения небольших изменений. Одним из таких методов является реализованный в стандартной библиотеке Microsoft С# метод Sort.

Данный метод сортирует элементы в массиве с заданным условием сравнения. Для работы с ним нужен массив, в котором находятся элементы, использующие реализацию интерфейса IComparable.

В данном интерфейсе реализован интроспективный алгоритм сортировки следующим образом:

1. Если количество возможных разделений на подмножества в массиве меньше 16, он использует алгоритм insertion sort.

2. При количестве разделений на подмножества превышающее 2 * Log N, где N - количество элементов в массиве, он использует алгоритм Heapsort.

3. В остальных случаях данный метод использует алгоритм под названием Quicksort.

В данном случае осуществляется нестрогая сортировка, что означает, что при равенстве значений двух элементов их порядок нахождения в массиве может изменяться.

Данный метод в среднем имеет сложность , где n - количество элементов в массиве. [13]

5 Многопоточное программирование

В программировании программы условно можно разделить на два типа: однопоточные и многопоточные.

В Microsoft C# программисту дается возможность выбирать, какую программу ему написать. Одно из преимуществ многопоточного программирования состоит в том, что в нем задача разделяется на несколько независимых частей, которые выполняются одновременно. Данная особенность позволяет не блокировать пользовательский интерфейс при выполнении работы программы. [14]

Поток -- это единица обработки данных, а многозадачность -- это одновременное использование нескольких потоков. Есть два вида многозадачности:

1.Совместная

2. Вытесняющая [15]

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

Данный способ реализации многозадачности является устаревшим и содержит в себе много недостатков.

В вытесняющей многозадачности процессор определяет количество времени для выполнения каждого потока. Для обозначения данного процесса используется термин "кванта времени". Далее процессор переключается между разными потоками, выдавая каждому потоку его квант времени. В библиотеке .Net реализована вытесняющая многозадачность.

Создание и управление потоками в ней осуществляется с помощью класса System. Threading. Thread. Для удобной работы в многопоточном режиме windows form можно осуществлять с помощью использования компонента BackgroundWorker. Этот класс управляет отдельными потоками указанного метода обработки.

Чтобы запустить операцию в фоновом режиме необходимо создать BackgroundWorker и отслеживать события, сообщающие о ходе выполнения операции и сигнализирующие о ее завершении. [16]

1.4 Основы баз данных

База данных является совокупностью данных, хранимых по определенной схеме. В госте Р ИСО МЭК ТО 10032-2007: Эталонная модель управления данными (идентичен ISO/IEC TR 10032:2003 Information technology -- Reference model of data) определение понятия базы данных было дано следующим образом:

"База данных -- это совокупность данных, которые хранятся в соответствии со схемой данных, манипулирование которыми выполняют в соответствии с правилами средств моделирования данных".

Основным принципом организации баз данных является тип описания хранения в соответствующей форме. [17]

Существует большое количество видов баз данных. При классификации по моделям используемых данных самыми распространёнными видами являются:

1. Иерархическая

2. Реляционная

3. Объектно-ориентированная

4. Объектно-реляционная

5. Сетевая

Поскольку в рамках ВКР была спроектирована реляционная база данных, мы более подробно остановимся именно на данном виде.

Реляционная модель данных (РМД) -- это логическая модель данных, которая является приложением к задачам обработки данных таких разделов математики, как теория множеств и логика первого порядка.

На базе теории РМД строятся реляционные базы данных.

В состав реляционной модели данных включается теория нормализации. Существует семь видов нормальной формы. Они имеют иерархическую схему. Например: если база находится в 5-ой нормальной форме, то она находится и в форме Бойса кода, и в 4 нормальной форме.

Первая нормальная форма (1НФ).

Отношение приведено к 1НФ тогда и только тогда, когда все его атрибуты простые.

Вторая нормальная форма (2НФ).

Отношение находится во 2НФ, если оно находится в 1НФ и каждый не ключевой атрибут функционально полно зависит от составного ключа. Третья нормальная форма (3НФ).

Отношение находится в 3НФ, если оно находится во 2НФ и каждый не ключевой атрибут не транзитивно зависит от первичного ключа.



Выводы к главе 1

В первой главе нами была рассмотрена теоретическая основа исследования. Было дано определение показателя дисконтированного денежного потока и приведена формула его расчёта. На основе показателя NPV была приведена формула для расчёта суммарного NPV для инвестиционного портфеля. Данный показатель в дальнейшем послужит инструментом для сравнения двух инвестиционных портфелей внутри нефтяной компании.

Кроме того, нами было дано определение генетического алгоритма и последующее объяснения его структуры, а также существующие виды его реализации.

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

В параграфе 1.3. нами было рассмотрено объектно - ориентированное программирование и даны три главных его свойства. Там же нами была представлена схема работы сортировки, реализованной в стандартной библиотеке Microsoft C#.

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



Глава 2. Инструментальные методы моделирования системы инвестиционной стратегии

2.1 Обоснования выбора инструментов

Для решения задач, поставленных в данном ВКР, был выбран генетический алгоритм. Подобный выбор обусловлен следующими факторами:

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

Во-вторых, в данной задаче гены хромосомы являются независимыми друг от друга.

В-третьих, данный алгоритм интуитивно понятен и легко модифицируется под требования поставленной задачи.

Как было уже сказано в первой главе, генетический алгоритм использует понятия, взятые из биологии. Благодаря данной особенности не представляется трудным описать данный алгоритм с использованием объектно-ориентированного языка. Поскольку программа предназначалась для пользователей ОС Windows, то выбор был сделан в пользу Microsoft C#, поскольку оно является лучшим объектно-ориентированным языком для написания программ для ОС Windows.

Microsoft C# тесно интегрирован с Microsoft SQL Server. В нем прописаны библиотеки и инструменты для удобной работы с базой данных. Именно данным фактом обусловлен выбор среды разработки локальной базы на базе Microsoft SQL.

Проектирование базы проводилось в программе Erwin 9.0. ERwin является удобной средой для проектирования базы данных. В данной программе присутствует функция экспортирования готового кода для MS SQL. Благодаря этому, после проектировки базы в Erwin можно запустить запрос в MS SQL и одним кликом мыши создать базу.

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

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

2.2 Математическая модель оценки инвестиционного портфеля

В построенной нами модели участвуют следующие объекты:

1. Инвестиционный портфель

2. Проекты

3. Банк

Проект

Представляет собой объект, в котором записана вся информация о проекте.

Каждый проект имеет 3 способа реализации: с маленьким бюджетом, средним бюджетом и большим бюджетом. Для каждого способа реализации даны данные доходов и затрат по каждому году, полученные с помощью инвестиционного проектирования для нефтедобывающей компании.

Инвестиционный портфель

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

Банк

Это объект, у которого можно взять денежные средства в займы под кредитный процент, а также вложить деньги под депозитный процент.

Алгоритм подсчета NPV инвестиционного портфеля

Проекты, которые не доходят до точки безубыточности ни в одном из трех вариантов, отбрасываются нами до начала алгоритма. В данной модели нами было сделано следующее допущение: у всех проектов ставка дисконтирования одна и та же (берется среднее по всем проектам). Это упрощает расчет NPV, при этом не на много ухудшая ее оценку.

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

Далее приведен данный алгоритм (рис. 2).

Рис. 2. Схема работы алгоритма

2.3 Модификация генетического алгоритма

В соответствии с задачей, операторы выбора родителя, мутации и рекомбинации были модифицированы под конкретную задачу.

Выбор родителей

Выбор родителя был осуществлен с помощью комбинации алгоритмов "Метод рулетки" и "Турнирный отбор".

В итоге оператор "выбор родителей" работает следующим образом:

1. Для каждой хромосомы подсчитывается целевая функция (в нашем случае значение NPV, способ подсчета которого был показан в главе 2.1)

2. На основе значения целевой функции рассчитывается пригодность хромосом. Она представляет собой вероятность выбора данной хромосомы (NPV хромосомы, деленная на сумму NPV всех хромосом в популяции)

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

4. Выбор особей для скрещивания происходит случайным образом.

Как можно заметить, чем больше NPV у хромосомы, тем выше ее пригодность, следовательно, тем чаще она будет выбираться.

Далее представлена блок-схема работы алгоритма выбора родителей. (Рис. 3)

Рис. 3. Блок-схема работы алгоритма выбора родителей

Рекомбинация

Для реализации данного алгоритма был выбран метод двухточечного кроссинговера. Он является подвидом многоточечного кроссинговера, описанного в главе 1.

В двухточечном кроссинговере хромосомы рассматриваются как циклы, которые формируются соединением концов линейной хромосомы. Для замены сегмента одного цикла сегментом другого цикла требуется выбор двух точек разреза. После выбора двух точек разреза происходит обмен наборами генов (2 набора) и создается два потомка.

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

Далее представлена блок-схема алгоритма рекомбинации. (Рис. 4)

Рис. 4. Блок-схема алгоритма рекомбинации

Отбор

Для создания новой популяции был использован "Элитарный отбор".

Элитарный отбор реализован следующим образом:

1. Создаётся промежуточная популяция, которая включает в себя как родителей, так и их потомков.

2. Оцениваются все члены этой популяции.

3. Из популяции выбираются N самых лучших (пригодных) хромосом, и они записываются в новую популяцию.

Далее представлена блок схема "Элитарного отбора". (Рис. 5)

Рис. 5 Блок - схема "Элитарного отбора"

Оператор мутации

В генетическом алгоритме была реализована мутация методом "Мутация для вещественных особей" для двух параметров. Шаг мутации был выбран равный 1 [20].

Вероятности задаются экзогенно. По умолчанию вероятность мутации хромосома равна 5 процентам, а вероятность мутации гена в нем при условии, что хромосома мутирует, 10 процентам [8, 20].

Далее представлена блок-схема генетического алгоритма (Рис. 6).

Рис. 6. Блок-схема генетического алгоритма

Изменение схемы работы генетического алгоритма

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

Программа запускалась 70 раз с последней модификацией и без нее, а также с равными количествами итераций в работе алгоритма.

В первом случае при количестве итераций, равным 20000-ам, программа выдавала каждый раз разный ответ, находящийся в промежутке от 10000000 до 12500000. Во втором случае при таком же количестве итераций и времени работы программа выдавала ответ, находящийся в промежутке от 13000000 до 13851593. Ответ, равный 13851593, без модификации схемы достигается при 80000 итераций. Как мы видим, во втором случае программа смогла найти максимум целевой функции лучше, чем в первый. Также можно заметить, что колебания ответов в первом случае намного выше, чем во втором. Это означает, что с помощью изменения схемы работы алгоритма мы смогли увеличить статичность выдаваемых им ответов.

Далее представлена блок-схема генетического алгоритма с модифицированной схемой (Рис. 7).

Рис. 7. Блок-схема генетического алгоритма модифицированной схемой



Выводы к главе 2

Во второй главе нами были представлены инструменты, с использованием которых производилось написание программы в рамках написания ВКР. Кроме того, нами были представлены обоснования использования именно этого набора инструментов. Была построена математическая модель расчёта суммарного NPV при взаимодействии с Банковским сектором. Также были показаны алгоритмы модификации операторов генетического алгоритма, необходимые для реализации задачи данной работы. Кроме того, нами была изменена схема работы генетического алгоритма и доказана эмпирическим путем ее эффективность для реализации данной задачи.



Глава 3. Реализация системы инвестиционной стратегии

3.1 Схема базы данных

Экзогенные данные взяты нами из базы данных и настроек пользователя в форме приложения. Далее представлена схема базы данных, взаимодействующая с приложением (Рис. 8).

Рис. 8. База данных

Как видно из рисунка, наша база находится в третьей нормальной форме и в данной базе присутствует 5 таблиц:

1. Таблица проекта (Project)

2. Таблица банка (Bank)

3. Таблица вариантов проекта (Project_var)

4. Таблица генов (Gene)

5. Таблица хромосом (Chromosome)

6. Таблица скрещивания таблиц хромосома, гена и проекта (Chromosome_proj_gene)

Источником данных для приложения являются таблицы проекта, вариантов проекта и банка.

Данные о лучших хромосомах из приложения записываются соответственно в таблицу хромосом, генов и Chromosome_proj_gene.

1 Описание таблиц

Project

Таблица проекта содержит всю дополнительную информацию о проекте. На данный момент в ней присутствует 2 атрибута:

1. Project_id - идентификационный ключ проекта (int)

2. Project_name - имя проекта (nvarchar)

Bank является таблицей, в которой записана информация о банках, с которыми можно проделывать операцию вклада и взятия кредита.

Атрибутами таблицы банка являются:

1. Bank_id - идентификационный ключ таблицы банка (int)

2. Bank_name - наименование банка (nvarchar)

3. Income_rate - депозитная процентная ставка (float)

4. Outcome_rate - кредитная процентная ставка (float)

Project_var

Данная таблица содержит в себе информацию о всех вариантах реализации каждого проекта.

Атрибутами таблицы являются:

Составной ключ:

1. Project_id(FK) - внешний ключ таблицы проекта (int)

2. Variant - вариант реализации проекта (1, 2 или 3) (int)

3. Year - год проекта (int)

Остальные атрибуты:

1. Income - полученный доход в этом году (float)

2. Outcome - затраты в этом году (float)

3. Comments - комментарии (nvarchar)

Chromosome_proj_gene

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

Составной ключ:

1. Project_id(FK) - внешний ключ таблицы проекта (int)

2. Gene_id(FK) - внешний ключ таблицы Gene (int)

3. Chromosome_id(FK) - внешний ключ таблицы Gene (int)

Chromosome может содержать в себе какую-то дополнительную информацию о хромосоме.

На данный момент в ней существует 2 атрибута:

1. Chromosome_id - идентификационный ключ хромосомы (int)

2. NPV - NPV хромосомы (int)

Gene

Атрибуты:

1. Bank_id - идентификационный ключ таблицы генов (int)

2. Timeofstart - год начала проекта (int)

3. Variant - вариант проекта (int)

Данные

Для тестирования программы таблицы были заполнены исходными данными.

Некоторые данные были заполнены нами в таблицу project_var (Рис. 9).

Рис. 9. Пример данных

3.2 Программная реализация

Хромосома в генетическом алгоритме представлена в виде двухмерного массива, где каждый столбец соответствует одному проекту, а строка - моменту времени. Значение, записанное в каждую ячейку, является планируемой суммой денежных средств, которые нужно вложить в данный проект в соответствующий год. Реализованная с помощью данного метода хромосома представляет собой один из множества вариантов портфолио нефтяной компании.

Для снижения сложности задачи с помощью методов объектно- ориентированного программирования хромосома была представлена в виде одномерного массива структуры данных с двумя элементами. Первый элемент показывает время начала проекта, а второй - вариант реализации данного проекта. Если вариант проекта в гене равен "0", это означает, что данный проект не участвует в портфолио. Реализованная данным способом хромосома не меняет сущности хромосомы, описанной выше, но намного уменьшает время работы программы.

Структура программы

Приложение состоит из шести windows forms и восьми классов. Так же в ней присутствуют элементы и классы, сгенерированные Microsoft C#.

Далее приведена структура программы (Рис. 10).

Рис. 10. Структура программы

Как следует из рисунка 10, в программе присутствует связь с базой данных. Данная связь была реализована благодаря технологии встроенных взаимодействий с локальной базой данных Microsoft SQL Server в Microsoft C#.

Далее представлены структура таблиц из базы данных в Microsoft C#.(Рис. 11)

Рис. 11 Таблицы, загруженные из базы в Microsoft C#

Данные в программе хранятся в виде экземпляров объектов. Благодаря свойствам объектно-ориентированного программирования классы объектов имеют иерархическую структуру, а данные в них могут иметь тип других объектов. Ниже представлено описание классов, в которых хранятся данные.

Variantproject

Класс, где хранится информация об одной реализации проекта. Он состоит из массивов доходов и расходов по годам, по проекту. Оба массива имеют тип List<double>

Gene

Является классом, где реализована структура Гена хромосомы. Оно состоит из двух атрибутов place и var. Значения атрибута place показывает время начала проекта, а атрибут var - вариант реализации.

Projectpr

Класс объектов, где хранится информация о проекте и о всех вариантах ее реализации. Состоит из трех атрибутов:

1. Var1 - является объектом класса variantproject и соответствует первому варианту реализации проекта.

2. Var2 - является объектом класса variantproject, где хранится информация о втором варианте реализации проекта.

3. Var3 - является объектом класса variantproject, в котором находятся данные о третьем варианте реализации проекта.

Chromosome

Является классом, где хранится структура одной хромосомы и метод подсчета его NPV. Так же в данном классе хранится статистический массив проектов, который имеет тип данных класса "Projectpr". В этот массив выгружается информация о проектах с локальной базы после приведения их в соответствующий вид.

Структура хромосомы реализована в виде массива из объектов класса Gene и атрибута npv типа double. При подобной реализации место гена в массиве показывает номер проекта.

Метод подсчета NPV реализован по алгоритму, предложенному в параграфе 2.1 (Рисунок 2).

Ekzogen

Класс, где хранятся экзогенные данные, вводимые пользователем, а также данные о банке.

В данном классе содержатся следующие переменные:

1. yr - количество лет, через которое нужно максимизировать суммарное NPV. (int)

2. d - ставка дисконтирования (double)

3. r - процентная ставка по кредиту (double)

4. vklad - количество начальных денег (double)

5. dep - депозитная ставка (double)

6. luch - лучшая хромосома (Chromosome)

7. iterat - количество итераций (int)

8. chromosomcount - количество хромосом в популяции

9. vergen - вероятность, с которой мутирует ген в хромосоме

10. verchrom - вероятность мутации хромосомы

Все переменные являются статистическими и имеют параметр public, что означает, что они доступны в любом месте программного кода.

Functions

Класс статистических вспомогательных методов.

В данном классе находятся методы:

Sortirovka - Данный метод написан с использованием стандартной сортировки в C#. Он имеет параметры static и public. Это означает, что он является статичным методом, который можно использовать из любой части программы. На его вход подаётся массив, состоящий из хромосом. Данный метод возвращает отсортированный массив в порядке убывания.

DoubleBinarySearch - Является статичным классом и также может быть вызван из любой части программы. Данный метод имеет следующие входные параметры: число и массив типа double. Метод находит первое число в массиве, которое не меньше заданного числа и возвращает его.

MaxiNPV - Как и предыдущие два метода, он также является статическим методом и имеет параметр public. На вход функции подаются следующие переменные: текущая популяция в виде массива из хромосом, лучшая хромосома в данной итерации и максимальное значение функции. Метод находит лучшую хромосому в популяции и сравнивает с лучшей особью из предыдущих итераций. В случае, если в популяции найдется особь значения npv которой превышает значения npv лучшей хромосомы, тогда лучшая особь в популяции заменяется найденной хромосомой. На выходе метод выдает максимальное суммарное NPV в данной итерации.

Далее приведена блок-схема метода "MaxiNPV" (рис. 11)

Рис. 11. Блок-схема метода "MaxiNPV"

Glavnoie

"Glavnoie" является начальной формой работы приложения. Класс "Glavnoie" является наследником встроенного в C# класса "Form". В этом классе находится тринадцать методов. Для интерактивного взаимодействия с пользователем в данном случае использовано многопоточное программирование. Оно реализовано в виде двух асинхронных потоков. Первый поток отвечает за скрепления частей генетического алгоритма и задания схемы ее работы в соответствии со схемой, показанной на рисунке 4. Второй поток, в свою очередь, отвечает за вывод информации пользователю на windows form. Кроме того, в данном классе реализован метод импортирования данных из локальной базы данных и их дальнейшее преобразование в нужной форме. Хромосома в программе имеет тип объекта "Chromosome", а популяция реализована в виде массива из этих хромосом.

Ниже приведен интерфейс формы "Glavnoie". (Рис. 12)

Рис. 12. Интерфейс формы Glavnoie.

Как видно из рисунка 8, в центральной части формы "Glavnoie" находятся график максимального суммарного NPV в зависимости от итераций и textbox с информацией о текущем квазимаксимуме целевой функции.

График реализован с помощью библиотеки ZedGraph. Он имеет вид кусочно постоянной функции. Шаг графика равен 0,01, что означает, что сто итераций соответствует шагу равному 1 по оси X. Ось Y на графике соответствует значению, равному максимальному суммарному NPV на данный момент, а ось X - количество итераций.

Далее приведен вид графика суммарного NPV во время работы приложения. (Рис. 13)

Рис. 13. График суммарного NPV.

В нижней части формы расположены следующие кнопки: Наилучшее портфолио, Начать и Остановить.

При нажатии на кнопку "Начать" программа начинает нахождение максимума целевой функции. Благодаря многопоточному программированию интерфейс программы не блокируется и можно в любой момент остановить ее работу нажатием кнопки "Остановить". При нажатии кнопки "Остановить" появляется сообщение, что работа программы была остановлена.

Далее можно увидеть всплывающее окно об остановке работы программы. (рис. 14)

Рис. 14. Сообщение о прекращении работы программы.

При завершении расчетов программы высвечивается сообщение об успешном завершении. (Рис. 15)

Рис. 15. Сообщение об успешном завершении программы

В случае если в работе программы произошла ошибка, то приложение сообщает пользователю об этом соответствующим сообщением.

Результат работы программы можно увидеть, нажав кнопку "Наилучшее портфолио", которая запускает Windows форму "Result".

В верхней части формы находится Меню. В меню находится 4 кнопки.

1. Файл - открывает список, в котором находятся кнопки и Выход.

a. Настройки ГА - осуществляет открытие формы "NastroikiGA"

b. Выход - осуществляет выход из программы с помощью встроенной функции "Close".

2. Данные - открывает форму "Dannie".

3. Настройки - открывает форму "Nastroiki".