Использование параллельных вычислений для оптимизации размещения на сети

ИСПОЛЬЗОВАНИЕ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ ДЛЯ ОПТИМИЗАЦИИ РАЗМЕЩЕНИЯ НА СЕТИ

*, **

*Красноярский государственный аграрный университет

**Сибирский государственный аэрокосмический университет

The parallel version of the heuristic optimization algorithm on networks based on the method of changing probabilities is proposed by the authors of the article.

За годы рыночных реформ в аграрном секторе произошли существенные изменения – выросли затраты на производство сельхозпродукции, упал уровень рентабельности, объемы производства резко снизились. В связи c этим особую значимость в обеспечении устойчивости агропромышленного производства приобретает решение  задач оптимизации затрат на производство, в том числе - задач по оптимальному размещению производственных мощностей в сельском хозяйстве. Исследования задач оптимального размещения в сельском хозяйстве, начатые в 1826 Й. Тюненом ("штандорт" сельского хозяйства), послужили мощной основой современной теории размещения [1].

Центральной задачей непрерывной теории размещения является задача Вебера, а главным из ее дискретных обобщений – p-медианная задача на сети [2] – состоящая в поиске p узлов на сети (графе), таких, чтобы суммарное расстояние от всех узлов сети до ближайшего из выбранных p узлов было минимальным. Поиск медиан осуществляется в известном конечном множестве узлов. В случае задачи, изначально сформулированной в виде задачи Вебера, зачастую целесообразной является ее дискретизация [3,4].

Эвристические методы случайного поиска не гарантируют нахождение точного решения, но они статистически оптимальны: процент задач, решенных «почти оптимально», растет с ростом размерности задачи [5]. При решении дискретных задач размещения применяется генетический алгоритм и другие методы [6].

Изначально разработанный для решения безусловных задач псевдо-булевой оптимизации, метод изменяющихся вероятностей (МИВЕР) — это метод случайного поиска, организованный по схеме, изложенной в [5, 7].

Метод изменяющихся вероятностей может также рассматриваться как специфический вариант генетического алгоритма [8]. Модификации, предложенные в [9], позволяют решать задачи размерности до миллионов переменных.

В связи с повсеместным распространением многоядерных систем, разработка параллельных версий алгоритмов для систем с общей памятью может существенно снизить временные затраты на решение подобных задач. Подобные алгоритмы для некоторых задач на базе метода изменяющихся вероятностей описаны в [3, 9, 10].

Пусть G=(V, E) — ненаправленный связный граф (сеть), V={v1,...,vn} — множество вершин, — множество ребер, без петель, т. е. . Каждому ребру ei поставлена в соответствие его длина (для введем обозначение ), каждой j-ой вершине поставлен в соответствие вес . Для любой пары вершин (i, j) определена функция расстояния L(i, j) — длина кратчайшего пути между данными вершинами.

(1)

Здесь — множество ребер, составляющих кратчайший путь между i-й и j-й вершинами, Pi, j — множество всех возможных путей между данными вершинами. Тогда p-медианную задачу можно сформулировать как

(2)

В данной задаче требуется выбрать p вершин таким образом, чтобы сумма взвешенных расстояний от каждой из вершин графа до ближайшей из выбранных вершин была минимальной.

Значения функции вычислим с помощью алгоритма, описанного в [11].

Для применения метода изменяющихся вероятностей целевая функция должна быть выражена как функция булевых переменных. Введем новые переменные x1,...,xn:

. (3)

В случае булевых переменных задача имеет ограничение

. (4)

Обратный переход к исходным целочисленным переменным осуществляется следующим образом:

. (5)

Задачу с псевдобулевой целевой функцией можно сформулировать следующим образом:

(6)

с ограничением (4)

Предлагаемый нами вариант алгоритма МИВЕР значительно повышает эффективность поиска.

Непрерывные задачи размещения, например, множественная задача Вебера в евклидовой, прямоугольной или чебышевской метриках, поддаются аналитическим методам решения благодаря следующему свойству: если — некоторое решение задачи (приведен пример задачи на плоскости), то малое изменение приводит к малому изменению значения целевой функции.

Пусть Lmax — максимальная длина пути в графе:

, (7)

lavg — средняя длина ребра:

. (8)

Наш алгоритм основан на следующих гипотезах:

1. В случае

(9)

при замене в решении любой mi-й точки на на другую j-ю точку, такую, что L(j, mi) мало, то и изменение значения целевой функции будет малым.

2. Если в решении для любых двух точек L(mi, mj) мало, велика вероятность того, что при замене одной из компонент решения mj на k-ю точку, такую, что при L(mi, k)>>L(mi, mj), значение целевой функции для нового решения будет «лучше»:

