• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

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

ФИО студента: Бондарцев Никита Сергеевич

Руководитель: Громов Василий Александрович

Кампус/факультет: Факультет компьютерных наук

Программа: Науки о данных (Магистратура)

Год защиты: 2019

Было предложено несколько новых модификаций генетического алгоритма с видообразованием: ГА с разбиением видов на хищники и жертвы случайным образом, ГА с разбиением видов на хищники и жертвы с максимизацией энтропии при соблюдении баланса между хищниками и жертвами (далее оптимальное разбиение), ГА с оптимальным разбиением на хищники и жертвы и решением СЛАУ на фитнесы видов с и без пересчёта фитнесов индивидов. Предложенные модификации были протестированы на четырёх бенчмарках с различными размерами популяции, мутациями и кроссоверами. Для всех бенчмарков и всех наборов параметров, кроме кроссовера DPX для задачи rat195, модифицированный алгоритм показал более хорошие результаты, чем классический с тем же числом вычислений фитнеса. По сравнению с классическим ГА с большим числом скрещиваний модифицированный ГА смог достичь устойчиво более хороших результатов для задачи eil51. На остальных бенчмарках модифицированный ГА дал результаты хуже, но по-прежнему использовал значительно меньшее количество вычислений фитнеса. Было показано, что в условиях, когда классический генетический алгоритм сходится к локальному оптимуму, модифицированный генетический алгоритм с большей вероятностью пройдёт ближе к глобальному оптимуму. Также было отмечено, что модифицированный генетический алгоритм имеет меньший разброс результатов, чем классический, а значит понадобится меньше запусков, чтобы удостовериться, что найдено решение, близкое к наилучшему из тех, которое можно найти с помощью выбранного ГА.

Выпускные квалификационные работы (ВКР) в НИУ ВШЭ выполняют все студенты в соответствии с университетским Положением и Правилами, определенными каждой образовательной программой.

Аннотации всех ВКР в обязательном порядке публикуются в свободном доступе на корпоративном портале НИУ ВШЭ.

Полный текст ВКР размещается в свободном доступе на портале НИУ ВШЭ только при наличии согласия студента – автора (правообладателя) работы либо, в случае выполнения работы коллективом студентов, при наличии согласия всех соавторов (правообладателей) работы. ВКР после размещения на портале НИУ ВШЭ приобретает статус электронной публикации.

ВКР являются объектами авторских прав, на их использование распространяются ограничения, предусмотренные законодательством Российской Федерации об интеллектуальной собственности.

В случае использования ВКР, в том числе путем цитирования, указание имени автора и источника заимствования обязательно.

Реестр дипломов НИУ ВШЭ