ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ ФОРЕКС

Лучшие Форекс брокеры 2021:

Содержание этой статьи:

Генетические алгоритмы в MetaTrader 4. Сравнение с прямым перебором оптимизатора

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

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

2. Эксперт

Для проведения экспериментов я немного доработал уже знакомого вам по статье Управление ордерами — это просто эксперта CrossMACD:

  • Добавил к устанавливаемым позициям СтопЛосс и ТейкПрофит.
  • Добавил сопровождение позиций ТрейлингСтопом.
  • Для фильтрации сигналов ввел параметр OpenLuft: теперь сигналом будет пересечение нулевой линии на определённое количество пунктов (с точностью до одной десятой пункта).
  • Добавил параметр CloseLuft для аналогичной фильтрации сигналов закрытия.
  • Вынес во внешние переменные периоды быстрой и медленной скользящих средних, используемых при расчёте индикатора MACD.

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

3. Оптимизация

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

Честные Форекс брокеры:

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

Для сравнения результатов оптимизация с использованием генетических алгоритмов будет проводиться дважды: первый раз – с целью найти максимальную прибыль (Profit), а второй – с целью найти лучшую прибыльность (Profit Factor). После этого три лучшие результата для обоих методов оптимизации будут представлены в сводной таблице отчёта, отсортированной по указанным колонкам.

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

Генетический алгоритм оптимизации торговой стратегии

В пространстве допустимых значений параметров каждая точка, каждая пара координат — “рост / цвет глаз” теоретически описывает одну “особь”. Допустим, мы случайным образом сотворили 10 особей. Это и был первый шаг генетического алгоритма оптимизации — создать первое поколение:

В пространстве координат M — T случайно выбраны точки. К примеру, две точки, отмеченные красной рамкой — “особи” с гендерно-нейтральными именами (это важный момент!) Женя и Саша. “Рост” Саши (в исходной постановке задачи — период скользящей средней) составляет 11 единиц, “цвет глаз” равен 0.6 (зелено-голубые глаза). Женя несколько отличается по параметрам. Те же характеристики описывают 8 оставшихся особей.

Второй шаг — размножение

От двух “родительских” особей получаем третью особь, которая наследует часть признаков одного родителя, часть — другого. Например, у Жени с Сашей родилась особь Никита (НикИта, НикитА?):

Надежные Форекс площадки:
  • Никита унаследовал признак “цвет глаз” (параметр TakeProfit робота) от одного из родителей — “Жени”,
  • “рост” (период скользящей средней робота) Никита унаследовал от “Саши”… но немного подкорректированный в сторону другого родителя, Жени.

Третий шаг — селекция

Движитель эволюционного процесса, естественный отбор. 4 из 10 лучших особей дали еще 10 потомков. Теперь у нас 20 особей. Генетический алгоритм оптимизации предполагает поддержание постоянного размера популяции. 10 особей должны “умереть”. В данной реализации “умирают” большинство особей первого поколения, от 80% до 100%.
Соответственно, в нашем примере новое поколение будет составлено из 0… 2 родителей и 8 — 10 их отпрысков. Иначе говоря, если опустить лирику, новые вектора параметров торгового робота будут рассчитываться от векторов, полученных на предыдущем шаге, “размножении” (комбинации) 4-х лучших лучших тестов. Большинство «стариков» в новой итерации селекции участия не примут (возможны и другие варианты реализации селекции).

Завершение алгоритма

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

  • вливание в популяцию “свежей крови”. К потомкам текущей популяции добавляется несколько новых особей, полученных случайно, таким же путем, которым формировалась начальная популяция,
  • механизм мутации: особь-потомок может иметь какую-то из характеристик (координат) несколько отличающийся от характеристик собственных родителей:

в данном примере

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

Если вернуться к исходным данным, на которых мы тестировали алгоритмы Монте-Карло, градиентного спуска и алгоритм с рабочим названием “морской бой”, процесс оптимизации можно проиллюстрировать следующей анимацией:

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

Теперь сравним алгоритмы на все той же поверхности: P = f(M , T ):

Монте-Карло градиентный спуск “морской бой” генетический алгоритм
95.7% 92.1% 97.0% 96.8%

Среднее значение найденного экстремума ЦФ в процентах от глобального значения.

Конечно, по одному набору входных данных судить рано, но пока что ГА, применительно к нашему торговому роботу, уступает алгоритму “морской бой”:

  • совсем незначительно — по среднему от найденного квазиоптимального значения ЦФ,
  • дает худшую оценку параметрической устойчивости торгового алгоритма, так как не слишком подробно “исследует” окрестности найденных квазиоптимальных кортежей параметров.

Итоговый тест 4-х алгоритмов оптимизации

Итоговый тест проведен на 4-х наборах входных данных — результаты бэктеста торговой стратегии на 4-х разных отрезках истории цен (EURUSD : 2022 год, EURUSD: 2022, XAUUSD : 2022, XAUUSD: 2022).

(примеры ЦФ как функций от двух параметров для 4-х временных рядов цен)

В этот раз оптимизация проводилась по 3-м параметрам:

  1. период “быстрой” скользящей средней
  2. период “медленной” скользящей средней
  3. TakeProfit (прибыль по сделке, в процентах, при достижении которой сделка завершалась).

Оптимизация проводилась с ограничением в 160, 400 и 800 тестов (вычислений ЦФ в выбранных координатах). Каждый раз результаты усреднялись для 1 000 итераций оптимизации. Среднее значение ЦФ для найденного квазиоптимального вектора параметров составило:

Монте-Карло градиентный спуск “морской бой” генетический алгоритм
84.1% 83.9% 77.0% 92.6%

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

тестов Монте-Карло градиентный спуск “морской бой” генетический алгоритм
160 из 8 000 79.1% 76.7% 73.1% 87.7%
400 из 8 000 84.7% 85.0% 77.4% 93.7%
800 из 8 000 88.6% 90.1% 80.4% 96.3%

Вместо заключения

Я был несколько удивлен результатом, который показал генетический алгоритм оптимизации. Не считаю, что конкретно “генетическая парадигма” метода обеспечила ему первое место в списке. В каком-то смысле, по логике выбора координат, он напоминал методы дихотомии / золотого сечения. Вероятно, стоит опробовать один из этих алгоритмов и сравнивать ГА именно с ним.

Возвращаясь к торговому роботу, стоит отметить, как меняется “рельеф” поверхности, образованной ЦФ (прибылью) от года к году. Т.е., “оптимизировав” робота на истории 2022 года нет смысла применять эти настройки в 2022 году (первом квартале, месяце, неделе … 2022 года).

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

Генетическое программирование торговых стратегий

Своим опытом в построении высокопроизводительных торговых систем с использованием генетического программирования делится Dr Jonathan Kinlay в своем блоге.

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

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

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

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

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

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

Внутридневная ГП стратегия

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

Для ответа на этот вопрос приведем ниже результаты созданной с помощью ГП внутридневной стратегии, которая торгует девять разных фьючерсных рынков: сырая нефть (CL), евро (EC), E-mini (ES), золото (GC), топочный мазут (HO), кофе (KC), природный газ (NG), десятилетние облигации (TY) и бонды (US). Система торгует один контракт на каждом рынке раздельно, входя в длинные и короткие позиции несколько раз в день. Торгуется только наиболее ликвидные периоды в течение дня, которые обычно соответствуют открытию/закрытию торгов, с выходом из открытых позиций к концу сессии с помощью маркет-ордеров. Кроме рынков NG и HO, где вход осуществляется по стоп ордерам, на остальных рынках для входа и выхода в/из позиции применяются лимитные ордера, по ценам, определенным алгоритмом.

Система была создана с использованием 15-минутных баров с января 2006 года по декабрь 2022 года и протестирована на out-of-sample данных с января 2022 года по май 2022 года. Тренировочный набор данных выбирался как с учетом периодов сильной активности рынков, так и чтобы были включены периоды со слабой волатильностью. Длина тестовой выборки составляет почти половину тренировочной для определения устойчивости системы.

Out-of-sample тестирование производилось по принципу " вслепую", то есть данные для тестирования не использовались для тренировки модели, также как и вычисление производительности осуществлялось до выбора модели.

Результаты получились следующие — средняя чистая прибыль за вычетом комиссий = 6 долларов на сделку, и в случае HO и NG дополнительное проскальзывание в размере 2 тика на сделку.

Самая поразительная особенность стратегии — это высокая степень прибыльности, выраженная коэффициентом Шарпа, который превысил 5 как в тренировочном, так и в тестовом периоде. Это отражение того факта, что в то время, как чистая прибыль упала со среднегодового значения 29% в тренировочной выборке до 20% в тестовой, волатильность тоже снизилась с 5,35% до 3,86% в следующем периоде. Уменьшение риска в тестовом периоде также отражено в уровне просадки.

Уменьшение средней прибыли за сделку с 25$ до 16$ (без вычета комиссии) объясняется некоторым увеличением количества сделок, с 42 до 44 в день в среднем, в то время как вероятность предсказания и процент прибыльных сделок остались постоянными — 65% и 56% соответственно.

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

Преимущества и риски ГП подхода к созданию торговых систем

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

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

Другой недостаток это то, что из-за природы процесса моделирования, бывает очень трудно понять, или объяснить инвесторам, идею, лежащую в основе конкретной модели. «Мы протестировали и оно работает» — это недостаточно убедительное объяснение для инвесторов, которые привыкли к более подробным теоретическим обоснованиям. К несчастью, во время просадок, сложно убедить себя или инвесторов, что это временное явление.

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

Заключение

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

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

Генетические алгоритмы: в поисках священного грааля

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

Подсмотрено у матушки-природы
Генетические алгоритмы (ГА) – по сути, это методы эффективной оптимизации и поиска решений, подсмотренные у матушки-природы. Обычно они применяются для решения задач, имеющих большое количество параметров и не имеющих четко формализованного метода решения. Перебирать все варианты – нереально долго, а с помощью ГА можно справиться удивительно быстро и с необходимой степенью точности. Каждый параметр решаемой задачи становится геном, а полный набор параметров системы – это набор генов, одна хромосома, одна особь. Например, в системе пять параметров, каждый из которых может меняться в пределах от 0 до 255. Тогда наша особь (или хромосома) – это набор из пяти байтов, идущих друг за другом, представленных в двоичной форме и выглядящих как двоичная цепочка длиной 40 бит. На начальном этапе ГА создается популяция из большого количества особей, значения генов (параметров) которых берутся случайным образом. Далее для каждой особи производится расчет системы и вычисляется фитнесс – функция некоторых результирующих значений системы. Собственно, фитнесс и является признаком приспособленности особи – показателем ее соответствия решению, которое ищется.
Далее популяция сортируется по значению фитнесса, и из нее берется половина особей, имеющих наилучший фитнесс. После чего в ход идут собственно механизмы ГА – скрещивание, мутация и инверсия. Для скрещивания из популяции выбираются две особи, которые будут родителями, определяется (случайным образом) точка разрыва, после чего создается потомок – как соединение части первого и второго родителя. Таким образом, потомок получает частично признаки обоих родителей. Это важнейшая часть ГА – собственно, здесь и происходит создание новой особи, несущей признаки обоих родителей и, возможно, более приспособленной, чем каждый из них.
После того как все особи прошли скрещивание и их количество стало совпадать с начальной популяцией, производят мутацию. Для этого случайным образом выбирается несколько особей, в которых каждый бит меняется на противоположный. Также используется еще и метод инверсии, который заключается в том, что хромосома с определенной долей вероятности делится на две части, которые затем меняются местами. Эти два метода ГА служат для привнесения как бы извне новых признаков, не содержащихся в исходной популяции.

