Исследование линейных дискретных систем, заданных интервальными характеристическими матрицами тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

САМОЙЛОВ Виктор Геннадьевич

ИССЛЕДОВАНИЕ ЛИНЕЙНЫХ ДИСКРЕТНЫХ СИСТЕМ, ЗАДАННЫХ ИНТЕРВАЛЬНЫМИ ХАРАКТЕРИСТИЧЕСКИМИ МАТРИЦАМИ

Специальность 01.01.09 — дискретная математика и математическая кибернетика

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

чЬ

Саратов — 2004 Ч

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

Научный руководитель: Официальные оппоненты:

доктор технических наук, профессор Сперанский Дмитрий Васильевич

доктор технических наук, профессор

Панкратов Владимир Михайлович

кандидат физико-математических наук, доцент

Богомолов Сергей Анатольевич

Ведущая организация:

Институт проблем управления РАН, г. Москва

Защита состоится " & " ^ьУ-хЪ^А. 2004 г. в /ч. мин. на заседании диссертационного совета К 212.243.02 по присуждению ученой степени кандидата физико-математических наук при Саратовском государственном университете им. Н.Г. Чернышевского по адресу: 410012, г. Саратов, ул. Астраханская, д 83, механико-математический факультет.

С диссертацией можно ознакомиться в библиотеке Саратовского государственного университета им. Н.Г. Чернышевского

Автореферат разослан 2004 г.

Учёный секретарь диссертационного совета, кандидат физ.-мат. наук, доцент

Корнев В.В.

ОБЩАЯ ХАРАКТЕРИСТИ КА РАБОТЫ

Актуальность темы.

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

Один из интересных классов автоматов носит название линейных автоматов. Автоматы этого класса сочетают в себе свойства линейных систем и конечных автоматов. Они имеют большое прикладное значение.

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

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

Цель работы. Цель работы состоит в исследовании линейных автоматов, заданных интервальными характеристическими матрицами, а также линейных автоматов с интервальным выходом.

В соответствии с целью исследования были поставлены следующие конкретные задачи:

1. Ввести интервальную арифметику над полем GF(p).

2. Исследовать свойства интервальных операций.

3. Найти метод решения системы линейных алгобремпоокшс уравнений

