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

Кодирование нечисловых данных

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

Определение фенотипа объекта по его генотипу

Таким образом, для того, чтобы определить фенотип объекта (то есть значения признаков, описывающих объект) нам необходимо только знать значения генов, соответствующим этим признакам, то есть генотип объекта. При этом совокупность генов, описывающих генотип объекта, представляет собой хромосому. В некоторых реализациях ее также называют особью. Таким образом, в реализации генетического алгоритма хромосома представляет собой битовую строку фиксированной длины. При этом каждому участку строки соответствует ген. Длина генов внутри хромосомы может быть одинаковой или различной. Чаще всего применяют гены одинаковой длины. Рассмотрим пример хромосомы и интерпретации ее значения. Допустим, что у объекта имеется 5 признаков, каждый закодирован геном длинной в 4 элемента. Тогда длина хромосомы будет 5*4=20 бит

теперь мы можем определить значения признаков

Допустим разрыв происходит после 3-го бита хромосомы, тогда

Затем с вероятностью 0,5 определяется одна из результирующих хромосом в качестве потомка.

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

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

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

Схема функционирования генетического алгоритма

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

1. Инициировать начальный момент времени $t=0$. Случайным образом сформировать начальную популяцию, состоящую из $k$ особей. $B_0 = \$
2. Вычислить приспособленность каждой особи $F_ = fit(A_i)$ , $i=1…k$ и популяции в целом $F_t = fit(B_t)$ (также иногда называемую термином фиттнес). Значение этой функции определяет насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи.
3. Выбрать особь $A_c$ из популяции $A_c = \mbox Get(B_t)$
4. С определенной вероятностью (вероятностью кроссовера $P_c$) выбрать вторую особь из популяции $A_ = \mbox Get(B_t)$ и произвести оператор кроссовера $A_c = \mbox (A_c, A_)$.
5. С определенной вероятностью (вероятностью мутации $P_m$) выполнить оператор мутации $A_c = \mbox (A_c)$.
6. С определенной вероятностью (вероятностью инверсии $P_i$) выполнить оператор инверсии $A_c = \mbox (A_c)$.
7. Поместить полученную хромосому в новую популяцию $\mbox (B_,A_c)$.
8. Выполнить операции, начиная с пункта 3, $k$ раз.
9. Увеличить номер текущей эпохи $t=t+1$.
10. Если выполнилось условие останова, то завершить работу, иначе переход на шаг 2.

Теперь рассмотрим подробнее отдельные этапы алгоритма.

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

Fit(A_i)/Fit(B_t)$. Использование этого метода приводит к тому, что вероятность передачи признаков более приспособленными особями потомкам возрастает. Другой часто используемый метод – турнирный отбор. Он заключается в том, что случайно выбирается несколько особей из популяции (обычно 2) и победителем выбирается особь с наибольшей приспособленностью. Кроме того, в некоторых реализациях алгоритма применяется так называемая стратегия элитизма, которая заключается в том, что особи с наибольшей приспособленностью гарантировано переходят в новую популяцию. Использование элитизма обычно позволяет ускорить сходимость генетического алгоритма. Недостаток использования стратегии элитизма в том, что повышается вероятность попадания алгоритма в локальный минимум.

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

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

15. ЭВОЛЮЦИОННЫЕ ВЫЧИСЛЕНИЯ И ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ

15.1. Основные сведения об эволюционных вычислениях

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

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

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

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

Эволюционные вычисления являются одним из возможных эвристических подходов к решению многомодальных (имеющих несколько локальных экстремумов) оптимизационных задач большой размерности за счет сочетания элементов случайности и детерминированности точно так, как это происходит в живой природе [15]. Как и всякий метод, использующий элемент случайности, эволюционные вычисления не гарантируют обнаружения глобального экстремума целевой функции (оптимального решения) за определенное время. Основное их преимущество в том, что они позволяют найти «хорошие» решения очень трудных задач за меньшее время, чем другие методы. Методы эволюционных вычислений оказались достаточно эффективными для решения ряда реальных задач инженерного проектирования, планирования, маршрутизации и размещения, управления портфелями ценных бумаг, прогнозирования, а также во многих других областях.

Основными направлениями эволюционных вычислений являются:

В основе эволюционного программирования (автор Лоуренс Дж. Фогель, 1960 год) лежит идея представления альтернатив решения задачи в виде универсальных конечных автоматов 1 , способных реагировать на стимулы, поступающие из окружающей среды. Эволюционное программирование было применено к решению различных прикладных задач, включая маршрутизацию трафика и планирование, выявление рака, военное планирование, обучение в играх, разработку систем управления, идентификации, обработки сигналов и т.д. В частности, Ангелине и Поллак описали, как эволюционное программирование может быть использовано для развития компьютерных программ. Гипотезы о виде зависимости целевой функции от переменных формулируются системой в виде программ на некотором внутреннем языке программирования. Процесс построения таких программ строится как эволюция в мире программ. Если система находит программу, которая достаточно точно выражает искомую зависимость, она начинает вносить в нее небольшие модификации и отбирает среди построенных таким образом дочерних программ те, которые повышают точность. Система «выращивает» несколько генетических линий программ, конкурирующих между собой в точности нахождения искомой зависимости. Специальный транслирующий модуль, переводит найденные зависимости с внутреннего языка системы на понятный пользователю язык (математические формулы, таблицы и др.) [31].

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

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

1 Абстрактный автомат (в теории алгоритмов) — математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. На вход этому устройству поступают символы одного алфавита, на выходе оно выдаёт символы (в общем случае) другого алфавита. Автомат может быть представлен в виде графа, вершинами которого являются состояния, а дуги — переходами между ними. Как правило, автоматы используются для описания поведения программного обеспечения, аппаратных и технических средств [31].

15.2. Генетические алгоритмы

15.2.1. Основные понятия

В теории генетических алгоритмов применяется следующая терминология [15, 31].

Ген (свойство) – атомарный элемент хромосомы. Ген может быть битом, числом или неким другим объектом.

Аппель – значение конкретного гена.

Локус – положение конкретного гена в хромосоме.

Хромосома (цепочка) – упорядоченная последовательность генов.

Генотип (код) – упорядоченная последовательность хромосом.

Особь (индивидуум) – конкретный экземпляр генотипа.

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

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

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

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

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

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

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

15.2.2. Основные отличия генетических алгоритмов от традиционных методов поиска решений

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

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

3. Генетический алгоритм использует как вероятностные правила для порождения новых точек для анализа, так и детерминированные для перехода от одних точек к другим [15].

15.2.3. Последовательность работы генетического алгоритма

Общая схема работы алгоритма представлена на следующем рисунке [15].

Критерием остановки работы генетического алгоритма может быть одно из следующих событий [31]:

— сформировано заданное число поколений;

— исчерпано время, отведенное на эволюцию;

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

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

15.2.4. Пример работы генетического алгоритма при поиске максимума функции одной переменной

Целевая функция задана выражением f(x) = 25 + 10x – 46x 2 + x 3 . Требуется найти максимальное и минимальное значение целевой функции в интервале x ϵ [-10, 53].

А) Решение с помощью классической теории оптимизации (точный метод решения оптимизационной задачи).

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

1. Определение первой производной: f’(x) = 10 – 92x + 3x 2 .

2. Определение корней квадратного уравнения 10 – 92x + 3x 2 = 0: x₁ = 30.558, x₂ = 0.109.

3. Определение второй производной: f”(x) = –92 + 6x.

4. Определение типа экстремумов:

— f”(30.558) = –92 + 6 * 30.558 = 91.348 > 0 → минимум;
— f”(0.109) = –92 + 6 * 0.109 = –91.348 2 + 30.558 3 = -14089;
— f(0.109) = 25 + 10 * 0.109 – 46 * 0.109 2 + 0.109 3 = 25.5.

6. Определение значений функции на границах интервала:

— f(-10) = 25 + 10 * (-10) – 46 * (-10) 2 + (-10) 3 = -5675;
— f(53) = 25 + 10 * 53 – 46 * 53 2 + 53 3 = 20218.

7. Определение максимального и минимального значений целевой функции:

— максимум: y_max = MAX(-14089, 25.5, -5675, 20218) = 20218 при x = 53;
— минимум: y_min = MIN(-14089, 25.5, -5675, 20218) = -14089 при x = 30.558.

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

Рис.15.2. График функции f(x) = 25 + 10x – 46x 2 + x 3 в интервале x ϵ [-10, 53]

Б) Решение с помощью генетического алгоритма (эвристический метод решения оптимизационной задачи).

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

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

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

1. Случайным образом генерируются особи исходной популяции.

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

3. Первая итерация – оператор мутации. Для мутации случайным образом выбран потомок 7, а в нем для инверсии случайно выбран 3 бит. В результате код особи изменился с 100001 на 101001.

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

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

За одну итерацию качество популяции значительно возросло. Если в исходной популяции среднее значение целевой функции было -4811, а ее минимальное значение составляло -12407, то в популяции после первой итерации среднее значение возросло до 1034, а минимальное значение составило -2327. Лучшее (максимальное) значение увеличилось с 2704 до 5113 при оптимальном решении 20218 (см. аналитическое решение). Таким образом, данный пример наглядно иллюстрирует процесс улучшения как популяции в целом, так и наилучшего решения в частности.

15.2.5. Пример работы генетического алгоритма при поиске решения задачи коммивояжера

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

Задача коммивояжера относится к категории NP-полных задач, т.е. задач, для которых еще не найден полиномиальный алгоритм ее решения.

Ген – число, характеризующее номер посещаемого города.

Хромосома – строка из чисел длиной N, характеризующая порядок посещения городов.

Генотип состоит из одной хромосомы.

Фенотип — порядок посещения городов (совпадает с генотипом).

Особь – конкретная строка из чисел (допустимый вариант решения задачи).

Предположим коммивояжеру необходимо посетить 9 городов, N = 9.

Особи «231586479» и «147523869» — примеры допустимых вариантов решения задачи.

Классическое скрещивание приведет к генерации недопустимых вариантов, например

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

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

1) Случайным образом выбираются два сечения генотипа

