Часть 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 с.


Если у вас есть статья, заметка или обзор, которыми вы хотите поделиться с аудиторией нашего сайта, присылайте информацию на: neuronus.com@yandex.ru.
Гость, оставишь комментарий?
Имя:*
E-Mail:


Свежее новое
  • На B-52 испытали новую гиперзвуковую ракету
  • Б-52 — знаменитый североамериканский бомбардировщик стратегического назначения. Минобороны США планирует оснастить этот самолет новейшим комплексом
  • Две погасшие звезды слились воедино и образовали одну, которая «ожила»
  • Можно ли из двух мертвых тел создать одно живое? Оказывается, это реально, если речь идет о звездах. Астрономы открыли такую редкую звезду, которая
  • Трансгенные грибы могут истреблять разносчиков малярии и других москитов
  • Ученые из США и Буркина-Фасо провели эксперименты, доказавшие эффективность нового средства от москитов. Это генномодифицированный гриб вида
  • Ролик о массовом взлете конвертопланов Osprey и вертолетов CH-53E завораживает
  • По сети гуляет видео, где несколько десятков летательных аппаратов ВМС Соединенных Штатов Америки демонстрируют слаженный взлет. Этот завораживающий
  • Ученые нашли окаменелость, которая сохранила целую стаю рыбок
  • В Америке нашли окаменелость, в которой «законсервирована» целая стайка рыбок. Они застыли в процессе движения, которое, как считают ученые, было
Последние комментарии
Ролик о массовом взлете конвертопланов Osprey и вертолетов CH-53E завораживает
Сколько раз я задавал вопрос про аварийную посадку конвертоплана,но так и не получил ответа. Если у него двигатели не повернутся вверх,то как он
5 необъяснимых для науки загадок
Ваша цитата: "Масса - это сконцентрированная Энергия. Энергия - это не сконцентрированная Масса".   Мой комментарий: Чтобы увеличить (в общем случае
Исследование показало: рождение ребенка старит женщину на 11 лет, а бездетные люди живут меньше
Корреляция в данном случае заключается в том что работает программа размножения. Программа размножения с точки зрения системы не дать умереть виду,
Сколько придется лететь со скоростью света до ближайшей звезды?
Ни какого замедления времени и ни какого сокращения расстояния не происходит при полёте в Космосе со скоростью близкой к скорости света, а тем более
Сколько придется лететь со скоростью света до ближайшей звезды?
Ближайшая звезда к нам, это Солнце. Расстояние порядка 150 млн. км. (Астрономическая единица). Несложные арифметические действия и "вуаля", получаем
Мы в социальных сетях
Статистика
3  
Всего статей 2003
1  
Всего комментариев 333
2  
Пользователей 118