РОС. НАЦИОНАЛЬНАЯ ( БИБЛИОТЕКА [

с интервальной правой частью над полем GF(p).

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

5. Предложить метод синтеза линейных автоматов для упрощения решения задачи распознавания.

6. Найти способ построения диагностической последовательности для линейного автомата с интервальным выходом.

7. Предложить методы решения диагностической задачи для линейного автомата с интервальным выходом.

Методы исследования. В работе используются теоретико-автоматные и алгебраические методы, а также методы интервального анализа, теория графов, теория экспериментов с автоматами, эволюционные вычисления. Новые научные результаты и положения, выносимые на защиту.

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

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

Исследования по теме диссертации выполнены в 2001-2004 гг. и проводились в рамках следующих грантов:

• Грант РФФИ № 01-01-00080, проект "Задачи и методы анализа взаимодействующих автоматов" (2001-2003 гг.).

• Грант Минобразования РФ, проект "Разработка методов анализа и синтеза экспериментов с линейными и билинейными системами" (2001-2002 гг.).

Апробация работы. Результаты диссертации докладывались и обсуждались на международной конференции "Компьютерные науки и информационные технологии" памяти A.M. Богомолова (Саратов, 2002 г.), 15-й, 1б-й и 17-й международных научно-технических конференциях "Перспективные системы управления на железнодорожном, промышленном и городском транспорте" (Алушта, Украина, 2002-2004 гг.), межвузовской научной конференции "Компьютерные науки и информационные технологии" (Саратов, 2004 г.), II международной научно-технической конференции "Восток-Запад. Проектирование и диагностика" (Харьков, 2004 г.).

Публикации. По результатам диссертации опубликовано 9 работ, из которых [1, 2, 5, 6, 8, 9] в соавторстве, остальные самостоятельно. В работах [1, 8] опубликованы результаты совместной разработки интервальной арифметики над полем GF{p). В работе [2] диссертантом описана собственная разработка программной системы, позволяющей проводить интервальные вычисления над полем GF(p). В работах [5, б, 9] диссертантом доказано обобщение теоремы для решения систем уравнений с интервальными правыми частями (случай мультиинтервалов), описан способ построения диагностической последовательности для интервальной диагностической задачи, приведен новый метод решения интервальной диагностической задачи для линейных и билинейных автоматов с использованием генетического алгоритма.

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность исследуемой проблемы, сформулированы цель и задачи диссертационной работы, перечислены полученные в диссертации новые результаты, их практическая ценность, представлены положения, выносимые на защиту и описана структура диссертации.

В первой главе диссертации рассматривается интервальная арифметика над полем GF(p).

В разделе 1.1 введены определения правильных, неправильных, вырожденных и обычных интервалов над полем GF(p).

Каждый элемент поля = {0,1,... ,р — 1} представляет собой

класс вычетов по модулю р. Выберем из каждого класса вычетов одного представителя, являющегося минимальным целым неотрицательным числом. Введем на множестве этих представителей порядок как на множестве целых чисел. Для полученного упорядоченного множества {0,1,..., р — 1} сохраним ранее использованное обозначение GF(p).

Определение 1.1 Подмножество а С такое, что а = [а, о] =

{а | а<а<а;а,аЕ ОР(р)} называется правильным интервалом, паи а - соответственно его нижней и верхней границами.

Определение 1.2 Интервал вида Ъ = [6, Ь], где

Ь > Ь, будем интерпретировать как множество СР(р)\ [5+1,6-1], где \ - операция разности в теоретико-множественном смысле. Интервалы такого вида называются неправильными.

Определение 1.3 Интервал вида [а, а), где а— а, называется вырожденным и интерпретируется как элемент поля GF(p).

Определение 1.4 Все правильные, неправильные и вырожденные интервалы называются обычными интервалами.

Конечность поля GF(p) позволяет рассматривать интервалы над полем GF(p) как множества элементов этого поля.

Определение 1.5 Два интервала а = [а,а] иЬ = [6,5] называютсярав-ными (и записывается это как а = Ь), если они равны в теоретико-множественном смысле.

Далее вводятся основные арифметические операции над обычными интервалами:

Определение 1.6 Пусть ® € {©,©,©,0} - бинарная арифметическая операция над элементами поля GF(p). Если а,Ь - обычные интервалы, то

определяет бинарную арифметическую операцию над обычными интервалами. (В случае деления предполагаем, что 0 ^ Ь).

Результатом операции наддвумя обычными интервалами может оказаться множество элементов поля GF(p), которое не будет являться обычным интервалом. Такие множества назовем мультиинтервалами.

Определение 1.7 Подмножество А С GF(p) такое, что

где щ - обычный интервал, I - конечное множество индексов и для г ф э, щ П о;- = 0, называется мулътиинтервалом поля GF(p).

Множество всех мультиинтервалов обозначим как IGF(p). Введем бинарные операции над мультиинтервалами.

Определение 1.8 Пусть * 6 {+,—,'1/} - бинарная операция. Если где - обычные интервалы поля GF(p), то

В разделе 12 изучаются свойства арифметических операций в ^(р).

Введем понятие ширины мультиинтервала

и обычного интервала x¡ = обозначаемой далее как wid(X) и

(»¿) соответственно:

"с1( ■) ^ — 21 если хг ~ правильный интервал,

Понятно, что 'тс1 (ж,) и wid (.У) - это число элементов в соответствующих интервалах. Очевидно также, что (ж») —ЩОХг + 1 для обычных интервалов.

Пусть а = [а,а],Ь = [¿>,6] - обычные интервалы поля тогда

для сложения интервалов справедлива следующая формула:

| [йФЬ,аф6], если \\rid (а) + wid (Ь) < р,

Ряд свойств введенных операций сформулирован в виде следующей теоремы.

Теорема 1.1 Пусть А, В, С е ^GF(p), тогда

1. А + В = В + А, А - В = В • А (коммутативность);

2. (А + В) + С = А + {В + С), (.А-В)С = А{ВС) (ассоциативность);

3. (VА е /сад) А = А + [0,0] = [0,0] + А, А = А ■ [1,1] = [1,1] • А,

т.е. [0,0] и [1,1] являются единственными нейтральными элементами для сложения и умножения соответственно;

4- ЮЕ(р) не имеет делителей нуля;

5. Произвольный невырожденный интервал из ЮР(р) не имеет обратного ни по сложению, ни по умножению, но 0 6 А — А, 1 € А/А;

6. А - (В + С) С А- В + А- С (субдистрибутивность);

7. (А + В) = А А + А В, где А € С-^Хр) (дистрибутивность умножения на число относительно сложения);

10. «гк! (а + Ь) = илё (о — Ь) = \vicl (а) + wid (Ь) — 1, если а,Ъ - обычные

В разделе 1.3 рассматриваются множества решений уравнений вида

зависящих от некоторых параметров (А\,...,Аа)Т = А, где А^В € г = 1,5, /(А,Х) - рациональное выражение, состоящее из интервалов А, X, соединенных знаками арифметических операций.

Определение 1.9 Назовем формальным решением уравнения (1.4) такой мулътиинтервал X € ЮР{р), что при его подстановке в (1.4) получается точное равенство.

Определение 1.10 Назовем объединенным множеством решений уравнения (1-4) следующее множество элементов:

Хээ = {£ е I (За € А)(Б/3 € В) Да, О = 0}.

Определение 1.11 Назовем допустимым множеством решений уравнения (1-4) следующее множество:

Хуэ = {£ € ОР{Р) I (Уа б А)(3/3 е В) /(а, 0 = /?}•

Определение 1.12 Назовем управляемым множеством решений уравнения следующее множество:

X* = € | (V/? 6 -В)(За € А) Да, О = /3}.

Теорема 1.2 Линейное уравнение а + X = Ь, где а^ - обычные интервалы над полем GF(p), имеет формальное решение X в виде мультиин-тервала тогда и только тогда, когда

Для уравнения

А + Х = В (1.5)

*ээ= и С) (0&<*) = В-А, (1.6)

аеАреВ аеА Рч В

П и (0®а)> (1-8)

реВаеА

Для уравнения

А В, где 00 А, (1.9)

множества решений определяются аналогично:

Хзз= 1] [](0<г>а) = В/А, (1.10)

