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

Пусть мы ищем решение, максимизирующее функцию w (целевую функцию)

1.Строим начальную популяцию S={s₁,…,s_k}, s_i – какие-то решения. 2.Производим селекцию особей, наиболее пригодных к размножению 3.Скрещивание выбранных особей 4.Мутация

5.Замещение. Самые слабые особи из популяции заменяются на самых жизнеспособных молодых особей

1)Начальная популяция выбирается случайным образом или жадными методами.

2)Селекция.При селекции отбираются особи, которые будут производить потомство. Первый шаг — вычисление пригодности особей (fitness assignment). Каждая особь популяции получает вероятность репродукции, зависящую от значения целевой функции на этой особи (целевого значения) и целевых значений всех других особей популяции.

При пропорциональной селекции для особи s_i вероятность стать родителем задается формулой P(i) =

Турнирная селекция Выбирается случайное подмножество элементов популяции (участников турнира) и среди них выбираются элементы с лучшими значениями целевой функции

3)Обычное скрещивание, многоточечное скрещивание(позиция скрещивания 2,6,10), однородное вероятностное скрещивание (По решениям s₁, s₂ строится решение s₃, присваивая каждому биту потомка с вероятностью 0,5 значение соответствующего бита одного из родителей )

4)Мутация Оператор мутации, применяемый к решению s₃, с заданной вероятностью p_mÎ(0,1) меняет значение каждого бита на противоположное. Применяем оператор мутации ко всем произведенным потомкам

5)Замещение 1.Произвести столько же потомков, сколько было особей в популяции и заместить всех потомками.

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

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

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