Р₁ = 231 | 586 | 479
Р₂ = 147 | 523 | 869

2) Для потомков копируются участки кода, расположенные между сечениями

П₁ = ххх | 586 | ххх
П₂ = ххх | 523 | ххх

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

B₁ = 479 231 586
В₂ = 869 147 523

4) Свободные гены потомков последовательно заполняются генами из перекрестных вспомогательных строк с пропуском уже имеющихся в потомке генов

П₁ = 914 | 586 | 723
П₂ = 479 | 523 | 186

Оператор мутации также может быть реализован различными способами, например:

1) перестановка пары, случайным образом выбранных генов местами: 479523186 → 473529186;
2) инверсия случайным образом выбранной последовательности генов: 479 | 523 | 186 → 479 | 325 | 186.

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

Древнегреческий историк Фукидид

В 1859 году был опубликован труд английского естествоиспытателя Чарльза Дарвина под названием «Происхождение видов путем естественного отбора», который перевернул представления человечества о жизни на земном шаре. Через сто с небольшим лет профессор психологии и компьютерных наук из Университета Мичиган Джон Голланд (Holland), вдохновленный эволюционной теорией великого ученого, совершил прорыв в области проектирования и построения вычислительных систем. Его книга под названием «Адаптация в естественных и искусственных системах», опубликованная в 1975 году, была посвящена новым мощным методам поиска наилучшего решения, которые получили название генетических алгоритмов.

Необходимость использования новых методов оптимизации

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

Эволюционная теория как основная идея ГА

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

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

Как же действует компьютер? В начале генерируется популяция исходных решений. Далее с помощью обозначенных операций (скрещивания и мутации) на свет производится новое поколение. Определенный процент этих решений, в меньшей степени улучшающих целевую функцию, отсеивается, а остальные продолжают участвовать в эволюционном процессе. Остановив его в некоторый момент, можно получить наилучшее или близкое к нему решение. Так выглядит основная мысль ГА, изложенная в свое время Джоном Голландом. Нужно отметить, что эффективность генетических алгоритмов сильно зависит от таких деталей, как метод кодирования решений, определение операций и критериев останова вычислительного процесса. Сейчас существует множество способов реализации ГА, но в каждом из них заложена описанная выше идея (различные модели смотри на сайте gai.narod.ru).

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

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

Исходя из сказанного, генетические алгоритмы совсем не являются просто умозрительной теорией, а широко используются на практике. Об этом говорят и многочисленные программные комплексы, которые доступны не только юридическим лицам, но и обычным пользователям. Одним из таких приложений является программный комплекс GeneHunter, разработанный российской компанией «НейроПроект», и программный пакет Auto2Fit от CPC-X Software, обновившийся 20 мая этого года до третьей версии. Рассмотрим их поближе.

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

Исходные данные вводятся в GeneHunter посредством рабочего листа Excel. В диалоговом окне программы следует указать ячейки, использующиеся при решении, задать список ограничений, которые должны выполняться, и определить целевую функцию, направив ее на максимум, на минимум или на указанное значение. Для написания целевой функции можно также использовать макросы Excel или функции Excel Visual Basic. В целом, работа с GeneHunter в Excel не многим отличается от решения задач при помощи надстройки «Поиск решения» (Solver), о которой я рассказывал в «КВ» №21/2005.

Чтобы каждый пользователь мог применить ГА в своих собственных приложениях, в пакет GeneHunter включена динамическая библиотека функций GALIB.DLL. В нее входят функции создания популяции, определения параметров эволюции (вероятности скрещивания, мутации, разнообразия) и значений целевой функции особей, а также следующие генетические операторы: оператор скрещивания, мутации, разнообразия и вымирания.

В GeneHunter присутствует целый ряд обучающих примеров задач с решениями, что, несомненно, удобно для людей, ранее не сталкивавшихся с подобными программами. Среди примеров можно найти такие распространенные проблемы, как анализ портфеля акций, оптимизация инвестиционного портфеля, задача коммивояжера, создание оптимального графика работ и другое. Кроме этого, в пакет включены исходники программ, написанных на Visual Basic, Delphi и Visual C++ и использующих библиотеку GALIB.DLL. Полную информацию о программных ограничениях и о GeneHunter можно посмотреть на странице www.neuroproject.ru.

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

Программа может работать в одном из следующих режимов: быстром и программном. Из дополнительных возможностей Auto2Fit можно отметить удобную навигацию по файлам, реализуемую с помощью дерева каталогов, рабочую область, представленную в виде таблиц Excel, построение 3D-графиков и другое. В комплект также включены многочисленные примеры, в том числе и классические примеры задач оптимизации. Программа обладает не очень большими системными требованиями. Скачать новую версию или найти подробную информацию о продукте можно на страничке www.geocities.com/neuralpower/introduction_af.htm.

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

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

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

1. Обзор возможностей.

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

1.1. Данные и индикаторы.

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

1.2. Прогнозы и торговые стратегии.

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

NeuroShell Trader может оповещать Вас о возникновении определенных условий. Например, можно настроить его подавать звуковой сигнал и/или выводить на экран окно с оповещением, когда торговая стратегия выдает предписание открывать или закрывать позиции. Вы можете создать несколько именованных оповещений, реагирующих на разные события.

1.4. Портфель инструментов.

В NeuroShell Trader Вы можете одновременно работать с несколькими финансовыми инструментами. Для этого просто добавьте необходимые инструменты на Ваш рабочий лист. Нейронная сеть или индикатор, построенные для одного финансового инструмента, автоматически применяются ко всем инструментам, которые Вы укажете. Если Вы пожелаете, будет обработан весь портфель без каких-либо дополнительных усилий с Вашей стороны! После того, как Вы применили свои сети, Вы можете увидеть результаты для каждого инструмента Вашего портфеля. NeuroShell Trader позволяет пользователю получить важную статистику и прочую информацию, касающуюся применения торговых стратегий и нейронных сетей к Вашим данным. Нажав на кнопку Prediction Analysis в Мастере Прогнозов, Вы получите подробный отчет, содержащий, например, среднегодовой процент прибыли для тренировочного и экзаменационного наборов, даты начала/конца тренировочного и экзаменационного наборов, средний годовой процент прибыли для каждого инструмента и многие другие параметры.

В NeuroShell Trader вы можете экспортировать временные ряды в текстовые файлы или в буфер обмена для последующего использования в других программах.

1.6. Программные интерфейсы.

В NeuroShell Trader реализованы следующие программные интерфейсы для взаимодействия с внешним ПО.

Для работы с внешними источниками данных в NeuroShell Trader используется Data Pump Server, интегрированный непосредственно в систему. Взаимодействие с ним из сторонних программ возможно с помощью программного интерфейса Data Pump API. Используя этот интерфейс, можно реализовать закачку данных real-time или исторических данных в форматах, не поддерживаемых NeuroShell Trader.

1.8. Data Exchange API.

Для использования данных и ордеров из NeuroShell Trader в других системах используется программный интерфейс Data Exchange API. Чтобы использовать его в Ваших программах для взаимодействия с NeuroShell Trader, необходимо установить на компьютере Data Exchange API Add-On, который Вы можете приобрести отдельно от NeuroShell Trader.

1.9. Активация NeuroShell Trader через Интернет.

При приобретении лицензионной копии NeuroShell Trader вы получаете индивидуальный серийный номер и пароль. После выполнения процедуры установки NeuroShell Trader для того, чтобы он начал работать на Вашем компьютере, необходимо выйти в Интернет, зайти в пункт меню Активация, ввести в соответствующие поля серийный номер и пароль и нажать кнопку Autorization. Вы можете использовать Вашу копию NeuroShell Trader только на одном компьютере в данный момент времени. Если Вы захотите работать с NeuroShell Trader на другом компьютере — деактивируйте его (аналогичным образом) на одном и активируйте на другом компьютере (переустанавливать NeuroShell Trader не требуется)! Такая операция не займет много времени, но позволит Вам использовать NeuroShell Trader дома, на работе и т.д.

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

2. Продукты семейства NeuroShell Trader.

Семейство продуктов NeuroShell Trader включает в себя следующие программные продукты:

• — NeuroShell Trader.
• — NeuroShell Trader Professional.
• — NeuroShell DayTrader Professional.

Различие между ними заключается в разной активированной функциональности. Это сделано для того, чтобы пользователь мог более гибко выбирать, что ему нужно, и не платил бы за возможности, в которых он не нуждается. Так, Вы можете приобрести самую простую комплектацию — NeuroShell Trader, а затем при необходимости приобрести NeuroShell Trader Professional или NeuroShell DayTrader Professional. Подробно о функциональности, активированной в конкретных продуктах, смотрите в пунктах, посвященных продуктам и Сравнительной таблице далее.

2.1. NeuroShell Trader.

NeuroShell Trader — самый простой программный продукт семейства. Но это совершенно не значит, что он гораздо хуже других. Он содержит функциональность, которая может оказаться вполне достаточной для многих трейдеров. Но в то же время не имеет некоторых возможностей, которые покажутся критическими другим трейдерам. Так, он не позволяет торговать внутри дня. В отличие от NeuroShell Trader Professional в нем нет возможности использовать весь спектр целевых функций, максимизирующих прибыль и минимизирующих ошибку при прогнозах, отсутствует возможность генетической оптимизации различных параметров, отсутствуют индикаторы, использующие анализ главных компонент, вейвлет-анализ и спектральный анализ (преобразование Фурье).

2.2. NeuroShell Trader Professional.

NeuroShell Trader Professional обладает расширенными возможностями по сравнению с базовой комплектацией NeuroShell Trader. Пользователь имеет возможность использовать генетические алгоритмы для оптимизации параметров индикаторов, входов нейросетей, используемых для прогнозирования, для поиска оптимальных торговых стратегий и т.д. Есть возможность получать звуковые и/или всплывающие предупреждения на основании любой комбинации индикаторов, прогнозов и/или торговых стратегий, использовать весь спектр целевых функций, максимизирующих прибыль и минимизирующих ошибку при прогнозах. Можно использовать индикаторы, использующие анализ главных компонент, вейвлет-анализ и спектральный анализ (преобразование Фурье). Также можно использовать нейронные сети, полученные в NeuroShell 2, NeuroShell Predictor и NeuroShell Classifier.

