Самооптимизация экспертов: Эволюционные и генетические алгоритмы

Vladimir Perervenko | 20 апреля, 2016

Содержание



Введение

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

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



1. История появления эволюционных алгоритмов

История эволюционных вычислений началась с разработки ряда различных независимых моделей. Основными из них были генетические алгоритмы и классификационные системы Голланда (Holland), опубликованные в начале 60-х годов и получившие всеобщее признание после выхода в свет книги, ставшей классикой в этой области, — "Адаптация в естественных и искусственных системах" ("Adaptation in Natural and Artifical Systems", 1975). В 70-х годах в рамках теории случайного поиска Л.А. Растригин предложил ряд алгоритмов, использующих идеи бионического поведения особей. Развитие этих идей нашло отражение в цикле работ И.Л. Букатовой по эволюционному моделированию. Развивая идеи М.Л. Цетлина о целесообразном и оптимальном поведении стохастических автоматов, Ю.И. Неймарк предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов, моделирующих процессы развития и элиминации особей. Большой вклад в развитие эволюционного программирования внесли Фогел (Fogel) и Уолш (Walsh). Несмотря на разницу в подходах, каждая из этих "школ" взяла за основу ряд принципов, существующих в природе, и упростила их до такой степени, чтобы их можно было реализовать на компьютере.

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

Конечно, на практике мы не можем разделять эти вещи так строго. Эти категории — просто два полюса, между которыми лежат различные вычислительные системы. Ближе к первому полюсу — эволюционные алгоритмы, например, Эволюционное Программирование (Evolutionary Programming), Генетические Алгоритмы (Genetic Algorithms) и Эволюционные Стратегии (Evolution Strategies). Ближе ко второму полюсу располагаются системы, которые могут быть классифицированы как Искусственная Жизнь (Artificial Life).



2. Эволюционные алгоритмы (методы)

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

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

Эволюционные методы (ЭМ) — приближенные (эвристические) методы решения задач оптимизации и структурного синтеза. Большинство ЭМ основано на статистическом подходе к исследованию ситуаций и итерационном приближении к искомому решению.

Эволюционные вычисления составляют один из разделов искусственного интеллекта. При построении систем ИИ по данному подходу основное внимание уделяется построению начальной модели и правилам, по которым она может изменяться (эволюционировать). При этом модель может быть составлена по самым различным методам. Например, это может быть и нейронная сеть, и набор логических правил. К основным эволюционным методам относятся методы отжига, генетические, поведения "толпы" (PSO), колонии муравьев (ACO), генетического программирования.

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

В методе отжига (Simulated Annealing) имитируется процесс минимизации потенциальной энергии тела во время отжига деталей. В текущей точке поиска происходит изменение некоторых управляемых параметров. Новая точка принимается всегда при улучшении целевой функции и лишь с некоторой вероятностью — при ее ухудшении.

Важнейшим частным случаем ЭМ являются генетические методы и алгоритмы. Генетические алгоритмы (ГА) основаны на поиске лучших решений с помощью наследования и усиления полезных свойств множества объектов определенного приложения в процессе имитации их эволюции.

Свойства объектов представлены значениями параметров, объединяемых в запись, называемую в ЭМ хромосомой. В ГА оперируют подмножеством хромосом, называемым популяцией. Имитация генетических принципов — вероятностный выбор родителей среди членов популяции, скрещивание их хромосом, отбор потомков для включения в новые поколения объектов на основе оценки целевой функции. Этот процесс ведет к эволюционному улучшению значений целевой функции (функции полезности) от поколения к поколению.

Среди ЭМ находят применение также методы, которые, в отличие от ГА, оперируют единственной хромосомой, а не их множеством. Так, метод дискретного локального поиска (его англоязычное название Hillclimbing) основан на случайном изменении отдельных параметров (значений полей в записи или, другими словами, значений генов в хромосоме). Такие изменения называют мутациями. После очередной мутации оценивают значение функции полезности F (Fitness Function). Результат мутации сохраняется в хромосоме только если F улучшилась. При "моделировании отжига" результат мутации сохраняется с некоторой вероятностью, зависящей от полученного значения .

В методе PSO (Particles Swarm Optimization) имитируется поведение множества агентов, стремящихся согласовать свое состояние с состоянием наилучшего агента.

Метод колонии муравьев (ACO) основан на имитации поведения муравьев, минимизирующих длину своих маршрутов на пути от муравейника до источника пищи.



3. Генетические алгоритмы (ГА)

Генетические Алгоритмы — адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной оптимизации. Они основаны на генетических процессах биологических организмов: биологические популяции развиваются на протяжении нескольких поколений, подчиняясь законам естественного отбора и принципу "выживает наиболее приспособленный" (survival of the fittest), открытому Чарльзом Дарвином. Подражая этому процессу, генетические алгоритмы способны "развивать" решения реальных задач, если те соответствующим образом закодированы.

В природе особи в популяции конкурируют друг с другом за различные ресурсы — такие, например, как пища или вода. Кроме того, члены популяции одного вида часто конкурируют за привлечение брачного партнера. Особи, которые наиболее приспособлены к окружающим условиям, будут иметь относительно больше шансов воспроизвести потомков. Слабо приспособленные особи либо совсем не произведут потомства, либо оно будет немногочисленным. Это означает, что гены от хорошо адаптированных особей будут распространяться в увеличивающемся количестве потомков в каждом последующем поколении. Комбинация удачных характеристик от разных родителей иногда может приводить к появлению "суперприспособленного" потомка, чья адаптированность больше, чем у любого из его родителей. Таким образом, вид развивается, всё лучше и лучше приспосабливаясь к среде обитания.

ГА используют прямую аналогию с таким механизмом. Они работают с совокупностью "особей" — популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее "приспособленности" в соответствии с тем, насколько "хорошо" соответствующее ей решение задачи.  Наиболее приспособленные особи получают возможность "воспроизводит" потомство с помощью "перекрестного скрещивания" с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции.

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