а

еАреВ

п и 00"). (1Л1)

аеАреВ /ЗеВ аеА

Равенства (1.6)-(1.8), (1.10)-(1.12) следуют из определения множеств ХЭЗ) -Худ, Хл и определения операций и и П> понимаемых в обычном смысле как операции объединения и пересечения множеств соответственно.

Теорема 1.3 Все множества решений уравнений А + Х=*ВиА-Х = В и формальное решение, если оно существует, включаются в объединенное множество решений, т.е. в В — А для уравнения А + X = В и в В/А для уравнения А - X = В.

В разделе 1.4 описана программная реализация интервальной арифметики.

Для программной реализации интервальной арифметики над полем GF(p) была использована система компьютерной алгебры Maple версии 6. В программе реализованы основные интервальные операции (сложение, вычитание, умножение, деление, умножение на число) над мультиинтер-валами и обычными интервалами. Программа содержит также ряд вспомогательных функций для работы с интервалами: нахождения ширины интервала, пересечения и объединения интервалов, нахождения обратного интервала по сложению, нахождения "внешнего" интервала, определения типа обычного интервала (правильный, неправильный, вырожденный), преобразования интервала во множество элементов поля GF(p) и обратно, проверки равенства двух интервалов и т.д. Дополнительно к интервальным операциям в программе есть функции решения уравнений А+Х = В,

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

В разделе 1.5 приведен метод решения систем уравнений с интервальной правой частью.

Рассмотрим систему уравнений с интервальной правой частью:

где - матрица, элемента-

ми которой являются элементы поля

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

Введем обозначения:

/О, если i ф к -— . -— I 1, если г— к

В = [ВиВ2,...,Вп]т, где Bi = аи af € Ви VA € В, (а; < А), i — 1,п.