2.3. NeuroShell DayTrader Professional.

NeuroShell DayTrader является самым совершенным из семейства NeuroShell Trader. Он включает в себя всю функциональность, реализованную в других продуктах семейства, и, кроме того, позволяет торговать внутри дня, получая котировки от источников данных в режиме real-time и анализируя их с разрешением до 1 минуты. С помощью NeuroShell DayTrader Professional трейдеры, работающие внутри дня, могут строить системы, выдающие сигналы покупки и продажи на основе 1, 2, 5, 10, 15, 20, 30 и 60-минутных отсчетов (bars). Они могут наблюдать в реальном времени изменение значений high, low и close для последнего отсчета, пока формирование этого отсчета не будет окончено. NeuroShell DayTrader отображает несформированный отсчет красным в процессе накопления информации о новых сделках. Таким образом, вы можете использовать NeuroShell DayTrader, например, для внутридневной торговли на FOREX.

По опыту компании Ward Systems Group, более сложные модели, необходимые для работы с позициями между днями, не являются необходимыми для торговли внутри дня. Здесь часто хорошо работают простые модели. Более того, поскольку Вы имеете дело с более краткосрочными отсчетами, Вам нет необходимости пользоваться многолетней историей для построения нейронных сетей и проверки торговых стратегий на исторических данных. Таким образом, Вы избегаете тренировки сетей на данных, полученных давным-давно в других рыночных условиях. Загрузив минутные отсчеты за два дня, вы получите количество данных, примерно эквивалентное трем годам ежедневных (суточных) отсчетов. Тренировка сетей лишь на нескольких последних днях становится не только возможна, но и желательна. Впрочем, некоторые могут и не согласиться с последним утверждением. (В конце концов, NeuroShell Trader именно для этого и создан — для построения моделей такими, какими их хотите видеть ВЫ, а не такими, какими их советует сделать кто-то другой). Некоторые игроки считают, что более длинные периоды могут оказаться предпочтительнее для учета трендов. Впрочем, и в этом случае Вам не понадобится обращаться за данными в историю Каменного века. Например, если Вы возьмете 30-минутные отсчеты за 90 торговых дней, Вы получите примерно 1170 отсчетов, что примерно эквивалентно по количеству данных 4.5 годам суточных отсчетов. Основная рекомендация на этот счет такова: если Вы используете мелкие (частые) отсчеты, то для обеспечения оптимального быстродействия ограничивайте Ваши проекты несколькими акциями и несколькими неделями внутридневных данных. Излишне широкие временные рамки при работе с мелкими отсчетами скорее всего приведут к длительной загрузке данных и снизят быстродействие программы.

2.4. Сравнительная таблица.

В NeuroShell Trader имеется обширная библиотека, включающая более 800 разнообразных индикаторов, отнесенных к 40 категориям. Помимо стандартных индикаторов, таких как скользящие средние(moving averages), норма изменения (rate-of-change) или стохастические линии (stochastics), вы можете пользоваться индикаторами, которые распознают графические фигуры технического анализа, такие, как head and shoulders (голова и плечи), bearish flag (медвежий флаг), Japanese candlestick hammer (молоток в японских свечках) и многие другие.

Приведем список категорий индикаторов:

У Вас есть свой собственный секретный индикатор? Прекрасно! NeuroShell Trader дает возможность реализовать его путем комбинации готовых функций из внушительного списка, в который входят условия ЕСЛИ-ТО, арифметические операторы, тригонометрические функции и многое другое. При этом изучения какого-либо языка программирования не требуется. Мастер индикаторов поможет Вам построить индикаторы, которые могут оказаться полезными при создании правил для торговых стратегий или сыграют важную роль при получении прогнозов, когда Вы перейдете к использованию Мастера прогнозов.

3.1. Мастер Индикаторов.

Мастер Индикаторов проведет Вас шаг за шагом через весь процесс создания индикатора. Для построения индикаторов достаточно нескольких щелчков мышью. Мастер может быть использован как для создания одного из стандартных индикаторов, так и для создания новых индикаторов на основе библиотечных, причем имеется возможность неограниченного вложения (т.е. индикатор от индикатора от индикатора и т.д.). Мастер позволяет устанавливать параметры для каждого индикатора. Временные ряды не обязаны представлять собой цены закрытия (close) для выбранных финансовых инструментов, это могут быть любые временные ряды из каталога с данными. Более того, Вы можете использовать разные временные ряды в качестве параметров в одном многопараметрическом индикаторе. Работа с Мастером индикаторов начинается со списка категорий индикаторов. Выбрав категорию, необходимо выбрать конкретный индикатор. Затем Вы можете изменить параметры индикатора или принять значения, установленные по умолчанию. Вы сможете создать сложный индикатор с несколькими уровнями вложения других индикаторов (например, Avg(%Change(Close,5),10) можно преобразовать в одноуровневый индикатор MyIndicator(Close, 5, 10)). Помимо этого, у Вас есть возможность спрятать параметры, которые, как Вам кажется, изменять не понадобится (например, MyIndicator(Close)). Также, Вы можете назвать индикатор так, чтобы легче понимался смысл производимых в нем операций. Вы можете взять многоуровневый индикатор (например, Avg(StdDev(Close, 10),10)), назначения которого не так уж очевидно, и дать ему более содержательное название (например, SmoothedVolatility(Close)). NeuroShell Trader Professional позволяет сохранять Ваши собственные новые индикаторы для использования в будущем. Это позволит Вам построить индикатор в одном проекте и использовать его во всех Ваших проектах. При желании Вы можете защитить свой собственный индикатор паролем.

NeuroShell Trader умеет качественно строить прогнозы с помощью нейронных сетей. Используемая в NeuroShell Trader нейронная сеть Turboprop2 была разработана специально для финансового прогнозирования. Она умеет качественно экстраполировать, поэтому ее можно использовать на растущих рынках. Кроме того, Turboprop2 имеет механизмы, помогающие предотвратить «переучивание». Помимо этого, у Turboprop2 нет параметров, которые надо было бы подбирать, чтобы заставить сеть работать, что делает ее использование еще более простым. Вам не нужно становиться экспертом в нейронных сетях — использовать нейросетевое прогнозирование в NeuroShell Trader так же просто, как индикатор.

Выбрав пункт меню «Predictions» (Прогнозы), вы попадаете в Мастер Прогнозов (Prediction Wizard), позволяющий быстро настроить систему для получения прогнозов. Мастер прогнозов позволяет выбрать, что Вы хотите прогнозировать. Это могут быть цены закрытия (close), их процентные изменения или иные данные или индикаторы. Вы также можете устанавливать длительность периода, на который вы желаете получить прогноз. И больше никаких забот о создании данных с опережениями (lead) и задержками (lag) — NeuroShell Trader все это сделает за Вас! Когда нейронная сеть применяется к Вашим данным и индикаторам, результаты появляются в виде дополнительного временного ряда подобно тому, как это происходит при добавлении любого другого индикатора или новых данных. Результаты затем можно использовать в качестве индикаторов или входов другой нейронной сети.

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

4.2. Walk Forward Testing — Проверка со сдвигом.

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

4.3. Тренировка на получение прибыли.

Многие трейдеры обращались с просьбой реализовать функциональность, позволяющую при прогнозировании ориентироваться на максимизацию прибыли вместо того, чтобы минимизировать ошибку прогнозирования. Это сделано! NeuroShell Trader позволяет Вам выбрать один из двух методов тренировки. Один метод минимизирует ошибку предсказания, а другой дает Вам возможность указать правила торговли и затем использует результаты торгов, основанные на предсказаниях сети, для максимизации прибыли. Т.к. при реальной торговле приходится учитывать комиссионные, проскальзывание и другие факторы, в NeuroShell Trader была реализована возможность обучать нейронную сеть максимизировать прибыль или другие целевые функции с учетом параметров торговли. Для выбора параметров торговли используйте вкладки Shares, Costs и Positions в Мастере Прогнозов.

Так, на вкладке Shares Вы можете выбрать, будет ли NeuroShell Trader при оптимизации нейронной сети:

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

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

На вкладке Costs можно установить размеры комиссионных на открытие и закрытие позиций, а также некоторые другие параметры торговли.

На вкладке Positions можно дать указание системе использовать для вычисления статистик только короткие, либо только длинные, либо и те и другие, либо не использовать никакие позиции. Также можно ввести правила для торговли, либо дать указание NeuroShell Trader самому определить оптимальные правила.

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

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

• 1. MOST RECOMMENDED PROFIT OBJECTIVE (наиболее рекомендуемая целевая ф-ия, основанная на доходности).
• 2. RECOMMENDED PROFIT OBJECTIVES (рекомендуемые целевые ф-ии, основанные на доходности).
• 3. OTHER PROFIT OBJECTIVES (другие целевые ф-ии, основанные на доходности).
• 4. RECOMMENDED ERROR OBJECTIVES (рекомендуемые целевые ф-ии, основанные на ошибке прогноза).
• 5. OTHER ERROR OBJECTIVES (другие целевые ф-ии, основанные на ошибке прогноза).

4.4. Генетическая оптимизация входов нейросети при прогнозировании.

NeuroShell Trader Professional дополнительно предоставляет Вам возможность использовать оптимизацию на основе генетического алгоритма для поиска наилучших входов (например, индикаторов), и/или наилучших параметров для входов (т.е., например, параметров индикаторов, таких, как временные интервалы для скользящих средних), что может существенно повысить качество прогнозов. Вы можете находить оптимальные параметры для индикаторов, подающихся на вход, а также пороги покупки/продажи при тренировке на получение прибыли.

5. Торговые стратегии.

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

5.1. Мастер Торговых Стратегий.

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

Вы сможете создавать торговые стратегии, которые позволят Вам:

• 1. Торговать с использованием длинных и/или коротких позиций.
• 2. Ограничивать убытки с помощью следящих стоп-приказов (trailing stops).
• 3. Торговать с использованием приказов типа «по наилучшей цене» (market), лимитных (limit), стоп-приказов (stop), стоп-лимитных (stop limit) и приказов «по цене закрытия» (market on close).
• 4. Проверять стратегии с учетом комиссионных, маржи (margin), проскальзывания (slippage) и стоимости пункта (point value).
• 5. Торговать фиксированным или растущим по мере получения прибыли количеством акций/контрактов, либо устанавливать сумму, которой Вы располагаете.

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

5.2. Оптимизация торговых стратегий с использованием генетических алгоритмов.

Наиболее важная особенность NeuroShell Trader Professional, делающая его таким мощным — это его способность оптимизировать торговые стратегии. При этом совершенно не обязательно использовать нейронные сети в Ваших торговых стратегиях. NeuroShell Trader Professional будет оптимизировать всю стратегию, даже если некоторые условия используют нейросети, а некоторые — нет. Как уже было сказано, под термином «торговая стратегия» подразумевается набор механических правил для определения того, когда открывать и закрывать позиции. Каждое из правил, входящих в набор, может иметь параметры, которые необходимо грамотно подобрать. Кроме того, необходимо подобрать сам набор правил, составляющий торговую стратегию.

NeuroShell Trader Professional предоставляет Вам возможность выбрать необходимую глубину оптимизации. Работа Мастера торговой стратегии начинается с появления диалогового окна, которое предлагает выбрать один из предустановленных шаблонов торговых стратегий, либо не использовать шаблоны. Далее вы попадаете на страницу, позволяющую просмотреть входящие в торговую стратегию правила торговли, модифицировать их, либо добавить новые. На следующей странице Вы можете установить параметры, которые будут использоваться при оптимизации торговой стратегии. Нажав на кнопку Modify Trading Strategy Parameters, Вы попадаете на форму, имеющую следующие вкладки: Rules, Trading, Dates, Costs, Optimization.

На вкладке Rules можно выбрать из нескольких вариантов оптимизации торговых стратегий:

1. Parameter Search (поиск параметров) — используются все заданные механические правила, а программа подбирает для них оптимальные параметры. С этими параметрами правила не обязательно будут оптимальными каждое по отдельности, но они будут оптимальными при использовании их всех вместе как единого комплекта.

2. Rule Selection (выбор правил) — выбираются правила из всех тех, которые Вы указали; остаются только те, которые лучше всего работают вместе. При этом параметры правил не подбираются.

3. Full Optimization (полная оптимизация) — производятся одновременно поиск параметров и выбор правил.

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

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

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

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

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

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

6. Готовые торговые системы.

NeuroShell Trader, NeuroShell Trader Professional и NeuroShell Trader DayTrader Professional не являются готовыми торговыми системами. Это мощные программные инструменты, которые позволяют пользователям реализовывать свои идеи без необходимости нанимать программистов и необходимости глубоко изучать алгоритмы прогнозирования и оптимизации.

В доступном только зарегистрированным пользователям разделе сайта ежемесячно публикуются новые торговые системы, готовые к использованию в NeuroShell Trader, разработанные экспертами в этой области и опубликованные в журнале Technical Analysis of Stock and Commodities Magazine. Ниже будет приведен список торговых систем, доступных для скачивания зарегистрированным пользователям.

ПРЕДУПРЕЖДЕНИЕ: Мы НЕ ГАРАНТИРУЕМ реальную результативность представленных торговых систем. Данные торговые системы являются реализацией идей экспертов, и хотя специалисты Ward System Group постарались аккуратно реализовать идеи экспертов, в некоторых случаях были построены торговые системы, которые немного отличаются от того, что подразумевали авторы идей этих торговых систем. Кроме того, идеи авторов теоретически могут работать не так, как авторы описывают в статье, либо могут работать по-другому в условия, отличающихся от условий, рассматриваемых автором.

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

Вот список некоторых реализованных торговых систем:

Self-Adjusting RSI (February 2006)
Swiss Army Knife Indicator (SWAK) (January 2006)
Overhauling Market Breadth (December 2005)
Speed Trading System (November 2005)
Fractal Adaptive Moving Average (October 2005)
Shorting Moving Average Pullbacks (September 2005)
Stochastics and Price Range Dynamics (August 2005)
Targeting Your Pattern (July 2005)
Modified Darvas Technique (June 2005)
Universal Cycle Index (May 2005)
Moving Average Pullbacks (April 2005)
Median Average Adaptive Filter (March 2005)
The Truth About Volatility (February 2005)
Detecting Breakouts (January 2005)
Trend Trigger Factor (December 2004)
True Range Specified Volume (November 2004)
Fibonacci and Gann Projections (October 2004)
Decomposition Method (September 2004)
Advance Issues Momentum (August 2004)
VFI Performance (July 2004)
Volume Flow Indicator (June 2004)
Inverse Fisher Transform (May 2004)
Trend Quality Indicator (April 2004)
Triangular Formations (March 2004)
Heikin-Ashi Technique (February 2004)
TRIX (January 2004)
Holding Overnight Positions (January 2004)
Divergence Bias (December 2003)
Price Swing (December 2003)
ZigZag Trend Indicator (November 2003)
Bull and Bear Balance Indicator (October 2003)
Index of Chart Sentiment (September 2003)
Detecting Breakouts Intraday (September 2003)
Strategies for DayTrading (August 2003)
Regularization (July 2003)
Thrust Oscillator (July 2003)
Reverse Engineering RSI (June 2003)
Implied Volatility And Volume (June 2003)
Fractal Dimension Index (May 2003)
Time and Money Charts (May 2003)
Finite Volume Elements (FVE) (April 2003)
Positive Volume Index/Negative Volume Index (April 2003)
Fibonacci Retracements And The RSI (March 2003)
Multiple Indicators (March 2003)
Z-Score (February 2003)
The Moving Trend (January 2003)
A Nonparametric Performance Measure (January 2003)
Developing Hot Zones (December 2002)
Testing Signal Efficacy (December 2002)
Fisher Transform (November 2002)
RSI Smoothed (October 2002)
Volatility Breakout (October 2002)
Cueing Off Support and Resistance Levels (September 2002)
Trading Fuzzy Patterns (September 2002)
ZigZag Validity (August 2002)
Center of Gravity Oscillator (August 2002)
RSI System (August 2002)
Zero-Lag Data Smoothers (July 2002)
Trading IBM Intraday (June 2002)
Trend Intensity Index (June 2002)
Projected Fibonacci Target (May 2002)
Daytrading Stock Pairs (May 2002)
Parabolic SAR (April 2002)
Head and Shoulders (April 2002)
If at first you don’t succeed… (March 2002)
Ehlers Instantaneous Trendline (February 2002)
Relative Vigor Index (January 2002)
RSI And Stochastics (December 2001)
Finding Key Reversals (December 2001)
Money Management Indicators (October 2001)
Nearest Neighbor Prediction (November 2001)
Money Management Indicators (October 2001)
Candle Code Training (September 2001)
MAMA (September 2001)
Balance of Power (August 2001)
Crude Oil (August 2001)
Elastic Moving Average (June 2001)
Which Volatility Measure? (Standard Deviation and Average True Range) (June 2001)
Relative Performance Charting (May 2001)
Volume Weighted Average Price (May 2001)
Nonlinear Ehlers Filters (April 2001)
Coding Candlesticks (March 2001)
Buff Up Your Moving Averages (February 2001)
The GAPO Index (January 2001)
Pattern Recognition (December 2000)
Optimizing With Hilbert Indicators (November 2000)
Ichimoku (October 2000)
Enhanced Fund Switching (October 2000)
Stock Screens (October 2000)
Normalization Techniques (October 2000)
Squelch (September 2000)
Catching DJIA Breakouts (August 2000)
Bollinger Band Targets (July 2000)
Trend Following System (June 2000)
Trend Friendly Oscillator Indicators (May 2000)
On Lag, Signal Processing, and The Hilbert Transform (March 2000)
MegaSeasonal System (February 2000)
More Responsive Moving Averages (January 2000)
Candlestick Filtering (December 1999)
Trading the Opening Gap (November 1999)
Sine Weighted Moving Average (June 1999)
Bollinger Bands (March 1999)
Stock Rhythm (February 1999)

7.1. Исторические данные.

NeuroShell Trader позволяет считывать стандартные текстовые файлы open/high/low/close/volume, файлы в формате MetaStock (включая версию 6), файлы данных в формате, используемом программами TradeStation, SuperCharts и Wall Street Analyst, и конечно файлы в собственном формате. С помощью NeuroShell Trader можно отображать данные на графиках, применять к ним технические индикаторы, использовать в качестве входов нейронной сети, конвертировать данные из исходного формата в текстовый формат.

7.2. Получение котировок real-time.

Для работы с NeuroShell DayTrader Вам понадобится связь с поставщиком данных в реальном времени. NeuroShell DayTrader поддерживает внутридневные real-time данные в форматах следующих поставщиков:

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

Генетические алгоритмы (ГА) — это стохастические, эвристические оптимизационные методы, впервые предложенные Джоном Холландом в 1975 году. Они основываются на идее эволюции с помощью естественного отбора. Кроме более быстрого нахождения экстремума, к положительным свойствам генетических алгоритмов можно отнести и нахождение «глобального» экстремума. В задачах, где целевая функция имеет значительное количество локальных экстремумов, в отличие от градиентного метода, генетические алгоритмы не «застревают» в точках локального экстремума, а позволяют найти «глобальный» минимум.

Генетические алгоритмы работают с совокупностью особей – популяцией , где каждая особь представляет возможное решение данной проблемы. Она оценивается мерой ее «приспособленности» согласно тому, насколько «хорошо» соответствующее ей решение задачи. В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы. Наиболее приспособленные особи получают возможность «воспроизводить» потомство с помощью «перекрестного скрещивания» с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции. Иногда происходят мутации, или спонтанные изменения в генах.

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

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

ГА производит над особями следующие действия