После проведения всех вышеуказанных действий мы получаем популяцию, равную по численности исходной, но более приспособленную к решению задачи. Далее процесс повторяется заново: расчет фитнесса, скрещивание, мутации и инверсия. Пройдя большое количество итераций (поколений), мы получим особи, содержащие гены с наиболее удачными параметрами оптимизируемой системы. Для оптимизации существующих стратегий Рассмотрим простейшую механическую торговую систему (МТС). Две скользящие средние (МА1 и МА2) пересекаются. Их пересечение дает точку входа в рынок. Пересечение двух других (МА3 и МА4) дает точку выхода. У каждой МА есть два параметра – длина и сдвиг (в будущее на n баров). То есть общее количество параметров системы равно 8. Четыре отвечают за вход, четыре за выход. Для упрощения будем считать, что значения каждого параметра лежат в промежутке от 0 до 255 (один байт). Длина каждой хромосомы, таким образом, составляет 8 байтов, или 64 бита.

Количество особей в популяции выбирается в зависимости от числа генов в хромосоме – эмпирически. Для рассматриваемого случая популяции в 300 особей будет достаточно. Фитнессом системы для простоты будем считать общую полученную прибыль. Запускаем ГА. На фазе расчета фитнесса прогоняем по историческим данным каждую особь – то есть нашу систему (MA1MA2-MA3MA4) с параметрами текущей особи. И получаем прибыль – она, напомню, у нас является фитнессом (или приспособленностью) данной особи. После прохождения некоторого количества итераций значения генов у особей с наибольшим фитнессом практически перестают изменяться. В этот момент можно считать, что итерационный процесс сошелся. Особь из получившейся популяции с наибольшим фитнессом – и будет тем набором параметров, который наилучшим образом подходит для нашей системы.

Я протестировал подобную МТС для 5-минутных графиков EUR/USD. Процесс сходится примерно после 100-150 поколений. Скорость схождения процесса зависит от параметров ГА – вероятностей скрещивания, мутации и инверсии. Уменьшая вероятности мутации и инверсии, мы убыстряем схождение процесса, однако появляется опасность, что процесс сойдется на одном из локальных максимумов. После тестирования стало ясно, что данная система нежизнеспособна (что, в общем-то, и не вызывало сомнений), хотя ГА и порождали наборы параметров, при которых такая система дает большую прибыль. Однако данная система приведена здесь лишь из-за своей простоты и для демонстрации принципа функционирования генетического алгоритма.

Выбор фитнесса
Одна из важнейших задач, которые необходимо решить при тестировании систем с помощью ГА, – выбор фитнесса. Как я уже говорил, фитнесс – это некоторая функция результирующих значений системы. Выше рассматривался вариант, когда фитнесс (Fit) равен прибыли (Profit). Однако оптимизация по такому фитнессу приводит к тому, что ГА порождает параметры, при которых система может выдавать, например, только одну (на периоде тестирования) сделку – прибыльную, конечно, но для устойчивости системы этого явно не достаточно. Хорошим решением будет ввести в расчет фитнесса количество сделок, совершаемых системой (CountTrade):

Fit = Profit * CountTrade.

Но тогда у нас появляются сделки с очень большой просадкой, и общая устойчивость системы уменьшается. Решить эту проблему довольно просто. Введем в формулу максимальную просадку (Prosadka) по одной сделке:

Fit = (Profit * CountTrade) / (Prosadka/10).

Так как просадка для нас все же менее важна, чем прибыль и количество сделок, мы уменьшили ее вес, разделив на 10. Эта формула уже довольна хороша, и системы, оптимизированные по ней, дают довольно неплохие результаты. Однако можно добавить в нее, например, количество минусовых сделок (KolvoMinus) или размер стопа (Stop), а также поэкспериментировать с различными весами параметров. Я использую также следующие формулы для определения фитнесса:

Fit = Profit/(1+Prosadka/10)* (CountTrade/20);
Fit = Profit/(1+Prosadka/10 + Stop / 10 ) * (CountTrade/10);
Fit = (Profit+KolvoPlus/5) / (1 + Prosadka / 10 + KolvoMinus/5).

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

Если формула построена некорректно, вы не придете ни к какому конечному результату: процесс как бы застрянет между несколькими максимумами.

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

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

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

В таблице 2 представлен краткий перечень таких фильтров. Их мы кодируем аналогичным образом: номер фильтра – один ген, параметры – еще четыре. Таким образом, мы получаем сигнал на вход, который должен быть подтвержден фильтрующим индикатором. Полный сигнал на вход в рынок у нас состоит из 10 генов: 5 – сам сигнал и 5 – фильтр. Аналогичным образом кодируется и сигнал на выход. Также 10 генов: 5 – сигнал и 5 – фильтр. Итого получается одна хромосома длиной 20 генов. Запускаем ГА. Для такого количества генов размер популяции должен составить не менее 1000 особей. В результате работы ГА через 340 поколений получаем результаты, приведенные в таблице 3. Итак, ГА для нас создали механическую торговую систему и оптимизировали ее параметры для данного исторического промежутка. При прогонке по более свежим данным (по которым оптимизация не проводилась) МТС показывает некоторую неустойчивость. На протяжении более недели она достаточно прибыльна. Далее МТС перестает приносить прибыль и становится убыточной. Это и не удивительно, если учесть простоту системы. Для улучшения работы системы будем использовать при фильтрации сигналов на вход и на выход не один фильтр, а, например, по четыре – построенных аналогичным образом. Также можно добавить временной период для возможного входа (например, вход только с 3 до 17 часов – кодируется двумя генами) и временной период для возможного выхода. Возможны также стоп и лимитпределы (в этой статье не рассматриваются). Итого у нас получается 27 генов, описывающих вход, и 27 – выход из рынка. Всего 54 гена в хромосоме. Так как хромосома значительно удлинилась, стоит увеличить и количество особей в популяции. Я использовал популяции в 2000 особей.

После того как ГА отработал и процесс сошелся, получаем результаты. Они представлены в таблице 4. Получившаяся система имеет достаточно неплохие показатели и на свежих исторических данных хорошо ведет себя в течение месяца после оптимизации (9 сделок, 2 убыточные, общая прибыль 400 пунктов).

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

Некоторые пояснения и выводы
Интересный вопрос – выбор временного интервала графиков для поиска МТС. В принципе, механическую торговую систему таким образом можно построить на любых графиках. Но если использовать графики размерностью более 4 часов, то на их форму влияют в основном фундаментальные факторы. А факторы такого типа могут со временем круто поменяться на противоположные (например, преобладающий тренд сменится на горизонтальный коридор). Это не лучшим образом скажется на стабильности работы МТС. Чем ниже мы спускаемся к тиковым графикам, тем больше психологичности в их форме. Однако тиковые графики слишком зашумлены и мало поддаются вообще какому-либо анализу.

Для тестирования я использовал 5-минутные графики EUR/USD с сентября 2003 г. по июнь 2004 г. Принцип тестирования комплекса, построенного описанным выше образом, следующий.

1. Задаются всевозможные сигналы и описываются их параметры.
2. Выбирается функция расчета фитнесса.
3. На достаточно длительном историческом промежутке проводится оптимизация.
4. Систему, полученную в результате оптимизации, прогоняют на данных, идущих непосредственно за промежутком оптимизации.
5. Если система показывает хорошие результаты, промежуток оптимизации сдвигается в будущее на размер свежих данных.
6. После этого процесс повторяют с пункта 3 до тех пор, пока не наступит уверенность в стабильности полученного комплекса.

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

Стоит отметить некоторые трудности, с которыми приходится сталкиваться при разработке таких систем. Во-первых, существуют вполне понятные проблемы с механизмом определения таких инструментов технического анализа, как, например, уровни поддержки и сопротивления, линии тренда, волн и растяжений. Во-вторых, программы, построенные с использованием ГА, очень требовательны к производительности компьютеров. Так, например, при расчете варианта 54 гена в хромосоме, 2000 особей в популяции, на истории в 18000 свечей одно поколение считается на ИнтелПентиуме-4 с частотой 2400 герц примерно 40 минут, а весь расчет занимает больше недели.

Далее двигаться можно в следующих направлениях.

1. Предоставить в распоряжение ГА все инструменты технического анализа, используемые человеком.
2. Значительно усложнить структуру МТС, добавив в нее большое количество сигналов, которые могут одновременно присутствовать в системе, а не только на этапе оптимизации.
3. Привнести в логику МТС элементы искусственного интеллекта – например, нечеткую логику. Это, а также многое другое, позволит создать, пока только теоретически, квинтэссенцию технического анализа – идеальную механическую торговую систему. Священный грааль где-то рядом.

ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ ФОРЕКС

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

СОДЕРЖАНИЕ:

Если путешествия во времени станут возможны, возникнет новая развлекательная индустрия. Назовем ее «Хронотуризм», а ее клиентов – «хронотуристами».

Представим хронотуриста, отправившегося на машине времени в Чехию 1860-х, точнее в город Брно (тогда Брюнне) в год, эдак, 1863-ий.

Что интересного можно было увидеть в провинциальном городке Австрийской империи, пусть и носившим гордый титул «столицы Моравии»?

Кто-то скажет: «Ничего, что там смотреть?» Конечно, если сравнивать Брно-1863 с античными Афинами, древним Римом и Египтом эпохи расцвета Фараонов, «кто-то» будет прав. Ратуша, несколько соборов, оперный театр… Готика, ренессанс и барокко. Кого этим удивишь. Вся старая Европа такая. С севера на юг и с запада на восток.

Проследим за нашим путешественником. Куда он пойдет? Быстрым шагом, нигде не останавливаясь, хронотурист минует «достопримечательности» чинного Брюнне и подходит к Августинскому аббатству Святого Томаша [1] .

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

Вид на монастырский сад Августинского аббатства Святого Томаша [1]

Что пытается разглядеть путешественник во времени? Заглянем из-за его спины.

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

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

Перед ним – внешне ничем не примечательный монах Августинского аббатства Святого Томаша по имени Грегор.

Ученый-самоучка, автор прохладно принятых современниками «Опытов над растительными гибридами» 1866 г., послуживших основой Законов наследования моногенных признаков, впоследствии получивших его имя.

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

Монах и горох, монастырь в Брно, далекий 1863 год…

Грегор Иоганн Мендель (1822-1884) [2]

1. ГЕНЕТИКА И ЕСТЕСТВЕННЫЙ ОТБОР, НАСЛЕДСТВЕННОСТЬ И ИЗМЕНЧИВОСТЬ

1.1. Понятие генетики и естественного отбора

Генетика – «наука о законах наследственности и изменчивости организмов» [3] . По объектам исследования различают генетику человека, животных, растений и микроорганизмов. По применяемым методам – молекулярную, экологическую, медицинскую, биохимическую генетику и т.д.

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

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

1.2. Генетическая информация. ДНК и хромосомы

Каждая клетка живого организма содержит о нем закодированную информацию. Наследственный материал получил название «геном» [5] . Подавляющее большинство геномов, в том числе, геном человека, состоят из ДНК [6] , у ряда вирусов геном формируется из РНК [7] .

