Часть 10. Правила выбора особей

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

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

Рассмотрим в отдельности каждый из случаев.

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

При решении задачи максимизации особь тем лучше, чем больше значение её функции приспособленности. Пусть имеем N особей, из которых производим выбор, и соответствующие им значения функции приспособленности Ri, i=(1, N). Для вычисления вероятностей выбора особей по значениям функции приспособленности необходимо использовать следующее выражение:

(1) ,

где

(2)

Следует учесть, что при использовании выражения (1) самая плохая особь никогда не будет выбрана: P = 0.

При решении задачи минимизации особь тем лучше, чем меньше значение её функции приспособленности. В этом случае для вычисления вероятностей выбора особей по значениям функции приспособленности можем использовать выражение:

(3) ,

где

(4)

Аналогично предыдущему случаю при использовании выражения (3) особь с наибольшим значением приспособленности никогда не будет выбрана.

Если число особей, из которых производится выбор, небольшое, вероятность выбора худшей из них должна отличаться от нуля. В этом случае имеет смысл задаться минимальной вероятностью выбора худшей особи, исходя из следующих рассуждений. При одинаковых значениях функции приспособленности всех особей вероятности выбора каждой из них должны быть равны и определяются числом самих особей: P = 1/N. Введём понижающий коэффициент (γ), определяющий минимальную вероятность выбора:

(5)

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

Зависимость минимальной вероятности выбора из нескольких особей от их количества и значения понижающего коэффициента

Понижающий коэффициент (γ)Количество особей (N)
23456
0,1 0,050 0,033 0,025 0,020 0,017
0,2 0,100 0,067 0,050 0,040 0,033
0,3 0,150 0,100 0,075 0,060 0,050
0,4 0,200 0,133 0,100 0,080 0,067
0,5 0,250 0,167 0,125 0,100 0,083

С учётом вышесказанного, в числитель и знаменатель соотношений (1) и (3) вносится поправка Q, в результате чего они преобразуются к видам (6) и (7) соответственно:

(6) ,
(7)

,

где значения Q рассчитываются по соотношениям (8) и (9) соответственно:

(8) ,
(9)

Ещё один способ перейти к отличной от нуля вероятности выбора худшей особи – принять значения Rmin и Rmax выходящими за пределы диапазона изменения приспособленностей всех особей текущей популяции на некоторую его часть (0 < φ ≤ 0,5). В этом случае соотношения (2) и (4) заменяются на (10) и (11), а формулы для расчёта вероятностей остаются прежними: (1) и (3):

(10) ,
(11)

При решении вопроса о выборе одной из получившихся дочерних особей для включения в новое поколение руководствуются следующими правилами:
– особь выбирается случайным образом;
– особь выбирается случайным образом с вероятностями, пропорциональными улучшению функции приспособленности, рассчитываемыми по соотношениям (1) или (6) – при решении задачи максимизации и (3) или (7) – при решении задачи минимизации;
– выбирается особь с наилучшим значением функции приспособленности.

При выборе особей для исключения из популяции, с учётом используемых эволюционных стратегий, руководствуются следующими правилами:
– все особи выбираются случайным образом;
– все особи выбираются случайным образом с вероятностями, пропорциональными ухудшению функции приспособленности, т. е. для задачи максимизации используют выражения (3) или (7), а для задачи минимизации – (1) или (6);
– выбираются особи с наихудшими значениями функции приспособленности.

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

По материалам учебного пособия:
Дударов С. П. Математические основы генетических алгоритмов: учеб. пособие/ С. П. Дударов. – М.: РХТУ им. Д. И. Менделеева, 2012. – 56 с.


Гость, оставишь комментарий?
Имя:*
E-Mail:


 
Свежее новое
  • В Москве пройдет один из крупнейших хакатонов в мире в сфере искусственного интеллекта
  • PicsArt, ведущая творческая платформа для создания контента и визуализации историй в социальных сетях с более чем 100 миллионами активных
  • Сильный Искусственный Интеллект «Smart-MES» меняет взгляды на Технологическую Сингулярность
  • Учёные полагают, что Технологическая Сингулярность наступит тогда, когда Сильный Искусственный Интеллект будет способен самостоятельно создавать себе
  • Навыки голосовых помощников от Amazon, Google, Microsoft и Яндекс
  • После лекции директора по маркетингу умного помощника Алисы, Даниилы Колесникова, меня посетило вдохновение и любопытство. Так как мы сами сейчас
  • Конкурс идей от лаборатории Касперского - Kaspersky Start Russia
  • Если ты инициативный лидер, у тебя есть знания в области IT и тебе хотелось бы возглавить собственный проект в лаборатории Касперского, то подай
  • Смарт-города, умный транспорт и инновации для ЖКХ: что обсуждали на конференции «Интернет вещей»
  • Интернет вещей для промышленности, транспорта, ЖКХ и торговли: в Москве обсудили развитие и внедрение технологии. Конференция «Интернет вещей»,
Последние комментарии
5 лучших приложений искусственного интеллекта для вашего телефона Android
какой это искусственный разум мне смешно не пудрите людям мозги ,голосовой поисковик- это интелект ха ха ну вы тут и загибаете фантастику
5 лучших приложений искусственного интеллекта для вашего телефона Android
Всё вышеперечисленное назвать интеллектом можно с большущей натяжкой. Так, программки-автоматы с почти хорошим распознаванием несложной речи.
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
У нас очень странный народ, если что не понимает, то обязательно надо сунуть в морду. Зачем? А не лучше ли поинтересоваться, почему именно так? У
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
Господин Чернов. Поясню. Любой инструмент, даже прозаическая кофемолка, проходят процедуру стендовых испытаний. Сертификат соответствия
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
     " И странная картина получается в коридорах власти ". Странная картина  получается, если полагать, что власть эта поставлена для решения задач
Мы в социальных сетях
Статистика
0  
Всего статей 1533
0  
Всего комментариев 65
0  
Пользователей 56