• Генерация начальной популяции хромосом – случайным образом выбираются значения параметров целевой функции и для этих значений параметров находится значение целевой функции.
• Селекция – выбор особей с наилучшей приспособленностью для воспроизводства (сортировка по значению целевой функции). Чем лучше приспособленность особи, тем выше ее шансы на скрещивание и наследование ее генов следующим поколением.
• Кроссовер – скрещивание. Случайным образом выбирается точка разрыва – участок между соседними битами в строке. Обе родительские структуры разрываются на два сегмента по этой точке. Затем, соответствующие сегменты различных родителей склеиваются и получаются два генотипа потомков.
• Мутация – случайное изменение генов. Случайным образом выбранный ген с некоторой вероятностью меняется на другой.
• Инверсия – изменение порядка следования частей кода. Случайным образом выбирается точка разрыва – участок между соседними битами в строке. Обе части родительские структуры, разорванной по этой точке, меняются местами, после чего склеиваются.

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

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

Целевая функция будет иметь вид

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

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

Инверсия будет изменять значение хромосомы на некоторую небольшую величину, таким образом осуществляя поиск в окрестностях точки с наилучшим решением.
Реализация на C++

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

Проектирование систем управления\Fuzzy Logic Toolbox

А.П.Ротштейн «Интеллектуальные технологии идентификации»

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

Как отмечалось в предисловии, оптимизация является важнейшим этапом решения задач идентификации. Основные трудности применения классических методов оптимизации нелинейных функций [10,58] связаны с проблемами локального экстремума (рис. 1.3) и (рис. 1.4).

Попытки преодоления указанных проблем привели к созданию теории генетических алгоритмов, которые выращивают оптимальное решение путем скрещивания исходных вариантов с последующей селекцией по некоторому критерию (рис. 1.5). Излагаемые в этом разделе общие сведения о генетических алгоритмах, базируются на работах [8,58,59,81]. Примеры, иллюстрирующие генетические алгоритмы, являются оригинальными.

Рис. 1.5. Идея генетического алгоритма (Goldberg D. Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley, 1989)

1.2.1. Принципы построения генетических алгоритмов

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

В отличие от существующих методик, ГА начинает работу с некоторого случайного набора исходных решений, который называется популяцией. Каждый элемент из популяции называется хромосомой и представляет некоторое решение проблемы в первом приближении. Хромосома представляет собой строку символов некоторой природы, не обязательно бинарных. Хромосомы эволюционируют на протяжении множества итераций, носящих название поколений (или генераций). В ходе каждой итерации хромосома оценивается с использованием некоторой меры соответствия (англ. fitness function ), которую мы будем называть функцией соответствия. Для создания следующего поколения новые хромосомы, называемые отпрысками, формируются либо путем скрещивания (англ. crossover) двух хромосом — родителей из текущей популяции, либо путем случайного изменения (мутации) одной хромосомы. Новая популяция формируется путем (а) выбора согласно функции соответствия некоторых родителей и отпрысков и (б) удаления оставшихся для того, чтобы сохранять постоянным размер популяции.

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

Процедура: Генетический алгоритм

Оценить с помощью функции соответствия;

while (нет условия_завершения) do

Cкрещивать чтобы получить ;

Оценить с помощью функции соответствия;

Таким образом, используются два вида операций:

1. Генетические операции: скрещивание и мутация;

2. Эволюционная операция: выбор.

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

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

Операция скрещивания. Скрещивание является главной генетической операцией. Эта операция выполняется над двумя хромосомами- родителями и создает отпрыск путем комбинирования особенностей обоих родителей. Приведем простейший пример скрещивания. В начале выберем некоторую случайную точку (точка скрещивания — англ. cut-point), после этого создадим хромосому-отпрыск путем комбинирования сегмента первого родителя, стоящего слева от выбранной точки скрещивания, с сегментом второго родителя, стоящего по правую сторону от точки скрещивания, как это показано на рис. 1.7.

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

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

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

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

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

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

1.2.4. Отличие от классического поиска

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

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

1.2.5. Преимущества генетических алгоритмов

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

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

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

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

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

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

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

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

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

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

Допустим нам нужно оптимизировать некоторую функцию F(X1,X2. Xn). Пусть мы ищем её глобальный максимум. Тогда, для реализации ГА нам нужно придумать, как мы будем хранить решения. По сути, нам нужно поместить все X1-Xn в некоторый вектор, который будет играть роль хромосомы. Один из наиболее распространенных способов — кодировать значения переменных в битовом векторе. Например, выделим каждому иксу по 8 бит. Тогда наш вектор будет длины L=8*n. Для простоты будем считать, что биты лежат в массиве X[0..L-1].

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

Тогда ГА будет состоять из следующих шагов:

1. Генерация начальной популяции — заполнение популяции особями, в которых элементы массива X (биты) заполнены случайным образом.
2. Выбор родительской пары — я всегда использую элитный отбор, то есть берем K особей с максимальными значениями функции F и составляю из них все возможные пары (K*(K-1)/2).
3. Кроссинговер — берем случайную точку t на массиве X (0..L-1).

Теперь, все элементы массива с индексами 0-t новой особи (потомка) заполняем элементами с теми-же индексами, но из массива X первой родительской особи. Остальные элементы заполняются из массива второй родительской особи. Для второго потомка делается наоборот — элементы 0-t берут от второго потомка, а остальные — от первого.

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

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

Кто придумал генетический алгоритм?

В 1966 г. Л.Дж.Фогель, А.Дж. Оуэнс, М.Дж.Волш предложили и исследовали эволюцию простых автоматов, предсказывающих символы в цифровых последовательностях. В 1975г. Д.Х.Холланд предложил схему генетического алгоритма. Эти работы легли в основу главных направлений разработки эволюционных алгоритмов.

Простой генетический алгоритм был впервые описан Гольдбергом на основе работ Холланда.

Преимущества генетических алгоритмов?

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

Недостатки генетических алгоритмов?

Не желательно и проблематично использовать ГА:

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

Alexander Pavlov [2:5030/399.11]

Необходимость поиска всех решений не является помехой. Исаев (статьи на www.algo.4u.ru) пишет: «. существует, по кpайней меpе, тpи класса задач, котоpые могут быть pешены пpедставленным алгоpитмом:

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

Для pешения втоpой задачи, очевидно, вопpосу «исследования» пpостpанства поиска должно уделяться гоpаздо большее внимание. Оно достигается за счет дpугого сочетания паpаметpов и достаточно большой численности популяции, пpи этом ГА сможет выделить несколько (или даже все) глобальные экстpемумы .

Для выделения нескольких глобальных максимумов, лучше использовать такую комбинацию [паpаметpов]: аутбpидинг в сочетании с инбpидингом, в качестве естественного отбоpа достаточно использовать элитный отбоp или отбоp с вытеснением (последний более надежный). Максимальная эффективность поиска достигается в сочетании аутбpидинга и инбpидинга, пpичем аутбpидинг pекомендуется использовать в начале поиска, достигая максимально шиpокого «исследования», а завеpшать поиск лучше уточнением pешения в локальных гpуппах, используя инбpидинг.»

Что такое простейший генетический алгоритм, схема, теорема Холланда?

В.М. Курейчик, статья

Механизм простого ГА (ПГА) несложен. Он копирует последовательности и переставляет их части. Предварительно ГА случайно генерирует популяцию последовательностей — стрингов (хромосом). Затем ГА применяет множество простых операций к начальной популяции и генерирует новые популяции.

ПГА состоит из 3 операторов: репродукция, кроссинговер, мутация.

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

После выполнения ОР оператор кроссинговера (ОК) может выполниться в несколько шагов На первом шаге выбираются члены нового репродуцированного множества хромосом. Далее каждая пара хромосом (стрингов) пересекается по следующему правилу: целая позиция k вдоль стринга выбирается случайно между l и длиной хромосомы минус единицу т.е. в интервале (1,L-1). Длина L хромосомы это число значащих цифр в его двоичном коде. Число k, выбранное случайно между первым и последним членами, называется точкой ОК или разделяющим знаком.

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

Генерация ГА начинается с репродукции. Мы выбираем хромосомы для следующей генерации, вращая колесо рулетки, такое количество раз, которое соответствует мощности начальной популяции. Величину отношения Fi(x)/SumF(x) называют вероятностью выбора копий (хромосом) при ОР и обозначают Pi(OP). Здесь Fi(x) — значение ЦФ i-той хромосомы в популяции, SumF(x) — суммарное значение ЦФ всех хромосом в популяции. Величину Pi(OP) также называют нормализованной величиной.

Лучшие брокеры без обмана

• 

  ☆☆☆☆☆

  ★★★★★

  Evotrade

  Бонусы для новых трейдеров до 5000$!

  Регистрация

• 

  ☆☆☆☆☆

  ★★★★★

  BINARIUM

  Лучший брокер по бинарным опционам. Огромный раздел по обучению.

  Регистрация

Ожидаемое число копий i-ой хромосомы после ОР определяют N=Pi(OP)*n. Здесь n — число анализируемых хромосом.

Число копий хромосомы, переходящее в следующее положение, иногда определяют на основе выражения Ai=Fi(x)/СреднееFi(x).

Далее, согласно схеме классического ПГА, выполняется оператор мутации. Считают, что мутация — вторичный механизм в ГА.

Понятие «схема» (схемата), согласно Холланду, есть шаблон, описывающий подмножество стрингов, имеющих подобные значения в некоторых позициях стринга. Для этого вводится новый алфавит <0,1,*>, где * — означает: не имеет значения 1 или 0. Для вычисления числа схем или их границы в популяции требуются точные значения о каждом стринге в популяции.

Для количественной оценки схем введены 2 характеристики: порядок схемы — О(H); определенная длина схемы — L(H).

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

Предположим, что заданы шаг (временной) t, m примеров частичных схем H, содержащихся в популяции A(t). Все это записывают как m=m(H,t) — возможное различное число различных схем H в различное время t.

В течение репродукции стринги копируются согласно их ЦФ или более точно: стринг A(i) получает выбор с вероятностью, определяемой Pi(OP).

После сбора непересекающихся популяций размера n с перемещением из популяции A(t) мы ожидаем иметь m(H,t+1) представителей схемы H в популяции за время t+1. Это вычисляется уравнением

где f(H) — есть средняя ЦФ стрингов, представленных схемой H за время t.