Теорема 1.4 Пусть (fi,.. . решение системы:

АС = В, (1.14)

(dp',..., 6п^)т - решения систем:

Тогда решение х = (xi,.,.., х„) системы (1.13) имеет вид

где В^ + Шк £ Вк, т.е. тк пробегают независимо все значения от 0 до р—1, при этом из них точно wid (Вк) удовлетворяют этому условию.

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

Далее приводится ряд определений и теорем, связанных с задачей распознавания конечных детерминированных автоматов, сформулированных Муром и Гиллом в своих работах.

Определение 2.1 Автомат является распознанным, если определена (с точностью до изоморфизма) его минимальная форма путем измерений на его внешних выводах. Будем также говорить, что автомат распознаваем, если он может быть распознан независимо от его начального состояния.

Теорема 2.1 Автомат Мнераспознаваем, если заранее не известен полностью его входной алфавит.

Теорема 2.2 Автомат М нераспознаваем, если предварительно не известно максимальное число состояний минимальной формы этого автомата.

Определение 2.2 Класс автоматов {Mj, М?,..., Мдт}, N > 1,называ-

ется исключительным, если ни одно состояние любого автомата не эквивалентно никакому состоянию автомата

Теорема 2.3 Известно, что заданный автомат М принадлежит конечному классу автоматов М = {М\, Мг,..., Л/дг}. Необходимое идостаточ-ное условие распознавания автомата М состоит в том, чтобы М был исключительным классом.

Теорема 2.4 Если Rn,m,p есть класс всех сильно связанных (п, т, р)-машин в приведенном виде, то существует простой эксперимент длины самое большое " ^ г , проведениемкоторогосэкземпляромпроизвольного элемента Sиз Ип^гп^р можно установить отличимость S от всех других элементов из Rnjmj>.

Следствие 2.1 О заданном автомате М известно, что он принадлежит исключительному классу автоматов {М\, М2,..., Mjv}, где каждый автомат имеет не более п состояний. Тогда автомат Мможет быть распознан простым безусловным экспериментом длины I, где I <

В разделе 2.1 приводится постановка задачи.

Пусть линейный автомат функционирует согласно следующим уравнениям:

где А = \dij\nxni В = [bij]nxj - характеристические матрицы, а входной вектор u(t), выходной вектор y(t) и вектор-состояние s(t) представляют собой упорядоченные наборы u(t) = [ui(t)u2(t).. ■ «¡(¿)]г, y{t) =

- знак транспонирования).

Величину принято называть размерностью линейного автомата.

Когда речь идет о линейных автоматах, то предполагается, что элементами характеристических матриц являются элементы поля GF(p), где р - простое число. В данной главе рассматриваются линейные автоматы, у которых элементами характеристических матриц являются мультиинтер-валы над полем GF(p).

Пусть известны интервальные матрицы являются

оценками матриц Л, В соответственно. Тогда А £ А', В 6 В'.

Требуется путем проведения эксперимента над автоматом найти матрицы Л, В.

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

Формулируется алгоритм для решения задачи распознавания конечного детерминированного автомата А на основе восстановления таблицы переходов и выходов.

Алгоритм 2.1 Установим автомат в состояние вх (в1 6 Б), подадим н а вход символах (#1 £ X), н а выходе наблюдаем реакцию (у £ Уу и определяем новое состояние 5 (а £ 5). Таким образом, будет получена одна строка в таблице переходов и выходов автомата. Действия, которые были выполнены для получения этой строки в таблице переходов и выходов, являются элементарным шагом алгоритма. Выполняя эти действия для всех состояний и всех входных символов автомата, получим таблицу переходов и выходов автомата и, таким образом, решим задачу распознавания автомата.

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

Определение 2.3 Входная последовательность р = х\хг называется установочной для автомата А,

Определение 2.4 Входная последовательность р — Х\Х2 называется диагностической для автомата А,

Определение 2.5 Входная последовательность р = Х1Х2 называется синхронизирующей для автомата А,

6 5 фьр) = ¿(52, р).

Во всех этих определениях функция переходов и функция выходов А расширены на входные последовательности так, как это традиционно делается в теории автоматов.

Далее рассматриваются синхронизируемые автоматы.

... хк

если

... хк

если

... хк

если

Определение 2.6 Линейный автомат называется синхронизируемым, если у него существует синхронизирующая последовательность.

Лемма 2.1 Установка синхронизируемого линейного автомата в нулевое состояние может быть осуществлена простым безусловным экспериментом длины п, где п - размерность автомата.

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

Теорема 2.5 Пусть автомат А задан уравнениями (2.16) - (2.17). Если автомат является синхронизируемым то автомат

может быть распознан в классе синхронизируемых линейных автоматов размерности п простым условным экспериментом порядка 2 и длины v,

- размерность автомата

Теорема 2.6 Пусть автомат А задан уравнениями (2.16) - (2.17) и известны интервальные матрицы А' и В'. Если для любых матриц А 6 А!

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

В разделе 2.3 рассматриваются вопросы построения автоматов специального вида для упрощения решения для них задачи распознавания.

Предложен метод построения такого автомата специального вида для заданного линейного автомата.

Теорема 2.7 Для любого синхронизируемого линейного автомата А, заданного с помощью уравнений (2.16) - (2.17), можно построить линейный автомат В, для которого задача распознавания в классе синхронизируемых линейных автоматов размерности п решается путем проведения простого условного эксперимента порядка где

v < (2п + l)(n + 1) +1, п - размерность автомата А.

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

В разделе 3.1 приводится формулировка задачи.

Объектом исследования является линейный автомат над полем заданный уравнениями переходов и выходов:

s{t + 1) = As(t) + Bu(t), (3.18)

y(t) = Cs{t) + Du(t), (3.19)

где A = [ац]„хп) В - [b4]Tlxi. С = [c,j]mxn, D = [dtJ]mw - так называемые характеристические матрицы, элементы которых предполагаются заданными в виде точных значений величин из поля а входной вектор u(t), выходной вектор y(t) и вектор-состояние s(i) представляют собой упорядоченные наборы u(t) = fiti(i), W2{i),..., Ui(t)]T, y(t) = [yi(t),y2{t),--->ym{t)}T, S(t) = [sl{t),S2(t),...,Sn(t)]T.

Величину п принято называть размерностью линейного автомата

Пусть линейный автомат задан уравнениями (3.18)—(3.19) и пусть известно множество допустимых начальных состояний, в одном из которых находится рассматриваемый линейный автомат. Задача нахождения неизвестного начального состояния называется диагностической.

Далее предполагается, что линейный автомат является минимальным.

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

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

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

которого, линейный автомат порождает в каждый момент времени t выходной вектор, координаты которого принадлежат интервальному вектору (3.20). Заметим, что как и классическая диагностическая задача, интервальная диагностическая задача либо имеет единственное решение, либо не имеет решения.

В разделе 3.2 описан способ построения диагностической последовательности для решения диагностической задачи в интервальной постановке.

В разделе 3.3 приводится алгебраический метод решения диагностической задачи в интервальной постановке.

Выходная последовательность, выдаваемая линейным автоматом в ответ на входную последовательность u(0),u(l),... ,и(к), может быть вычислена по формуле полной реакции:

Здесь - начальное состояние линейного автомата, которое в диагностической задаче является целью поиска. При этом исходной информацией для его поиска служит диагностическая последовательность и наблюдаемая в процессе проведения эксперимента с линейным автоматом выходная последовательность у (0), 2/(1), • •. ,i/(fc). Используя формулу (3.21), сформируем систему линейных алгебраических уравнений, где неизвестными являются координаты искомого начального состояния s(0) = [si(0), йг(0),..., s„(0)]T:

Поскольку выходные реакции представляют собой

интервальные вектора, то правые части системы (3.22) также являются интервальными векторами, тогда как матрица системы (3.22) является точной.

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

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

Простой генетический алгоритм использует операторы отбора (селекции), скрещивания (кроссинговера) и мутации. Механизм этого алгоритма несложен, и ниже кратко описаны его этапы:

