Эволюционные вычисления


Содержание

Эволюционные вычисления

Данный документ может свободно распространяться и использоваться при выполнении следующих условий:

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

Любые притензии по поводу содержимого рассматриваются составителем, но не обязательно удовлетворяются ;)

Исходники ищите по приведенным ссылкам, так как они (исходники) давольно тяжелые.

Эволюционные вычисления

Курейчик В.М., Родзин С.И.

ВВЕДЕНИЕ

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

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

1. ДОСТОИНСТВА И НЕДОСТАТКИ ЭВОЛЮЦИОННЫХ ВЫЧИСЛЕНИЙ

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

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

  1. Установка параметров эволюции;
  2. Инициализация начальной популяции P(0);
  3. t:=0;
  4. Оценка решений, входящих в популяцию;
  5. t:=t+1;
  6. Селекция (отбор);
  7. Репликация (повторение, копирование, аутосинтез);
  8. Вариация (видоизменение);
  9. Оценка решений-потомков;
  10. Образование новой популяции P(t);
  11. Выполнение алгоритма до тех пор, пока параметр t не достигнет заданного значения tmax либо не будут выполнены другие условия останова.
  12. Вывод результатов и останов.

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

Предпринятая в [3] попытка сравнительного анализа конкурирующих эвристических алгоритмов с точки зрения их результативности, даже при том, что NFL-теорема не учитывает время решения оптимизационной задачи, имеет два важных практических следствия:

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

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

Достоинства эволюционных вычислений:

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

Недостатки эволюционных вычислений:

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

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

Рассмотрим подробнее две относительно малоисследованные формы эволюционных вычислений: генетическое и эволюционное программирование.

2. ГЕНЕТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ И КОМПЬЮТЕРНЫЙ СИНТЕЗ МАТЕМАТИЧЕСКИХ ВЫРАЖЕНИЙ

Проблемы компьютерного синтеза программ стали одним из направлений искусственного интеллекта примерно в конце 50-х годов. Интерес исследователей к данной проблематике резко возрос благодаря работам Дж. Коза, посвященным генетическому программированию [6] и направленным на решение задач автоматического синтеза программ на основе обучающих данных путем индуктивного вывода.

Хромосомы или математические выражения, которые автоматически генерируются с помощью генетических операторов, являются компьютерными программами различной величины и сложности. Программы состоят из функций, переменных и констант. Исходная популяция P(0) хромосом в ГП образуется стохастически и состоит из программ, которые включают в себя элементы множества проблемно-ориентированных элементарных функций (function set: +, , ?, *, %, sin, сos, log, or, and, for, do-until и пр., а также любая другая функция из предметной области задачи), проблемно-ориентированные переменные и константы (terminal set: ephemeral random – константы регрессионных функций с коротким временем жизни; T, Nil– булевы константы; вещественные константы принимающие значение на отрезке [-1.000; 1.000] с шагом 0.001). Множества function set и terminal set являются основой для эволюционного синтеза программы, способной наилучшим образом решать поставленную задачу. Одновременно устанавливаются правила выбора элементов из указанных множеств в пространстве всех потенциально синтезируемых программ, структура которых имеет древовидную форму.

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

Стартовыми условиями для ГП являются установка множеств terminal set и function set; определение подходящего вида функции соответствия (fitness-function); установка параметров эволюции; определение критерия останова моделирования эволюции и правил декодирования результатов эволюции.

Способом оценки качества функции соответствия в ГП является среднеквадратичная ошибка (чем она меньше, тем лучше программа) или критерий «выигрыша», согласно которому выигрыш определяется в зависимости от степени близости к корректному значению математического выражения. Размер популяции ? в ГП обычно составляет несколько тысяч программ. Для максимального числа генераций tmax используется значение tmax=51.

Рассмотрим подробнее процедуру ГП.

  1. Инициализация. На этом этапе стохастически генерируется популяция P(0), состоящая из µ древовидных программ, причем корневой вершиной дерева всегда является функция, аргументы которой выбираются случайно из множеств function set или terminal set. Концевыми вершинами дерева должны быть переменные или константы, в противном случае процесс генерации необходимо рекурсивно продолжить. Если структура дерева становится сложной, то заранее устанавливается максимальная высота дерева, равная числу ребер дерева, которое содержит самый длинный путь от корневой вершины до некоторой концевой вершины. В экспериментах обычно максимальная высота дерева колеблется от шести для популяции P(0) до 17 в более поздних популяциях P(t).
  2. Оценка решений. Оценивается целевая функция каждой программы в P(0). Поскольку все программы выбраны случайно, то большинство из них могут иметь значение целевой функции далекое от лучшего решения, поэтому в качестве оценки можно взять разницу между лучшим и худшим значением функции в популяции P(0).
  3. Генерация новой популяции и селекция. Основными операторами ГП являются рекомбинация (кроссинговер) и репродукция, селекция и репликация, выполняемые по схемам, аналогичным генетическим алгоритмам [7]. Если к некоторой программе применяют оператор репродукции, то эта программа копируется в новую популяцию. Для проведения кроссинговера выбираются две родительские хромосомы (программы), случайным образом определяются точки кроссинговера и путем обмена образуются два потомка. При программной реализации на языке LISP кроссинговер сводится к обмену списками между двумя программами при сохранении синтаксической корректности вновь получаемых программ.
  4. Проверка критерия остановки. Процедура ГП является итерационной, критерии останова аналогичны критериям для генетических алгоритмов.

Проиллюстрируем рассмотренную процедуру на примере вычисления разности объемов двух параллелепипедов. Пусть два параллелепипеда задаются шестью независимыми переменными L1,B1,H1,L2,B2,H2 и одной зависимой переменной D. Для получения корректных значений величины D установим следующие стартовые условия:

  • terminal set: =< L1,B1,H1,L2,B2,H2>;
  • function set: =<+,-,*,%>;
  • функция соответствия указывает абсолютную ошибку, определяемую разностью между корректным значением D и тем значением, которое получается программно;
  • выигрыш определяется числом случаев, когда сравниваемые величины D различаются менее, чем на 0.01;
  • mu=4000;
  • программа останавливается, если число выигрышей равно 10, либо tmax=51.

В табл. 1 представлены 10 различных вариантов исходных значений для шести независимых переменных, а также разность объемов D= L1*B1*H1-L2*B2*H2.

Исходные данные для вычисления разности объемов двух параллелепипедов

В результате моделирования эволюции для популяции P(0) лучшее значение D=783, что соответствовало следующему выражению:

(*(?(?B1L2)(?B2H1))(+(?H1H1)(*H1L1))) или H1L1(B1+H1?B2?L2).

Видно, что в данном математическом выражении отсутствует переменная H2 и оно мало похоже на корректное решение. Далее, лучшие значения D в популяциях P(1)-P(6) имели значения 778, 510, 138, 117, 53, 51 соответственно. Лучшая программа на восьмом этапе эволюции дала значение D, равное 4.44, что соответствовало LISP-выражению следующего вида:

или B1H1L1?B2H2L2?(B1+L1)/(L1?2B2?L2?L2B2).

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

(?(*(*B1H1)L1)(*(*L2H2)B2)) или L1B1H1?L2B2H2.

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

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

Однако имеется целый ряд задач, свидетельствующих об обратном. Рассмотрим одну из них, связанную с проверкой на четность. Пусть булева функция, зависящая от пяти аргументов (D0,D1,D2,D3,D4), принимает значение T, если четное число аргументов принимают значение «истина», в противном случае, булева функция принимает значение Nil (константа, обозначающая список, в котором нет ни одного элемента); 32 возможных комбинации аргументов служат основой для оценки ГП с ADF и без ADF.

Для ГП без ADF и с ADF устанавливаются одинаковые стартовые условия и параметры эволюции: функция соответствия определяется числом совпадений значений исходной функции со значениями, выдаваемыми ГП; ?=16000; программа останавливается, если число совпадений равно 32.

