Применение метода изменяющихся вероятностей для задач оптимального размещения на сети

Описание

Перевод названия: Application of the probability changing method for optimal location problems on a network

Тип публикации: статья из журнала

Год издания: 2014

Ключевые слова: discrete optimization, P-median problem, methods of random search, location problem, дискретная оптимизация, p-медианная задача, методы случайного поиска, задачи размещения

Аннотация: Рассматривается p-медианная задача оптимального размещения на графе (сети), являющаяся популярной моделью как в логистических задачах (оптимальное размещение транспортной, телекоммуникационной и иной инфраструктуры), так и опосредованно в задачах кластерного анализа, распознавания образов, в теории оценивания. Цель p-медианной задаПоказать полностьючи на графе (сети) заключается в нахождении определенного числа вершин (узлов) таких, чтобы суммарное расстояние от всех узлов сети до ближайшей из выбранных вершин (узлов) было минимальным. Для приближенного решения рассматриваемой неразрешимой (в общем случае) за полиномиальное время задачи предложен эвристический алгоритм, основанный на идеях метода изменяющихся вероятностей, являющегося методом случайного поиска с адаптацией. Идея алгоритма заключается в случайном выборе вершин в соответствии с заданными вероятностями выбора каждой из вершин и изменении этих вероятностей для каждой из выбранных вершин и вершин в некоторой ее окрестности в зависимости от достигнутого значения целевой функции (т. е. в зависимости от суммарного расстояния от каждой из вершин графа до ближайшей из выбранных вершин). При создании алгоритма для p-медианных задач с большой размерностью и вычислительной сложностью ставится задача оптимального использования вычислительных мощностей. Эффективность алгоритма подтверждена экспериментальной проверкой на тестовых примерах из библиотеки ORLIB. Также приведены результаты работы комбинированного алгоритма - комбинации предложенного алгоритма с процедурой локального поиска для решения данной задачи. Экспериментально показано, что результаты такой комбинации превосходят результаты оригинального многократных запусков алгоритма, реализующего локальный поиск из случайным образом выбранных вершин. Кроме того, в работе экспериментально показано, что для небольших задач алгоритм способен получить точное решение задачи.

Ссылки на полный текст

Издание

Журнал: Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева

Выпуск журнала: 5

Номера страниц: 10-19

ISSN журнала: 18169724

Место издания: Красноярск

Издатель: Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева

Авторы

Вхождение в базы данных