1. Генерация случайной популяции, состоящей из N хромосом, длина каждой из которых равна (каждая хромосома - кандидат на роль решения задачи). Эта начальная популяция образует поколение с номером 0.

2. Вычисление функции приспособленности для каждой хромосомы в популяции.

3. Выполнение следующих шагов, пока не будет получено N потомков:

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

(Ь) С вероятностью рс (вероятность кроссинговера) производится кроссинговер пары в произвольно выбранной точке (одноточечный кроссинговер), которая выбирается с равномерно распределенной вероятностью, и формируются два потомка. Если кроссинговер не производится, то формируются два потомка, которые являются точными копиями родителей.

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

помещаются в новую популяцию.

Если N нечетное и количество потомков равно N1-1, то один произвольно выбранный потомок удаляется из новой популяции.

4. Текущая популяция замещается новой популяцией с увеличением номера поколения.

5. Если номер текущего поколения меньше заданного максимального числа поколений, то переход на шаг 2, иначе окончание алгоритма.

Каждому допустимому решению 5 сопоставим битовую строку, представляющую собой хромосому. Сопоставление осуществим следующим образом: каждому элементу вектора й = [вь 82,..., 5„]т поставим в соответствие число в двоичной системе (битовую строку), которое равно числу (г = 1,п) в системе счисления с основанием р. Допустимому решению в будет соответствовать битовая строка, являющаяся объединением п битовых строк, полученных для каждого элемента вектора. Такая схема сопоставления является взаимнооднозначной, что позволяет проводить как кодирование, так и декодирование хромосомы.

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

Пусть в == $2,..., 5„]г - решение, которое необходимо оценить. Так как это решение представляет собой предполагаемое начальное состояние, то получаем в(0) = й. Осуществляя подстановку а(4) в систему уравнений

равно длине диагностической последовательности, получим набор из 1„шх + 1 выходных векторов размерности ТП: ус(0), ус(1), ..., Ус^тах)-

Целевую функцию определим следующим образом: £2(в) =

Е ЯМ)),

4=0

где

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

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

^тах

£?(*) = £№(*)), (3.24)

4=0

где

ЧУсЦ)) = 1 -

аы<))

(3.25)

т,(р — 1)

Таким образом, целевая функция ф($) будет принимать значения в диапазоне от 0 до 1. При этом большему значению целевой функции соответствует большая степень приспособленности хромосомы, т.е. данная целевая функция является "истинной" функцией приспособленности. Очевидно, что на решениях интервальной диагностической задачи целевая функция будет принимать значение 1.

В заключении кратко сформулированы основные результаты, полученные в диссертации.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ В диссертационной работе исследовались вопросы распознавания линейных автоматов, заданных интервальными характеристическими матрицами, а также решалась диагностическая задача для линейных автоматов с интервальным выходом. Получены следующие результаты:

1. Введена интервальная арифметика над полем Основным

объектом в ней является мультиинтервал над полем СР(р). Исследованы

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

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

3. Описан способ построения диагностической последовательности для решения интервальной диагностической задачи. Предложен алгебраический метод решения интервальной диагностической задачи, также рассмотрено решение этой задачи с использованием генетического алгоритма.

4. Создан ряд программ: для реализации интервальной арифметики (в среде Maple), для решения диагностической задачи для линейных автоматов с интервальным выходом (построение диагностической последовательности реализовано на Delphi, решение на основе решения СЛАУ -в Maple, решение на основе генетических алгоритмов - на языке С).

СПИСОК ПУБЛИКАЦИЙ

1. Куприянова Л.В., Сперанский Д.В., Самойлов В.Г. Интервальная арифметика над полем GF(p) // Вычислительные технологии. - 2002.

- Т. 7. - №. - с. 54-64.

2. Самойлов В.Г., Сперанский Д.В. Интервальные вычисления над конечными полями // Информационно-управляющие системы на железнодорожном транспорте. - 2002. - №4,5. - с. 68-70.

3. Самойлов В. Г. Программная реализация интервальных операций над полем GF(p) // Тезисы докладов международной конференции "Компьютерные науки и информационные технологии". - Саратов: Изд-во Саратовского Университета. - 2002. - с. 57-58.

4. Самойлов В.Г. Эксперименты с билинейными системами с запаздыванием // Теоретические проблемы информатики и ее приложений. -Саратов: Изд-во Саратовского Университета. - 2003. - №5. - с. 126-134.

5. Самойлов В.Г., Сперанский Д.В. О диагностической задаче для линейных автоматов в интервальной постановке // Информационно-управляющие системы на железнодорожном транспорте. - 2003. - №4.

- с. 19-23.

6. Самойлов В.Г., Сперанский Д.В. Диагностическая задача для билинейного автомата в интервальной постановке // Автоматика и телемеханика. - 2004. - №9. - с. 120-130.

7. Самойлов В.Г. Эксперименты по распознаванию автоматов // Информационно-управляющие системы на железнодорожном транспорте. - 2004. - №4,5 (48, 49). - с. 35-38.

8. Kupnyanova L.V., Speransky D.V., and Samoilov V.G. Interval Arithmetics over a Field GF(p) // SIAM, Workshop on Validated Computing (Toronto, Canada, May 23-25, 2002). Extended abstracts. -El Paso, Texas. - 2002. - p. 98-101.

