Research output: Contribution to journal › Article › peer-review
Гибридный алгоритм для двухкритериальной задачи оптимизации трафика в сети. / Юськов, Александр Дмитриевич; Кулаченко, Игорь Николаевич; Мельников, Андрей Андреевич et al.
In: Дискретный анализ и исследование операций, Vol. 32, No. 3 (165), 2025, p. 117-144.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - Гибридный алгоритм для двухкритериальной задачи оптимизации трафика в сети
AU - Юськов, Александр Дмитриевич
AU - Кулаченко, Игорь Николаевич
AU - Мельников, Андрей Андреевич
AU - Кочетов, Юрий Андреевич
N1 - Гибридный алгоритм для двухкритериальной задачи оптимизации трафика в сети / А. Д. Юськов, И. Н. Кулаченко, А. А. Мельников, Ю. А. Кочетов // Дискретный анализ и исследование операций. – 2025. – Т. 32, № 3(165). – С. 117-144. – DOI 10.33048/daio.2025.32.827. – EDN NTZARH. Исследование выполнено в рамках государственного задания Института математики им. С. Л. Соболева (проект № FWNF-2022-0019).
PY - 2025
Y1 - 2025
N2 - Рассматривается задача оптимизации трафика в сети передачи данных. Для моделирования трафика используется имитационная модель. Пути передачи задаются неявно весами дуг. Если поток по дуге превышает её пропускную способность, то дуга считается перегруженной. Задача состоит в минимизации двух целевых функций: числа перегруженных дуг и расстояния от исходного вектора весов при соблюдении ограничений на суммарный поток в сети и появление новых перегруженных дуг. Предложена двухстадийная эволюционная схема, включающая алгоритм локального поиска по окрестностям большой мощности для получения стартового приближения границы Парето. Лучшее соседнее решение ищется при помощи оригинальной модели целочисленного линейного программирования. Проведено сравнение предложенного подхода с лучшими эволюционными алгоритмами на примерах с 628 каналами и 1324 запросами, и показано, что новая схема демонстрирует результаты, статистически лучшие на 15-49% по многим показателям качества (9 из 10). Табл. 3, ил. 6, библиогр. 42
AB - Рассматривается задача оптимизации трафика в сети передачи данных. Для моделирования трафика используется имитационная модель. Пути передачи задаются неявно весами дуг. Если поток по дуге превышает её пропускную способность, то дуга считается перегруженной. Задача состоит в минимизации двух целевых функций: числа перегруженных дуг и расстояния от исходного вектора весов при соблюдении ограничений на суммарный поток в сети и появление новых перегруженных дуг. Предложена двухстадийная эволюционная схема, включающая алгоритм локального поиска по окрестностям большой мощности для получения стартового приближения границы Парето. Лучшее соседнее решение ищется при помощи оригинальной модели целочисленного линейного программирования. Проведено сравнение предложенного подхода с лучшими эволюционными алгоритмами на примерах с 628 каналами и 1324 запросами, и показано, что новая схема демонстрирует результаты, статистически лучшие на 15-49% по многим показателям качества (9 из 10). Табл. 3, ил. 6, библиогр. 42
KW - оптимизация «чёрного ящика»
KW - матэвристика
KW - поиск с чередующимися окрестностями
KW - OSPF
KW - эволюционный алгоритм
KW - black box optimization
KW - matheuristic
KW - variable neighbourhood search
KW - OSPF
KW - evolutionary algorithm
UR - https://elibrary.ru/item.asp?id=88898864
UR - https://math-sobolev.ru/content/32-3/117
U2 - 10.33048/daio.2025.32.827
DO - 10.33048/daio.2025.32.827
M3 - статья
VL - 32
SP - 117
EP - 144
JO - Дискретный анализ и исследование операций
JF - Дискретный анализ и исследование операций
SN - 1560-7542
IS - 3 (165)
ER -
ID: 75508242