Имеются разные способы реализации идеи биологической эволюции в рамках ГА.



3.1. Область применения

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

Однако нередки случаи, когда ГА работает не так эффективно, как ожидалось.

Предположим, есть реальная задача, сопряженная с поиском оптимального решения. Как узнать, подходит ли для этого ГА? Строго ответа на этот вопрос до настоящего времени еще не получено. Однако многие исследователи разделяют предположения о том, что ГА имеет хорошие шансы стать эффективной процедурой поиска в следующих случаях:

Иными словами, в ситуациях, когда нужно быстро и просто найти приемлемое "хорошее" решение (что довольно часто имеет место в реальных задачах), ГА конкурирует и превосходит другие методы, которые не используют знания о пространстве поиска.

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

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

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



3.2. Решаемые задачи

Генетические алгоритмы применяются для решения следующих задач:


3.3. Классический ГА

Работа простого ГА

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

Сначала пропорциональный отбор назначает каждой структуре вероятность Ps(i), равную отношению ее приспособленности к суммарной приспособленности популяции. 

Затем происходит отбор (с замещением) всех n особей для дальнейшей генетической обработки, согласно величине Ps(i). Простейший пропорциональный отбор — рулетка (roulette-wheel selection, Goldberg, 1989c) — отбирает особей с помощью n "запусков" рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален соответствующей величине Ps(i). При таком отборе более приспособленные члены популяции с большей вероятностью будут чаще выбираться, чем особи с низкой приспособленностью.

После отбора n выбранных особей подвергаются кроссоверу (иногда называемому рекомбинацией) с заданной вероятностью Pc. n строк случайным образом разбиваются на n/2 пары. Для каждой пары с вероятностью Pc может применяться кроссовер. Соответственно, с вероятностью 1-Pc кроссовер не происходит, и неизмененные особи переходят на стадию мутации. Если кроссовер происходит, полученные потомки заменяют собой родителей и переходят к мутации.

Одноточечный кроссовер работает следующим образом. Сначала случайным образом выбирается одна из l-1 точек разрыва. (Точка разрыва — участок между соседними битами в строке.) Обе родительские структуры разрываются на два сегмента по этой точке. Затем соответствующие сегменты различных родителей склеиваются, и получаются два генотипа потомков.

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

В настоящее время исследователи ГА предлагают множество других операторов отбора, кроссовера и мутации. Вот лишь наиболее распространенные из них. Прежде всего, турнирный отбор (Brindle, 1981; Goldberg и Deb, 1991). Турнирный отбор реализует n турниров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с k=2.

Элитные методы отбора (De Jong, 1975) гарантируют, что при отборе обязательно будут выживать лучший или лучшие члены популяции совокупности. Наиболее распространена процедура обязательного сохранения только одной лучшей особи, если она не прошла, как другие через процесс отбора, кроссовера и мутации. Элитизм может быть внедрен практически в любой стандартный метод отбора.

Двухточечный кроссовер (Cavicchio, 1970; Goldberg, 1989c) и равномерный кроссовер (Syswerda, 1989) — вполне достойные альтернативы одноточечному оператору. В двухточечном кроссовере выбираются две точки разрыва, и родительские хромосомы обмениваются сегментом, который находится между двумя этими точками. В равномерном кроссовере каждый бит первого родителя наследуется первым потомком с заданной вероятностью; в противном случае этот бит передается второму потомку. И наоборот.

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

Оператор отбора (селекции)

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

Оператор скрещивания

Чаще всего скрещивание производят над двумя лучшими особями. Результатом обычно являются две особи с компонентами, взятыми от их "родителей". Цель этого оператора — распространение "хороших" генов по популяции и стягивание плотности популяции к тем областям, где она и так велика в том предположении, что "нас много там, где хорошо".

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

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

Критерии останова



3.4. Стратегии поиска

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

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



3.5. Отличие от классического поиска оптимума

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

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

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

Хотя модель эволюционного развития, применяемая в ГА, сильно упрощена по сравнению со своим природным аналогом, тем не менее, ГА является достаточно мощным средством и может с успехом применяться для широкого класса прикладных задач, включая те, которые трудно, а иногда и вовсе невозможно решить другими методам. Однако, ГА, как и другие методы эволюционных вычислений, не гарантируют обнаружения глобального решения за полиномиальное время. Не гарантируют они и того, что глобальное решение вообще будет найдено. Однако генетические алгоритмы хороши для поиска "достаточно хорошего" решения задачи "достаточно быстро". Там, где задача может быть решена специальными методами, почти всегда такие методы будут эффективнее ГА и в быстродействии и в точности найденных решений. Главным же преимуществом ГА-мов является то, что они могут применяться даже на сложных задачах, там, где не существует никаких специальных методов. Даже там, где хорошо работают существующие методики, можно достигнуть улучшения сочетанием их с ГА.



3.6. Терминология ГА

Поскольку ГА происходят как из естественных наук (генетика), так и из компьютерных, то используемая терминология представляет собой сплав естественного и искусственного. Соответствие терминов, относящихся к ГА, и тех, которые относятся к решению оптимизационных проблем, приведено в табл. 1.1.

Таблица 1.

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

                             Объяснение                        
 Хромосома
  Вариант решения (набор параметров)
 Гены
  Параметры, которые оптимизируются
 Локус (положение)
  Позиция гена в хромосоме 
 Аллель
  Значение гена
 Фенотип
  Раскодированное решение
 Генотип
  Закодированное решение


Классический (одноточечный) кроссинговер.

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

Двухточечный кроссинговер.

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

Унифицированный (однородный) кроссинговер.

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

Дифференциальное скрещивание.

