Статьи по экономическим темам

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

С. М. БАБУР, асп., Київський національний економічний університет

Останнім часом генетичні алгоритми набули широкої популярності та використовуються в багатьох сферах людської діяльності, насамперед в економічній. У фінансовій сфері вони застосовуються в основному в двох напрямах — це задачі прогнозування (курсів фінансових інструментів, цін на ресурси, попиту, доходу компанії) та задачі оптимізації (розкладу, маршрутів, плану інвестицій, стратегії розвитку).

Основи генетичних алгоритмів розроблені Джоном Холландом в 1960 р. Генетичні алгоритми основані на штучному інтелекті та пропонують математичну імітацію адаптивного процесу біологічного феномена, комбінуючи виживання сильніших індивідуумів у популяції зі структурованим випадковим інформаційним обміном. Основа функціонування генетичних алгоритмів досить проста: спочатку формується популяція можливих рішень проблеми, потім кращі рішення рекомбінуються між собою для формування кращих рішень, наостанок нові рішення замінюють менш придатні початкові рішення і процес повторюється знову.

У простих генетичних алгоритмах потенційне рішення представлено послідовністю двійкових чисел, що називаються хромосомою. Потенціал хромосоми, як рішення, оцінюється за допомогою функції еволюції. Множина хромосом називається популяцією, а популяція в часі — поколінням. Розмір популяції залишається незмінним від покоління до покоління і значно впливає на роботу генетичного алгоритму. Фундаментальний механізм генетичного алгоритму складається з трьох основних операцій: репродукції (вибір копій хромосом згідно із значенням їх придатності), наслідування (обмін частинами хромосом), мутації (випадкова модифікація хромосом). Хромосоми, одержані в результаті цих трьох операцій, називаються нащадками, або дітьми, і формують наступні покоління. Репродукція робить копію індивідуума з одного покоління в наступне, наслідування комбінує ознаки двох і більше батьків для одного і більше дітей, мутація викликає незначні локальні зміни. Репродукція та наслідування сильних індивідуумів забезпечує покращання або погіршання, мутація підтримує різноманітність популяції і дає змогу вести подальші дослідження. Кожний індивідуум входить до наступного покоління згідно з його придатністю. Пошук проводиться в послідовності поколінь. Процес ітерацій повторюється бажану кількість разів.

При розв’язанні конкретної задачі еволюція генетичного алгоритму включає прийняття рішень двох типів. Рішення першого типу моделюють задачу, придатну для використання структури генетичного алгоритму, при якій задається область допустимих значень, форма функції еволюції, спосіб представлення індивідуумів у вигляді рядка. При прийнятті рішення другого типу задаються параметри генетичного алгоритму: пропорція популяції, яку дістаємо при відтворенні; наслідування; мутація; процедура відбору; розмір популяції; число поколінь.

Базовий генетичний алгоритм може бути представлений схемою, наведеною на рис. 1.

 Блок-схема базового генетичного алгоритму

Рис. 1. Блок-схема базового генетичного алгоритму

Розглянемо основні кроки базового генетичного алгоритму згідно з наведеною схемою.

Запис (репрезентація). Першим кроком застосування генетичних алгоритмів для розв’язування задач оптимізації є вибір способу запису задачі. Для представлення комбінаторних задач мож­на використовувати суміжний запис, запис з перестановками, порядковий запис, запис у вигляді матриці переваг. Розв’язок задачі може бути представлено у вигляді бінарного рядка.

Ініціалізація. Наступний важливий крок у створенні генетичного алгоритму — ініціалізація популяції або створення початкової популяції. Процес ініціалізації створює випадкову або добре адаптовану популяцію.

Функція еволюції. Різноманітні характеристики функції еволюції покращують чи погіршують ефективність функціонування генетичного алгоритму. Ефективність функціонування генетичного алгоритму залежить від значення цільової функції. Значення цільової функції використовується для вибору батьків для наслідування. Важливо вибрати шкалу значень функції еволюції таким чином, щоб популяція була різноманітною.

Рекомбінація операторів. У задачах перестановки використовується рекомбінація операторів, що комбінують риси інверсії та наслідування. Наприклад, часткове парне наслідування, порядкове наслідування та кругове наслідування.

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