Генетическая информация генома комплектуется из генов. «Ген — единица передачи наследственной информации и участок ДНК, влияющий на определенную характеристику организма» [8] . Совокупность генов именуют генотипом [9] .

ДНК в разных формах [8]

С точки зрения химии, ДНК – длинная полимерная молекула в виде двойной спирали, состоящая из различных комбинаций четырех блоков, нуклеотидов. Каждому нуклеотиду присвоена латинская буква: A, G, T, C. За генетическую информацию отвечает порядок следования, чередования нуклеотидов в ДНК – генетический код. Генетические сведения, в конечном итоге, должны быть прочитаны и использованы клеткой при синтезе биополимеров, ее кирпичиков.

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

Человеческий геном состоит из 23 пар хромосом и одной отдельной ДНК [10] . В них зашито 28 тыс. генов.

1.3. Скрещивание, мутация и селекция

При размножении происходит слияние родительских половых клеток, их ДНК образуют ДНК потомства. Синтезируется дочерняя молекула ДНК. Процесс, названый репликацией ДНК [11] , заключается в разделении родительских ДНК на две части, с их последующим обменом и сшиванием в новую, дочернюю ДНК. Исходя из перекрестного характера, он известен, как скрещивание, кроссовер или кроссинговер (cross-over, crossing over).

Репликацию можно рассматривать, как часть более общего биомеханизма: рекомбинации. Рекомбинация – «перераспределение генетического материала (ДНК или РНК) путем разрыва и соединения разных молекул, приводящее к появлению новых комбинаций генов или других нуклеотидных последовательностей» [12] .

Таким образом, генетическая информация от родителей точно передается детям. Обеспечивается наследственность и изменчивость.

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

Процедура естественного отбора интенсифицируется и подправляется селекцией. Селекция пришла на смену простому искусственному отбору и позволяет «воздействовать на растения и животных с целью изменения их наследственных качеств в нужном для человека направлении» [13] . Мощный импульс современной селекции придала генная инженерия.

2. ГЕНЕТИЧЕСКИЙ АЛГОРИТМ. ОПРЕДЕЛЕНИЕ И ПРИНЦИП ДЕЙСТВИЯ

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

Почином в области симуляции природного отбора стали исследования Нильса Баричелли, выполненные им в 1954 г. на компьютерах Принстонского института перспективных исследований. Отцом генетических алгоритмов считают американца Джона Генри Холланда, автора книги «Адаптация в естественных и искусственных системах», Adaptation in Natural and Artificial Systems (1975).

Упрощенно алгоритм создания и функционирования ГА выглядит так:

Схема работы генетического алгоритма [14]

ЭТАП 1. НАЧАЛЬНАЯ ПОПУЛЯЦИЯ И ФУНКЦИЯ ПРИСПОСОБЛЕННОСТИ

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

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

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

Отобранные особи оцениваются, как хорошо они решают поставленную задачу, насколько «жизнеспособны». Делается это через функцию приспособленности (ФП), fitness function.

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

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

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

ЭТАП 2. РАЗМНОЖЕНИЕ. СКРЕЩИВАНИЕ И МУТАЦИЯ

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

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

Для того, чтобы и здесь была некая система, применяют три пути формирования пары:

1) Панмиксия – «папа» и «мама» подбираются случайно.

2) Инбридинг – «папа» (первый родитель) выбирается случайно, а «маму» (второго родителя) ищут максимально похожую на «папу».

3) Аутбридинг – «папа», по-прежнему, случаен, но предпочтение отдают той «маме», которая меньше всех напоминает «сильную половину».

Все очень подобно человеческим судьбам, вы не находите?

Основной посыл – «сильное», «здоровое», если хотите, «красивое» потомство, в свою очередь, способное при скрещивании произвести «хороших и симпатичных» детей.

ЭТАП 3. СЕЛЕКЦИЯ

Согласно установленным критериям, функция приспособленности отбирает лучших из «родившегося» потомства. Они формируют очередное новое поколение, готовое к размножению. Прочим – «дорога на кладбище».

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

В противном случае, по меткому выражению автора одной из статей о ГА [17] , уже сразу, на двух-трех первых циклах, создатель генетического алгоритма получит «альфа-самца», супермена (или супервумен), который/которая подомнет под себя всю популяцию, «взгромоздится на трон», окружит себя копиями-подражателями, и о дальнейшем плавном улучшении детей речь уже не пойдет.

Простейший принцип отбора – «турнирная селекция». После кроссовера случайным образом выбираются пары особей. Победитель в паре. тот у кого значение ФП лучше. Среди других подходов можно отметить вероятностные методы рулетки, ранжирования, равномерного ранжирования и сигма-отсечения [14] .

ЭТАП 4. ФОРМИРОВАНИЕ НОВОГО ПОКОЛЕНИЯ.

Логическое завершение третьего этапа.

Далее, племя генотипов гоняется генетическим алгоритмом по этапам 2-4. И так – до остановки.

Остановка имеет место в трех случаях.

1) Результат достигнут и решение найдено.

2) Количество поколений, предусмотренных ГА на эволюцию, исчерпано.

3) Закончилось время отбора.

3. ПРИМЕР. ГЕНЕТИЧЕСКИЙ АЛГОРИТМ И ДИОФАНТОВО УРАВНЕНИЕ

Суть алгоритмической генетики будет проиллюстрирована на линейном Диофантовом уравнении (ДУ).

Использование генетического алгоритма для поиска корней линейного ДУ – излюбленное рунетовское объяснение смысла ГА для новичков (смотрите, в частности [17] ). Не претендуя на оригинальность, покажем и мы, как работает ГА для этой задачи. Образец привлекает доступностью и наглядностью, и красив математически, что немаловажно.

3.1. Диофантово уравнение и немного истории

Прежде всего, что такое Диофантово уравнение?

Где P – целочисленная функция, обычно полином с целыми коэффициентами, переменные xi также принимают целые значения [18] . Названо по имени древнегреческого математика Диофанта Александрийского.

Линейное ДУ представляется так:

где d – некоторое целое число.

К понятию ДУ примыкает знаменитая «Великая теорема Ферма» [19] , гласящая, что для любого натурального n>2, уравнение x n +y n =z n не имеет целых решений. Другими словами, подобное ДУ неразрешимо. Для n=2, решение лежит на поверхности: x=3, y=4, z=5.

Ироничный французский математик (на то, он и француз) Пьер Ферма в 1637 году на полях книги «Арифметика», все того же Диофанта, написал: «Наоборот, невозможно разложить куб на два куба, биквадрат на два биквадрата, и вообще никакую степень, большую квадрата, на две степени с тем же показателем. Я нашел этому поистине чудесное доказательство, но поля книги слишком узки для него».

Узость полей «Арифметика» Диофанта заставили лучших (и не только) математиков почти 360 лет искать доказательство теоремы Ферма. Только в 1995 году профессор Принстонского университета Эндрю Джон Уайлс публикует наиболее полное (на сегодня) корректное доказательство Великой теоремы Ферма.

3.2. Постановка задачи

Конечно, задание, которое будет стоять перед нашим генетическим алгоритмом, не идет ни в какое сравнение с проблемой Ферма и Уайлса.

ГА должен наметить путь поиска корней линейного ДУ с четырьмя переменными:

3.3. Начальная популяция (родители)

Предположив, что корни уравнения лежат на отрезке [1;30], выберем начальную популяцию из пяти особей (генотипов) – строк, включающих четыре случайных числа (гена) от 1 до 30, потенциальных корней решаемого ДУ:

Особь 1 – (1,28,15,3);

Особь 4 – (23,8,16,19);

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

Результаты обработки сведем в Таблицу 1:

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

Далее, для каждой особи считается левая часть уравнения. Затем, для каждой особи берется модуль разности правой части ДУ (числа 30) и получившегося значения левой части. Таким образом, начинает работать функция приспособленности. Для формализации итоговых данных ФП, вычисляется величина, обратная найденному модулю, и умножается на 100. Полученный показатель назовем «коэффициентом выживания» (кратко, КВ). Чем он выше, тем исследуемый генотип имеет большее право идти дальше.

КВ лежит в диапазоне от 0,75 (Особь 4), худший результат, до 4,17 (Особь2) – «победитель соревнования». Среднее арифметическое значение КВ равно 2,71.

3.4. Скрещивание, первые дети

Переходим к размножению, через скрещивание, к кроссоверу.

Отберем случайным образом пять пар родителей (особей). Генератор случайных чисел настроим так, чтобы он учитывал коэффициенты выживания. Вероятность выпадения особи должна быть пропорциональна ее КВ. Вообразим многомерный куб со ста гранями. На 31-ой грани нанесен значок лучшей Особи2, на 28-ми гранях – значок Особи3, у которой результаты чуть похуже и т.д. Наименьшее количество граней заслужила Особь4 – 6. Число граней пропорционально весу КВ каждой особи.

Кидаем «сто-сторонний кубик» десять раз (пять раз по два). Пары для скрещивания вполне могут иметь следующий вид:

Главный лузер, Особь4, вообще не выпала. Победитель (Особь2) появляется дважды. Остальные участники – крепкие середняки.

Для краткости, рассмотрим потомство одной, первой пары: Особь3-Особь1.

Кроссовер происходит путем разрывов строк (ДНК) каждой особи и соединения получившихся кусочков в ДНК ребенка.

Процесс скрещивания отображен в Таблице 2:

В верхней части представлен генотип родителей. В нижней – детей после трех скрещиваний. Разрыв цепочки родительской ДНК проходит по границе смены цветов, с желтого на зеленый и с зеленого на желтый (вертикальный отрезок розового цвета)

При первом скрещивании, часть ДНК Особи3 с одним геном «13» (желтое поле) по красной стрелке сшивается с фрагментом ДНК Особи 1, строка (28,15,3) на желтом поле. Рождается ребенок1 (13, 28, 15, 3).

Здесь же, кусочек ДНК Особи1 с одним геном «1» (зеленое поле) по синей стрелке сшивается с фрагментом ДНК Особи 3, строка (5,7,3) на зеленом поле. Рождается ребенок2 (1, 5, 7, 3).

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

Итог – от пары родителей Особь3-Особь1 рождаются 6 детей: ребенок1, ребенок2…ребенок6.

Настало время проверить потомство от первой пары на функцию выживаемости и сравнить результат с достижениями «пап и мам».

Строим Таблицу 3, аналогичную Таблице 1:

Средний коэффициент выживания повысился до 2,81 (у родителей КВ=2,70). Лучшее дитя – Ребенок2 существенно превзошло лучшего родителя (Особь2). По КВ: 7,14 против 4,17. Что уж говорить о «родных папах и мамах» (Особей 3 и 1) с КВ 3,84 и 1,19 соответственно.

3.5. Продолжение процесса и остановка

Далее – стандартные этапы ГА.

Скрещиваются 4 оставшиеся пары. К детям применяется функция приспособленности. Отбираются лучшие индивидуумы, по определенной системе «разбавляются» не очень удачными ровесниками и вновь – скрещивание, селекция и формирование нового поколения. Вплоть до остановки алгоритма согласно условиям, описанными в общем виде выше.

Результат может считаться достигнутым, когда левая часть уравнения будет отличаться от правой (числа 30), допустим, не более, чем на 0,00001 или, предположим, когда КВ преодолеет отметку 10000. Все решает разработчик.

