Software & Systems

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

Стратегия применения метода заключается в управлении шириной поиска на дереве решений с помощью выбора порога функции оценки глобального решения и глубиной поиска, которая не должна превышать величину веса наилучшего текущего решения.

Область применения метода ограничивается недетерминированными полиномиальными полными задачами потребления ресурсов произвольной природы, допускающими приближенное решение. К таковым относятся задачи оптимизации пути коммивояжера, раскроя-упаковки и нестинга, размещения обслуживающих центров, поиска оптимального подмножества заданного множества и т.п. [1].

В общем случае исходные данные описываются в виде графов без петель и кратных ребер G=(V, E, d), где V – множество вершин-ресурсов vi произвольной природы, |V|=n; каждая вершина vi характеризуется вектором параметров ресурсов Pi=(p1, p2,…, pd), определенных на множестве ℝ+, piÎℝ+; d – размерность ресурсов, определенная на множестве ℤ+; E – множество ребер eij, задающих отношение смежности произвольной природы между вершинами vi и vj, eij=eji, i¹j, .

Дерево решений

Потребление ресурсов заключается в пошаговом исключении из графа G выбираемых по определенному критерию ресурсов и в формировании на их основе цепи p(n,k)=[v1, v2, …, vk], k – длина цепи [1]. Дерево решений задается множеством ветвей Pn,k, каждая из которых является цепью p(n,k) на графе G: Pn,k={p(n,k) | 0

Так как степень вершин на каждом шаге решения уменьшается на единицу, количество всех цепей p(n,k) равно

что обусловливает факториальный рост сложности NPC-задач потребления невозобновляемых ресурсов.

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

Определим вес вершины v графа G функцией , а вес цепи , где w(ei,i+1) – вес ребра. Задача состоит в нахождении подмножества субоптимальных решений , которое содержит только те цепи , у которых наибольшая вероятность того, что их вес h(p*) минимален во всем множестве Pn,k:

, где .

Ранжированные цепи

Построение функции оценки веса цепи предлагается проводить для ранжированных цепей p(n, k)=(r1, r2,…, ri,…, rk), то есть тех цепей, у которых все вершины заменены их рангами.

Для введения метрики в пространство поиска определена количественная характеристика произвольной ранжированной цепи pm(n, k) с фиксированной длиной k – ее уникальный целочисленный номер m в факториальной системе счисления (ФСС): .

По номеру m цепи pm(n, k) взаимно-од­нозначно восстанавливаются ранги локальных решений (r1, r2,…, ri,…, rk).

Например, ранжированная цепь, удовлетворяющая принципу оптимальности Беллмана, содержит только нулевые значения рангов p0(n, k)= =(01, 02, …, 0k) и ее номер в ФСС m=0. Такая цепь является глобальным оптимумом, так как имеет наибольшую среди прочих цепей вероятность того, что вес этой цепи оптимален.

Функция оценки веса ранжированной цепи

На каждом шаге решения приращение Dhi= =w(ei,i+1)+q(vi+1) увеличивает вес цепи h(pi+1)= =h(pi)+Dhi. Рассмотрим приведенную к интервалу ]0, 1] функцию оценки веса цепи f(pi+1)=f(pi)+Dfi и зависимость приращения оценки Dfi от величины ранга ri+1 и номера текущего шага i.

Так как на каждом шаге решения присоединяемая к цепи вершина удаляется из графа исходных данных вместе с инцидентными ей ребрами, на i-м шаге решения оценка приращения Dfi может принимать одно из n‑i значений. Нахождение функции оценки веса ранжированной цепи опирается на два постулата, принятые для произвольного i-го шага решения.

1.   Все n-i возможных оценок приращений Dfi лежат в интервале [Dfmin, 1] с шагом Dfmin, где .

2.   Оценка приращения веса прямо пропорциональна рангу ri локального решения и обратно пропорциональна числу возможных приращений n‑i.

