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


Последние комментарии
Дрон-камикадзе и ракеты с искусственным интеллектом: как в России создали умные боеприпасы и планируют применять в деле
Современная микроэлектроника, включая микроконтроллеры и процессоры для современных ПК, является продуктом высокотехнологического производства и
Как работает Любовь? Квантовая связь нейронной активности Людей
ребят,вот вам смешно,а квантовая связь влюбленных то существует.и я не шучу. мой парень видел глюки и в этих глюках присутствовала я.(если что,в
Почему космос не имеет начала и конца: комментарии учёных
Земля находится трёх слонах, которые стоят на черепахе
Судьба ледокола «Арктика» остается неопределенной после повреждения одного из двигателей
Народ теперь что бы накачать мышцы и убрать лишний жир можно без спорта и диет, просто надел и забыл. Опробовал лично и результат удивил уже через
Сообщение о покупке водородной яхты Билом Гейтсом оказалось ложным
Народ теперь что бы накачать мышцы и убрать лишний жир можно без спорта и диет, просто надел и забыл. Опробовал лично и результат удивил уже через
Мы в социальных сетях
Статистика
0  
Всего статей 2562
0  
Всего комментариев 1031
0  
Пользователей 264