DOI: 10.17587/prin.16.462-469

УДК: 004.021

Алгоритмы ранжирования по доминированию при решении задач многокритериальной оптимизации генетическими алгоритмами

А. Г. Юртаев, аспирант, agyurtaev@mail.ru, Саратовский государственный технический университет имени Гагарина Ю. А.

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

Ключевые слова: генетические алгоритмы, многокритериальная оптимизация, ранжирование по доминированию, Парето-фронт, попарное сравнение, KD-дерево, разделяй и властвуй, рекурсивные алгоритмы, асимптотическая сложность, геометрический баланс, коэффициент вариации, коэффициент асимметрии, нормированная энтропия

Стр. 462—469

Ссылка для цитирования:
Юртаев А. Г. Алгоритмы ранжирования по доминированию при решении задач многокритериальной оптимизации генетическими алгоритмами // Программная инженерия. 2025. Том 16, № 9. С. 462—469. DOI: 10.17587/prin.16.462-469.

Полный текст на eLIBRARY