ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2015, № 1, с. 72-78
КОМПЬЮТЕРНЫЕ ^^^^^^^^^^^^^^ МЕТОДЫ
УДК 519.144.1+519.16
ГИПОТЕЗА О "БОЛЬШОЙ ДОЛИНЕ" ДЛЯ ПОТОКОВОЙ ЗАДАЧИ ШТЕЙНЕРА
© 2015 г. В. Д. Кукин
Петрозаводск, ИПМИ КарНЦ РАН Поступила в редакцию 06.05.14 г., после доработки 15.09.14 г.
Для потоковой задачи Штейнера ландшафт "большой долины" представлен как объединение субструктур с общими свойствами. Приводится определение субструктуры и рассматривается ее реализация в эволюционном алгоритме для этой задачи.
DOI: 10.7868/S0002338815010096
Введение. Статья завершает обсуждение эволюционного метода поиска глобального экстремума в потоковой задаче Штейнера, представленного в настоящем журнале в [1, 2]. Эта задача, одно из обобщений проблемы Штейнера [3], рассматривается для транспортной сети с одним стоком, множеством источников с заданными мощностями (запасами продукта), неограниченными пропускными способностями и балансом объемов перевозки продукта (потоков) в точках ветвления сети. Предполагается, что затраты на строительство и перевозки на участках сети зависят от максимальной величины потоков на них. Требуется построить сеть с минимальными суммарными затратами на ее строительство и транспортировку продукта.
Модель транспортной сети — ориентированное корневое дерево. Множество его вершин включает два подмножества. Во-первых, заданные на евклидовой плоскости терминальные вершины, в том числе выделенную вершину — корень дерева. Число терминальных вершин считают размерностью задачи. Во-вторых, дополнительные свободно размещаемые вершины.
С этой задачей связаны следующие понятия, определенные в статье [3]. Свободно размещаемые вершины называются точками Штейнера (ТШ). Под топологией дерева понимают структуру данных, которая указывает пары вершин, связанные дугами. Множество всех топологий дерева определяется множеством значений выбранного отображения инцидентности между вершинами и дугами дерева. Дерево однозначно задается координатами ТШ и топологией. Дерево Штейнера (ДШ) — дерево с оптимальными координатами точек Штейнера для данной топологии. Минимальное дерево Штейнера (МДШ) — минимальное ДШ на множестве всех топологий для заданного множества терминальных вершин. В случае подмножеств топологий, которые могут появиться далее, будем говорить о локально минимальном ДШ (ЛМДШ).
Для поиска ДШ мы применяли методы случайного поиска экстремума многопараметрической функции. Тогда задача дискретно-непрерывной оптимизации сводится к NP-трудной комбинаторной задаче поиска топологии [4]. Для ее решения разработаны [1, 2]: способ представления топологии и принцип ее кодирования / декодирования; эвристические генетические операторы; эволюционная модель; композитный эволюционный алгоритм (ЭА). Проведены эксперименты: для евклидовой задачи Штейнера — на сериях тестов из OR-Library [5]; для потоковой задачи — на сериях тестов этой библиотеки, адаптированных к этой задаче. Эксперименты подтвердили высокую эффективность ЭА по сравнению с генетическим алгоритмом (ГА).
Потоковая задача Штейнера имеет множество локальных минимумов, анализ распределения которых связан с понятием ландшафта полезности [6]. Впервые такой анализ был проведен для симметричной задачи коммивояжера [7]. Он выявил сильную корреляцию между значениями целевой функции и расстояниями между локальными минимумами (fitness-distance correlation). Это позволило авторам предположить, что ландшафт полезности задачи образует выпуклую структуру с центральным глобальным минимумом, которую назвали "большой долиной" ("big valley"). Позже она была выявлена у некоторых других задач.
Развитию гипотезы о "большой долине" способствовали дальнейшие исследования ландшафта полезности многопараметрических задач. В качестве прецедента сошлемся на задачу планирования работ. В [8] ее ландшафт представлен как UV-структура, которую образуют: u-valleys — мелкие широкие долины и v-valley — глубокая изогнутая долина с глобальным мини-
мумом. В [9] отмечено, что число долин зависит от соотношения между числом работ и машин; дано также определение ландшафта "большой долины" и указаны необходимые условия его существования: 1) малые улучшающие переходы; 2) кластеризация оптимальных решений.
В данной статье приводятся результаты исследований ландшафта полезности для потоковой задачи Штейнера. Гипотеза о "большой долине" представляет ландшафт как объединение субструктур, образованных множествами ДШ с общими прикорневыми поддеревьями и близкими значениями целевой функции. Показано, что существование такой "большой долины" влияет на эффективность эволюционного алгоритма, разработанного для решения этой задачи [1].
Раздел 1 статьи содержит постановку потоковой задачи Штейнера и основы метода ее решения. Формулировка гипотезы о "большой долине" дана в разд. 2. Особенности реализации ЭА и ландшафт полезности задачи обсуждаются в разд. 3 и 4. Вычислительные эксперименты, показывающие влияние этой гипотезы на эффективность ЭА, приведены в разд. 5.
1. Постановка задачи и эвристические основы метода. 1.1. Математическая модель. Пусть A = (V, D, I) - ориентированное корневое дерево, где V — множество его вершин; D = = {(i, j)\i, j g V} — множество дуг; I: Vх V^ D - отображение инцидентности, определяющее множество Tтопологий дерева. Множество V = V0 U Vs и V0 | Vs = 0, где V0 — подмножество терминальных вершин, i0 g V0 — корень дерева (сток); Vs — подмножество ТШ. Мощность множества IV = \ V0\ + \ Vs\ = n + s, 0 < s < n - 2 [3], где n — число терминальных вершин, s — число ТШ.
Терминальным вершинам из V0 сопоставим: мощности источников M0 = {mi g R + |i g V0\{i0}}; координаты их размещения на евклидовой плоскости X0 = {(xi, y) xi, yi g R + ; i g V0}. Введем переменные: (т, Xs) g Tх R2, где т g T - топология дерева; Xs = {(x;, y,)Xi, yi g R + , i g Vs} — координаты ТШ.
Определим на дугах: евклидову метрику l: D ^ R + U {0}; функцию распределения потоков q: D ^ R+; кусочно-постоянные функции от величины потока: k(q): D ^ R + — удельные капитальные затраты и c(q): D ^ R + — удельные транспортные затраты на единицу потока.
Выбор топологии т g T однозначно определяет на дуге (i, j) g Dt величину потока q^, j) и затраты, отнесенные к единице длины дуги, k^,j + С(,,^q^,¡у Это выражение задает значение весовой функции, которое называют весом дуги. Транспортной сети соответствует положительная вогнутая весовая функция. Длина дуги (i, j) равна l(j = ((x; — xy)2 + ((yi — y-)2)1/2. Взвешенной длиной дуги назовем величину (k^ + c^q-,У))1(,-,У). Целевая функция S(A) задачи — это сумма взвешенных длин дуг дерева A. Задача состоит в том, чтобы найти дерево минимальной стоимости с весами, зависящими от потоков. В зарубежной литературе эту задачу иногда называют the Gilbert—Steiner Arborescence problem. Модель решаемой задачи имеет вид
S(A) = Z (kj + c<-u)q(''j)) l{i'j) ^ min ;
(i, j) E DT, Xs (T> Xs)E T x rR
Не нарушая общности, будем рассматривать деревья только с полными топологиями, т.е. с максимальным числом ТШ: s = n — 2 [3]. Вырожденные дуги (нулевой длины), которые появляются при оптимизации координат ТШ, считаем полноправными элементами дерева. Далее предполагаем, что T - множество всех полных топологий дерева и размерность задачи n > 3.
1.2. Представление топологии и эвристики. Пусть вершины дерева помечены натуральными числами: подмножество {1, 2, ... n} — метки терминальных вершин, метка корня всегда 1; {n + 1, n + 2, ... 2n — 2} — метки ТШ. Используя аналог кода Прюфера для ориентированного дерева [2], представим топологию т g T строкой длины 2n — 2:
т = (t1, t2, ■■, tn - 1, tn, tn + 1, — t2n - 4, t2n - 3, t2n - 2),
где ti - попарно одинаковые метки из {n + 1, n + 2, ... 2n - 2}, i = 2, ... 2n - 3. Фиксированные метки: фиктивной вершины t1 = 0 и корня дерева t2n - 2 = 1. Дополнительно зафиксируем предпоследний элемент топологии - метку последней ТШ: t2n - 3 = 2n - 2.
Назовем прародителем A0 дерево с полной топологией вида:
т0 = (0, n + 1, n + 1, n + 2, n + 2, — m, m, — 2n - 2, 2n - 2, 1).
Опираясь на представление топологий, примем следующий принцип их кодирования. Устанавливаем взаимно однозначное соответствие между элементами строки т0 и начальной перестановкой {1, 2, ... 2n - 2}. Новые топологии генерируем с помощью перестановок и последующего декодирования. Так как три элемента строки зафиксированы, число всех перестановок составляет (2n - 5)!. После декодирования многие из них дают представления топологий изоморфных дере-
Рис. 1. Углы, образованные дугами с весами Ю1, Ю2, ®3 > 0
вьев с точностью до перенумерации ТШ. Число неповторяющихся топологий составляет (2п — 5)!!. В свое время автору удалось создать алгоритм исчерпывающего и неизбыточного перебора таких топологий [10]. Начиная с т0, он генерирует все (2п — 5)!! топологий и позволяет последовательно получить все ДШ и найти порядковый номер топологии МДШ.
Разработанный автором ЭА использует генетические операторы, основанные на наглядных и эффективных эвристиках [1, 2]. Первая эвристика состоит в том, что случайно выбранные концевые дуги в дереве попарно обмениваются своими конечными вершинами. Это самая простая операция, и она дает только допустимые топологии. Вторая эвристика — такая переброска дуги в дереве, при которой ее конечная вершина перемещается на середину одной из ближайших дуг. Операция может давать контуры в дереве, поэтому необходима проверка допустимости топологии. Третья эвристика — замена топологии в выделенном поддереве.
2. Гипотеза о "большой долине". Из-за оптимизации координат ТШ деревья Штейнера имеют много вырожденных дуг. Как в евклидовой, так и в потоковой задаче вырождение дуг может быть следствием взаимного расположения вершин ДШ на плоскости. В потоковой задаче это происходит также из-за суммирования потоков на дугах. Рассмотрим произвольную ТШ и смежные с ней вершины А1, А2, А3 (рис. 1). Пусть дуги из А2 и А3 входят в ТШШ^ а исходящая из нее дуга входит вА1. Веса дуг юъ ю2, ю3 > 0. В [11] получена формула для углов между дугами, инцидентными ТШ. Для угла а1, лежащего против исходящей ду
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.