Journal influence
Bookmark
Next issue
Method of construction of a neighbourhood of a global optimum of NPC-problems on the ranked tree of searching of solutions
The article was published in issue no. № 1, 2010Abstract:The method of construction of a neighbourhood of a global optimum as ranked subtree which contains only suboptimal solutions of NPC-problems is considered in paper. Function of an estimation of weight of the ranked solution which describes statistically the detected regularities of distribution of the ranked solutions is put in a basis of an offered method.
Аннотация:Рассматривается метод построения окрестности глобального оптимума в виде ранжированного поддерева, содержащего только субоптимальные решения NPC-задач. В основу предлагаемого метода положена функция оценки веса ранжированного решения, описывающая статистически выявленные закономерности распределения ранжированных решений.
Authors: (vlasenko@kubstu.ru) - , Ph.D, (vinitar@yandex.ru) - , | |
Keywords: NPC-problems, ranked subtree, the neighbourhood of a global optimum |
|
Page views: 8509 |
Print version Full issue in PDF (4.03Mb) Download the cover in PDF (1.25Мб) |
Суть описываемого метода заключается в построении ранжированного поддерева поиска решения посредством выбора на каждом шаге только тех локальных решений, при которых функция оценки веса глобального решения от рангов локальных решений не превышает заданный порог. Стратегия применения метода заключается в управлении шириной поиска на дереве решений с помощью выбора порога функции оценки глобального решения и глубиной поиска, которая не должна превышать величину веса наилучшего текущего решения. Область применения метода ограничивается недетерминированными полиномиальными полными задачами потребления ресурсов произвольной природы, допускающими приближенное решение. К таковым относятся задачи оптимизации пути коммивояжера, раскроя-упаковки и нестинга, размещения обслуживающих центров, поиска оптимального подмножества заданного множества и т.п. [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 функцией
Ранжированные цепи Построение функции оценки веса цепи предлагается проводить для ранжированных цепей 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. Согласно принятым постулатам найдем оценку приращения веса в виде
с граничными условиями для минимального rmin=0 и максимального rmax=n‑i рангов
Как видно из (2), приращения оценок при rmin представляют собой гармонический ряд. Приращения оценок при rmax равны единице. Подставляя (1) в (2), легко найти значения коэффициентов А=1 и В=1. Таким образом, приведенная функция приращений весовой функции принимает вид
а оценка весовой функции является суммой k оценок приращений Dfi:
На рисунке 1 приведены средние веса двадцати четырех цепей hm(p(5, 6)) и их оценка fm(p(5, 6)), полученные при решении полным перебором задачи коммивояжера на полном графе, генерируемом 100 тысяч раз со случайными весами ребер в интервале 0 Кроме этого, на рисунке 1 показана аппроксимация веса hm на основе экспоненциального приближения Построение ранжированной окрестности глобального оптимума Предлагаемый метод является вариантом метода ветвей и границ для случая ранжированного пространства поиска и установленной функции оценки веса ранжированной цепи (3). Суть метода заключается в построении окрестности Величина порога f0(p(n, k)) находится в интервале
и может быть задана двумя способами: · оценкой веса m-й цепи f(pm), тогда ОГО будет содержать только те цепи, оценка веса которых не выше оценки веса цепи f(pm); · оценкой веса f0, при которой ОГО будет включать точно заданное количество проверяемых субоптимальных цепей, оценка веса которых не выше f0. Точное нижнее значение порога fmin(p(n, k)) из (4) определяется как сумма гармонического ряда на интервале от Для полной цепи p(n, n) точное нижнее значение порога определяется как сумма гармонического ряда от 1 до С целью повышения эффективности программной реализации оценки нижнего значения порога можно вычислять приближенно:
Для реализации предлагаемого метода необходимо указать конкретное значение порога
где Df0 определяется отношением разности максимального и минимального значений порога к общему количеству решений |Пn,k|:
Умножая среднее приращение порога на величину q‑1, получим оценку величины порога для известного количества q проверяемых цепей:
С целью повышения эффективности программной реализации приближенная оценка величины порога от известного значения q имеет вид и от известной доли d:
В окрестность На рисунке 3 изображено полное дерево поиска решений в описанной задаче коммивояжера, которое содержит 4! решений. Сплошными линиями выделена ОГО. Ребра помечены рангами локальных решений. Вершины дерева содержат номер шага решения. Листья дерева снизу подписаны номерами m цепей pm(5, 6) в ФСС. Самая левая ветвь поддерева является цепью глобального оптимума, она построена по принципу оптимальности Беллмана – содержит только нулевые ранги.
Оценка эффективности метода построения ОГО На рисунке 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) минимального веса с вышеуказанными условиями задачи коммивояжера.
На основании изложенного можно сделать следующие выводы. Предложенный метод построения окрестности глобального оптимума NPC-задач на ранжированном дереве поиска решений превосходит быстрые эвристики Шермана–Рейтера и Лина и известные методы ИИ по точности решения и может применяться как самостоятельный инструмент при решении NPC-задач. Достоинством предлагаемого метода является постепенное улучшение текущего субоптимального решения, что позволяет завершать поиск либо по времени, либо по количеству/доле просмотренных цепей, либо по достижении заданного порога весовой функции, либо по завершении построения окрестности глобального оптимума. Недостатком метода являются дополнительные вычислительные затраты, обусловленные ранжированием локальных решений для каждой вершины исходного графа и использованием экспертно задаваемого порога оценки веса глобального решения. Литература 1. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб: БХВ-Петербург, 2003. 1104 с. 2. Корн Г., Корн Т. Справочник по математике. Определения, теоремы, формулы. СПб: Изд-во «Лань», 2003. 832 с. 3. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность; пер. с англ. М.: Мир, 1985. 4. Макконелл Дж. Основы современных алгоритмов; пер. с англ. М.: Техносфера, 2004. 368 с. |
Permanent link: http://swsys.ru/index.php?id=2415&lang=en&page=article |
Print version Full issue in PDF (4.03Mb) Download the cover in PDF (1.25Мб) |
The article was published in issue no. № 1, 2010 |
Back to the list of articles