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

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

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

Марков В.Н.

Введение

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

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

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

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

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

1. Параметры системы

В общем случае дискретные значения параметров системы представляются в виде простых графов, то есть графов без петель и кратных рёбер. Каждый граф задаётся двойкой G = (V, E), где V - множество параметров vi произвольной природы, |V| = n. E - множество рёбер eij, задающих отношение смежности произвольной природы между значениями параметров vi и vj, eij = eji, i j. Множество E определено на множестве ?+ и его мощность

.

Структурные свойства дерева поиска цепей на графе G:

А) Для произвольной цепи

(n,k) = [v1, v2, …,vi, vi+1, …, vk]

степень значения параметра vi на дереве поиска подчиняется рекурсивному определению

deg vi+1 deg vi_1

или в рекуррентном представлении

deg vi n_i+1.

Б) Число листьев дерева

.

В) Количество всех цепей (n,k) определяется выражением

.

2. Алгебра цепей значений параметров

Определим тривиальную алгебру (,), содержащую операции : на носителе

П = {(n,k) | 0 < k n+1}.

Пусть недетерминированная операция:

n,i n,i+1

присоединения параметра v к цепи (n,i) при условии

v (N(vi) \ (n,i))

определена по правилу

(n,i+1) = (n,i) & vi+1,

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

[v1, v2,…, vi] & vi+1 = [v1, v2,…, vi, vi+1].

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

|N(vi) \ (n,i)| > 1 при i < n_1.

Именно данный недетерминизм служит причиной неопределённости функции перехода состояний дискретной системы.

Операция ret: n,i n,i-1 усечения цепи (n,i) определена по правилу

(n,i-1) = ret((n,i)),

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

ret([v1, v2,…, vi-1, vi]) = [v1, v2,…, vi-1].

3. Постановка задачи оптимизации значений параметров

Пусть показатель качества системы описывается каррированной функцией над цепью значений параметров системы

\ max. (1)

и имеется дополнительная функция веса цепи h() значение которой минимизируется

, (2)

где kV, kE - коэффициенты, характеризующие веса вершин и рёбер соответственно, kV 0, kE 0.

4. Определение дискретного автомата

а) Граф переходов состояний автомата

Так как пространство поиска решений является деревом Пn,k, обладающим структурными свойствами, указанными в пункте 2, то граф переходов состояний дискретного автомата представляет собой дерево, обладающее теми же структурными свойствами.

б) Структура дискретной системы

Характерным признаком дискретной NP_полной системы являются k n последовательных преобразований seli, .

На рисунке 1 изображена схема преобразований, реализующих описанные операции.

Рисунок 1 - Структурная схема последовательных преобразований

5. Модель дискретной автоматизации со стековой памятью состояний автомата

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

s(i) = (U(i), (n,i), j),

i - длина цепи,

j - индекс вершины последнего просмотренного потомка - состояния s(i+1), при отсутствии потомков

j = 0. U(i) - состояние графа после исключения i показателей определяется рекуррентным соотношением

U(i) = U\{u1, u2, …, ui-1}

или в рекурсивном виде

U(i) = U(i-1)\{ui-1}.

Означивание одного параметра ui+1 осуществляется операцией присоединения

(n,i+1) = (n,i) & vi+1

и переводом системы из состояния

s(i) = (U(i), (n,i), j)

в состояние

s(i+1) = (U(i+1), (n,i+1), 0).

При этом в стеке сохраняется состояние с модифицированным индексом потомка

s(i) = (U(i), (n,i), i+1).

Такой переход обозначается s(i) s(i+1).

Развязывание параметра ui из цепи (n,i) в граф U осуществляется операцией усечения цепи

(n,i-1) = ret((n,i)),

выталкиванием из стека состояния

s(i1) = (U(i_1), (n,i-1), j)

и переводом системы из состояния s(i) в состояние s(i1) с модифицированным индексом потомка

s(i_1) = (U(i_1), (n,i_1), i).

Такой переход обозначается s(i) s(i_1) или s(i_1) s(i).