Помимо кроссовера, существуют и другие методы скрещивания. Например, для поиска минимума/максимума функции многих вещественных переменных наиболее удачным является "дифференциальное скрещивание". Вкратце опишем его суть. Пусть a и b  — это два индивидуума в популяции, т.е., вещественные вектора от которых зависит наша функция. Тогда потомок c вычисляется по формуле с=a+k*(a-b), где k —это некоторый вещественный коэффициент (который может зависить от ||a-b|| — растояния между векторами).
В этой модели мутация — это добавление к индивидууму случайного вектора малой длины. Если исходная функция непрерывна, то эта модель работает хорошо. А если она еще и гладкая, то и вовсе превосходно.

Инверсия и переупорядочение.

Часто порядок генов в хромосоме является критическим для строительных блоков, позволяющих осуществлять эффективную работу алгоритма. Были предложены методы для переупорядочения позиций генов в хромосоме во время работы алгоритма. Одна из таких методик — инверсия, выполняющая реверсирование порядка генов между двумя случайно выбранными позициями в хромосоме. (Когда используются эти методы, гены должны содержать некоторую "метку", так, чтобы их можно было правильно идентифицировать независимо от их позиции в хромосоме.)
Цель переупорядочения состоит в том, чтобы попытаться найти порядок генов, который имеет лучший эволюционный потенциал. Многие исследователи использовали инверсию в своей работе, хотя кажется, что немногие попытались ее обосновать или определить ее вклад. Goldberg & Bridges анализируют оператор переупорядочения на очень маленькой задаче, показывая, что она может дать определенное преимущество, хотя они заключают, что их методы не принесли бы то же самое преимущество на больших задачах.
Переупорядочение также значительно расширяет область поиска. Мало того, что генетический алгоритм пытается находить хорошие множества значений генов, он также одновременно пробует находить их "правильное" упорядочение. Это гораздо более трудная задача для решения.

Что такое эпистаз?

Термин "эпистаз" в генетике определяется как влияние гена на пригодность индивидуума в зависимости от значения гена, присутствующего в другом месте. Иными словами, генетики используют термин "эпистаз" в смысле эффекта "переключения" или "маскирования": "Ген считают эпистатическим, когда его присутствие подавляет влияние гена в другом локусе. Эпистатические гены иногда называют ингибирующими из-за их влияния на другие гены, которые описываются как гипостаз".
В терминологии ГА это может звучать так: "Приспособленность особи зависит от взаимного расположения хромосом в генотипе".

Что такое ложный оптимум?

Одним из фундаментальных принципов генетических алгоритмов является то, что хромосомы, включенные в шаблоны, содержащиеся в глобальном оптимуме, увеличиваются по частоте. Особенно это верно для коротких шаблонов небольшого порядка, известных как строительные блоки. В конечном счете при кроссинговере эти оптимальные шаблоны сойдутся, и будет создана глобальная оптимальная хромосома. Но если шаблоны, которые не содержатся в глобальном оптимуме, будут увеличиваться по частоте быстрее, чем другие, то генетический алгоритм будет введен в заблуждение и уйдет в другую сторону от глобального оптимума, вместо того, чтобы приблизиться к нему. Это явление известно как ложный оптимум.
Ложный оптимум — частный случай эпистаза, и он был глубоко изучен Goldberg и другими. Ложный оптимум непосредственно связан с вредными влияниями эпистаза в генетических алгоритмах.
По статистике, шаблон увеличится по частоте в популяции, если его пригодность выше, чем средняя пригодность всех шаблонов в популяции. Задача обозначается как задача ложного оптимума, если средняя пригодность шаблонов, которые не содержатся в глобальном оптимуме, больше, чем средняя пригодность других шаблонов.
Задачи ложного оптимума трудны для решения. Однако, Grefenstette остроумно демонстрирует, что они возникают не всегда. После первого поколения генетический алгоритм не получает объективную выборку точек в области поиска. Поэтому он не может оценивать объективную глобальную среднюю пригодность шаблона. Он способен только получить необъективную оценку пригодности шаблона. Иногда это предубеждение помогает генетическому алгоритму сходиться (даже при том, что задача иначе могла бы иметь сильный ложный оптимум).

Что такое инбридинг, аутбридинг, селективный выбор, панмиксия?

Существует несколько подходов к выбору родительской пары. Наиболее простой из них — панмиксия. Этот подход предполагает случайный выбор родительской пары, когда обе особи, которые составят родительскую пару, случайным образом выбираются из всей популяции. В этом случае любая особь может стать членом нескольких пар. Несмотря на простоту, такой подход универсален для решения различных классов задач. Однако он достаточно критичен к численности популяции, поскольку эффективность алгоритма, реализующего такой подход, снижается с ростом численности популяции.
Селективный способ выбора особей в родительскую пару состоит в том, что "родителями" могут стать только те особи, значение приспособленности которых не меньше среднего значения приспособленности по популяции, при равной вероятности таких кандидатов составить брачную пару.
Такой подход обеспечивает более быструю сходимость алгоритма. Однако из-за быстрой сходимости селективный выбор родительской пары не подходит тогда, когда ставится задача определения нескольких экстремумов, поскольку для таких задач алгоритм, как правило, быстро сходится к одному из решений. Кроме того, для некоторого класса задач со сложным ландшафтом приспособленности быстрая сходимость может превратиться в преждевременную сходимость к квазиоптимальному решению. Этот недостаток может быть отчасти компенсирован использованием подходящего механизма отбора, который бы "тормозил" слишком быструю сходимость алгоритма.
Инбридинг представляет собой такой метод, когда первый член пары выбирается случайно, а вторым с большей вероятностью будет максимально близкая к нему особь.
При аутбридинге также используют понятие схожести особей. Однако теперь брачные пары формируют из максимально далеких особей.
Последние два способа по-разному влияют на поведение генетического алгоритма. Так, инбридинг можно охарактеризовать свойством концентрации поиска в локальных узлах, что фактически приводит к разбиению популяции на отдельные локальные группы вокруг подозрительных на экстремум участков ландшафта. Аутбридинг же направлен на предупреждение сходимости алгоритма к уже найденным решениям, заставляя алгоритм просматривать новые, неисследованные области.

Динамическая самоорганизация параметров ГА