Если обозначить среднюю ЦФ всей популяции как f`=sum[f(j)]/n, тогда

Правило репродукции Холланда: схема с ЦФ выше средней «живет», копируется и с ниже средней ЦФ «умирает».

Предположим, что схема H остается с выше средней ЦФ с величиной c*f`, где c — константа. Тогда выражение (2) можно модифицировать так

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

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

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

Если ОК выполняется посредством случайного выбора, например, с вероятностью P(ОК), то вероятность выживания схемы определится Допуская независимость репродукции (ОР) и ОК, получим: Из выражения (6) следует, что схемы с выше средней ЦФ и короткой L(H) имеют возможность экспоненциального роста в новой популяции.

Рассмотрим влияние мутации на возможности выживания.

ОМ есть случайная альтернативная перестановка элементов в стринге с вероятностью Р(ОМ). Для того, чтобы схема H выжила, все специфические позиции должны выжить. Следовательно, единственная хромосома выживает с вероятностью (1-P(ОМ)) и частная схема выживает, когда каждая из l(H) закрепленных позиций схемы выживает.

Тогда мы ожидаем, что частная схема H получает ожидаемое число копий в следующей генерации после ОР,ОК ОМ

Это выражение называется «схема теорем» или фундаментальная теорема ГА.

Ответа на вопрос, почему необходимо давать выживание схемам с лучшей ЦФ, нет или он расплывчатый, или каждый раз зависит от конкретной задачи.

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

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

В элитарном ПГА не ясна роль «не элитных» особей.

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

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

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

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

Дэвид Бисслей, статья

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

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

Дэвид Бисслей, статья

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

vitalie vrabie [2:469/303]

Проще (и понятнее) будет сказать что многоточечный кроссинговер эквивалентен последовательному применению одноточечного кроссинговера несколько раз. То есть, имея n точек скрещивания: x_i, i=1..n, и хромосомы c1_0, c2_0, строим c1_i и c2_i путём скрещивания c1_(i-1) с c2_(i-1) в точке x_i. Повторять для i от 1 до n. c1_n, c2_n и будет результатом скрещивания c1_0, c2_0 в точках x_i, i=1..n.

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

Дэвид Бисслей, статья

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

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

Ilya S. Potrepalov [ispotrepalov@asu.tnk.ru]

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

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

Исходники некоторых кроссинговеров.

Вот вырезки из моих прог. Вполне можно прикрутить куда нужно 🙂

EBitSize — количество бит на одну переменную

Сырци вырезаны из задачи с 4-мя переменными.

Процедуры GetBit, SetBit и InvertBit — соответственно читают, устанавливают и инвертируют указанный бит в векторе (хромосоме). Если Вы храните каждый бит в byte и хромосома соответственно представлена массивом этих byte, процедурки можно сразу сменить на обращение к массиву 🙂

Что такое инверсия и переупорядочение?

Дэвид Бисслей, статья

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

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

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

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

Дэвид Бисслей, статья

Термин эпистаз был определен генетиками как влияние гена на пригодность индивидуума в зависимости от значения гена, присутствующего в другом месте. Более определенно, генетики используют термин эпистаз в смысле эффекта «переключения» или «маскирования». «Ген считают эпистатическим, когда его присутствие подавляет влияние гена в другом локусе. Эпистатические гены иногда называют ингибирующими из-за их влияния на другие гены, которые описываются как гипостаз».

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

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

Дэвид Бисслей, статья

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

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

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

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

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

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

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

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

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

Пример определения родства хромосом при выборе родительской пары для хромосомы 1010001:

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

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

Alexander Pavlov [2:5030/399.11]

По поводу источника. Hачало, по кpайней меpе, с www.algo.4u.ru, статья Д.И. Батищева, С.А. Исаева «Оптимизация многоэкстpемальных функций с помощью генетических алгоpитмов» (опубликовано в сбоpнике статей, издаваемом ВГТУ, осень 1997).

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

Зачастую, выбор параметров генетического алгоритма и конкретных генетических операторов производится на интуитивном уровне, так как пока не существует объективных доказательств преимущества тех или иных настроек и операторов. Однако, не нужно забывать, что сама суть ГА заключается в динамике и «мягкости» алгоритма и производимых вычислений. Тогда почему бы не позволить алгоритму самому настраиваться во время решения задачи и адаптироваться к ней?

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

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

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

В.В Курейчик, статья

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

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

В.В Курейчик, статья

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

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

Почему у меня популяция пpи малых размерах вообще не сходится?

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

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

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

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

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

Разное.

vitalie vrabie [2:469/303]

ГА, однородный побитовый recombination, elitistic selection, все вектора одинакового размера.

Ввёл такое понятие: «однородность» (степень однородности) популяции. Определяется отношением количества одинаковых битов к общему их числу в векторе.

Поясню на примере. Скажем, вектор из 10 бит. При следующей популяции:

Имеем «однородность» равную 6/10 (шесть из десяти битов у всех одинаковые — в помеченных позициях).

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

ГА не рекомендуется, если нужно найти точный глобальный экстремум. Почему?

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

На каких функциях проверить мой генетический алгоритм?

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

• Функция Растригина. Число переменных 2. Максимумов — 96 локальных, 4 глобальных.
• Griewank. Число переменных 2. Максимумов — множество локальных и 1 глобальный.
• Функция Растригина. Число переменных 10. Максимумов — (10^10)-1 локальных и 1 глобальный.

Назад | Оглавление | Далее

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

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

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

Впервые подобный алгоритм был предложен в 1975 году Дж. Холландом (John Holland) в Мичиганском университете. Он получил название «репродуктивный план Холланда» и лег в основу практически всех вариантов генетических алгоритмов.

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

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

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

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

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

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

Допустим, разрыв происходит после 3-го бита хромосомы, тогда

Хромосома_1: 0000000000 >> 000 1111111 Результирующая_хромосома_1

Хромосома_2: 1111111111 >> 111 0000000 Результирующая_хромосома_2

Затем с вероятностью 0,5 определяется одна из результирующих хромосом в качестве потомка.

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

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

000 1111111 >> 1111111 000

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

Схема функционирования генетического алгоритма

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

1. Инициировать начальный момент времени t=0. Случайным образом сформировать начальную популяцию, состоящую из k особей. B₀ = 1,A₂,…,A_k)
2. Вычислить приспособленность (пригодность) каждой особи F_Ai = fit(A_i) , i=1…k и популяции в целом F_t = fit(B_t) (также иногда называемую термином фиттнес). Значение этой функции определяет насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи.
3. Выбрать особь A_c из популяции. A_c = Get(B_t)
4. С определенной вероятностью (вероятностью кроссовера P_c) выбрать вторую особь из популяции А_c1 = Get(B_t) и произвести оператор кроссовера A_c = Crossing(A_c,A_c1).
5. С определенной вероятностью (вероятностью мутации P_m) выполнить оператор мутации. A_c = mutation(A_c).
6. С определенной вероятностью (вероятностью инверсии P_i) выполнить оператор инверсии A_c = inversion(A_c).
7. Поместить полученную хромосому в новую популяцию insert(B_t+1,A_c).
8. Выполнить операции, начиная с пункта 3, k раз.
9. Увеличить номер текущей эпохи t=t+1.
10. Если выполнилось условие останова, то завершить работу, иначе переход на шаг 2.

Рассмотрим подробнее отдельные этапы алгоритма.

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

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

Другой важный момент – определение критериев останова.

В качестве критериев останова алгоритма могут использоваться такие:

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

Пример

Найти максимум функции f(x)=x2 в диапазоне 0

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

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

ЧАСТЬ II ИССЛЕДОВАНИЕ входов в РЫНОК

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

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

Genetic algorithm

In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger >[1] John Holland introduced genetic algorithms in 1960 based on the concept of Darwin’s theory of evolution; afterwards, his student Dav >[2]

Contents

Methodology [ edit ]

Optimization problems [ edit ]

In a genetic algorithm, a population of cand >[3]

The evolution usually starts from a population of randomly generated individuals, and is an iterative process, with the population in each iteration called a generation. In each generation, the fitness of every individual in the population is evaluated; the fitness is usually the value of the objective function in the optimization problem being solved. The more fit individuals are stochastically selected from the current population, and each individual’s genome is modified (recombined and possibly randomly mutated) to form a new generation. The new generation of candidate solutions is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population.

A typical genetic algorithm requires:

1. a genetic representation of the solution domain,
2. a fitness function to evaluate the solution domain.

A standard representation of each cand >[3] Arrays of other types and structures can be used in essentially the same way. The main property that makes these genetic representations convenient is that their parts are easily aligned due to their fixed size, which facilitates simple crossover operations. Variable length representations may also be used, but crossover implementation is more complex in this case. Tree-like representations are explored in genetic programming and graph-form representations are explored in evolutionary programming; a mix of both linear chromosomes and trees is explored in gene expression programming.

Once the genetic representation and the fitness function are defined, a GA proceeds to initialize a population of solutions and then to improve it through repetitive application of the mutation, crossover, inversion and selection operators.

Initialization [ edit ]

The population size depends on the nature of the problem, but typically contains several hundreds or thousands of possible solutions. Often, the initial population is generated randomly, allowing the entire range of possible solutions (the search space). Occasionally, the solutions may be «seeded» in areas where optimal solutions are likely to be found.

Selection [ edit ]

During each successive generation, a portion of the existing population is selected to breed a new generation. Individual solutions are selected through a fitness-based process, where fitter solutions (as measured by a fitness function) are typically more likely to be selected. Certain selection methods rate the fitness of each solution and preferentially select the best solutions. Other methods rate only a random sample of the population, as the former process may be very time-consuming.

The fitness function is defined over the genetic representation and measures the quality of the represented solution. The fitness function is always problem dependent. For instance, in the knapsack problem one wants to maximize the total value of objects that can be put in a knapsack of some fixed capacity. A representation of a solution might be an array of bits, where each bit represents a different object, and the value of the bit (0 or 1) represents whether or not the object is in the knapsack. Not every such representation is valid, as the size of objects may exceed the capacity of the knapsack. The fitness of the solution is the sum of values of all objects in the knapsack if the representation is valid, or 0 otherwise.

