ВЕСТН. САМАР. ГОС. ТЕХН. УН-ТА. СЕР. ТЕХНИЧЕСКИЕ НАУКИ. 2012. № 2 (34)

Системный анализ, управление и автоматизация

УДК 519.7+007.3+510.8

СИСТЕМНЫЙ АНАЛИЗ ГЕТЕРОГЕННЫХ СЛАБОСТРУКТУРИРОВАННЫХ АВТОМАТОВ.
II. ПЕРЕХОД ОТ ПРЕОБРАЗОВАНИЙ «ХИМИЧЕСКОГО ТИПА»
К ЛОГИЧЕСКИМ СХЕМАМ И ОБРАТНО

Е.Н. Гребенщиков, С.М. Крылов

^[1]

Самарский государственный технический университет

443100, г. Самара, ул. Молодогвардейская, 244

E-mail: [email protected]

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

Ключевые слова: логические схемы, функциональная полнота, «химические логические элементы», двухстабильные элементы, автоматы Мили и Мура.

В первой части статьи «Системный анализ гетерогенных слабоструктурированных автоматов. I. Основные определения и свойства» были рассмотрены некоторые свойства автоматов нового типа, для которых предложено название «слабоструктурированные гетерогенные самосинхронные автоматы с индивидуальными именами объектов операций» (СГСА с ИИОО) [1]. Для удобства во второй части статьи сохранена сквозная нумерация утверждений (т. е. как продолжение [1]).

В [2] для аналого-цифровых систем обработки информации гетерогенного характера предложен следующий набор функциональных блоков – ФБ (рис. 1).

Рис. 1. Реализация булевых функций в специальном базисе ФБ

В [2, 3] доказано, что справедливо следующее.

Лемма 1. С помощью ФБ типа «2И», «НЕ», «разветвителя», «константы 0» или «константы 1» (рис. 1) могут быть реализованы любые булевы функции.

Фактически лемма 1 повторяет, с учетом специфики СГСА с ИИОО, известную в логике теорему о функциональной полноте системы логических функций с конъюнктором и инвертором [4].

Химические реакции (т. е. функциональности «химического типа») с очевидностью относятся к самосинхронным процессам, которые происходят только тогда, когда в среде присутствуют все компоненты реакции. Чтобы исследовать возможные пути перехода к «химическим» самосинхронным функциональностям, сначала снабдим все ФБ (рис. 1) входами синхронизации ci, при подаче сигнала на которые выполняется заданная функция элемента и на выходе запомнится полученный результат – до прихода следующего импульса синхронизации (рис. 2).

Введем также понятие уровня обработки – т. е. положения соответствующего элемента и других элементов, которые переключаются синхронно с ним, на самой длинной цепочке распространения сигнала в схеме реализации функции. На рис. 2 одной из таких цепочек является следующая: вход x – верхний разветвитель – верхняя схема «НЕ» – следующий разветвитель – верхняя схема «2И» – выход 0. Момент подачи очередного синхронизирующего импульса на любом уровне должен отстоять от импульса предшествующего уровня на время, достаточное для надежной обработки сигналов на предшествующем уровне.

Рис. 2. Пример двоичного дешифратора на синхронных ФБ. Уровни обработки сигналов отмечены вертикальными пунктирными линиями с цифрами 1...4. Рядом показаны входы синхронизации соответствующего уровня

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

Доказательство. Поскольку в условии леммы 2 сразу оговаривается нормальный (естественный) режим синхронизации, а состав ФБ – тот же, что и в лемме 1, то с очевидностью все логические операции будут выполнены так же и в том же порядке, что и для схем, построенных на основании леммы 1.

В соответствии с определениями 1, 2 сформулируем следующее.

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

Схемы таких преобразований элементов рис. 1, рис. 2 представлены на рис. 3.

Заметим, что согласно рис. 3 одна и та же функция может быть выполнена несколькими типами гетерогенных самосинхронных автоматов с индивидуальными именами объектов именно благодаря индивидуализации «имен» сигналов.

