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

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

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

В генетических алгоритмах популяция эволюционирует от поколения k к поколению k+1 с помощью трех операторов:

  • оператор выбора
  • оператор кроссовера
  • Оператор мутации.

Процесс исходит из генетической эволюции. Начнем с совокупности произвольно выбранных начальных потенциальных решений. Оценивается их относительная работоспособность (приспособленность). На основе этих показателей мы создаем новую совокупность потенциальных решений с помощью операторов. Мы повторяем этот цикл, пока не получим удовлетворительное решение.

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

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

  1. Случайно сгенерированная базовая популяция: n векторов решений (индивидов)
  2. Оценка каждого человека, эта оценка возвращает количественное значение (фитнес)
  3. Отбор по жребию подмножества людей с помощью колеса смещения, по рангу, по турниру или по евгенике. У каждого человека есть вероятность быть выбранным, пропорциональная его оценке (или адаптации к проблеме).
  4. Скрещивания и мутации отдельных особей.

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

Пример

Чтобы можно было как можно проще проводить скрещивания и мутации, мы будем кодировать особи двоичной строкой. Затем скрещивание будет выполняться подстрокой, а мутация - изменением бита. Этот процесс называется двоичным кодированием.

Мы ищем максимум f(x)=4x*(1-x) на интервале [0,1]. Мы берем начальную совокупность из 4 элементов, закодированных в 8 битах (которые будут преобразованы в значение от 0 до 1). Новые поколения всегда будут включать 4 человека. Таблица значений начальной генерации выглядит следующим образом:

Элемент
е(х)
% / всего
кумуляция
10111010
0.794678
0.79/2.59=0.31
0.31
11011110
0.460693
0.18
0.49
00011010
0.364990
0.14
0.63
01101100
0.9775586
0.37
1.00
2.595947

Элемент представляет отдельные лица, f(x) значение целевой функции, % / total представляет собой процент значения целевой функции элемента по сравнению с суммой значений целевой функции, кумулятивное значение представляет собой сумму процентов. Таким образом, в конечном итоге мы имеем важность каждого человека с учетом значения целевой функции.

Теперь, когда оценка сделана, нам нужно выбрать особей для скрещивания. Поскольку у нас есть шкала важности каждого человека, мы можем рисовать людей случайным образом. Действительно, чем выше объективная ценность индивидуума, тем больше вероятность того, что он будет привлечен. Выбирается четыре случайных числа от 0 до 1: 0,34, 0,02, 0,64 и 0,77. Поэтому мы выбрали этих людей: 11011110, 10111010, 01101100, 01101100.

Мы выбрали родителей, теперь нам предстоит скрещивание. Для этого выбираем случайный маркер в битовой строке и меняем местами правую часть строки:

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

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

Делиться
ru_RURU
%d такие блоггеры, как: