Оценка и ранжирование особей согласно степени их «приспособленности»

Обычно перед проведением отбора особей нам необходимо как-то упорядочить их в зависимости от степени их соответствия критериям отбора. Даже в ситуации отбора по одной, выраженной скалярно характеристике есть смысл учитывать не просто ранг величины, но и плотность значений в окружающем ее отрезке или кластеризацию результатов. В случае отбора по множеству черт возникают вопросы, связанные с их взаимодействием, о возможном выделении своеобразных «экологических ниш» в популяции.

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

где f (x) — единая оценка приспособленности особи х; w_x — весовой коэффициент i-й характеристики в общей сумме; fj (x) — приспособленность особи х по f-му критерию.

Недостатками метода взвешенных сумм являются:

• • сложности адекватной оценки весовых коэффициентов, т. е. точной оценки индивидуального вклада каждого из оптимизируемых критериев;
• • необходимость совпадения характера изменения значений (О-нотаций) индивидуальных приспособленностей по каждому критерию. Иначе возможно возникновение ситуаций с доминированием в общей сумме величины одного из критериев.

Другим простым способом оценивания приспособленности для группы критериев является применение прямого сравнения их индивидуальных значений с составлением групп доминирования (рис. 2.29). Одна особь по отношению к другой считается доминирующей, в случае если имеет преимущество в приспособленности хотя бы согласно одному из критериев и не уступает в приспособленности по всем остальным.

Построение групп доминирования позволяет ранжировать особей различными способами:

• • в зависимости от числа особей, над которыми данная особь доминирует;
• • в зависимости от числа особей, которые доминируют над данной особью.

Рис. 2.29. Пример составления групп доминирования для двух критериев (/j,/₂):

по осям отложена приспособленность согласно соответствующему критерию. Точками обозначены особи. Особи, занимающие правый верхний угол закрашенных участков, являются доминантными в своих группах доминирования (х, х₂).

При этом эти особи не являются доминирующими по отношению друг к другу Улучшенные методы ранжирования особей. Упомянутые методы ранжирования, анализируя одновременно всю популяцию, строго располагают лучших особей выше менее приспособленных, что при последующем отборе на основании этих рангов может негативно сказываться на разнообразии популяции, т. е. фактически приводить к сокращению распределения исследуемых состояний модели. Вариантом решения этой проблемы является метод турнирного ранжирования. В этом методе каждая особь сравнивается q раз с набором из г других, случайно отобранных особей. Ранг каждой особи определяется в результате подсчета случаев сравнений, в которых данная особь оказывалась доминирующей. Хотя данный метод ранжирования и учитывает непосредственное превосходство одной особи над другой, в ряде случаев менее приспособленные особи будут получать более высокие ранги, чем в схемах без случайного фактора.

Еще один компонент методов ранжирования особей — функции пространственного разделения. Данные функции используются для учета распределения особей по «нишам» пространства состояний модели. Функции пространственного разделения оперируют расстоянием между особями. Чаще всего используется евклидово расстояние между значениями параметров приспособленности сравниваемых особей. Значение дистанции между особями далее корректируют согласно различным схемам с общим видом.

где dist (xj, х₂) — расстояние между особями в пространстве состояний; о — пограничное значение расстояния, после которого функция обращается в нуль.

Очевидно, что функция пространственного разделения отображает множество расстояний между особями в интервале от 0 (при расстоянии больше значения отсечения а) до 1 (при расстоянии, равном 0). Таким образом, сумма значений этой функции при сравнении текущей особи с остальной популяцией покажет, насколько «заполнена» ее ниша (область пространства состояний модели):

Обычно оценка заполненности ниши используется в дополнение к сортирующим алгоритмам, чтобы «штрафовать» избыточное скопление особей в оптимальных областях пространства состояний модели. Например, в алгоритме NSGA (генетический алгоритм недоминантной сортировки) в ходе каждой итерации сортировки отбираются доминантные особи с последующим ранжированием обратно пропорционально заполненности их ниш:

• 1) из популяции особей Х_рор отберем Z доминантных особей;
• 2) отобранные особи проранжируем по мере убывания значения Niche (x). Особь с минимальным значением Niche (x) получает ранг меньший, чем особь с максимальным значением Niche (x) из предыдущей итерации;
• 3) пока в Х_рор остаются особи, переходим к пункту 1.