Так интересно соединяются биогенетика гороха и алгогенетика уравнения.

ПРИМЕЧАНИЯ И ССЫЛКИ

(источник – Википедия, если не оговорено иное)

    «Старобрненский монастырь» «Мендель, Грегор Иоганн» «Генетика» «Естественный отбор» «Геном» ДНК – дезоксирибонуклеиновая кислота — одна из трех макромолекул (две другие – РНК и белки), обеспечивающая хранение, передачу из поколения в поколение и реализацию генетической программы развития и функционирования живых организмов РНК – одна из трех макромолекул (две другие – ДНК и белки), которые содержатся в клетках всех живых организмов и играют важную роль в кодировании, прочтении, регуляции и выражении генов «Дезоксирибонуклеиновая кислота» «Генотип» «Геном человека» «Репликация ДНК» «Рекомбинация (биология)» «Селекция» «Генетический алгоритм» «Холланд, Джон Генри» «Функция приспособленности» «Генетический алгоритм. Просто о сложном», Habr, 20.09.2022 «Диофантово уравнение» «Великая теорема Ферма»

ИСПОЛЬЗУЕМЫЕ СОКРАЩЕНИЯ

ДНК – дезоксирибонуклеиновая кислота
ГА – генетический алгоритм
ФП – функция приспособленности
ДУ – Диофантово уравнение
КВ – коэффициент выживания (для раздела 3 текста)

С использованием генетических алгоритмов для прогнозирования финансовых рынков — 2022 — Talkin go money

Владимир Черкашенко: финансовый инженер и оверфиттинг (Август 2022).

Table of Contents:

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

Учебное пособие: Стратегии сбора акций

Что такое генетические алгоритмы?
Генетические алгоритмы (GA) — это методы решения проблем (или эвристика), которые имитируют процесс естественной эволюции. В отличие от искусственных нейронных сетей (ANN), предназначенных для работы как нейроны в мозге, эти алгоритмы используют концепции естественного отбора для определения наилучшего решения проблемы. В результате GA обычно используются в качестве оптимизаторов, которые корректируют параметры для минимизации или максимизации некоторой меры обратной связи, которые затем могут использоваться независимо или в конструкции ANN.

На финансовых рынках генетические алгоритмы чаще всего используются для нахождения наилучших комбинационных значений параметров в правилах торговли, и их можно встроить в модели ANN, предназначенные для выбора акций и определения сделок. Несколько исследований показали, что эти методы могут оказаться эффективными, в том числе «Генетические алгоритмы: генезис оценки запасов» (2004) Рамы и «Применение генетических алгоритмов в оптимизации добычи данных на фондовом рынке» (2004) Лин, Цао, Ванг , Чжан. (Чтобы узнать больше об ANN, см. Нейронные сети: Прогнозирование прибыли .)

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

Например, правило торговли может включать использование таких параметров, как Moving Average Convergence-Divergence (MACD), экспоненциальная скользящая средняя (EMA) и стохастика. Затем генетический алгоритм вводит значения в эти параметры с целью максимизации чистой прибыли. Со временем появляются небольшие изменения, и те, которые оказывают желательное воздействие, сохраняются для следующего поколения.

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

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

Эти три оператора затем используются в пятиэтапном процессе:

  1. Инициализировать случайную совокупность, где каждая хромосома n — длина, при этом n является числом параметры. То есть случайное число параметров устанавливается с помощью n элементов каждый.
  2. Выберите хромосомы или параметры, которые увеличивают желаемые результаты (предположительно, чистую прибыль).
  3. Применить операторов мутации или кроссовера выбранным родителям и создать потомство.
  4. Рекомбинируйте потомство и текущую популяцию, чтобы сформировать новую популяцию с оператором выбора.
  5. Повторите шаги два-четыре.

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

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

При использовании этих приложений трейдеры могут определять набор параметров, которые затем оптимизируются с использованием генетического алгоритма и набора исторических данных. Некоторые приложения могут оптимизировать, какие параметры используются, и значения для них, в то время как другие в основном ориентированы на простое оптимизацию значений для заданного набора параметров. (Чтобы узнать больше об этих стратегиях, полученных с помощью программы, см. Power of Program Trades .)

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

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

Нижняя линия
Генетические алгоритмы — это уникальные способы решения сложных проблем путем использования силы природы. Применяя эти методы для прогнозирования цен на ценные бумаги, трейдеры могут оптимизировать торговые правила, определяя наилучшие значения для каждого параметра для данной безопасности. Тем не менее, эти алгоритмы не являются Святым Граалем, и трейдеры должны быть осторожны, чтобы выбрать правильные параметры, а не подгонка кривой (над посадкой). (Чтобы узнать больше о рынке, ознакомьтесь с Слушайте рынок, а не его эксперты> .)

Мой эксперимент в генетических алгоритмах + исходный код

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

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

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

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

(Прошу прощения за качество гифок, очень сильно сожралось при уменьшении размеров до разрешённых на пикабу)

После одной ночи работы программы стали заметны первые зачатки «разума»:

После двух ночей «разум» заметно улучшился, вместе с продолжительностью жизни ботов:

Для особо упоротых товарищей (вроде меня), и для желающих поржать над моим кривым кодом, выкладываю исходник всей этой истории. Откомментировал в коде всё, что смог.
Ссылка на исходник — http://almostgames.ru/games/evol.gmz
Спасибо за внимание.

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

Найдены дубликаты

Лига Разработчиков Видеоигр

4.1K поста 18.7K подписчиков

Правила сообщества

ОБЩИЕ ПРАВИЛА:

— Уважайте чужой труд и используйте конструктивную критику

— Не занимайтесь саморекламой, пишите качественные и интересные посты

— Не употребляйте мат без необходимости

СТОИТ ПУБЛИКОВАТЬ:

— Посты о Вашей игре с историей её разработки и описанием полученного опыта

— Обучающие материалы, туториалы

— Интервью с опытными разработчиками

— Анонсы бесплатных мероприятий для разработчиков и истории их посещения;
— Ваши работы, если Вы художник/композитор и хотите поделиться ими на безвозмездной основе

НЕ СТОИТ ПУБЛИКОВАТЬ:

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

— Посты, содержащие только идею игры

— Посты, единственная цель которых — набор команды для разработки игры, для этих целей больше подойдёт Discord-сервер сообщества

— Посты, не относящиеся к тематике сообщества

Подобные посты по решению администрации могут быть перемещены из сообщества в общую ленту.

ЗАПРЕЩЕНО:

— Публиковать бессодержательные посты с рекламой Вашего проекта (см. следующий пункт), а также все прочие посты, содержащие рекламу/рекламные интеграции

— Выдавать чужой труд за свой

Подобные посты будут перемещены из сообщества в общую ленту, а их авторы по решению администрации могут быть внесены в игнор-лист сообщества.

О РАЗМЕЩЕНИИ ССЫЛОК:

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

— Пост должен быть содержательным и интересным для пользователей, нести пользу для сообщества

— Ссылка должна размещаться непосредственно в начале или конце поста и только один раз

— Cсылка размещается в формате: «Страница игры в Steam: URL»

Если хотите обратной связи с другими программистами — научитесь работать с Github. Там Вы можете найти огромное количество других интересных решений (правда не видел delphi не самый популярный язык).

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

Конечно надо это дело усложнять.

Я бы предложил создать модель небольшого биома: трава — зайцы — волки.

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

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

Если чуть разобраться в теме, делается очень просто. После подобной реализации я усложнил задачу, сделал траву, травоядных и хищников (3 класса-реализации). Трава — это трава, но появляется после съедения/смерти животного (сразу несколько штук). у животных есть характеристики, скорость, размер (влияет в основном на ср. максимальный возраст), зоркость, плодовитость. В зависимости от характеристик менялись цвета и размеры самих кружочков на карте. В этих самих характеристиках и заключался генетический алгоритм. Каждое животное, когда рождалось, могло немного мутировать один из показателей, в итоге через N поколений имелся целый набор «слонов», «антилоп», «зайцев» и тд. Для баланса нужно я ограничил максимальную сумму всех характеристик. Так же, например, размер отрицательно влиял на плодовитость.

есть один баян на эту тему.

про объекты ТБаран и ТСлон )

Погуглите, если не лень.

Хахах))) Очень странное решение, превращать в «интерьер») Хотя для «лишь бы сдать» может и норм)

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

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

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

собственно сам мир описан — нужно было просто создать обработчик поведения персонажа )

Или я чего-то не знаю, или у Вас очень странные понятия о несложной нейронной сети) Там столько входных параметров в игре (для нейронов первого слоя), что можно охренеть)) Я правда, по моему, не занимался «принятием решений», перцептрон там, сеть Кохоннена (кластеризация). От нефиг делать либу замутил https://github.com/A1essandro/neural-network . Правда на пыхе, и содержит ошибку в проектировании, хочу на Java переписать, сейчас думаю как исправить эту самую ошибку.

Если у Вас есть хорошая статья по принятию решений и сетям, дайте почитать, пожалуйста.

у меня нет какой то конкретной статьи.

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

собственно суть сводилась определению «верно/неверно». верно — коэффициенты не трогаем, неверно — коэффициенты корректируем.

Обратное распространение ошибки. Понятно.

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

собственно там не так уж много состояний окружающей среды.

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

а второй проблемой стал вопрос результата, точнее — что именно считать за результат.

вообще мне всегда нейронка нравилась больше генетических алгоритмов.

Просто не научился ещё на тот момент. Но пару тысяч поколений спустя он исправился.

@Neptun, на гитхаб не судьба была выложить ?
Или уж совсем начинающий ?

Автор, перезалей код) Хочу поковыряться. Может чему научусь!

Ссылка на исходник всё ещё рабочая.

А есть исполняемый файл?

Есть. Только он немного отличается от того, что в исходнике и на гифках. В нём боты ещё и дерутся друг с другом и жрут трупы.
http://almostgames.ru/games/evol.exe

На самом деле очень круто наблюдать как они изучают новые движения. Например у одного получилось съесть траву шагнув назад и вперед и в следующем поколении уже несколько ботов пытаются ходить назад и вперед не понимая, что стоят на пустом месте, а потом кто-то обошел яд съев траву и новое поколение уже начинает нормально его избегать. МОЖЕТ КОГДА У ТЕБЯ БУДЕТ ВРЕМЯ ТЫ ОБЪЯСНИШЬ ПОДРОБНЕЕ УСТРОЙСТВО «МАТРИЦЫ-МОЗГА»? Не настаиваю)

У меня что то не запустился exeшник — было бы интересно поглядеть, вываливается сразу с ошибкой (win7x64).

Тоже развлекаюсь генетическими алгоритмами, но твой примерчик уже тянет на Indi world 🙂 Круто!

Довольно давно делал решение задачи коммивояжера на Delphi, используя ГА.

Я на днях запилил примерчик на javascript на тему использования ГА

А видел — фразу Hello, World собирают, используя методику ГА?

Хед фёрст джава, паттерны проектирования, статьишки всякие в интернетах.

есть это в открытом доступе или только покупать ?

Знаком и с тем и с другим =)
В амёбах даже успешного бойца воспитал — http://amebas.ru/amoebas/6659/

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

