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

1.

Генетические алгоритмы (ГА)
Основная идея
Терминология
Настройка шаблона
Пример

2.

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

3.

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

4.

Примеры кодирования
• Цикл Гамильтона
– Любая перестановка на множестве
вершин:
• 12345
• 32415
• 52431
• Цикл Эйлера:
– Не любая перестановка на
множестве ребер:
• abcdefghijk - допустимое решение
• bfhegcidjak – недопустимое решение
– Это плата за случайную генерацию

5.

Оценочная функция
• Мера «жизнеспособности» варианта
• Должна учитывать возможность оценки
нежизнеспособных вариантов:
– Базовая составляющая – «поощрение» за
жизнеспособность:
• Сумма весов ребер в цикле Гамильтона
– Штрафная составляющая – «наказание» за
нежизнеспособность:
• Разность длины максимального из найденных
фрагментов цикла Эйлера и количества ребер графа

6.

Генетические операторы
• Случайные процедуры эволюции хромосом
– Селекция
• Выбор пары особей из текущей популяции для
последующего скрещивания
– Скрещивание
• Комбинация генетического материала хромосомродителей в хромосоме-потомке
– Мутация
• Изменение хромосомы для увеличения
генетического разнообразия

7.

Оператор селекции
• Метод «рулетки»:
– упорядочить решения в популяции по возрастанию
значения оценочной функции;
– сопоставить каждому решению сумму оценочных
функций в упорядоченной популяции;
– вычислить сумму значений оценочных функций
всех решений в популяции;
– генерировать случайное число rand {0.. ΣОФ -1};
– найти первое решение j, для которого ΣОФi > rand.

8.

Оператор скрещивания
• Одноточечный кроссовер:
– Родители:
• adf|bce
• cea|bfd
– Потомки:
• adfbfd
• Ceabce
• Перестановка с участием генов двух родителей:
– Генерировать случайную двоичную маску, длина которой меньше длины
хромосомы.
– Поместить в дочернюю хромосому гены первого родителя,
соответствующие единичным битам маски.
– Составить список генов первого родителя, соответствующих нулевым
битам маски.
– Упорядочить список в соответствии с порядком этих генов у второго
родителя.
– Заполнить оставшиеся гены дочерней хромосомы элементами списка.

9.

Оператор мутации
• Перестановка генов хромосомы:
– Выделить участок, подверженный мутации
– Переставить гены на этом участке

10.

Псевдокод ГА
Инициализация популяции;
do
// цикл эволюции
{
Ранжировать популяцию по значению оценочной функции
do
//формирование новой популяции
{
Селекция;
Скрещивание;
Замена худших особей новыми;
}
while (выполнено нужное количество замен)
Мутация
}
while (выполнено условие сходимости)

11.

Параметры настройки ГА
• Способ кодирования варианта решения
• Размер популяции
• Оценочная функция
• Генетические операторы
– Скрещивания
– Мутации
• Параметры использования генетических
операторов
– Процент замещаемых особей в популяции
– Процент особей, подвергающихся мутации
• Критерий сходимости:
– Динамика изменения оценочной функции
– Количество поколений

12.

Пример применения ГА – задача
коммивояжера
• Размер популяции
– 20
• Максимальное
количество
поколений -30
• Матица графа:
0 10 25 40 26 12
10 0 20 30 28 18
25 20 0 15 19 22
40 30 15 0 8 21
26 28 19 8 0 16
12 18 22 21 16 0