9. Samoilov V.G., Speranskiy D.V., Kupriyanova L.V. Diagnostic problem for linear automata in interval statement // Proceeding of East-West Design and Test Workshop (Ukraine, September 17-21, 2004). - Kharkov. - 2004. - p. 142-148.

Подписано в печать 9.11.04 г. Формат 60x84/16. Бумага офсетная. Печать трафаретная. Усл. печ.л. 1,0 Тираж 100 экз. Заказ 138

Типография АВП «Саратовский источник»

Лиц. ПД № 7-0014 от 29 мая 2000 г. г. Саратов, ул. Университетская, 42, оф. 22 Т.52-05-93

23926

Введение

1 Интервальная арифметика над полем GF(p)

1.1 Обозначения и основные определения.

1.2 Свойства арифметических операций в IGF(p).

1.3 Множества решений уравнений в IGF(p)

1.4 Программная реализация интервальной арифметики

1.5 Решение систем уравнений с интервальной правой частью

2 Исследование линейных дискретных систем, заданных интервальными характеристическими матрицами

2.1 Постановка задачи.

2.2 Решение задачи распознавания автомата.

2.3 Синтез автоматов для упрощения решения задачи распознавания

3 Эксперименты с линейными дискретными системами с интервальным выходом

3.1 Постановка задачи.

3.2 Построение диагностической последовательности

3.3 Алгебраический метод нахождения решения интервальной диагностической задачи.

3.4 Генетический алгоритм для решения интервальной диагностической задачи.

В настоящее время теория автоматов успешно применяется в различных областях современной науки и техники. Это обусловлено тем, что автомат является адекватной математической моделью описания поведения сложных систем. Существуют две основных модели автоматов: автомат Мили и автомат Мура. Эти модели впервые были описаны в 1955 году Мили в работе [37] и в 1956 году Муром в работе [38], которая была переведена на русский и опубликована в 1956 году [21].

Теория экспериментов с автоматами является основой для некоторых разделов кибернетики, одним из которых является техническая диагностика. Эта теория является фундаментом многих современных методов и средств технической диагностики цифровой аппаратуры. Одной из существенных причин, порождающих сложности при решении проблемы диагностирования, является отсутствие информации о начальном, промежуточном или конечном состоянии устройства. Для снятия указанной неопределенности служат синхронизирующие, установочные и диагностические последовательности, подаваемые при проведении соответствующего эксперимента на входы устройства. В настоящее время теория экспериментов с автоматами достаточно хорошо развита и представлена в ряде работ: Гинзбурга С. [10], Глушкова В.М. [11], Гилла А. [8], Минского [20], Твер-дохлебова В.А. [30], Кудрявцева В.Б. [18], Сперанского Д.В. [6], Сытника А.А.[28], Богомолова A.M. [5, 6], Салия В.Н. [5] и других авторов. Полученные результаты позволяют сделать вывод о значительной трудоемкости методов синтеза упомянутых последовательностей, а также о сложности проверки факта существования этих последовательностей для конкретного автомата. Заметим, что в большинстве случаев проверка наличия у заданного автомата того или иного вида последовательности фактически была равносильна по трудоемкости ее построению.

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

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

Один из таких подклассов является классом линейных дискретных систем, так называемых линейных последовательностных машин или линейных автоматов. В дальнейшем мы будем использовать термин линейный автомат для обозначения представителя этого класса. Линейные автоматы сочетают в себе свойства линейных систем и конечных автоматов. Они имеют большое прикладное значение, так в монографии Гилла А. [9] отмечается, что такие автоматы: ". нашли широкое применение для решения многих характерных задач вычислительной техники, связи и автоматического управления, чем объясняется практический интерес к изучению этих машин. Среди наиболее важных областей их применения нужно отметить следующие: вычисления в кольцах многочленов и конечных полях, построение синхронизирующих устройств и счетчиков, воспроизведение линейных кодов, обнаружение и исправление ошибок, адресация в запоминающих устройствах, построение тестовых последовательностей с минимальным временем испытания, генерация последовательностей псевдослучайных чисел, которые применяются для повышения точности измерений в радиолокационных устройствах, при проведении вероятностных экспериментов, в задачах, требующих использования метода Монте-Карло, и т.д.".

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

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

Из работ, посвященных изучению свойств линейных автоматов, необходимо отметить следующие: монография Гилла А. [9], работа Фараджева Р.Г. [31], а также ряд работ Сперанского Д.В. [24, 25, 26].

В этих работах основное внимание уделялось диагностическим, установочным и синхронизирующим экспериментам. Эти эксперименты выясняют начальное и конечное состояния исследуемого автомата. Построение таких экспериментов основано на знании поведения линейного автомата, которое в свою очередь точно определяется его характеристическими матрицами. Однако не всегда эти матрицы известны перед началом проведения экспериментов по распознаванию состояний автомата. Поэтому и возникает задача определения этих матриц на основе эксперимента с экземпляром автомата, который перед началом эксперимента представляет собой "черный ящик". Эта задача является задачей распознавания автомата в классе линейных автоматов. Задача распознавания конечных детерминированных автоматов исследовалась в работах Гилла [8], Мура [21], Твердохлебова [30]. В них получены условия разрешимости задачи распознавания и оценки длин распознающих экспериментов. Эти оценки позволяют говорить о том, что такие эксперименты являются трудно реализуемыми из-за большой длины для автоматов, описывающих поведение реальных устройств с большим числом состояний.

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

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

