Гибридный алгоритм для двухкритериальной задачи оптимизации трафика в сети

Standard

Гибридный алгоритм для двухкритериальной задачи оптимизации трафика в сети. / Юськов, Александр Дмитриевич ; Кулаченко, Игорь Николаевич ; Мельников, Андрей Андреевич и др.

в: Дискретный анализ и исследование операций, Том 32, № 3 (165), 2025, стр. 117-144.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

BibTeX

@article{122603a2baa84700a601eb3774181370,

title = "Гибридный алгоритм для двухкритериальной задачи оптимизации трафика в сети",

abstract = "Рассматривается задача оптимизации трафика в сети передачи данных. Для моделирования трафика используется имитационная модель. Пути передачи задаются неявно весами дуг. Если поток по дуге превышает её пропускную способность, то дуга считается перегруженной. Задача состоит в минимизации двух целевых функций: числа перегруженных дуг и расстояния от исходного вектора весов при соблюдении ограничений на суммарный поток в сети и появление новых перегруженных дуг. Предложена двухстадийная эволюционная схема, включающая алгоритм локального поиска по окрестностям большой мощности для получения стартового приближения границы Парето. Лучшее соседнее решение ищется при помощи оригинальной модели целочисленного линейного программирования. Проведено сравнение предложенного подхода с лучшими эволюционными алгоритмами на примерах с 628 каналами и 1324 запросами, и показано, что новая схема демонстрирует результаты, статистически лучшие на 15-49% по многим показателям качества (9 из 10). Табл. 3, ил. 6, библиогр. 42",

keywords = "оптимизация «чёрного ящика», матэвристика, поиск с чередующимися окрестностями, OSPF, эволюционный алгоритм, black box optimization, matheuristic, variable neighbourhood search, OSPF, evolutionary algorithm",

author = "Юськов, {Александр Дмитриевич} and Кулаченко, {Игорь Николаевич} and Мельников, {Андрей Андреевич} and Кочетов, {Юрий Андреевич}",

note = "Гибридный алгоритм для двухкритериальной задачи оптимизации трафика в сети / А. Д. Юськов, И. Н. Кулаченко, А. А. Мельников, Ю. А. Кочетов // Дискретный анализ и исследование операций. – 2025. – Т. 32, № 3(165). – С. 117-144. – DOI 10.33048/daio.2025.32.827. – EDN NTZARH. Исследование выполнено в рамках государственного задания Института математики им. С. Л. Соболева (проект № FWNF-2022-0019).",

year = "2025",

doi = "10.33048/daio.2025.32.827",

language = "русский",

volume = "32",

pages = "117--144",

journal = "Дискретный анализ и исследование операций",

issn = "1560-7542",

number = "3 (165)",

}

RIS

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