Синие квадратики — боты. По аквариуму разбросаны стены (серые), еда (зелёная) и яд (красный). Боты бегают по полю, и пытаются выжить. 8 самых живучих дают жизнь новому поколению, по 8 потомков каждый. У неготорых из потомков мутирует один или несколько генов.
У каждого бота есть свой геном — набор из 64 чисел, от 0 до 63 каждое (на гифках внизу написаны геномы лидеров предыдущего поколения).
Каждая цифра в ячейке генома обозначает какую-то конкретную функцию бота, например 1 — посмотреть прямо перед собой. В зависимости от того, каким был результат выполнения команды, управление перескакивает на другую ячейку генома. Например на картинке изображён кусочек генома. В первой клетке стоит цифра 1 — значит бот смотрит прямо перед собой. В зависимости от того, что он там увидел он переключается на другую ячейку генома. Например, если он увидел стену, то следующей он будет выполнять команду 23, а если увидел еду, то выполнит комадну 9. Таким образом, весь его геном — это алгоритм его действий в аквариуме.
Благодаря системе отбора самых живучих и незначительным мутациям, происходит постепенная адаптация генома к условиям среды, и боты становятся всё умнее и умнее.

Русские Блоги

Генетический алгоритм (Genetic Algorithm) подробное объяснение и анализ кода Matlab и соответствующий код реализации набора инструментов gaot

Из принципа-учебного примера-кода

1. Определение

Генетический алгоритм (GA) имитирует биологическую эволюцию ДарвинаЕстественный отбор и генетический механизмРасчетная модель процесса биологической эволюции является своего рода симуляциейЕстественная эволюцияПроцесс поиска оптимального решения.

Основные особенности

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

объекты: Все люди в группе

Основная операция: Селекция, кроссовер и мутация

Основное содержание:

  • Кодирование параметров
  • Начальная настройка группы
  • Дизайн фитнес-функции
  • Генетические манипуляции дизайн
  • Настройка параметров управления

2 общих слова:

Генотип (генотип):
Внутреннее выражение хромосомы признака.

Фенотип:
Внешние характеристики хромосомно определяемых признаков

Кодирование (кодирование):
Генетическая информация в ДНК расположена по определенной схеме на длинной цепочке.

Декодирование (декодирование):

Индивидуальный (индивидуальный):
относится к объекту с хромосомами;

Население (население):
Коллекция людей, количество людей в коллекции называется популяцией

Фитнес (фитнес):
измеряет приспособляемость вида к окружающей среде.

3 понимание изображения

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

Вот несколько способов ввести «прыжок кенгуру».

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

Общие шаги генетического алгоритма:

  1. Случайно сгенерированные популяции.
  2. В соответствии со стратегией оценивается, соответствует ли пригодность индивидуума критерию оптимизации.Если это так, выводится лучшее индивидуум и его оптимальное решение, и процесс заканчивается. В противном случае перейдите к следующему шагу.
  3. Родители отбираются в соответствии с их физической подготовкой, лица с высокой физической подготовленностью выбираются с высокой вероятностью, а лица с низкой физической подготовленностью исключаются.
  4. Используйте родительские хромосомы для скрещивания в соответствии с определенным методом для получения потомства.
  5. Мутация хромосом потомства.
  6. Создайте новое поколение популяции из кроссовера и мутации и возвращайтесь к шагу 2, пока не будет найдено оптимальное решение.

Конкретный метод двоичного кодирования, выбор колеса рулетки, одноточечный кроссовер и базовая вариация битов являются наиболее простыми и понятными. ссылка
https://blog.csdn.net/u012422446/article/details/68061932

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

Пример алгоритма

реализация кода Matlab

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

% Максимальное значение следующей функции%

Он включает в себя расчет длины хромосомы:

Выразите значение x в 10-битной двоичной форме как двоичную проблему, 10-битное двоичное число обеспечивает разрешение каждого бита(10-0)/(2^10-1)≈0.01

Дискретизируйте переменную область [0,10] в двоичную область [0,1023], x = 0 + 10 * b / 1023, где b — двоичное число в [0,1023].

Следуйте алгоритму алгоритма:

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

Каждая функция сохраняется в виде файла

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

1. Инициализация

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

2 Рассчитать значение целевой функции

decodechrom.m
(в основном для расщепления хромосом, когда есть несколько переменных, пример здесь не нужно расщеплять, pop1 = pop)

3 Рассчитать фитнес-функцию

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

4 Выбор

Выбор рулетки.
Принцип заключается в следующем
Ниже приведен пример выбора рулетки:

Если есть 5 хромосом, их пригодность составляет 5, 8, 3, 7, 2 соответственно.

Тогда общая пригодность: F = 5 + 8 + 3 + 7 + 2 = 25.

Тогда вероятность выбора каждого отдельного человека равна:

α1 = ( 5 / 25 ) * 100% = 20%=0.2

α2 = ( 8 / 25 ) * 100% = 32%=0.32

α3 = ( 3 / 25 ) * 100% = 12%=0.12

α4 = ( 7 / 25 ) * 100% = 28%=0.28

α5 = ( 2 / 25 ) * 100% = 8%=0.08

Как использовать код для его достижения?
Мысль:

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

eg:
Когда точка достигает 0,25, она находится после α1 и в сегменте α2, поэтому индивидуум α2 выбирается один раз.
Произведите случайную генерацию 0.55 снова в сегменте α3, поэтому индивидуум α3 выбирается один раз.

Чтобы упростить сортировку, точки сначала генерируются и располагаются по порядку и сравниваются от малого к большому.
— это следующий код:

5 Крест

Одноточечный кроссовер с вероятностью 0,6 случайным образом выбирает скрещивание между двумя смежными отдельными хромосомами и случайным образом выбирает местоположение скрещивания.

Что такое генетические алгоритмы

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

Естественный отбор

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

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

5 шагов генетического алгоритма

Процесс обучения генетического алгоритма делится на 5 этапов:

  1. Начальная популяция
  2. Функция силы особи
  3. Отбор наиболее сильных решений
  4. Обмен характеристиками между двумя особями
  5. Мутация
  6. Новая итерация с созданием начальной популяции

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

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

Популяция, хромосомы и гены

Функция силы

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

Отбор

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

Скрещивание

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

Точка скрещивания

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

После обмена генами между родителями потомство добавляется в новую популяцию.

Мутация

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

Пример мутации особи

Завершение алгоритма

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

Псевдокод процесса обучения генетического алгоритма:

Генетические алгоритмы в глубоком обучении

В глубоком обучении с помощью генетических алгоритмов оптимизируются параметры нейросети. В качестве особей популяции выступают сами параметры. Введение в state-of-the-art использование генетических алгоритмов для задач глубокого обучения находится по ссылке .

Документация

Некоторые опции перечислены в italics . Эти опции не появляются в листинге это optimoptions возвращается. Видеть почему’ optimoptions скрывает эти значения опции, см. Опции, которые Скрывает optimoptions.

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

Постройте опции

PlotFcn задает функцию построения графика или функции, вызванные на каждой итерации ga или gamultiobj . Установите PlotFcn опция, чтобы быть встроенным именем функции построения графика или указателем на функцию построения графика. Можно остановить алгоритм в любое время путем нажатия кнопки Stop на окне графика. Например, чтобы отобразить лучшее значение функции, установите options можно следующим образом:

Чтобы отобразить несколько графиков, используйте массив ячеек встроенных имен функции построения графика или cell-массива указателей на функцию:

где @plotfun1 , @plotfun2 , и так далее указатели на функцию в функции построения графика. Если вы задаете больше чем одну функцию построения графика, все графики появляются как подграфики в том же окне. Щелкните правой кнопкой по любому подграфику, чтобы получить увеличенную версию в отдельном окне рисунка.

Доступные функции построения графика для ga или для gamultiobj :

‘gaplotscorediversity’ строит гистограмму баллов при каждой генерации.

‘gaplotstopping’ уровни критерия остановки графиков.

‘gaplotgenealogy’ строит генеалогию индивидуумов. На линии от одной генерации до следующего наносят цветную маркировку можно следующим образом:

Красные линии указывают на дочерние элементы мутации.

Синие линии указывают на перекрестные дочерние элементы.

Черные линии указывают на элитных индивидуумов.

‘gaplotscores’ строит множество индивидуумов при каждой генерации.

‘gaplotdistance’ строит среднее расстояние между индивидуумами при каждой генерации.

‘gaplotselection’ строит гистограмму родительских элементов.

‘gaplotmaxconstr’ строит максимальное нелинейное нарушение ограничений при каждой генерации. Для ga , доступный только, когда NonlinearConstraintAlgorithm опцией является ‘auglag’ (значение по умолчанию для проблем нецелого числа). Поэтому не доступный для ограниченных целым числом проблем, когда они используют ‘penalty’ нелинейный ограничительный алгоритм.

Можно также создать и использовать собственную функцию построения графика. Структура Функций построения графика описывает структуру пользовательской функции построения графика. Передайте любую пользовательскую функцию как указатель на функцию.

Следующие функции построения графика доступны для ga только:

‘gaplotbestf’ строит лучшее значение баллов и средний счет по сравнению с генерацией.

‘gaplotbestindiv’ строит векторные записи индивидуума с лучшим значением функции фитнеса в каждой генерации.

‘gaplotexpectation’ строит ожидаемое количество дочерних элементов по сравнению с необработанными баллами при каждой генерации.

‘gaplotrange’ строит минимум, максимум и средние значения баллов в каждой генерации.

Следующие функции построения графика доступны для gamultiobj только:

‘gaplotpareto’ строит переднюю сторону Парето для первых двух целевых функций.

‘gaplotparetodistance’ строит столбчатую диаграмму расстояния каждого индивидуума от его соседей.

‘gaplotrankhist’ строит гистограмму рангов индивидуумов. Индивидуумы ранга 1 находятся на границе Парето. Индивидуумы ранга 2 ниже, чем по крайней мере один ранг 1 индивидуум, но не ниже, чем какие-либо индивидуумы от других рангов и т.д.

‘gaplotspread’ строит средний спред в зависимости от номера итерации.

Структура функций построения графика

Первая линия функции построения графика имеет эту форму:

Входные параметры к функции

options — Структура, содержащая все текущие настройки опций.

state — Структура, содержащая информацию о текущем поколении. Структура состояния описывает поля state .

flag — Описание этапа алгоритм находится в настоящее время в. Для получения дополнительной информации см. Опции Выходной функции.

Передача Дополнительных Параметров объясняет, как предоставить дополнительные параметры функции.

Выходной аргумент state структура состояния также. Передайте входной параметр, измененный, если вам нравится; смотрите Изменение Структуры состояния. Чтобы остановить итерации, установите state.StopFlag к непустому вектору символов, такому как ‘y’ .

Структура состояния

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

Generation — Номер текущего поколения.

StartTime — Время, когда генетический алгоритм, запущенный, возвращенный tic .

StopFlag — Причина остановки, вектора символов.

LastImprovement — Генерация, при которой произошло последнее улучшение значения фитнеса.

LastImprovementTime — Время, в которое произошло последнее улучшение.

Best — Вектор, содержащий лучшую оценку в каждой генерации.

how — ‘augLag’ нелинейный ограничительный алгоритм сообщает об одном из следующих действий: ‘Infeasible point’ , ‘Update multipliers’ , или ‘Increase penalty’ ; смотрите Увеличенный лагранжевый Генетический алгоритм.

FunEval — Совокупное число вычислений функции.

Expectation — Ожидание выбора индивидуумов.