Полный граф переходов состояний представляет дерево поиска решений П_задачи, изображённое на рисунке 2. Множество состояний системы разделено на k+1 классов эквивалентностей {(0), (1), …, (i), (i+1), …, (k)}, 0 i k. Отношением эквивалентности является длина цепи i. Назовём класс эквивалентности (i) стратой с номером i или i_й стратой. На рисунке 2-а представлена цепь переходов страт. Каждая страта есть множество вершин, имеющих одинаковую глубину (уровень). Каждая i-я страта (i) описывается двойкой (U(i), n,i) и составляет всё множество

n,i =

возможных цепей (n,i) длины i и взаимосвязанное с ними состояние графа U(i)

.

Рисунок 2 - Полный граф переходов состояний

а) граф переходов состояний ,

б) страты графа переходов (i)

Страты с минимальным и максимальным номерами

,

.

Дискретная система может менять страту состояния путём инкремента или декремента номера страты

(0) (1) … (i) (i+1) … (k).

При переходе

(i) (i+1)

система занимает одно из всех возможных состояний

s(i+1) (i+1),

обусловленное предыдущим состоянием s(i) и присоединяемым параметром ui+1.

При переходе

(i) (i-1)

система возвращается в состояние

s(i_1) (i_1),

определяемое состоянием памяти системы.

Процесс оптимизации системы заключается в переводе системы из состояния

s(0) = (U(0), (n, 0))

в такое состояние

s(k) = (U(k), (n, k)),

при котором цепь (n, k) имеет вес, удовлетворяющий целевой функции 1 и 2.

6. Определение функции детерминированного перехода автомата

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

.

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

(3)

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

оценкой веса i-й цепи , тогда вес этой цепи будет определять ширину ( + )_окрестности глобального оптимума;

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

Точное нижнее значение порога определяется как сумма гармонического ряда на интервале от до

,

где

- логарифмическая производная гамма-функции.

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

,

где C 0,57721 - постоянная Эйлера-Маскерони.

Оценку нижнего значения порога можно вычислять приближённо

,

.

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

, (4)

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

.

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

.

Величина q уменьшена на единицу, так как первое слагаемое в формуле (4) представляет собой проверку одного варианта из окрестности глобального оптимума. При известной доле



проверяемых цепей оценка величины порога имеет вид

.

Приближённая оценка величины порога для известного значения q имеет вид

.

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

.

7. Характеристики вычислительной сложности дискретной оптимизации

Вычислительная сложность F(s) получения произвольной цепи (n,k) лежит в пределах 1 F(s) k. Определим удельные вычислительные затраты алгоритма, как средние затраты для получения одной цепи *(n,k) , в виде отношения количества Ns состояний s(i) системы, в которых она находилась при порождении всех цепей *(n,k) из окрестности глобального оптимума к количеству этих цепей

. (3)

Рассмотрим в качестве исходных данных граф Kn, предполагающий максимальные вычислительные затраты при прочих равных условиях. В случае единственности каждого перехода s(i) s(i+1) и количество Ns минимально

. (4)

Когда каждый переход s(i) s(i+1) совершается заново при получении всех цепей *(n,k) количество Ns максимально

,

и при достигает величины

. (5)

Удельные затраты для Ns min

(6)

и для Ns max

Удельные затраты для Ns min и больших значений k

,

Лемма 1

С ростом k количество состояний системы Ns растёт быстрее, чем .

Доказательство

Рассмотрим предел отношения Ns к

Так как по условию задачи k n, то

Следовательно

Теорема 1

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

.

Доказательство

На основании леммы 1 максимальные вычислительные затраты совершаются при порождении самых длинных цепей k = n, для которых выражение (6) принимает вид

.

Произведём замену переменной j = n-i и пределов суммирования

.

Совершая предельный переход

,

получаем выражение для

.

Следовательно, для конечных величин n

интеллектуальный автоматизированный дискретный вычислительный

Выводы

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

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

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

1. Хопкрофт Д.Э., Мотвани Р., Ульман Д.Д. Введение в теорию автоматов, языков и вычислений, 2_е изд.: - М.: Издательский дом "Вильямс", 2002. - 528 с.

2. Романовский И.В. Дискретный анализ. 2-е изд., исправ. - СПб.: Нев. Диалект, 2000. - 240 с.

3. Марков В.Н. Редукция порождающего графа в NP-проблемах // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2004. Спецвыпуск. с. 51_53.

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

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