Так, функция «2И» может быть реализована как по схеме с промежуточным объектом c и сигналом синхронизации ((a=x)+(b=y)c)+(d=ci)(e=z), где объект «d» выполняет функцию внешнего сигнала синхронизации ci, так и по схемам без специального сигнала синхронизации (a=x) + (b=y) (c=z) и даже (a=x) + (b=y) <(c=z), («f» игнорируется)>. Необходимость в двух последних случаях (изображенных на рис. 3 в верхней строке справа) в сигнале синхронизации отпадает по той причине, что его функцию выполняют оба входных сигнала x и y. Только при одновременном наличии объектов (a=x) и (b=y) будет получен объект «c», соответствующий выходному сигналу «z». Если все же сигнал синхронизации необходим, можно воспользоваться схемой, в которую он введен в явном виде.

Последняя сверху справа схема на рис. 3 с двумя основными выходными «сигналами-объектами» «c» и «f» иллюстрирует возможность использования только части выходных объектов в качестве важных, несущих «информацию» о входных объектах-сигналах. Действительно, индивидуализация имен входных и выходных объектов дает возможность на всех последующих уровнях обработки игнорировать сигнал «f» как не относящийся к сигналам, несущим значимую информацию. В дальнейшем такую ситуацию «игнорирования» некоего объекта-сигнала «w» будем записывать так: w=indif (то есть «w» – бесполезный, ненужный сигнал-объект).

Рис. 3. Перевод универсального базиса двоичной синхронной логики в гетерогенные автоматы с функциональностями типа (1) и (2) из [1]

Для инвертора с внешним сигналом синхронизации схема очевидна: (g=x)+(h=ci)(k=y=-x=0, если объекту x приписывается смысл логической 1). То есть объекту «k» мы приписываем значение выхода y= -x = 0 при наличии на входе x=1 и сигнале синхронизации ci. Соответственно, при отсутствии на входе x=1, то есть при x=0 и наличии сигнала синхронизации ci=1, «значение» выходного объекта гетерогенного автомата «равно» объекту, представляющему сам «сигнал» синхронизации, то есть «h». Т. о., «инверсное» значение входного сигнала x=0, соответствующее выходному сигналу -x=1=y, представляется объектом «h» – то есть «сигналом» синхронизации, обойтись без которого в данном случае нельзя. Исходя из этого обстоятельства и должна строиться вся последующая обработка объектов.

Отметим, что как и для схемы «2И», для реализации инвертора «НЕ» возможна гетерогенная схема с несколькими выходными сигналами-объектами, только один из которых является значимым, тогда как остальные – indif-объекты. Более того, согласно нашим определениям схема (2) из [1] может выполнять функции схемы (1) из [1]: т. е. функция a+bc может быть реализована с помощью схемы a+bd+f, так как можно записать d+f= <(d=c), (f=indif)>.

Для разветвителя с синхронизацией можно использовать схему в верхнем ряду справа рис. 3. Для реализации разветвителя без синхронизации используется схема, соответствующая (2) из [1], изображенная на рис. 3 справа внизу.

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

Лемма 4. Любая конечная комбинационная схема (КС) от конечного числа булевых переменных может быть преобразована в эквивалентную конечную систему (сеть) слабоструктурированных гетерогенных автоматов с индивидуальными именами объектов и некоторым конечным числом дополнительных внешних объектов («сигналов»), выполняющих функцию синхронизации.

Наиболее очевидный путь доказательства леммы 4 – это сначала перевод схемы реализации данной булевой функции в универсальном базисе леммы 1 в схему с синхронизацией, и затем – перевод последней в систему гетерогенных самосинхронных автоматов с возможно меньшим числом сигналов синхронизации. Покажем, что для любого конечного числа входных булевых переменных исходной функции такое преобразование в рамках МНФ («метода назначенных функциональностей» – см. [1]) по предложенным выше схемам всегда осуществимо. Действительно, после ее перевода (лемма 2) в схему с синхронизацией мы получим схему с конечным числом элементов. Выберем в ней сигнал i (из всех входных, выходных и промежуточных), в котором используется наибольшее число разветвителей с наибольшим числом уровней обработки, на которых происходит разветвление. Пусть их число равно p. Выполняем следующее.

1. Для самого последнего из этих p уровней – уровня j – выберем согласно МНФ любой объект типа bk*bs. Для всех остальных схем разветвления сигнала i на том же уровне j выберем другие объекты, компоненты (и имена) bk, bs которых не совпадают с компонентами (именами) уже использованных. Так продолжаем до тех пор, пока не припишем всем разветвителям сигнала i на уровне j индивидуальные объекты (и имена). Теперь на входе каждого разветвителя сигнала i уровня j запишем выбранный для него объект bk*bs; на входе его синхронизации – подходящий объект типа xks; на выходах разветвителя – соответствующие данному входному объекту bk*bs и xks его компоненты – то есть выходные объекты bk и bs*xks.

2. Переходим на предыдущий уровень j-1 разветвления сигнала i. Для соответствующих пар выходных объектов типа bk*bs каждого разветвителя сигнала i на этом уровне подбираем подходящий объект типа xks и соответствующий входной объект, не использовавшиеся ранее. Записываем их на соответствующих входах каждого разветвителя сигнала i на уровне j-1, пока не припишем индивидуальные объекты (и имена) всем входам сигналов и всем входам синхронизации всех таких разветвителей.

3. Повторяем пункт 2 для каждого предыдущего уровня разветвления сигнала i, пока процесс разветвления не закончится – т. е. пока не выйдем на уровень j-p.

4. Для всех схем типа «2И» и инверсии «НЕ», связанных своими входами и/или выходами с входами-выходами схем разветвления, подбираем подходящие индивидуальные объекты (с индивидуальными именами) из оставшегося списка функциональностей в соответствии с рис. 3. Заканчиваем, когда все схемы, связанные с разветвителями, получат индивидуальные имена объектов для всех своих входных и выходных объектов-сигналов.

5. Переходим к логическим элементам и разветвителям, входы и/или выходы которых связаны с входами и/или выходами элементов, имеющих индивидуальные имена объектов. Поскольку булевы функции в КС не содержат обратных связей, то мы не столкнемся с ситуацией, когда какой-либо выходной сигнал-объект j-ого уровня попадает на предыдущий и тем самым приводит к противоречию, когда входные и выходной сигналы для какого-то элемента уже определены и требуется подобрать функциональность, соответствующую этой комбинации, уже задействованную в другом месте. Здесь, однако, могут возникнуть иные критические ситуации – когда перед разветвителями стоит достаточно много схем «2И» и мы, пытаясь использовать для реализации этих схем функциональности типа (1), вынуждены в качестве исходных объектов для схемы «2И» использовать те же объекты, что и на выходе разветвителя. То есть, имея на входе разветвителя объекты типа bk*bs и, соответственно, на его выходе два объекта bk и bs, мы хотим в схеме «2И» предшествующего уровня, выход которой связан со входом данного разветвителя, использовать те же элементы bk и bs, а именно реализовать схему «2И» в соответствии с (1) из [1]: bk+bsc= bk*bs. Согласно правилу индивидуализации сигналов это недопустимо. Для разрешения конфликта необходимо использовать либо другие объекты, либо другой тип функциональности – например, типа (2) из [1]: a+bc+f= =<(c=bk*bs), (f=indif)> (запись функциональности дана по рис. 3). Ясно, что используемые здесь объекты a и b должны отличаться от bk и bs. Более того, вариантов таких схем с исходными объектами, отличными от bk и bs, по крайней мере теоретически, может быть сколь угодно много.

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

Заметим, что в случае ООП рассмотренный выше подход вполне реализуем практически, поскольку при написании текстов программ мы вольны сами выбирать имена объектов и назначать их функциональности (которые в ООП называются «методами»). Однако для химических реакций мы фактически пока доказали лишь теоретическую (абстрактную) возможность преобразования конечных КС булевых функций в некие гипотетические и конечные системы химических реакций типа (1) и (2) из [1]. Вопрос о том, как такие системы химических реакций реализовать практически в каждом конкретном случае, остается открытым. Однако этого и не требует принятая нами формулировка утверждения 2.ю

Лемма 4 обеспечивает также истинность следующего утверждения.

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

Чтобы доказать утверждение 5, нам нужно лишь показать реализуемость в системе рассмотренных выше функциональностей элементов памяти. Но это уже было сделано раньше – см. интерпретацию схемы функциональности (2) в работе [1], а также на рис. 1 в [1]. Таким образом, утв. 5 доказано в полном объеме.ю

Утверждение 6. С помощью функциональностей утв. 5 может быть реализован любой конечный автомат Мили (Мура) в виде системы (сети) гетерогенных автоматов с индивидуальными именами объектов и внешней синхронизацией.

Как известно, любой автомат (в том числе Мили или Мура) может быть реализован в виде комбинационной схемы (КС) и запоминающего устройства, в котором запоминается текущее состояние автомата [5].

Рассмотрим автомат Мили (рис. 4). Выполним его комбинационную схему (КС) в функционально-полном базисе элементов «2И», «НЕ», констант и разветвителей согласно лемме 1. Переведем КС автомата в соответствующие схемы с синхронизацией, а затем – в систему гетерогенных автоматов по алгоритму, использованному в доказательстве леммы 4.

На основе МНС и с использованием способов преобразования сигналов-объектов, аналогичных рис. 3 и лемме 4, дополним соответствующие выходы новой схемы КС на гетерогенных автоматах гетерогенными же элементами памяти нужного (конечного) объема. С использованием аналогичных приемов согласуем выходные сигналы-объекты блока памяти с соответствующими входными сигналами-объектами нашей новой КС.

Рис. 4. Стандартная реализация автомата Мили

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

Наличие внешних синхронизирующих сигналов в гетерогенных автоматах, способных работать в режиме самосинхронизации, конечно, ухудшает качество системы в целом. Сигналы синхронизации появляются тогда, когда мы сталкиваемся с задачей разветвления или инверсии основных «информационных» сигналов. Таким образом, одна из важных задач оптимизации гетерогенных автоматов – максимальный их перевод на элементный базис «2И», т. е. на функциональности типа (1) из [1] с минимумом инверторов и разветвителей.

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

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

Простейший вариант доказательства истинности этого утверждения – провести индивидуализацию сигналов исходного автомата, т. е. приписать каждому сигналу во всех преобразованиях типа (1) и/или (2) из [1] уникальное двоичное кодовое имя и заменить все элементарные химические преобразования типа (1) и (2) на схемы сравнения соответствующих сигналов-имен с заданными. В случае совпадения поступившего извне сигнала-имени с заданным происходит генерирование новых сигналов-имен в соответствии с эмулируемыми химическими функциональностями (т. е. в соответствии с имитируемыми химическими реакциями и выполненной индивидуализацией сигналов). Все перечисленные операции элементарно реализуются в любой функционально-полной системе булевских функций.ю

Заключение. В статье показано, что, по крайней мере в теоретическом плане, сети (схемы) слабоструктурированных гетерогенных самосинхронных автоматов с индивидуальными именами объектов операций (СГСА с ИИОО), включая схемы химических реакций, заданные формами (1) и (2) в [1], могут быть заменены подходящими схемами обычных автоматов Мили или Мура, и наоборот – для конечных схем автоматов Мили или Мура можно подобрать соответствующие сети СГСА с ИИОО, выдающих определенные типы сигналов-объектов в ответ на определенные внешние сигналы-объекты и текущее состояние автомата. Однако в практическом плане гарантий реализации произвольных конечных схем классических автоматов Мили или Мура в соответствующих системах химических реакций данная статья не дает. Тем не менее полученный теоретический результат может рассматриваться как призыв к поиску таких подходов, поскольку из подобных сетей могут быть построены различные химические аналоги существующих вычислительных систем, включая самовоспроизводящиеся и саморазвивающиеся автоматы.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Крылов С.М. Системный анализ гетерогенных слабоструктурированных автоматов I. Основные определения и свойства // Вестник СамГТУ. Сер. Технические науки. – Самара: СамГТУ, 2012. – № 1. – С. 17-23.
2. Крылов С.М. Синтез электронных блоков из гетерогенных компонентов // Труды 6-й межвузовск. научно-практ. конференции. – Самара: СамГТУ, 2007. – С. 116-119.
3. Крылов С.М., Сараев М.В. Синтез конфигурируемых блоков для аналого-цифровых систем-на-кристалле с использованием гетерогенных функциональных компонентов // Вестник Самарск. гос. техн. ун-та. Сер. Техн. науки. – Самара: СамГТУ, 2007. – № 2. – С. 58-63.
4. Крылов С.М., Сараев М.В. Функциональная полнота вычислительных систем // Труды 7-й межвузовск. научно-практ. конференции. – Самара: СамГТУ, 2008. – С. 194-197.
5. Алгебраическая теория автоматов, языков и полугрупп / Под ред. М.А. Арбиба. Пер. с англ. – М.: Статистика, 1975. – 335 с.

