Эволюционные методы и алгоритмы оптимизации. Лекция 1

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

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

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

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

Классы генетических алгоритмов
Генетические алгоритмы
Гаплоидные
Размерность хромосомного набора
Диплоидные
Полиплоидные
Область допустимых значений переменных
Непрерывные (вещественные)
Дискретные
Бинарные (двоичные)
Многозначные
Состав генетических операторов
Состав эволюционных стратегий
Организация эволюционной программы

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

Кодирование переменных
Переход к двоичной форме (пример)
R = (x – 7)2

Сравнение генотипов
Расстояние Хэмминга – количество различающихся битов данных
Сравнение фенотипов
По значению функции приспособленности

Кодирование переменных
Код Грея
Правило 1 (из двоичного в код Грея). Для представления двоичного кода в форме кода Грея требуется приписать к двоичной форме слева ноль. Тогда соответствующей формой кода Грея будет последовательность значений функции «Исключающее ИЛИ» для пар: нуля и первого гена исходной двоичной формы, первого и второго генов, второго и третьего и т. д. То есть, например, для случая преобразования двоичной последовательности (a1, b1, c1) в последовательность в форме кода Грея (a2, b2, c2) получим: a2 = XOR(0, a1); b2 = XOR(a1, b1); c2 = XOR(b1, c1).

Кодирование переменных
Код Грея
Правило 2 (из кода Грея в двоичный). Для преобразования из кода Грея в двоичную форму к исходному коду слева приписывается ноль. Тогда результирующей двоичной формой будет последовательность значений функции «Исключающее ИЛИ» для первых двух знаков расширенной последовательности, первых трёх, четырёх и т. д. Например, для преобразования кода Грея (a1, b1, c1) в двоичную последовательность (a2, b2, c2) получим: a2 = XOR(0, a1); b2 = XOR(0, a1, b1); c2 = XOR(0, a1, b1, c1).