Файл: Лекции Простой генетический алгоритм Холланда. Теория схем и гипотеза строительных блоков. Генетический алгоритм с самообучением.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 10.01.2024
Просмотров: 49
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Генетические алгоритмы
План лекции
1. Простой генетический алгоритм Холланда.
2. Теория схем и гипотеза строительных блоков.
3. Генетический алгоритм с самообучением.
Charles Darwin. The Origin of Species. John Murray,
London, 1859.
Генетический алгоритм Холланда (SGA)
• Holland J.N. Adaptation in Natural and
Artificial Systems. Ann Arbor, Michigan:
Univ. of Michigan Press, 1975.
Применение ГА
• построение оптимальных игровых стратегий,
• машинное обучение (нейронные сети, классификаторы),
• задачи математического программирования,
• построение расписаний,
• задачи на графах (раскраска, задача коммивояжера, нахождение паросочетаний).
Генетический алгоритм Холланда (SGA)
• Основан на использовании механизмов естественной эволюции:
1. Изменчивость → операция мутации
2. Наследственность → операция скрещивания
3. Естесственный отбор → операция селекции
Основные понятия
• Популяция - это множество битовых строк.
• Каждая строка - одно из возможных решений задачи.
• По строке может быть вычислена функция
выживаемости, которая характеризует качество решения.
• Основные операции алгоритма: селекция,
скрещивание и мутация выполняются над элементами популяции.
Схема ГА
1.
Сгенерировать случайным образом популяцию размера P.
2. Вычислить функцию выживаемости для каждой строки популяции.
3. Выполнить операцию селекции.
4. Выполнить операцию скрещивания:
– 4.1. Выбрать пары для скрещивания.
– 4.2. Для каждой выбранной пары выполнить скрещивание, получить двух потомков и произвести в популяции замену родителей на их потомков.
5. Выполнить операцию мутации.
6. Если критерий останова не достигнут, перейти к п.2, иначе завершить работу.
Требования к кодированию решений
1. Однозначность: каждая закодированная строка должна соответствовать единственному решению исходной задачи.
2. Возможность кодирования любого допустимого решения.
3. Получение в результате генетических операций корректных вариантов решений.
4. Возможность перехода от любого корректного решения к любому другому корректному решению.
Требования к кодированию решений
•
Для задач непрерывного и целочисленного мат. программирования, оптимизируемые параметры задаются:
– двоичным кодом числа,
– кодами Грея – двоичный код, последовательные значения которого отличаются одним двоичным разрядом.
0 - 0000 1 - 0001 2 - 0011 3 - 0010 4 - 0110 5 - 0111
Создание начальной популяции
• Случайным образом генерируется начальная популяция в пределах допустимых значений (в области поиска):
Вычисление функции выживаемости
• Выбирается согласно задаче
• Оценивает качество решения
• Применяется ко всем элементам популяции:
Операция селекции
• Схема пропорциональной селекции:
• Схема рулетки:
…
Операция селекции
Операция скрещивания
Выбор пар для скрещивания
• Случайный выбор (
требует популяций большого размера
).
• Селективный выбор – участвуют строки значение функции выживаемости которых не меньше среднего значения:
– имбридиг – первая строка выбирается случайно, второй является максимально близкая к ней по расстоянию.
– аудбридинг – формируются пары из максимально далеких строк.
– комбинация этих подходов.
Операция мутации
Критерий останова
• Процесс продолжается итерационно
• Варианты критерия останова:
– Выполнение заданного числа итераций
– Выполнение заданного числа итераций без улучшения
– Достижение заданного значения функции выживаемости
1. Простой генетический алгоритм Холланда.
2. Теория схем и гипотеза строительных блоков.
3. Генетический алгоритм с самообучением.
4. Задача построения расписания.
5. Задача поиска подмножества с требуемой суммой.
Cхемы
Cхемы
примеры схем
Cхемы
• Порядок схемы (K)- количество фиксированных позиций в схеме
:
Cхемы
• Определяющая длина схемы (L)– расстояние между самыми дальними фиксированными позициями
:
Cхемы
Cхемы
• Для любой схемы, представляющей хорошее решение, нужно, чтобы количество ее примеров увеличивалось с увеличением количества итераций
• На преобразование схем влияют операции ГА: мутация, скрещивание и селекция
Теорема схем
Теорема схем
Теорема схем
Теорема схем
Теорема схем
• Схема всегда будет разрушена операцией одноточечного скречивания
• Двухточечное скрещивание решает проблему
1 * * * * * * * * * * * * * * * * 0 1 * * * * * * * * * * * * * * * * 0 1 * * * * * * * * * * * * * * * * 0 1 * * * * * * * * * * * * * * * * 0
Теорема схем
• Проблема выбора параметров ГА является для многих приложений сложной задачей
• Теоретические результаты для решения данной проблемы на данный момент отсутствуют
• На практике данная проблема решается экспериментальным путем
Гипотеза строительных блоков
• Строительные блоки - схемы с низким порядком, малыми определяющими длинами и большими значениями средних целевых функций
• Гипотеза строительных блоков: комбинирование хороших строительных блоков дает хорошую строку.
Применение марковских цепей для
моделирования поведения ГА
• Марковская цепь – вероятность того, что процесс в момент времени t будет в состоянии j, зависит только от состояния i в момент (t-1).
• Состояние ГА – текущая популяция.
• Множество всех состояний – множество всевозможных популяций.
• Построить модель – определить вероятность перехода между популяциями (построить матрицу переходов).
При n=8 и N=8 матрица переходов имеет более
10 ^29 элементов.
1. Простой генетический алгоритм Холланда.
2. Теория схем и гипотеза строительных блоков.
3. Генетический алгоритм с самообучением.
4. Задача построения расписания.
5. Задача поиска подмножества с требуемой суммой.
ГА с самообучением
• Идея:
– ввести индивидуальные параметры вероятности операций мутации и скрещивания для каждого элемента строки-решения
– корректировать эти параметры на каждой итерации алгоритма в зависимости от того, насколько удачным или неудачным оказалось применение конкретной операции к элементу решения
ГА с самообучением
• Костенко В. А., Фролов А. В. Генетический алгоритм с самообучением // Известия РАН.
Теория и системы управления, 2015, № 4, С. 24-38.
DOI: 10.7868/S0002338815040101.
• V.A. Kostenko, A.V. Frolov. Self-Learning Genetic
Algorithm // Journal of Computer and Systems
Sciences International, 2015, Vol. 54, No. 4, pp.
525–539. DOI: 10.1134/S1064230715040103
Матрицы вероятности
Схема ГА c самообучением
Операция скрещивания
Операция мутации
Способы коррекции элементов МП
Способы коррекции элементов МП
Способы коррекции элементов МП
1. Простой генетический алгоритм Холланда.
2. Теория схем и гипотеза строительных блоков.
3. Генетический алгоритм с самообучением.
4. Задача построения расписания.
5. Задача поиска подмножества с требуемой суммой.
Задача построения расписания
Модель прикладной программы
• Ацикличный ориентированный граф
•
- дуги
K
k
i
k
i
ik
p
p
1
,
,
Модель прикладной программы
• Задается:
1.
Множеством процессов:
2.
Отношением
:
3.
Вычислительными сложностями процессов:
K
k
i
k
i
ik
p
p
1
,
,
Модель расписания
•
c
M
i
i
HP
1
Математическая постановка
Кодирование решений
- привязка
- приоритеты
Матрицы вероятности
Функция выживаемости
• Ограничена сверху:
Операции генетического алгоритма
• Cелекция: смешанная стратегия
• Скрещивание: одноточечное
• Мутация: стандартная
Критерий останова
o Ограничение на число итераций алгоритма, т.е. алгоритм прекращает свою работу, если не смог за
I
0
шагов улучшить значение функции выживаемости в популяции.
1. Простой генетический алгоритм Холланда.
2. Теория схем и гипотеза строительных блоков.
3. Генетический алгоритм с самообучением.
4. Задача построения расписания.
5. Задача поиска подмножества с требуемой суммой.
Задача поиска подмножества с
требуемой суммой
Кодирование решений
Матрицы вероятности
Функция выживаемости
Операции генетического алгоритма
• Cелекция: смешанная стратегия
• Скрещивание: равномерное с замещением
• Мутация: стандартная
Критерий останова
• Итерационный процесс до достижения критерия останова
• Совокупность условий
:
– Выполнение заданного числа итераций без улучшения (без уменьшения наименьшего значения функции выживаемости)
– Достижение функцией выживаемости значения 0