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


 
Свежее новое
  • Четверть населения Финляндии, будет обучена работе с роботами и нейросетями.
  • Финляндии предстоит расти и расти, перед тем, как она сможет выйти на мировой рынок с технологиями искусственного интеллекта и все же, это не мешает
  • Как искусственный интеллект передает информацию от людей, потерявших способность говорить?
  • Несколько групп ученых смогли преобразовать команды головного мозга в речь с помощью компьютера-синтезатора. Для того, чтобы это сделать, они
  • К 2025 году, роботы строители, могут составить 10 процентов рабочей силы Японии.
  • Япония является одной из стран, в которой автоматизация процесса строительства, происходит очень медленно. Роботы на практике показывают лишь то, что
  • Интуитивный Алгоритм Технологической Сингулярности на основе Сильного Искусственного Интеллекта «Smart-MES»
  • Технологическая Сингулярность означает такое быстрое развитие прогресса, связанное с созданием сообщества Сильных Искусственных Интеллектов, когда
  • Видеокамеры научились различать телефоны в руках автомобилистов
  • Совсем недавно, в Москве, Сергей Собянин сделал официальное заявление, что с 2019 года в Москве заработают камеры, которые будут отслеживать опасных
Последние комментарии
Каким был первый робот в мире? Происхождение слова "Робот"
Восхищения нет предела делу ваших рук и идей. Хочется склонить голову перед вашим трудом, хотя твердо придерживаюсь Библии (не поклоняться идолам)
Как работает Любовь? Квантовая связь нейронной активности Людей
Я думаю, когда начнется квантовое взаимодействие мржду человеком и ИИ это и будет началом конца.
Как работает Любовь? Квантовая связь нейронной активности Людей
Как вы считаете, возможно ли образование квантовых взаимодействий между человеком и ИИ? 
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
А почему бы сразу СИИ не запустить в другую галактику, может там нет коррупции, воровства, плебейства и прочей муры, которая не только мешает
Искусственный Интеллект. Концепция развития и внедрения Искусственного Интеллекта (Искусственной Аналитики)
Согласен. проблема ИИ не в наборе задач. Главная проблема - познание процесса мышления как феномена физиологии головного мозга человека.
Мы в социальных сетях
Статистика
0  
Всего статей 1545
0  
Всего комментариев 76
0  
Пользователей 69