In some problems, it is hard or even impossible to define the fitness expression; in these cases, a simulation may be used to determine the fitness function value of a phenotype (e.g. computational fluid dynamics is used to determine the air resistance of a vehicle whose shape is encoded as the phenotype), or even interactive genetic algorithms are used.

Genetic operators [ edit ]

The next step is to generate a second generation population of solutions from those selected through a combination of genetic operators: crossover (also called recombination), and mutation.

For each new solution to be produced, a pair of «parent» solutions is selected for breeding from the pool selected previously. By producing a «child» solution using the above methods of crossover and mutation, a new solution is created which typically shares many of the characteristics of its «parents». New parents are selected for each new child, and the process continues until a new population of solutions of appropriate size is generated. Although reproduction methods that are based on the use of two parents are more «biology inspired», some research [4] [5] suggests that more than two «parents» generate higher quality chromosomes.

These processes ultimately result in the next generation population of chromosomes that is different from the initial generation. Generally the average fitness will have increased by this procedure for the population, since only the best organisms from the first generation are selected for breeding, along with a small proportion of less fit solutions. These less fit solutions ensure genetic diversity within the genetic pool of the parents and therefore ensure the genetic diversity of the subsequent generation of children.

Opinion is divided over the importance of crossover versus mutation. There are many references in Fogel (2006) that support the importance of mutation-based search.

Although crossover and mutation are known as the main genetic operators, it is possible to use other operators such as regrouping, colonization-extinction, or migration in genetic algorithms. [6]

It is worth tuning parameters such as the mutation probability, crossover probability and population size to find reasonable settings for the problem class being worked on. A very small mutation rate may lead to genetic drift (which is non-ergodic in nature). A recombination rate that is too high may lead to premature convergence of the genetic algorithm. A mutation rate that is too high may lead to loss of good solutions, unless elitist selection is employed.

Heuristics [ edit ]

In addition to the main operators above, other heuristics may be employed to make the calculation faster or more robust. The speciation heuristic penalizes crossover between cand >[7] [8]

Termination [ edit ]

This generational process is repeated until a termination condition has been reached. Common terminating conditions are:

• A solution is found that satisfies minimum criteria
• Fixed number of generations reached
• Allocated budget (computation time/money) reached
• The highest ranking solution’s fitness is reaching or has reached a plateau such that successive iterations no longer produce better results
• Manual inspection
• Combinations of the above

The building block hypothesis [ edit ]

Genetic algorithms are simple to implement, but their behavior is difficult to understand. In particular it is difficult to understand why these algorithms frequently succeed at generating solutions of high fitness when applied to practical problems. The building block hypothesis (BBH) consists of:

1. A description of a heuristic that performs adaptation by identifying and recombining «building blocks», i.e. low order, low defining-length schemata with above average fitness.
2. A hypothesis that a genetic algorithm performs adaptation by implicitly and efficiently implementing this heuristic.

Goldberg describes the heuristic as follows:

«Short, low order, and highly fit schemata are sampled, recombined [crossed over], and resampled to form strings of potentially higher fitness. In a way, by working with these particular schemata [the building blocks], we have reduced the complexity of our problem; instead of building high-performance strings by trying every conceivable combination, we construct better and better strings from the best partial solutions of past samplings. «Because highly fit schemata of low defining length and low order play such an important role in the action of genetic algorithms, we have already given them a special name: building blocks. Just as a child creates magnificent fortresses through the arrangement of simple blocks of wood, so does a genetic algorithm seek near optimal performance through the juxtaposition of short, low-order, high-performance schemata, or building blocks.» [9]

Despite the lack of consensus regarding the val >[10] [11] Although good results have been reported for some >[12] [13] [14]

Limitations [ edit ]

There are limitations of the use of a genetic algorithm compared to alternative optimization algorithms:

• Repeated fitness function evaluation for complex problems is often the most prohibitive and limiting segment of artificial evolutionary algorithms. Finding the optimal solution to complex high-dimensional, multimodal problems often requires very expensive fitness function evaluations. In real world problems such as structural optimization problems, a single function evaluation may require several hours to several days of complete simulation. Typical optimization methods cannot deal with such types of problem. In this case, it may be necessary to forgo an exact evaluation and use an approximated fitness that is computationally efficient. It is apparent that amalgamation of approximate models may be one of the most promising approaches to convincingly use GA to solve complex real life problems.
• Genetic algorithms do not scale well with complexity. That is, where the number of elements which are exposed to mutation is large there is often an exponential increase in search space size. This makes it extremely difficult to use the technique on problems such as designing an engine, a house or a plane. In order to make such problems tractable to evolutionary search, they must be broken down into the simplest representation possible. Hence we typically see evolutionary algorithms encoding designs for fan blades instead of engines, building shapes instead of detailed construction plans, and airfoils instead of whole aircraft designs. The second problem of complexity is the issue of how to protect parts that have evolved to represent good solutions from further destructive mutation, particularly when their fitness assessment requires them to combine well with other parts.
• The «better» solution is only in comparison to other solutions. As a result, the stop criterion is not clear in every problem.
• In many problems, GAs have a tendency to converge towards local optima or even arbitrary points rather than the global optimum of the problem. This means that it does not «know how» to sacrifice short-term fitness to gain longer-term fitness. The likelihood of this occurring depends on the shape of the fitness landscape: certain problems may prov >[15] although the No Free Lunch theorem[16] proves that there is no general solution to this problem. A common technique to maintain diversity is to impose a «niche penalty», wherein, any group of indiv >Variants [ edit ]

Chromosome representation [ edit ]

The simplest algorithm represents each chromosome as a bit string. Typically, numeric parameters can be represented by integers, though it is possible to use floating point representations. The floating point representation is natural to evolution strategies and evolutionary programming. The notion of real-valued genetic algorithms has been offered but is really a misnomer because it does not really represent the building block theory that was proposed by John Henry Holland in the 1970s. This theory is not without support though, based on theoretical and experimental results (see below). The basic algorithm performs crossover and mutation at the bit level. Other variants treat the chromosome as a list of numbers which are indexes into an instruction table, nodes in a linked list, hashes, objects, or any other imaginable data structure. Crossover and mutation are performed so as to respect data element boundaries. For most data types, specific variation operators can be designed. Different chromosomal data types seem to work better or worse for different specific problem domains.

When bit-string representations of integers are used, Gray coding is often employed. In this way, small changes in the integer can be readily affected through mutations or crossovers. This has been found to help prevent premature convergence at so-called Hamming walls, in which too many simultaneous mutations (or crossover events) must occur in order to change the chromosome to a better solution.

Other approaches involve using arrays of real-valued numbers instead of bit strings to represent chromosomes. Results from the theory of schemata suggest that in general the smaller the alphabet, the better the performance, but it was initially surprising to researchers that good results were obtained from using real-valued chromosomes. This was explained as the set of real values in a finite population of chromosomes as forming a virtual alphabet (when selection and recombination are dominant) with a much lower cardinality than would be expected from a floating point representation. [17] [18]

An expansion of the Genetic Algorithm accessible problem domain can be obtained through more complex encoding of the solution pools by concatenating several types of heterogenously encoded genes into one chromosome. [19] This particular approach allows for solving optimization problems that require vastly disparate definition domains for the problem parameters. For instance, in problems of cascaded controller tuning, the internal loop controller structure can belong to a conventional regulator of three parameters, whereas the external loop could implement a linguistic controller (such as a fuzzy system) which has an inherently different description. This particular form of encoding requires a specialized crossover mechanism that recombines the chromosome by section, and it is a useful tool for the modelling and simulation of complex adaptive systems, especially evolution processes.

Elitism [ edit ]

A practical variant of the general process of constructing a new population is to allow the best organism(s) from the current generation to carry over to the next, unaltered. This strategy is known as elitist selection and guarantees that the solution quality obtained by the GA will not decrease from one generation to the next. [20]

Parallel implementations [ edit ]

Parallel implementations of genetic algorithms come in two flavors. Coarse-grained parallel genetic algorithms assume a population on each of the computer nodes and migration of individuals among the nodes. Fine-grained parallel genetic algorithms assume an individual on each processor node which acts with neighboring individuals for selection and reproduction. Other variants, like genetic algorithms for online optimization problems, introduce time-dependence or noise in the fitness function.

Adaptive GAs [ edit ]

Genetic algorithms with adaptive parameters (adaptive genetic algorithms, AGAs) is another significant and promising variant of genetic algorithms. The probabilities of crossover (pc) and mutation (pm) greatly determine the degree of solution accuracy and the convergence speed that genetic algorithms can obtain. Instead of using fixed values of pc and pm, AGAs utilize the population information in each generation and adaptively adjust the pc and pm in order to maintain the population diversity as well as to sustain the convergence capacity. In AGA (adaptive genetic algorithm), [21] the adjustment of pc and pm depends on the fitness values of the solutions. In CAGA (clustering-based adaptive genetic algorithm), [22] through the use of clustering analysis to judge the optimization states of the population, the adjustment of pc and pm depends on these optimization states. It can be quite effective to combine GA with other optimization methods. GA tends to be quite good at finding generally good global solutions, but quite inefficient at finding the last few mutations to find the absolute optimum. Other techniques (such as simple hill climbing) are quite efficient at finding absolute optimum in a limited region. Alternating GA and hill climbing can improve the efficiency of GA [ citation needed ] while overcoming the lack of robustness of hill climbing.

This means that the rules of genetic variation may have a different meaning in the natural case. For instance – prov >[23]

A variation, where the population as a whole is evolved rather than its individual members, is known as gene pool recombination.

A number of variations have been developed to attempt to improve performance of GAs on problems with a high degree of fitness epistasis, i.e. where the fitness of a solution consists of interacting subsets of its variables. Such algorithms aim to learn (before exploiting) these beneficial phenotypic interactions. As such, they are aligned with the Building Block Hypothesis in adaptively reducing disruptive recombination. Prominent examples of this approach include the mGA, [24] GEMGA [25] and LLGA. [26]