Зачастую выбор параметров генетического алгоритма и конкретных генетических операторов производится на интуитивном уровне, поскольку пока не существует объективных доказательств преимущества тех или иных настроек и операторов. Однако не нужно забывать, что сама суть ГА заключается в динамике и "мягкости" алгоритма и производимых вычислений. Тогда почему бы не позволить алгоритму самому настраиваться во время решения задачи и адаптироваться к ней?
Проще всего организовать адаптацию применяемых операторов. Для этого встроим в алгоритм несколько (чем больше, тем лучше) различных операторов выборки (элитная, случайная, рулеточная,..), кроссинговера (одноточечный, двухточечный, унифицированный,..) и мутации (случайная одноэлементная, абсолютная,..). Установим для каждого оператора равные вероятности применения. Далее на каждом цикле алгоритма будем выбирать один из операторов каждой группы (выбор, кроссинговер, мутация) в соответствии с вероятностным распределением. При этом в полученной особи отметим, с помощью какого именно оператора она была получена.  Тогда, если новое распределение вероятностей мы вычислим исходя из информации, содержащейся в популяции (вероятность применения оператора пропорциональна числу особей в популяции, полученных при помощи этого оператора), то генетический алгоритм получит механизм динамической самоадаптации.
Такой подход дает еще одно преимущество: теперь не нужно беспокоиться о применяемом генераторе случайных чисел (линейный, экспоненциальный и т.д.), поскольку алгоритм динамически изменяет характер распределения.

Метод миграции и искусственной селекции

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

Метод прерывистого равновесия

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



4. Преимущества ГА

Есть два главных преимущества генетических алгоритмов перед классическими оптимизационными методиками.

1. ГА не имеет значительных математических требований к видам целевых функций и ограничений. Исследователь не должен упрощать модель объекта, теряя ее адекватность, и искусственно добиваясь возможности применения доступных математических методов. При этом могут использоваться самые разнообразные целевые функции и виды ограничений (линейные и нелинейные), определенные на дискретных, непрерывных и смешанных универсальных множествах.

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

Менее глобальные, но тоже важные преимущества ГА:



5. Недостатки ГА



6. Экспериментальная часть

Все эксперименты мы будем проводить в среде языка R 3.2.4. Используем набор данных для обучения модели и большинство функций из предыдущей статьи.

Задачам оптимизации и математического программирования посвящен раздел депозитария CRAN, который содержит большое количество пакетов, предназначенных для их решения. Мы применим несколько различных методов ГА и ЭМ для решения задач, перечисленных ниже. Требование к моделям, которые участвуют в процессе оптимизации, только одно — быстродействие. Применять модели, которые обучаются в течение сотни секунд, нежелательно. С учетом того, что в каждом поколении будет минимум 100 особей, а популяция пройдет через ряд (от единиц до десятков) эпох, процесс оптимизации затянется на неприемлемое время. В предыдущих статьях мы применяли два вида глубоких сетей (с инициализацией SAE и RBM). Обе показали высокое быстродействие и вполне могут использоваться при генетической оптимизации.

Мы будем решать две задачи оптимизации: поиск лучшей комбинации предикторов и выбор оптимальных параметров индикаторов.  Для решения первой (выбор предикторов) мы с целью осваивания новых алгоритмов  применим часто упоминаемый в последнее время алгоритм XGBoost(Extreme Gradient Boosting). По упоминаниям в источниках, он показывает очень хорошие результаты в задачах классификации. Алгоритм доступен для языков R, Python, Java. В языке R этот алгоритм реализован в пакете “xgboost” v. 0.4-3.

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

6.1. Поиск лучшей комбинации предикторов

Для решения задачи оптимизации любым методом необходимо определить:

Фитнес-функция в нашем случае будет выполнять последовательно:

Критерием оптимизиции могут быть как стандартные метрики — Accuracy,Recall, Kappa, AUC, так и предложенные разработчиком. Мы будем использовать в этом качестве ошибку классификации.

Поиск лучшей комбинации предикторов будем производить с помощью пакета "tabuSearch" v.1.1, который является расширением алгоритма HillClimbing. Алгоритм TabuSearch оптимизирует двоичную строку, используя объективную функцию, определенную пользователем. В результате он выдает лучшую бинарную конфигурацию с самым высоким значением объективной функции. Мы будем использовать этот алгоритм для поиска наилучшей комбинации предикторов.

Основная функция:

tabuSearch(size = 10, iters = 100, objFunc = NULL, config = NULL, neigh = size, listSize = 9, 
           nRestarts = 10, repeatAll = 1, verbose = FALSE)

Аргументы:

size – длина оптимизируемой бинарной конфигурации;

iters – число итераций в предварительном поиске алгоритма;

objFun – предлагаемый пользователем метод, который оценивает целевую функцию для данной двоичной строки;

config – стартовая конфигурация;

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

listSize – размер табу-списка;

nRestarts – максимальное количество перезапусков на интенсивном этапе поиска алгоритма;

repeatAll – количество повторений поиска;

verbose – логический, если true, печатается имя текущего этапа алгоритма, например, предварительный этап, этап интенсификации, этап диверсификации.

Напишем объективную функцию и приступим к экспериментам.
ObjFun <- function(th){
  require(xgboost)
  # Если в бинарной строке все ноли выходим
  if (sum(th) == 0) return(0)
  # имена предикторов соответствующих 1 в бинарной строке
  sub <- subset[th != 0]
  # Создадим структуру для обучения модели
  dtrain <- xgb.DMatrix(data = x.train[ ,sub], label = y.train)
  # Обучим модель
  bst = xgb.train(params = par, data = dtrain, nrounds = nround, verbose = 0)
  # Вычислим предсказания по тестовому набору
  pred <- predict(bst, x.test[ ,sub])
  # Определим ошибку предсказания
  err <- mean(as.numeric(pred > 0.5) != y.test)
  # Вернем критерий качества
  return(1 - err) 
}