Selection — Индексы индивидуумов выбраны для элиты, перекрестного соединения и мутации.

Population — Население в текущем поколении.

Score — Множество текущего населения.

NonlinIneq — Нелинейные ограничения неравенства в текущей точке, представьте только, когда нелинейная ограничительная функция задана, нет никаких целочисленных переменных, flag не ‘interrupt’ , и NonlinearConstraintAlgorithm ‘auglag’ .

NonlinEq — Нелинейные ограничения равенства в текущей точке, представьте только, когда нелинейная ограничительная функция задана, нет никаких целочисленных переменных, flag не ‘interrupt’ , и NonlinearConstraintAlgorithm ‘auglag’ .

EvalElites — Логическое значение, указывающее, ли ga выполняет функцию фитнеса элитных индивидуумов. Первоначально, этим значением является true . В первом поколении, если элитные индивидуумы оценивают к их предыдущим значениям (который указывает, что функция фитнеса детерминирована), затем это значение становится false по умолчанию для последующих итераций. Когда EvalElites false , ga не переоценивает функцию фитнеса элитных индивидуумов. Можно заменить это поведение в пользовательской функции построения графика или пользовательской выходной функции путем изменения выхода state.EvalElites .

HaveDuplicates — Логическое значение, указывающее, ли ga добавляют дублирующиеся индивидуумы для начальной генеральной совокупности. ga использует маленькую относительную погрешность, чтобы определить, дублирован ли индивидуум или уникален. Если HaveDuplicates true то ga определяет местоположение уникальных индивидуумов и выполняет функцию фитнеса только однажды для каждого уникального индивидуума. ga копирует фитнес и ограничительные значения функции, чтобы скопировать индивидуумов. ga повторяет тест в каждой генерации, пока все индивидуумы не уникальны. Тест берет, заказывают n*m*log(m) операции, где m численность населения и n nvars . Чтобы заменить этот тест в пользовательской функции построения графика или пользовательской выходной функции, установите выход state.HaveDuplicates к false .

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

Population — Население в текущем поколении

Score — Множество текущего населения, Population — nObjectives матрица, где nObjectives количество целей

Generation — Номер текущего поколения

StartTime — Время, когда генетический алгоритм, запущенный, возвращенный tic

StopFlag — Причина остановки, вектора символов

FunEval — Совокупное число вычислений функции

Selection — Индексы индивидуумов выбраны для элиты, перекрестного соединения и мутации

Rank — Вектор из рангов членов в населении

Distance — Вектор из расстояний каждого члена населения самому близкому соседнему члену

AverageDistance — Стандартное отклонение (не средний) Distance

Spread — Вектор, где записи являются распространением в каждой генерации

mIneq — Количество нелинейных ограничений неравенства

mEq — Количество нелинейных ограничений равенства

mAll — Общее количество нелинейных ограничений, mAll = mIneq + mEq

C — Нелинейные ограничения неравенства в текущей точке, PopulationSize — mIneq матрица

Ceq — Нелинейные ограничения равенства в текущей точке, PopulationSize — mEq матрица

isFeas — Выполнимость населения, логического вектора с PopulationSize элементы

maxLinInfeas — Максимальная недопустимость относительно линейных ограничений для населения

Опции населения

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

PopulationType задает тип входа к функции фитнеса. Типы и их ограничения:

‘doubleVector’ — Используйте эту опцию, если индивидуумы в населении имеют, вводят double . Используйте эту опцию для частично-целочисленного программирования. Это значение по умолчанию.

‘bitstring’ — Используйте эту опцию, если у индивидуумов в населении есть компоненты, которые являются 0 или 1 .

Внимание

Индивидуумы в Bit string население является векторами из типа double , не строки или символы.

Для CreationFcn и MutationFcn , используйте ‘gacreationuniform’ и ‘mutationuniform’ или указатели на пользовательские функции. Для CrossoverFcn , используйте ‘crossoverscattered’ , ‘crossoversinglepoint’ , ‘crossovertwopoint’ , или указатель на пользовательскую функцию. Вы не можете использовать HybridFcn , и ga игнорирует все ограничения, включая границы, линейные ограничения и нелинейные ограничения.

‘custom’ — Указывает на пользовательский тип населения. В этом случае необходимо также использовать пользовательский CrossoverFcn и MutationFcn . Необходимо обеспечить или пользовательскую функцию создания или InitialPopulationMatrix . Вы не можете использовать HybridFcn , и ga игнорирует все ограничения, включая границы, линейные ограничения и нелинейные ограничения.

PopulationSize задает, сколько индивидуумов там находится в каждой генерации. С размером значительной части населения генетический алгоритм ищет пробел решения более тщательно, таким образом, уменьшая шанс, что алгоритм возвращает локальный минимум, который не является глобальным минимумом. Однако размер значительной части населения также заставляет алгоритм запускаться более медленно. Значением по умолчанию является ’50 when numberOfVariables <= 5, else 200′ .

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

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

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

‘gacreationuniform’ создает случайную начальную генеральную совокупность с равномерным распределением. Это — значение по умолчанию, когда нет никаких линейных ограничений, или когда существуют целочисленные ограничения. Равномерное распределение находится в области значений начальной генеральной совокупности ( InitialPopulationRange ). Значения по умолчанию для InitialPopulationRange [-10;10] для каждого компонента или [-9999;10001] когда существуют целочисленные ограничения. Эти границы смещены и масштабируются, чтобы совпадать с любыми существующими границами lb и ub .

Внимание

Не используйте ‘gacreationuniform’ когда у вас есть линейные ограничения. В противном случае ваше население не может удовлетворить линейным ограничениям.

‘gacreationlinearfeasible’ значение по умолчанию, когда существуют линейные ограничения и никакие целочисленные ограничения. Этот выбор создает случайную начальную генеральную совокупность, которая удовлетворяет всем границам и линейным ограничениям. Если существуют линейные ограничения, ‘gacreationlinearfeasible’ создает многих индивидуумов на контурах области ограничений и создает хорошо рассеянное население. ‘gacreationlinearfeasible’ игнорирует InitialPopulationRange . ‘gacreationlinearfeasible’ вызовы linprog создать выполнимое население относительно границ и линейных ограничений.

‘gacreationnonlinearfeasible’ функция создания по умолчанию для ‘penalty’ нелинейный ограничительный алгоритм. Для получения дополнительной информации смотрите Параметры ограничения.

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

Ваша функция создания должна иметь следующий синтаксис вызова.

Входные параметры к функции:

Genomelength — Количество независимых переменных для функции фитнеса

FitnessFcn — Функция фитнеса

Функция возвращает Population , начальная генеральная совокупность для генетического алгоритма.

Передача Дополнительных Параметров объясняет, как предоставить дополнительные параметры функции.

Внимание

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

InitialPopulationMatrix задает начальную генеральную совокупность для генетического алгоритма. Значением по умолчанию является [] , в этом случае ga использует CreationFcn по умолчанию создать начальную генеральную совокупность. Если вы вводите непустой массив в InitialPopulationMatrix , массив должен иметь не больше, чем PopulationSize строки, и точно nvars столбцы, где nvars количество переменных, второго входа к ga или gamultiobj . Если у вас есть начальная генеральная совокупность partial, означая меньше, чем PopulationSize строки, затем генетический алгоритм вызывает CreationFcn сгенерировать остающихся индивидуумов.

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

InitialPopulationRange указывает диапазон векторов в начальной генеральной совокупности, которая сгенерирована gacreationuniform функция создания. Можно установить InitialPopulationRange быть матрицей с двумя строками и nvars столбцы, каждый столбец которых имеет форму [lb;ub] , где lb нижняя граница и ub верхняя граница для записей в той координате. Если вы задаете InitialPopulationRange чтобы быть 2 1 вектор, каждая запись расширена до постоянной строки длины nvars . Если вы не задаете InitialPopulationRange , значением по умолчанию является [-10;10] ( [-1e4+1;1e4+1] для ограниченных целым числом проблем), измененный, чтобы совпадать с любыми существующими границами. ‘gacreationlinearfeasible’ игнорирует InitialPopulationRange . Смотрите Область значений Начальной буквы Набора для примера.

Опции масштабирования фитнеса

Масштабирование фитнеса преобразует необработанные баллы фитнеса, которые возвращены функцией фитнеса в значения в области значений, которая подходит для функции выбора.

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

‘fitscalingrank’ — Функция масштабирования фитнеса по умолчанию, ‘fitscalingrank’ , масштабирует необработанные баллы на основе ранга каждого индивидуума вместо его счета. Ранг индивидуума является своим положением в отсортированных баллах. Индивидуум с рангом r масштабировал счет, пропорциональный 1 / r . Таким образом, масштабированный счет самого подходящего индивидуума пропорционален 1, масштабированный счет следующего самого подходящего пропорционален 1 / 2 , и так далее. Займите место масштабирование фитнеса удаляет эффект распространения необработанных баллов. Квадратный корень заставляет плохо оцениваемых индивидуумов более близко равняться в счете, сравненном с выигрышем ранга. Для получения дополнительной информации смотрите, что Фитнес Масштабируется.

‘fitscalingprop’ — Пропорциональное масштабирование делает масштабированное значение индивидуума пропорциональным его необработанному счету фитнеса.

‘fitscalingtop’ — Главное масштабирование масштабирует главных индивидуумов одинаково. Можно изменить главное масштабирование с помощью дополнительного параметра:

quantity задает количество индивидуумов, которые присвоены положительные масштабированные значения. quantity может быть целое число от 1 до численности населения или части от 0 до 1 определения части численности населения. Значением по умолчанию является 0.4 . Каждый из индивидуумов, которые производят потомков, присвоен равное масштабированное значение, в то время как остальные присвоены значение 0. Масштабированные значения имеют форму [01/n 1/n 0 0 1/n 0 0 1/n. ].

‘fitscalingshiftlinear’ — Переключите линейные шкалы масштабирования необработанные баллы так, чтобы ожидание самого подходящего индивидуума было равно постоянному названному rate умноженный на среднюю оценку. Можно изменить rate параметр:

Значение по умолчанию rate 2 .

Указатель на функцию позволяет вам записать свою собственную функцию масштабирования.

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

Входные параметры к функции:

scores — Вектор из скаляров, один для каждого члена населения

nParents — Количество родительских элементов необходимо от этого населения

Функция возвращает expectation , вектор-столбец скаляров той же длины как scores , предоставление масштабированных значений каждого члена населения. Сумма записей expectation должен равняться nParents .

Передача Дополнительных Параметров объясняет, как предоставить дополнительные параметры функции.

Смотрите, что Фитнес Масштабируется для получения дополнительной информации.

Опции выбора

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

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

gamultiobj использование только ‘selectiontournament’ функция выбора.

‘selectionstochunif’ — ga функция выбора по умолчанию, ‘selectionstochunif’ , размечает линию, в которой каждый родительский элемент соответствует разделу линии длины, пропорциональной ее масштабированному значению. Алгоритм проходит линия с шагом равного размера. На каждом шаге алгоритм выделяет родительский элемент от раздела, на который это приземляется. Первый шаг является универсальным случайным числом меньше, чем размер шага.