Problem domains [ edit ]

Problems which appear to be particularly appropriate for solution by genetic algorithms include timetabling and scheduling problems, and many scheduling software packages are based on GAs [ citation needed ] . GAs have also been applied to engineering. [27] Genetic algorithms are often applied as an approach to solve global optimization problems.

As a general rule of thumb genetic algorithms might be useful in problem domains that have a complex fitness landscape as mixing, i.e., mutation in combination with crossover, is designed to move the population away from local optima that a traditional hill climbing algorithm might get stuck in. Observe that commonly used crossover operators cannot change any uniform population. Mutation alone can provide ergodicity of the overall genetic algorithm process (seen as a Markov chain).

Examples of problems solved by genetic algorithms include: mirrors designed to funnel sunlight to a solar collector, [28] antennae designed to pick up radio signals in space, [29] walking methods for computer figures, [30] optimal design of aerodynamic bodies in complex flowfields [31]

In his Algorithm Design Manual, Skiena advises against genetic algorithms for any task:

[I]t is quite unnatural to model applications in terms of genetic operators like mutation and crossover on bit strings. The pseudobiology adds another level of complexity between you and your problem. Second, genetic algorithms take a very long time on nontrivial problems. [. ] [T]he analogy with evolution—where significant progress require [sic] millions of years—can be quite appropriate.

I have never encountered any problem where genetic algorithms seemed to me the right way to attack it. Further, I have never seen any computational results reported using genetic algorithms that have favorably impressed me. Stick to simulated annealing for your heuristic search voodoo needs.

History [ edit ]

In 1950, Alan Turing proposed a «learning machine» which would parallel the principles of evolution. [33] Computer simulation of evolution started as early as in 1954 with the work of Nils Aall Barricelli, who was using the computer at the Institute for Advanced Study in Princeton, New Jersey. [34] [35] His 1954 publication was not w >[36] the Australian quantitative geneticist Alex Fraser published a series of papers on simulation of artificial selection of organisms with multiple loci controlling a measurable trait. From these beginnings, computer simulation of evolution by biologists became more common in the early 1960s, and the methods were described in books by Fraser and Burnell (1970) [37] and Crosby (1973). [38] Fraser’s simulations included all of the essential elements of modern genetic algorithms. In addition, Hans-Joachim Bremermann published a series of papers in the 1960s that also adopted a population of solution to optimization problems, undergoing recombination, mutation, and selection. Bremermann’s research also included the elements of modern genetic algorithms. [39] Other noteworthy early pioneers include Richard Friedberg, George Friedman, and Michael Conrad. Many early papers are reprinted by Fogel (1998). [40]

Although Barricelli, in work he reported in 1963, had simulated the evolution of ability to play a simple game, [41] artificial evolution became a w >[42] [43] [44] [45] Another approach was the evolutionary programming technique of Lawrence J. Fogel, which was proposed for generating artificial intelligence. Evolutionary programming originally used finite state machines for predicting environments, and used variation and selection to optimize the predictive logics. Genetic algorithms in particular became popular through the work of John Holland in the early 1970s, and particularly his book Adaptation in Natural and Artificial Systems (1975). His work originated with studies of cellular automata, conducted by Holland and his students at the University of Michigan. Holland introduced a formalized framework for predicting the quality of the next generation, known as Holland’s Schema Theorem. Research in GAs remained largely theoretical until the mid-1980s, when The First International Conference on Genetic Algorithms was held in Pittsburgh, Pennsylvania.

Commercial products [ edit ]

In the late 1980s, General Electric started selling the world’s first genetic algorithm product, a mainframe-based toolkit designed for industrial processes. [46] In 1989, Axcelis, Inc. released Evolver, the world’s first commercial GA product for desktop computers. The New York Times technology writer John Markoff wrote [47] about Evolver in 1990, and it remained the only interactive commercial genetic algorithm until 1995. [48] Evolver was sold to Palisade in 1997, translated into several languages, and is currently in its 6th version. [49]

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

Основываясь на моделях, используемых в биологии и экономике, мате­матик и психолог Джон Холланд (John Holland ) разработал алгоритм ге­нетической оптимизации. Алгоритм впервые был опубликован в книге Холланда Адаптация в естественных и искусственных системах (J . Holland , Adaptation in Natural and Artificial Systems , 1975). Генетичес­кие алгоритмы (ГА) впервые стали применяться в компьютерных дисцип­линах в начале 1990-х годов (Yuret and de la Maza , 1994). Торговое сообще­ство впервые обратило на них внимание около 1993г., когда появилось несколько статей (Burke , 1993; Katz and McCormick , 1994; Oliver , 1994) и компьютерных программ. С тех пор несколько фирм добавили генетичес­кое обучение в свои программные пакеты, а у некоторых есть даже про­граммы генетической оптимизации профессионального уровня.

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

В данной книге представлен общий обзор ГА и их применения в торгов­ле. Читателям, заинтересованным в детальном изучении этого предмета, следует прочитать книгу Девиса (Davis , 1991), а также нашу главу в книге Virtual Trading (Katz , McCormick , 1995a , 1995b ) и наши статьи (Katz , McCormick , июль/август 1994, декабрь 1996, январь 1997, февраль 1997).

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

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

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

РАЗВИТИЕ МОДЕЛЕЙ ВХОДА , ОСНОВАННЫХ НА ПРАВИЛАХ

Что бы произошло, если ГА позволяли искать не просто лучшие парамет­ры (именно так чаще всего используют ГА), но и лучшие правила? В этой главе приводится результат использования ГА для развития законченной модели входа путем поиска оптимальных правил и параметров для этих правил. Несмотря на сложность, эта методология оказалась эффективной в нашем первом исследовании (Katz , McCormick , февраль 1997).

Как можно использовать ГА для поиска наилучших торговых правил? Доморощенный ГА просто жонглирует числами. Необходимо найти спо­соб нумерации различных наборов правил. Этого можно достичь мно­гими способами. Простой и эффективный метод включает в себя пост­роение набора шаблонов правил. Шаблон правила — это частичное опи­сание правила с оставленными пробелами, которые необходимо запол­нить. Например, если некоторые из правил предыдущих глав рассмот­реть как шаблоны правил, то пробелами будут значения периодов ус­реднения, порогов и других параметров. Шаблоны правил, определен­ные таким образом, несложно пронумеровать, поставив в соответствие каждому шаблону набор чисел. Первое число в наборе используется как индекс в таблице шаблонов правил. Оставшиеся числа набора исполь­зуются для заполнения пробелов в шаблоне, в результате чего мы полу­чаем четко определенное правило. Приведенный ниже компьютерный код содержит функцию C ++ (Rules ), которая производит нумерацию шаблонов; она будет описана позже. Хотя в данном исследовании использовался язык C ++, данный метод также можно реализовать в TradeStation с помощью программы TS -EVOLVE , созданной Scientific Consultant Services (516-696-3333).

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

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

Лучшие брокеры с бонусами:

• 

  ☆☆☆☆☆

  ★★★★★

  Evotrade

  Бонусы для новых трейдеров до 5000$!

  Регистрация

• 

  ☆☆☆☆☆

  ★★★★★

  BINARIUM

  Лучший брокер по бинарным опционам. Огромный раздел по обучению.

  Регистрация

Forex

Управление советниками для Форекс

Читать далее

Forex

Советники для Форекс puria

Читать далее

Forex

Спокойные советники для Форекса

Читать далее

Forex

Статистика сигналов для Форекс

Читать далее

Forex

Стратегии для Форекс периодов

Читать далее

Forex

Стратегия для Форекса money

Читать далее

Forex

Страхование рисков для Форекс

Читать далее

Forex

Теория импульсов для Форекс

Читать далее

Forex

Торговая математика для Форекс

Читать далее

Forex

Три индейца стратегия для Форекс

Читать далее

Forex

Советники для Форекс bollinger

Читать далее

Forex

Установка стратегий для Форекс

Читать далее

Forex

Финансовое посредничество для Форекс

Читать далее

Forex

Форекс брокер forexstart

Читать далее

Forex

Форекс или турбоФорекс — что лучше

Читать далее

Forex

Форекс индикатор moneyges

Читать далее

Forex

Форекс индикатор xo mtf

Читать далее

Forex

Форекс комментарии и отзывы

Читать далее

Forex

Форекс советник master

Читать далее

Forex

Swap free счета для Форекс

Читать далее

Forex

Трейдинг акциями с чего начинать

Читать далее

Forex

Трейдинг и инвестиции от рената сейтуарова

Читать далее

Forex

Трейдинг от александра шевелева

Читать далее

Forex

Трейдинг через интернет

Читать далее

Forex

60 секунд или Турбо в трейдинге

Читать далее

Forex

Dinapoli индикатор для Форекс

Читать далее

Forex

Hilo стратегия для Форекс

Читать далее

Forex

Megadroid для Форекс советник

Читать далее

Forex

Privat finance для Форекса

Читать далее

Forex

Трейдер Шаман

Читать далее

Forex

Winning solution для Форекс

Читать далее

Forex

Автоматический индикатор для Форекса

Читать далее

Forex

Актуальная аналитика для Форекс

Читать далее

Forex

Американские индикаторы для Форекс

Читать далее

Forex

Аналитика для Форекса по йене

Читать далее

Forex

Ассоциация трейдеров для Форекс

Читать далее

Forex

Баскет трейдинг для Форекс

Читать далее

Forex

Беспроигрышные тактики для Форекса

Читать далее

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

Нажмите, чтобы отменить ответ.

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

Part of a series on the
Evolutionary algorithm
Artificial development Cellular evolutionary algorithm Cultural algorithm Differential evolution Effective fitness Evolution strategy Gaussian adaptation Evolutionary multimodal optimization Grammatical evolution Particle swarm optimization Memetic algorithm Natural evolution strategy Promoter based genetic algorithm Spiral optimization algorithm
Genetic algorithm
Chromosome Clonal selection algorithm Crossover Mutation Genetic memory Genetic fuzzy systems Selection Fly algorithm
Genetic programming
Cartesian genetic programming Linear genetic programming Multi expression programming Schema Eurisko Parity benchmark