Для вычислений нам нужно подготовить наборы данных для обучения и тестирования модели, а также определить параметры модели и начальную конфигурацию для оптимизации. Используем те же данные и функции, что и в предыдущей статье (EURUSD/M30, 6000 баров по состоянию на 14.02.16).

Листинг с комментариями:

#---tabuSearch----------------------
require(tabuSearch)
require(magrittr)
require(xgboost)
# Исходный датафрейм
dt <- form.data(n = 34, z = 50, len = 0)
# Имена всех предикторов в исходном наборе 
subset <- colnames(In())
set.seed(54321, kind = "L'Ecuyer-CMRG")
# Подготовим наборы для обучения и тестирования
DT <- prepareTrain(x = dt[  ,subset], 
                   y = dt$y, 
                   balance = FALSE, 
                   rati = 4/5, mod = "stratified", 
                   norm = FALSE, meth = method)
train <- DT$train
test <- DT$test
x.train <- train[  ,subset] %>% as.matrix()
y.train <- train$y %>% as.numeric() %>% subtract(1)
x.test <- test[  ,subset] %>% as.matrix()
y.test <- test$y %>% as.numeric() %>% subtract(1)
# Исходный бинарный вектор
th <- rep(1,length(subset))
# Параметры модели
par <- list(max.depth = 3, eta = 1, silent = 0, 
            nthread = 2, objective = 'binary:logistic')
nround = 10

# Начальная конфигурация 
conf <- matrix(1,1,17)
res <- tabuSearch(size = 17, iters = 10, 
                  objFunc = ObjFun, config = conf,
                  listSize = 9, nRestarts = 1)
# Максимальное значение объективной функции
max.obj <- max(res$eUtilityKeep)
# Лучшая комбинация бинарного вектора
best.comb <- which.max(res$eUtilityKeep)%>% res$configKeep[., ]
# Лучший набор предикторов
best.subset <- subset[best.comb != 0]

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

> system.time(res <- tabuSearch(size = 17, iters = 10, 
+  objFunc = ObjFun, config = conf, listSize = 9, nRestarts = 1))
   user  system elapsed 
  36.55    4.41   23.77 
> max.obj
[1] 0.8
> best.subset
 [1] "DX"     "ADX"    "oscDX"  "ar"     "tr"     "atr"   
 [7] "chv"    "cmo"    "vsig"   "rsi"    "slowD"  "oscK"  
[13] "signal" "oscKST"
> summary(res)
Tabu Settings
  Type                                       = binary configuration
  No of algorithm repeats                    = 1
  No of iterations at each prelim search     = 10
  Total no of iterations                     = 30
  No of unique best configurations           = 23
  Tabu list size                             = 9
  Configuration length                       = 17
  No of neighbours visited at each iteration = 17
Results:
  Highest value of objective fn    = 0.79662
  Occurs # of times                = 2
  Optimum number of variables      = c(14, 14)

Вычисления заняли около 37 секунд при точности предсказания около 0.8 и 14 предикторах. Полученный показатель качества с параметрами по умолчанию очень хорош. Проведем тот же расчет, но со 100 итерациями.

> system.time(res <- tabuSearch(size = 17, iters = 100, 
+  objFunc = ObjFun, config = conf, listSize = 9, nRestarts = 1))
   user  system elapsed 
 377.28   42.52  246.34 

> max.obj
[1] 0.8042194
> best.subset
 [1] "DX"     "ar"     "atr"    "cci"    "chv"    "cmo"   
 [7] "sign"   "vsig"   "slowD"  "oscK"   "SMI"    "signal"
>

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

Это не единственный алгоритм и пакет, который помогает выбрать лучший набор предикторов с помощью ГА. Вы можете использовать пакеты kofnGA, fSelector.  Кроме них, в пакете "caret" функцией gafs() реализован выбор предикторов с помощью ГА.



6.2. Поиск лучших параметров ТС

1. Исходные данные для проектирования. Возьмем для примера эксперт MACDSampl.

В эксперте MACDSample реализован алгоритм, генерирующий сигналы при пересечении линий macd и signal. Используется один индикато. 

MACD(x, nFast = 12, nSlow = 26, nSig = 9, maType, percent = TRUE, ...)
Arguments

x

Таймсерия одной переменной; как правило price, но может быть volume, и т.п.

nFast

Количество периодов для быстрой МА.

nSlow

Количество периодов для медленной МА

nSig

Количество периодов для сигнальной МА

MaType – тип применяемой МА

percent – логическая, если true, то возвращается разница между быстрой и медленной МА в процентах, иначе — простая разница.

Функция MACD возвращает две переменных: macd — разница между быстрой МА и медленной МА, или скорость изменения расстояния между быстрой МА и медленной МА; signal — МА от этой разницы. MACD является частным случаем общего осциллятора, применяемого к цене. Он может быть использован также с любой таймсерией одной переменной. Временные периоды для MACD часто устанавливают как 26 и 12, но функция первоначально использовала экспоненциальные константы 0.075 и 0.15, которые ближе к 25.6667 и 12.3333 периодов.

Итак наша функция имеет 7 параметров с диапазонами изменений:

p5,p6 = Cs(SMA, EMA, DEMA, ZLEMA).

Сигналы для торговли можно генерировать различными способами:

Вариант 1

Buy = macd > signal 

Sell = macd < signal

Вариант 2

Buy = diff(macd) > 0

Sell = diff(macd) <= 0

Вариант 3

Buy = diff(macd) > 0 & macd > 0

Sell = diff(macd) < 0 & macd < 0

Это еще один параметр оптимизации signal(1:3).

И, наконец, последний параметр — глубина истории оптимизации len = 300:1000 (количество последних баров на которых проводится оптимизация).

Итого имеем 9 параметров оптимизации. Я умышленно увеличил их количество, чтобы показать: параметром может стать все, что угодно (числа, строки и т. п.).

Критерий оптимизации — коэффициент качества К в пунктах (в моих предыдущих публикациях он уже был подробно описан).

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

