Презентация на тему Эволюционные вычисления

функции (оптимального решения) за определенное время. Основное их преимущество

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

поиск скрытых правил и закономерностей в компьютерных базах данных

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

эволюционных вычислений 

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

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

Эволюционное программирование

формулируются системой в виде программ на некотором внутреннем языке

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

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

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

эволюционные стратегия

в виде кодовой (как правило, битовой) строки фиксированной длины,

манипуляции с которой производятся в отсутствие всякой связи с ее смысловой интерпретацией

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

битом, числом или неким другим объектом.
Аппель – значение конкретного гена.
Локус –

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

Определения

виде битовой строки.
Тогда ген – это бит;
генотип

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

точек поиска решения одновременно.
Совокупность этих точек является набором

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

путем создания новых особей и уничтожения ненужных.
Чтобы отличать

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

помощью оператора скрещивания.
порождающие особи называются родителями,
порожденные - потомками.
Выбор родителей

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

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

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

которых зависят значения аргументов целевой функции и, соответственно, значение

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

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

на эволюцию;
- популяция достигла заданного качества (значение критерия одной

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

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

31 и функция, определенная на этом наборе чисел, f(х)

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

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

функции.
Таким образом, ген - это отдельный бит строки,

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

строк (1, 2) и (2, 4). Работа оператора скрещивания
При

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

в строке 3 и данный код изменился с 10000 на

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

особей, исключив из нее те, значение целевой функции которых

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

Если в исходной популяции среднее значение целевой функции было

10.75, а ее минимальное значение составляло 2, то в популяции первого поколения среднее значение возросло до 19, а минимальное значение составило 14. Лучшее же решение увеличилось с 18 до 27 при оптимальном решении 31.

коммивояжера

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

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

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

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

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

Формализация задачи

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

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

сечениями
П1 = ххх | 586 | ххх
П2 = ххх | 523

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