Генетический алгоритм (презентация). Лекции Простой генетический алгоритм Холланда. Теория схем и гипотеза строительных блоков. Генетический алгоритм с самообучением
 Скачать 1.82 Mb.
|
|
Генетические алгоритмы План лекции 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. Задача поиска подмножества с требуемой суммой. Задача построения расписания Модель прикладной программы • Задается: 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 |