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

Сентябрь 3, 2022

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

Содержание

2. эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации
3. Оптимизация функций Оптимизация запросов в базах данных Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний)
4. Схема работы
5. Задача формализуется таким образом, чтобы её решение могло быть закодировано в виде вектора («генотипа») генов. Где
6. Из полученного множества решений («поколения») с учётом значения «приспособленности» выбираются решения (обычно лучшие особи имеют большую
7. Бинарное кодирование не лишено недостатков. Основной недостаток заключается в том, что соседние числа отличаются в значениях
8. 0 - 0000 1 - 0001 2 - 0011 3 - 0010 4 - 0110 5
9. Самый простой способ – использовать битовое представление. Хотя такой вариант имеет те же недостатки, что и
10. Допустим, что значения признака лежат в интервале [0,1]. При кодировании использовалось разбиение участка на 256 интервалов.
11. для того, чтобы определить фенотип объекта (то есть значения признаков, описывающих объект) нам необходимо только знать
12. 1. Задать целевую функцию (приспособленности) для особей популяции 2. Создать начальную популяцию 3. (Начало цикла) A.
13. Перед первым шагом нужно случайным образом создать начальную популяцию; даже если она окажется совершенно неконкурентоспособной, генетический
14. Размножение в генетических алгоритмах обычно половое — чтобы произвести потомка, нужны несколько родителей, обычно два. Размножение
15. 1.из популяции выбираются две особи, которые будут родителями; 2.определяется (обычно случайным образом) точка разрыва; 3.потомок определяется
16. Хромосома_1: 0000000000 Хромосома_2: 1111111111 Допустим разрыв происходит после 3-го бита хромосомы, тогда Хромосома_1: 0000000000 >> 000
17. К мутациям относится все то же самое, что и к размножению: есть некоторая доля мутантов m,
18. При использовании данного оператора каждый бит в хромосоме с определенной вероятностью инвертируется. Кроме того, используется еще
19. На этапе отбора нужно из всей популяции выбрать определенную ее долю, которая останется «в живых» на
20. кроссовер может быть не одноточечный (как было описано выше), а многоточечный, когда формируется несколько точек разрыва
21. Инициировать начальный момент времени t=0. Случайным образом сформировать начальную популяцию, состоящую из k особей. B0 =
22. Наиболее часто используется метод отбора, называемый рулеткой. При использовании такого метода вероятность выбора хромосомы определяется ее
23. Обычно в качестве них применяются или ограничение на максимальное число эпох функционирования алгоритма, или определение его
24. # include # include # include int main() { using namespace std; srand((unsigned)time(NULL)); const int N
25. Непрерывные генетические алгоритмы
26. двоичное представление хромосом влечет за собой определенные трудности при поиске в непрерывных пространствах большой размерности, и
27. хромосома есть вектор вещественных чисел Длина хромосомы будет совпадать с длиной вектора-решения оптимизационной задачи, иначе говоря,
28. Использование непрерывных генов делает возможным поиск в больших пространствах (даже в неизвестных), что трудно делать в
29. В качестве операторов отбора особей в родительскую пару здесь подходят любые известные из BGA: рулетка, турнирный,
30. Большинство real-coded алгоритмов генерируют новые векторы в окрестности родительских пар. Пусть C1=(c11,c21,…,cn1) и C2=(c12,c22,…,cn2) – две
31. Плоский кроссовер (flat crossover): создается потомок H=(h1,…,hk,…,hn), hk, k=1,…, n – случайное число из интервала [ck1,ck2].
32. Арифметический кроссовер (arithmetical crossover): создаются два потомка H1=(h11,…,hn1), H2=(h12,…,hn2), где hk1=w*ck1+(1-w)*ck2, hk2=w*ck2+(1-w)*ck1, k=1,…,n, w либо константа
33. Смешанный кроссовер (blend, BLX-alpha crossover): генерируется один потомок H=(h1,…,hk,…,hn), где hk – случайное число из интервала
34. Дискретный кроссовер (discrete crossover): каждый ген hk выбирается случайно по равномерному закону из конечного множества {ck1,ck2}.
35. Нечеткий кроссовер (fuzzy recombination, FR-d crossover): создаются два потомка H1=(h11,…,hn1), H2=(h11,…,hn2). Вероятность того, что в i-том
36. Параметр d определяет степень перекрытия треугольных функций принадлежности, по умолчанию d=0.5 BLX-кроссовер с параметром alpha=0.5 –
37. наибольшее распространение получили: случайная и неравномерная мутация (random and non-uniform mutation). При случайной мутации ген, подлежащий
38. SBX (англ.: Simulated Binary Crossover) – кроссовер, имитирующий двоичный. Был разработан в 1995 году исследовательской группой
40. Скачать презентацию

Слайд 2

эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём

случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию.
Является разновидностью эволюционных вычислений.
Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

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

Слайд 3

Оптимизация функций
Оптимизация запросов в базах данных
Разнообразные задачи на графах (задача коммивояжера,

раскраска, нахождение паросочетаний)
Настройка и обучение искусственной нейронной сети
Задачи компоновки
Составление расписаний
Игровые стратегии
Теория приближений
Искусственная жизнь
Биоинформатика (фолдинг белков)

Применение

Слайд 4

Схема работы

Слайд 5

Задача формализуется таким образом, чтобы её решение могло быть закодировано в

виде вектора («генотипа») генов. Где каждый ген может быть битом, числом или неким другим объектом.
Некоторым, обычно случайным, образом создаётся множество генотипов начальной популяции. Они оцениваются с использованием «функции приспособленности», в результате чего с каждым генотипом ассоциируется определённое значение («приспособленность»), которое определяет насколько хорошо фенотип им описываемый решает поставленную задачу.

Слайд 6

Из полученного множества решений («поколения») с учётом значения «приспособленности» выбираются решения

(обычно лучшие особи имеют большую вероятность быть выбранными), к которым применяются «генетические операторы» (в большинстве случаев «скрещивание» — crossover и «мутация» — mutation), результатом чего является получение новых решений. Для них также вычисляется значение приспособленности, и затем производится отбор («селекция») лучших решений в следующее поколение.
Этот набор действий повторяется итеративно, так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть:
нахождение глобального, либо субоптимального решения;
исчерпание числа поколений, отпущенных на эволюцию;
исчерпание времени, отпущенного на эволюцию.

Слайд 7

Бинарное кодирование не лишено недостатков. Основной недостаток заключается в том, что

соседние числа отличаются в значениях нескольких битов, так например числа 7 и 8 в битовом представлении различаются в 4-х позициях, что затрудняет функционирование генетического алгоритма и увеличивает время, необходимое для его сходимости. Для того, чтобы избежать эту проблему лучше использовать кодирование, при котором соседние числа отличаются меньшим количеством позиций, в идеале значением одного бита. Таким кодом является код Грея

Кодирование признаков, представленных целыми числами

Слайд 8

0 - 0000
1 - 0001
2 - 0011
3 - 0010
4 - 0110
5

- 0111
6 - 0101
7 - 0100
8 - 1100
9 - 1101
10 - 1111
11 - 1110
12 - 1010
13 - 1011
14 - 1001
15 - 1000

Код Грея

Слайд 9

Самый простой способ – использовать битовое представление. Хотя такой вариант имеет

те же недостатки, что и для целых чисел. Поэтому на практике обычно применяют следующую последовательность действий:
1.Разбивают весь интервал допустимых значений признака на участки с требуемой точностью.
2.Принимают значение гена как целочисленное число, определяющее номер интервала (используя код Грея).
3.В качестве значения параметра принимают число, являющиеся серединой этого интервала.

Кодирование признаков

Слайд 10

Допустим, что значения признака лежат в интервале [0,1]. При кодировании использовалось

разбиение участка на 256 интервалов. Для кодирования их номера нам потребуется таким образом 8 бит. Допустим значение гена: 00100101bG (заглавная буква G показывает, что используется кодирование по коду Грея).
Для начала, используя код Грея, найдем соответствующий ему номер интервала: 25hG->36h->54d.
Теперь посмотрим, какой интервал ему соответствует… После несложных подсчетов получаем интервал [0,20703125, 0,2109375].
Значит значение нашего параметра будет (0,20703125+0,2109375)/2=0,208984375.

Пример

Слайд 11

для того, чтобы определить фенотип объекта (то есть значения признаков, описывающих

объект) нам необходимо только знать значения генов, соответствующим этим признакам, то есть генотип объекта. При этом совокупность генов, описывающих генотип объекта, представляет собой хромосому. В некоторых реализациях ее также называют особью. Таким образом, в реализации генетического алгоритма хромосома представляет собой битовую строку фиксированной длины. При этом каждому участку строки соответствует ген. Длина генов внутри хромосомы может быть одинаковой или различной. Чаще всего применяют гены одинаковой длины.

Определение фенотипа

Слайд 12

1. Задать целевую функцию (приспособленности) для особей популяции
2. Создать начальную популяцию
3.

(Начало цикла)
A. Размножение (скрещивание)
B. Мутирование
C. Вычислить значение целевой функции для всех особей
D. Формирование нового поколения (селекция)
E. Если выполняются условия останова, то (конец цикла), иначе на шаг 3.

Обобщенный алгоритм

Слайд 13

Перед первым шагом нужно случайным образом создать начальную популяцию; даже если

она окажется совершенно неконкурентоспособной, генетический алгоритм все равно достаточно быстро переведет ее в жизнеспособную популяцию. Таким образом, на первом шаге можно особенно не стараться сделать слишком уж приспособленных особей, достаточно, чтобы они соответствовали формату особей популяции, и на них можно было подсчитать функцию приспособленности (Fitness). Итогом первого шага является популяция H, состоящая из N особей.

Создание начальной популяции

Слайд 14

Размножение в генетических алгоритмах обычно половое — чтобы произвести потомка, нужны

несколько родителей, обычно два.
Размножение в разных алгоритмах определяется по-разному — оно, конечно, зависит от представления данных. Главное требование к размножению — чтобы потомок или потомки имели возможность унаследовать черты обоих родителей, «смешав» их каким-либо способом.
Почему особи для размножения обычно выбираются из всей популяции H, а не из выживших на первом шаге элементов H0 (хотя последний вариант тоже имеет право на существование)? Дело в том, что главный бич многих генетических алгоритмов — недостаток разнообразия (diversity) в особях. Достаточно быстро выделяется один-единственный генотип, который представляет собой локальный максимум, а затем все элементы популяции проигрывают ему отбор, и вся популяция «забивается» копиями этой особи. Есть разные способы борьбы с таким нежелательным эффектом; один из них — выбор для размножения не самых приспособленных, но вообще всех особей.

Размножение (скрещивание)

Слайд 15

1.из популяции выбираются две особи, которые будут родителями;
2.определяется (обычно случайным

образом) точка разрыва;
3.потомок определяется как конкатенация части первого и второго родителя.

Классический оператор скрещивания

Слайд 16

Хромосома_1: 0000000000
Хромосома_2: 1111111111
Допустим разрыв происходит после 3-го бита хромосомы, тогда
Хромосома_1:

0000000000 >> 000 1111111 Результирующая_хромосома_1
Хромосома_2: 1111111111 >> 111 0000000 Результирующая_хромосома_2
Затем с вероятностью 0,5 определяется одна из результирующих хромосом в качестве потомка.

Пример

Слайд 17

К мутациям относится все то же самое, что и к размножению:

есть некоторая доля мутантов m, являющаяся параметром генетического алгоритма, и на шаге мутаций нужно выбрать mN особей, а затем изменить их в соответствии с заранее определенными операциями мутации.

Мутации

Слайд 18

При использовании данного оператора каждый бит в хромосоме с определенной вероятностью

инвертируется.
Кроме того, используется еще и так называемый оператор инверсии, который заключается в том, что хромосома делится на две части, и затем они меняются местами.

Слайд 19

На этапе отбора нужно из всей популяции выбрать определенную ее долю,

которая останется «в живых» на этом этапе эволюции. Есть разные способы проводить отбор. Вероятность выживания особи h должна зависеть от значения функции приспособленности Fitness(h). Сама доля выживших s обычно является параметром генетического алгоритма, и ее просто задают заранее. По итогам отбора из N особей популяции H должны остаться sN особей, которые войдут в итоговую популяцию H'. Остальные особи погибают.

Отбор

Слайд 20

кроссовер может быть не одноточечный (как было описано выше), а многоточечный,

когда формируется несколько точек разрыва (чаще всего две). Кроме того, в некоторых реализациях алгоритма оператор мутации представляет собой инверсию только одного случайно выбранного бита хромосомы.

Вариации операторов

Слайд 21

Инициировать начальный момент времени t=0. Случайным образом сформировать начальную популяцию, состоящую

из k особей. B0 = {A1,A2,…,Ak)
Вычислить приспособленность каждой особи FAi = fit(Ai) , i=1…k и популяции в целом Ft = fit(Bt) (также иногда называемую термином фиттнес). Значение этой функции определяет насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи.
Выбрать особь Ac из популяции. Ac = Get(Bt)
С определенной вероятностью (вероятностью кроссовера Pc) выбрать вторую особь из популяции Аc1 = Get(Bt) и произвести оператор кроссовера Ac = Crossing(Ac,Ac1).
С определенной вероятностью (вероятностью мутации Pm) выполнить оператор мутации. Ac = mutation(Ac).
С определенной вероятностью (вероятностью инверсии Pi) выполнить оператор инверсии Ac = inversion(Ac).
Поместить полученную хромосому в новую популяцию insert(Bt+1,Ac).
Выполнить операции, начиная с пункта 3, k раз.
Увеличить номер текущей эпохи t=t+1.
Если выполнилось условие останова, то завершить работу, иначе переход на шаг 2.

Алгоритм

Слайд 22

Наиболее часто используется метод отбора, называемый рулеткой. При использовании такого метода

вероятность выбора хромосомы определяется ее приспособленностью, то есть PGet(Ai)~Fit(Ai)/Fit(Bt). Использование этого метода приводит к тому, что вероятность передачи признаков более приспособленными особями потомкам возрастает.
Другой часто используемый метод – турнирный отбор. Он заключается в том, что случайно выбирается несколько особей из популяции (обычно 2) и победителем выбирается особь с наибольшей приспособленностью.
Кроме того, в некоторых реализациях алгоритма применяется так называемая стратегия элитизма, которая заключается в том, что особи с наибольшей приспособленностью гарантировано переходят в новую популяцию. Использование элитизма обычно позволяет ускорить сходимость генетического алгоритма. Недостаток использования стратегии элитизма в том, что повышается вероятность попадания алгоритма в локальный минимум.

Этап отбора

Слайд 23

Обычно в качестве них применяются или ограничение на максимальное число эпох

функционирования алгоритма, или определение его сходимости, обычно путем сравнивания приспособленности популяции на нескольких эпохах и остановки при стабилизации этого параметра.

Определение критериев останова

Слайд 24

# include
# include
# include
int main()
{
using namespace std;
srand((unsigned)time(NULL));
const int

N = 1000;
int a[N]; //заполняем нулями
fill(a, a+N, 0);
for (;;)
{ //мутация в случайную сторону каждого элемента:
for (int i = 0; i < N; ++i)
if (rand()%2 == 1) a[i] += 1; else a[i] -= 1;
//теперь выбираем лучших, отсортировав по возрастанию...
sort(a, a+N);
//... и тогда лучшие окажутся во второй половине массива. //скопируем лучших в первую половину, куда они оставили потомство, а первые умерли:
copy(a+N/2, a+N, a /*куда*/);
//теперь посмотрим на среднее состояние популяции. Как видим, оно всё лучше и лучше.
cout << accumulate(a, a+N, 0) / N << endl;
}
}

Пример на C++

Слайд 25

Непрерывные генетические алгоритмы

Слайд 26

двоичное представление хромосом влечет за собой определенные трудности при поиске в

непрерывных пространствах большой размерности, и когда требуется высокая точность найденного решения.
точность представления определяется количеством разрядов, используемых для кодирования одной хромосомы. Поэтому при увеличении N пространство поиска расширяется и становится огромным
при увеличении длины битовой строки необходимо увеличивать и численность популяции

Проблемы двоичного кодирования

Слайд 27

хромосома есть вектор вещественных чисел
Длина хромосомы будет совпадать с длиной вектора-решения

оптимизационной задачи, иначе говоря, каждый ген будет отвечать за одну переменную. Генотип объекта становится идентичным его фенотипу.

Вещественное кодирование

Слайд 28

Использование непрерывных генов делает возможным поиск в больших пространствах (даже в

неизвестных), что трудно делать в случае двоичных генов, когда увеличение пространства поиска сокращает точность решения при неизменной длине хромосомы.
Одной из важных черт непрерывных ГА является их способность к локальной настройке решений.
Использование RGA для представления решений удобно, поскольку близко к постановке большинства прикладных задач. Кроме того, отсутствие операций кодирования/декодирования, которые необходимы в BGA, повышает скорость работы алгоритма.

Преимущества

Слайд 29

В качестве операторов отбора особей в родительскую пару здесь подходят любые

известные из BGA: рулетка, турнирный, случайный.
Операторы скрещивания и мутации не годятся: в классических реализациях они работают с битовыми строками.

Особенности

Слайд 30

Большинство real-coded алгоритмов генерируют новые векторы в окрестности родительских пар.
Пусть C1=(c11,c21,…,cn1)

и C2=(c12,c22,…,cn2) – две хромосомы, выбранные оператором селекции для скрещивания. Предполагается, что ck1<=ck2 и f(C1)>=f(C2).

Оператор кроссовера

Слайд 31

Плоский кроссовер (flat crossover): создается потомок H=(h1,…,hk,…,hn), hk, k=1,…, n –

случайное число из интервала [ck1,ck2].
Простейший кроссовер (simple crossover): случайным образом выбирается число k из интервала {1,2,…,n-1} и генерируются два потомка H1=(c11,c21,…,ck1,ck+12,…,cn2) и H2=(c12,c22,…,ck2,ck+11,…,cn2).

Арифметический кроссовер (arithmetical crossover): создаются два потомка H1=(h11,…,hn1), H2=(h12,…,hn2), где hk1=wck1+(1-w)ck2,

hk2=w*ck2+(1-w)*ck1, k=1,…,n, w либо константа (равномерный арифметический кроссовер) из интервала [0;1], либо изменяется с увеличением эпох (неравномерный арифметический кроссовер).
Геометрический кроссовер (geometrical crossover): создаются два потомка H1=(h11,…,hn1), H2=(h12,…,hn2), где hk1= (сk1)w*(ck2)1-w, (ck2)w*(ck1)1-w, w – случайное число из интервала [0;1].

Слайд 33

Смешанный кроссовер (blend, BLX-alpha crossover): генерируется один потомок H=(h1,…,hk,…,hn), где hk

– случайное число из интервала [cmin–I*alpha,cmax+I*alpha], cmin=min(ck1,ck2), cmax=max(ck1,ck2), I=cmax–cmin. BLX-0.0 кроссовер превращается в плоский
Линейный кроссовер (linear crossover): создаются три потомка Hq=(h1q,…,hkq,…,hnq), q=1,2,3, где hk1=0.5*ck1+0.5*ck2, hk2=1.5*ck1-0.5*ck2, hk3=–0.5*сk1+1.5*ck2. На этапе селекции в этом кроссовере отбираются два наиболее сильных потомка.

Слайд 34

Дискретный кроссовер (discrete crossover): каждый ген hk выбирается случайно по равномерному

закону из конечного множества {ck1,ck2}.
Расширенный линейчатый кроссовер (extended line crossover): ген hk=ck1+w*(ck2–ck1), w – случайное число из интервала [-0.25;1.25].
Эвристический кроссовер (Wright’s heuristic crossover). Пусть C1 – один из двух родителей с лучшей приспособленностью. Тогда hk=w*(ck1-ck2)+ck1, w – случайное число из интервала [0;1].

Слайд 35

Нечеткий кроссовер (fuzzy recombination, FR-d crossover): создаются два потомка H1=(h11,…,hn1), H2=(h11,…,hn2).

Вероятность того, что в i-том гене появится число vi , задается распределением p(vi) {F(ck1),F(ck2)}, где F(ck1),F(ck2) – распределения вероятностей треугольной формы (треугольные нечеткие функции принадлежности) со следующими свойствами (ck1<=ck2 и I=|ck1–ck2|):

Слайд 36

Параметр d определяет степень перекрытия треугольных функций принадлежности, по умолчанию d=0.5
BLX-кроссовер

с параметром alpha=0.5 – превосходит по эффективности большинство простых кроссоверов.

Слайд 37

наибольшее распространение получили: случайная и неравномерная мутация (random and non-uniform mutation).
При

случайной мутации ген, подлежащий изменению, принимает случайное значение из интервала своего изменения. В неравномерной мутации значение гена после оператора мутации рассчитывается по формуле:

Оператор мутации

Слайд 38

SBX (англ.: Simulated Binary Crossover) – кроссовер, имитирующий двоичный. Был разработан

в 1995 году исследовательской группой под руководством K. Deb’а. Как следует из его названия, этот кроссовер моделирует принципы работы двоичного оператора скрещивания.
Для генерации потомков используется следующий алгоритм, использующий выражение для P(β). Создаются два потомка Hk=(h1k, …, hjk, …, hnk), k=1,2, где , – число, полученное по формуле:

SBX-кроссовер