Компьютерные исследования и моделирование
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Компьютерные исследования и моделирование:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Компьютерные исследования и моделирование, 2024, том 16, выпуск 1, страницы 53–68
DOI: https://doi.org/10.20537/2076-7633-2024-16-1-53-68
(Mi crm1148)
 

СПЕЦИАЛЬНЫЙ ВЫПУСК

Модификации алгоритма Frank–Wolfe в задаче поиска равновесного распределения транспортных потоков

И. Н. Игнашинa, Д. В. Ярмошикab

a Национальный исследовательский университет «Московский физико-технический институт», Россия, 141701, г. Долгопрудный, Институтский пер., д. 9
b Институт проблем передачи информации РАН, Россия, 127051, г. Москва, Большой Каретный пер., д. 19, стр. 1
Список литературы:
Аннотация: В работе приведены различные модификации алгоритма Frank–Wolfe для задачи поиска равновесного распределения потоков. В качестве модели для экспериментов используется модель Бекмана. В этой статье в первую очередь уделяется внимание выбору направления базового шага алгоритма Frank–Wolfe (FW). Будут представлены алгоритмы: Conjugate Frank–Wolfe (CFW), Bi-conjugate Frank–Wolfe (BFW), Fukushima Frank–Wolfe (FFW). Каждой модификации соответствуют различные подходы к выбору этого направления. Некоторые из этих модификаций описаны в предыдущих работах авторов. В данной статье будут предложены алгоритмы N-conjugate Frank–Wolfe (NFW) и Weighted Fukushima Frank–Wolfe (WFFW). Эти алгоритмы являются некоторым идейным продолжением алгоритмов BFW и FFW. Таким образом, если первый алгоритм использовал на каждой итерации два последних направления предыдущих итераций для выбора следующего направления, сопряженного к ним, то предложенный алгоритм NFW использует N предыдущих направлений. В случае же Fukushima Frank –Wolfe в качестве следующего направления берется среднее от нескольких предыдущих направлений. Соответственно этому алгоритму предложена модификация WFFW, использующая экспоненциальное сглаживание по предыдущим направлениям. Для сравнительного анализа были проведены эксперименты с различными модификациями на нескольких наборах данных, представляющих городские структуры и взятых из общедоступных источников. За метрику качества была взята величина относительного зазора. Результаты экспериментов показали преимущество алгоритмов, использующих предыдущие направления для выбора шага, перед классическим алгоритмом Frank–Wolfe. Кроме того, было выявлено улучшение эффективности при использовании более двух сопряженных направлений. Например, на многих датасетах модификация 3-conjugate FW сходилась наилучшим образом. Кроме того, предложенная модификация WFFW зачастую обгоняла FFW и CFW, хотя и проигрывала модификациям NFW.
Ключевые слова: Conjugate Frank–Wolfe, Weighted Fukushima Frank–Wolfe, N-conjugate Frank–Wolfe
Финансовая поддержка Номер гранта
ФЦК МФТИ целевой капитал № 5
Министерство науки и высшего образования Российской Федерации FSMG-2024-0011
Работа И. Н. Игнашина была выполнена при поддержке ежегодного дохода ФЦК МФТИ (целевого капитала № 5 на развитие направлений искусственного интеллекта и машинного обучения в МФТИ, https://fund.mipt.ru/capitals/ck5/). Работа Д. В. Ярмошика была выполнена при поддержке Министерства науки и высшего образования Российской Федерации (госзадание), номер проекта FSMG-2024-0011.
Поступила в редакцию: 23.12.2023
Принята в печать: 23.12.2023
Тип публикации: Статья
УДК: 519.8
Образец цитирования: И. Н. Игнашин, Д. В. Ярмошик, “Модификации алгоритма Frank–Wolfe в задаче поиска равновесного распределения транспортных потоков”, Компьютерные исследования и моделирование, 16:1 (2024), 53–68
Цитирование в формате AMSBIB
\RBibitem{IgnYar24}
\by И.~Н.~Игнашин, Д.~В.~Ярмошик
\paper Модификации алгоритма Frank–Wolfe в задаче поиска равновесного распределения транспортных потоков
\jour Компьютерные исследования и моделирование
\yr 2024
\vol 16
\issue 1
\pages 53--68
\mathnet{http://mi.mathnet.ru/crm1148}
\crossref{https://doi.org/10.20537/2076-7633-2024-16-1-53-68}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/crm1148
  • https://www.mathnet.ru/rus/crm/v16/i1/p53
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Компьютерные исследования и моделирование
    Статистика просмотров:
    Страница аннотации:32
    PDF полного текста:7
    Список литературы:11
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024