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

Размещено на http://www.allbest.ru/

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

Задача дискретной оптимизации расходования невозобновляемых ресурсов представлена в виде задачи поиска минимума целевой функции ранжированных цепей на полном графе [1] состояний NP-системы [2] в окрестности статистического оптимума, - ранг перехода из i-го состояния, j - номер цепи, имеющий в факториальной системе счисления разряды . Статистический оптимум является решением Беллмана и выражается цепью с нулевыми рангами переходов NP-системы системы , то есть, наилучшее локальное решение реализуется переходом с рангом 0, а глобальное решение содержит только наилучшие локальные решения. V - множество состояний NP-системы, , n - количество ресурсов для потребления, E - множество взвешенных на области переходов состояний NP-системы, - вес перехода из состояния i в состояние j, , k - количество потреблённых ресурсов, [3].

Для управления дискретной NP-системой используются ранги локальных переходов , значения которых задаются эвристической функцией, построенной в соответствии с закономерностями распределения оптимальных решений, . Количество цепей на графе переходов равно числу вариантов потребления k единиц ресурсов из заданных n ресурсов и определяется отношением .

1. Окрестность статистического оптимума

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

.

Величина является шириной окрестности. На рисунке 1 изображён пример _окрестности статистического оптимума для экспериментальной функции вероятности оптимальных цепей для и . На оси абсцисс отложены все 24 цепи от беллмановского решения до цепи . Окрестность субоптимальных решений включает цепи с номерами .

дискретный оптимизация геометрический ресурс

2. Типы эвристик построения окрестностей статистического оптимума

Эвристики порождают отображение , при котором для двух цепей , имеет место либо при , либо при . Такие эвристики порождают из элементов исходного множества цепей такое упорядоченное множество [25, 68], что вероятности монотонно убывают

.

Достоинства:

малые вычислительные затраты на этапе решения прикладной задачи,

реализация оптимального по убыванию вероятности поиска.

Недостаток: сложность формализации эвристики.

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

Недостаток: реализация субоптимального по убыванию вероятности поиска.

Достоинство: относительная лёгкость формализации.

3. Вероятностный метод построения окрестности статистического оптимума

На данный момент не существует методов построения точной окрестности статистического оптимума ввиду сложности построения эвристики , априорно оценивающих величину по рангам цепи . В настоящем исследовании рассматривается эвристика типа .

Полученные в ходе статистических испытаний характеристики случайной функции значений рангов в каждом i-м переходе состояний NP-системы позволяют задавать закон генерации величин рангов посредством датчиков псевдослучайных чисел с геометрической функцией вероятности . Для поиска субоптимальных цепей предлагается реализовать генератор рангов переходов состояний NP-системы в виде k параллельно работающих генераторов псевдослучайных чисел (ГПСЧ). На рисунке 2 представлена структурная схема генератора рангов. Величины рангов каждого перехода состояний выставляются на выходах генераторов псевдослучайных чисел в соответствии с функцией генератора . На входы ГПСЧ подаётся сигнал «Разрешение», тактирующий работу всей системы, а также параметры цепи n и k.

Для того чтобы задать параметр геометрического распределения для каждого ГПСЧ необходимо определить закон изменения величины от параметров n, k, i на основе экспериментальных данных, полученных в ходе работы NP-системы по методу грубой силы.

Вспомогательный алгоритм

Рассмотрим алгоритм определения функции для случая нахождения оптимальной цепи . Параметр геометрического распределения ГПСЧ для каждого i-го разряда цепи представим функцией .

1. Для определения данной функции необходимо построить аппроксимирующие функции

(1)

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

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

Таблица 1 - Параметры аппроксимирующих экспонент

2. Рассматривая столбцы , , в качестве исходных данных построить экстраполирующие функции. На рисунке 3 изображены графики экстраполяции параметров экспоненциальной функции (1).

Функция (1) аппроксимирует параметр ? геометрического распределения значений рангов переходов NP-системы для оптимизации цепи (6, 6).

Таким образом, псевдослучайная функция генерации рангов i-х переходов NP-системы аппроксимируется функцией (1), где

3. Построить композицию функций на диапазоне

.

4. Конец алгоритма.

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

Это обосновывается тем, что для геометрического распределения характерно приближённое равенство .

Определение параметра для цепи произвольной длины включает дополнительный шаг - фиксацию переменной k при поиске параметров , , .

Алгоритм нахождения параметра

1. Для каждого значения n из анализируемого диапазона, например из , при фиксированном значении найти функции

рассмотренным выше вспомогательным алгоритмом.

2. Повторив пункт 1 для всех получить семейство k уравнений

3. Найти закон изменения для каждого из семейств параметров , , , , , путём построения экстраполирующих функций , , , , , , где , , , , , - векторы вспомогательных параметров.

4. Путём замены аргументов , , , , , на аргумент k построить из композиции функций

композицию

(2)

5. Конец алгоритма.

4. Структура генератора рангов переходов

Для упрощённой реализации генератора рангов достаточно использовать один генератор псевдослучайных чисел (рис. 4).

При наличии сигнала «Разрешение» k рангов выставляются на выходах буферного регистра через k тактов работы внутренней схемы тактирования. Схема тактирования может быть выполнена в виде счётчика, работающего в диапазоне . Данный счётчик инициируется сигналом «Разрешение». ГПСЧ по входным данным n, k, i генерирует псевдослучайное число , удовлетворяющее заданному закону распределения вероятностей (2). Такая схема замедляет работу NP-системы, но уменьшает аппаратные затраты, и делает возможной программную реализацию на непараллельной вычислительной технике.

Достоинства вероятностного метода:

Отсутствие притяжения к локальным оптимумам.

Большой объём поиска.

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

Возможность останова либо по времени, либо по заданному объёму поиска, либо при достижении заданного порога веса решения.

Возможность повторного запуска алгоритма.

Недостатки вероятностного метода:

Повтор наиболее вероятных субоптимальных решений.

Эффективность решения пропорциональна времени работы алгоритма.

5. Эксперимент

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

В качестве показателя оценки эффективности выбрано среднее за N опытов отношение минимального веса цепи к весу i-й цепи . Веса рёбер полного графа генерировались случайным образом для каждого опыта. На рисунке 5 приведены результаты сравнения, которые позволяют сделать вывод о том, что различия наблюдаются при малом числе запусков вероятностных алгоритмов. С ростом числа запусков, а также с ростом размерности задачи n различия уменьшаются. Это объясняется малым значением разности между средним квадратичным отклонением геометрического и экспоненциального распределений от экспериментального распределения вероятностей.

Выводы

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

Исследование выполняется в рамках гранта Российского гуманитарного научного фонда «Управление эффективностью пространственно распределённых промышленных предприятий с учётом фактора надёжности на примере нефтегазодобывающего комплекса» проект № 14-02-00334а.

Список литературы

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

2. Марков В.Н. Математические основы построения дискретного автомата оптимизации параметров системы // Политематический сетевой электронный научный журнал кубанского государственного аграрного университета. - 2014. - № 103. - С. 37-49.

4. Марков В.Н. Способ порождения эвристик для решения NP-трудных задач // Информационные технологии. 2006. №6. с. 21-25.

Размещено на Allbest.ru