‘selectionremainder’ — Родительские элементы присвоений выбора остатка детерминировано от целой части масштабированного значения каждого индивидуума и затем используют выбор рулетки на остающейся дробной части. Например, если масштабированное значение индивидуума 2.3, тот индивидуум перечислен дважды как родительский элемент, потому что целая часть равняется 2. После того, как родительские элементы были присвоены согласно целым частям масштабированных значений, остальная часть родительских элементов выбраны стохастическим образом. Вероятность, что родительский элемент выбран на этом шаге, пропорциональна дробной части своего масштабированного значения.

‘selectionuniform’ — Универсальный выбор выбирает родительские элементы с помощью ожиданий и количества родительских элементов. Универсальный выбор полезен для отладки и тестирования, но не является очень эффективной поисковой стратегией.

‘selectionroulette’ — Выбор рулетки выбирает родительские элементы путем симуляции колеса рулетки, в котором область раздела колеса, соответствующего индивидууму, пропорциональна ожиданию индивидуума. Алгоритм использует случайное число, чтобы выбрать один из разделов с вероятностью, равной ее области.

‘selectiontournament’ — Выбор турнира выбирает каждый родительский элемент путем выбора size проигрыватели наугад и затем выбор лучшего индивидуума из того набора, чтобы быть родительским элементом. size должны быть по крайней мере 2. Значение по умолчанию size 4 . Установите size к различному значению можно следующим образом:

Когда NonlinearConstraintAlgorithm Penalty , ga использование ‘selectiontournament’ с размером 2 .

Указатель на функцию позволяет вам записать свою собственную функцию выбора.

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

ga предоставляет входным параметрам expectation , nParents , и options . Ваша функция возвращает индексы родительских элементов.

Входные параметры к функции:

Для ga , expectation вектор-столбец масштабированной физической формы каждого члена населения. Масштабирование прибывает из Опций Масштабирования Фитнеса.

Совет

Можно гарантировать, что у вас есть вектор-столбец при помощи expectation(:,1) . Например, edit selectionstochunif или любая из других встроенных функций выбора.

Для gamultiobj , expectation матрица, первый столбец которой является отрицанием ранга индивидуумов, и чей второй столбец является мерой по расстоянию индивидуумов. См. Многоцелевые Опции.

nParents — Количество родительских элементов, чтобы выбрать.

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

Функция возвращает parents , вектор-строка из длины nParents содержа индексы родительских элементов, которые вы выбираете.

Передача Дополнительных Параметров объясняет, как предоставить дополнительные параметры функции.

Смотрите Выбор для получения дополнительной информации.

Опции воспроизведения

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

EliteCount задает количество индивидуумов, которые, как гарантируют, выживут к следующему поколению. Установите EliteCount быть положительным целым числом, меньше чем или равным численности населения. Значением по умолчанию является ceil(0.05*PopulationSize) для непрерывных проблем и 0.05*(default PopulationSize) для смешанных целочисленных задач.

CrossoverFraction задает часть следующего поколения, кроме элитных дочерних элементов, которые производятся перекрестным соединением. Установите CrossoverFraction быть частью между 0 и 1 . Значением по умолчанию является 0.8 .

Опции мутации

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

‘mutationgaussian’ — Мутация по умолчанию функционирует для неограниченных проблем, ‘mutationgaussian’ , добавляет случайное число, взятое из Распределения Гаусса со средним значением 0 к каждой записи родительского вектора. Стандартное отклонение этого распределения определяется параметрами scale и shrink , и InitialPopulationRange опция. Установите scale и shrink можно следующим образом:

scale параметр определяет стандартное отклонение в первом поколении. Если вы устанавливаете InitialPopulationRange быть 2 1 векторным v , начальное стандартное отклонение является тем же самым во всех координатах родительского вектора и дано scale *(v(2)-v(1)) .

Если вы устанавливаете InitialPopulationRange быть векторным v с двумя строками и nvars столбцы, начальное стандартное отклонение в координатном i из родительского вектора дан scale *(v(i,2) — v(i,1)) .

shrink параметр управляет, как стандартное отклонение уменьшается, когда поколения проходят. Если вы устанавливаете InitialPopulationRange чтобы быть 2 1, вектор, стандартное отклонение в k th генерация, σ k, являются тем же самым во всех координатах родительского вектора и даны рекурсивной формулой

σ k = σ k − 1 ( 1 − Уменьшение k Поколения ) .

Если вы устанавливаете InitialPopulationRange быть вектором с двумя строками и nvars столбцы, стандартное отклонение в координатном i родительского вектора в k th генерация, σi,k, даны рекурсивной формулой

σ i , k = σ i , k − 1 ( 1 − Уменьшение k Поколения ) .

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

Значение по умолчанию обоих scale и shrink 1.

Внимание

Не используйте mutationgaussian когда у вас есть границы или линейные ограничения. В противном случае ваше население не обязательно удовлетворит ограничениям. Вместо этого используйте ‘mutationadaptfeasible’ или пользовательская функция мутации, которая удовлетворяет линейным ограничениям.

‘mutationuniform’ — Универсальная мутация является двухступенчатым процессом. Во-первых, алгоритм выбирает часть векторных записей индивидуума для мутации, где каждая запись имеет вероятность rate из того, чтобы быть видоизмененным. Значение по умолчанию rate 0.01 . На втором шаге алгоритм заменяет каждую выбранную запись случайным числом, выбранным однородно из области значений для той записи.

Изменить значение по умолчанию rate ,

Внимание

Не используйте mutationuniform когда у вас есть границы или линейные ограничения. В противном случае ваше население не обязательно удовлетворит ограничениям. Вместо этого используйте ‘mutationadaptfeasible’ или пользовательская функция мутации, которая удовлетворяет линейным ограничениям.

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

Указатель на функцию позволяет вам записать свою собственную функцию мутации.

Ваша функция мутации должна иметь этот синтаксис вызова:

Аргументы к функции

parents — Вектор-строка из родительских элементов выбран функцией выбора

nvars — Количество переменных

FitnessFcn — Функция фитнеса

state — Структура, содержащая информацию о текущем поколении. Структура состояния описывает поля state .

thisScore — Вектор из множества текущего населения

thisPopulation — Матрица индивидуумов в текущем населении

Функция возвращает mutationChildren — видоизмененные потомки — как матрица, где строки соответствуют дочерним элементам. Количеством столбцов матрицы является nvars .

Передача Дополнительных Параметров объясняет, как предоставить дополнительные параметры функции.

Внимание

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

Перекрестные опции

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

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

‘crossoverscattered’ , перекрестная функция по умолчанию для проблем без линейных ограничений, создает случайный бинарный вектор и выбирает гены, где вектор является 1 от первого родительского элемента и генами, где вектор является 0 от второго родительского элемента, и комбинирует гены, чтобы сформировать дочерний элемент. Например, если p1 и p2 родительские элементы

и бинарный вектор [1 1 0 0 1 0 0 0], функция возвращает следующий дочерний элемент:

Внимание

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

‘crossoversinglepoint’ выбирает случайное целое число n между 1 и nvars и затем

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

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

Конкатенации этих записей, чтобы сформировать дочерний вектор.

Например, если p1 и p2 родительские элементы

и точка перехода равняется 3, функция возвращает следующий дочерний элемент.

Внимание

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

‘crossovertwopoint’ выбирает два случайных целых числа m и n между 1 и nvars . Функция выбирает

Векторные записи, пронумерованные меньше чем или равный m от первого родительского элемента

Векторные записи пронумерованы от m+1 к n , включительно, от второго родительского элемента

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

Алгоритм затем конкатенирует эти гены, чтобы сформировать один ген. Например, если p1 и p2 родительские элементы

и точки перехода равняются 3 и 6, функция возвращает следующий дочерний элемент.

Внимание

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

‘crossoverintermediate’ , перекрестная функция по умолчанию, когда существуют линейные ограничения, создает дочерние элементы путем взятия взвешенного среднего родительских элементов. Можно задать веса одним параметром, ratio , который может быть скаляром или вектором-строкой из длины nvars . Значение по умолчанию ratio вектор из всех 1’s. Установите ratio параметр можно следующим образом.

‘crossoverintermediate’ создает дочерний элемент из parent1 и parent2 использование следующей формулы.

Если все записи ratio находитесь в диапазоне [0, 1], произведенные дочерние элементы в гиперкубе, заданном путем размещения родительских элементов в противоположных вершинах. Если ratio не находится в той области значений, дочерняя сила лежат вне гиперкуба. Если ratio скаляр, затем вся дочерняя ложь на линии между родительскими элементами.

‘crossoverheuristic’ возвращает дочерний элемент, который лежит на линии, содержащей два родительских элемента, маленькое расстояние далеко от родительского элемента с лучшим значением фитнеса в направлении далеко от родительского элемента с худшим значением фитнеса. Можно задать, как далеко дочерним элементом является от лучшего родительского элемента параметром ratio . Значение по умолчанию ratio 1.2. Установите ratio параметр можно следующим образом.

Если parent1 и parent2 родительские элементы и parent1 имеет лучшее значение фитнеса, функция возвращает дочерний элемент

Внимание

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

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

Указатель на функцию позволяет вам записать свою собственную перекрестную функцию.

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

Аргументы к функции

parents — Вектор-строка из родительских элементов выбран функцией выбора

nvars — Количество переменных

FitnessFcn — Функция фитнеса

unused — Заполнитель, не используемый

thisPopulation — Матрица, представляющая текущее население. Количеством строк матрицы является PopulationSize и количеством столбцов является nvars .

Функция возвращает xoverKids — перекрестные потомки — как матрица, где строки соответствуют дочерним элементам. Количеством столбцов матрицы является nvars .

Передача Дополнительных Параметров объясняет, как предоставить дополнительные параметры функции.

Внимание

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

Опции миграции

Примечание

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

Поскольку ga в настоящее время не поддерживает эту форму параллельной обработки, нет никакого преимущества к установке PopulationSize к вектору, или к установке MigrationDirection , MigrationInterval , или MigrationFraction опции.

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

Можно управлять, как миграция происходит следующими тремя опциями:

MigrationDirection — Миграция может произойти в одной или обоих направлениях.

Если вы устанавливаете MigrationDirection к ‘forward’ , миграция происходит к последнему поднаселению. Таким образом, n th поднаселение мигрирует в (n +1) th поднаселение.

Если вы устанавливаете MigrationDirection к ‘both’ , n th поднаселение мигрирует в обоих (n –1) th и (n +1) th поднаселение.

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

MigrationInterval — Задает сколько передачи генерации между миграциями. Например, если вы устанавливаете MigrationInterval к 20 , миграция происходит каждые 20 поколений.

MigrationFraction — Задает, сколько индивидуумов перемещается между подпопуляциями. MigrationFraction задает часть меньших из двух подпопуляций, которые перемещаются. Например, если индивидуумы мигрируют от поднаселения 50 индивидуумов в поднаселение 100 индивидуумов, и вы устанавливаете MigrationFraction к 0.1 , количество индивидуумов, которые мигрируют, 0.1*50=5.

Параметры ограничения

Параметры ограничения относятся к нелинейному ограничительному решателю. Для получения дополнительной информации на алгоритме, смотрите Нелинейные Ограничительные Алгоритмы решателя.

Выберите между нелинейными ограничительными алгоритмами путем установки NonlinearConstraintAlgorithm опция к ‘auglag’ (Увеличенная функция Лагранжа) или ‘penalty’ (Алгоритм штрафа).

Увеличенный лагранжевый генетический алгоритм