В [2] отмечается, что интервальные методы являются наиболее перспективными при решении задач в условиях неопределенности.

Методы интервального анализа, используемые в настоящее время, базируются на использовании арифметических операций с вещественными и комплексными числами. В первой главе диссертации вводится интервальная арифметика над конечными полями GF(p), где р - простое число. Необходимость такой интервальной арифметики обусловлена потребностями развития методов теории дискретных систем.

С физической точки зрения уровни значений напряжений для входных и выходных значений сигналов, а также уровни значений состояний элементов памяти электронных устройств, описываемых математическими моделями линейных автоматов, можно измерять в "квантованных" единицах. Поскольку по техническим условиям значения напряжений имеют ограничения сверху, предельное значение этих напряжений, выраженное в "квантованных" единицах, и дает характеристику р поля GF(p). Отсюда же возникает и необходимость оперировать с квантованными значениями напряжений в арифметике по модулю р.

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

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

В соответствии с целью исследования были поставлены следующие конкретные задачи:

1. Ввести интервальную арифметику над полем GF(p).

2. Исследовать свойства интервальных операций.

3. Найти метод решения системы линейных алгебраических уравнений с интервальной правой частью над полем GF(p).

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

5. Предложить метод синтеза линейных автоматов для упрощения решения задачи распознавания.

6. Найти способ построения диагностической последовательности для линейного автомата с интервальным выходом.

7. Предложить методы решения диагностической задачи для линейного автомата с интервальным выходом.

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

Работа состоит из введения, трех глав, содержащих 12 разделов, заключения и списка литературы, включающего в себя 49 наименований. Диссертация изложена на 101 странице.

Заключение

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

1. Введена интервальная арифметика над полем GF(p). Основным объектом в ней является мультиинтервал над полем GF(p). Исследованы свойства интервальных операций. Предложен метод решения системы линейных алгебраических уравнений с интервальной правой частью над полем GF(p).

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

3. Описан способ построения диагностической последовательности для решения интервальной диагностической задачи. Предложен алгебраический метод решения интервальной диагностической задачи, также рассмотрено решение этой задачи с использованием генетического алгоритма.

4. Создан ряд программ: для реализации интервальной арифметики (в среде Maple), для решения диагностической задачи для линейных автоматов с интервальным выходом (построение диагностической последовательности реализовано на Delphi, решение на основе решения СЛАУ -в Maple, решение на основе генетических алгоритмов - на языке С).

1. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. -М.: Мир. - 1987.

2. Алтунин А.Е., Семухин М.В. Модели и алгоритмы принятия решений в нечетких условиях. Тюмень: Изд-во ТГУ. - 2000.

3. Батищев Д.И. Генетические алгоритмы решения экстремальных задач. Учебное пособие. Воронеж: ВГТУ. - 1995.

4. Батищев Д.И., Исаев С.А. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов // Высокие технологии в технике, медицине и образовании. Воронеж: ВГТУ. - Ч. 3. - 1997.

5. Богомолов A.M., Салий В.Н. Алгебраические основы теории дискретных систем. М.: Наука. - 1997.

6. Богомолов A.M., Сперанский Д.В. Аналитические методы в задачах контроля и анализа дискретных устройств. Саратов: Изд-во Саратовского Университета. - 1986.

7. Богомолов А.С., Сперанский Д.В. Оптимальные синхронизирующие эксперименты с линейными автоматами // Автоматика и телемеханика. МО. - 2001. - с. 203-208.

8. Гилл А. Введение в теорию конечных автоматов. М.: Наука. - 1966.

9. Гилл А. Линейные последовательностные машины. М.: Наука. - 1974.

10. Гинзбург С. О длине кратчайшего однородного эксперимента // Кибернетический сборник. М.: ИЛ. - вып. 3. - 1961. - с. 25-30.

11. Глушков В. М. Синтез цифровых автоматов. М.: Физматгиз. - 1962.

12. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир. - 1982.

13. Дьяконов В. Maple 6: учебный курс. М.: Питер. - 2001.

14. Калмыков С.А., Шокин Ю.И., Юлдашев З.Х. Методы интервального анализа. Новосибирск: Наука. - 1986.

15. Карманов В.Г. Математическое программирование: Учеб. пособие. М.: ФИЗМАТЛИТ. - 2001.

16. Карпов Ю.Г. Теория автоматов. СПб.: Питер. - 2002.

17. Клемент Р. Генетические алгоритмы: почему они работают? когда их применять? // Компьютерра. 1999. - №11. - с. 23-26.

18. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. М.: Наука. - 1985.

19. Курейчик В.М. Генетические алгоритмы и их применение. Таганрог: Изд-во ТРТУ. - 2002.

