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

Повышение эффективности алгоритмов решения задач дискретной оптимизации средствами параллельного программирования

ФИО студента: Малхасян Степан Арамович

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

Кампус/факультет: Факультет прикладной математики и кибернетики

Программа: Системы управления и обработки информации в инженерии (Магистратура)

Год защиты: 2015

В данной работе рассматривается проблема повышения эффективности алгоритмов решения задач дискретной оптимизации на примере задачи маршрутизации транспорта с ограничением грузоподъемности методами параллельного программирования. Первая глава посвящена исследованию задач дискретной оптимизации и алгоритмов их решения. В ней рассмотрены различные виды задачи маршрутизации транспорта, из числа которых была выделена одна, наиболее широкая, к которой сводятся как другие ЗМТ, так и различные задачи дискретной оптимизации. Также были исследованы методы решения ЗМТ, из числа которых был выбран и проанализирован алгоритм муравьиных колоний, относящийся к метаэвристическим алгоритмам. Во второй главе исследованы основные принципы и подходы параллельного программирования, рассмотрены различные классификации параллельных вычислительных систем, проанализированы современные и наиболее часто используемые средства параллельного программирования, из числа которых, на основе специфики применения каждого из них, были выделены наиболее подходящие для решения задач дискретной оптимизации. Кроме того, была исследована основная схема работы алгоритма муравьиных колоний на предмет областей, имеющих возможность быть разделенными на несколько параллельно выполняющихся потоков. Была предложена блок-схема, отражающая все параллельные блокиалгоритма муравьиных колоний. В качестве вывода к этой главе, были рассмотрены инструменты параллельного программирования, которые лучшим образом подходят для распараллеливания тех или иных блоков, выделенных в алгоритме. В третьей главе приведены результаты вычислительных экспериментов. Расчет проводился на выборке модельных задач маршрутизации транспорта с ограничениями грузоподъемности. Повышение эффективности вычислений подтверждается сравнением результатов, полученных без и с использованием средств параллельного программирования.

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

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

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

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

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

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