Формулювання задачі. Є в наявності інвестиційний капітал, який необхідно розподілити серед n проектів. Для кожного проекту задано функцію залежності прибутку від обсягу вкладення. Необхідно знайти найбільш прибутковий варіант розподілення капіталу за умови, що задані максимальний та мінімальний об’єми інвестицій для кожного проекту.

Традиційне рішення. Найчастіше рішення в такому разі приймає керівник, базуючись на особистих враженнях від проектів. Розміри втраченого прибутку при цьому не підраховують, і неоптимальне рішення може залишитися невиявленим. У випадку, коли керівник дає доручення своїм аналітикам вибрати найбільш прибутковий варіант, застосовуються математичні методи оптимізації. Якщо всі дані функції лінійні, то можна застосувати методи лінійного програмування. Якщо хоча б одна функція нелінійна, то можна застосувати метод градієнтного спуску або повного перебору.

Розглянемо деякі проблеми, що виникають при розв’язанні задачі оптимального розподілення інвестицій:

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

2. Детермінований алгоритм для пошуку оптимального рішення (симплекс-метод) застосовується тільки в тому разі, коли всі дані функції лінійні. В реальних задачах бізнесу ця умова не виконується. Хоча ці функції можна апроксимувати лінійними, але рішення в такому випадку буде далеким від оптимального.

3. Якщо одна з функцій нелінійна, то симплекс-метод застосувати неможливо, залишаються два традиційних шляхи розв’язання цієї задачі. Перший шлях — використати метод градієнтного спуску для пошуку максимуму прибутку. В даному випадку область визначення функції прибутку має складну форму, а сама функція — декілька локальних максимумів і тому градієнтний метод може призвести до неоптимального рішення. Другий шлях — провести повний перебір варіантів інвестування. Якщо кожна із 10 функцій задана в 100 точках, то перевірка всіх варіантів потребує не менше декількох місяців роботи сучасного комп’ютера.

Статистичні методи розв’язання подібних практичних задач добре розроблені тільки для одномірних випадкових величин. Якщо ж необхідно враховувати, наприклад, для прогнозування курсу акцій декілька взаємопов’язаних факторів (наприклад, курс долара, обсяг угод), то доведеться вдаватися до побудови багатомірної статистичної моделі. Однак такі моделі або допускають гаусівський розподіл спостережень, що не виконується на практиці, або не обґрунтовані теоретично. В багатомірній статистиці за відсутністю кращого нерідко застосовують малообґрунтовані евристичні методи, які за своєю суттю близькі до технології генетичних алгоритмів і нейронних мереж.

Розглянемо особливості реалізації генетичного алгоритму у разі оптимального розподілення інвестицій.

Індивідуум = варіант рішення задачі = набір із 10 хромосом Хj.

Хромосома Хj = обсяг вкладень у проект j = 16-розрядний запис цього числа. Оскільки обсяги вкладень обмежені, то не всі значення хромосом є допустимими. Це враховується при генерації популяцій. Оскільки сумарний обсяг інвестицій фіксований, то реально змінюються тільки дев’ять хромосом, а значення десятої визначається по них однозначно.

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

Квадратами на графіках прибутку позначено, який обсяг вкладень у даний проект рекомендовано генетичним алгоритмом. На рис. 2 капітальні вкладення дорівнюють 500 од., прибуток дорівнює 1391,18 од. Видно, що при малому значенні капітальних вкладень інвестуються тільки ті проекти, які прибуткові при мінімальних вкладеннях.

Результати роботи генетичного алгоритму: капітальні вкладення = 500 од., прибуток = 1391,18 од.

Рис. 2. Результати роботи генетичного алгоритму: капітальні вкладення = 500 од., прибуток = 1391,18 од.

На рис. 3 видно, що якщо збільшувати сумарний обсяг інвестицій, то стає прибутковим вкладати кошти в більш дорогі проекти.

Результати роботи генетичного алгоритму: капітальні вкладення = 2500 од., прибуток = 4413,82 од.

Рис. 3. Результати роботи генетичного алгоритму: капітальні вкладення = 2500 од., прибуток = 4413,82 од.

На рис. 4 видно, що при подальшому збільшенні K досягається поріг максимального вкладення в прибуткові проекти і тому інвестування малоприбуткових проектів знову має сенс.