20. Минский М. Вычисления и автоматы. М.: Мир. - 1971.

21. Мур Э. Умозрительные эксперименты с последовательностными машинами // Автоматы. М.: ИЛ. - 1956. - с. 179-210.

22. Наместников A.M., Ярушкина Н.Г. Эффективность генетических алгоритмов для задач автоматизированного проектирования // Известия РАН. Теория и системы управления. 2002. - №2. - с. 127-133.

23. Оре О. Теория графов. М.: Наука. - 1968.

24. Сперанский Д.В. Синхронизация линейных последовательностных машин // Автоматика и телемеханика. 1996. - №5. - с. 141-149.

25. Сперанский Д.В. О тестировании линейных автоматов // Автоматика и телемеханика. 2000. - №5. - с. 157-165.

26. Сперанский Д.В. Эксперименты с линейными и билинейными конечными автоматами: Учебное пособие. Саратов: Изд-во Саратовского Университета. - 2004.

27. Сперанский Д.В., Сперанский И.Д. Эксперименты с линейными дискретными системами // Электронное моделирование. 1999. - №4. - с. 64-73.

28. Сытник А.А. Восстановление поведения сложных систем. Саратов: Изд-во Саратовского Университета. - 1992.

29. Табак Д., Куо Б. Оптимальное управление и математическое программирование. М.: Наука. - 1975.

30. Твердохлебов В.А. Логические эксперименты с автоматами. Саратов: Изд-во Саратовского Университета. - 1988.

31. Фараджев Р.Г. Линейные последовательностные машины. М.: Советское радио. - 1975.

32. Шарый С.П. Оптимальное внешнее оценивание множеств решений интервальных систем уравнений. Часть 1. // Вычислительные технологии. 2002. - Т. 7. - № 6. - с. 79-88.

33. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Pub. Co. - 1989.

34. Holland J.H. Adaptation in Natural and Artificial Systems. Ann Arbor: University of Michigan. - 1975.

35. Holland J.H. Genetic Algorithms: Computer programs that 'evolve' in ways that resemble natural selection can solve complex problems even their creators do not fully understand // Scientific American. 1992. - p. 5662.

36. Kearfott R.B. Rigorous Global Search: Continuous Problems. Dordrecht: Kluwer. - 1996.

37. Mealy G.H. A method for synthesizing sequential sircuits // Bell System Techn. Vol. 34. - 1955. - P. 1045-1079.

38. Moore E.F. Gedanhen-experiments on sequential machines // In C. Shannon and J. McCarthy editors. Automata Studies Princeton University Press. 1956. - P. 129-153.

39. Shary S.P. Algebraic approach to the linear static identification, tolerance and control problems, or One more application of Kaucher arithmetic // Reliable Computing. Vol.2. - №1. - 1996. - p. 3-33.

40. Smith R.E., Goldberg D.E., Earickson J.A. The Clearinghouse for Genetic Algorithms (TCGA) Report No. 91002. The University of Alabama. -1994.

41. По теме диссертации опубликованы следующие работы:

42. Куприянова JI.B., Сперанский Д.В., Самойлов В.Г. Интервальная арифметика над полем GF(p) // Вычислительные технологии. 2002. - Т. 7. - № 6. - с. 54-64.

43. Самойлов В.Г., Сперанский Д.В. Интервальные вычисления над конечными полями // Информационно-управляющие системы на железнодорожном транспорте. 2002. - № 4, 5. - с. 68-70.

44. Самойлов В.Г. Программная реализация интервальных операций над полем GF(p) // Тезисы докладов международной конференции "Компьютерные науки и информационные технологии". Саратов: Изд-во Саратовского Университета. - 2002. - с. 57-58.

45. Самойлов В.Г. Эксперименты с билинейными системами с запаздыванием // Теоретические проблемы информатики и ее приложений. Саратов: Изд-во Саратовского Университета. - 2003. - №5. - с. 126-134.

46. Самойлов В.Г., Сперанский Д.В. О диагностической задаче для линейных автоматов в интервальной постановке // Информационно-управляющие системы на железнодорожном транспорте. 2003. - № 4. - с. 19-23.

47. Самойлов В.Г., Сперанский Д.В. Диагностическая задача для билинейного автомата в интервальной постановке // Автоматика и телемеханика. 2004. - №9. - с. 120-130.

48. Самойлов В.Г. Эксперименты по распознаванию автоматов // Информационно-управляющие системы на железнодорожном транспорте. 2004. - № 4, 5 (48, 49). - с. 35-38.

49. Kupriyanova L.V., Speransky D.V., and Samoilov V.G. Interval Arithmetics over a Field GF(p) // SIAM, Workshop on Validated Computing (Toronto, Canada, May 23-25, 2002). Extended abstracts. -El Paso, Texas. 2002. - p. 98-101.

50. Samoilov V.G., Speranskiy D.V., Kupriyanova L.V. Diagnostic problem for linear automata in interval statement // Proceeding of East-West Design and Test Workshop (Ukraine, September 17-21, 2004). Kharkov. - 2004. - p. 142-148.