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

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

2.

Методы глобальной
оптимизации

3.

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

4.

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

5.

Генетический алгоритм
Особь (индивидуум) – набор хромосом, содержащий генетический код
Используется явное разделение на пространство поиска (генотип) и пространство
решений (фенотип)
Каждое решение кодируется в виде бинарной хромосомы C длиной L(C),
состоящей из n числа генов g
Каждый ген есть двоичный код длиной L(g), соответствующий одной переменной
задачи оптимизации
- использование кода Грея
- символьное
- вещественных чисел
- определяется программистом

6.

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

7.

Генетический алгоритм.
Инициализация
Инициализация – создание начальной популяции (производится произвольно). Популяция
должна быть разнообразной. Допускается добавлять в популяцию «здоровые» хромосомы
Считают, что каждому параметру соответствует свой ген. Хромосома на рис. состоит из 4-х
10-разрядных генов. Несмотря на то, что каждый параметр закодирован в хромосоме целым
числом, ему могут быть поставлены в соответствие и вещественные числа. Если известен
диапазон [xmin ; xmax], в пределах которого лежит значение параметра и m – разрядность
гена, то этот диапазон разбивают на 2m равных отрезков, и каждому отрезку соответствует
определенное значение гена. При этом для перевода значений из закодированного
значения в дробные применяют следующие формулы:
где r – вещественное (декодированное) значение параметра, g – целочисленное
(закодированное) значение параметра.

8.

Генетический алгоритм.
Инициализация

9.

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

10.

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

11.

Генетический алгоритм.
Рекомбинирование

12.

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

13.

Генетический алгоритм.
Пример рекомбинирования
Вещественное кодирование. Для вещественного кодирования рассмотрим 2точечный, арифметический и BLX-α операторы кроссинговера. 2-точечный
кроссинговер для вещественного кодирования в целом аналогичен 2-точечному
кроссинговеру для целочисленного кодирования. Различие заключается в том, что
точка разрыва не может быть выбрана «внутри» гена, а должна попасть между
генами

14.

Генетический алгоритм.
Мутация
Оператор мутации используется для внесения случайных изменений в
хромосомы особей. Это позволяет «выбираться» из локальных экстремумов и
тем самым эффективнее исследовать пространство поиска. Аналогично
оператору кроссинговера, работа оператора мутации зависит от вероятности
применения мутации PM.
Целочисленное кодирование. Одним из основных операторов мутации для
целочисленного кодирования является битовая мутация. В случае
целочисленного кодирования мутация изменяет отдельные разряды в
хромосоме.
Вещественное кодирование. Оператор мутации для вещественного
кодирования изменяет содержимое каждого гена с вероятностью PM. При этом
величина изменения выбирается случайно в некотором диапазоне [– ξ; + ξ],
например, [−0,5; 0,5], и может иметь как равномерное, так и любое другое
распределение, к примеру нормальное с mx = 0, σx = 0,5.

15.

Генетический алгоритм.
Условия окончания работы ГА

16.

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

17.

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

18.

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