Результаты моделирования однозначно свидетельствуют о преимуществе ГП с ADF как по структурной сложности решений, так и по вычислительной трудоемкости.

Другим перспективным направлением в ГП является применение в качестве оператора поиска не только кроссинговера, но и мутации, а также реализацию ГП на транспьютерных вычислительных системах. Существенное увеличение быстродействия ГП может быть получено и на последовательных машинах. В частности, реализация ГП на языке C увеличивает скорость ГП примерно на два порядка, а реализация ГП в машинных кодах ? примерно на три порядка в сравнении с LISP-реализациями.

Авторы [8], исследуя решения различной длины, получаемые с помощью ГП, обратили внимание на так называемый эффект «компрессионного давления», которым обладают решения с малой структурной сложностью. Программы, генерируемые по методу ГП, как уже отмечалось выше, зачастую содержат «лишние» блоки, не влияющие на функциональные возможности программы и на целевую функцию. В генетике это соответствует понятию интрона, который является нечувствительным к кроссинговеру. Принято считать, что применение кроссинговера носит деструктивный характер, если целевая функция ухудшается. Следовательно, для программы с относительно большим значением структурной сложности, но содержащей много интронов, опасность деструктивного воздействия кроссинговера заметно уменьшается. С учетом этого, а также принимая во внимание известную Schema-теорему Дж.Холланда, приведем следующую последовательность рассуждений.

Обозначим через Се(аi) эффективную сложность программы ai (i=1,2,…?), через Сa (ai) абсолютную сложность программы аi, через pc – вероятность применения кроссинговера, а через pd –вероятность того, что применение кроссинговера приведет к деструктивному эффекту, причем pd=0, если кроссинговер проводится с интроном. Пусть Ф(ai) – значение функции соответствия программы ai; ?(ai)- среднее значение функций соответствия всех программ в популяции P(t). Если применяется пропорциональная селекция, то нижняя оценка Ai(t+1) «доли» программы ai в популяции P(t+1) примерно равна

Ai(t+1) ? Ai(t)·?(ai)/[?(t)]·(1?pc·Се(аi)·pdi/ Сa (ai)) = = Ai(t)·? ?(ai)?pc·?(ai) Се(аi)·pdi/ Сa (ai) ?,

где выражение в скобках представляет собой функцию ?e(ai) эффективной сложности программы:

?e(ai) = ?(ai)?pc·?(ai) Се(аi)·pdi/ Сa (ai),

которая соответствует вкладу программы ai в следующую популяцию P(t+1). Отсюда следует, что репродуктивные шансы некоторой программы ai тем выше, чем меньше отношение между эффективной и абсолютной сложностью программы. Достигнуть этого можно двумя путями.

Первый заключается в увеличении абсолютной сложности путем добавления интронов, второй – в поиске простых решений. Эмпирические данные [1], подтверждают приведенные выше соображения:

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


Теоретически обоснованное и эмпирически наблюдаемое явление «компрессии» таит в себе опасность преждевременной сходимости ГП к субоптимальным решениям.

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

3. ЭВОЛЮЦИОННОЕ ПРОГРАММИРОВАНИЕ И ВЗАИМОДЕЙСТВИЕ АГЕНТОВ

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

3.1. Концепция и направления развития эволюционного программирования

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

Рассмотрим стандартную форму ЭП-алгоритма. Пусть стоит задача минимизации функции F(а1,…, аn), зависящей от n непрерывных переменных: F: Rn > R.

В ЭП отсутствуют ограничения на вид целевой функции и представление альтернативных решений, кроме тех, которые вытекают из постановки задачи. Вещественные переменные обычно представляются в виде вектора A=(а1,…, аn), который в ЭП соответствует отдельной особи. Тогда стандартная форма ЭП-алгоритма включает следующие этапы.

1) Инициализация. На этапе инициализации случайным образом генерируется популяция Р(0), состоящая из ? особей Ai (i=1,2,…, ?). Рекомендуемое значение размера популяции ??200. Значение элемента aj для каждой особи Ai устанавливается случайно с помощью равномерного распределения на интервале [lj , rj ] Є R, lj A??+i . При окончании этапа 3 размер популяции становится равным 2•?.

4) Случайная селекция. Селекция выполняется по соревновательному принципу, согласно которому каждый родитель или потомок попарно сравнивается с h противниками, причем hЄN (h?1) является параметром ЭП, устанавливается пользователем и обычно принимает значения от h=0.05? до h=0.1?. Противники выбираются случайно с помощью закона равномерного распределения. Победитель определяется путем попарного сравнения функций соответствия. Особь побеждает в соревновании, если ее функция соответствия по меньшей мере не хуже, чем у ее противника. Для представленной выше задачи минимизации число побед Wi i-ой особи (i=1,2,…2•?) определяется как Wi =?<1, если ?(Ai)? ?(Ad)>, причем суммирование ведется для d=1,2,…h и d?i является целочисленным значением равномерно распределенной в интервале [1, 2•?] случайной величины, которое для каждого d определяется заново. После этого все особи сортируются по убыванию числа побед (а не по значению функций соответствия). Лучшие особи образуют новую родительскую популяцию размером ?. При одинаковом числе побед преимущество получает особь с лучшим значением функции соответствия. Очевидно, что при таком механизме селекции «слабые» особи имеют некоторую отличную от нуля вероятность репродукции. С ростом значения параметра h селекция начинает принимать дискриминационный элитарный характер.

5) Критерий останова. В качестве критерия останова могут быть следующие заданные пользователем события:

a) достижение в ходе эволюции заданного числа поколений tmax ;

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

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

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

В отличие от генетических алгоритмов, ЭП является относительно малоисследованной парадигмой моделирования эволюции. Из теоретических результатов внимания заслуживает доказательство асимптотической сходимости рассмотренной выше стандартной формы ЭП [10], основанное на теории марковских цепей. Доказательство приводится для случая, когда параметры kj , zj принимают значение 1 и 0 соответственно, а также справедливо ?(Ai)=F(Ai)>0. Представляется, что математический аппарат марковских цепей как модель описания стохастических процессов вполне подходит в качестве одной из фундаментальных основ для формирования единой концепции эволюционных вычислений. С помощью марковских цепей можно обосновать эффективность эволюционного процесса.

Одним из перспективных направлений практического развития идей ЭП является преодоление следующих проблем:

(1) Если глобальный оптимум функции соответствия отличается от 0, то это негативно влияет на устойчивость ЭП;

(2) Если значения функции соответствия являются очень большими, то поиск становится квазислучайным;

(3) Если пользователь не обладает информацией о глобальном оптимуме, то согласование и подбор функции скаляризации ? становится затруднительным;

(4) Необходимость установки 2•n значений параметров эволюции kj и zj выдвигает перед пользователем дополнительные оптимизационные трудности, даже если он использует стандартную установку (kj =1, zj =0).

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

Пусть популяция составляется не из векторов Ai (i=1,2,…, ?), а из векторов Ei = (Ai , ui ), где ui – вектор среднеквадратичного отклонения, элементы которого uj Є R+ (j=1,2,…n). Тогда речь может идти о следующих отличиях модифицированной ЭП от рассмотренных ранее этапов стандартной формы ЭП.