Мы будем применять надежный, быстрый, а главное — многократно проверенный на практике пакет "rgenoud". Основное его ограничение — в том, что его параметры должны быть или все целые, или все вещественные. Это мягкое ограничение, оно легко обходится. Функция genoud()комбинирует алгоритм эволюционного поиска с методами на базе производных (Newton or quasi-Newton) для решения различных оптимизационных проблем. Genoud()можно использовать для решения оптимизационных проблем, для которых производные не определяемы. Кроме того, используя опцию cluster, функция поддерживает использование нескольких компьютеров, процессоров или ядер для качественного параллельного вычисления. 

genoud(fn, nvars, max = FALSE, pop.size = 1000, 
        max.generations = 100, wait.generations = 10,
      hard.generation.limit = TRUE, starting.values = NULL, MemoryMatrix = TRUE, 
      Domains = NULL, default.domains = 10, solution.tolerance = 0.001,
      gr = NULL, boundary.enforcement = 0, lexical = FALSE, gradient.check = TRUE,
      BFGS = TRUE, data.type.int = FALSE, hessian = FALSE, 
      unif.seed = 812821, int.seed = 53058,
      print.level = 2, share.type = 0, instance.number = 0, 
      output.path = "stdout", output.append = FALSE, project.path = NULL,
      P1 = 50, P2 = 50, P3 = 50, P4 = 50, P5 = 50, P6 = 50, P7 = 50, P8 = 50, 
        P9 = 0, P9mix = NULL, BFGSburnin = 0, BFGSfn = NULL, BFGShelp = NULL,
      control = list(), 
        optim.method = ifelse(boundary.enforcement < 2, "BFGS", "L-BFGS-B"), 
      transform = FALSE, debug = FALSE, cluster = FALSE, balance = FALSE, ...)

Arguments

Несмотря на то, что переменная max.generations по умолчанию не ограничивает количество поколений, это, тем не менее, важно, потому что многие операторы используют его, чтобы скорректировать свое поведение. В сущности, многие операторы становятся менее случайными, поскольку количество поколений становится ближе к пределу max.generations. Если предел превышен и genoud решает продолжать работать, то он автоматически увеличивает предел max.generation. 

У boundary.enforcement есть три возможных значения: 0 (подходит все), 1 (частично ограничен), и 2 (никаких нарушений границы):

С целочисленными параметрами genoud никогда не использует информацию о производных. Это подразумевает, что оптимизатор  BFGS никогда не используется — т.е., флаг BFGS установлен в FALSE. Это также подразумевает, что Оператор P9 (Локально-минимальный кроссовер) обнулен и что проверка градиента (как критерий сходимости) выключена. Независимо от того, во что были установлены другие опции, data.type.int имеет приоритет — т.е., если genoud сказано, что нужно искать по целочисленному пространству параметров, информация о градиенте никогда не рассматривается.
Нет опции, позволяющей смешать целочисленные параметры и с плавающей точкой. Если вы хотите смешать эти два типа, можно указать целочисленный параметр, а в объективной функции преобразовать целочисленный диапазон в диапазон с плавающей точкой. Например, вам нужно получить поисковую сетку от 0.1 до 1.1. Вы указываете genoud искать от 10 до 110, а в фитнес-функции разделяете этот параметр на 100.

Операторы. Genoud имеет и использует 9 операторов. Целочисленные значения, которые присвоены каждому из этих операторов (P1... P9) — веса. Genoud вычисляет сумму s = P1+P2 +... +P9. Каждому оператору присваивают вес, равный W_n = s / (P_n). Количество вызовов оператора обычно равняется c_n = W_n * pop.size.

Операторы Р6 (Простой кроссовер) и Р8 (Эвристический кроссовер) требуют четного количества особей для продолжения работы — иными словами, им нужны два родителя. Поэтому переменная pop.size и наборы операторов должны быть такими, чтобы у этих трех операторов было четное число особей. Если этого не происходит, genoud автоматически корректирует вверх численность популяции, чтобы это ограничение выполнялось.

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

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

Универсальная мутация, граничная мутация и неоднородные мутации действуют на единственное испытательное решение.

Замечание:

Самые важные опции, влияющие на качество, — это те, которые определяют численность популяции (pop.size) и число поколений, выполняемых алгоритмом (max.generations, wait.generations, hard.generation.limit и gradient.check). Поисковая производительность, как ожидают, улучшится, если численность популяции и число поколений, выполняемых программой, увеличатся. Эти и другие опции должны быть скорректированы для различных проблем вручную. Обратите особое внимание на области поиска (Домены и default.domains).

Линейные и нелинейные ограничения среди параметров могут быть представлены пользователями в их фитнес-функции. Например, если сумма параметров 1 и 2 должна быть меньше чем 725, это условие можно заложить в фитнес-функцию, пользователь будет максимизировать genoud, : if((parm1 + parm2)>= 725) {return (-99999999)}. В этом примере очень плохое фитнес-значение будет возвращено genoud, если линейное ограничение нарушено. Тогда genoud попытается найти значения параметров, которые удовлетворят ограничение.

Напишем нашу фитнес-функцию. Она должна вычислять:

# фитнес функция-------------------------fitnes <- function(param, test = FALSE){
  require(TTR)
  require(magrittr)
  # определим переменные
  x <- pr[param[1]]
  nFast <- param[2]
  nSlow <- param[3]
  nSig <- param[4]
  macdType <- MaType[param[5]]
  sigType <- MaType[param[6]]
  percent <- per[param[7]]
  len <- param[9]*100 
  # линейное ограничение для macd
  if (nSlow <= nFast) return(-Inf)
  # вычисляем macd
  md <- MACD(x = x, nFast = nFast, nSlow = nSlow,
             nSig = nSig, percent = TRUE,
             maType = list(list(macdType), 
                           list(macdType),
                           list(sigType)))
  # вычисляем сигналы и сдвигаем вправо на 1 бар
  sig <- signal(md, param[8]) %>% Lag()
  #вычисляем баланс на истории длиной len
  bal <- cumsum(tail(sig, len) * tail(price[ ,'CO'], len))
  if(test)
        {bal <<- cumsum(tail(sig, len) * tail(price[ ,'CO'], len))}
  # вычисляем коэффициент качества(округляем до целого числа)
  K <- ((tail(bal,1)/length(bal))* 10 ^ Dig) %>% floor()
  # возвращаем полученный критерий оптимизации
  return(unname(K))
}

