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

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