InitialPenalty — Задает начальное значение параметра штрафа, который используется нелинейным ограничительным алгоритмом. InitialPenalty должен быть больше или быть равен 1 , и имеет значение по умолчанию 10 .

PenaltyFactor — Увеличивает параметр штрафа, когда задача не решена к требуемой точности, и ограничениям не удовлетворяют. PenaltyFactor должен быть больше 1 , и имеет значение по умолчанию 100 .

Алгоритм штрафа

Алгоритм штрафа использует ‘gacreationnonlinearfeasible’ функция создания по умолчанию. Эта функция создания использование fmincon найти выполнимых индивидуумов. ‘gacreationnonlinearfeasible’ запускается fmincon от множества начальных точек в границах от InitialPopulationRange опция. Опционально, ‘gacreationnonlinearfeasible’ может запуститься fmincon параллельно на начальных точках.

Можно задать настраивающиеся параметры для ‘gacreationnonlinearfeasible’ использование следующих пар "имя-значение".

Имя Значение
SolverOpts fmincon опции, созданное использование optimoptions или optimset .
UseParallel Когда true запущенный fmincon параллельно на начальных точках; значением по умолчанию является false .
NumStartPts Количество стартовых точек, положительного целого числа до sum(PopulationSize) в значении.

Включайте пары "имя-значение" в массив ячеек наряду с @gacreationnonlinearfeasible .

Многоцелевые опции

Многоцелевые опции задают характеристику параметров gamultiobj алгоритм. Можно задать следующие параметры:

ParetoFraction — Устанавливает часть индивидуумов сохранять первую переднюю сторону Парето, в то время как решатель выбирает индивидуумов из более высоких передних сторон. Эта опция является скаляром между 0 и 1.

Примечание

Часть индивидуумов на первой передней стороне Парето может превысить ParetoFraction . Это происходит, когда существует слишком мало индивидуумов других рангов на шаге 6 Итераций.

DistanceMeasureFcn — Задает указатель на функцию, которая вычисляет меру по расстоянию индивидуумов, вычисленных на пробеле переменной решения (генотип, который также называют пробелом переменной проекта) или в функциональном пространстве (фенотип). Например, функцией меры по расстоянию по умолчанию является ‘distancecrowding’ в функциональном пространстве, которое совпадает с <@distancecrowding,'phenotype'>.

“Расстояние” измеряет давку каждого индивидуума в населении. Выберите между следующим:

‘distancecrowding’ , или эквивалентный <@distancecrowding,'phenotype'>— Измерьте расстояние в функциональном пространстве фитнеса.

<@distancecrowding,'genotype'>— Измерьте расстояние на пробеле переменной решения.

@distancefunction — Запишите пользовательской функции расстояния использование следующего шаблона.

gamultiobj передает население в pop , вычисленная музыка к населению в scores , и опции в options . Ваша функция расстояния возвращает расстояние от каждого члена населения к ссылке, такой как самый близкий сосед в некотором смысле. Для примера отредактируйте встроенный файл distancecrowding.m .

Гибридные функциональные опции

ga Гибридная функция

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

[] — Никакая гибридная функция.

‘fminsearch’ — Использует функцию MATLAB ® fminsearch выполнять безусловную минимизацию.

‘patternsearch’ — Использует поиск шаблона, чтобы выполнить ограниченную или безусловную минимизацию.

‘fminunc’ — Использует функцию Optimization Toolbox™ fminunc выполнять безусловную минимизацию.

‘fmincon’ — Использует функцию Optimization Toolbox fmincon выполнять ограниченную минимизацию.

Примечание

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

Можно установить отдельные опции для гибридной функции. Использование optimset для fminsearch , или optimoptions для fmincon , patternsearch , или fminunc . Например:

gamultiobj Гибридная функция

Гибридная функция является другой функцией минимизации, которая выполняется после многоцелевого генетического алгоритма, завершает работу. Можно задать гибридный функциональный ‘fgoalattain’ в HybridFcn опция.

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

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

F max ( j ) = max k F k ( j ) F min ( j ) = min k F k ( j ) .

Вычислите общую массу в каждом решении k,

w ( k ) = ∑ j F max ( j ) − F k ( j ) 1 + F max ( j ) − F min ( j ) .

Вычислите вес для каждой целевой функции j в каждом решении k,

p ( j , k ) = w ( k ) F max ( j ) − F k ( j ) 1 + F max ( j ) − F min ( j ) .

Для каждого решения k выполните целевую проблему достижения с целевым векторным Fk (j) и вектор веса p (j, k).

Для получения дополнительной информации смотрите раздел 9.6 из Деб [3].

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

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

MaxGenerations — Задает максимальное количество итераций для генетического алгоритма, чтобы выполнить. Значением по умолчанию является 100*numberOfVariables .

MaxTime — Задает максимальное время в секундах запуски генетического алгоритма перед остановкой, как измерено tic и toc . Этот предел осуществляется после каждой итерации, таким образом, ga может превысить предел, когда итерация занимает время.

FitnessLimit — Алгоритм останавливается, если лучшее значение фитнеса меньше чем или равно значению FitnessLimit . Не применяется к gamultiobj .

MaxStallGenerations — Алгоритм останавливается если среднее относительное изменение в лучшем значении функции фитнеса по MaxStallGenerations меньше чем или равно FunctionTolerance . (Если StallTest опцией является ‘geometricWeighted’ , затем тест для геометрического средневзвешенного относительного изменения.) Для проблемы с нелинейными ограничениями, MaxStallGenerations применяется к подпроблеме (см. Нелинейные Ограничительные Алгоритмы решателя).

Для gamultiobj , если среднее геометрическое относительного изменения в spread решений Парето по MaxStallGenerations меньше FunctionTolerance , и итоговое распространение меньше, чем средний спред по последнему MaxStallGenerations , затем остановки алгоритма. Коэффициент среднего геометрического ½. Распространение является мерой перемещения передней стороны Парето. См. gamultiobj Алгоритм.

MaxStallTime — Алгоритм останавливается, если нет никакого улучшения лучшего значения фитнеса в течение интервала времени в секундах, заданных MaxStallTime , как измерено tic и toc .

FunctionTolerance — Алгоритм останавливается если среднее относительное изменение в лучшем значении функции фитнеса по MaxStallGenerations меньше чем или равно FunctionTolerance . (Если StallTest опцией является ‘geometricWeighted’ , затем тест для геометрического средневзвешенного относительного изменения.)

Для gamultiobj , если среднее геометрическое относительного изменения в spread решений Парето по MaxStallGenerations меньше FunctionTolerance , и итоговое распространение меньше, чем средний спред по последнему MaxStallGenerations , затем остановки алгоритма. Коэффициент среднего геометрического ½. Распространение является мерой перемещения передней стороны Парето. См. gamultiobj Алгоритм.

ConstraintTolerance — ConstraintTolerance не используется в качестве останавливающегося критерия. Это используется, чтобы определить выполнимость относительно нелинейных ограничений. Кроме того, max(sqrt(eps),ConstraintTolerance) определяет выполнимость относительно линейных ограничений.

Опции выходной функции

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

Для нескольких выходных функций введите cell-массив указателей на функцию:

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

в командной строке MATLAB.

Структура выходной функции

Ваша выходная функция должна иметь следующий синтаксис вызова:

MATLAB передает options , state , и flag данные к вашей выходной функции и выходной функции возвращают state Опции , и optchanged данные.

Примечание

Чтобы остановить итерации, установите state.StopFlag к непустому вектору символов, такому как ‘y’ .

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

state — Структура, содержащая информацию о текущем поколении. Структура состояния описывает поля state .

flag — Текущий статус алгоритма:

‘init’ — Состояние инициализации

‘iter’ — Состояние итерации

‘interrupt’ — Итерация подпроблемы нелинейно ограниченной проблемы для ‘auglag’ нелинейный ограничительный алгоритм. Когда flag ‘interrupt’ :

Значения state поля применяются к подпроблемным итерациям.

ga не принимает изменения в options , и игнорирует optchanged .

state.NonlinIneq и state.NonlinEq поля не доступны.

‘done’ — Конечное состояние

Передача Дополнительных Параметров объясняет, как предоставить дополнительные параметры функции.

Выходная функция возвращает следующие аргументы в ga :

state — Структура, содержащая информацию о текущем поколении. Структура состояния описывает поля state . Чтобы остановить итерации, установите state.StopFlag к непустому вектору символов, такому как ‘y’ .

options — Опции, как изменено выходной функцией. Этот аргумент является дополнительным.

optchanged — Указание булева флага превращается в options . Изменить options для последующих итераций, набор optchanged к true .

Изменение структуры состояния

Внимание

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

ga выходные функции могут изменить state структура (см. Структуру состояния). Будьте осторожны при изменении значений в этой структуре, когда можно передать противоречивые данные обратно ga .

Совет

Если ваша структура output изменяет Population поле, затем убедиться обновить Score поле, и возможно Best , NonlinIneq , или NonlinEq поля, так, чтобы они содержали сопоставимую информацию.

Обновить Score поле после изменения Population поле, сначала вычислите значения функции фитнеса населения, затем вычислите фитнес, масштабирующийся для населения. Смотрите, что Фитнес Масштабирует Опции.

Отобразитесь к опциям командного окна

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

‘final’ (значение по умолчанию) — Причина остановки отображена.

‘off’ или эквивалентный ‘none’ — Никакой вывод не отображен.

‘iter’ — Информация отображена в каждой итерации.

‘diagnose’ — Информация отображена в каждой итерации. Кроме того, диагностика перечисляет некоторую информацию о задаче и опции, которые были изменены от значений по умолчанию.

Оба ‘iter’ и ‘diagnose’ отобразите следующую информацию:

Generation — Номер генерации

f-count — Совокупное число вычислений функции фитнеса

Best f(x) — Лучшее значение функции фитнеса

Mean f(x) — Среднее значение функции фитнеса

Stall generations — Количество поколений начиная с последнего улучшения функции фитнеса

Когда нелинейная ограничительная функция была задана, ‘iter’ и ‘diagnose’ не отображайте Mean f(x) , но дополнительно отобразится:

Max Constraint — Максимальное нелинейное нарушение ограничений

Векторизуйте и найдите что-либо подобное опциям (оценка функции пользователя)

Можно принять решение иметь физическую форму и ограничительные функции, выполненные в последовательном, параллельном, или векторизованным способом. Установите ‘UseVectorized’ и ‘UseParallel’ опции с optimoptions .

Когда ‘UseVectorized’ false (значение по умолчанию), ga вызывает функцию фитнеса на одном индивидууме за один раз, когда она циклично выполняется через население. (Это принимает ‘UseParallel’ в его значении по умолчанию false .)

Когда ‘UseVectorized’ true , ga вызывает функцию фитнеса на целом населении целиком, в одном вызове функции фитнеса.

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

Когда UseParallel true , ga вызывает функцию фитнеса параллельно, с помощью параллельной среды, которую вы установили (см., Как Использовать Параллельную обработку в Global Optimization Toolbox). Установите UseParallel к false (значение по умолчанию), чтобы вычислить последовательно.

Примечание

Вы не можете одновременно использовать векторизованный и найти что-либо подобное расчетам. Если вы устанавливаете ‘UseParallel’ к true и ‘UseVectorized’ к true , ga оценивает вашу физическую форму и ограничительные функции векторизованным способом, не параллельно.

Рейтинг Форекс брокеров: