close

Вход

Забыли?

вход по аккаунту

?

Dubarenko

код для вставкиСкачать
Федеральное агенТство по образованию
Государственное образовательное учреждение
высшего профессионального образования
Санкт-петербургский государственный университет
аэрокосмического приборостроения
В. В. Дубаренко, А. С. Коновалов, А. Ю. Кучмин
ОПТИМИЗАЦИЯ
ДИНАМИКИ СИСТЕМ ПРИ УПРАВЛЕНИИ
В НЕСТАЦИОНАРНЫХ УСЛОВИЯХ
Учебное пособие
Рекомендовано учебно-методическим объединением вузов
Российской федерации по образованию в области радиотехники,
электроники, биомедицинской техники и автоматизации
в качестве учебного пособия для студентов высших учебных
заведений, обучающихся по специальности 220201
«Управление и информатика в технических системах»
Санкт-Петербург
2008
УДК 681.51.01
ББК 32.96
Д79
Рецензенты:
доктор физико-математических наук, профессор Санкт-Петербургского
государственного университета Г. А. Леонов;
доктор технических наук, профессор
Института проблем машиноведения РАН А. Л. Фрадков
Утверждено
редакционно-издательским советом университета
в качестве учебного пособия
Дубаренко В. В., Коновалов А. С., Кучмин А. Ю.
Д79 Оптимизация динамики систем при управлении в нестационарных условиях: учеб. пособие / В. В. Дубаренко,
А. С. Коновалов, А. Ю. Кучмин.  СПб.: ГУАП, 2008. 
96 с.: ил.
ISBN 978-5-8088-0351-0
Пособие соответствует курсам дисциплин, прочитанным авторами на кафедре управления и информатики в технических системах
в Санкт-Петербургском государственном университете аэрокосмического приборостроения в период 2001–2007 гг.: «Автоматизация
проектирования систем и средств управления»; «Информационное
обеспечение систем управления»; «Имитационное моделирование
систем автоматического управления»; «Системы автоматического
управления c искусственным интеллектом»; «Автоматизированные
информационные управляющие системы».
В пособии рассмотрены численные методы решения задач оптимизации систем с обратной связью по вектору состояния; методы оптимального оценивания координат вектора состояния, недоступных
для прямого измерения.
предназначено для аспирантов и студентов, изучающих дисциплины специализации по направлениям подготовки «Автоматизация
и управление» и «Приборостроение».
УДК 681.51.01
ББК 32.96
ISBN 978-5-8088-0351-0
© ГУАП, 2008
© В. В. Дубаренко,
А. С. Коновалов,
А. Ю. Кучмин, 2008
2
Содержание
Список аббревиатур........................................................... Введение.......................................................................... Глава 1. Метод кластерного пространства управляемых
динамических объектов..................................................... § 1.1. Метрологические характеристики упорядоченных
множеств элементов пространства состояний и алгоритмы
их вычислений............................................................. 1.1.1. Определения.................................................... 1.1.2. Кластерное пространство динамических объектов.
1.1.3. Индексация элементов кластерного пространства. 1.1.4. Интервальная арифметика для задач кластерного
анализа................................................................... § 1.2. О точности решения задач кластерного анализа
систем управления динамическими объектами................. Глава 2. Алгебраический подход к анализу и синтезу систем
логического типа.............................................................. § 2.1. Основные понятия и определения теории
логических систем........................................................ § 2.2. Методика арифметизации логических уравнений...... Глава 3. Метод логико-вероятностных функций.................... § 3.1. Концепция логико-лингвистических функций. ........ 3.1.1. Определения.................................................... 3.1.2. Логико-лингвистическое управление.................. § 3.2. Комбинаторный метод вычисления вероятностей
сложных логических функций....................................... 3.2.1. Характеристики логико-вероятностных систем
с упорядоченными элементами................................... 3.2.2. Комбинаторные операции над логическими
функциями с упорядоченными элементами.................. 3.2.3. Алгоритм вычисления вероятности сложной
логической функции................................................. 3.2.4. Приближенные методы вычисления вероятности
сложной логической функции по заданным
вероятностям ее базисных переменных........................ Глава 4. Метод приведения систем логического типа
к форме линейной последовательностной машины................. Глава 5. Проблемы логического управления
динамическими объектами................................................. § 5.1. Стратегии управления динамическими объектами.... § 5.2. Метод ситуационного управления........................... 5
6
8
8
8
9
10
14
16
18
18
23
32
32
32
35
36
37
37
39
42
47
56
56
59
3
§ 5.3. Метод бинарных деревьев...................................... 5.3.1. Стратегия управления динамическим объектом
по методу бинарных деревьев..................................... 5.3.2. Алгоритм управления динамическим объектом
по методу бинарных деревьев..................................... Глава 6. Оценка эффективности методов оптимизации
динамических процессов.................................................... Заключение..................................................................... Библиографический список................................................ Приложение..................................................................... 4
61
65
67
69
75
77
79
Список аббревиатур
ББ – булев базис
БД – бинарное дерево
БЖ – базис Жегалкина
ВС – вектор состояния
ВУ – вычислительное устройство
ДНФ – дизъюнктивная нормальная форма
ДО – динамический объект
КА – конечный автомат
КНФ – конъюнктивная нормальная форма
ЛЛП – логико-лингвистическая переменная
ЛЛФ – логико-лингвистическая функция
ЛП – логическая переменная
ЛПМ – линейная последовательностная машина
ЛФ – логическая функция
МБД – метод бинарных деревьев
ММ – математическая модель
НЗПР – нечеткая задача принятия решения
ПМ – прогнозирующая модель
ПНФ – полиномиальная нормальная форма
ПС – пространство состояний
СДНФ – совершенная дизъюнктивная нормальная форма
СЛУ – система логических уравнений
5
Введение
В связи с неуклонным ростом требований к точности формирования динамических процессов в сложных электромеханических
системах современные методы их анализа и синтеза все меньше
удовлетворяют целям функционирования таких систем. Одной из
причин неудовлетворенности является недостаточная изученность
их поведения и связанная с этим проблема создания адекватных
математических моделей (ММ) динамических объектов (ДО). Кроме того, сами требования часто плохо формализуются, носят декларативный характер. Другой причиной является чрезмерная вычислительная трудоемкость методов формирования динамических
процессов, т. е. процессов управления.
Задачи автоматического управления условно можно разделить
на два класса: класс задач проектирования, в которых решаются
принципиальные вопросы построения регуляторов объектов управления в соответствии с принятыми критериями качества, и класс
задач функционирования ДО в реальном времени.
Проблемы, стоящие в задачах проектирования и специфика
принятия проектных решений при создании традиционных систем управления хорошо известны, сравнительно чётко обозначены
и изучены. Эти задачи сводятся к вариационным задачам и решаются с применением методов математического программирования,
при этом трудоемкость задач проектных решений не имеет решающего значения.
Специфика задач функционирования ДО в реальном времени состоит в том, чтобы периодически за заданный, сравнительно малый
интервал времени на вычислительном устройстве успеть провести
вычисления определенного объема. Эти вычисления связаны с численным интегрированием систем дифференциальных уравнений,
решением системы линейных неравенств, определением значений
вещественных и логических функций и др. Результатом вычислений является вектор управляющих воздействий на ДО как объект
управления, обеспечивающих получение требуемых динамических
процессов с заданной точностью.
В большинстве практических случаев регуляторы ДО, в том числе с самонастройкой и адаптацией к внешним воздействиям, из-за
жестких ограничений, связанных с производительностью вычислительных устройств, не содержат решателей, опирающихся на
поисковые процедуры, характерные для неклассических методов
управления.
6
При управлении нелинейными нестационарными ДО, на фазовые координаты которых наложены произвольные ограничения
типа неравенств, классические методы управления оказываются
непригодными. К числу неклассических задач управления, к которым неприменимы классические методы, можно отнести такие
задачи, как управление транспортными средствами при наличии
препятствий, парковка транспортных средств с учетом их динамики, управление летательными аппаратами в нечетко определенной
обстановке, управление электроприводами наведения крупных радиотелескопов при ограничениях на мощность, ток, крутящий момент и др. Подобные задачи связаны с решением весьма трудоемких неклассических вариационных задач переборными методами.
Действительно, в регуляторах для таких задач логические функции необходимо представлять в форме конечных автоматов (КА)
с жесткой структурой, синтезированных на стадии проектирования. Реализация подобных регуляторов с поисковыми процедурами для работы в реальном времени является проблематичной. Поэтому требуются новые подходы, позволяющие уменьшать размерность исходной задачи или сокращать число поисковых операций.
7
Глава 1
Метод кластерного пространства управляемых
динамических объектов
§ 1.1. Метрологические характеристики
упорядоченных множеств элементов пространства состояний
и алгоритмы их вычислений
Рассматриваемый метод связан с применением интервальных
методов вычислений к задачам численного исследования поведения ДО, в частности их перемещения из одного заданного состояния в другое при условии, что эти последние не являются точными,
а принадлежат ограниченным числовым множествам. Такой подход позволяет существенно сократить размерность задач и время
поиска численных решений. В многомерном фазовом пространстве
состояний (ПС) упорядочивание отдельных локальных числовых
множеств, которым принадлежат координаты ДО, может осуществляться различными способами. Рассмотрим метрологические характеристики упорядоченных множеств элементов пространства
состояний и алгоритмы их вычислений.
Применение методов интервального анализа к задачам управления ДО обусловлено тем, что технология этих методов позволяет получать гарантированные двухсторонние границы искомого решения в случаях, когда получение точного решения требует
большой трудоемкости или вообще невозможно. Возникновение
интервального анализа связано с именами известных математиков
В. М. Брадиса [26] и Р. Э. Мура [44]. В настоящее время интервальные методы расчета интенсивно развиваются [3, 15, 26, 37] и уже
чувствуется необходимость в разработке стандартов.
1.1.1. Определения
Вектор supinf – интервальный вектор ограничений вектора состояния (ВС) по нижней и верхней границам. Представляет собой
двухстолбцовую матрицу. В первом столбце записываются ограничения компонент ВС по нижним границам. Во втором столбце записываются ограничения по верхним границам.
Вектор kv – вектор кластеризации пространства состояний:
вектор целых чисел, значения которых определяют, на какое число
подынтервалов разбивается каждый интервал матрицы supinf.
8
Кластер – область пространства состояний ДО, обозначаемая
вектором номеров подынтервалов компонент вектора состояния,
на которые он проектируется.
Кластеризация пространства состояний ДО – разбиение фазовых координат вектора состояний ДО на целое число подынтервалов, в которые могут попадать проекции вектора состояния.
Управление – принятие решения о значении управляющего воздействия, подаваемого на ДО в текущий момент времени для заданного критерия качества системы управления.
Критерий качества системы управления – цель управления
выраженная в математической форме.
Цель управления – численное решение вариационной задачи
нахождения функции управления ДО, обеспечивающей его перевод из текущего состояния в целевое множество состояний за минимально возможное время и удержание его в этом множестве при
соблюдении заданных ограничений на вектор состояния или его
функции (задача максимального быстродействия).
1.1.2. Кластерное пространство динамических объектов
Допустим ВС ДО x имеет размерность size(x) = [n, 1]. Очевидно, что вектор квантования kv также имеет размерность size(kv) =
= [n, 1], а размерность матрицы supinf size(supinf) = [n, 2]. Элементы матрицы supinf c индексами (i, 1)и (i, 2) определяются выражениями supinf(i, 1) = min(x(i)) и supinf(i, 2) = max(x(i)). Вектор
kv является вектором целых чисел, а вектор-строка, образованная
путем транспонирования kv, условно совпадает с кодом кластера,
имеющего максимальный порядковый номер.
Код кластера, имеющий первый порядковый номер, представляет собой вектор-строку размерности n, состоящую из одних единиц. Элементы вектор-строки, обозначающей код кластера, будем
называть разрядами кода кластера. Допустимые значения каждого
i-го разряда являются целыми числами и лежат в интервале от 1 до
kv(i).
Таким образом, вектор-строка длины n с произвольным набором
чисел, с учетом введенного ограничения, обозначает один из кластеров гиперпространства состояний ДО.
Для проведения кластерного анализа поведения ДО в обозначенном пространстве требуется определить следующие характеристики:
– общее число кластеров;
– порядковый номер кластера по заданному коду;
– код кластера по заданному порядковому номеру;
9
– код кластера, которому принадлежит заданный вектор состояния x;
– матрицу границ кластера в пространстве состояния;
– основные элементарные арифметические действия над интервальными числами;
– расстояние от начала координат до произвольного кластера;
– расстояние между двумя произвольными кластерами;
– время пребывания ДО в заданном кластере;
– вероятность попадания ВС ДО в заданный кластер.
1.1.3. Индексация элементов кластерного пространства
Данные выше определения позволяют интерпретировать совокупность кодов кластеров как многомерный массив. Организация
формирования элементов многомерного массива и доступа к ним
может осуществляться различными методами. Одним из наиболее
известных является страничный метод организации. Для любой
размерности многомерного массива выше двух используется понятие страницы. Допустим код кластера имеет размерность, равную 5,
т. е. kod = [a b c d e]. Тогда a интерпретируется как номер строки
двумерной таблицы, b – как номер ее столбца, с определяет номер
страницы, куда входит эта таблица, а d – номер книги, в которую
входит страница c. Индекс e в этом случае может рассматриваться
как номер полки, на которой находится указанная книга, и т. д.
Пример
Допустим вектор кластеризации kv = [3 4 5 3]. Будем условно считать, что при обращении к любому элементу, например cl(2, 3, 4, 2),
массива кластеров cl, с кодом соответственно kod = [2, 3, 4, 2], в таблице размером 3 × 4, принадлежащей странице 4, книги номер 2, выбран элемент, находящийся в строке 2 и столбце 3.
Найдем алгоритм вычисления порядкового номера этого элемента среди всех элементов массива cl. Для этого требуется выбрать какой либо принцип упорядочения. Например, преобразование многомерного массива в одномерный массив путем «вытягивания» элементов массива из каждой таблицы по столбцам. При этом условии
порядковый номер элемента cl(2, 3, 4, 2) определяется следующим
образом:
– одна страница содержит nc = kv(1)kv(2) = 3 · 4 = 12 элементов;
– первая книга содержит kv(3) = 5 страниц и соответственно
nk(1) = nc · kv(3) = 12 · 5 = 60 элементов;
10
– во второй книге выбрана страница 4, следовательно предыдущие 3 страницы содержат еще 12 · 3 = 36 элементов, итого
60 + 36 = 96 элементов;
– на четвертой странице элемент cl(2, 3) имеет порядковый номер 3 · 2 + 2 = 8.
Таким образом, элемент cl(2, 3, 4, 2) имеет порядковый номер
ncl = 96 + 8 = 104.
Из изложенного следует, что общее число кластеров определяется как произведение всех индексов вектора кластеризации kv, т. е.
nncl = prod(kv).
Алгоритм вычисления порядкового номера
кластера ncl
Входными данными являются вектор квантования kv и вектор
кода кластера kod, а выходным значением – порядковый номер
кластера ncl.
function [ncl]= nomcl(kv, kod)
nn = size(kv); %Определение размерности матрицы;
n = nn(2); %nn(1) – число строк; nn(2) – число столбцов.
ncl = kod(1);
v = kv(1);
for i = 1:n %Начало цикла.
ncl = ncl + (kod(i + 1) – 1)*v;
if i < n – 1 %Начало условия.
v = v*kv(i + 1); %При выполнении условия.
else %Условный переход при невыполнении условия.
break %Выход из цикла.
end %Конец условия.
end %Конец цикла.
Алгоритм определения кода кластера
Алгоритм вычисления кода кластера kod по заданным: порядковому номеру кластера ncl и вектору квантования kv:
function [kod]= kodcl(kv, ncl)
nn = size(kv)
n = nn(2)
v(1) = kv(1)
for i = 1:n – 1
v(i + 1) = v(i) * kv(i + 1)
end
11
if ncl > v(n)
error(‘кластера с заданным номером не существует’)
else
x = ncl
for i = 1:n – 1
y = x / v(n – i)
kod(n + 1 – i) = ceil(y) %Функция ceil округляет y до целого в большую сторону
x = rem(x, v(n – i)) %Функция rem вычисляет остаток от деления x на
у
if x == 0
x = v(n – i)
end
end
kod(1) = x
end
Алгоритм определения кода кластера
вектора состояния
Алгоритм вычисления кода кластера kx вектора состояния x по
заданным: вектору состояния x, интервальному вектору ограничений supinf и вектору квантования kv:
function [kx, flag(2)] = kodclx(supinf, kv, x)
diap = supinf(:, 2) – supinf(:, 1)
cr = diap./ kv %Поэлементное деление элементов векторов diap и kv
kx = floor((x – supinf(:, 1))./ cr) + 1% Функция floor округляет
скобках до целого в большую сторону. Нижняя граница принята за начало
отсчета компонентов кода кластера.
if any((x – supinf(:, 1)) <= 0)
flag(2) = 1
disp(‘x выходит за пределы заданного supinf пространства по нижней
границе’)
end
if any((x – supinf(:,2)) >= kv)
flag(2) = 1
disp(‘x выходит за пределы заданного supinf пространства по верхней
%границе’)
end
12
Алгоритм определения границ пространства состояний,
занимаемых кластером
function [sicl] = suincl(supinf, kv, kod)
diap = supinf(:, 2) – supinf(:, 1);
cr = diap./ kv;
sicl(:, 2) = cr.* kod’;
sicl(:,1) = sicl(:, 2) – cr;
if any((sicl(:, 1) – supinf(:, 1)) <= 0)
disp(‘код кластера выходит за пределы заданного матрицей supinf’);
disp(‘пространства по нижней границе’);
end
if any((sicl(:, 2) – supinf(:, 1)) >= kv)
disp(‘код кластера выходит за пределы заданного матрицей supinf’);
disp(‘пространства по верхней границе’);
end
Алгоритм вычисления евклидовой нормы
интервального числа
Дано непрерывное множество вещественных чисел y на отрезкe
x = [a, b], (a <= b, т. е. a = inf(y), b = sup(y)). Определить z =
= norm(x)
function [z] = normint(x)
if sign(prod(x)) >= 0; %Если знак произведения элементов x не изменяется, то
z = [abs(min(x)), abs(max(x))];
else %В противном случае
z = [0, max(abs(min(x)), abs(max(x))];
end
Алгоритм вычисления расстояния distcl
от начала координат до кластера
Задан вектор границ пространства состояний кластера sicl. Расстояние distcl вычисляется как норма интервального вектора sicl.
function [rcl] = distcl(sicl)
nn = size(sicl);
s = [0 0];
for i = 1:nn(1)
z{i} = kvint(sicl(i,:));
13
s = sumint(s, z{i});
end
rcl = normint(s);
1.1.4. Интервальная арифметика
для задач кластерного анализа
Алгоритм определения интервальной суммы
двух интервальных векторов
Даны два интервальных вектора x и у, компоненты которых заданы на отрезках, соответственно для x(i) на отрезке [a, b], (a <= b,
т. е. a = inf(x(i)), b = sup(x(i)) и для у(i) на отрезке [c, d], (c <= d, т. е.
c = inf(y(i)), d = sup(y(i))).
function [z] = sumint(x, y)
nn = size(x);
for i = 1:nn(1)
z(i,:) = [min(x(i,:)) + min(y(i,:)), max(x(i,:)) + max(y(i,:))];
end
Алгоритм определения интервальной разности
двух интервальных чисел
Даны множества вещественных чисел x и у, заданные на отрезках, соответственно для x на отрезке [a, b], (a <= b, т. е. a = inf(x),
b = sup(x)) и для у на отрезке [c, d], (c <= d, т. е. c = inf(y), d = sup(y)).
Определить z = x – y.
function [z] = subint(x, y)
z = [min(x) – max(y), max(x) – min(y)]
Алгоритм возведения в степень интервального числа
Дано множество вещественных чисел x, заданное на отрезке [a,
b], (a <= b, т. е. a = inf(x), b = sup(x)). Определить z = x2.
function [z] = kvint(x)
if sign(prod(x)) >= 0
z = [(min(x))^2, (max(x))^2];
else
z = [0, max((min(x))^2, (max(x))^2];
end
14
Алгоритм умножения двух интервальных чисел
Даны множества вещественных чисел x и у, заданные на отрезках, соответственно для x на отрезке [a, b], (a <= b, т. е. a = inf(x),
b = sup(x)) и для у на отрезке [c, d], (c <= d, т.е. c = inf(y), d = sup(y)).
Определить z = x·y. Для этого предварительно определим вектор B.
function [z] = mulint(x, y)
B = [min(x)*min(y), min(x)*max(y), max(x)*min(y), max(x)*max(y)];
z = [min(B), max(B)];
Алгоритм деления двух интервальных чисел
Даны множества вещественных чисел x и у, заданные на отрезках, соответственно для x на отрезке [a, b], (a <= b, т. е. a = inf(x),
b = sup(x)) и для у на отрезке [c, d], (c <= d, т. е. c = inf(y), d = sup(y)).
Определить z = x/y. Для этого определим вектор D.
function [z] = divint(x, y)
D = [min(x)/min(y), min(x)/max(y), max(x)/min(y), max(x)/max(y)];
z = [min(D), max(D)];
Алгоритм вычисления произведения постоянной матрицы
на интервальный вектор
Вычисляется произведение матрицы A на интервальный вектор:
x1 = A # x0, где символ # означает операцию интервального умножения матрицы A на интервальный вектор x0.
function x1 = mulcl(A, x0)
nn = size(A)
for j = 1:nn(2)
X0{j} = x0(j,:); %Фигурные скобки означают тип данных – ячейки.
%Ячейки позволяют хранить массивы с элементами разных типов и размерностей.
end
for i = 1:nn(1)
for j = 1:nn(2)
s{i, j} = A(i, j)*X0{j};
end
end
for i = 1:nn(1)
q{i, 1} = 0;
end
for i = 1:nn(1)
15
for j =
q{i, 1}
end
end
x1 = q;
for i =
x1(i,:)
end
1:nn(2)
= sumint(q{i, 1}, s{i, j});
1:nn(1)
= q{i, 1};
Применение описанных выше алгоритмов кластерного анализа
для задач управления ДО подробно рассмотрено в главе 5.
§ 1.2. О точности решения задач кластерного анализа
систем управления динамическими объектами
При использовании прогнозирующей модели (ПМ) для получения оценок состояния ДО при нахождении функции управления
возникает вопрос, какова точность этих оценок. Ошибки обусловлены неточностями идентификации параметров модели, ошибками измерительной системы ВС и методом вычислений, в частности
от выбора вектора кластеризации и шага квантования управляющего воздействия по времени, т. е. от времени перехода из одного
кластера в другой.
Для оценки точности вычислений в течение одного периода
кластеризации рассмотрим линейную систему управления ДО:
x (t) = Ax(t) + Bu(t).
Далее для упрощения записи будем считать начальные условия
нулевыми, а в обозначении переменных опустим их зависимость от
времени.
Пусть ξ – возмущение решения от внешней помехи g, тогда
x + g = A(x + ξ) + Bu. Обозначив x − Bu = f, получим: A(x + ξ) = f + g.
Относительная погрешность norm(ξ)/norm(x) решения может
быть выражена через относительную погрешность возмущения
norm(g)/norm(f) следующим образом. Введем определение norm(g)/
norm(f) = µ(A)(norm(ξ)/norm(x)), где µ(A) – число обусловленности
матрицы А.
Известно, что любую невырожденную матрицу А можно представить в виде произведения A = UKV, где U и V – ортогональные матрицы, а K – диагональная матрица, диагональными элементами которой являются сингулярные числа σ1, σ2, … σn, а µ(A) = σmax/σmin.
16
Поэтому относительную погрешность решения приведенной
выше линейной системы при внешнем возмущении можно определить следующим выражением:
norm(ξ)/norm(x) = σmax,/σmin(norm(g)/norm(f)).
Используя сингулярное разложение матрицы А, можно получить также оценку относительной точности решения при несовпадении реальных параметров этой матрицы с расчетными параметрами.
Выводы
Применение алгоритмов кластерного анализа к задачам логического (ситуационного) управления ДО по сравнению с алгоритмами,
в которых действия над числами не обобщены на числовые множества, имеет ряд преимуществ. Главными из них, на наш взгляд, являются: во-первых, возможность сокращения размерности задачи
и увязывание ее с заданной точностью, во-вторых, возможность управления нелинейными нестационарными объектами с произвольными ограничениями. До последнего времени реализация методов
логического управления ДО в реальном времени сдерживалась изза сравнительно низкого быстродействия вычислительных средств
и слабого внедрения методов расчета, в которых операндами арифметических и иных вычислительных действий служат в основном
числовые множества и лишь в частном случае индивидуальные
числа. В настоящее время, с ростом вычислительной мощности
современных ЭВМ и развитием методов интервального анализа,
возникают условия для отказа от регуляторов систем управления
ДО, рассчитанных только для стационарных точек и перехода к
синтезу регуляторов, основанных на методах логического управления с арифметикой четких и нечетких множеств. Предложенный
авторами набор алгоритмов кластерного анализа систем управления ДО не исчерпывает всего многообразия подходов и способов их
синтеза, но может быть небесполезным для специалистов, интересующихся данной областью исследований.
17
Глава 2
Алгебраический подход к анализу и синтезу
систем логического типа
§ 2.1. Основные понятия и определения теории
логических систем
При анализе и синтезе интеллектуальных систем управления
нелинейными ДО, функционирующими в нестационарных, экстремальных условиях с заданными показателями качества, одной из
важнейших задач является задача логического вывода и принятия
решения для системы логических функций, записанной в символьном виде. Решение такой задачи в символьном виде наталкивается
на принципиальные трудности и лишь в простейших случаях достигается методами направленного перебора. В более сложных случаях основными методами её решения являются эвристические методы, в которых большую роль играет интуиция и знания по решению аналогичных задач и предшествующий практический опыт.
Эти знания в экспертных системах используются так называемой
машиной логического вывода, т. е. программой, оперирующей с базой знаний и формирующей выводы. База знаний рассматривается также как программа, для которой машина логического вывода
является интерпретатором. Его входной информацией являются
выражения языка представления знаний. Результат работы машины логического вывода заключается в интерпретации входных
выражений в соответствии с имеющимися данными. В основу работы интерпретатора положена система исчисления высказываний и
формальный метод доказательства (логической дедукции). Одной
из разновидностей машины логического вывода является система
продукционных правил (система продукций), которая наиболее
часто применяется в экспертных системах.
Работа системы продукций может рассматриваться как выполнение следующей последовательности операций: отыскание всех
правил, условия которых соблюдены; выбор одного из этих правил и реализация предписанных им действий. Недостатком эвристических методов получения решений в системах логического
вывода является: отсутствие гарантии решения за конечное число
шагов алгоритма, случайность в выборе наиболее рационального
пути поиска решения, малая скорость числа логических выводов
в единицу времени, чрезмерная сложность интерпретации струк18
турных свойств решающего устройства. Поэтому интерес к проблемам эквивалентных символьных преобразований логических
функций (ЛФ) и образуемых ими систем логических уравнений
(СЛУ) неуклонно растет, они лежат в основе решения таких задач
искусственного интеллекта, как логический вывод и принятие решений, независимо от того, к какой прикладной области данные
решения относятся [14, 30]. Однако символьное представление ЛФ
и СЛУ при больших размерностях логических задач громоздко и
неудобно, поэтому актуален поиск других форм представления ЛФ
и СЛУ, например таких, в которых используются их арифметические свойства [10, 11, 12].
Кроме того, методы решения задач логического вывода и принятия решений, основанные на эвристических правилах и манипуляциях с символьными строками и использовании нечисловых
исчислений (языки LISP, PROLOG и их диалекты), не обеспечивают гарантированного решения за конечное время, трудоемки и
маловыразительны при больших размерностях этих задач. Однако
существуют методы, основанные на представлениях ЛФ как упорядоченных множеств и комбинаторных (не символьных) приемах
их преобразования [30, 31], или такие, когда для упорядоченного
множества строится декартово произведение, элементы которого
лексикографически упорядочены [20] и нет необходимости записывать явно все его члены, а достаточно знать, как вычисляется
любой из них. При этом благодаря арифметическим свойствам ЛФ
и СЛУ, которые они проявляют при их представлении в виде алгебраических структур по mod2, т. е. в алгебре И. И. Жегалкина [11],
оказывается возможным сведение логических задач к арифметическим, или подобным арифметическим. Это в общем случае позволяет представлять логические системы как линейные структуры,
уравнения которых не содержат конъюнктивных элементов, а для
анализа и синтеза их структурных свойств использовать математический аппарат векторно-матричной алгебры [32].
Тогда для таких систем логический вывод представляется в качестве процедуры обращения [0, 1]-матриц, а принятие решения
является многократным повторением этой процедуры при изменении начальных условий.
Для обозначения различных форм отношений и взаимосвязи
высказываний, термов, предикатов логических функций, используемых в дальнейшем для удобства изложения, в табл. 2.1 дается
принятая нами система знаков [17, 18].
Особую роль при решении задач логического вывода играют
операции импликации и эквивалентности. Под импликацией двух
19
высказываний – логических переменных (ЛП) 〈x1x 2 〉 обычно понимают новое высказывание x3, которое считается ложным, когда x1 –
истинно, а x2 – ложно, и истинным – во всех остальных случаях:
x 3 ⇔ x1x 2. Под эквивалентностью двух высказываний понимают
новое высказывание x4, которое считается истинным, когда оба высказывания 〈x1x 2 〉 либо одновременно истинны, либо одновременно
ложны, и ложным – во всех остальных случаях: x 4
x1x 2 ∨ x1x 2.
⇔
Таблица 2.1. Обозначения различных форм отношений и взаимосвязи
высказываний, термов, предикатов логических функций
Символ
Название
Пример
Читается
Операция
∨
Дизъюнкция
x1 ∨ x2
x1 или x2
OR
∧
Конъюнкция
Умножение по mod2
x1 ∧ x2
x1x2
x1 и x2
AND
⊕
Исключающее ИЛИ
(сложение по mod2)
x1 ⊕ x2
либо x1,
либо x2
XOR
=
Равенство
x1 = x2
⇔
Эквивалентность
(двойная импликация)
x1 ⇔ x2
x1 тогда
и только тогда,
когда x2
–
Отрицание
(надчеркивание)
x
не х
⇒
Импликация
x1 ⇒ x2
если x1,
то следует x2
{}
Множество
{x1, …, xn}
конечное
множество
〈 〉
Упорядоченное
множество
〈x1, x2 〉
упорядоченная пара
(вектор)
()
Скобки
(x1 ⊕ x2) x3
приоритет
операции
1
Истина (True)
x=1
x истинно
0
Ложь (False)
x=0
x ложно
NOT
Импликация и эквивалентность, по существу, являются функциями простых логических операций, и их употребление в математической логике отличается от лингвистического употребления
(в обычной речи). Нередко при построении баз знаний и принятии
20
решений, применяя лингвистические связки «если..., то...» и «...
тогда и только тогда...», смысловое содержание высказываний не
проверяется на соответствие таблицам истинности, и это является источником ошибок. Например, высказывание «если корабль
тонет, то крен больше 90°» не соответствует приведенной таблице
истинности для импликации, так как корабль может тонуть (x1 =
= 1) и в том случае, когда крен будет меньше 90° (x2 = 0). Поэтому
для исключения возможных ошибок импликацию и эквивалентность следует применять как логические функции x 3 ⇔ x1x 2 и
x 4 ⇔ x1x 2 ∨ x1x 2.
Логические значения операций импликации и эквивалентности
описываются таблицами истинности (табл. 2.2, 2.3).
Таблица 2.2. Таблица истинности импликации
Таблица 2.3. Таблица истинности эквивалентности
x1
x2
x3
x1
x2
x4
0
0
1
1
0
1
0
1
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
В связи с многообразием трактовок одних и тех же терминов в
различной литературе по системам искусственного интеллекта и
для удобства изложения последующего материала дадим ряд определений, которые будут часто использоваться в дальнейшем.
Логическая переменная – произвольная цепочка символов (символьная строка), используемая для обозначения структуры данных
(набора данных), одним из значений которой является значение
true или false самой ЛП. Другой частью структуры данных является атрибутная часть ЛП, которая представляет собой набор данных любого типа. Логическая переменная используется в качестве
одного из аргументов логических функций и является неделимой
логической формой (атомом).
Логическая функция по определению эквивалентна ЛП, но может использоваться и как аргумент, и как функция с любой глубиной вложенности.
Структура данных – упорядоченное множество данных в абстрактном типе данных, которым задается эта структура.
Абстрактный тип данных представляет собой множествотройку (D, F, A), состоящую из множеств: аргументов D, функций
F и аксиом A.
Атрибут ЛФ – элемент структуры данных.
21
Базисное множество ЛП – минимальное подмножество некоторого множества ЛП, порождающее все элементы исследуемого
множества.
Базисный вектор логической системы – упорядоченное множество, которые нельзя разложить на более простые, т. е. они не
могут быть продуцированы другими переменными: xT = <x1, x2, …,
xn>, где символ «T» означает транспонирование вектора x.
Базисные элементы – элементы xi базисного вектора x (атомы
логической системы).
Фундаментальная функция логической системы – логическое
произведение отрицаний ЛП: ff ⇔ x1x 2 ... x n, где x i – отрицание ЛП
xi. В полиномиальной нормальной форме (ПНФ) x i = x i ⊕ 1, тогда
ff = x1 ⊕ x2 ⊕ ... ⊕ xn ⊕ x1x2 ⊕ x1x3 ⊕ ... ⊕ x1x2x3 ⊕ ... ⊕ x1x2 ...
xj ⊕ ... ⊕ x1x2 ... xn ⊕ 1.
Здесь и далее в математических выражениях и формулах для
ЛФ символ логического умножения или опускается или заменяется символом «·», а символ «⊕» означает исключающее ИЛИ (XOR),
или, в другой терминологии, сложение по mod2.
Фундаментальный вектор логической системы – упорядоченное множество элементов декартова произведения базисного вектора x, дополненного 1 на месте последнего элемента: ST = <x1, x2,
..., xn, x1x2, x1x3, ..., x1x2x3, ..., x1x2 ... xn, 1>. Размерность этого
вектора равна nS = 2n.
Логическая функция – логическая сумма ЛП или других ЛФ,
представленная в одной из эквивалентных форм (ДНФ, СДНФ,
ПНФ и др.), например в форме ПНФ:
f1, 2, ..., k = f1 ⊕ f2 ⊕ ... ⊕ fm ⊕ ... ⊕ fk.
Идентификационная строка ЛФ – строка, состоящая из нулей
и единиц вида: Ci = <1, 1, 0, 1, 1, 0, 1, ..., 1>. Единицы в данной
строке идентифицируют элементы вектора S, которые в i-й ЛФ
складываются по mod2. Если последний элемент идентификационной строки равен 1, то это означает отрицание fi. Такая форма
задания (представления) ЛФ позволяет не вводить дополнительные
идентификаторы, например, надчеркивания, для обозначения логической связки отрицания НЕ (NOT).
Каноническая форма ЛФ – логическое произведение идентификационной строки Сi на фундаментальный вектор S: fi = CiS. Фундаментальная функция может быть определена как произведение
идентификационной вектора-строки Cff размерностью nS, заполненной одними единицами, и фундаментального вектора S:
22
Cff = <1, 1, ..., 1>, ff = CffS.
Базисный вектор ЛФ – упорядоченное множество ЛФ СЛУ:
FT = <f1, f2, ..., fm, ..., fk>.
Фундаментальный вектор ЛФ – упорядоченное множество элементов декартова произведения базисного вектора F, дополненного 1 на месте последнего элемента:
Sf T = <f1, f2, ..., fk, f1f2, f1f3, ..., f1f2f3, ..., f1f2 ... fm, ...,
f1f2 ... fk, 1>.
Компоненты фундаментального вектора ЛФ, кроме последнего
элемента, представляют собой конъюнкции компонент базисного
вектора F.
Конъюнкция ЛФ – fm = f1f2 ... fj, где f1 = C1S, f2 = C2S, ...,
fj = CjS. Тогда fm = CmS, где идентификационная строка Cm ЛФ fm
равна дизъюнкции идентификационных строк ее логических сомножителей. При этом дизъюнкцией векторов или векторов-строк
будем называть результат от дизъюнкций их элементов, имеющих
равные индексы, т. е. Cm = C1 ∨ C2 ∨ … ∨ Cm.
§ 2.2. Методика арифметизации логических уравнений
Идея арифметизации символьной логики принадлежит И. И. Жегалкину и изложена в [10, 11, 12], где, основываясь на алгебре Буля,
он упростил законы оперирования с логическими сложением и умножением и свел эти операции к действиям, на которые распространяются арифметические законы ассоциативности, коммутативности и дистрибутивности. При этом, по И. И. Жегалкину, логическая
связка «или» может употребляться только в строго разделительном
смысле, как связка «либо». Очевидно, что указанное ограничение
выдвигает дополнительное требование к процессу формирования баз
знаний предметной области.
Одним из важнейших свойств введенной И. И. Жегалкиным алгебры логики является то, что в ней логическое содержание символов «1» и «0» соответствует всегда истинной или ложной функции,
а операция отрицания заменена на операцию прибавления к ЛП
единицы: x = x ⊕ 1.
В настоящее время при анализе логических функций и их символьных преобразованиях чаще других используются булев базис
(ББ) и базис Жегалкина (БЖ). Для сравнения в табл. 2.4 приведены аксиомы этих базисов.
23
Таблица 2.4. Сравнение булева базиса и базиса Жегалкина
Булев базис
Базис Жегалкина
x∨x⇔x
x·x⇔x
x ⋅x ⇔ 0
x ∨x ⇔1
x⊕x=0
x·x=x
x ⋅x = 0
x ⊕1 = x
Отличительной особенностью представления ЛФ в БЖ является
то, что при осуществлении их преобразований ЛФ могут рассматриваться как алгебраические выражения в символьном виде, а операции манипулирования с ними представляют собой операции алгебры. Такими операциями являются: сложение, умножение, перенесение выражений из левой части в правую и наоборот, составление
и решение систем уравнений, в том числе матричными методами,
подстановка одних функций в другие, приведение подобных членов. При этом они не противоречат аксиомам БЖ.
В булевой алгебре ЛФ могут быть представлены в различных
эквивалентных формах [35], наиболее используемыми из которых
являются: дизъюнктивная нормальная форма (ДНФ), совершенная дизъюнктивная нормальная форма (СДНФ) и конъюнктивная
нормальная форма (КНФ). В алгебре Жегалкина ЛФ могут быть
представленs в виде полинома Жегалкина [10, 11, 12] или ПНФ,
называемой в западной литературе разложением Рида – Маллера.
Для ЛФ со сравнительно небольшим числом ЛП алгоритмы их преобразования из одной формы в другую хорошо изучены и для них
разработаны эффективные вычислительные процедуры [14, 25],
в том числе и для вычисления вероятностей ЛФ [29, 30]. При большом числе ЛП число логических слагаемых k в выражении для
ЛФ может быть велико, так как k = 2n–1, где n – число ЛП. Запись
таких функций в символьном виде в ЭВМ требует больших затрат
памяти, в связи с чем для сравнительно богатых содержанием логических задач, требующих больших размерностей ЛФ, вряд ли
является целесообразным использовать представление этих функций и их систем в ЭВМ в символьном виде. Практическую реализацию символьных преобразований в ЭВМ, как будет показано далее, можно осуществлять на основе вычислительной комбинаторики. В частности, если условиться, что элементы ЛФ расположены
в некотором лексикографическом порядке, то нет необходимости
хранить ее в памяти ЭВМ в символьном виде, а для однозначной
идентификации любого члена логической суммы (конъюнктивного
элемента) достаточно задать размерность множества ЛП и порядковый номер этого члена. Тогда номера индексов конъюнктивных
24
элементов, входящих в это слагаемое, определяются комбинаторными методами. Оперирование с упорядоченными множествами
позволяет заменить хранение ЛФ, представленных в символьном
виде, на хранение сравнительно простых программ, обеспечивающих быстрое вычисление индексов переменных и атрибутов. Основой для преобразования ЛФ из БЖ в ББ и обратно служит таблица истинности ЛФ для двух ЛП (табл. 2.5).
Таблица 2.5. Таблица истинности логических функций
x1
x1
x1 ∨ x2
x1 ⊕ x2
x1x2
x1x2 ∨ x1x2
0
0
1
1
0
1
0
1
0
1
1
1
0
1
1
0
0
0
0
1
0
1
1
0
Из табл. 2.5 непосредственно следует, что:
x1 ∨ x 2 ⇔ x1 ⊕ x 2 ⊕ x1x 2, x1 ⊕ x 2 ⇔ x1x 2 ∨ x1x 2,
тогда для трех ЛФ:
x1 ⊕ x 2 ⊕ x 3 ⇔ x1x 2 ∨ x1x 2 ∨ x 3 (x1x 2 ∨ x1x 2 ),
а в соответствии с законами де Моргана получим:
x1 ∨ x 2 ⇔ x1x 2, x1 ∨ x 2 ⇔ x1x 2,
x1x 2 ∨ x1x 2 ⇔ x1x 2 ⋅ x1x 2, x1x 2 ⇔
x1 ∨ x 2, x1x 2 ⇔ x1 ∨ x 2, x1x 2 ∨ x1x 2 ⇔ x1x 2 ∨ x1x 2.
Окончательно получим, что
x1 ⊕ x 2 ⊕ x 3 ⇔ x1x 2x 3 ∨ x1x 2x 3 ∨ x1x 2x 3 ∨ x1x 2x 3.
По виду слагаемых результирующей ЛФ можно заключить, что
они ортогональны. При числе членов исходной ЛФ n число членов
результирующей ЛФ N = 2n – 1. Число элементов в каждом слагаемом равно n. Слагаемые результирующей функции можно упорядочить по некоторому признаку, например по числу и порядку
отрицаний ЛП в каждом слагаемом, и связать их с номерами индексов переменных. Далее будет показано, что задачу символьного
преобразования ЛФ можно и удобнее свести к комбинаторной задаче вычисления номеров индексов элементов результирующей ЛФ
вместо манипуляций с символами.
25
С другой стороны, при переходе от ББ к БЖ для трех ЛФ имеем:
x1 ∨ x 2 ∨ x 3 ⇔ x1 ⊕ x 2 ⊕ x 3 ⊕ x1x 2 ⊕ x1x 3 ⊕ x 2x 3 ⊕ x1x 2x 3.
Число групп слагаемых по признаку количества элементов
в каждом слагаемом равно n. Число слагаемых в группе равно числу сочетаний из n по k, где k номер группы: Cnk . Общее число членов
приведенной ЛФ N = 2n – 1. Таким образом, при решении систем
логических уравнений их арифметизация легко осуществляется
переводом ЛФ из ББ в БЖ, а при интерпретации полученных решений – обратно в ББ. Поэтому решение и анализ логических задач
сводятся к анализу и решению системы
AS = b,
(2.1)
где A – прямоугольная двоичная матрица размерностью [n, m],
n > m; S – фундаментальный вектор логической системы размерностью n; b – двоичный вектор размерностью n.
Основная задача состоит в том, чтобы найти матрицу, псевдообратную матрице А. Решение системы (2.1), в которой переменных
больше, чем уравнений, приводит к множеству решений. Поэтому
псевдообратная матрица не является единственной. Полный их набор определяет все допустимые векторы решений.
Одним из методов решения является метод, аналогичный методу
исключения К. Ф. Гаусса при решении линейных систем алгебраических уравнений с вещественными числами. Суть метода состоит
в сложении уравнений для исключения переменных, входящих
в эти уравнения. Эффект поглощения членов уравнений в результате их сложения по mod2 связан с выполнением одной из аксиом
алгебры И. И. Жегалкина: x ⊕ x = 0. Процедура заключается в преобразовании матрицы А так, чтобы в результате сложения строк
матрицы по правилам элементарных преобразований по mod2 результирующая матрица имела бы минимальное число ненулевых
элементов, что и является решением.
Если по условию задачи требуется среди возможных допустимых решений найти наилучшее, то ее решение, как правило, связано с проблемами оптимизации. Задачи оптимизации возможны
только тогда, когда существует некоторая мера для вектора S. Эта
мера скрыта в атрибутах S, так как сам вектор является логическим. Поэтому необходимо ввести определение его меры (нормы),
что требует метризуемости множества атрибутов, добиться которой,
к сожалению, не всегда просто, а иногда и невозможно. Оптимизационная задача легче всего решается, если указанная мера имеет
26
скалярный тип. (Многоместные задачи имеют свою специфику и
рассматриваются в [40]). В простейшем случае скалярной мерой,
например, может служить евклидова норма, т. е. сумма ненулевых
элементов вектора S, вес которых условно принимается равным
единице. Здесь можно усмотреть аналогию с кодовым расстоянием
в теории Р. В. Хемминга [7]. Нахождение минимума этой суммы
является задачей комбинаторной оптимизации. Известно [32], что
минимизация евклидовой нормы линейной системы с вещественными числами AaSa = ba достигается при выполнении условия:
= (A Ta A a ) −1 A Ta b a , (2.2)
где A Ta – транспонированная матрица Aa.
Аналогичным является решение, при котором S содержит минимальное число ненулевых компонент, т. е. если A~ – псевдообратная матрица, то решение уравнений (2.1) имеет вид: A~AS =
= A~b. Если A~A = E – единичная матрица, тогда
Sa
min
S = A~b.
(2.3)
В системе (2.1) матрицы и векторы имеют двоичный тип данных, а в выражении (2.2) элементам присваивается вещественный
тип, и задача оптимизации переходит в область атрибутов. Если по
условию задачи требуется найти только допустимые решения, т. е.
весь набор псевдообратных матриц, то решения оптимизационной
задачи не требуется. Однако наиболее изученной и часто встречающейся оптимизационной задачей является нахождение допустимого решения с максимальным значением его вероятности, что
характерно для нечетких задач принятия решения (НЗПР) логиковероятностного типа.
Теперь рассмотрим динамические системы, которые характерны для НЗПР эволюционно-генетического типа. В наиболее общей
форме динамические системы логического типа известны как конечные автоматы (КА) и математическую модель произвольной логической системы можно представить в виде системы:
x(t + 1) = Ax(t) ⊕ Bu(t) ⊕ Fz(t) ⊕ r,
y(t) = Gx(t) ⊕ Du(t) ⊕ Hz(t) ⊕ s,
z(t) = K&x(t) ⊕ q.
(2.4)
По аналогии с линейными системами управления: x(t) – вектор
состояния КА; y(t) – вектор выхода КА; u(t) – вектор управляющих
воздействий; z(t) – вектор возмущающих воздействий; x(t), y(t),
27
u(t), z(t) – двоичные [0, 1] векторы; A, B, G, D, F, K, H – двоичные
[0, 1] матрицы; A – квадратная не особенная; r, s, q – постоянные
двоичные [0, 1] векторы; t = 1, 2, 3, ...; T – параметр целого типа.
В выражении (2.4) оператор & означает, что компонентами вектора z(t) являются логические (или алгебраические по mod2) произведения компонент вектора x(t), номера которых задаются ненулевыми (единичными) значениями компонент матрицы K. Таким
образом, компонентами вектора z(t) являются конъюнкции из компонент вектора x(t).
При отсутствии аргумента t система (2.4) переходит в алгебраическую форму:
Ax ⊕ Bz = r; y = Gx ⊕ Dz ⊕ s. (2.5)
С каждой компонентой xi вектора x связан вектор, названный
вектором атрибутов xa. Например, значениями атрибутов могут
быть: xa(i, 1) – значение i-го компонента вектора x, тип данных –
двоичный; xa(i, 2) – значение параметра t, тип данных – целый;
xa(i, 3) – текст высказывания на естественном языке, с которым
связана i-й компонент вектора x, тип данных – символьная строка;
xa(i, 4) определяет, является ли высказывание «атомом» или нет,
тип данных – двоичный; и т. д.
Значения «атома» имеют высказывания, которые по определению пользователя не требуют семантической (смысловой) интерпретации. Количество компонентов вектора атрибутов не является
фиксированным и может изменяться в зависимости от смыслового
содержания задачи.
Пример
Рассмотрим процедуру приведения квадратной матрицы к диагональному виду. Данная процедура важна, так как неособенная
матрица, приведенная к диагональному виду, имеет минимальное
значение нормы.
Дана матрица:
 C 1  1
 C  1
A =  2 = 
 C 3  1
C 4  0
0
1
0
1
1
0
0
1
0
0
.
1

1 
Сложение строк будем осуществлять по mod2:
28
1
0
1-й шаг: C 2 (1) = C 2 ⊕ C 1 = 
1

0
0
1
0
1
0
0
;
1

1 
1
1
0
1
1
0
2-й шаг: C 4 (1) = C 4 ⊕ C 2 (1) = C 4 ⊕ C 2 ⊕ C 1 = 
1

0
0
1
0
0
1
0
3-й шаг: C 3 (1) = C 3 ⊕ C 4 (1) = C 1 ⊕ C 2 ⊕ C 3 ⊕ C 4 = 
1

0
0
0
4-й шаг: C 1(1) = C 1 ⊕ C 3 (1) = C 2 ⊕ C 3 ⊕ C 4 = 
1

0
0
0
;
1

1 
1
1
0
0
0
1
0
0
1
1
0
0
0
1
0
0
1
1
0
0
0
0
;
0

1 
0
0
5-й шаг: C 2 (2) = C 2 (1) ⊕ C 1(1) = C 3 ⊕ C 4 ⊕ C 1 = 
1

0
0
1
0
0
1
0
0
0
0
0
;
0

1 
0
0
.
0

1 
6-й шаг: в каждой строке имеем по одной единице, если поменять строки 1 и 3 местами, то получим диагональную матрицу размерности 4.
Собрав в систему выражения для всех строк, получим:
 C 3 (1)   C 1 C 2
 C 2 (1)   C 1 0

=
 C 1(1)   0 C 2
C 4 (1)  C 1 C 2
C3
C3
C3
0
C 4  1
C 4  1
=
C 4  0

C 4  1
1
0
1
1
1
1
1
0
1  C 1 0
1  0 C 2

0
1  0

1  0
0
0
0
0
0
 = A 1C.
C3 0 
0 C 4 
Матрица A1 является обратной по отношению к исходной матрице A. Перемножив A и A1 по mod2, можно показать, что AA1 = E,
где E – единичная матрица.
Еще одним алгоритмом приведения матриц к диагональному
виду является алгоритм умножения матрицы саму на себя, т. е.
возведение в степень по mod2. После последовательности шагов:
29
A2 = AA = A2, A3 = AAA = A3, A4 = AAAA= A4,
A5 = AAAAA = A5 = E.
Полученный результат можно интерпретировать по отношению
к динамическим системам как стремление системы к устойчивому
состоянию за конечное число шагов.
Выводы
Формализованное представление цели задачи заключается
в том, что высказывания, заданные в вопросительной форме, можно интерпретировать как цели и преобразовывать их в математическую форму. Например:
– задача прогнозирования, когда требуется для системы (2.4) определить x(T) при заданных x(0), u(t), r, s, q;
– задача идентификации состояния, когда требуется для системы (2.4) определить x(0), по наблюдению y(t) за число шагов Т;
– задача оптимального управления, генетического алгоритма,
когда для системы (2.4) требуется определить минимальное число
шагов Т для перевода её из заданного состояния x(0) в другое заданное состояние x(T);
– прямая задача логического вывода, когда для системы (2.5)
определяют x по заданному r;
– обратная задача логического вывода, когда для системы (2.5)
определяют r по заданному x.
Согласно существующей парадигме перечисленные задачи относятся к классу логических задач и обычно решаются посредством
так называемой дедуктивной машины логического вывода. Как отмечалось выше, недостаток этих методов – эвристический характер принятия решений.
Основным препятствием к решению перечисленных задач является их нелинейный характер, скрытый в векторе конъюнкций z.
Поэтому для устранения этого препятствия предлагается системы
(2.4)–(2.5) преобразовать в линейные. Возможность такого преобразования не является очевидной.
Векторы x и z являются компонентами фундаментального вектора S, который содержит полный набор конъюнкций базисного
множества ЛП, поэтому ЛФ, образованные путем умножения их
идентификационных строк на вектор S, всегда линейны. Это и есть
основание для приведения систем (2.4)–(2.5) к линейной форме.
Основным результатом решения СЛУ в линейной форме является нахождение допустимых значений двоичных переменных и
функций.
30
Нахождение лучшего или, более корректно, предпочтительного решения из допустимых приводит к проблеме их идентификации с использованием значений атрибутов переменных. При этом
вначале осуществляется переход от ЛП к числовым переменным.
Затем, если все атрибуты могут быть представлены в виде метризуемых множеств, то после выбора критерия предпочтительного
решения задача сводится к числовой задаче математического программирования. Методы решения задач математического программирования хорошо разработаны, поэтому сведение исходной задачи к задаче или последовательности задач математического программирования можно считать желаемой целью применительно
к излагаемому нами алгебраическому подходу.
31
Глава 3
Метод логико-вероятностных функций
§ 3.1. Концепция логико-лингвистических функций
3.1.1. Определения
Объект – элемент материального мира или понятие.
Высказывание – любое действие объекта или действия над объектом.
Временное сечение (номер такта) – определенный перечень событий в некоторый момент времени.
Событие – высказывание, отнесенное к определенному временному сечению (такту).
Переменная – именованная фиксированная и неделимая структура данных определенного типа, предназначенная для идентификации события и его атрибутов.
Атрибут – необходимый, постоянный признак объекта, события или переменной.
Тип данных – набор признаков переменной заданного класса.
Класс – абстрактный тип данных, представляющий собой множество: тройку (D, F, A), состоящую из множеств: областей D, функций F, каждая из которых существует и изменяется в D, и аксиом
A, которые задают свойства функции в F.
Структура данных – реализация данных определенного типа
в абстрактном типе данных путем задания аксиом для функций
хранения, доступа и взаимодействия атрибутов, например массивы
(array), записи (struct), ячейки (cell).
Имя переменной – языковое выражение, которое предназначено
для обозначения события.
Логико-лингвистическая переменная (ЛЛП) – переменная, имеющая структуру данных логико-лингвистического типа.
Структура данных логико-лингвистического типа – именованное упорядоченное множество типа cell, элементами которого
являются записи типа struct, представляющие собой упорядоченный набор (упорядоченное множество) именованных полей, в свою
очередь предназначенных для хранения атрибутов событий.
Имя (идентификатор) ЛЛП – символьная конечная последовательность букв из некоторого заданного алфавита с двумя числовыми индексами, заключенными в фигурные скобки, например
32
AC{i, j}, где AC – имя множества ЛЛП, i – индекс порядкового номера ЛЛП, j – порядковый номер временного сечения, фигурные
скобки { } являются конструктором множества AC и означают,
что это множество принадлежит типу cell (ячеек), отличительной
особенностью которого является то, что этот тип данных в качестве своих элементов допускает содержание массивов любого типа,
в том числе и ячейки с любой глубиной вложенности.
Поля атрибутов структуры данных логико-лингвистического
типа:
– порядковый номер ЛЛП;
– номер временного сечения (такта времени), к которому принадлежит ЛЛП (если система ЛЛП не связана или не рассматривается
в связи с процессами, развивающимися во времени, то номер такта
равен нулю);
– величина такта времени в секундах;
– значение ЛЛП (0 или 1);
– лингвистическое описание ЛЛП (описание события, обозначаемого ЛЛП на естественном языке);
– верхняя граница вероятности события, обозначаемого ЛЛП;
– нижняя граница вероятности события, обозначаемого ЛЛП.
Базисное множество ЛЛП – минимальное подмножество некоторого множества ЛЛП, порождающее все элементы исследуемого
множества.
Базисный вектор логической системы – упорядоченное множество ЛЛП, отнесенных к некоторому начальному временному сечению, которые нельзя разложить на более простые, т. е. они не могут быть продуцированы другими переменными: xT = < x{1}, x{2},
…, x{n} >, где символ «T» означает транспонирование вектора x
(второй индекс в фигурных скобках ЛЛП опущен, так как все ЛЛП
рассматриваются в одном начальном временном сечении).
Логико-лингвистическая функция (ЛЛФ) обозначает сложное
событие, аргументами которого являются ЛЛП, связанные логической операцией посредством одной из следующих логических
связок: & (конъюнкция), ∨ (дизъюнкция), – (отрицание), ⊕ (сложение по mod2) и имеющая в своей структуре два дополнительных
поля по сравнению с ЛЛП из базисного множества.
Дополнительные поля атрибутов ЛЛФ к полям базисных ЛЛП:
– матрица индексов ЛЛП, являющихся явными аргументами
данной ЛЛФ;
– логическая операция, связывающая аргументы в ЛЛФ.
Например, если для ЛЛФ x{16, 1}, определены матрица индексов ЛЛП [1, 1; 5, 2; 7, 2; 15, 1] и логическая операция &, то
33
это означает, что ЛЛП x{1, 1}, x{5, 2}, x{7, 2}, x{15, 1} являются
аргументами x{16, 1} в конъюнктивной форме x{1, 1) & x{5, 2} & 
& x{7, 2} & x{15, 1}.
Вложенность ЛЛФ – аргументами ЛЛФ могут быть другие
ЛЛФ. При дальнейшем изложении принято, что структура ЛЛП не
отличается от структуры ЛЛФ. Различие ЛЛП и ЛЛФ заключается
в значениях поля для матрицы индексов и поля логической операции. Для ЛЛП значения этих полей равны нулю.
Формы представления ЛЛФ – любая ЛЛФ может быть выражена в явном виде через базисные ЛЛП в одной из следующих
форм: КНФ (конъюнктивная нормальная форма), ДНФ (дизъюнктивная нормальная форма), СДНФ (совершенная дизъюнктивная
нормальная форма), ПНФ (полиномиальная нормальная форма).
Представление ЛЛФ в той или иной форме состоит в выполнении
соответствующего алгоритма (программы), результатом работы
которого (которой) является вычисление индексов базисных ЛЛП
для любого элемента ЛЛФ соответствующей формы.
Импликация для ЛЛФ – выражает причинно-следственную зависимость между двумя событиями, отнесенными к двум различным моментам времени t1 и t2.
Если допустить, что эта же зависимость существует и между
двумя временными сечениями, разделенными во времени сколь
угодно малым интервалом, то это равносильно допущению о рефлексивности этого отношения. Как заметил Р. Акофф [ ], «такое понимание причины-следствия аналогично утверждению о том, что
форма сосуда, содержащего газ, и форма самого газа определяют
друг друга».
Поэтому формулу x{3} ≡ x {1} ∨ x{2} мы не будем интерпретировать как импликацию x{3} ≡ x{1} ⇒ x{2}. Импликацией ЛЛФ станет
при условии x{3, j} ≡ x{1, k} ⇒ x{2, j}, j > k.
Тавтология ЛЛФ – событие, состоящее в том, что при преобразовании исходной матрицы индексов ЛЛФ к матрице индексов
относительно базисных ЛЛП в одной из эквивалентных форм полученная матрица индексов совпадает с матрицей индексов уже определенной ранее ЛЛФ, порядковый номер которой меньше порядкового номера исходной.
Вырожденность ЛЛФ – событие, состоящее в том, что при преобразовании исходной матрицы индексов ЛЛФ к матрице индексов
относительно базисных ЛЛП в одной из эквивалентных форм полученная матрица индексов становится пустой.
Логическая зависимость между ЛЛФ, входящими в рассматриваемую ЛЛФ как аргументы – событие, состоящее в том, что при
34
преобразовании исходных матриц индексов каждой ЛЛФ к матрицам индексов в одной из эквивалентных форм эти матрицы содержат равные строки.
Аксиома – логическое отношение двух ЛЛП, которое влечет
функцию или алгоритм, аргументами которых являются их атрибуты.
П р и м е ч а н и е 1. Некоторые ЛЛФ в одной форме могут иметь
компактный вид, т. е. содержать матрицу индексов малой размерности, а в другой форме – большой размерности. Поэтому важна
возможность вычислять индексы любого порядкового номера строки матрицы индексов для любой формы ЛЛФ.
П р и м е ч а н и е 2. При операциях с логическими атрибутами
ЛЛФ справедливы все основные аксиомы алгебры логики.
3.1.2. Логико-лингвистическое управление
Принятие решений в задачах управления ДО связано с операциями над ЛП и ЛФ. Формальная логика, после того как определены
ЛП, позволяет путем логического вывода выражать одни ЛФ через
другие ЛФ или ЛП. Формализм преобразования ЛФ достаточно
хорошо отработан, позволяет эквивалентно представлять их в различных логических базисах, решать задачи логического вывода,
интерпретации решений и других, не прибегая к понятиям атрибута ЛФ. Можно сказать, что формальная логика является самодостаточной.
С введением понятия атрибута ЛФ, например вероятности, возникают проблемы, связанные с определением математических операций с атрибутами, при проведении операций над ЛФ. Отсюда появляются определения: «логико-вероятностная задача», «нечеткая
логика» и др. Для отделения логических задач от задач, связанных
с операциями над атрибутами ЛФ, нами принята следующая концепция:
– логические переменные являются атомами логической системы;
– если с ЛП связывается атрибут, она называется логико-лингвистической;
– атрибутом может быть любой упорядоченный набор данных;
– логические операции имеют приоритет перед операциями над
атрибутами;
– символьное выражение, описывающее ЛФ, является алгоритмом над атрибутами ЛП.
Благодаря арифметическим свойствам ЛФ, которые они проявляют при их представлении в виде алгебраических структур по
35
mod2, оказывается возможным сведение логических задач к «арифметическим» или подобным арифметическим. Это в общем случае
позволяет представлять логические системы как линейные структуры, уравнения которых не содержат конъюнктивных элементов.
для таких систем логический вывод представляется как процедура обращения [0, 1]-матриц, а принятие решения – как многократное повторение этой процедуры при изменении начальных
условий.
Линеаризация систем уравнений логического типа, содержащих
конъюнкции из компонентов ВС, позволяет за счет его расширения
упорядочить причинно-следственные связи в комбинаторных задачах математического программирования и сравнительно просто определить их сложность, а также оценить логическую замкнутость и
непротиворечивость исходной нелинейной сЛУ.
Понятие лингвистической переменной и его применение к принятию приближенных решений, введенное Л. Заде в 1976 г. [13],
практически не повлияло на развитие логики. На наш взгляд, формальная логика осталась неизменной. В большинстве работ по нечеткой логике и ее приложениям лишь только изменился порядок
операций над ЛП и их атрибутами, в результате чего интерпретация задач существенно усложнилась.
Введением концепции ЛФ нами сделана попытка упорядочить
понятия, относящиеся к принятию решений при управлении ДО,
обозначить проблемы, возникающие при учете различных ограничений и показать возможные пути их решения.
§ 3.2. Комбинаторный метод вычисления вероятностей
сложных логических функций
При большом числе ЛП, число логических слагаемых k в выражении для ЛФ может быть велико, так как k может достигать значений 2n – 1, где n – число ЛП. Запись таких функций в символьном виде в ЭВМ требует больших затрат памяти. Ещё раз отметим,
что для сравнительно богатых содержанием логических задач,
требующих больших размерностей ЛФ, вряд ли является целесообразным использовать представление этих функций и их систем
в ЭВМ в символьном виде. Практическую реализацию символьных
преобразований в ЭВМ можно осуществлять на основе вычислительной комбинаторики. В частности, если условиться, что элементы ЛФ расположены в некотором лексикографическом порядке, то нет необходимости хранить ее в памяти ЭВМ в символьном
виде, а для однозначной идентификации любого члена логической
36
суммы достаточно задать число элементов множества ЛП и порядковый номер этого члена. Тогда номера индексов конъюнктивных
элементов, каждого члена логической суммы могут быть определены комбинаторными методами. Оперирование с упорядоченными
множествами позволяет заменить хранение ЛФ, представленных
в символьном виде, на хранение сравнительно простых программ,
обеспечивающих быстрое вычисление индексов переменных и атрибутов для их использования в последующих численных операциях, в том числе и для вычисления вероятностей.
3.2.1. Характеристики логико-вероятностных систем
с упорядоченными элементами
Для формального описания алгоритмов вычисления вероятности ЛФ с упорядоченными элементами введем следующие определения:
Базисный вектор вероятностей логической системы – упорядоченное множество вероятностей элементов базисного вектора x:
PxT = < px1, px2, ..., pxn >.
Фундаментальный вектор вероятности логической системы –
упорядоченное множество элементов декартова произведения базисного вектора Px, дополненного 1 на месте последнего элемента:
PsT = < px1, px2, ..., pxn, px1px2, px1px3, ..., px1px2px3, ...,
px1px2 ... pxn, 1 >.
Фундаментальный вектор вероятности ЛФ – упорядоченное
множество вероятностей элементов вектора Sf, дополненного 1 на
месте последнего элемента:
PSf = < pf1, pf2, ..., pfn, pf1f2, pf1f3, ..., pf1f2f3, ..., pf1f2, ..., fm, ...,
pf1f2, ..., fk, 1>.
3.2.2. Комбинаторные операции над логическими функциями
с упорядоченными элементами
При определении фундаментального вектора S как упорядоченного множества нами формально не был определен закон упорядочения. В частности, порядок следования элементов si, которые
можно рассматривать как конъюнкции из компонентов базисного
вектора, может подчиняться закону, согласно которому:
– индексы компонентов xi базисного вектора x, входящих в компоненты si фундаментального вектора S, представляются в виде
37
кортежей (векторов) Ai целых чисел, располагающихся в порядке
возрастания;
– для каждого si, соответствующий ему кортеж индексов Ai,
имеет значение их произведения не меньше, чем значение произведения индексов, входящих в кортеж Ai – 1 и не больше, чем в кортеж Ai + 1;
– ни одно сочетание входящих в кортежи индексов базисного
вектора не повторяется. Таким образом, вектору S ставится в соответствие таблица A, строками которой являются кортежи Ai целых чисел, обозначающих индексы компонентов базисного вектора
ЛП.
Алгоритм упорядочения элементов фундаментального вектора
S в соответствии с этим законом в нотации языка Паскаль можно
представить в следующем виде:
begin
for i:= 1 to k do A[i]:= i; {Первое подмножество}
p:= k;
while p >=1 do
begin
write (A[1], ...,A[k]); {На печатать}
if A[k] = n then p:= p – 1 else p:= k;
if p >= 1 then {Цикл с уменьшением на 1}
for i:= k downto p then A[i]:= A[p] + i – p + 1;
end
end
В основе алгоритма лежит комбинаторная процедура генерирования всех k-элементных подмножеств множества {1, ..., n}, названная в [20] лексикографическим упорядочением.
Все элементы вектора S после лексикографического упорядочения могут быть разбиты на группы. Номер группы определяется по признаку количества элементов в каждом слагаемом. Число
групп в S равно « n ». Число элементов ni в группе с номером i равно
n!
ni = Cni =
.
i !(n − i)!
Пример
Пример генерирования последовательности k-элементных подмножеств множества {1, ..., n}, при помощи рассмотренной выше
процедуры, где n = 6, представлен в табл. 3.1.
38
Таблица 3.1. Результаты упорядочения элементов фундаментального
вектора
m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A
1
2
3
4
1
2
3
5
1
2
3
6
1
2
4
5
1
2
4
6
1
2
5
6
1
3
4
5
1
3
4
6
1
3
5
6
1
4
5
6
2
3
4
5
2
3
4
6
2
3
5
6
2
4
5
6
3
4
5
6
Рассмотрим нахождение индексов S в 4-й группе для числа переменных базисного вектора равного шести, т. е. n = 6, i = 4. Пусть
требуется определить набор индексов пятого (m = 5) элемента четвертой группы(i = 4). Для этого обратимся к табл. 3.1. Как видно из
таблицы, для m = 5 имеем A = < 1 2 4 6 >. Число членов этой группы
6!
= 15. Другой задачей является определение
равно n4 = C64 =
4!(6 − 4)!
порядкового номера m по заданному упорядоченному набору индексов. Например, для заданного набора индексов < 1 3 5 6 > ЛП,
составляющих один из элементов фундаментального вектора S, из
табл. 3.1 определяем, что этому набору соответствует порядковый
номер m = 9. Поэтому, как будет показано далее, отказ от символьной формы представления в ЭВМ ЛФ, замена ее формой индексных векторов и применение комбинаторных методов их обработки
имеет принципиальное значение, так как при большом числе ЛП
и слагаемых ЛФ позволяет существенно экономить память ЭВМ и
сокращать время вычислений.
3.2.3. Алгоритм вычисления вероятности
сложной логической функции
Пусть задана произвольная логическая функция в ПНФ, аргументы которой логически совместны: f1, 2, ..., k = f1 ⊕ f2 ⊕ ... ⊕ fm ⊕ ...
⊕ fk. Требуется вычислить вероятность этой функции при заданном
базисном векторе вероятностей логической системы Px.
Так как составляющими fi являются другие ЛФ fm и глубина
вложенности ЛФ не ограничена, то без приведения их к каноническому виду невозможно определить логическую зависимость одной
ЛФ от другой. Поэтому приведение ЛФ к каноническому виду является основным условием при вычислении ее вероятности. При
этом любая ЛФ [35] может быть представлена в форме полинома
Жегалкина (канонической ПНФ) единственным образом – посредством компонент вектора S в качестве ее аргументов.
39
Несложно показать, что значение вероятности логической суммы двух совместных ЛФ в алгебре Жегалкина f1,2 = f1 ⊕ f2 определяется выражением:
p f1,2 = p f1 + p f 2 − 2 p f1f 2,
для трех ЛФ:
p f1,2,3 = p f1 + p f 2 + p f 3 − 2( p f1f 2 + p f1f 3 + p f 2f 3 ) + 4 p f1f 2f 3,
для четырех ЛФ:
p f1,2,3,4 = p f1 + p f 2 + p f 3 + p f 4 − 2( p f1f 2 + p f1f 3 + p f1f 4 + p f 2f 3 + p f 2f 4 + p f 3f 4 ) +
+4( p f1f 2f 3 + p f1f 2f 4 + p f1f 3f 4 + p f 2f 3f 4 ) − 8 p f1f 2f 3f 4,
и т. д., где вероятности pf1, pf2, pf3, pf4, pf1f2, pf1f3, pf1f4, pf2f3, pf2f4,
pf1f2f3, pf1f2f4, pf1f3f4, pf2f3f4, pf1f2f3f4 – являются элементами вектора
PSf.
В общем случае вероятность произвольной ЛФ, приведенной
к каноническому виду, можно представить как произведение вектора-строки R на PSf:
pf1, 2, …, k = RPSf,
где R – вектор-строка, содержащая k + 1-ю группу упорядоченных
элементов ri; i – обозначает номер группы; k – число логических
слагаемых в исходной ЛФ.
Все элементы в i-й группе равны, а их число ni определяется числом сочетаний из k по i: ni = Cki.
Значения элементов ri для каждой i-й группы, кроме последней k + 1-й группы, определяются выражением: ri = (−1) rk +1 (−2) i −1 ,
k + 1-я группа содержит всего один элемент.
Значение нормирующего коэффициента rk + 1 для единственного
элемента (k + 1)-й группы равно 0 или 1. При rk + 1 = 0, вычисляется вероятность ЛФ, а при rk + 1 = 1 – вероятность отрицания ЛФ.
При представлении ЛФ в форме ДНФ, т. е. в виде:
f1, 2, …, k ⇔ f1 ∨ f2 ∨ … ∨ fm ∨ … ∨ fk ⇔ fd1, 2, …, k,
(3.1)
где символ ∨ – дизъюнкция. Выражение для вероятности ЛФ () совпадает с общеизвестным выражением для вероятности совместных
событий [1], которая может быть вычислена по формуле:
pfd1, 2, …, k = RdPSf,
а элементы rdi вектора Rd – по формуле: rdi = (−1) (i −1) + rk +1 .
При представлении любой ЛФ как произведения идентификационной строки на фундаментальный вектор, вероятность этой
40
функции можно рассматривать как алгебраическую сумму, каждый элемент которой может вычисляться независимо от других
компонентов только по его порядковому номеру.
Пример 1
Логическая функция fi имеет шесть слагаемых k = 6, тогда число компонентов вектора PSf будет: nsf = 2k = 64. Требуется вычислить вероятность 50-го компонента (m = 50). Напомним, что число
элементов в i-й группе: ni = Cki.
Порядковые номера элементов вектора PSf, которые являются
последними в каждой i-й группе, могут быть вычислены по формуле: ji =
m =i
∑ Ckm.
m =1
Вектор строка J из этих элементов для нашего примера имеет
вид: J = < 6 21 41 56 62 63 64 >. При заданном m = 50, j3 = 41, j4 =
= 56, т. е. 41 < m < 56, определяем, что элемент находится в 4-й группе. Порядковый номер элемента в группе будет m – j3 = 50 – 41 = 9.
В соответствии с табл. 3.1 9-й элемент 4-й группы A9 = < 1 3 5 6 >.
Он идентифицирует номера индексов слагаемых ЛФ, которые
должны быть логически перемножены. После логического умножения компонентов слагаемых ЛФ в соответствии с группой A9,
будет получен компонент, являющийся конъюнкцией компонентов базисного вектора.
Вычисление значения вероятности этого компонента осуществляется путем арифметического умножения вероятностей, составляющих ее ЛП.
Таким образом, вероятность ЛФ определяется как сумма 2k элементов. Эти элементы могут быть разбиты на k групп. Число элементов в каждой группе определяется числом сочетаний из k элементов
по i, где i – номер группы. Элементы, входящие в группы с нечетными номерами, имеют положительный знак, а с четными – отрицательный. Вычисление значения каждого элемента осуществляется алгоритмически, так как затруднительно указать формулу, по
которой можно было бы вычислить вероятность путем подстановки
исходных данных, а алгоритм можно описать и реализовать в ЭВМ
в виде вычислительной процедуры.
Пример 2
Рассмотрим пример вычисления вероятности ЛФ f, представленной в форме ДНФ:
f ⇔ x1x3 ∨ x1x4x5 ∨ x2x4 ∨ x2x3x5.
41
Исходные данные для расчета вероятности ЛФ имеют следующие значения:
– размерность базисного вектора n = 5;
– число логических слагаемых в ЛФ k = 4;
– базисный вектор вероятностей логической функции: Pf =
= [0,6 0,7 0,9 0,6 0,7].
В соответствии с введенными выше определениями: f ⇔ fd1, 2,
..., 4, а p = pfd1, 2, …, k = RdPSf.
Вычисления вероятности ЛФ для этого примера дают следующие результаты:
1. Число слагаемых функции вероятности np = 2k = 16.
2. Rd = [1 1 1 1 –1 –1 –1 –1 –1 –1 1 1 1 1 –1 0].
3. PSf = [0,54 0,25 0,42 0,44 0,23 0,23 0,27 0,18 0,16 0,27 0,16
0,16 0,16 0,16 0,16 0]T.
4. Вероятность ЛФ p = 0,81.
3.2.4. Приближенные методы вычисления вероятности
сложной логической функции по заданным вероятностям
ее базисных переменных
При значениях k > 50 процедура вычисления на ЭВМ вероятности ЛФ по формуле pf1, 2, …, k = RPSf требует больших затрат машинного времени. Однако, как показали численные расчеты, не
все слагаемые pf1, 2, …, k дают соизмеримый вклад. Оказывается,
что при определенных условиях частью слагаемых при вычислении pf1, 2, …, k можно пренебречь из-за их малого значения, при этом
объем вычислений резко сокращается. По существу, задача состоит
в определении числа первых номеров групп, которые определяют
основной вклад в значение вероятности p, а влиянием остальных
можно пренебречь.
Для оценки вклада отдельных групп слагаемых в выражении
для вероятности ЛФ в ее результирующее значение допустим, что:
– логическая функция имеет k логических слагаемых и представлена в форме, в которой каждое логическое слагаемое является
конъюнкцией из компонентов базисного вектора x;
– все логические слагаемые независимы и совместны;
– вероятности всех логических слагаемых равны М.
Для иллюстрации процесса вычисления p сформируем вспомогательный вектор SPS = DrPSf, где Dr – диагональная матрица, диагональными элементами которой являются элементы вектора-строки
Rd. Тогда процесс вычисления вероятности ЛФ p можно представить как суммирование элементов вектора SPS: p(i) =
j =i
∑ sps(j), где
j =1
42
i – номер слагаемого функции вероятности ЛФ. При таких допущениях для каждой i-й группы можно вычислить составляющую
вероятности ЛФ, которая определяет вклад в p всех элементов i-й
группы.
Значение sps(i) при задании ЛФ в форме ПНФ определяется по
формуле
sps(i) = (–2)i + 1(M)iCki,
i
где Ck – число сочетаний из k по i.
При задании ЛФ в форме ДНФ sps(i) определяется по формуле
sps(i) = (–1)i + 1(M)iCki.
Тогда вероятность ЛФ p можно представить как функцию
p(i) =
j =i
∑ sps(j).
j =1
В соответствии с принятой моделью была составлена программа
и проведены расчеты влияния M на то, какие группы слагаемых
нужно учитывать, а какими можно пренебречь. На рис. 3.1–3.5
Рис. 3.1. Графики приближенного вычисления вероятности ЛФ:
p(k) = 0,338; k = n = 41; M = 0,01; число групп, необходимых
для точного расчета вероятности ЛФ, не превышает i = 4
Рис. 3.2. Графики приближенного вычисления вероятности ЛФ:
p(k) = 0,8779134; k = n = 41; M = 0,05; число групп, необходимых для точного расчета вероятности ЛФ, не превышает i = 8
43
Вероятность ЛФ Р
Рис. 3.3. Графики приближенного вычисления вероятности ЛФ: p(k) = 1;
k = n = 41; M = 0,3; число групп, необходимых для точного расчета вероятности ЛФ, не превышает i = 25
Рис. 3.4. Графики функции вероятности ЛФ p = f(M) при фиксированных значениях числа логических слагаемых k = 10, 20, ..., 50
Вероятность ЛФ
1
0.5
0
0
50
Число конъюнкций ЛФ
100 0
м
0.1
0.2
Рис. 3.5. Трехмерный график функции вероятности ЛФ от двух аргументов: числа логических слагаемых k и их вероятности M
44
показаны результаты этих расчетов. На каждом из рис. 3.1–3.5
изображено по две кривые линейно-интерполированных функций
sps(i) и p(i). Вероятность ЛФ равна p при k = n = 41. Из результатов расчетов видно влияние на поведение p(i) заданного значения M
слагаемых ЛФ. При малых значениях M (0,01 < M < 0,05) p(i) сходится к вероятности p ЛФ при числе групп i < 7, т. е. из 41 группы,
следует, что для расчета вероятности ЛФ нужно учитывать только
7 первых групп. При значениях 0,05 < M < 0,15 (рис. 3.5) p(k, M)
быстро сходится к 1 при числе слагаемых ЛФ k < 30. Анализ графиков, изображенных на рис. 3.1–3.5, позволяет сделать следующий
вывод: при числе слагаемых в ЛФ больше 50 и их среднеарифметической вероятности M больше 0,15 нет необходимости точно вычислять вероятность ЛФ, так как она практически равна 1, с другой
стороны, чем меньше среднеарифметическое значение вероятности
слагаемых ЛФ, тем меньше число слагаемых в выражении для ее
вероятности нужно учитывать при вычислениях (рис. 3.4).
Нами рассмотрен пример, в котором ЛФ представлена суммой
других ЛФ, которые совместны и независимы. При несовместных
ЛФ вычисление вероятности p ЛФ проводится для слагаемых только
первой группы, при этом сумма вероятностей слагаемых не должна
превышать 1 (по определению несовместных ЛП и ЛФ [41]).
Если слагаемые ЛФ совместны и логически зависимы, то при
вычислении ее вероятности, в общем случае, нельзя дать оценку
числу групп слагаемых, которые необходимо учитывать при расчетах.
Однако оценку числа удерживаемых при расчете вероятности
ЛФ групп слагаемых, при принятых выше допущениях, можно
считать первым приближением. Если приближенный расчет вероятности ЛФ не удовлетворяет по точности, то число слагаемых можно итерационно увеличивать до тех пор, пока значение вероятности
при последующих итерациях не будет удовлетворять заданной точности. Полученные в результате численных приближенных расчетов оценки точности вычислений вероятности ЛФ в зависимости от
учета только первых групп слагаемых и отбрасывания остальных
имеют важное принципиальное значение, так как позволяют при
точном расчете p существенно уменьшить число слагаемых при
суммировании. При большом числе базисных переменных такой
двухэтапный подход к вычислению p может оказаться единственно возможным. Следует заметить, что именно лексикографическое
упорядочение фундаментального вектора ЛФ и, соответственно,
слагаемых в выражении для ее вероятности дает возможность при
проведении вычислений контролировать вычислительный процесс
45
и принимать решение о его прекращении при достижении требуемой точности.
Выводы
Таким образом, прежде чем приступать к точным расчетам вероятности ЛФ, содержащей большое число слагаемых, необходимо
предварительно оценить погрешность, вносимую составляющими,
входящими в соответствующую группу слагаемых, определяющих
эту вероятность, что позволит существенно уменьшить объем вычислений путем «отсечения хвостов», дающих малый вклад в значение вероятности ЛФ. Кроме того, описанный подход к вычислению вероятности сложной ЛФ является одним из возможных.
Для сравнения его с другими подходами и оценки эффективности
предложенных алгоритмов должны быть приняты общие критерии
сложности. Одним из таких критериев может служить критерий
сложности, в соответствии с которым мера сложности вычислительной процедуры определяется числом шагов алгоритма. Поскольку
число слагаемых в выражении для вероятности ЛФ возрастает по
экспоненте от числа составляющих ее логических слагаемых, то
вряд ли можно ожидать, что будет найден алгоритм, принципиально уменьшающий экспоненциальную сложность вычислительных
процедур. В случае приведения ЛФ к ортогональному виду (СДНФ),
число ее слагаемых также имеет экспоненциальную зависимость от
исходной размерности [30]. Поэтому вычисление вероятности ЛФ
«в лоб», без предварительных приближенных оценок числа «удерживаемых» членов, приведет к неоправданно большим затратам
машинного времени или памяти ЭВМ.
Нами были рассмотрены возможности вычисления вероятности
сложных ЛФ аналитическими методами, однако существует подход, когда эта вероятность может быть вычислена методом прямого статистического эксперимента, путем генерирования значений
базисных ЛП и последующей статистической обработки. Однако
обоснование корректности постановки статистического эксперимента представляет самостоятельную задачу, которая по сложности может оказаться не проще рассматриваемой.
46
Глава 4
Метод приведения систем логического типа
к форме Линейной последовательностной
Машины
В данной главе рассматривается новый метод, названный методом расширения пространства состояний логических систем. Метод позволяет сводить исходные системы в форме конечных автоматов к линейным системам алгебраических уравнений в форме,
известной как линейные последовательностные машины (ЛПМ)
[7]. Это позволяет перейти от имитационных методов исследования
к аналитическим методам линейной алгебры по mod2. В этом случае эксперименты над моделями не проводятся. Численные оценки
определяются беспоисковыми способами, а результаты представляются в аналитической форме.
Представление моделей в форме ЛПМ имеет принципиальное
значение, так как позволяет задачи, для которых неизвестно решение за полиномиальное время, привести к задачам, для которых
известны эффективные алгоритмы решения. По терминологии
С. Кука [41], это означает свести задачу к подклассу Р так называемых NP-полных задач. В теории NP-полноты задач дискретной оптимизации, разработанной С. Куком, проблема сводимости одной
задачи к другой за полиномиальное время как функции числа шагов от ее размерности n является одной из важнейших.
Алгоритм приведения системы логических уравнений к форме
ЛПМ включает в себя следующие шаги:
1. Задача описывается СЛУ в полиномиальной форме (форме
Рида – Малера – Жегалкина), отнесенной к некоторому начальному шагу алгоритма и соответствующего ему начальному ВС.
2. Рассматривается последовательный ряд шагов алгоритма, на
которых векторы состояний выражаются через компоненты вектора начального состояния и компоненты неповторяющихся конъюнкций (термов) из этих компонентов (компонентов фундаментального вектора S).
3. Внутренний язык задачи L в алфавите (0, 1), определяющийся на первом шаге суммарным вектором начального состояния и
вектором термов из компонентов этого вектора, расширяется за
счет термов, составленных из новых комбинаций компонентов
вектора начального состояния, отнесенных к различным тактам
алгоритма.
47
4. Расширение исходного языка L заканчивается на такте T,
после которого на каждом новом такте не образуется новых комбинаций (сочетаний) термов из компонентов вектора начального состояния. В результате исходная СЛУ, описывающая задачу, преобразуется в расширенную СЛУ, по форме совпадающую с системой,
характерной для ЛПМ:
x(t + 1) = Ax(t) ⊕ Bu(t) ⊕ g,
y(t) = Cx(t) ⊕ Du(t) ⊕ h,
(4.1)
где x(t) – расширенный, по отношению к первому словарю, двоичный вектор состояния; u(t) – вектор входа; y(t) – вектор выхода; g,
h – 0, 1 векторы; A, B, C, D – 0, 1 матрицы.
Рассматриваемый ниже метод, названный методом расширения
пространства состояний базируется на известных идеях расширения алфавитов операторов логических систем.
Приведение СЛУ к форме ЛПМ связано с применением технологии символьных преобразований. Для этих целей используются
известные приёмы сравнения символьных строк и подстановок, а
также новые приемы матрично-векторного умножения и сложения
данных типа символьной строки, компонентами которой являются
целые числа, обозначающие номера слов языка L. При этом символьные строки типа полиномов Рида –Малера – Жегалкина подставляются в другие символьные строки, преобразуются за счет
приведения подобных членов по правилам вычислений логических
функций по mod2 в новые полиномы.
Решение задач сводимости произвольных систем логических
уравнений к уравнениям линейного типа в форме, известной как
линейные последовательностные машины, может быть представлено в виде обобщенной схемы. Для автономной системы такая схема
может иметь следующий вид:
x1(1) = A 1x1(0) ⊕ A 2x2 (0),
x 2 (0) = s1(x(0)),
x 2 (1) = A 3x1(0) ⊕ A 4x 2 (0) ⊕ A 5x 3 (0),
x 3 (0) = s2 (x(0)),
x 3 (1) = A 6x1(0) ⊕ A 7x 2 (0) ⊕ A 8x 3 (0) ⊕ A 9x 4 (0),
..................................................................................
x n (0) = sn −1(x(0)),
x n (1) = A j x1(0) ⊕ A j +1x 2 (0) ⊕ ... ⊕ A j + nx n +1(0),
48
(4.2)
где s1(x(0)), s2(x(0)), …, si(x(0)), …, sn–1(x(0)) – конъюнкции из
компонентов вектора начального состояния x(0), т. е. компонентов
фундаментального вектора S логической системы.
В основе излагаемого метода лежит прием символьного выражения последующих состояний КА через начальный ВС. В результате
рекурсивной подстановки символьного выражения для x(i) в x(i +
+ 1) оказывается, что после приведения подобных членов в x(i + 1)
появляются новые компоненты фундаментального вектора S. Генерация каждого нового уравнения происходит при условии, что после преобразований и вычислений Аj+n не равно нулю. Генерация
уравнений прекращается при Аj + n = 0, т. е. тогда, когда не появляется новых компонентов вектора S.
В этом случае система (4.2) принимает вид:
 x1(1)   A 1
 x 2 (1)   A 3

= 
   
x n (1)   A j
A2
A4
A j +1

  x1(0) 
  x (0) 
 ⋅  2 .    
A j + n1  x n (0) 
0
0
0
(4.3)
В компактной векторной форме систему (4.3) можно представить в виде
x(1) = Ax(0).
(4.4)
При Aj + n = 0 число переменных в системе (4.4) становится равным числу уравнений и матрица A превращается из прямоугольной в квадратную, а система (4.3) принимает форму ЛПМ.
Число компонентов фундаментального вектора S равно 2n, а вектор x является линейной функцией из этих компонентов, поэтому
очевидно, что его размерность не превышает этой величины.
Если некоторые параметры матриц A, B, C и D в системе (4.1)
неизвестны и их нужно идентифицировать путем наблюдения вектора выхода y(t), возникает известная задача совместного оценивания параметров и состояния.
Когда x(t), y(t) и u(t) являются непрерывными (аналоговыми)
сигналами, задача совместного оценивания параметров и состояния неизбежно имеет нелинейный характер [39].
Положим, что параметры ai матрицы А не изменяются во времени, т. е. dai/dt = 0, тогда
 x  f (x, ai, u,t) 
a i  = 
 . 0
(4.5)
49
Очевидно, что даже если динамика объекта линейна, уравнение
(4.5) невозможно преобразовать к форме (4.6):
 x (t) 
 x(t) 
a i (t)  = M ai (t)  , (4.6)
где М не зависит ни от x, ни от ai.
Таким образом, задача совместного оценивания параметров и
состояния ДО является нелинейной относительно вектора параметров и состояния. Это означает, что все подходы к решению этой задачи связаны с трудностями, которые приходится преодолевать при
решении задач нелинейного программирования. Характер задачи
одновременного (совместного) оценивания параметров и состояния
существенно изменяется в случае динамических систем логического типа. Можно показать, что данную задачу можно свести к задаче
оценивания лишь состояния путем увеличения размерности исходной системы (см. пример 3).
Линейный характер задачи совместного оценивания параметров и состояния ЛУ имеет принципиальное значение при решении
задач диагностирования. Характеристические матрицы А, В, С, D
представляют структурно-параметрический образ СЛУ, поэтому
их идентификация путем наблюдения ВС и последующая обработка результатов наблюдения фактически решают проблему диагностирования, так как, сравнивая эти матрицы с эталонными, можно
сразу ответить на главные вопросы диагностики – где и какая обнаружена неисправность.
Пример 1
В качестве примера рассмотрим двоичный счетчик, который является типичным КА простейшего вида (рис. 4.1).
x1(t + 1) = x1(t) ⊕ u(t),
y1(t) = x1(t) ⋅ u(t),
x 2 (t + 1) = x 2 (t) ⊕ y1(t),
y2 (t) = x 2 (t) ⋅ y1(t),
x 3 (t + 1) = x 3 (t) ⊕ y2 (t),
y3 (t) = x 3 (t) ⋅ y2 (t),
.................................
x n (t + 1) = x n (t) ⊕ y n −1(t),
50
y n (t) = x n (t) ⋅ y n −1(t),
(4.7)
u(t)
x1(t+1)
Задержка
x2(t+1)
x1(t)
y1(t)
x2(t)
y2(t)
yn–1(t)
xn(t+1)
yn(t)
xn(t)
Рис. 4.1. Структура КА простейшего вида
y1(t) = x1(t) ⋅ u(t),
y2 (t) = x1(t) ⋅ x 2 (t) ⋅ u(t),
(4.8)
y3 (t) = x1(t) ⋅ x 2 (t) ⋅ x 3 (t) ⋅ u(t), т. е. КА, описывающий счетчик, имеет обратную связь по состоянию.
Покажем, как двоичный счетчик представить в форме ЛПМ.
Положим, что на вход двоичного счетчика подаются импульсы,
равные «1», т. е. u(t) = 1. Пусть число двоичных разрядов равно 3,
тогда
x1(t + 1) = x1(t) ⊕ 1,
x 2 (t + 1) = x 2 (t) ⊕ y1(t),
x 3 (t + 1) = x 3 (t) ⊕ y2 (t), (4.9)
y1(t) = x1(t),
y2 (t) = x 2 (t) ⋅ x1(t) = x 4 (t), (4.10)
x 4 (t + 1) = x 2 (t + 1) ⋅ x1(t + 1) = (x1(t) ⊕ 1) ×
×(x1(t) ⊕ x 2 (t)) = x2 (t) ⊕ x 4 (t).
(4.11)
51
Объединяя уравнения (4.10), (4.11) и проводя преобразования
по правилам алгебры логики, получим:
x1(t + 1) = x1(t) ⊕ 1,
x 2 (t + 1) = x1(t) ⊕ x 2 (t),
x 3 (t + 1) = x 3 (t) ⊕ x 4 (t),
x 4 (t + 1) = x 2 (t) ⊕ x 4 (t), 1
1
x(t + 1) = 
0

0
0
1
0
1
0
0
1
0
(4.12)
0
1 
0 
0
⋅ x(t) +   ⋅ 1. 
1
0

 
1 
0 
(4.13)
Матричное уравнение (4.13) типично для КА в форме ЛПМ.
При каскадном наращивании структуры (4.12) двоичный счетчик можно представить в форме ЛПМ для любого числа разрядов.
Пример 2
Рассмотрим другой пример: приведение к форме ЛПМ СЛУ автономного синхронного КА.
Пусть КА описывается СЛУ:
x1(t + 1) = x1(t)x 2 (t) ⊕ x 3 (t),
x 2 (t + 1) = x1(t) ⊕ x 2 (t) ⊕ x 3 (t),
x 3 (t + 1) = x 2 (t) ⊕ x 3 (t).
(4.14)
Обозначим x1(t)x2(t) = x4(t), x2(t) x3(t) = x5(t) и рассмотрим значение x4 и x5 на следующем шаге:
x 4 (t + 1) = x1(t + 1)x 2 (t + 1),
x5 (t + 1) = x 2 (t + 1)x 3 (t + 1), подставив (4.14) в (4.15), получим:
(4.15)
x 4 (t + 1) = x 3 (t) ⊕ x1(t)x 3 (t) ⊕ x2 (t)x3 (t) ⊕ x1 (t)x2 (t)x3 (t),
x5 (t + 1) = x1(t)x 2 (t)x 3 (t).
(4.16)
Обозначим:
52
х6(t) = х1(t)х3(t), х7(t) = х1(t)х2(t)х3(t).
Объединяя уравнения (4.16) и (4.17), получим:
(4.17)
x 4 (t + 1) = x 3 (t) ⊕ x5 (t) ⊕ x6 (t) ⊕ x7 (t),
x5 (t + 1) = x7 (t),
x 6 (t + 1) = x7 (t) ⊕ x7 (t),
x7 (t + 1) = 0.
(4.18)
Объединяя все уравнения, представим расширенную систему
в векторно-матричной форме:
где
x(t+1) = Аx(t),
 x1(t) 
0
 x 2 (t) 
1


0
 x 3 (t) 

x(t) = x 4 (t)  , A = 0
 x5 (t) 
0
 x (t) 
0
6



0
 x7 (t) 
0
1
0
0
0
0
0
1
1
0
1
0
0
0
1
0
0
0
0
0
0
(4.19)
0
0
1
1
0
1
0
0
0
0
1
0
0
0
0
0
0

1.
1
1
0 
В результате система уравнений, описывающая КА, преобразуется в расширенную СЛУ (4.19), по форме совпадающую с системой
уравнений, характерной для ЛПМ.
Пример 3
Приведем пример сведения задачи совместного оценивания параметров и состояния СЛУ к задаче оценивания только состояния
путем увеличения размерности исходной системы.
Дана двоичная система (4.20):
x1(t + 1) = a1x1(t) + a2x 2 (t),
x 2 (t + 1) = a3x1(t) + a4x 2 (t), или в матричном виде:
(4.20)
 x1(t + 1)   a1 a2   x1(t) 
x 2 (t + 1)  = a3 a4  ⋅ x 2 (t)  .
Пусть a1 – неизвестный параметр, обозначим а1 = x3(t) = const,
тогда
x1(t + 1) = x3(t)x1(t) + a2x2(t).
Обозначим: x3(t)x1(t) = x4(t), тогда
(4.21)
53
x4(t + 1) = x1(t + 1)x3(t + 1) = (x3(t)x1(t) + a2x2(t))x3(t) =
= x4(t) + a2x2(t)x3(t).
Введём x5(t) = x2(t)x3(t), после подстановок и преобразований
получим:
x5(t + 1) = a3x4(t) + a4x5(t),
или в матричной форме:
 x1(t + 1)   0
 x 2 (t + 1)  a4
 x (t + 1)  = 
 3
 0
x
(
t
+
1)
 4
 0
 x5 (t + 1)   0
a2
a4
0
0
0
0 1 0   x1(t) 
0 0 0   x 2 (t) 

 
1 0 0  ⋅  x 3 (t)  . 0 1 a2  x 4 (t) 
0 a3 a4   x5 (t) 
(4.22)
Параметр a1 исключен из матрицы и входит в вектор состояния,
поэтому определяется в результате решения задачи наблюдения
вектора состояния системы (4.22).
Выводы
Линеаризация СЛУ, содержащих конъюнкции из компонентов
вектора состояний, позволяет за счет его расширения упорядочить
причинно-следственные связи в комбинаторных задачах математического программирования и сравнительно просто определить их
сложность, а также оценить логическую замкнутость и непротиворечивость исходной нелинейной СЛУ.
Модели в форме ЛПМ, в свою очередь, могут быть использованы
для:
– численного оценивания состояний и параметров динамического двоичного объекта;
– определения базисных и небазисных переменных вектора состояния X(t) в логическом пространстве двоичных переменных;
– операций над символьно-полиномиальными матрицами;
– численного определения характеристик управляемости, наблюдаемости, идентифицируемости, контроле пригодности двоичных динамических объектов;
– вычисления сигнатур дискретных устройств;
– обнаружения ошибок в циклических кодах;
– генерирования последовательности псевдослучайных чисел на
основе заданного циклического кода и др.
К виду ЛПМ можно привести достаточно большой класс КА.
В этом случае для решения задач логического анализа придется ре54
шать уже ряд других математических задач, постановки которых
являются известными, а особенности решения исследованными.
К таким задачам в первую очередь относятся задачи решения систем линейных уравнений с дискретными неизвестными и задачи
минимизации линейной целевой функции с линейными ограничениями.
55
Глава 5
Проблемы логического управления
динамическими объектами
§ 5.1. Стратегии управления динамическими объектами
Дано:
– динамический объект, функционирующий в реальном времени, с которого посредством измерительной системы снимаются
данные, характеризующие его состояние;
– математическая модель ДО, реализованная в некоторой вычислительной среде и с определенной степенью адекватности имитирующая поведение реального ДО.
Требуется:
– на интервале некоторого времени наблюдения показаний датчиков измерительной системы дать оценку ВО ДО в текущий момент времени (задача идентификации состояния);
– для заданных условий и ограничений необходимо найти функцию управления, отвечающую цели управления.
При аппроксимации уравнений ДО уравнениями в конечных
разностях задачу оптимального управления можно интерпретировать как многошаговую задачу математического программирования, основной целью которой является отыскание экстремума функции многих переменных, подчиненных различным ограничениям
[4].
При решении этой задачи возникают следующие основные проблемы:
– задача идентификации состояния ДО при одновременном оценивании фазового вектора и вектора параметров принципиально
нелинейна даже для линейных стационарных ДО, поэтому может
быть решена только с применением методов нелинейного программирования [19];
– решение вариационной краевой задачи максимального быстродействия лишь в простейших случаях для линейных стационарных ДО сводится к решению последовательности задач линейного
программирования, а для подавляющего большинства реальных
объектов также не может быть решена без применения поисковых
методов нелинейного программирования [38];
– численные методы нелинейного программирования, позволяющие решать перечисленные выше задачи, требуют сравнительно
56
больших затрат времени на поиск решения, поэтому не могут быть
реализованы в системах реального времени, для которых допустимый интервал времени, за который необходимо решить эти задачи,
существенно мал, даже для вычислителей сверхвысокой производительности.
Поэтому для преодоления указанных трудностей задачу управления решают в два этапа. На первом этапе, называемом этапом
проектирования, отыскивают параметры идентификатора состояния и оптимальную управляющую функцию, а на втором этапе
смягчают требования цели управления, и, используя полученные
данные, реализуют в регуляторе законы управления, лишь приближенно отвечающие первоначальной цели. К ним относятся законы с квадратичным функционалом качества, приводящих к стационарной обратной связи по ВС или релейному управлению при
применении метода скоростного градиента [36]. Эти методы имеют
существенный недостаток – они применимы только для локальных
областей пространства состояний, так как выбор весов коэффициентов квадратичного функционала, определяющих качество процесса управления, осуществляется для стационарных условий.
Рассмотрим уравнение движения n-мерного динамического объекта управления в разностной форме:
x(t + ∆t)=f(x(t), A(t), u(t)),
(5.1)
где: x(t), A(t), u(t) – функции времени t; t = ∆tm, m = 0, 1, 2,...;
∆t – период дискретности; x(t) – ВС; A(t) – оператор перехода системы из x(t) в x(t + ∆t); u(t) – функция управления.
На фазовые координаты ДО и управления наложены следующие
ограничения:
x(t) ∈ H,
(5.2)
u(t)∈ (U, – U).
(5.3)
Управление u(t) является кусочно-постоянной функцией на интервале ∆t и принимает одно из двух возможных значений U или
–U.
Требуется найти функцию u(t), которая обеспечивает переход
ДО из x(0) в x(Т) за минимальное время Т = n∆t или минимальное
число шагов n. Точность перевода ДО в конечное состояние зависит
от точности, с которой известны его характеристики и возмущения.
Очевидно, что неточности математического описания ДО, наличие стохастических факторов, нестабильность его параметров
57
и измерительных средств требуют частого пересчета (прогнозирования) управляющего воздействия
Целевое множество
на основе текущей информации
о векторе состояния x(t). Поэтому
H
численное решение вариационной
задачи в реальном масштабе времеx*(T)
ни требует высокой производительности вычислительных средств, что
s2
a
Q
s1
до последнего времени сдерживало
применение численных методов
x(0)
математического программирования в регуляторах ДО.
В области фазового пространКорень дерева
ства H (рис. 5.1) выделим две точки – начальное состояние ДО x(0) и
вектор целевого множества x*(Т), а
также ограничение Q – в виде неРис. 5.1. К выбору стратегии прерывной кривой.
Требуется выбрать стратегию
управления ДО при неперевода
x(0) в x*(Т) и в соответпрерывном ограничении Q
ствии с выбранной стратегией
найти функцию управления, обеспечивающую перевод за минимальное число шагов. Если в качестве целевой функции выбрать расстояние между x(0) и x*(Т) как
евклидову норму R = ||x*(Т) – x(0)||, то становится очевидным, что
градиентные методы для этой задачи неприменимы, так как в стационарных точках, в которых вычисляется градиент, ограничение
Q(x) никак не учитывается. Движение по экстремали s1, например,
с максимальной скоростью уменьшения R (метод скоростного градиента), будет проходить до точки а, в которой дальнейшее уменьшение R невозможно из-за ограничения Q(x). Выбор стратегии управления для построения экстремали s2, при движении по которой
ограничения соблюдаются, становится очевидным только тогда,
когда можно оценить всю обстановку внутри региона H. Однако
получение и формализация этой информации являются довольно
сложными проблемами.
Пример
Другой концептуальный пример сложности формализации выбора стратегии управления поясняет рис. 5.2.
Из точки x(0), находящейся в области А, требуется перейти в окрестность точки x*(Т), находящуюся в области В. В этой задаче для
58
H
B
x*(T)
s1
A
Q
x(0)
Рис. 5.2. К выбору стратегии управления ДО при ограничении Q(x) виде
щели
построения экстремали s1 нужно найти щель в ограничении Q(x),
региона фазового пространства H.
Далее будут рассмотрены два возможных подхода к смягчению
требований оптимального управления. Первый подход связан с методом ситуационного управления [26], другой – с методом бинарных деревьев [8].
§ 5.2. Метод ситуационного управления
Идея метода ситуационного управления состоит в том, что области изменения каждой компоненты векторов состояния и управления ДО разбиваются по уровню на целое число частей (квантов
или разрядов). Также квантуется целевой ВС.
С каждым квантом компонентов векторов состояния в текущий
и конечный моменты времени связывается ЛП xi. При таком представлении задачи управления пространство состояний становится
квантованным, или кластеризованным. Каждому кластеру соответствует определенный набор (сочетание) ЛП. На первом этапе
решается краевая вариационная задача по переводу ДО из одного
произвольного кластера в другой. Накапливаются статистические
данные и помещаются в базу данных, в архив.
Пусть базисное множество ЛП x = < x1, x2, ..., xn >T определяет
совокупность признаков начальных условий задачи управления,
заданной ЛФ f = f(x). Например, факт, что в результате решения
краевой задачи максимального быстродействия, управляющая
функция в текущий момент времени t принимает значение u(t) =
= +U0, (f = 1), или u(t) = –U0, (f = 0). Пусть из (2n – 1) возможных
59
наборов признаков задан набор x(1), x(2), …, x(j), …, x(m), (j = 1, 2,
…, m) и соответствующий ему ряд значений ЛФ f(j) = f(x(j)). Функция f(x(j)) имеет неявный вид. Требуется на основании этих данных
и заданном векторе вероятностей указанных признаков базисного
множества ЛП Px = < p1, p2, ..., pn >T дать прогноз значения ЛФ f(k)
и ее вероятности для любого произвольного k-го набора признаков
x(k).
Сходимость алгоритма
Для решения этой задачи представим набор признаков в виде
матрицы Ax = < x(1), x(2), …, x(j), …, x(m) >T с размерами [m, n],
а соответствующий ему набор значений функции – в виде вектора
fx = < f(1), f(2), …, f(m) >T.
Каноническая форма ЛФ представляет собой логическое произведение идентификационной строки С на фундаментальный вектор
S, т. е. f = CS, тогда
fx = < CS(1), CS(2), …, CS(m) >T =
= < S(1), S(2), ..., S(m) >TCT = AsCT,
где As = < S(1), S(2), ..., S(m) >T – матрица вычисленных значений
вектора S в соответствии с Ax.
Матрица As прямоугольная с размерами [m, 2n], поэтому С имеет
множество решений. Кроме того, если значения m и n измеряется
десятками или сотнями, то размерности матриц As и С большие. Без
дополнительных условий решение указанного уравнения является
проблематичным. Например, можно искать решение относительно
С, исходя из условий минимизации числа его ненулевых элементов, что связано с псевдообращением матрицы As и также может
быть проблематичным. Построение оптимизационной процедуры
отыскания редуцированной С ЛФ представляет самостоятельную
задачу.
При упорядочении сочетаний признаков по какому-либо закону, например лексикографическому, каждому сочетанию признаков соответствует определенный номер на оси лексикографического упорядочения. Следовательно, вектору fx может быть поставлен
в соответствие вектор номеров упорядочения. При прогнозировании значений управляющей функции для произвольного набора
признаков исходных данных задачи управления вычисляется его
номер на лексикографической оси. Затем определяются ближайшие номера компонентов вектора fx. Так как для этих номеров
известны значения функции управления и их вероятности, то по
этим данным могут быть определены прогнозируемые значения
60
функции управления и ее вероятности. Описанный алгоритм отыскания управляющих функций возможно реализовать при управлении в реальном времени, так как он имеет малую трудоемкость. К
недостаткам можно отнести сравнительно большие размеры базы
архивных данных, полученных на первом этапе.
§ 5.3. Метод бинарных деревьев
Идея метода бинарных деревьев (МБД) заключается в следующем: управляющие воздействия ограничиваются классом кусочнопостоянных функций, в виде положительных и отрицательных импульсов, порождающих в ПС бинарные деревья (БД). Динамический процесс интерпретируется как рост БД. По мере роста БД, его
узлы попадают в различные области ПС (кластеры). Ограничения,
накладываемые на фазовые координаты ДО, образуют запретныe
области для узлов БД. В узлах, которые попали в запретные области, включая их границы, эволюция БД заканчивается. С течением
времени в одни и те же кластеры могут попадать новые узлы дерева
и образовывать циклы. Для исключения зацикливаний, в этих узлах эволюция БД также завершается. Целью управления является попадание, в процессе роста БД, одного или нескольких узлов
в заданный кластер (целевое множество). Другими словами целью
управления является отыскание оптимальной управляющей функции, переводящей ДО из начального состояния в некоторую точку целевого множества за минимальное время и удерживание ДО
в этом целевом множестве, путем периодического прогнозирования
решения на заданном интервале времени прогнозирования.
Реализация алгоритмов регуляторов, основанных на МБД,
предназначенных для работы в реальном времени, представляет
значительную трудность из-за сложности вычислительного процесса. В настоящей работе рассматривается новый метод поиска
оптимального управления при адаптации к воздействиям внешней
среды. Он назван логической оптимизацией управления по методу бинарных деревьев. В этом методе оптимизационная процедура
отыскания управляющего воздействия осуществляется посредством построения БД состояний ДО. Для этого строится прогнозирующая модель, с помощью которой, для заданного времени прогнозирования и шага прогнозирования, в каждом узле БД вычисляются оценка ВС ДО и его евклидова норма, которая запоминается
и хранится в памяти ЭВМ в течении всего цикла прогнозирования.
Норма ВС рассматривается как мера расстояния от узла до начала
координат. Управляющее воздействие определяется комбинатор61
ным методом как логическая функция упорядоченного множества
узлов БД.
H
9
Стратегия MБД иллюстрирует
10
x*(T)
рис. 5.3. Цепочка узлов 1–10 лел
л
жит на экстремали. Узлы, обозна7
8
л
ченные символом «л», достигшие
Q
л
ограничений Q и H, исключаются
6
из процесса поиска оптимального
л
2 1
x(0)
решения и называются «листья4
3
ми».
5
При R = |x*(Т) – x(0)| ≤ ε точки
x(0) и x*(0) cовпадают, т. е. x(0)
находится в целевом множестве.
Возникает вопрос о выборе стратегии управления в этом случае. Для
Рис. 5.3. Стратегия управле- этого на основании динамических
ния ДО по методу би- свойств ДО назначается время пронарных деревьев
гнозирования τ и шаг ∆t квантования управляющего воздействия.
МБД основан на следующих допущениях:
– регион пространства состояний Н, в котором отыскивается управляющая функция, замкнута и не имеет разрывов;
– в регионе Н из любой произвольной точки x(t) за интервал времени ∆t посредством операторов А+(х) и А–(х) возможен переход
в две соседние области, заданные векторами x+ (t + ∆t) и x–(t + ∆t) и
ограниченные радиусом ε;
– расстояние между двумя произвольными точками ПС x1 и x2
определяется как R = (x1 – x2)TM(x1 – x2), где М – положительно
определенная матрица нормирования ПС;
– переход из x1 в x2 осуществляется за конечное число шагов;
– переход из x1 в x2, при R ≤ ε осуществляется за время, не превышающее допустимое.
– общее число узлов БД в заданном регионе не превышает допустимого значения.
Построим бинарное дерево возможных состояний, задавая каждому узлу следующие характеристики: ns – порядковый номер узла
БД; mf – номер этажа (такта); nf – число узлов в этаже; nsf – номер
узла в этаже; ks – код управляющего воздействия в узле.
На рис. 5.4 цифрами вне скобок обозначены номера узлов БД –
ns, цифрами в скобках обозначены коды управляющих воздействий – ks. Символом «1» обозначено положительное значение уп62

2

+
 4
100
1001
1000

8
16 17
10000
1
+
10
 5 +
101
1011
1010
+
1

110
1101
+  10 +  11 +  12 + 
19 20 21 22 23 24 25 26
1
 7
+
+  9
18
+
3
11
 6
1100
0
1110
+
111
1111
13 +  14 + 
27 28 29 30
15 +
2
3
31
4
11111
Рис. 5.4. Бинарное дерево
равляющего воздействия u(t) = +U, а символом «0» – отрицательное значение u(t) = –U.
Для идентификации узла и соответствующего ему кода достаточно преобразовать порядковый номер узла ns, заданный в десятичной форме, в двоичную форму binns. Код управляющего воздействия ks образуется из вектора binns путем удаления старшего
разряда (первого элемента вектора).
Номер этажа БД mf равен числу разрядов ks, а порядковый номер узла в этаже nsf вычисляется по формуле: nsf = ns + 1 – 2mf.
Например, при ns = 19, binns=[1 0 0 1 1], ks = [0 0 1 1], mf = 4,
nsf = 4 (рис. 5.5).
При решении задач управления ДО при явно заданной целевой
функции квадратичного критерия качества, отыскание управляющей функции не является принципиально проблематичной и
связано с вычислительными трудностями технического характера [21]. Например, решение задачи синтеза системы управления с
u(t)
∆t
0
1
2
3
4
t
Рис. 5.5. График управляющего воздействия от корня БД до узла ns = 19
63
линейной обратной связью, оптимальной относительно некоторого
квадратичного функционала, определяется исключительно возможностью численного решения матричного уравнения Риккати.
Вопросы устойчивости вычислений при использовании того или
иного метода решения уравнения Риккати определяются свойствами матриц ДО, выбором начального приближения, а также особенностями применяемого вычислительного алгоритма и исследуются
в каждом конкретном случае самостоятельно. Можно указать на
два существенных недостатка синтеза систем управления с квадратичным критерием качества.
Первый недостаток определяется тем, что оптимальное решение
справедливо только для стационарной точки. Другим существенным недостатком является проблема выбора весовых коэффициентов в квадратичном критерии качества. Поэтому современные
методы управления нестационарнымим ДО с ограничениями на ВС
основываются на иных методах, вычислительной основой которых
является математическое программирование [4].
Применение математического программирования для задач
управления нелинейных ДО привело к большому числу различных алгоритмов, основными чертами которых являются поисковые переборные процедуры возможных решений. Практическое
применение таких алгоритмов сдерживается из-за их большой
вычислительной трудоемкости (сложности). Теоретическое обоснование принципиальной возможности уменьшения вычислительной сложности представляет самостоятельную проблему, которой
посвящено значительное число работ [33]. По существу оценка вычислительной сложности любой задачи требующей численного решения является необходимой, так как определяет эффективность
этого решения. Общепринятая методика исследования таких задач
предполагает разложение или сведение исходной задачи к некоторому числу задач, для которых вычислительная сложность является известной. Обычно оценка сложности связывается с размерностью объектов, входящих в задачу. При этом возможны следующие
пути решения:
– решение в один этап на мелкой сетке;
– последовательность решений в несколько этапов на крупной
сетке.
Решение в один этап на мелкой сетке связано с большой размерностью задачи, но с малой комбинаторной сложностью. Последовательность решений в несколько этапов на крупной сетке на каждом
этапе связана с малой размерностью задачи, но со сравнительно
64
u(t)
f(t)
Динамический
объект
Внешнее
f(t)
возмущение
x(t)
A(t)
x(t)
y(t) y(t)
x^(t)
Наблюдатель
A(t) Измерительная
A^(t)
A1(t) A1(t)
f(t)
система
s(t)
f1(t) f1(t)
f^(t)
Шумы
s(t)
измерений
R(t)
Логико-лингвистический
x*(t + nh)
u(t) блок принятия решения
о значении управляющего z(t + nh)
воздействия
G(t + nh)
Система построения
x*(t + nh)
целевого
α(t + nh)
вектора состояния
α(t + nh)
(целеуказание)
Блок вычисления x*(t + nh)
R(t) расстояния от ДО
D(t)
z(t + nh)
до цели
Логический блок
z(t + nh) построения x^(t + nh)
БД
Система
G(t)
ограничений
Веса
квадратичного D(t)
функционала
Прогнозирующая f^(t)
x^(t + nh) имитационная модель A^(t)
x^(t)
поведения ДО
h
Рис. 5.6. Структурная схема СЛУ
большой комбинаторной сложностью. Очевидно, возможен компромисс при выборе числа этапов и размеров ячеек сетки. Для переборных задач такой подход к решению в несколько этапов делает
вычислительную сложность объектом оптимизации, что в конечном итоге может увеличить эффективность решения.
Логическое управление ДО в кластерном пространстве состояний является характерным примером указанного подхода. Структурная схема СЛУ приведена на рис. 5.6.
5.3.1. Стратегия управления динамическим объектом
по методу бинарных деревьев
Предлагается следующая стратегия управления:
1. В ПС выделяется регион, ограниченный максимально допустимыми значениями компонентов вектора ВС.
2. Если ДО находится вне региона, то для возвращения его в регион применяется Стратегия 1, согласно которой:
2.1. Посредством ПМ ДО вычисляются два ВС при заданном значении времени прогнозирования для двух постоянных, противоположных по значению управляющих воздействий x+ и x–.
65
2.2. Векторы состояния нормируются путем деления их компонент на соответствующие максимально допустимые значения.
2.3. В нормированном пространстве определяются расстояния
между целевой точкой xg, точками x+ и x–.
2.4. Выбирается тот знак управляющего воздействия, которому
соответствует меньшее расстояние до целевой точки. Это управляющее воздействие подается на ДО. Алгоритм Стратегии 1 повторяется до тех пор пока ДО не войдет в заданный регион.
3. Если ДО и цель находятся в заданном регионе ПС, применяется Стратегия 2. Суть ее заключается в следующем:
3.1. Регион разбивается на кластеры.
3.2. Определяются номера кластеров, которым принадлежит
цель и ДО.
3.3. Задается время запаздывания, необходимое вычислительному устройству (ВУ) для решения задачи перевода ПМ ДО в целевую точку.
3.4. Прогнозирующая модель ДО и модель цели продвигаются
(путем интегрирования уравнений движения) в точки, соответствующие времени запаздывания.
3.5. Из указанных точек строятся или одно, или два дерева навстречу друг другу. Дерево из точки ПМ ДО строится с прямым
оператором перехода, а из точки нахождения модели цели – с обратным оператором перехода. Алгоритм построения деревьев описывается ниже.
3.6. Решением считается событие, состоящее в том, что одному
кластеру принадлежат какие-либо ВС двух деревьев или, что ВС дерева ПМ ДО и ВС модели цели принадлежит одному кластеру.
3.7. Размеры региона уменьшаются до размеров кластера, которому принадлежат ВС ДО и цели. Регион снова разбивается на кластеры, но меньших размеров и осуществляется переход к п. 3.2.
4. Если ДО и цель находятся в одном кластере и размеры кластера минимально допустимы, т. е. кластер является целевым множеством, то применяется Стратегия 3, согласно которой:
4.1. Задается время запаздывания, необходимое ВУ для решения задачи перевода ПМ ДО в целевую точку.
4.2. Прогнозирующая модель ДО и модель цели продвигаются
(путем интегрирования уравнений движения) в точки, соответствующие времени запаздывания. Управляющее воздействие на ДО остается таким, каким оно было на предыдущем цикле вычислений.
4.3. Задается время прогнозирования.
66
4.4. Из точки состояния ПМ ДО прогнозируются два ВС при заданном значении времени прогнозирования для двух постоянных,
противоположных по значению управляющих воздействий x+ и x–.
4.5. ВС нормируются путем деления их компонентов на соответствующие максимально допустимые значения.
4.6. В нормированном пространстве определяются расстояния
между целевой точкой xg, точками x+ и x–.
4.7. Выбирается тот знак управляющего воздействия, которому
соответствует меньшее расстояние до целевой точки. Это управляющее воздействие подается на ДО.
5.3.2. Алгоритм управления динамическим объектом
по методу бинарных деревьев
Алгоритм перевода ДО из начальной точки ПС в заданную область пространства, ограниченную интервалами по каждому компоненту ВС, за минимальное время состоит из следующих шагов:
1. Ввод исходных данных.
2. Положить значение глобального номера узла ns = ns + 1.
3. Вычислить:
3.1. ns в бинарной форме binns = dec2bin(ns).
3.2. число разрядов binns siz = size(binns).
3.3. номер этажа mf = siz.
3.4. номер узла в этаже nsf = ns + 1 – 2mf – 1.
3.5. код управляющего воздействия в узле ks = binns(2 : mf).
3.6. число узлов в этаже nf = 2mf – 1.
4. Определить номер родительского узла.
5. Проверить является ли кластер, которому принадлежит родительский узел помеченным: если да, то перейти к п. 6; если нет, то
перейти к п. 7.
6. Пометить текущий узел как запретный.
7. Проверить является ли узел в этаже последним: если да, то
перейти к пункту 8; если нет, то перейти к п. 9.
8. Проверить все ли узлы этажа являются помеченными: если
да, то перейти к п. 19 (нет решения); если нет, то перейти к п. 9.
9. Определить величину шага tu квантования для управляющего воздействия.
10. По значению глобального номера узла определить знак управляющего воздействия.
11. Интегрировать уравнения математической модели ДО из текущего значения ВС x(0) на интервале t = tu. Вычислить ВС x(tu).
12. Определить принадлежит ли ВС в узле целевому кластеру:
либо для детерминированного случая по логической функции; либо
67
для стохастического случая по пороговому значению вероятности:
если да, то перейти к п. 18; если нет, то перейти к п. 13.
13. Проверить выполняются ли ограничения, наложенные на
ВС: либо для детерминированного случая по логической функции;
либо для стохастического случая по пороговому значению вероятности: если да, то перейти к п. 17; если нет, то перейти к п. 14.
14. Определить находится ли ВС в пределах заданного ПС: либо
для детерминированного случая по логической функции; либо для
стохастического случая по пороговому значению вероятности: если
да, то перейти к пункту 16; если нет, то перейти к п. 15.
15. Согласно Стратегии 1 перевести ДО, находящийся за пределами ПС, в заданный регион, в котором ограничения на ВС выполняются. Определить значение ВС. Перейти к п. 2.
16. Определить номер кластера, которому принадлежит ВС, и
пометить его как запретный. Перейти к п. 2.
17. Определить номер кластера, которому принадлежит ВС, пометить его как допустимый. Выбрать Стратегию 2. Перейти к п. 2.
18. Выбрать Стратегию 3.
19. Нет решения. Заново разбить кластерное пространство на
кластеры, увеличив их число. Положить ns = 1 и перейти к п. 2.
Вычислительный процесс организуемый в соответствии с приведенным выше алгоритмом имеет ряд особенностей. Во-первых,
он опирается на кластерный анализ, технику комбинаторных и
интервальных вычислений [9, 22], что в конечном итоге дает интервальный (нечеткий) результат и, в свою очередь, порождает
дополнительную задачу выбора решения. Во-вторых, при учете
случайных воздействий задача выбора решения приобретает логико-вероятностный характер. Как известно, для нормального стационарного случайного процесса вероятность p попадания случайной
величины x в интервал [a, b] определяется выражением:
p(a < x < b) = Φ((b – m)/σ) – Φ((a – m)/σ),
где m – математическое ожидание процесса x(t); σ – среднеквадраx
тическое значение x(t); Φ(x) =
1 2
− t
1
e 2 dt – интегральная функ∫
2π −∞
ция Лапласа.
Для принятия решения выбирается максимум вероятности попадания случайной величины в заданный интервал.
68
Глава 6
Оценка эффективности методов оптимизации
динамических процессов
Эффективность методов управления ДО обычно связывается
с возможностью реализации этих методов управления средствами
ВУ. В соответствии с выбранными критериями качества управления, алгоритмы вычисления управляющих функций могут иметь
различную вычислительную сложность. Так, например, беспоисковые алгоритмы, основанные на методах с квадратичными критериями качества, обеспечивают в ВУ численное интегрирование векторно-матричных уравнений и имеют простую логическую часть.
Поисковые алгоритмы, основанные на методах математического
программирования, напротив, имеют более сложную логическую
часть. Беспоисковые алгоритмы обеспечивают качество управления для стационарных условий, без учета нелинейностей и ограничений на ВС и управления, а поисковые алгоритмы обеспечивают
качество управления для нестационарных условий и с учетом ограничений. Очевидно, поисковые алгоритмы способны обеспечить более высокое качество управления, но их сложно реализовать в ВУ.
Сложность реализации алгоритмов обусловлена жестким требованием к времени их выполнения в ВУ, характерных для систем
реального времени. Другими словами, алгоритмы должны выполняться в ВУ за строго определенное время τ. Если длину алгоритма измерять числом элементарных операций и обозначить L, то
величина Q = L / τ оп/с характеризует вычислительную производительность ВУ. Обычно производительность универсальных и управляющих ЭВМ с одним процессором существенно ниже требуемой производительности для алгоритмов управления и обработки
информации, поэтому в мировой практике применяются многопроцессорные ЭВМ или вычислительные сети, специализированные
для многопоточной обработки данных, например на базе матричных процессоров, нейропроцессоров и т. д.
Если под качеством управления ДО понимать максимальное или
среднеквадратическое значение ошибки, при заданных значениях
управляющих и возмущающих воздействий, учете нелинейностей,
ограничений для компонентов ВС и управления, то очевидно, что
одно и то же качество управления может быть обеспечено разными методами и соответствующими им алгоритмами. Тогда наиболее эффективным окажется тот метод, алгоритм которого имеет
69
наименьшую сложность. С другой стороны, качество управления,
обеспечиваемое одним алгоритмом, может несущественно отличаться от качества, обеспечиваемого другим алгоритмом, но сложности их могут существенно различаться.
Таким образом, для сравнительной оценки эффективности методов управления нужно, прежде всего, уметь определять сложность
вычисления управляющих воздействий.
Сложность вычислений составляет одну из важнейших проблем
современной науки о вычислениях [6, 33] и представляет быстро развивающуюся область математики. Было выработано много различных подходов к проблеме сложности вычислений [6, 9].
Большинство из этих подходов связано с отысканием для логических схем и описывающих их булевых функций таких форм символьного или комбинаторного представления, из которых легко
вычисляется количество вычислительной работы. При этом для
изучения свойств алгоритмов требуется некая общая для всех форма представления. Такой общепринятой формой является машина
Тьюринга, которая, согласно выдвинутому А. Чёрчем тезису, обладает свойством, заключающимся в том, что любая изобретенная
человеком процедура может быть реализована машиной Тьюринга.
Машина Тьюринга является простым по своей идее устройством,
предназначенным для механической реализации вычислительных
процедур, но как средство для описания вычисляемых функций
малопригодна, так как не имеет развитого языка, в котором можно
явно обращаться к функциям.
Следуя [33], рассмотрим общепринятый, или более точно, известный подход к оценкам сложности.
Рассмотрим логическую функцию f с областью определения
{0, 1}n и множеством значений {0, 1}, где n – целое число, а {0, 1}n
обозначает n-кратное декартово произведение множества {0, 1}на
себя, т. е. множество всех двоичных наборов длины n.
Компактно, изложенные выше определения функции, будем записывать в виде f: {0, 1}n → {0, 1}. Наборы из m логических функций f1, f2, …, fm будем записывать f: {0, 1}n → {0, 1}m, или f(x1, x2,
…, xn), где x = (x1, x2, …, xn) ∈ {0, 1}n обозначено базисное множество логических переменных из области определения {0, 1}n.
Базисом Ω назовем минимально возможное множество логических операторов, достаточных для порождения любой произвольной
ЛФ. Примерами базисов могут служить Ω = {∨, &, ¯}, Ω = {⊕, &, 1}.
Часто для записи формул ЛФ используются смешанные базисы,
например Ω = {∨, &, ¯, ⊕}. Строго говоря, для записи ЛФ в смешанном базисе необходимо применение еще одного оператора, который
70
должен включаться в базис, а именно оператор «()» – скобки, который определяет приоритет операций. Однако в литературе по исследованию логических систем этот оператор часто опускается, а
приоритет операций как бы подразумевается, что в конечном итоге
приводит к неоднозначностям и недоразумениям.
Такое же замечание можно сделать относительно использования оператора «=». Один из крупнейших специалистов в области
математической логики С. К. Клини [68] замечает, что «равенство» помимо основных свойств рефлексивности, симметричности и
транзитивности, обладает свойством замены, а неучитывание этого
последнего свойства приводит к подмене «равенства» «эквивалентностью», что также порождает недоразумения и ошибки. Поэтому
при описании ЛФ, «равенство» допустимо применять только в базисах Ω = {⊕, &, 1}, Ω = {⊕, 1} и недопустимо в базисе Ω = {∨, &, ¯}.
Одни и те же ЛФ в различных базисах могут иметь различную
длину, которая прямо связывается с понятием комбинационной
сложности. Стремление получить минимальную комбинационную
сложность ЛФ определяется их реализацией в логических схемах
ЭВМ. Оценки сложности при таком подходе носят утилитарный,
прагматический характер и не во всех случаях могут использоваться для сравнения алгоритмов. Для такого сравнения ЛФ должны
быть представлены в одном базисе. Отмечались достоинства базиса
Ω={⊕, 1}, характерного для ЛПМ [7]. Любая ЛФ в этом базисе представляется в виде полинома Жегалкина единственным образом
[10, 11], а конечный автомат – ЛПМ.
При синтезе законов управления линейных или линеаризованных ДО относительно квадратичных критериев качества для стационарных условий или градиентных критериев, для локальных
областей фазового пространства сами законы, полученные в результате синтеза, представляют собой тривиальные вычислительные
алгоритмы векторно-матричных операций. Длина этих алгоритмов
и вычислительная сложность могут быть определены по известным
формулам в зависимости от размерности ВС.
Характерной особенностью нетривиальных вычислительных
алгоритмов является то, что они могут быть представлены в форме
двух частей (рис. 6.1): арифметической части, в которой последовательно выполняются вычислительные процедуры, вычислительная
сложность которых известна, и логической части, которая использует результаты расчета для того, чтобы сделать один или несколько логических шагов для вычисления вектора ЛП. Атрибуты ЛП
[25] в качестве начальных условий (или обратной связи) подаются
в арифметическую часть для того, чтобы осуществить следующую
71
Вектор состояния x
Операции
отношения
Исходные данные
логической части
Арифметическая
часть
Атрибуты ЛП
ЛПвход
Логическая часть
(конечный автомат)
Интерпритация
атрибутов ЛП
Исходные данные
арифметической части
ЛПвыход
СЛУ
Ограничения
ЛПМ
Оценка
сложности
По размеру
По характеристическому
характеристических
полиному
матриц
По показателям
управляемости,
наблюдаемости и др.
Рис. 6.1. Схема вычислительного алгоритма
итерацию. Процесс продолжается до тех пор, пока значения атрибутов вектора ЛП не удовлетворят заданным условиям.
Поисковые процедуры алгоритмов могут быть представлены
в форме логической комбинаторной схемы или КА Милли [9].
Напомним, что ЛПМ – это ММ вычислительной машины с памятью в базисе Ω = {⊕, 1}. Следовательно, для эквивалентного преобразования КА в ЛПМ за счет расширения ВС КА необходимо исключить из базиса Ω = {⊕, &, 1} оператор &.
Используя понятие фундаментального вектора, задачу приведения произвольной СЛУ к форме ЛПМ можно сформулировать следующим образом.
Пусть S(t) – фундаментальный вектор, построенный из базисного вектора КА. Тогда его ММ в базисе Ω = {⊕, 1} может быть записана в форме
GS(t + 1) = HS(t) ⊕ Bu(t),
72
y(t) = C·S(t) ⊕ D·u(t),
где x(t), y(t), u(t) – двоичные [0, 1] векторы; B, G, C, D, H – двоичные [0, 1] матрицы; t = 1, 2, 3, …, T – параметр целого типа.
Если базисный вектор дополнить вектором u(t), то фундаментальный векторS(t) расширится до Sр(t) и КА Милли преобразуется в КА Мура:
Sр(t + 1) = АSр(t),
y(t) = CрSр(t),
где А – квадратная матрица [0, 1].
Для конкретного КА ранг матрицы А существенно меньше ее
размера и может быть еще уменьшен для его логико-вероятностной
модели за счет исключения компонентов второго порядка малости
в соответствии с методом [9].
В конечном итоге KA может быть представлен в форме сдвигового регистра [7] или системы сдвиговых регистров, комбинационная
сложность которых известна. Сравнение алгоритмов управления
в форме сдвиговых регистров имеет существенное преимущество
по сравнению с другими формами их представления, так как для
сравнения существует небольшой набор характеристик и параметров. К таким характеристикам относятся ранг матрицы сдвигового
регистра и его характеристический полином.
Выводы
Приведение произвольного КА к форме ЛПМ не исчерпывает
проблем вычислительной сложности задач управления ДО. Линейная последовательная машина служит лишь удобной математической моделью для исследования динамических процессов. Одной из
основных задач для ЛПМ является ее перевод из одного произвольного состояния в другое за минимальное число шагов. Несложно
показать, что эта задача представляет собой задачу булева линейного программирования, которая относится к классу NP-полных
задач, для которых не гарантируется решение за полиномиальное
время и не исключен полный перебор. Для этих задач все известные полиномиальные по времени приближенные алгоритмы дают
результаты, которые не могут сколь угодно точно приближать точные решения.
Для ДО, специфика свойств и ограничений фазового пространства которых позволяет использовать прием кластеризации и ограничения длины алгоритмов за счет приближенного вычисления
вероятностей ЛФ, задачи принятия решений могут быть сведены
73
к задачам сравнительно невысокой размерности, для которых уже
возможен полный перебор.
Если известна мера сложности и численные оценки сложности
нескольких алгоритмов, окончательное принятие решения об эффективности методов, которым соответствуют эти алгоритмы, происходит с участием человека. Однако задачи принятия решений с
участием человека носят специфический характер и в этой работе
не рассматриваются. Теория, специфика этих задач и математический аппарат их решения изложен в работе Д. Б. Юдина [40].
Одним из выводов этой теории является то, что «человеческое
мышление не приспособлено эволюцией к естественному с формальной точки зрения переходу от предпочтений на множестве
объектов к предпочтениям на множестве наборов их характеристик. Поэтому имеется основание предполагать, что целенаправленный многомерный синтез знаний проще организовать с автоматами фиксированной структуры и предсказуемым поведением, чем
неформально мыслящими людьми. Напрашивается вывод, что в
сложных задачах синтеза знаний искусственный интеллект в обозримом будущем имеет более благоприятные перспективы, чем живой мозг.
В отличие от автоматов, какими бы свойствами мы ни наделяли понятия компромисс, равновесие, справедливость, какие бы
требования ни предъявлялись к этим категориям, всегда найдутся
ситуации, когда этих требований окажется недостаточно для решения вопроса о компромиссном, равновесном, справедливом выборе.
Появится необходимость во введении дополнительных свойств рационального выбора. И модификация требований к рациональному решению может продолжаться сколь угодно долго. Эта мысль
находит подтверждение у К. Гёделя [17], который показал, что в
широком классе достаточно богатых формальных систем, всегда
найдётся утверждение, истинность или ложность которого нельзя
проверить исходя из набора аксиом, определяющих правила вывода, ибо задача установления истинности формул в исчислении предикатов алгоритмически неразрешима.
74
Заключение
В настоящем учебном пособии дано концептуальное описание
подходов к решению задач управления ДО, не вписывающихся
в известные схемы. При изменении некоторых условий и ограничений интерпретации процессов неузнаваемо изменяются возникают
новые вопросы.
Нами описан метод, в котором существенным ограничением является исключение зацикливаний при росте БД, однако если снять
это ограничение, динамические процессы ДО можно аппроксимировать типовыми уравнениями математической физики использовать различные физические аналогии.
По мере роста дерева, с увеличением номера такта количество
точек (узлов) дерева в отдельных кластерах будет возрастать, т. е.
будет увеличиваться их плотность. При этом распределение плотности по всему объему области H для каждого конкретного ДО будет
уникальным. Например, рост БД можно отождествить с процессом
нагревания анизотропной среды, описываемых уравнениями теплопроводности, когда температура отдельных участков среды постепенно увеличивается, или с процессом движения делящихся в каждом узле заряженных частиц в n-мерном гиперполе, с заданным
оператором A(t) – перехода x(t) в x(t + 1). Можно усмотреть биофизическую аналогию неограниченного деления клеток в замкнутом
объеме, отождествив ее с известными процессами ММ«A-Life» (искусственной жизни). Интерес представляют аналогии колебательных ДО, описываемых уравнениями колебаний гиперболического
типа. Отличительной чертой этих уравнений является то, что область зависимости их решения ограничена характеристическим
конусом, так что область пространства H, расположенная вне этого
конуса, не влияет на решение в рассматриваемой точке. Узлы БД
колебательных ДО, достигая границ пространства H, отражаются
от этих границ и образуют пучности, проявляя волновые свойства. Волновые свойства бинарных деревьев ДО проявляются также
при прохождении нелинейностей щелевого типа и напоминают по
характеру интерференционные и дифракционные явления, свойственные световой волне. Фронт волны бинарного дерева может
быть определен как поверхность равной плотности узлов БД для
заданного такта.
Для строгого обоснования того или иного метода требуются доказательства сходимости, скорости сходимости и сложности. Однако,
как справедливо заметил академик Н. Н. Моисеев в предисловии к
книге известного специалиста по численным методам оптимизации
75
Э. Полака: «Алгоритм – это некоторое изобретение, и, как всякое
изобретение, он проходит большой путь, прежде чем превратиться
в надежную конструкцию и начинает служить людям. Исходная
идея, которая рождается у автора алгоритма, никогда в чистом
виде не может быть реализована» [24].
76
Библиографический список
1. Абрамов А. А. О переносе граничных условий для систем линейных
дифференциальных уравнений // ЖВМ и МФ. 1963. 3,6.
2. Акофф З., Эмери Ф. О целеустремленных системах. Пер. с англ. М.:
Сов. радио, 1974. 271 с.
3. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления.
М.: Мир, 1987. 356 с.
4. Беллман Р., Калаба Р. Квазилинеаризация и нелинейные краевые
задачи. М.: Мир, 1968. 183 с.
5. Вентцель Е. С. Теория вероятностей. М.: Наука, 1969. 425 с.
6. Гасфилд Ден. Строки, деревья и последовательности в алгоритмах:
Информатика и вычислительная биология / Пер. с англ. И. В. Романовского. СПб.: Невский Диалект; БХВ-Петербург, 2003. 654 с.: ил.
7. Гилл А. Линейные последовательные машины. М.: Наука, 1974. 288 с.
8. Городецкий А. Е., Дубаренко В. В., Курбанов В. Г. Метод поиска оптимальных управляющих воздействий на динамические объекты с адаптацией к изменениям внешней среды // 6-й Санкт-Петербургский симпозиум по теории адаптивных систем (SPAS»99). СПб., 1999.
9. Городецкий А. Е., Дубаренко В. В. Комбинаторный метод вычисления
вероятности сложных логических функций // Журнал вычислительной
математики и математической физики. 1999. Т. 39. № 7. С.1246–1248.
10. Жегалкин И. И. Арифметизация символической логики (продолжение) // Матем. сб. 1929. Т. 36. Вып. 3–4. стр. 205–338.
11. Жегалкин И. И. Арифметизация символической логики. Теория предложений и функций одного аргумента // Матем. сб. 1928. Т. 35.
Вып. 3–4. С. 311–377.
12. Жегалкин И. И. О технике вычисления предложений в символической логике //Матем. сб. 1927. Т. 34. Вып. 1. С. 9–28.
13. Заде Л. А. Понятие лингвистической переменной и его применение
к принятию приближенных решений. М.:Мир, 1976. 165 с.
14. Закревский А. Д. Параллельные алгоритмы логического управления. 2-е изд. Едиториал УРСС, 2003. 200 с.
15. Калмыков С. А., Шокин Ю. И., Юлдашев З. Х. Методы интервального анализа. Новосибирск: Наука, 1986. 223 с.
16. Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003. С. 1104.
17. Клини С. Математическая логика. М.: Физ.-мат. лит., 1995. 250 с.
18. Кондаков Н. И. Логический словарь-справочник. М.: Наука, 1976.
717 с.
19. Крылов И. А., Черноусько Ф. Л. Алгоритм метода последовательных
приближений для задач оптимального управления // Журнал вычислительной математики и математической физики. 1972. Т. 12. № 1. c. 14–34.
20. Липский В. Комбинаторика для программистов: Пер. с польск. М.:
Мир, 1988. 213 с.
21. Лорьер Ж. Л. Системы искусственного интеллекта. М.: Мир, 1991.
566 с.
22. Люгер, Джордж, Ф. Искусственный интеллект: стратегии и методы
решения сложных проблем. 4-е изд.: пер. с англ. М.: Изд. дом «Вильямс»,
2003. 864 с.
23. Моисеев Н. Н. Численные методы в теории оптимальных систем.
М.: Наука, 1971. 426 c.
24. Полак Э. Численные методы оптимизации Единый подход / Пер.
с англ. Ф. И. Ерешко; под ред. И. А. Ватель. М.: Мир, 1974. 376 с.
77
25. Потемкин В. Г., Рудаков П. И. Система MATLAB 5 для студентов.
2-е изд., испр. и доп. М.: ДИАЛОГ-МИФИ, 1999. 448 с.
26. Рассел Стюарт, Норвиг Питер. Искусственный интеллект: современный подход. 2-е изд.: Пер. с англ. М.: Изд. дом «Вильямс», 2006. 1408 с.
27. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы.
Теория и практика. М.: Мир, 1980. 476 c.
28. Рябинин И. А., Черкесов Г.Н. Логико-вероятностные методы исследования надёжности структурно сложных систем. М.: Радио и связь, 1981.
264 с.
29. Рябинин И. А. Логико-вероятностная теория безопасности и ее возможности // Тр. Международной научной школы «Моделирование и анализ безопасности, риска и качества в сложных системах» (МА БРК – 2001).
СПб.: Изд-во ООО «НПО “Омега”», 2001. с. 23–28.
30. Рябинин И. А. Надежность и безопасность сложных систем. СПб.:
Политехника, 2000. 248 с.
31. Рябинин И. А. О количественной оценке важности элементов при
исследовании проблем надежности и безопасности структурно-сложных
систем в условиях отсутствия исходных вероятностей их отказов или опасностей / РАН. ИПМАШ. СПб., 1995. Препринт 123. Вып. 5. С. 5–17.
32. Стренг Г. Линейная алгебра и ее применения. М.: Мир, 1980. 454 с.
33. Сэвидж Джон Э. Сложность вычислений / Пер. с англ. О. М. КасимЗаде. М.: Факториал, 1998. 368 с.
34. Табак Д., Куо Б. Оптимальное управление и математическое программирование. М.: Наука, 1975. 280 с.
35. Толковый словарь по вычислительным системам / Под общ. ред.
В. Иллингуорта. М.: Машиностроение, 1990. 560 с.
36. Фрадков А. Л. Адаптивное управление в сложных системах: беспоисковые методы. М.: Наука, 1990. 296 с.
37. Хемминг Р. В. Численные методы. М.: Наука, 1972. 400 с.
38. Шатровский Л. И. Об одном численном методе решения задач оптимального управления // Журнал вычислительной математики и математической физики. 1962. Т. 2. № 3. с. 488–490.
39. Эйкхофф П. Основы идентификации систем управления. М.: Мир,
1975. С. 569–588.
40. Юдин Д. Б. Вычислительные методы теории принятия решений.
М.: Наука, 1989. 320 с.
41. Cook S. A. The complexity of theorem proving procedures // Proceedings
of the 3rd ACM Simposium on Theory of Cmputing (1971) p. 151–158. [Русск.
пер.: С. А.Кук. Сложность процедур вывода теорем. Кибернетический сб.,
нов. сер. вып. 12. с. 5–15.
42. Gorodetsky A. E., Dubarenko V. V. About One Method Of The Decision
Dynamic Logical-And-Probabilistic Problems // First International Conferense
on Problems of Dynamic Objects Logic-Linguistic Control DOLLC’97:
Proceedings / Ed. A. E. Gorodetsky. SPb., 1997. P. 104–122.
43. Gorodetsky A. E., Dubarenko V. V. Binary trees in state space of dynamic
control objects // First International Conferense on Problems of Dynamic
Objects Logic-Linguistic Control DOLLC’97. SPb.: 1997.
44. Moore R. E. Interval analysis. N.J.: Prentice-Hall, Englewood Cliffs.
1966. 159 p.
78
Приложение
Библиотека программ для численной, комбинаторной
и символьной реализации методов исследования систем
логического управления сложными динамическими объектами
на ЭВМ в вычислительной среде MatLab
Комплекс программ векторно-матричных операций (по mod2)
над объектами логического типа
delete alf1
diary alf1
% Процедура приведения подобных членов логического произведения (по
mod2)
% алгебраических символьных выражений типа (a(1)+a(2)+...+a(m))*(b(
1)+b(2)+...
% +b(n))=(a(1)b(1)+a(2)b(1)+...+a(m)b(1)+a(2)b(2)+...+a(m)b(2)+...+
a(m)b(n)
% Значениями алгебраических величин a(i),b(i) являются индекы компонент за% данного вектора определенной размерности. Логичекое произведение
записано
% в форме матрицы А. Например,первую строку матрицы А следует трактовать:
% a(1) равно символу 1, b(1) равно символу 3.
A=[1 3
2 2
3 4
3 4
4 5
7 8
7 8]
M=size(A);
m=M(1)
n=M(2);
for i=1:m
if A(i,1)==A(i,2);
A(i,2)=0;
end
end
B=A;
k=m;
l=1;
for i=1:(m-1)
for j=(i+1):m
79
i;
j;
c=all(A(i,:)==A(j,:));
if c>0
X(l)=i;
X(l+1)=j;
l=l+2;
k=k-2;
end
end
end
B(X,:)=[];
% Вычеркивание из матрицы В попарно равных
строк
% B – это матрица А после приведения подобных членов, а “k”-число
оставшихся
% членов.
B
K
% Демонстрационная программа решения задачи
% логического вывода методом сложения строк по mod2
echo on all
A=rand(5,6)>0.5
B=ratmovie(A)
C=((abs(B)/2-fix(abs(B)/2))>0.0001)
P=C\A
R=((abs(P)/2-fix(abs(P)/2))>0.0001)
A_=C*R
A1=((abs(A_)/2-fix(abs(A_)/2))>0.0001)
Maxf.m – программа-функция решения оптимизационной задачи C*X =
max,
X – вектор, принимающий значения [0,1],
A*X <= N
% Программа-функция решения оптимизационной задачи
% C*X = max
% X – вектор, принимающий значения [0,1]
% A*X <= N
function [SM,X] = maxf(n,m,A,U,C,N)
echo off;
delete proba;
diary proba;
n
m
A
U
C
N
X(1:m,1)=zeros(m,1);
80
for t=1:(2^m)-1,
for i=1:m-1,
%
%
%
%
X(1,t+1)=X(1,t)~=U(1,t);
X
Z(i+1,t)=U(1,t)*prod(X(1:i,t));
X(i+1,t+1)=X(i+1,t)~=Z(i+1,t);
X
Z
end
X
R(:,t)=A*X(:,t);
%
R(:,t)
Y(:,t)=R(:,t)<=N;
w(t)=all(Y(:,t));
if w(t)>=1,
S(:,t)=C*X(:,t);
S(:,t)
else
end
end
[SM,T]=max(S);
XM=X(:,T);
‘Значения целевой функции’
S
‘A*X(T)’
R(:,T)
‘Вектор ограничений для максимального значения целевой
%
функции’
N
‘Максимальное значение целевой функции’
SM
‘Номер искомого оптимального вектора’
T
‘Искомый оптимальный вектор’
XM
‘Ограничения выполняются при w=1’
w
X
diary off
‘Вы можете проверить или изменить любые переменные’
‘программы inimax’
‘Выход в MATLAB по “CTRL-Z”’
keyboard
return
% Программа инициализации исходных данных для
% функции maxf.m
echo on;
m=’введите число,определяющее длину искомого вектора’;
81
m=input(‘m=’);
m
n=’введите число ограничений’;
n=input(‘n=’);
n
A=rand(n,m);
A
U=ones(1,(2^m)-1);
U
C=rand(1,m);
C
N=rand(n,1)*m;
N
pause
[SM,X] = maxf(n,m,A,U,C,N)
return
% Программа символьного умножения двух логических
% выражений, характерных при символьных подстановках
% одних алгебраических уравнений в другие с приведением% подобных
членов
function [B1,SS]=spis1(B,S)
delete spis1
diary spis1
%
B=[1 2
%
3 4
%
5 7
%
5 8]
%
%
%
S=[1 2
3 4
5 8]
SS=S;
c1=0;
M=size(B)
N=size(S)
for i=1:M(1)
for j=1:N(1)
i
j
for k=1:N(2)
%
%
%
%
if S(j,k)>0
SR(1,k)=S(j,k)
else
SR(1,k)=[];
end
end
SR
K=size(SR)
82
%
%
%
k1=K(1)
k2=K(2) ;
if k2==M(2)
c=all(B(i,:)==SR(1,:));
c1=c1+c;
if c>0
B1(i,1)=j;
B1(i,2)=0;
end
end
end
if c1==0
for l=1:M(2)
S1(1,l)=B(i,l);
B1(i,1)=N(1)+1;
B1(i,l+1)=0
end
SSS=[SS
S1];
SS=[];
SS=SSS;
end
c1=0;
end
B1
Комплекс программ расчета вероятности логической функции
по заданным значениям вероятностей базисных переменных
Комплекс программ включает в себя следующие программы:
Программа 1. Verrr.m – Расчет вероятности логической функции
(ЛФ) по заднным значениям вероятностей базисных переменных.
Программа 2. Ver3.m – Приближенный расчет вероятностей ЛФ
по заданным значениям вероятностей базисных переменных при
их большом количестве
Программа 3. Ver4_1.m – Расчет графиков функции вероятности ЛФ. P = f(M) при фиксированных значениях числа логических
слагаемых k = 10,20, ..., 50
Программа 4. Ver5.m – Расчет трехмерного графика функции вероятности ЛФ от двух аргументов: числа логических слагаемых-k,
и их вероятности-M
Программа 5. Sxi(n,k,m) – Определение индексов m-элемента
k-элементного подмножествамножества {1, ..., n},при представлении этого подмножества в лексикографическом порядке
Программа 6. Si1(n,m) – определение индексов m-элемента фундаментального вектора множества {1, ..., n} и числа k k-элементного
83
подмножества , к которому принадлежит этот элемент, при представлении всего множества в лексикографическом порядке
Программа 7. Is(n,Sk) – определение порядкового номера элемента фундаментального вектора по заданным индексам элементов
базисного вектора.
Программа 8. C5.m – Искючение из вектора f, представляющего
собой упорядоченный по возрастанию набор целых чисел, повторяющихся элементов
Программа 9. not1(sk,pf) – учет логических переменных со знаком отрицания
Программа 10. soch(n,i) – определение числа элементов k-элементного подмножества множества {1, ..., n}
Программа 11. V.m – ввод исходных данных для Программы 1.
Verrr.m
Программа 12. Da.m – ввод исходных данных для Программы
2. Ver3.m
%delete vvv.lx
%diary vvv.lx
clear all
%Программа расчета вероятности логической функции по заданным
%значениям вероятностей базисных переменных
%
v % ввод исходных данных
% Вводятся матрица D(j,max(kk)) и вектор kk.
%j – число строк D (совпадает с числом слагаемых ЛФ”)
%kk – вектор, элементами которого являются числа, определяющие
%количество логических переменных в каждом слагаемом. Отрица% тельные значения чисел в матрице D означают отрицания логи% ческих переменных
rr=(2^j)-1 % число слагаемых в выражении для вероятности
% логической функции
P=0;
n=j
%bi %смена директории
for t=1:rr,
t ; %номер слагаемого в выражении для вероятности
% логической функции
%”функция si1(n,t)- определение индексов A i-элемента фунда%ментального вектора функции вероятности множества {1,...,j}
%и числа k элементов подмножества (номер группы), к кото%рому принадлежит этот элемент, при представлении всего
%множества в лексикографическом порядке
%bi1
[A,k]=si1(n,t);
DD=D(A,:);
84
DD=DD(:);
ds=sort(DD);
ds1=c5(ds);
ik=find(ds1);
sk=ds1(ik);%вектор номеров компонентов базисного множества Л”
%для i-го элемента фундаментального вектора функции
%вероятности, указывающий, что в соответствии с
% этими номерами, заданные в векторе ps исходные
% значения вероятности должны быть арифметически
%перемножены. Отрицательные значения номеров компо%нентов означают отрицания соответствующих им ЛП.
%”функция not1(sk,pf) вычисляет значение этого про%изведения обозначенного как pf1. Переменная z яв%ляется индикатором, указывающим, что в векторе sk
%содержатся компоненты с одинаковыми по абсолютно%му значению номерами, но разными знаками, поэтому
%для этого случая pf1=[] и соответственно sps=0.
[z,pf1]=not1(sk,pf);
if z>=1,
sps=0;
else
sps=((-1)^(k+1))*prod(pf1);
end
P=P+sps;% “функция вероятности ЛФ”
ps(t)=sps;
ver(t)=P;
T(t)=t;
end
format long
diary vvv.lx
ps
P
PP=P*ones(1,rr)%Значение вероятности ЛФ», введенное для изоб%ражения на графике асимптоты, к которой
%стремится процесс P(t)=ver(t)
format
diary off
%ma
subplot(212)
plot(T,ver,’k’,T,ps,’k’,T,PP,’k’)
ylabel(‘Функции вероятности’)
%xlabel(‘m-номер слагаемого в выражении для функции вероятности
TL ‘)
text(7,-0.4,’sps(m)’)
text(5.5,1.6,’P=sum(sps) ‘)
%text(2,0.6,’вероятность ЛФ ‘)
text(2,-1.6,’m-номер слагаемого функции вероятности’)
%text(6,-2.,’рис. ‘)
text(12,0.5,’P=0.81132’)
85
grid
axis(‘normal’)
end
echo off
clear all
%Программа приближенного расчета вероятностей логических
%функций (ЛФ) по заданным значениям вероятностей базисных
%переменных при их большом количестве
for n=10:10:50,
j=n;
R=0;
%число базисных переменных
for pfi=0.0:0.02:0.2,
pf =pfi*ones(1,j); %вектор вероятностей слагаемых ЛФ
R=R+1
%ma
% Определение среднего значения и дисперсии вектора вероят%ностей отдельных слагаемых ЛФ
mo=mean(pf);
% bi
% Определение вектора числа слагаемых в каждой группе k-эле
%ментных подмножеств при вычислении вероятности ЛФ
for i=1:j,
ch(i)=soch(n,i);
end
format long
ch;
P=0;
for k=1:j,
sps=((-1)^(k+1))*(mo^k)*ch(k);
P=P+sps;
end
M(R)=pfi
PP(R)=P
end
%cl2=clock;
%time=cl2-cl1
hold on
subplot(212)
plot(M,PP)
% xlabel(‘M – среднее значение вероятностей слагаемых ЛФ’)
ylabel(‘Вероятность ЛФ P’)
%xlabel(‘M’)
ax=axis;
ax1=-0.5*ax(4)
ax2=1.1*ax1
ax3=1.2*ax1
86
ax4=1.3*ax1
ax5=1.5*ax1
% w1=’ Значения вероятностей ЛФ P=f(k,M)’
text(0.21,0,’M’)
text(0.01,0.85,’k=50’)
text(0.075,0.7,’k=20’)
text(0.125,0.65,’k=10’)
%text(0,ax4,w1)
ris=’рис.’
nn=’5’
s1=[ris nn]
text(0.09,-0.2,s1)
%ma
grid
end
hold off;
return
echo off
%delete ver2.lx
%diary ver2.lx
cl1=clock
%Программа расчета вероятности логической функции по заданным
%значениям вероятностей базисных переменных при их большом
% количестве
da
%m
% Определение мат. ожидания и дисперсии вектора вероятностей
% отдельных слагаемых ЛФ
mo=mean(pf)
%bi
% Определение вектора числа слагаемых в каждой группе k-эле% ментных подмножеств при вычислении вероятности ЛФ
n=j;
for i=1:j
ch(i)=soch(n,i);
end
format long
ch
P=0
for k=1:j
sps(k)=((-1)^(k+1))*(mo^k)*ch(k);
P=P+sps(k)
ps(k)=P
N(k)=k
end
sps
ps
cl2=clock;
cl1(6)
87
cl2(6)
time=cl2-cl1
disp(‘время счета’)
disp(time(1,5:6))
diary off
mn=max(N)
x= 0.5*mn
yps=ps(mn)+0.2*max(abs(ps))
ysps=sps(mn)-0.1*max(abs(sps))
ksps=-max(abs(sps))
subplot(212)
plot(N,ps,’k’,N,sps,’k’)
xlabel(‘Номер группы -k ‘)
ylabel(‘Функции вероятности ЛФ’)
%text(10,1,’ps’)
text(x,ysps,’sps’)
ps1=[0 ps]
ps2=[ps ps(mn)]
ps3=ps1-ps2
ss=min(find(abs(ps3)<=0.01*ps(mn)))
ss1=sprintf(‘%g’,ss)
ax=axis
if mm1==1,
ax1=4*ax(3)
else
ax1=2*ax(3)
end
ax2=1.15*ax1
ax3=1.2*ax1
ax4=1.3*ax1
ax5=1.4*ax1
w1=’Как видно из графиков, число групп, необходимых для точного’
w2=’расчета вероятности ЛФ, не превышает k=’
w3=[w2 ss1]
text(0,ax4,w1)
text(0,ax5,w3)
text(x,yps,’ps=sum(sps)’)
z1=’, n=’
z2=sprintf(‘%g’,n)
z3=’, M=’
z4=sprintf(‘%g’,pfi)
z5=[z1 z2 z3 z4]
ris=’ ’
aa=mm1+1
nn=sprintf(‘%g’,aa)
s1=[ris nn]
text(x,ax1,s1)
s2=’Вероятность ЛФ. P = lim(ps(k)) =’
s3=sprintf(‘%g’,ps(mn))
s4=[s2 s3 z5]
88
text(0.,ax2,s4)
%text(0.5*x,ax3,z5)
%text(0.5*x,-11,s)
%ma
grid
MAP=HSV;
[rov,col]=size(MAP);
MAP=ones(rov,col);
colormap(MAP);
%bi
%clear
%bi
%bi1
return
echo off
clear all
%Программа расчета вероятности логической функции по заданным
%значениям вероятностей базисных переменных при их большом
% количестве
da;
q=1;
nn=10;
mm=0.02;
for n=nn:nn:10*nn,
for pfi=mm:mm:10*mm,
j=n;
pf=pfi*ones(1:size(j));
%ma;
% Определение мат. ожидания и дисперсии вектора вероятностей
% отдельных слагаемых ЛФ
mo=mean(pf);
M=mo;
% bi;
% Определение вектора числа слагаемых в каждой группе k-эле% ментных подмножеств при вычислении вероятности ЛФ
j=n;
for i=1:j
ch(i)=soch(n,i);
end
ch;
P=0;
for k=1:j
sps(k)=((-1)^(k+1))*(mo^k)*ch(k);
P=P+sps(k);
ps(k)=P;
N(k)=k;
end
89
sps;
ps;
mn=max(N);
ps1=[0 ps];
ps2=[ps ps(mn)];
ps3=ps1-ps2;
ss=min(find(abs(ps3)<=0.01*ps(mn)));
zz(q,:)=[n M P ss];
q=q+1;
end
end
x=zz(1:nn:10*nn,1);
y=zz(1:nn,2);
jj=1;
for i=1:nn,
z(:,i)=zz(jj:nn*i,3);
jj=jj+nn;
end
%subplot(211);
text(20,0,-0.05,’Число слагаемых ЛФ – k’);
%ylabel(‘M’);
text(101,0.21,0.15,’M’)
%zlabel(‘число групп слагаемых вероятности TL’);
zlabel(‘Вероятность ЛФ’);
%text(0,0,-1,’рис. число групп слагаемых, которое нужно’)
%text(0,0,-1.1,’удерживать
при
расчете
вероятности
ss=f(N,M)’)
text(90,0,-0.2,’рис.‘)
TL
view(30,10);
% MAP=HSV;
% [rov,col]=size(MAP);
% MAP=ones(rov,col);
% colormap(MAP);
grid
mesh(x,y,z);
%ma;
%bi;
return
Sxi(n,k,m) – Программа-функция определения индексов m-элемента kэлементного подмножества множества {1, ..., n} при представлении
этого подмножества в лексикографическом порядке
% Программа-функция определения индексов m-элемента
% k-элементного подмножества множества {1, ..., n},
% при представлении этого подмножества в лексикографическом
% порядке
function [A] = sxi(n,k,m)
% m не должно превышать C
90
% C – число сочетаний (k) из (n)
% C=n!/k!*(n-k)!
% f1=1:n
% f2=1:k
% f3=1:(n-k)
f1=1:n;
f2=1:k;
f3=1:(n-k);
if k>n,
‘ошибка – k не может быть больше n’
break
end
if k>=n & m>=2,
‘ошибка – при k=n, m=1’
break
end
if k==n,
C=1;
else
C=prod(f1)/(prod(f2)*prod(f3));
end
if(C>1) & (m>C),
‘m превышает допустимое значение m>C ‘
C;
break
else
end
A=[1:k];
r=2;
p=k;
while p>=1,
if A(k)==n,
p=p-1;
else
p=k;
end
if p>=1,
for i=k: -1: p,
A(i)=A(p)+i-p+1;
end
end
if m<=1,
A=[1:k];
break
end
if r==m,
A;
break
else
r=r+1;
91
end
end
diary off
return
% Программа-функция определения индексов m-элемента фунда% ментального вектора множества {1,...,n} и числа k % k-элементного
подмножества , к которому принадлежит этот
% элемент, при представлении всего множества в лексикографи% ческом порядке
function [A,k] = si1(n,m)
if m<=n,
k=1;
A=m;
break
end
R=n;
for i=2:n,
C=soch(n,i);
R=R+C;
if m<=R
k=i;
j=m+C-R;
A=sxi(n,k,j);
break
else
end
end
return
% Программа определения порядкового номера элемента фундамен% тального вектора по заданным индексам элементов базисного
% вектора
function [Is,k]=is(n,Sk)
[m,k] = sk(n,Sk);
Is=m;
if k<=1,
break
else
for i=1:k-1,
C=soch(n,i);
Is=Is+C;
end
end
return
%Программа исходных данных для расчета вероятности
%логической функции по заданным значениям вероятностей
%базисных переменных при большом их количестве
echo on;
92
mm1=’назовите номер набора данных для расчета вероятности ЛФ’;
mm1=input(‘m=’);
echo off;
mm1;
n=41;
j=41;
D=[1:j];
D=D(:);
if mm1==1,
pfi=0.01;
else
end
if mm1==2,
pfi=0.05;
else
end
if mm1>=3,
pfi=0.3;
else
end
pf =pfi*ones(1,j);
return
function [f,n]=c5(f)
% Исключение из вектора f, представляющего собой
% упорядоченный по возрастанию набор целых чисел
% повторяющихся элементов
n=length(f);
j=1;
for i=1:n,
if j>=n,
break
end
z= (f(j+1) – f(j));
if z<=0,
f(j)=[];
n=length(f);
else
j=j+1;
end
end
end
function [z,pf1]=not1(sk,pf) % программа-функция учета отрицательных значений логических
% переменных
% Определение вектора номеров ЛП, значения которых меньше -1
qk=find(sk<=-1);
lq=length(qk);
qt=abs(sk(qk));
kt=length(sk);
93
if lq<=0,
pf1=pf(sk);
z=0;
else
for i0=1:lq,
for i1=1:kt,
if sk(i1)==qt(i0),
z=1;
pf1=[];
break
else
z=0;
end
end
end
x=pf(abs(sk));
x(qt)=[];
y=1-pf(qt);
pf1=[x,y];
end
return
function [C]=soch(n,i)
% Подпрограмма-функция определения числа элементов k-элемент- %
ного подмножества множества {1,...,n}
% Число элементов С определяется как число сочетаний из n по
% k. C=n!/i!*(n-i)!
% f1=1:n
% f2=1:i
% f3=1:(n-i)
f1=[1:n];
f2=[1:i];
f3=[1:(n-i)];
C=prod(f1)/(prod(f2)*prod(f3));
Return
% echo off
% delete v.lx
% diary v.lx
mydata1 % m-файл ввода исходных данных
ma % m-файл с командой перехода в директорию
%jj=1;
%k=0;
D=0;
for i=1:j,
A=[eval([‘f’,int2str(i)])]
kk(i)=length(A)
D(i,1:kk(i))=A
end
% jj=k+1;
%k=k+kk(i);
94
%for ii=jj:k,
%B(1,ii)=A(ii+1-jj);
kk
%kk – вектор, элементами которого являются числа, определяющие
%количество логических переменных в каждом слагаемом.
D;% матрица строк [f1
% f2
% .
% .
% fj]
% при неравном числе элементов в строках fi, матрица D до% полняется нулями в конце каждой строки
% B = <f1,f2,...,fj> – вектор-строка
return
95
Учебное издание
Дубаренко Владимир Васильевич
Коновалов Александр Сергеевич
Кучмин Андрей Юрьевич
ОПТИМИЗАЦИЯ
ДИНАМИКИ СИСТЕМ ПРИ УПРАВЛЕНИИ
В НЕСТАЦИОНАРНЫХ УСЛОВИЯХ
Учебное пособие
Редактор Г. Д. Бакастова
Верстальщик С. Б. Мацапура
Сдано в набор 11.06.08. Подписано к печати 30.09.08.
Формат 60×84 1/16. Бумага офсетная. Печать офсетная.
Усл.-печ. л. 5,58. Уч.-изд. л. 5,75. Тираж 150 экз. Заказ № 622
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
Документ
Категория
Без категории
Просмотров
11
Размер файла
1 221 Кб
Теги
dubarenko
1/--страниц
Пожаловаться на содержимое документа