Согласно принятым постулатам найдем оценку приращения веса в виде

                                             (1)

с граничными условиями для минимального rmin=0 и максимального rmax=n‑i рангов

                                                 (2)

Как видно из (2), приращения оценок при rmin представляют собой гармонический ряд. Приращения оценок при rmax равны единице. Подставляя (1) в (2), легко найти значения коэффициентов А=1 и В=1. Таким образом, приведенная функция приращений весовой функции принимает вид

,

а оценка весовой функции является суммой k оценок приращений Dfi:

.                                         (3)

На рисунке 1 приведены средние веса двадцати четырех цепей hm(p(5, 6)) и их оценка fm(p(5, 6)), полученные при решении полным перебором задачи коммивояжера на полном графе, генерируемом 100 тысяч раз со случайными весами ребер в интервале 0

Кроме этого, на рисунке 1 показана аппроксимация веса hm на основе экспоненциального приближения  оценки fm к весу hm по критерию минимума среднего квадратичного отклонения, s = 0,014 при А=0,77, В= –0,0059, С=0,078.

Построение ранжированной окрестности глобального оптимума

Предлагаемый метод является вариантом метода ветвей и границ для случая ранжированного пространства поиска и установленной функции оценки веса ранжированной цепи (3). Суть метода заключается в построении окрестности  глобального оптимума (ОГО), содержащей в лексикографическом порядке только те цепи p(n,k), оценка веса которых не превышает априорно заданного порога f0(p(n, k))   в задачах минимизации. В задачах максимизации веса цепей ОГО не ниже априорно заданного порога. Лексикографический порядок минимизирует вычислительные затраты при построении окрестности.

Величина порога f0(p(n, k)) находится в интервале

     (4)

и может быть задана двумя способами:

·     оценкой веса m-й цепи f(pm), тогда ОГО будет содержать только те цепи, оценка веса которых не выше оценки веса цепи f(pm);

·     оценкой веса f0, при которой ОГО будет включать точно заданное количество проверяемых субоптимальных цепей, оценка веса которых не выше f0.

Точное нижнее значение порога fmin(p(n, k)) из (4) определяется как сумма гармонического ряда на интервале от  до : , где  – логарифмическая производная гамма-функции [2]. Точное верхнее значение порога fmax(p(n, k))=k.

Для полной цепи p(n, n) точное нижнее значение порога определяется как сумма гармонического ряда от 1 до : , где C – постоянная Эйлера–Маскерони.

С целью повышения эффективности программной реализации оценки нижнего значения порога можно вычислять приближенно:

, .

Для реализации предлагаемого метода необходимо указать конкретное значение порога  в зависимости от значений n, k, а также требуемого количества проверяемых цепей. Для этого порог представляется в виде суммы его минимального значения и приращения:

,                                (5)

где Df0 определяется отношением разности максимального и минимального значений порога к общему количеству решений |Пn,k|:

.

Умножая среднее приращение порога на величину q‑1, получим оценку величины порога для известного количества q проверяемых цепей:

Величина q уменьшена на единицу, так как первое слагаемое в формуле (5) представляет собой проверку одного варианта – глобального оптимума. При известной доле  проверяемых цепей оценка величины порога имеет вид f0(p(n,k))=d×k+(1-d)×y(n+1)+(d-1)×y(n- -k+1).

С целью повышения эффективности про­граммной реализации приближенная оценка величины порога от известного значения q имеет вид

и от известной доли d:

.

На рисунке 2 приведена ОГО  в задаче коммивояжера на полном пятивершинном графе. ОГО ограничена порогом, заданным оценкой веса 18-й цепи f18. Цепи окрестности ={0, 1, 2, 4, 6, 7, 8, 12, 18} выделены круглыми маркерами. Данные цепи pi(5, 6) являются прообразами оценок fi(p(5, 6)), не превосходящих указанный порог f18 и отмеченных квадратными маркерами.