Статья поступила в редакцию 27 октября 2010 г.

HETEROGENEOUS WEAKLY-STRUCTURED AUTOMATA.
II CONVERsION from "CHEMICAL-LIKE TRANSFORMATIONS"
TO LOGICAL ONES AND VICE VERSA

E.N. Grebenschikov, S.M. Krylov

^[2]

Samara State Technical University

244, Molodogvardeyskaya st., Samara, 443100

The paper deals with the problems concerning functional completeness of one>

Keywords: logical circuits, logical functional completeness, chemical reactions, «chemical logic gates», Mealy machine, Moore machine.

УДК 681.5.015

адаптивный алгоритм оценивания Детерминированных ХАОТИЧЕСКИХ ПРОЦЕССОВ с использованием базиса нерегулярных функций^[3]

А.Н. Дилигенская

Самарский государственный технический университет

443100, г. Самара, ул. Молодогвардейская, 244

E-mail: [email protected]

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

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

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

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

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

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

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

В большинстве работ, посвященных оцениванию и прогнозированию хаотических процессов, задача аппроксимации и прогнозирования решается на коротких выборках в условиях малого числа наблюдений (N<50) [3]. В этом случае для построения математических моделей процессов с нерегулярной динамикой наряду с использованием глобальных универсальных моделей и нейронных сетей применяется разложение исходного временного ряда по базису ортогональных хаотических процессов [4]. Базисные процессы выбираются, во-первых, из условия ортогональности, под которым понимается взаимная некоррелированность, и, во-вторых, из условия достижения на некотором доступном множестве параметров базисных функций максимальной корреляции с исходным временным рядом. Если в наблюдаемом сигнале действительно присутствует детерминированная составляющая, содержащая хаотические компоненты, такая модель может аппроксимировать исходный процесс с высокой степенью адекватности. Количество необходимых базисных функций выбирается таким, чтобы в остатке ряда не содержалось подлежащих аппроксимации детерминированных составляющих.

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

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

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

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

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

(1)

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

(2)

и при проявляющие хаотическую динамику.

Параметры хаотических базисных процессов и начальные условия выбираются исходя из условия взаимной ортогональности [4]

, (3)

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

, (4)

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

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

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

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

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

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

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

. (5)

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

, (6)

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

. (7)

В качестве примера рассматривалась хаотическая компонента одномерного временного ряда из 200 значений. Для построения ее модели выделены локальные участки по 20 точек, на каждом из которых строится система ортогональных базисных процессов. На некоторых локальных участках удается построить разложение исходного сигнала по двум базисным функциям, и при этом наблюдается удовлетворительный коэффициент корреляции полученного разложения с исходным процессом (свыше 80 %), однако на других интервалах приемлемого разложения из двух составляющих построить не удается. В соответствии с этим было принято решение строить базисную систему из трех процессов. На каждом участке находятся параметры и начальные условия логистических отображений (2). В результате рекуррентного алгоритма адаптивного оценивания (6) получена временная аппроксимация (1) наблюдаемого сигнала, представленная на рис. 1.

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

Рис. 2. Автокорреляционные функции наблюдаемого временного ряда (1)
и его аппроксимации (2)

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

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

Попытки использовать универсальный алгоритм определения параметров (характеризующийся одним и тем же числом учитываемых точек в каждом интервале и одинаковым числом базисных функций) приводит к тому, что коррелированность исходного временного ряда и построенного разложения на отдельных временных интервалах может достигать 90-98 % при некоторых значениях параметров разложения, а на других опускаться до 70-75 % (в отдельных случаях ниже 60 %).

Если же отойти от универсальности и на каждом интервале добиваться желаемой корреляции базисных процессов как с исходным рядом, так и между собой, то возможно достичь высокого соответствия модельного представления и экспериментальных значений на каждом временном участке и, соответственно, на всей длинной выборке. В результате коэффициент корреляции наблюдаемого процесса и полученного модельного представления может достигать 92-96 % на всем временном интервале при любом учитываемом числе точек (см. рис. 1). Построение автокорреляционной функции полученного модельного представления также показывает высокую адекватность аналогичной характеристике исходного ряда (см. рис. 2). Аппроксимирующая и исходная корреляционные функции имеют идентичную сложную динамику, характеризующуюся выраженными пиками при одинаковых временных сдвигах.

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

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Андриевский Б.Р., Фрадков А.Л. Управление хаосом: методы и приложения. Ч. II. Приложения. – АиТ. 2004 (4). – С. 3-34.
2. Яковлев В.Л., Яковлева Г.Л., Лисицкий Л.А. Модели детерминированного хаоса в задаче прогнозирования тенденций финансовых рынков и их нейросетевая реализация // Информационные технологии, 2000. – № 2. – С. 46-52.
3. Лукашин Ю.П. Адаптивные методы краткосрочного прогнозирования временных рядов. – М.: Финансы и статистика, 2003. – 415 с.
4. Шелудько А.С., Ширяев В.И. Построение ортогонального разложения хаотического процесса // Научная сессия МИФИ – 2011. Сб. научных трудов. – М.: МИФИ, 2011. – Ч. 1: XIII Всероссийская научно-техническая конференция «Нейроинформатика – 2011». Нейронные сети. – С. 44-52.
5. Синай Я.Г. Современные проблемы эргодической теории. – М.: Наука, 1995.
6. Чернов В.М. Арифметические методы синтеза быстрых алгоритмов дискретных ортогональных преобразований. – М.: Физматлит, 2007.

Статья поступила в редакцию 2 марта 2012 г.

Adaptive algorithm for estimating the DETERMINED chaotic processes with the USage of IRREGULAR FUNCTIONS BASIS

A.N. Diligenskaya

^[4]

Samara State Technical University

244, Molodogvardeyskaya st., Samara, 443100

The problem of estimation of chaotic time series under the perturbation is examined. For more accurate estimation during the continuous processing the correcting feedback from the observed process is used. As a mathematical model the expansion of the system of orthogonal chaotic processes is applied.

Keywords: chaotic process, nonlinear irregular oscillations, expansion of time series, orthogonal basis, identify algorithm, recursive estimation algorithm.

УДК 005; 519.7; 303.732

Системный анализ вклада научно-технической деятельности в развитиЕ технологических платформ

Н.В. Дилигенский, М.В. Цапенко, А.Н. Давыдов

^[5]

Самарский государственный технический университет

443100, г. Самара, ул. Молодогвардейская, 244

E-mail: [email protected]

Рассмотрены вопросы многокритериального оценивания сравнительной эффективности технологических платформ на примере научно-технической деятельности крупного научного учреждения.

Ключевые слова: технологические платформы, многокритериальное оценивание, системная эффективность научных исследований.

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

Решением Правительственной комиссии по высоким технологиям и инновациям от 1 апреля 2011 г. (с добавлением от 31 мая 2011 г.) утвержден Перечень технологических платформ в России. В этот перечень входят 28 технологических платформ, сформированных по 11 базовым направлениям создания высоких инновационных технологий:

– медицинские и биотехнологии;

– информационно-коммуникационные технологии;

– фотоника;

– авиа-, космические технологии;

– ядерные и радиационные технологии;

– энергетика;

– технологии транспорта;

– технологии металлургии и новые материалы;

– добыча природных ресурсов и нефтепереработка;

– электроника и машиностроение;

– экологическое развитие.

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

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

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

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

На их основе сформирован глобальный критерий оценки системной эффективности научных исследований по каждой технологической платформе. В качестве способа свертки локальных показателей в обобщенный критерий применена DEA-методология [1-4], позволяющая получить глобальные оценки эффективности без использования информации о рангах частных разнородных критериев путем формулировки и решения специальных задач математического программирования.

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

,

(1)

где – значение -го частного показателя эффективности для -ой технологической платформы;

– неизвестные при постановке задачи многокритериального оценивания весовые коэффициенты частных показателей;

– область значений весовых коэффициентов.

Область конструируется исходя из условий нормирования всех обобщенных показателей эффективности на интервале и определяется системой ограничений:

(2)

Результаты сравнительной оценки технологических платформ

Постановки (1), (2) определяют 22 задачи линейного математического программирования, решениями которых являются показатели обобщенной эффективности исследований по каждой технологической платформе и соответствующие им ранги частных критериев

Свойства метода DEA и примеры его апробации рассмотрены в работах [5-8].

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

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

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

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

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

Настоящее исследование проведено в рамках выполнения Государственного контракта Минобразования и науки РФ № 16.740.11.0749.

Библиографический список

1. HANDBOOK ON DATA ENVELOPMENT ANALYSIS edited by: William W. Cooper, Lawrence M. Seiford, Joe Zhu // Kluwer Academic Publishers, 2004. – 593 p.
2. Farrel M.J. The Measurement of Productive Efficiency // Journal of the Royal Statistical Society, Series A (General), Vol. 120, Part III, 1957, 253-281 p.
3. Charnes A., Cooper W., Rhodes E. Measuring the Efficiency of Decision Making Units // European Journal of Operational Research, Vol. 2, 1978, pp. 429-444.
4. Banker R.D., Charnes A., Cooper W. Some Models for Estimating Technical and Scale Efficiency in Data Envelopment Analysis // Management Science, Vol. 30, No. 9, 1984, pp. 1078-1092.
5. Дилигенский Н.В., Цапенко М.В. Математическое моделирование и обобщенное оценивание эффективности производственно-экономических систем // Труды VI Международной конференции «Проблемы управления и моделирования в сложных системах». – Самара, СНЦ РАН. – 2004. – С. 96-106.
6. Дилигенский Н.В., Цапенко М.В. Методология DEA: оценка эффективности экономических объектов, анализ метода и свойств решений // Межвузовский сборник научных трудов «Высшее образование, бизнес, предпринимательство – 2001». – Самара: СамГТУ, Поволжский институт бизнеса. – 2001. – С. 149–159.
7. Дилигенский Н.В., Цапенко М.В., Давыдов А.Н. Методология и технологии формирования и классификации знаний о деятельности научных коллективов // Труды XII Международной конференции «Проблемы управления и моделирования в сложных системах». – Самара, СНЦ РАН. – 2011. – С. 95-103.
8. Дилигенский Н.В., Цапенко М.В., Давыдов А.Н. Многокритериальная методология выявления перспективных направлений научных исследований // Вестник Самар. гос. техн. ун-та. Сер. Технические науки. – Вып. №4 (32). – Самара, 2011. – С. 26-33.

Статья поступила в редакцию 4 марта 2012 г.

SYSTEMS ANALYSIS OF THE CONTRIBUTION OF SCIENCE
AND TECHNOLOGY IN THE DEVELOPMENT OF TECHNOLOGY PLATFORMS

N.V. Diligensky, M.V. Tsapenko, A.N. Davydov

^[6]

Samara State Technical University

244, Molodogvardeyskaya st., Samara, 443100

This article discusses the issues of multi-criteria evaluation of the comparative effectiveness of Technology Platforms on the example of scientific and technical activities of a large research institution.

Keywords: Technology Platforms, multicriteria estimation, system effectiveness of scientific researche.

УДК 629.053

Система позиционного управления движением колесного механизма

Г.Н. Рогачев, Е.С. Учаев

^[7]

Самарский государственный технический университет

443100, г. Самара, ул. Молодогвардейская, 244

E-mail: [email protected]

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

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

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

Моделью объекта управления является система нелинейных обыкновенных дифференциальных уравнений [1]

. (1)

В (1) x и y – это координаты центра задней оси, – курсовой угол, угловая и линейная v скорость – два сигнала управления. Наблюдаемыми величинами являются фазовые координаты x, y и . Объект изображен на рис. 1.

Существует множество алгоритмов решения задачи перевода объекта (1) из любого начального состояния в заданное координатами x и y конечное. Они делятся на два класса: программные и позиционные.

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

, (2)

где – координаты цели, – координаты положения объекта.

Рис. 1. Колесный механизм

Был рассмотрен программный алгоритм [2] перевода объекта в заданное положение по траектории, имеющей минимальную длину. Этот алгоритм определяет значения управляющих воздействий на интервалах их постоянства и длительности самих интервалов. Количество интервалов зависит от начального и конечного состояний и лежит в диапазоне от одного до пяти. При исследовании системы управления на базе этого программного алгоритм были выявлены крайне жесткие требования к обеспечению моментов переключения управляющих воздействий. Так, на рис. 2 приведены результаты работы программного алгоритма управления перемещением объекта управления (1) из точки в точку . На этом рисунке траектория 1 соответствует точному соблюдению моментов переключения. Движение по траекториям 2, 3 происходит, если переключение с первого интервала управления на второй выполняется с погрешностью +0,2 с, что приводит к погрешности достижения цели E1=1.02 и Е2=0.99. Изменение управляющих воздействий во времени приведено на рис. 3.

Рис. 2. Траектории движения колесного механизма	Рис. 3. Изменение управляющих воздействий во времени

Известные позиционные алгоритмы за счет использования обратных связей по координатам способны преодолеть возмущения, но не являются оптимальными и тем самым уступают программным. Трудность применения обратных связей в системе управления объектом (1) состоит в том, что его невозможно стабилизировать непрерывной обратной связью [3], необходим гибридный закон управления. Был рассмотрен гибридный позиционный алгоритм [3], произведено его исследование. В ходе исследования была обнаружена проблема, связанная с «параллельной парковкой». Результат движения из точки в точку приведен на рис. 4.

Был также рассмотрен позиционный алгоритм [4]. Этот гибридный алгоритм осуществляет выбор одного из четырех позиционных законов управления в зависимости от положения объекта управления, определяя зоны переключения в собственной системе координат регулятора. В ходе исследования этого регулятора был обнаружен ряд «критических» зон, движение внутри которых выглядит нелогично. Результат движения из точки в точку приведен на рис. 5.

Рис. 4. Траектория движения колесного механизма (гибридный позиционный алгоритм [3])	Рис. 5. Траектория движения колесного механизма (гибридный позиционный алгоритм [4])

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

Спроектированный регулятор в своей основе имеет программный алгоритм перевода объекта в заданное состояние по траектории минимальной длины. В отсутствие помех программный регулятор в состоянии справиться с поставленной задачей. При действии возмущений объект отклоняется от расчетной траектории. Для контроля этого в регуляторе реализована модель объекта управления, с помощью которой периодически рассчитывается требуемое положение объекта и сравнивается с реальным. Если объект заметно отклонился от расчетной траектории, то необходимо вновь произвести расчет оптимальной программы движения из текущего положения и продолжить движение по новой оптимальной траектории. Аналогично разрешается ситуация оперативного вмешательства, когда требуется срочно изменить координаты цели назначения. Структура системы автоматического управления приведена на рис. 6, Stateflow-диаграмма вычислительного блока – на рис. 7.

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

– если объект управления отклонился от расчетной траектории движения, то следует произвести перерасчет управляющих воздействий и определить новую траекторию движения из текущего положения;

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

– если объект наткнулся на непреодолимое препятствие, то следует изменить управление на [-v -1] (движение «назад – налево» по радиусу максимальной кривизны). Продолжительность этого «аварийного» закона управления определяется случайным образом и лежит в диапазоне от двух до шести секунд. Если в это время объект вновь обнаружит препятствие, то процедура повторяется. По истечении данного времени производится перерасчет управляющих воздействий и определяется новая траектория движения из текущего положения.

Рис. 6. Структура системы автоматического управления

Рис. 7. Stateflow-диаграмма вычислительного блока

Произведено исследование поведения системы позиционного регулирования с моделью объекта управления в контуре. Результат движения колесного механизма из точки в точку ^[8] при отсутствии помех приведен на рис. 8.

Предположим, что на объект действует возмущение в виде ветра, дующего в северо-восточном направлении, который смещает объект. Результат движения из точки в точку приведен на рис. 9. На этом рисунке непрерывной линией обозначена истинная траектория движения объекта управления, пунктиром обозначена расчетная (модельная) траектория.

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

Рис. 8. Траектория движения колесного механизма при отсутствии помех (универсальный программно-позиционный алгоритм)	Рис. 9. Траектория движения колесного механизма при наличии помех (универсальный программно-позиционный алгоритм)