Читать книгу Портфельная теория и методы оптимизации. NSGA, POWER BI - - Страница 3

NSGA-II запускается с популяцией размером, генерируемой случайно в пределах границ переменных. Параметры включают: вероятность кроссовера, мутации (где – размер хромосомы), индексы распределения для SBX-кроссовера и полиномиальной мутации. Максимум поколений или функция оценок служит критерием остановки. [51] [53]

Шаг 1: Недоминирующая сортировка

Для объединенной популяции (размер) присваивается ранг каждому индивиду:

– Инициализировать (множество доминируемых индивидов), (число доминирующих), фронт.

– Для каждого: для каждого, если доминирует (, строгое неравенство хотя бы для одного), то; иначе. Если, добавить в.

– Для: пока не пуст, для каждого, для каждого:; если, добавить в. Ранг индивида из равен. Сложность, где – число целей. [51] [52] [54]

Шаг 2: Вычисление crowding distance

Для каждого фронта (отсортированного по каждой цели отдельно):

– Инициализировать для всех целей,.

– Для каждой цели:, сортировать по (пусть – индексы). Граничным.

– Для:, где предотвращает деление на ноль.

– . Индивиды сортируются сначала по рангу (возрастанию), затем по (убыванию). [51] [55] [53]

Шаг 3: Турнирная селекция и рекомбинация

Из формируется mating pool размером: бинарный турнир между случайными парами – побеждает меньший ранг, при равенстве больший. Затем применяются кроссовер (SBX для вещественных, одно-/двухточечный для бинарных) и мутация (полиномиальная/битовая), генерируя потомков размером. [51] [52] [56]

Шаг 4: Элитный отбор и переход

Объединить, выполнить шаги 1—2. Формировать: начинать с, пока размер; в частично заполняющем фронте взять индивидов с наибольшим до. Установить, повторить до. Итоговый фронт из – аппроксимация Парето-фронта. [51] [52] [54]

⁂

Как рассчитывается crowding distance в деталях

Crowding distance в NSGA-II оценивает плотность решений на каждом фронте Парето, предпочитая разреженные области для поддержания разнообразия. Расчет выполняется отдельно для каждого фронта после недоминирующей сортировки. [71] [72]