Результати роботи генетичного алгоритму: капітальні вкладення = 4000 од., прибуток = 5725,60 од.

Рис. 4. Результати роботи генетичного алгоритму: капітальні вкладення = 4000 од., прибуток = 5725,60 од.

Розглянемо генетичний алгоритм, застосований для розв’язу­вання задачі розміщення інвестицій на комбінаті «Азовсталь», м. Маріуполь.

Для пошуку оптимального рішення адаптований генетичний алгоритм робить дев’ять кроків:

1. Генерація початкової множини n' пробних рішень. Якщо деяке рішення має придатність, що дорівнює 0, то переходимо до кроку 9, інакше — до кроку 2.

2. Виберемо два рішення P та Q, використовуючи бінарну турнірну селекцію, t = 0.

3. Генеруємо нове пробне рішення С, використовуючи оператор злиття.

4. Виберемо nbits із рядка бітів С, де nbits визначається коефіцієнтом мутації, що змінюється.

5. Якщо придатність С дорівнює 0, то переходимо до кроку 9, інакше — до кроку 6.

6. Якщо С дорівнює пробному рішенню, то переходимо до кроку 2, інакше — t = t + 1 і переходимо до кроку 7.

7. Замінюємо вибране випадковим чином пробне рішення зі значенням придатності меншим, ніж у С, на С.

8. Якщо t = m', то вибираємо рішення з найменшим значенням придатності, інакше повторюємо кроки 2—7.

9. Фінальний крок після завершення генетичної фази: покращання рішення з використанням двохфазового локального пошуку.

Задача оптимізації розподілення інвестицій по декількох проектах, коли проекти неможливо поділити, записується в такому вигляді:

за умови:

де: z — сумарний чистий приведений ефект (NPV);

pijNPV від включення i-го проекту до j-ї інвестиційної програми;

xij — рішення про включення i-го проекту до j-ї інвестиційної програми;

wij — обсяг необхідних інвестицій при включенні і-го проекту до j-ї інвестиційної програми;

ci — обсяг інвестиційних ресурсів по і-й інвестиційній програмі.

При цьому NPV розраховується за формулою

,

де: множина р1, р2, …, рk — річні доходи,

r — норма дохідності.

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

По закінченні роботи генетичного алгоритму використовується метод локального пошуку. Метод локального пошуку складається з двох фаз. Нехай (i = 1, 2, 3, …, m; j = 1, 2, 3, …, n) — рішення, представлене у вигляді n-бітного рядка (i1, i2, …, in), в якому для кожного іk виконується умова: = 1, = 0 (i ¹ іk).

Перша фаза: перевірка рішення на оптимальність.

Якщо ¹ для кожного і, на кожному кроці перевірки j' = 1, 2, … n, тоді якщо j' заміна на для кожного і М дає допустиме рішення, то заміна виконується, і = для кожного і М.

Друга фаза: покращання вибором із пари рішень.

Виберемо пару (j', j'') таку, що j' (1, 2, … n1), j'' (2, 3, … n), j' < j''. Нехай для вибраних j' та j'' виконуються умови та .

Якщо виконуються умови:

та

,

тоді , , , . Продовжимо для кожної пари (j', j''). Задача не має допустимих значень, якщо після завершення другої фази не було знайдено оптимального рішення.

Отже, генетичний алгоритм зарекомендував себе життєздатним методом оптимізації, придатним для розв’язування задач розміщення.

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

1. Гнатушенко В. В., Лысенко Ю. Г., Петренко В. Л., Юханов Д. А. Моделирование процессов инвестиционной деятельности с использованием генетических алгоритмов. — Донецк: ИЭП НАН Украины, 1998. — 30 с.

2. Вороновский Г. К., Махотило К. В., Петрашев С. Н., Сергеев С. А. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. — Харьков: Основа, 1997. — 111 с.

3. Шарп Уильям Ф., Гордон Дж. Александр, Бэйли Джеффри В. Инвестиции. — М.: Инфра-М, 1998. — 1024 с.

4. HTTP // www. neuroproject. ru. Аналитические технологии для прогнозирования и анализа данных.

Добавить комментарий


Защитный код
Обновить