Ниже приведен листинг определения всех переменных и функций

require(Hmisc)
# Типы средних = 4 -------------------------------------------
MaType <- Cs(SMA, EMA, DEMA, ZLEMA)
require(dplyr)
# Типы цен = 4 -----------------------------------------------
pr <- transmute(as.data.frame(price), Close = Close, Med = Med, 
                Typ = (High + Low + Close)/3,
                WClose = (High + Low + 2*Close)/4)
# как считать?
per <- c(TRUE, FALSE)
# Варианты сигналов = 3 --------------------------
signal <- function(x, type){
  x <- na.omit(x)
  dx <- diff(x[ ,1]) %>% na.omit()
  x <- tail(x, length(dx))
  switch(type,
         (x[ ,1] - x[ ,2]) %>% sign(),
         sign(dx),
         ifelse(sign(dx) == 1 & sign(x[ ,1]) == 1, 1,
                ifelse(sign(dx) == -1 & sign(x[ ,1]) == -1,-1, 0))
  )
}
# начальная крнфигунация-------------------------- 
par <- c(2, 12, 26, 9, 2, 1, 1, 3, 5)
# пространство поиска------------------------------
dom <- matrix(c(1, 4,   # для типов цен
                8, 21,  # для периода быстрой МА
                13, 54, # для периода медленной МА
                3, 13,  # для периода сигнальной МА
                1, 4,   # тип МА для быстрой и медленной
                1, 4,   # тип МА для сигнальной
                1, 2,   # тип percent
                                1, 3,   # вариант signal
                3,10),  # длина истории [300:1000]
                                ncol = 2, byrow = TRUE)
# создать кластер из доступных ядер процессора
puskCluster<-function(){
  library(doParallel)
  library(foreach)
  cores<-detectCores()
  cl<-makePSOCKcluster(cores)
  registerDoParallel(cl)
  #clusterSetRNGStream(cl)
  return(cl)
}

Определим коэффициент качества с начальными (как правило, по умолчанию) параметрами

> K <- fitnes(par, test = TRUE)
> K
[1] 0
> plot(bal, t="l")

Img.1. Balance 1

Рис.1 Баланс с параметрами по умолчанию 

Результат очень плохой.

Для сравнения скорости вычисления проведем оптимизацию на одном ядре и на кластере из двух ядер процессора.

На одном ядре:

pr.max <- genoud(fitnes, nvars = 9, max = TRUE, 
                 pop.size = 500, max.generation = 300,
                 wait.generation = 50, 
                 hard.generation.limit = FALSE,
                 starting.values = par, Domains = dom, 
                 boundary.enforcement = 1,
                 data.type.int = TRUE,
                 solution.tolerance = 0.01,
                 cluster = FALSE,
                 print.level = 2)
'wait.generations' limit reached.
No significant improvement in 50 generations.

Solution Fitness Value: 1.600000e+01

Parameters at the Solution:
 X[ 1] :        1.000000e+00
 X[ 2] :        1.400000e+01
 X[ 3] :        2.600000e+01
 X[ 4] :        8.000000e+00
 X[ 5] :        4.000000e+00
 X[ 6] :        1.000000e+00
 X[ 7] :        1.000000e+00
 X[ 8] :        1.000000e+00
 X[ 9] :        4.000000e+00

Solution Found Generation 5
Number of Generations Run 56

Thu Mar 24 13:06:29 2016
Total run time : 0 hours 8 minutes and 13 seconds

Оптимальные параметры (генотип)
> pr.max$par
[1]  1 14 26  8  4  1  1  1  4

Расшифруем (фенотип):

Посмотрим, как выглядит линия баланса с оптимальными параметрами. Для этого выполним фитнес-функцию с этими параметрами и с опцией test = TRUE.

> K.opt <- fitnes(pr.max$par, test = TRUE)
> K.opt
[1] 16
> plot(bal, t="l")

Img.2. Balance 2

Рис.2. Баланс с оптимальными параметрами 

Это вполне приемлемый результат, с которым может работать эксперт.

Выполним те же вычисления на кластере из двух ядер

# запускаем кластер
cl <- puskCluster()
# максимизация фитнес функции
# передаем каждому ядру в кластере необходимые переменные и функции
clusterExport(cl, list("price", "pr", "MaType", "par", "dom", "signal", 
                                                "fitnes", "Lag", "Dig", "per" ) )
pr.max <- genoud(fitnes, nvars = 9, max = TRUE, 
                 pop.size = 500, max.generation = 300,
                 wait.generation = 50, 
                 hard.generation.limit = FALSE,
                 starting.values = par, Domains = dom, 
                 boundary.enforcement = 1,
                 data.type.int = TRUE,
                 solution.tolerance = 0.01,
                 cluster = cl,
                 print.level = 2) # только для экспериментов. 
                                            #   В эксперте установить в 0
# останавливаем кластер
stopCluster(cl)
'wait.generations' limit reached.
No significant improvement in 50 generations.

Solution Fitness Value: 1.300000e+01

Parameters at the Solution:

 X[ 1] :        1.000000e+00
 X[ 2] :        1.900000e+01
 X[ 3] :        2.000000e+01
 X[ 4] :        3.000000e+00
 X[ 5] :        1.000000e+00
 X[ 6] :        2.000000e+00
 X[ 7] :        1.000000e+00
 X[ 8] :        2.000000e+00
 X[ 9] :        4.000000e+00

Solution Found Generation 10
Number of Generations Run 61

Thu Mar 24 13:40:08 2016
Total run time : 0 hours 3 minutes and 34 seconds

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