В окрестность  вошло множество цепей {4, 7}, не являющихся субоптимальными по отношению к весу f18, так как их веса больше веса f18. Эти цепи отмечены незакрашенными круглыми маркерами, а их оценки – незакрашенными квадратными маркерами. Таким образом, окрестность  распадается на множество цепей {0, 1, 2, 6, 8, 12, 18}, которые находятся в пределах величины e-окрестности глобального оптимума, определяемой порогом e=h18, а также на множество цепей {4, 7}, находящихся в пределах изменяемого параметра x=max(h4, h7)‑h18.

На рисунке 3 изображено полное дерево поиска решений в описанной задаче коммивояжера, которое содержит 4! решений. Сплошными линиями выделена ОГО. Ребра помечены рангами локальных решений. Вершины дерева содержат номер шага решения. Листья дерева снизу подписаны номерами m цепей pm(5, 6) в ФСС. Самая левая ветвь поддерева является цепью глобального оптимума, она построена по принципу оптимальности Беллмана – содержит только нулевые ранги.

Предварительное ранжирование локальных решений для каждой вершины исходного графа и лексикографический порядок проверки всех цепей ОГО позволяют сократить вычислительные затраты, так как для получения новой цепи достаточно заменить в текущей цепи последние вершины на вершины с очередным рангом, удовлетворяющим неравенству (4), а не строить всю цепь заново.

Оценка эффективности метода построения ОГО

На рисунке 4 приведены результаты сравнительных испытаний предлагаемого метода, оценивающего q решений, q=n, 5n, 10n, и методов Шермана–Рейтера и Лина [3] при поиске цепи p(n, n+1) минимального веса в задаче коммивояжера, n – число вершин исходного графа. Для всех n=20, 30, …, 120 задача решалась 10 тысяч раз каждым алгоритмом. Нижняя теоретическая оценка вычислялась в виде суммы минимальных весов ребер, каждое из которых инцидентно каждой вершине исходного графа.

На рисунке 5 приведены результаты сравнительных испытаний предлагаемого метода построения ОГО при q=n, 5n, 10n и эволюционного метода (генетического алгоритма – ГА) при поиске цепи p(n, n+1) минимального веса с вышеуказанными условиями задачи коммивояжера.

В основу используемого ГА положены следующие правила. Алгоритм инициализировался путем построения популяции здоровых хромосом, которые являются участками цепи, представляющей собой статистический глобальный оптимум. Роль генетических операторов выполняли операторы перекрестного скрещивания участков двух и более хромосом между собой. Хромосомы с наименьшим весом относительно своей длины составляли элиту и подвергались мутации с меньшей вероятностью, чем хромосомы с большим относительным весом. Каждое поколение содержало набор здоровых хромосом, представляющих собой правильную цепь p(n, n+1) того или иного веса h(p(n, n+1)). Такой эпистазис дал возможность просматривать текущее решение в произвольный момент без остановки ГА. Продолжительность работы ГА определялась временем работы предлагаемого алгоритма построения ОГО, оценивающего q решений, q=n, 5n, 10n, n – число вершин исходного графа. Таким образом, для каждого n=20, 30, …, 120 ГА возвращал три решения в моменты получения q решений, q=n, 5n, 10n, алгоритмом построения ранжированной ОГО.

На основании изложенного можно сделать следующие выводы. Предложенный метод построения окрестности глобального оптимума NPC-задач на ранжированном дереве поиска решений превосходит быстрые эвристики Шермана–Рейтера и Лина и известные методы ИИ по точности решения и может применяться как самостоятельный инструмент при решении NPC-задач.

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

Литература

1. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб: БХВ-Петербург, 2003. 1104 с.

2. Корн Г., Корн Т. Справочник по математике. Определения, теоремы, формулы. СПб: Изд-во «Лань», 2003. 832 с.

3. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность; пер. с англ. М.: Мир, 1985.

4. Макконелл Дж. Основы современных алгоритмов; пер. с англ. М.: Техносфера, 2004. 368 с.