Болдырев М. - Генезис в финансах. Выбор оптимальных путей
С задачами нахождения оптимальных решений мы сталкиваемся постоянно. В финансовом анализе и планировании это - формирование портфелей (оптимальное соотношение доходности и риска), составление бизнес-планов (оптимальная прибыль), реинжиниринг (оптимизация финансовых, товарных и т.п. потоков), управление динамическими системами... Список, естественно, можно продолжить.
В первом приближении задачи оптимизации можно решать существующими инструментальными средствами, встроенными в популярные в России табличные процессоры (вроде MS Excel). Но при нарастании объемов информационных потоков мы приходим к выводу, что скорость работы алгоритмов оптимизации неплохо бы повысить -как известно, процесс принятия оперативных решений связан с достаточно жесткими временными рамками.
Методы решения задачи.
Для задачи с двумя переменными можно построить некоторую плоскость (поверхность) возможных решений. При этом вертикальная координата здесь есть величина ошибки между значением искомого критерия (максимальное, минимальное, заданное значение) и вычесленными результатом. (см. Рис.
1).
Методы нахождения оптимальных решений можно разделить на три основные группы: прямой перебор, "градиентный спуск", случайный поиск.
В первом случае поиск оптимального решения сводится к перебору всех возможных значений для всех переменных и к сравнению полученного результата с известным критерием. Метод наиболее точный, но и наиболее медленный.
Метод "градиентного спуска" - разновидность направленного поиска в сторону уменьшения ошибки. Метод случайного поиска - наиболее быстрый, но наименее точный.
При всем разнообразии данных методов их недостаток - слишком большое время обработки данных (особенно при большом количестве переменных и/или сложной форме N-мерной абстрактной "поверхности") и , соответственно, большие вычислительные ресурсы, требуемые для решения подобных задач.
Преимущество генетических алгоритмов оптимизации.
В какой-то момент времени мы задаемся вопросом: а можно ли объединить достоинства всех методов ? То есть вести направленный поиск с элементами "случайных блужданий" ? При ближайшем рассмотрении мы обнаруживаем, что данный процесс наблюдается ... в природе. Это процесс генезиса.
Каждая популяция подвержена элементам отбора (условие выживания особей, наиболее приспособившихся к воздействию некоторых факторов), скрещивания (выживают особи, наследующие лучшие качества родителей) и мутации (некоторые особи приобретают новые качества, способствующие выживанию). То есть производится отбор из большого числа элементов по некоторому критерию.
Применительно к решению задачи оптимизации генетический алгортим представляет собой разновидность метода градиентного спуска, при котором исследование абстрактной "поверхности" возможных значений производится одновременно из множества исходных точек. То есть каждый шаг оптимизации - порождение множества точек, соответствующих различным комбинациям значений переменных.
Здесь же задается требуемый уровень скрещивания -наследования (параметр "crossover"), например 0.8 . То есть для каждой точки вычисляется отклонение текущего значения ошибки от заданного (fitness-функция) и следующий шаг оптимизации будет произведен из тех 80 % предыдущих точек, которые показали "лучший результат" в смысле минимизации ошибки. Остальные отбрасываются.
Таким же образом задается фактор мутации (mutation), например, 0.1 . То есть при каждом шаге оптимизации (новое поколение точек или популяция) в 10 % точек изменения значений соответствующих переменных будут проводиться по случайному закону. Поскольку каждое следующее поколение наследует лучшие признаки предыдущего (в данном случае -направления движения в сторону минимальной ошибки, причем с учетом периодических мутаций), то в конечном счете мы получаем некоторое подмножество точек, отклонение от целевой функции для которых минимально.
Процесс оптимизации для одной переменной показан на рис. 2. Обратим внимание на проблему локальных минимумов. На этом "спотыкается" градиентный спуск.
Но элемент случайного поиска как раз и позволяет находить решения, расположенные "ниже" локальных минимумов. Кстати, почему данный алгоритм работает быстро ? Процесс генерации множеств точек, их скрещивания и мутаций производится определенным образом. Множество возможных значений для каждой переменной кодируется (разными способами) в машинное слово длиной 8, 16 или 32 бита, каждому биту соответствует тот или иной диапазон значений.
Это машинной слово описано в литературе как хромосома. Все операции над хромосомой производятся как с одним целым, что существенно увеличивает скорость вычислений. Механизм наследования / скрещивания (crossover) производится над отдельными битами - генами (genes), то есть выделяются те гены, закодированные значения которых соответствуют уменьшению ошибки, то есть отклонения текущего значения от заданного.
Механизм мутации работает аналогично. В результате генезиса образуется хромосома, гены которой соответствуют лучшему значению минимальной ошибки.
После процедуры декодирования получаем подмножество значений, соответствующее субоптимальному решению задачи.
Необходимо отметить, что генетический алгоритм оптимизации является множественновероятностным, то есть позволяет находить множество значений, примерно соответствующих искомому условию. Это обстоятельство существенно для решения задач с неявно выраженными максимумами или минимумами.
Инструменты, использующие генетические алгоритмы.
Генетические алгоритмы оптимизации решений используются в пакетах Genetic Hunter фирмы WARD System и Evolver фирмы Axcelis. Пакеты сходны по конструкции и выполняемым функциям, поэтому рассмотрим их общие свойства и характеристики. Оба пакета предоставляют возможность автовыделения множества значений переменных, возможность задания ограничивающих условий в процессе оптимизации, возможность явного задания параметров скрещивания и мутации, возможность задания различных типов преобразования (кодирования) переменных, возможность задания различных типов целевой функции (минимум, максимум, значение), возможность задания параметров остановки процесса.
Пакет Evolver, кроме того, предоставляет возможность визуализации вычислений. Оба пакета рассчитаны на применение в составе программы Microsoft Excel, написаны на языке Visual Basic for applications (VBA) и представляют собой один или несколько файлов-приложений Excel (*.xla), которые отвечают за работу интерфейса Excel, а также наборов библиотек *.dll, и файлы Excel *.xls, содержащие демонстрационные примеры.
Стоит отметить, что пакет Genetic Hunter при установке предлагает работу в 16-битном варианте в среде Excel 5 for Windows 3.* или в 32-битном варианте в среде Excel 7.0 for Windows 95. Попытки установить под Windows 95 пакет Evolver успехом не оканчиваются. Пакет Genetic Hunter входит в состав системы AI Trilogy, поэтому имеет средства для разработки отторгаемых приложений и интеграции их в состав разрабатываемых систем. Встроенные функции детально описаны в руководстве.
Пакет Evolver также имеет инструмент для разработки приложений Developer Kit.
Опыт применения.
В практическом применении известны примеры решени задач формирования опимальных портфелей, нахождения оптимальных комбинаций решающих правил для принятия решения в управлении финансовыми ресурсами, весьма положительные результаты достигаются при использовании генетической оптимизации в процессах настройки нейросетей для оценок и прогнозов в финанссовом анализе. Во многом генетические оптимизационные алгоритмы как частный случай в круге задач искусственного интелекта - явление достаточно новое применительно к финансовым задачам, поэтому вызывает множество вопросов, но, тем не менее, предоставляет обширное поле деятельности для финансовых аналитиков и экспертов.
