Слайд 2Для размышления
КМУ (выступление, публикация)
Конкурс портфолио (4,75 + наследство КМУ)
Экзамен
Перезачет?
Слайд 3эволюционные вычисления (ЭВ)
эволюционные алгоритмы (ЭА) [Beyer, Schwefel, Wegener,
2002]
- генетический алгоритм [Holland, 1975, Емельянов и др., 2003]
-
эволюционное программирование [Фогель и др., 1969]
- эволюционные стратегии [Rechenberg, 1973, Schwefel, 1977]
- генетическое программирование [Koza, 1992]
Слайд 4Задачи
- задачи численной оптимизации;
- задачи о кратчайшем пути;
- задачи компоновки;
- составление расписаний;
- аппроксимация функций;
-
отбор (фильтрация) данных;
- настройка и обучение искусственной нейронной сети;
- искусственная жизнь;
- биоинформатика;
- игровые стратегии;
- нелинейная фильтрация;
- развивающиеся агенты/машины
Слайд 5Общая схема генетического алгоритма
Слайд 6Факторы длительности эволюции
− нахождение решения в результате эволюционного поиска;
−
ограниченность количества поколений;
− ограниченность количества вычислений функции приспособленности (целевой
функции);
− вырождение популяции, когда степень разнородности хромосом в популяции становится меньше допустимого значения.
Слайд 8диапазон [xmin ; xmax]
m – разрядность гена
диапазон разбивают
на 2m равных отрезков, и каждому отрезку соответствует определенное значение
гена
r – вещественное (декодированное) значение параметра
g – целочисленное (закодированное) значение параметра
Слайд 9искомое значение параметра [1; 2]
каждый ген кодируется 16 разрядами
если содержимое гена равно ABCD16 = 4398110
r = 43981
* (2 – 1)/(216 – 1) + 1 = 0,6711 + 1 = 1,6711
если декодированное значение равно 1,3275
g = (1,3275 – 1)(216 – 1) / (2 – 1) = 0,3275 * 65535 = 21462,7125 ≈ 2146210 = 0101 0011 1101 01102.
Слайд 11Формирование начальной популяции
i = 0;
ПОКА (i
РАЗМЕР_ПОПУЛЯЦИИ) {
j = 0;
ПОКА (j < ЧИСЛО_ГЕНОВ) {
ОСОБЬ[i].ГЕН[j] = СЛУЧАЙНАЯ_ВЕЛИЧИНА;
j = j+1; }
i = i+1; }
Слайд 12Оценивание популяции
функция приспособленности (целевая функция)
Gi = { gik
: k = 1,2,...,N } – хромосома i-й особи
gik
– значение k-го ге- на i-й особи,
N – количество генов в хромосоме
если решается задача минимизации и f(Gi) < f(Gj)
если решается задача максимизации и f(Gi) > f(Gj)
Слайд 13Селекция
Рулеточная селекция
вероятность i-й особи принять участие в скрещивании
pi пропорциональна значению ее приспособленности fi и равна
Рулеточный круг
делится на сектора,
площадь i-го сектора пропорциональна значению pi.
n раз «вращается» рулетка, где n – размер популяции,
по сектору, на котором останавливается рулетка, определяется особь, выбранная для скрещивания
Слайд 14Селекция усечением
после вычисления значений приспособленности для скрещивания выбираются ln
лучших
l – «порог отсечения», 0 < l < 1
n
– размер популяции.
Чем меньше значение l, тем сильнее давление селекции, меньше шансы на выживание у плохо приспособленных особей
l в интервале от 0,3 до 0,7
Слайд 15Турнирный отбор
отбираются n особей.
из популяции случайно выбираются t
особей,
самая приспособленная из них допускается к скрещиванию.
Говорят, что формируется
турнир из t особей, t – размер турнира.
Эта операция повторяется n раз. Чем больше значение t, тем больше давление селекции.
Вариант турнирного отбора, когда t = 2, называют бинарным турниром.
Типичные значения размера турнира t = 2, 3, 4, 5.
Слайд 16Скрещивание и формирование нового поколения
Слайд 17Целочисленное кодирование
1-точечный кроссинговер работает аналогично операции перекреста для хромосом
при скрещивании биологических организмов.
выбирается произвольная точка разрыва и для
создания потомков производится обмен частями родительских хромосом.
Слайд 182-точечный кроссинговер
выбираются 2 случайные точки разрыва, после чего для
создания потомков родительские хромосомы обмениваются участками, лежащими между точками разрыва
Слайд 19При использовании однородного оператора кроссинговера разряды родительских хромосом наследуются независимо
друг от друга.
определяют вероятность p0, что i-й разряд хромосомы
1-го родителя попадет к первому потомку, а 2-го родителя – ко второму потомку.
Вероятность противоположного события равна (1 – p0). Каждый разряд родительских хромосом «разыгрывается» в соответствии со значением p0 между хромосомами потомков.
В большинстве случаев вероятность обоих событий одинакова, т.е. p0 = 0,5
Слайд 20Вещественное кодирование
2-точечный кроссинговер для вещественного кодирования аналогичен 2-точечному кроссинговеру
для целочисленного кодирования.
точка разрыва не может быть выбрана «внутри»
гена, а должна попасть между генами
– k-е гены родительских особей, 1 ≤ k ≤ N
N – количество генов в хромосоме
k-е гены по- томков
Слайд 21значение k-го гена по-
томка выбирается случайным образом (равномерное распределение)
из интервала [cmin – αΔk, cmax + αΔk], где α
– константа
Слайд 23Мутация
Целочисленное кодирование
Слайд 24Вещественное кодирование
Оператор мутации для вещественного кодирования изменяет содержимое каждого
гена с вероятностью PM.
величина изменения выбирается случайно в диапазоне
[– ξ; + ξ],
например, [−0,5; 0,5],
может иметь как равномерное, нормальное с mx = 0, σx = 0,5 распределения
Слайд 26Основными параметрами ГА являются
– длительность эволюции (количество поколений)
– размер
популяции
– интенсивность (давление) селекции
– тип оператора кроссинговера;
– вероятность кроссинговера
РС
– тип оператора мутации
– вероятность мутации РМ
– величина разрыва поколений Т
Слайд 27Влияние параметров ГА на характеристики эволюционного поиска
Слайд 28Канонический генетический алгоритм
Джон Холланд и описан в его книге
«Адаптация в естественных и искусственных системах», 1975 г.
− целочисленное
кодирование;
− все хромосомы в популяции имеют одинаковую длину;
− постоянный размер популяции;
− рулеточная селекция;
− одноточечный оператор кроссинговера;
− битовая мутация;
− новое поколение формируется только из особей-потомков (разрыв поколений Т = 1).
Слайд 29Пример работы и анализа генетического алгоритма
Определить количество и тип
оптимизируемых переменных задачи, которые необходимо закодировать в хромосоме.
Определить критерий
оценки особей, задав функцию приспособленности (целевую функцию).
Выбрать способ кодирования и его параметры.
Определить параметры ГА (размер популяции, тип селекции, генетические операторы и их вероятности, величина разрыва поколений).
Слайд 34n задает количество переменных функции z.
Необходимо найти такие значения
переменных xi ,
при которых функция z прини мает наименьшее
значение
Слайд 36Определение неизвестных переменных задачи
в хромосоме кодировать значения xi.
Таким
образом, каждый i-й ген хромосомы будет соответствовать i-й переменной функции
z
Задание функции приспособленности
Приспособленность i-й особи fi будем определять по следующей формуле:
fi =zi,
где zi – значение функции z в точке, соответствующей i-й особи.
Слайд 37Выбор способа кодирования
целочисленное кодирование с точностью кодирования параметров 0,01.
в имеющемся по условию задачи диапазоне изменения значений параметров
[–5,12; 5,11] можно закодировать (5,12 – (-5,11))/0,01 + 1 = 1024 различных значений переменной
достаточно использовать log21024 = 10 бит на каждую переменную
Слайд 38Определение параметров ГА
популяция из 20 особей.
При отборе особей
для скрещивания использовать турнирную селекцию с бинарным турниром.
В качестве генетических
операторов использовать 1-точечный кроссинговер и битовую мутацию.
Вероятности применения операторов скрещивания и мутации установить равными 0,7 и 0,05, соответственно.
Новое поколение будем формировать только из особей-потомков, т.е. величина разрыва поколений T равна 1.
Слайд 39Изменение zmin(t) и (t). Популяция из 20 особей, бинарный турнирный
отбор, одноточечный кроссинговер (РС = 0,7), битовая мутация (РМ =
0,05)
Слайд 40Изменение zmin(t) и (t). Популяция из 20 особей, бинарный турнирный
отбор, одноточечный кроссинговер (РС = 0,7), битовая мутация (РМ =
0,01)
Слайд 41Варианты реализации компонентов ГА
![эволюционные вычисления (ЭВ) эволюционные алгоритмы (ЭА) [Beyer, Schwefel, Wegener, 2002] - генетический алгоритм [Holland, 1975,](/img/thumbs/d0518170ce8e5607664a70511d2b5737-800x.jpg "ГА эволюционные вычисления (ЭВ) эволюционные алгоритмы (ЭА) [Beyer, Schwefel, Wegener, 2002]")
![диапазон [xmin ; xmax] m – разрядность гена диапазон разбивают на 2m равных отрезков, и каждому отрезку](/img/thumbs/bbc8aa7058b4aaa1539c3a6ec2332005-800x.jpg "ГА диапазон [xmin ; xmax] m – разрядность гена диапазон разбивают на")
![искомое значение параметра [1; 2] каждый ген кодируется 16 разрядами если содержимое гена равно ABCD16 = 4398110](/img/thumbs/de83307c7d4c87bf4877314a221898bc-800x.jpg "ГА искомое значение параметра [1; 2] каждый ген кодируется 16 разрядами если")