На этапе инициализации для каждого вектора Ai дополнительно образуется вектор ui на основе равномерного распределения в интервале [0, ?], где ?>0 является параметром эволюции (рекомендуемое значение ?=25), который требует адаптации к каждому конкретному классу задач. На этапе генерации потомков отличие состоит в операторе мутации. В частности, потомок E’i = (A’i , u’i ), где u’j = uj + uj?Nj (0,1), a’j = aj + u’jNj (0,1). Отметим, что, если коэффициент ? выбрать слишком большим, то величина u’j может стать отрицательной и тогда она заменяется на некоторое малое ?>0, что несколько противоречит идее адаптации. Если ? выбрать слишком малым, то проявляется тенденция замедления эволюции. Рекомендуемое значение ?=1/6 [Fog92a]. Заслуживает внимания и другая идея. Речь идет о программируемой мутации путем с использованием ковариационной матрицы, составленной из коэффициентов корреляции и подробно рассмотренной в [11] применительно к другой парадигме моделирования эволюции – эволюционным стратегиям.

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

3.2. Прикладные аспекты эволюционного программирования

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

В частности, одним из наиболее объективных средств тестирования эволюционных алгоритмов для NP-полных комбинаторных проблем является задача о коммивояжере [7]. Приведем результаты тестирования ЭП для задачи о коммивояжере, предусматривающей обход 100 городов.

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

1 — (длина цикла особи/сумма длин циклов оцениваемой особи и контрагента).

Это означает, что у слабой особи имеется некоторый шанс победить в соревновании. Затем популяция из 100 особей сокращалась до 50 особей, имевших наибольшее число побед, после чего цикл эволюции повторялся вновь до останова. Сравнение полученных результатов с генетическим алгоритмом на основе PMX-операторов [10] о некотором преимуществе ЭП.

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

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

M Г
M (1,1) (5,0)
Г (0,5) (3,3)

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

Задачей ЭП является поиск такой игровой стратегии, которая позволит минимизировать средние потери при многократном повторении игровой ситуации. Следуя [Fog66], можно представить каждую совместную игровую стратегию одним из состояний конечного автомата. Множество возможных входных сигналов автомата при символьном представлении равно <(м/м), (м/г), (г/м), (г/г)>. Множеством выходов автомата являются символы <м, г>.

В ходе эксперимента размер исходной популяции ?=50, число ходов в игре — не менее 150, число состояний, переходы состояний, первый ход, а также выход автомата устанавливаются случайно. Каждый автомат копировался, над ним производилась мутация на базе равномерного распределения. В дальнейшем каждый автомат попарно сравнивался с 99 другими, причем в качестве функции соответствия выбирались ожидаемые средние потери. Хотя в игре возможна стохастическая селекция, предпочтительнее применять детерминированный отбор, согласно которому из 100 автоматов выбирались 50 лучших. Критерием останова в данной задаче являлось значение tmax =200. В табл. 2 в качестве иллюстрации приводится список возможных автоматных состояний и переходов между состояниями, полученный в ходе работы ЭП-алгоритма для задачи «дилемма узника».

Здесь S0 — это стартовое состояние, входом которого являлось решение узника говорить («г»), а, например, запись в столбце S4 (г,г/м, S2 ) означает, что узник на очередном ходе принял решение говорить, на предыдущем ходе использовалась стратегия г/м, автомат из состояния S4 переходит в состояние S2. Эксперименты с автоматами показали, что примерно в течение первых 20 ходов преобладает стратегия молчания, хотя уже после 5-10 ходов начинает встречаться стратегия кооперативного поведения, которая в дальнейшем однозначно становится доминирующей.

Эволюционные вычисления

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Создание исходной популяции
Размножение родителей и создание потомков (оператор скрещивания)
Сокращение расширенной популяции до исходного размера (оператор редукции)
Определение лучшей особи в конечной популяции
Да
Нет
Начало
Мутация потомков (оператор мутации)
Критерий остановки выполнен?
Конец

Рис. 40. Общая схема работы генетического алгоритма

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

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

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

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

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

| следующая лекция ==>
Задание на выполнение работы | Описание задачи и пример ее решения

Дата добавления: 2020-09-19 ; просмотров: 577 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Эволюционные вычисления

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

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

Биокомпьютинг — (или квазибиологическая парадигма[1]) (англ. Biocomputing) биологическое направление в искусственном интеллекте, сосредоточенное на разработке и использовании компьютеров, которые функционируют как живые организмы или содержат… … Википедия

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

Система поддержки принятия решений — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Система поддержки принятия решений (СППР) (англ. Decision Support System … Википедия

ИСППР — Система поддержки принятия решений (СППР) (англ. Decision Support System, DSS) компьютерная автоматизированная система, целью которой является помощь людям, принимающим решение в сложных условиях для полного и объективного анализа предметной… … Википедия

СППР — Система поддержки принятия решений (СППР) (англ. Decision Support System, DSS) компьютерная автоматизированная система, целью которой является помощь людям, принимающим решение в сложных условиях для полного и объективного анализа предметной… … Википедия

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

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

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

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

Эволюционные вычисления

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

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

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

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

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

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

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

История эволюционных вычислений началась с разработки ряда различных независимых моделей эволюционного процесса, среди которых можно выделить три основных направления исследований [20]:

  • • генетические алгоритмы;
  • • эволюционные стратегии;
  • • эволюционное программирование.

Парадигма генетических алгоритмов была предложена Джоном Холландом (J.H. Holland) в начале 1960-х гг. [21]. Основное отличие генетических алгоритмов заключается в представлении любого варианта решения в виде битовой строки фиксированной длины, манипуляции с которой производятся в отсутствие всякой связи с ее смысловой интерпретацией, т.е. в данном случае применяется единое универсальное представление любой задачи.

Эволюционные стратегии, напротив, оперируют объектами, тесно связанными с решаемой задачей. Каждая из альтернатив решения представляется единым массивом численных параметров, за каждым из которых скрывается, по сути, аргумент целевой функции. Воздействие на данные массивы осуществляется, в отличие от генетических алгоритмов, с учетом их смыслового содержания и направлено на улучшение значений входящих в них параметров. Парадигму эволюционных стратегий предложили Реченберг (I. Rechenberg) и Ше- фель (Н.-Р. Schwefel) соответственно в 1973 и 1977 гг.

Эволюционные вычисления

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

Содержание

Виды алгоритмов [ | ]

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

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

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

Отрасли использования [ | ]

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

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

ИИС 03 ЭВОЛЮЦИОННЫЕ ВЫЧИСЛЕНИЯ эволюционные

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

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

Основные направления эволюционных вычислений — эволюционное программирование; — эволюционные стратегии; — генетические алгоритмы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

№ строки Код Фенотип, x Значение целевой функции, f(x) = x 1 01011 11 11 2 10010 18 18 3 00010 2 2 4 01100 12 12 Среднее значение 10. 75

оператор отбора выбрал для производства потомков две пары строк (1, 2) и (2, 4). Работа оператора скрещивания При этом в каждой паре разбиение на подстроки происходит независимо и случайным образом.

№ строки Родители Потомки 1 0 | 1011 00010 2 1 | 0010 11011 3 100 | 10 10000 4 011 | 00 01110

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

№ строки Код Фенотип, x Значение целевой функции, f(x) = x Исходная популяция 1 01011 11 11 2 10010 18 18 3 00010 2 2 4 01100 12 12 Порожденные потомки 5 00010 2 2 6 11011 27 27 7 10001 17 17 8 01110 14 14

Оператор редукции далее сократит популяцию до исходного числа особей, исключив из нее те, значение целевой функции которых минимально. То есть будут исключены строки 1, 3, 4 и 5, и популяция первого поколения примет вид,

№ строки Код Фенотип, x Значение целевой функции, f(x) = x 1 10010 18 18 2 11011 27 27 3 10001 17 17 4 01110 14 14 Среднее значение 19

даже за одну итерацию качество популяции значительно возросло. Если в исходной популяции среднее значение целевой функции было 10. 75, а ее минимальное значение составляло 2, то в популяции первого поколения среднее значение возросло до 19, а минимальное значение составило 14. Лучшее же решение увеличилось с 18 до 27 при оптимальном решении 31.

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

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

Формализация задачи Ген – число, характеризующее номер посещаемого города. Хромосома – строка из чисел длиной N, характеризующая порядок посещения городов. Генотип состоит из одной хромосомы. Фенотип — порядок посещения городов (совпадает с генотипом). Особь – конкретная строка из чисел (допустимый вариант решения задачи). Предположим N = 9. Особи « 231586479» и « 147523869» — примеры допустимых вариантов решения задачи. Классическое скрещивание приведет к генерации недопустимых вариантов, например

Родители Потомки 23158 | 6479 23158 | 3869 14752 | 6479

потомках посещение некоторых городов будет дублироваться или проигнорировано. Рядом исследователей предложены различные варианты решения данной проблемы, в частности Л. Девис предлагает следующую модификацию оператора скрещивания. 1) Случайным образом выбираются два сечения генотипа Р 1 = 231 | 586 | 479 Р 2 = 147 | 523 | 869