Вычислим cамый простой вариант

pr.max <- genoud(fitnes, nvars = 9, max = TRUE, 
                 pop.size = 500, max.generation = 100,
                 wait.generation = 10, 
                 hard.generation.limit = TRUE,
                 starting.values = par, Domains = dom, 
                 boundary.enforcement = 0,
                 data.type.int = TRUE,
                 solution.tolerance = 0.01,
                 cluster = FALSE,
                 print.level = 2)
'wait.generations' limit reached.
No significant improvement in 10 generations.

Solution Fitness Value: 1.500000e+01

Parameters at the Solution:

 X[ 1] :        3.000000e+00
 X[ 2] :        1.100000e+01
 X[ 3] :        1.300000e+01
 X[ 4] :        3.000000e+00
 X[ 5] :        1.000000e+00
 X[ 6] :        3.000000e+00
 X[ 7] :        2.000000e+00
 X[ 8] :        1.000000e+00
 X[ 9] :        4.000000e+00

Solution Found Generation 3
Number of Generations Run 14

Thu Mar 24 13:54:06 2016
Total run time : 0 hours 2 minutes and 32 seconds

Хороший результат. А баланс?

> k
[1] 15
> plot(bal, t="l")

Img.3. Balance 3

Рис.3. Баланс с оптимальными параметрами

Очень приличный результат за приемлемое время.

Для сравнения результатов генетического алгоритма с эволюционными, проведем серию экспериментов с ними. Первым испытаем алгоритм SOMA(Self-Organising Migrating Algorithm), реализованный в пакете "soma". 

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

soma(costFunction, bounds, options = list(), strategy = "all2one", …)

Arguments

costFunction

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

bounds

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

options

Список опций для самого SOMA алгоритма (см. ниже).

strategy

Тип использованой стратегии. В настоящее время "all2one" является единственным поддерживаемым значением.

...

Дополнительные параметры для  costFunction

Детали
Для настройки проведения оптимизации и критериев ее завершения доступны множество опций. Значения по умолчанию, используемые здесь, рекомендованы автором Zelinka (2004).

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

require(soma)
x <- soma(fitnes, bounds = list(min=c(1,8,13,3,1,1,1,1,3), 
          max = c(4,21,54,13,4,4,2,3,10)), 
          options = list(minAbsoluteSep = 3,
                         minRelativeSep = -1,
                         nMigrations = 20,
                         populationSize = 20),
                        opp = TRUE)
Output level is not set; defaulting to "Info"
* INFO: Starting SOMA optimisation
* INFO: Relative cost separation (-2.14) is below threshold (-1) - stopping
* INFO: Leader is #7, with cost -11

Лучшие параметры:

> x$population[ ,7]
[1]  1.532332 15.391757 37.348099  9.860676  1.918848
[6]  2.222211  1.002087  1.182209  3.288627
Округлим
> x$population[ ,7]%>% floor
[1]  1 15 37  9  1  2  1  1  3

Лучшее значение фитнес-функции = 11. Это приемлемо для практического применения, но есть возможность для улучшения.

Алгоритм быстр, но нестабилен по результатам и требует тонкой настройки.

Generalized Simulated Annealing Function( Обобщенная функция симуляции отжига)

Этот алгоритм реализован в пакете «GenSA”. Эта функция может выполнять поиск глобального минимума весьма сложной нелинейной целевой функции с очень большим количеством оптимумов. 

 GenSA(par, fn, lower, upper, control=list(), …)

Аргументы:

Значения компонентов управления по умолчанию установлены для сложной задачи оптимизации. Для обычной задачи оптимизации со средней сложностью GenSA может найти разумное решение быстро, поэтому пользователю рекомендуется позволить GenSA остановиться раньше:

установив threshold.stop, если threshold.stop — это ожидаемое значение функции;

либо путем установки max.time, если пользователь просто хочет запустить GenSA для max.time секунд;

либо установив max.call, если пользователь просто хочет запустить GenSA в пределах max.call вызовов функций.

Для очень сложных задач оптимизации пользователю рекомендуется увеличить maxit  и  temperature.

Запустим оптимизацию, ограничив максимальное время исполнения 60 секундами.

require(GenSA)
pr.max <- GenSA(par, fitnes, lower = c(1,8,13,3,1,1,1,1,3),
            upper = c(4,21,54,13,4,4,2,3,10), 
                        control = list(verbose = TRUE, simple.function = TRUE, 
                                                        max.time = 60), opp = TRUE)

Значение фитнес-функции и значение оптимальных параметров:

> pr.max$value * (-1) [1] 16
> par1 <- pr.max$par 
> par1
[1]  1.789901 14.992866 43.854988  5.714345  1.843307
[6]  1.979723  1.324855  2.639683  3.166084

Округлим:

> par1 <- pr.max$par %>% floor
[1]  1 14 43  5  1  1  1  2  3

Вычислим значение фитнес-функции с этими параметрами и посмотрим на линию баланса:

> f1 <- fitnes(par1, test = TRUE)
> plot(-1 * bal, t="l")

Img.4 Balance 4

Рис.4 Баланс 4

Показатели качества — на хорошем уровне, а вычисления удивительно быстры.

Все эти и многие другие аналогичные алгоритмы (пакеты dfoptim, nlopt,CEoptim, DEoptim,RcppDE и др) оптимизируют функцию по одному критерию. Для многокритериальной оптимизации предназначен пакет mco.



7. Пути и методы улучшения качественных показателей

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



Заключение

Мы рассмотрели основные принципы, заложенные в эволюционных алгоритмах, их разновидности и особенности. На примере простого эксперта MACDSample мы с помощью экспериментов показали, что применение оптимизации параметров даже для такой элементарной ТС  дает значительный положительный эффект. 

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

Самая важная часть работы при этом — правильно написать фитнес-функцию.

Надеюсь эта статья поможет вам понять, что это несложно, и самим попробовать внедрить оптимизацию в Ваши эксперты.