Если ,

то .

Наша модификация алгоритма на базе МИВЕР сводится к изменению на шагах 2 и 5.

Пусть L0 – максимальное расстояние, при котором выполняются условия гипотез 1 и 2. Тогда, согласно Гипотезе 2, для L*<L0 вероятность

На шаге генерации экземпляров вектора X должно быть учтено ограничение (4). Данное условие выполняется следующей версией алгоритма:

Алгоритм 4. Реализация шага 2 алгоритма на базе МИВЕР согласно Гипотезе 2.

Дано: вектор вероятностей P=(p1,...,pn).

1. ;

2. Для каждого цикл:

2.1. P*=P;

2.2. ; S=0;

2.3. Для каждого цикл:

2.3.1. S=S+p*i;

2.3.2. Если тогда ; j'=j; прервать цикл 2.2;

2.3.3 Конец цикла 2.2;

2.4. Для каждого выполнить ; конец цикла;

2.5. Конец цикла 2;

3. Возврат .

Результатом алгоритма является множество . Соответствующий вектор X может быть получен согласно формуле (3). Здесь Random() - функция, генерирующая случайные значения в интервале [0,1) с равномерным распределением.

Шаг 5 (адаптация вектора вероятностей) на k-й итерации алгоритма на базе МИВЕР выполняется, в соответствии с Гипотезой 1, по формулам

(10)

, (11)

(12)

Здесь ib и iw — ближайшие к i-й вершине такие, что , , где и — те экземпляры сгенерированных множеств индексов входящих в решение вершин , в которых целевая функция принимает лучшее (минимальное) и худшее (максимальное) значения.

Оценки времени выполнения алгоритма (результаты профайлинга) и основной его процедуры — вычисления целевой функции — были произведены для различных задач стандартного тестового набора ORLIB [12]. Использовался кластер с 4-ядерными узлами Xeon X5GHz, 12Gb RAM на каждом узле, HyperThreading отключен, компилятор GNU Fortran + OpenMPI, сеть MiryNet.

Параллельная работа алгоритма на 4 ядрах единственного узла для задач pmed22, pmed32, pmed39 показывает параллельную эффективность 63-91%, которая растет с ростом размерности задач.

Использование метода изменяющихся вероятностей при решении дискретных задач размещения показывает высокую эффективность, в том числе при использовании высокопроизводительных вычислительных мощностей.

Литература

1. Suntum, U. van, Die Thünen’schen Ringe. In: Wirtschaftswissenschaftliches Studium (WiSt), 9. Jg., Heft 8 (August 1980), p. 383

2. Hakimi S. L. Optimum locations of switching centers and the absolute centers and medians of a graph / Operations Research, May/June 1964, 12(3), pp. 450-459

3. , Казаковцев случайного поиска для обобщенной задачи Вебера в дискретных координатах / Информатика и системы управления, 2013, Вып. 1, cтр. 87–98.

4. Kazakovtzev L. A. Adaptation probability changing method for Weber problem with an arbitrary metric // Facta universitatis (NIS), Ser. Math. Inform. Vol. 27 No 2 (2012), pp. 239-254

5. , Сараев изменяющихся вероятностей / Проблемы случайного поиска, Рига: Зинатне, 1988, вып. 11, стр. 26–34.

6. Alp O., Erkut E. and Drezner Z. An Efficient Genetic Algorithm for the p-Median Problem / Annals of Operations Research, 2003, Vol. 122, Issue 1–4, pp. 21–42.

7. Antamoshkin A. Brainware for Searchal Pseudoboolean Optimization / Tr. оf Tenth Prague Conf. on Inf. Theory, Stat. Dec. Functions, Random Processes / Prague: Academia, 1987, Vol. 10A-B, pp. 203-206.

8. , , Сумароков генетических алгоритмов и алгоритмов схемы МИВЕР / Электронный журнал ”Исследовано в России”, 2004, том 7, стр. 1658–1665. URL: http://zhurnal. ape. *****/articles/2004/153.pdf.

9. , Ступина Реализация Метода Изменяющихся Вероятностей / Современные проблемы науки и образования, 2012, № 4, URL: www. *****/.

10. Казаковцев алгоритм случайного поиска с адаптацией для систем с распределенной памятью / Системы управления и информационные технологии, 2012, №3 (49), стр.11-15.

11. , , Кириллов выбора оптимального размещения элементов беспроводной сети // Современные проблемы науки и образования. – 2013. – № 3; 
URL: www. *****/.

12. Beasley J. E. OR-Library: distributing test problems by electronic mail / Journal of the Operational Research Society, 1990, vol.41, no.11, pp.