2) Для потомков копируются участки кода, расположенные между сечениями П 1 = ххх | 586 | ххх П 2 = ххх | 523 | ххх 3) Из родителей генерируются вспомогательные строки, у которых участки кода циклически смещаются вправо. B 1 = 479 231 586 В 2 = 869 147 523

4) Свободные гены потомков последовательно заполняются генами из перекрестных вспомогательных строк с пропуском уже имеющихся в потомке генов П 1 = 914 | 586 | 723 П 2 = 479 | 523 | 186 Оператор мутации также может быть реализован различными способами, например: 1) перестановка пары, случайным образом выбранных генов местами: 479523186 → 473529186; 2) инверсия случайным образом выбранной последовательности генов: 479 | 523 | 186 → 479 | 325 | 186.

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

Содержание

  • Введение
  • 1. История появления эволюционных алгоритмов
  • 2. Эволюционные алгоритмы (методы)
  • 3. Генетические алгоритмы (ГА)
    • 3.1. Область применения.
    • 3.2. Решаемые задачи
    • 3.3. Классический ГА
    • 3.4. Стратегии поиска
    • 3.5. Отличия от классического поиска оптимума
    • 3.6. Терминология ГА
  • 4. Преимущества ГА
  • 5. Недостатки ГА
  • 6. Экспериментальная часть
    • 6.1. Поиск лучшей комбинации предикторов
      • с использованием tabuSearch
    • 6.2. Поиск лучших параметров ТС:
      • с использованием rgenoud (Genetic Optimization Using Derivatives)
      • с использованием SOMA ( Self-Organising Migrating Algorithm)
      • с использованием GenSA ( Generalized Simulated Annealing)
  • 7. Пути и методы улучшения качественных показателей
  • Заключение

Введение

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

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

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

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

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

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

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

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

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

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

    генетическое программирование — автоматическое создание или изменение программ с помощью генетических алгоритмов;

    эволюционное программирование — аналогично генетическому программированию, но структура программы постоянна, изменяются только числовые значения;

    эволюционные стратегии — похожи на генетические алгоритмы, но в следующее поколение передаются только положительные мутации;

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

    • Оптимизация функций
    • Оптимизация запросов в базах данных
    • Разнообразные задачи на графах (задача коммивояжёра, раскраска, нахождение паросочетаний)
    • Настройка и обучение искусственной нейронной сети
    • Задачи компоновки
    • Составление расписаний
    • Игровые стратегии
    • Теория приближений

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

    большое число свободных параметров, позволяющее эффективно встраивать эвристики;

    работает заведомо не хуже абсолютно случайного поиска;

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

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

    Большое количество свободных параметров, которое превращает «работу с ГА» в «игру с ГА»

    В простых целевых функциях (гладкие, один экстремум и т.п.) генетика всегда проигрывает по скорости простым алгоритмам поиска

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

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

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

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

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

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

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

    параметры, которые будут оптимизироваться;

    критерий оптимизации — скаляр, который нужно максимизировать/минимизировать. Критерий может быть не один;

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

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

    формирование исходного датафрейма;

    разделение его на train/test;

    вычисление критерия оптимизации.

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

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

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

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

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

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

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

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

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

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

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

    Напишем объективную функцию и приступим к экспериментам.

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

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

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

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

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

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

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

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

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

    Arguments

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

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

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

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

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

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

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

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

    p1 — расчетная цена (Close, Med, Typ, WClose)

    p2 — nFast ( 8 :21)

    p3 – nSlow( 13 :54)

    p5 — MAtypeMACD – тип МА для линии MACD

    p6 — MatypeSig – тип МА для линии Signal


    p 7 — percent (TRUE, FALSE)

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

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

    Buy = macd > signal

    Sell = macd = diff(macd) > 0

    Sell = diff(macd) 0 & macd > 0

    Sell = diff(macd) Это еще один параметр оптимизации sig nal (1:3) .

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

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

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

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

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

    • fn– объективная функция, которая минимизируется (или максимизируется, если max = TRUE) . Первым аргументом функции должен быть вектор с параметрами, с использованием которых и проводится минимизация. Функция должна возвращать скаляр (за исключением случая lexical = TRUE)
    • nvars– количество параметров, которые будут выбраны для минимизируемой функции
    • max = FALSE М аксимизировать( TRUE) или Минимизировать( FALSE) объективную функцию
    • pop.size = 1000 размер популяции. Это количество особей, которые будут использо в аны для решения оптимизационной проблемы. Есть несколько ограничений на то, каким может быть значение этого числа. Независимо от того, что численность популяции запрашивается у пользователя, число автоматически скорректируется, чтобы удовлетворить соответствующим ограничениям. Эти ограничения происходят от требований некоторых операторов ГА. В частности, оператор Р6 (простой кроссовер) и Р8 (эвристический кроссовер) требуют, чтобы количество особей было четным, т. е., они требуют двух родителей. Поэтому переменная pop.size должна быть четной. Если это не так, численность популяции увеличивается для удовлетворения этого ограничения.
    • max.generations = 100 — Максимум Поколений. Это максимальное количество поколений, которые genoud выполнит при попытке оптимизировать функцию. Это — мягкое ограничение. Максимальный предел поколений будет действовать для genoud, только если hard.generation.limit будет установлен в TRUE , иначе два мягких триггера контролируют, когда genoud должен остан овиться : wait.generations и gradient.check.

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

    • wait.generations = 10. Если не будет никакого улучшения целевой функции в этом количестве поколений, то genoud будет думать, что найден оптимум. Если триггер gradient.check был включен, genoud начнет считать wait.generations, только если градиенты будут в рамках solution.tolerance равны нулю. Другими переменными, управляющие завершением, являются max.generations и hard.generation.limit.
    • hard.generation.limit = TRUE. Эта логическая переменная определяет, является ли переменная max.generations обязательным ограничением для genoud. При hard.generation.limit, выставленном на FALSE, genoud может превысить количество max.generations, если в любо м из числе поколений (определенн ом в wait.generations) целевая функция улучшила сь или если градиент (определенный в gradient.check) не равен нулю .
    • starting.values = NULL — Вектор или матрица, содержащая значения параметров, которые genoud будет использовать при запуске. Используя эту опцию, пользователь может ввести одну или более особей в стартовую популяцию. Если предоставлена матрица , столбцы должны быть параметрами, а строки — особями. genoud в произвольном порядке создаст другие особи.
    • Domains = NULL . Это — nvars *2 матриц а . Для кажд о го параметра в первом столбце — нижняя граница, а во втором столбце — верхняя. Ни одн аособь из стартово й п опуляции genoud не будет сгенерирован а за пределами границ. Но некоторые операторы могут генерировать дочерние элементы, которые будут находиться за пределами границ, если флаг boundary.enforcement не будет включен.
    • Если пользователь не обеспечит значений для Доменов, то genoud установит домены по умолчанию, используя default.domains.
    • default.domains = 10. Если пользователь не хочет предоставлять матрицу Доменов, домены, тем не менее, могут быть установлены пользователем с этой простой в использовании скалярной опцией. Genoud создаст матрицу Доменов, устанавливая нижнюю границу для всех параметров, равн ую ( -1 ) * default.domains, и верхн юю границ у , равн ую default.domains.
    • solution.tolerance = 0.001. Это уровень допуска, используемый genoud. Числа с разницей solution.tolerance, как полагают, равны. Это особенно важно, когда дело доходит до оценки wait.generations и проведения gradient.check.
    • gr = NULL. Функция, предоставляющая градиент для оптимизатора BFGS. Если это NULL, то вместо этого будут использоваться числовые градиенты.
    • boundary.enforcement = 0. Эта переменная определяет уровень , до которого genoud подчиняется граничным ограничениям пространства поиска (ПП) . Несмотря на значение этой переменной, ни у одн ой особи из стартов ого поколения значени я параметров не будет за пределами границ ПП .

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

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

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

    2: н икако го н арушени я границы. З а предел ами ПП оценки никогда не будут требовать ся . В этом случае граничное ограничение также применено к алгоритму BFGS, котор ое препятствует тому, чтобы кандидаты отклон я лись вне границ, определенных Доменами. Обратите внимание на то, что это вызывает использование L-BFGS-B алгоритма для оптимизации . Этот алгоритм требует, чтобы все подходящие значения и градиенты были определены и конечны для всех функциональных оценок. Если это вызывает ошибку, предложено, чтобы использовался алгоритм BFGS и установк а boundary.enforcement=1.

    • lexical= FALSE. Эта опция включает лексическую оптимизацию. Это оптимизация по нескольким критериям, при этом они определяются последовательно, в порядке, выдаваемом фитнес-функцией. Фитнес- функция, используемая с этой опцией, должна возвратить числовой вектор значений фитнеса в лексическом порядке. Эта опция может иметь значения FALSE , TRUE или целого числа, равно го числу подходящих критериев, которые возвращены фитнес-функцией .
    • gradient.check = TRUE. Если эта переменная равна TRUE, то genoud не начнет считать wait.generations, пока каждый градиент не будет с solution.tolerance близок к нулю. Эта переменная не имеет никакого эффекта, если предел max.generations был превышен , и hard.generation.limit опция была установлена в TRUE. Если BFGSburnin 0, то это будет проигнорировано, если gradient.check = TRUE.
    • BFGS= TRUE. Эта переменная обозначает, применять или нет квазиньютоновский оптимизатор производной (BFGS) к лучшей особи в конце каждого поколения после начального. Установка в FALSE не означает, что BFGS не будет применяться. В частности, если Вы хотите чтобы BFGS никогда не применялся, оператор Р9 (Локально-минимальный кроссовер) должен быть обнулен.
    • data.type.int = FALSE. Эта опция устанавливает тип данных параметров функции, которая будет оптимизирована. Если переменная будет TRUE, то genoud будет искать решение среди целых чис ел , когда оптимизирует параметры.

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

    Н е т опции, позволяющей смешать целочисленные параметры и с плавающей точкой. Если вы хотите смешать эти два типа, можно указать целочисленный параметр, а в объективной функции преобразовать целочисленный диапазон в диапазон с плавающей точкой. Например, вам нужно получить поисковую сетку от 0.1 до 1.1. Вы указываете genoud искать от 10 до 110, а в фитнес-функции разделяете этот параметр на 100.

    • hessian = FALSE. Когда этот флаг установлен в TRUE, genoud возвратит матрицу гессиана в решении как часть его списка возврата. Пользователь может использовать эту матрицу, чтобы вычислить стандартные погрешности.
    • unif.seed= 812821. Эт им устанавливает ся seed для генератора псевдослучайного числа с плавающей точкой для использования genoud. Значение по умолчанию этого seed 81282. genoud использует свой собственный внутренний генератор псевдослучайн ых чис ел (Tausworthe-Lewis-Payne генератор), чтобы допускать рекурсивные и параллельные вызовы к genoud.
    • int.seed = 53058. Эт им устанавливает ся seed для целочисленного генератора, использ уемого genoud. Значение по умолчанию этого seed 53058 . genoud использует свой собственный внутренний генератор псевдослучайн ых чис ел (Tausworthe-Lewis-Payne генератор), чтобы допускать рекурсивные и параллельные вызовы к genoud.
    • print.level = 2. Эта переменная управляет уровнем печати того, что делает genoud. Есть 4 возможных уровня : 0 (минимальная печать), 1 ( нормальный), 2 (подробный) и 3 (отладка). Если будет выбран уровень 2, то genoud распечатает детали о популяции в каждом поколении.
    • share.type = 0. Если share.type равен 1, то genoud при запуске проверит, существует ли файл проекта (см. project.path). Если такой файл существует, он а инициализирует свою исходную популяцию, используя его. Эта опция может использоваться с lexical, но не с transform опцией.

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

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

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


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

    • P1 = 50 – Клонирование. Клонирующий оператор просто делает копии лучшего испытательного решения в текуще м поколении (независимый от этого оператора, rgenoud всегда сохраняет один экземпляр лучшего испытательного решения).

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

    • P2 = 50 – Универсальная мутация. Универсальная мутация изменяет один параметр в испытательном решении случайным значением, однородно распределенным на домене, определенном для параметра.
    • P3 = 50 – Граничная мутация. Граничная мутация заменяет один параметр одной из границ его домена.
    • P4 = 50 – Неоднородн ая мутация . Неоднородная мутация уменьшает один параметр к одной из границ с суммой уменьшения, уменьшающейся, когда количество поколений приближается к указанному максимальному числу поколений.
    • P5 = 50 – Многогранный кроссовер. Многогранныйкроссовер (вдохновленный симплексным поиском, Gill и др. 1981, p. 94–95), вычисляет испытательное решение, которое является выпуклой комбинацией стольких же испытательных решений, сколько есть параметр ов .
    • P6 = 50 – Простой кроссовер. Простой кроссовер вычисляет два испытательных решения из двух входных испытательных решений, обменивая значения параметров между решениями после разделения решений в произвольном порядке в выбранной точке. Этот оператор может быть особенно эффективным, если упорядочивание параметров в каждом испытательном решении последовательно е .
    • P7 = 50 – Целая неоднородная мутация. Целая неоднородная мутация делает неоднородную мутацию для всех параметров в испытательном решении.
    • P8 = 50 – Эвристический кроссовер. Эвристическийкроссовер использует два испытательных решения для производства нового решения, расположенного вдоль вектора, который начинаетс я в одном испытательном решении.
    • P9 = 0 — Локально-минимальный кроссовер: BFGS. Локально-минимальный кроссовер вычисляет решение для нового рассмотрения в дв а шага. Сначала BFGS выполняет предварительно установленное число итераций, запускающихся с входного решения ; после этого вычисляют выпуклую комбинацию входных решений, и BFGS выполняет итерации.

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

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

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

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

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

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

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

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

    • тип цены pr[ ,1]= Close
    • nFast = 1 4
    • nSlow = 2 6
    • nSig = 8
    • macdType = ZLEMA
    • sigType = SMA
    • percent = TRUE
    • signal = пересечение линий macd и signal
    • длина истории = 400 баров.

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

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

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

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

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

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

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

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

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

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

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

    Arguments

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

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

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

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

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

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

    • pathLength: Расстояние до лидер а , к которому могут мигрировать особи . Значение 1 соответствует позиции лидера, а значение больше единицы (рекомендуется) уч итывает некоторое перерегулирование. По умолчанию выставлено 3.
    • stepLength: Минимальный шаг, по котором у оцениваются возможные шаги. Рекомендуется, чтобы длина пути не была целым кратным этого значения. Значение по умолчанию составляет 0.11.
    • perturbationChance: Вероятность того, что отдельные параметры изменятся на любом данном этапе. Значение по умолчанию 0.1.


    • minAbsoluteSep: Наименьшая абсолютная разница между максимальным и минимальным значениями функции стоимости . Если разница падает ниже этого минимума, то алгоритм завершается. Значение по умолчанию равно 0. Это означает, что данный критерий прекращения никогда не будет удовлетворен.
    • MinRelativeSep: Наименьшая относительная разница между максимальным и минимальным значениями функции стоимости . Если разница падает ниже этого минимума, то алгоритм завершается. Значение по умолчанию составляет 0,001.
    • nMigrations: Максимальное количество миграций для завершения. Значение по умолчанию 20.
    • populationSize : Число особей в популяции. Рекомендуется, чтобы это значение было несколько больше, чем число оптимизируе мых параметров, и оно не должно быть меньше 2. Значение по умолчанию равно 10.

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

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

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

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

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

    • par — Начальные значения для компонентов, которые должны быть оптимизированы. По умолчанию NULL, в этом случае значения по умолчанию будут сгенерированы автоматически.
    • fn — функци я , которая будет минимизирована . Д ля минимизации функциии задается ряд параметров в виде вектора . Она должна возвращать скалярн ый результат.
    • lower – вектор длиной length(par). Нижняя граница компонентов.
    • upper — вектор длиной length(par). В ерхняя граница компонентов.
    • позволяет пользователю передать дополнительные аргументы функции fn.
    • control — аргумент управления. Это список, который может быть использован для управления поведением алгоритма.
    • maxit – Целое. Максимальное число итераций алгоритма.
    • threshold.stop — Числовой. Программа остановится при достижении ожидаемо го значени я целевой функции threshold.stop. Значение по умолчанию — NULL.
    • nb.stop.improvement — Целое. Программа будет остановлена, если нет каких-либо улучшений на протяжении nb.stop.improvement шагов.
    • smooth — логическая . TRUE, когда целевая функция является гладкой, или почти всюду дифференцируема в области пар аметров ; FALSE — в противном случае. Значение по умолчанию — TRUE
    • max.call — Целое. Максимальное количество вызова целевой функции. По умолчанию установлено значение 1 е 7.
    • max.time — Числовой. Максимальное время работы в секундах.
    • temperature — Числовой. Начальное значение температуры.
    • visiting.param — Числовой. Параметр для распределения посещения.
    • acceptance.param — Числовой. Параметр для распределения приема.
    • verbose — Логический. TRUE означает, что сообщения от алгоритма показ ываются . По умолчанию — FALSE

    • simple.function — Логический. TRUE означает, что целевая функция имеет лишь несколько локальных минимумов. По умолчанию установлено FALSE, что означает, что целевая функция осложнена многими локальными минимумами.
    • trace.mat — Логический. По умолчанию — TRUE. Это означает, что матрица трассировки будет доступна в возвращаемом значении GenSA вызова.

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

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

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

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

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

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

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

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

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

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

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

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

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

    Заключение

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

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

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

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

    Эволюционные вычисления

    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: x1 = 30.558, x2 = 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. Определение максимального и минимального значений целевой функции:

    — максимум: ymax = MAX(-14089, 25.5, -5675, 20218) = 20218 при x = 53;
    — минимум: ymin = 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. Случайным образом генерируются особи исходной популяции.

    Представление особи Фенотип,
    x
    Значение целевой функции,
    f(x) = a + bx + cx 2 + dx 3
    битовое десятичное
    1 011011 27 17 -8186
    2 100010 34 24 -12407
    3 000100 4 -6 -1355
    4 111001 57 47 2704

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

    № пары Родитель Потомок
    битовое
    представление
    битовое
    представление
    1 1 01 | 1011 5 010010
    2 10 | 0010 6 101011
    2 2 1000 | 10 7 100001
    4 1110 | 01 8 111010

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

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

    Представление особи Фенотип,
    x
    Значение целевой функции,
    f(x) = a + bx + cx 2 + dx 3
    битовое десятичное
    Родители
    1 011011 27 17 -8186
    2 100010 34 24 -12407
    3 000100 4 -6 -1355
    4 111001 57 47 2704
    Потомки
    5 010010 18 8 -2327
    6 101011 43 33 -13802
    7 101001 41 31 -14080
    8 111010 58 48 5113

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

    Представление особи Фенотип,
    x
    Значение целевой функции,
    f(x) = a + bx + cx 2 + dx 3
    битовое десятичное
    3 000100 4 -6 -1355
    4 111001 57 47 2704
    5 010010 18 8 -2327
    8 111010 58 48 5113

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

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

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

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

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

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

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

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

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

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

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

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

    Родители Потомки
    23158 | 6479 23158 | 3869
    14752 | 3869 14752 | 6479

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

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

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

    Р1 = 231 | 586 | 479
    Р2 = 147 | 523 | 869

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

    П1 = ххх | 586 | ххх
    П2 = ххх | 523 | ххх

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

    B1 = 479 231 586
    В2 = 869 147 523

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

    П1 = 914 | 586 | 723
    П2 = 479 | 523 | 186

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

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

    Эволюционные вычисления

      Римма Мордвинова 2 лет назад Просмотров:

    1 Лекции Заметки Практика Эволюционные вычисления Акира Имада Брестский государственный технический университет

    2 (Современные Интеллектуальные Информационные Методы) 2 I. All One Problem

    3 (Современные Интеллектуальные Информационные Методы) 3 Что такое «All one Problem»? Предположим, что «1» это хороший ген и «0» плохой ген. Затем попробуем создать популяцию случайных бинарных хромосом, с фитнесом где количество ген со значением «1» чем меньше, тем лучше. 1-ое поколение Промежуточное Финальное поколение

    5 (Современные Интеллектуальные Информационные Методы) 5 Задание 2 1. Попробуйте улучшить эффективность с помощью: (1) Изменив частоту мутации, скажем, 0.005, (2) Увеличив количество поколений, скажем, 200, 300. (3) Изменив начальное соотношение «1» и «0:», скажем, 600 vs 400, 700 vs Продемонстрировать все успешные результаты.

    6 (Современные Интеллектуальные Информационные Методы) 6 II.Счастливая собака (Lucky Dog)

    7 (Современные Интеллектуальные Информационные Методы) 7 Что такое Lucky Dog Проблема? Смоделировать одну собаку как хромосому с 1000 генов из 1, 2, 3 или 4. Из работы Дмитрия Веренича (2015)

    8 (Современные Интеллектуальные Информационные Методы) 8 Задание 3 1. Сымитировать 100 собак в сеточном мире (0,0) — (1000,1000) с сосиской в точке (800,800) где все собаки начинают с точки (500,500) искать сосиску по: (1) Предполагая, что все собаки имеют хромосому, каждая из 1000 генов (1, 2, 3 или 4) (2) Шаг за шагом двигаясь согласно его/её хромосоме, (3) с 1, 2, 3, 4 обозначают движение по сторонам вверх, вниз, вправо, влево, соответственно. 2. Предоставьте следующие результаты: (1) Лучший и средний Фитнес vs. Поколение для 5 лучших собак 1ого, промежуточного, и финального поколения. (2) Маршрут для 5 лучших собак в 1ом, промежуточном, и финальном поколении.

    9 (Современные Интеллектуальные Информационные Методы) 9 Задание 4 Посмотрите, что будет происходить, когда две сосиски в сеточном мире (0,0) — (1000,1000) в точке (200,800) и (800,800).

    10 (Современные Интеллектуальные Информационные Методы) 10 III. Минимизировать тестовые функции (Test Functions)

    11 (Современные Интеллектуальные Информационные Методы) 11 Многомерная тестовая функция Проблема заключается в минимизации или максимизации п-мерную функцию y = f (x1; x2; x3; ; xn) Мы можем использовать хромосомы с n генами реальных значений, таких как (0:32; 0:51; 0:48; ; 0:93) Например, минимизировать y = x x x x 2 20

    12 (Современные Интеллектуальные Информационные Методы) 12 Что же тогда насчет 2-D случаев? Например, y = x 2. Тогда, путь используется в 20-D (с реальными значениями 20 ген) не могут быть использованы, так как хромосома только с одним геном с реальным значением больше не имеет смысла. Итак, давайте представим каждый x с бинарной хромосомой, как представлено ниже!

    13 (Современные Интеллектуальные Информационные Методы) 13 (1) 20-Размерная функция Шефела Задание 5 1. Минимизировать y следующим образом! y = x1 sin( x1 ) + x2 sin( x2 ) + + x20 sin( x20 ) (1) Представьте каждый xi(i = 1; ; 20) как хромосому из 20 генов. (2) Создайте поколение из 20 хромосом, случайным образом, фитнесом будет y. (3) Развивать эту популяцию до тех пор, пока фитнес не перестанет меняться. 2. Продемонстрировать (1) График фитнес vs поколение. (2) Создать поколение из 20 случайных хромосом, где фитнес y. (3) Развивать эту популяцию до тех пор, пока фитнес не перестанет меняться.

    14 (Современные Интеллектуальные Информационные Методы) 14 Минимизировать У Советы Создайте популяцию из 20 случайных хромосом (чем меньше фитнес, тем лучше хромосома) Развивать поколение пока фитнес меняется

    15 (Современные Интеллектуальные Информационные Методы) 15 (2) 2-D версия функции Шефела Задание 6 1. Минимизировать Следующим способом! y = x sin( x ) (1) Представьте значение x с помощью 10-бит бинарных хромосом. (2) Создать популяцию из 20 случайных хромосом, где фитнес y. (3) Развивать популяцию пока фитнес меняется. 2. Продемонстрировать: (1) График Фитнес vs Поколение. (2) Все 20 точек (x; y) в 1ом, промежуточном, и финальном поколении.

    16 (Современные Интеллектуальные Информационные Методы) 16 Минимизировать У Совет Создать поколение из 20 случайных хромосом -> 20 точек (меньше фитнес, лучше хромосома) Развивать поколение пока фитнес изменяется График 20 точек (x,y) в первом, промежуточном и финальном поколении

    17 (Современные Интеллектуальные Информационные Методы) 17 (3) 3-D версия функции Шефела Задание 7 1. Минимизировать следующим способом! y = x1 sin( x1 ) + x2 sin( x2 ) (1) Представьте значения x из 10-бит бинарных хромосом. (2) Создать поколение из 20 случайных хромосом, фитнесом будет y. (3) Развивать потомство пока изменяется фитнес. 2. Продемонстрировать (1) График Фитнес vs Поколение. (2) Все 20 точек (x; y) в 1ом, промежуточном, и финальном поколении.

    18 (Современные Интеллектуальные Информационные Методы) 18 Минимизировать У Советы Создать поколение из 20 случайных хромосом (меньше фитнес, лучше хромосома) Развивать поколение пока изменяется фитнес.

    19 (Современные Интеллектуальные Информационные Методы) 19 3-D график функции Шефела, как подсказка

    20 (Современные Интеллектуальные Информационные Методы) 20 Тем не менее, другие функции тестирования

    21 (Современные Интеллектуальные Информационные Методы) 21 Функция Растригина Задание Минимизировать следующий y в (i) 20-D, (ii) 3-D и (iii) 2-D видах. 2. Показать следующие графики в каждом из 3 случаев (i), (ii) и (iii). (1) График Фитнесс vs Поколения. (2) Создать популяцию из 20 случайных хромосом, с фитнесом y.

    22 (Современные Интеллектуальные Информационные Методы) 22 3-D график функции Растригина, как подсказка

    23 (Современные Интеллектуальные Информационные Методы) 23 Функция Гриванка Задание 9 1. Минимизировать следующий y в (i) 20-D, (ii) 3-D and (iii) 2-D видах. 2. Продемонстрировать следующие графики в 3ех случаях (i), (ii) и (iii). (1) График Фитнес vs Поколение. (2) Создать популяцию из 20 случайных хромосом, с фитнесом y.

    24 (Современные Интеллектуальные Информационные Методы) 24 3-D график функции Гриванка, как подсказка

    25 (Современные Интеллектуальные Информационные Методы) 25 Функция Экли Задание Минимизировать следующий y в (i) 20-D, (ii) 3-D и (iii) 2-D видах. 2. Продемонстрировать следующие графики в 3ёх случаях (i), (ii) и (iii). (1) График Фитнес vs Поколение. (2) Создать популяцию из 20 случайных хромосом, с фитнесом y.

    26 (Современные Интеллектуальные Информационные Методы) 26 3-D график функции Экли, как подсказка

    27 (Современные Интеллектуальные Информационные Методы) 27 IV. Проблема путешествия менеджера по продажам (Traveling Salesperson Problem (TSP))

    28 (Современные Интеллектуальные Информационные Методы) 28 Что такое TSP? Предположим, что менеджер по продажам, начиная с его/её города, должен посетить N городов, каждый из них только один раз, и затем вернуться в город где он/она начал/начала. Проблема заключается в том, чтобы найти минимальную длину такого пути. Реальный пример городов представлен ниже.

    29 (Современные Интеллектуальные Информационные Методы) 29 Как закодировать хромосому, представляющую один тур?

    30 (Современные Интеллектуальные Информационные Методы) 30 (1) TSP с 5 случайно расположенными городами Задание Создать 5 городов Z, A, B, C, D случайным образом в x-y координатах от (0,0) до (10,10). Все A, B, C и D должны быть посещены единожды, начиная от Z и вернувшись в Z. 2. Рассчитать матрицу растояний (5 15). 3. Найти все возможные пути и рассчитать продолжительность каждого пути 4. Применим GA и будем развивать хромосомы, что бы путь был минимальной длинны. 5. Продемонстрировать (1) карту с 5 городами, (2) матрицу расстояний, (3) список всех путей с их длинами. (Смотри пример на следующей странице!) 6. Также показать (4) График Фитнес vs Поколение. (5) Минимальный путь в 1ом, в двух промежуточных, и финальном поколении.

    31 (Современные Интеллектуальные Информационные Методы) 31

    32 (Современные Интеллектуальные Информационные Методы) 32 (2) TSP с 25 городами фиксированного расположения Задание Пусть есть 15 городов, как показано на следующей странице (начиная с Z и возвращаясь в Z). 2. Вычислить матрицу расстояний (15 15). 3. Применим GA и будем развивать хромосомы, что бы путь был минимальной длинны. 4. Так же продемонстрируйте (5) График Фитнес vs Поколение. (6) Минимальный путь в 1ом, в двух промежуточных, и финальном поколении.

    33 (Современные Интеллектуальные Информационные Методы) 33

    34 (Современные Интеллектуальные Информационные Методы) 34 (3) TSP с 15 городами по кругу Задание Создать 25 городов случайным образом на круге (x 5) 2 + (y 5) 2 = 25. Смотри следующую страницу (начиная с Z в вернувшись в Z). 2. Вычислить матрицу расстояний (15 15). 3. Применим GA и будем развивать хромосомы, что бы путь был минимальной длинны. 4. Так же продемонстрируйте (5) График Фитнес vs Поколение. (6) Минимальный путь в 1ом, в двух промежуточных, и финальном поколении.

    35 (Современные Интеллектуальные Информационные Методы) 35

    36 (Современные Интеллектуальные Информационные Методы) 36 IV. Что делать, если несколько решений?

    37 (Современные Интеллектуальные Информационные Методы) 37 (1) Fitness Sharing Algorithm

    38 (Современные Интеллектуальные Информационные Методы) 38 Максимизация функции 2-D с 2-мя вершинами Задание Создайте популяцию из 20 бинарных хромосом с 10 генов, каждая из которых представляет собой значение x [0; 2] 2. Предполагая что фитнес y = 1 sin 2 (2 x), применим Fitnessg Sharing Algorithm с s(dij ) = 1 (dij /σ ) гдеσ= 0:06 3. Продемонстрировать (4) График Фитнес vs Поколение. (5) 20 точек (x; y) на графике в 1ом поколении, двух промежуточных поколениях, и финальном поколении. (6) Кроме того, таблицу оригинального фитнеса и shared фитнеса для 20 хромосом в вышеуказанных 5 поколениях (Смотри следующую страницу).

    39 (Современные Интеллектуальные Информационные Методы) 39

    40 (Современные Интеллектуальные Информационные Методы) 40 Советы

    41 (Современные Интеллектуальные Информационные Методы) 41 Советы

    42 (Современные Интеллектуальные Информационные Методы) 42 Проблема счастливой собаки с Fithess Sharing Algorithm Задание Создать популяцию из N хромосом с 1000 ген, каждая из которых имеет значение 1,2,3 или 4. Хромосома представляет 1000 шагов одной собаки. 2. Предполагая, что фитнес является <600 расстояние до ближайшей сосиски>, принять Fitnessg Sharing Algorithm с = 5 3. Продемонстрировать (4) График Фитнес vs Поколение 8ми, с высшим фитнесом, собак. (5) Маршруты, для 8, с высшим фитнесом, собак в 1ом поколении, два промежуточных поколения, и в финальном поколении. (6) Кроме того таблицу оригинального фитнеса и shared фитнес для N хромосом в вышеуказанных 5 поколений (Смотри следующую страницу).

    43 (Современные Интеллектуальные Информационные Методы) 43

    44 (Современные Интеллектуальные Информационные Методы) 44 Пример того, где эти собаки сейчас.

    45 (Современные Интеллектуальные Информационные Методы) 45 Те собаки, которых собака A должна share

    46 (Современные Интеллектуальные Информационные Методы) 46 Как собака B и D share фитнес?

    47 (Современные Интеллектуальные Информационные Методы) 47 Собака C действительно везучая, поскольку не нужно share

    48 (Современные Интеллектуальные Информационные Методы) 48 (2) Crowding Algorithm

    49 (Современные Интеллектуальные Информационные Методы) 49 Алгоритм 1 Crowding Algorithm 1. Выберите 2 родителя, p1 и p2, случайным образом. 2. Создайте двух детей, c 1 и c Замените родителя с ребенком следующим образом: — IF d(p1; c1) + d(p2; c2) > d(p1; c2) + d(p2; c1) IF f (c1) > f (p1) THEN поменять p1 с c1 IF f (c2) > f (p2) THEN поменять p2 с c2 — ELSE IF f (c2) > f (p1) THEN поменять p1 с c2 IF f (c1) > f (p2) THEN поменять p2 с c1 Смотри пример на следующей странице.

    50 (Современные Интеллектуальные Информационные Методы) 50

    51 (Современные Интеллектуальные Информационные Методы) 51 3D с 4-ёх пиковой-функцией

    52 (Современные Интеллектуальные Информационные Методы) 52 Максимизация функции 3D с Crowding Algorithm Задание Создать популяцию из 10 бинарных хромосом по 22 гены, каждая из которых представляет одну точку в x y плоскости 2 x; y Фитнес будет значение z, максимизировать z с помощью Crowding Algorithm. 3. Продемонстрировать (4) График Фитнес vs Поколение, повторять развитие пока фитнес не перестанет изменяться. (5) 3D график включает 10 точек на поверхности в 1ом поколении, два промежуточных поколения, и финальное поколение. (6) Так же таблица, как на следующей странице для вышеуказанных 5 поколений.

    53 (Современные Интеллектуальные Информационные Методы) 53

    54 (Современные Интеллектуальные Информационные Методы) 54 Совет

    55 (Современные Интеллектуальные Информационные Методы) 55 V. Что делать, если множественные фитнес функции?

    56 (Современные Интеллектуальные Информационные Методы) 56 Parate Optimum Solution- Dominate & Rank Мы сейчас стараемся развить популяцию хромосом, каждая из которых имеет несколько критериев (фитнес). Таким образом, мы не можем сортировать популяцию по фитнесу как раньше (потому что мы имеем несколько фитнесов). В этой ситуации, когда хромосома A лучше чем хромосома B по всем критериям (фитнесам) это называется A доминирует над B. Тогда как часто хромосома доминирует над другими в поколении называется ранг. Мы сортируем популяцию по рангу. Если хромосома не доминирует над другими в популяции, тогда эта хромосома называется недоминируемое решение or Parate Optimum Solution.

    57 (Современные Интеллектуальные Информационные Методы) 57 Например

    58 (Современные Интеллектуальные Информационные Методы) 58 Алгоритм 2 1. Инициализировать популяцию. Алгоритм 2. Выберете представителей равномерно из популяции. 3. Выполните скрещивание и мутацию, что бы создать ребенка. 4. Рассчитать ранг для нового ребенка. 5. Найдите представителя из всей популяции, который наиболее похож на ребенка. Замените эту особь новым ребенком, если ранг ребенка лучше, или ребенок доминирует над ним Обновите ранги популяции, если ребенок был добавлен. 7. Выполните шаги 2-6 в соответствии с размером популяции. 8. Если критерий остановки не выполняется переходите к шагу 2 и начинайте новое поколение. 1 Шаг 5 означает, что новый ребенок добавляется в популяцию, если он доминирует над наиболее похожим индивидуумом, или если он имеет более низкий рейтинг, то есть более низкую степень доминирования. Ограниченная стратегия замены также представляет собой крайнюю форму элитарности, как единственный способ замены

    59 (Современные Интеллектуальные Информационные Методы) 59 Например Задание 17 (Parate Optimal Solutions) Попробуйте алгоритм, описанный выше, с двумя целевыми функциями y1 = (x 2) 2 и y2 = (x 4) 2 следующим образом: 1. Создайте битных бинарных хромосом, предполагая, что каждая хромосома представляет x-координата колеблется от 0 до 6 с ( ) и ( ) будет соответствовать 0 и 6, соответственно. 2. Вычислить y 1 и y 2 для каждого из 20 x-ов представленных этими 20 хромосомами. 3. Создайте таблицу из 5 колонок: (i) хромосома, (ii) её x значение, (iii) её y1 значение, (iv) её y2 значение, (v) как часто они (y1, y2) доминируют над другими (ранг). 4. Изобразите эти 20 точек двумя кривыми (например, красным и синим цветом). 5. Создайте следующее поколение применив этот алгоритм для данных 20 хромосом. 6. Пока 20 точек отличаются от предыдущего поколения делайте пункты 2-4, иначе остановитесь. Предоставьте таблицу и график для первого поколения, двух промежуточных поколений и для финального поколения.

    60 (Современные Интеллектуальные Информационные Методы) 60 Vi. Iterated Prisonner’s Dillenmma

    61 (Современные Интеллектуальные Информационные Методы) 61 Два игрока играют в Камень Ножницы Бумага Награда когда каждый получит

    62 (Современные Интеллектуальные Информационные Методы) 62 Игра: Итерация игры Попробуйте: Случайный vs Случайный и Лучший vs Случайный, Всегда-1, Всегда-0, зуб за зуб

    63 (Современные Интеллектуальные Информационные Методы) 63 Хромосома Хромосома как стратегия игры

    64 (Современные Интеллектуальные Информационные Методы) 64 Дальнейшие действия зависят от хромосомы

    Илон Маск рекомендует:  Что такое код setclipboarddata
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL