автореферат диссертации по приборостроению, метрологии и информационно-измерительным приборам и системам, 05.11.16, диссертация на тему:Разработка методов оптимизации структуры каналов информационно-измерительных систем

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ В.И.УЛЬЯНОВА (ЛЕНИНА)

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

Алин Галымзада Темиртасович

РАЗРАБОТКА МЕТОДОВ ОПТИМИЗАЦИИ СТРУКТУРЫ КАНАЛОВ ИНФОРМАЦИОННО-ИЗМЕРИТЕЛЬНЫХ СИСТЕМ

Специальндсть: 05.11.16 - Информационно-измерительные системы

АВТОРЕФЕРАТ диссертаций на соискание ученой степени кандидата технических наук

Санкт-Петербург - 1994

Работа выполнена в Санкт-Петербургском государственно}, электротехническом .университете имени В. И. .Ульянова (Ленина).

Научнйй руководитель доктор Технических наук профессор ЧЕРНЯВСКИЙ Е.А.

Официальные оппоненты: доктор технических наук профессор КОНДРАШКОВА Г.А. кандидат технических наук доцент ЕРАСТ08 В. Д.

Ведущая организация - Санкт-Петербургский научно-исследовательский институт электроприборостроения '

Защита диссертации состоится _" ¿^и^м 1994г.

ъ ¡¿г часов на заседании диссертационного совета К 063.36.0-1 Санкт-Петербургского государственного электротехниче'скогс университета имени В.И.Ульянова (Ленина) по адресу: 197376, Санкт-Петербург, ул. Проф.Попова. 5.

С диссертацией можно ознакомиться в библиотеке университета. •Автореферат разослан "А_" /¿-¿'А1994 г. •

Ученый секретарь диссертационного совета

ЮРКОВ Ю.В.

- 1 -

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

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

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

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

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

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

Достижение поставленной цели предполагает решение следующих задач:

1) разработка и исследование алгоритмов, позволяющих моделировать расчет параметров измерительно - вычислительного канала /метрологических и технических характеристик/ на основе параметров составляющих канал компонентов;

2) создание и теоретическое обоснование алгоритмов и методов проектирования, позволяющих выбрать оптимальный вариант структуры измерительного канала по заданному критерию

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

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

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

Научная новизна проведенных исследований состоит в том,

что:

1) разработаны и теоретически обоснованы модели описа-1 ния и расчета параметров измерительного канала, в том.числе и характеристик погрешности, позволяющие проводить - оптимизацию по точностным параметрам;'

2) дано формальное описание и исследованы особенности применения,алгоритмов беспошагового (отсевающего) метода оптимального синтеза измерительных каналов,- алгоритмов поиска приближенного решения типа "жадного алгоритма", построенных на основе метода перестановок, и алгоритма метода последовательного анализа отсева вариантов, основанные на моделях описания и расчета параметров канала;

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

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

- разработана инженерная методика проектирования измерительных каналов и пакет прикладнык программ;

- использование 'разработанных методов й алгоритмов возможно, также при проектировании других сложных/ технических систем, параметры которых расчитываются'на осйовё параметров составляющих систему компонентов, сокращает трудоемкость

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

Реализация результатов работы. Предложенная методика логического проектирования измерительно - вычислительных каналов и пакет прикладных программ внедрены на опытном заводе-института Гипроуглегормаш г. Караганды, что подтверждается соответствующим актом о внедрении, и использовались в учебном процессе в СПб ТЭТУ.

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

- научно-техническом семинаре "Применение персональных ЭВМ в проектировании и технологии", ЛДТП, Санкт-Петербург, 30-31 октября .1992 г;

- научно-технических конференциях профессорско-преподавательского состава СПб ГЭГУ, Санкт-Петербург, 1993-1994 гг'_.

Публикации. По материалам диссертации опубликовано й печатных работ, из них 4 статьи и 1 депонированная рукопись.

Структура и объем работы. Диссертация состоит из введения, четырех глав с выводами, заключения и списка литературы, включающего 1Í0 наименований. Основная часть работы изложена на 150 страницах машинописного текста. Работа содержит 9 рисунков и 7 таблиц. ■

КРАТКОЕ СОДЕРЖАНИЕ РАБОЩ,

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

В первой главе дана обобщенная постановка задачи:

- требуется определить оптимальную на заданном множестве измерительных средств структуру измерительного канала, обеспечивающего преобразование заданного в техническом задании измерительного сигнала SBX в заданный сигнал SBU, с учетом требований, предъявляемых со стороны сигналов-(датчиков), а также вектора ограничений {wp,. p£Q), накладываемых на реализацию канала и функции цели критерия эффективности.

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

ся как совокупность последовательно и"параллельно выполняемых операций (0):

где 0„_____Oj - отдельные измерительные операции, п -

число операций.

Т.е. для того, чтобы синтезировать ИК, выполняющий определенный набор {0} необходимо на основе имеющейся в наличии базы измерительно-вычислительных средств /вопросы ее организации 'детально рассмотрены/ подобрать совокупность исполнителей с необходимыми 0t в заданной последовательное^ выполнения.

Т. о. получим ИК, состоящий из п компонентов, связанны; между собой очередностью измерительно-вычислительных преоб' разований. причем вариантов может быть множество.

Представлена общая ' формализованная запись постанови задачи,

Необходимо найти оптимальный вариант структуры ИК: • е* = argmin(Wp. (Еа)) или е* = argjnax(wp-;(E^)),

Еа задается : SBX = OieJ'Seux и 0(e) з 0„ •... ■ Oj • — • Oj, 6ЕЕ, wp (e)<wp. , еЕЕ, p£Q, , Wp(e)<wp, , e£E, peQz, wp2.<wp (e)<Wp. , eeE, p6Q3.

• где E - множество возможных вариантов реализации струк туры ИК; wp(е) - оценка значения р-параметра варианта структуры на основе параметров составляющих компонентов; ОО — набор выполняемых измерительно-вычислительных операций Sbx- sbux' ~ ВИД сигнала на входе и на выходе канала соот ветственно.

В процессе проектирования возникает войрос физической i информационной сопрягаемости составляющих канал компонентов Учет сопрягаемости является мощным фактором отсева недопус тимых вариантов. ' Для анализа сопрягаемости введено понята функции наследственности:

ri. CL(Sout (et ),Sinp(é2 ) ) = true Eû(e,,e2) = 4

: AO, CLfSoutfej),SInp(e2)) = ialsh

, где e,, ег - передающий и воспринимающий компоненты; Sout(ej),Slnp(e2) - функции,, описывающие множества выходны

[ входных сигналов соответствующих компонентов: :L(Sout(e,).Slnp(ez)) - Функция соответствия классов выход-юго и входного сигналов.

Тогда дополнительное условие: п

П EQdnpie^.ejM. e^Ej.

»• t "■

где Inp(ej) - функция определяющая компонент ИК, подключаемый к 1-компоненту; Et={e1(n ,... ,е1(1(1)).....еИМ)1

- множество реализаций i-компонента ИК. 1(1) = {l,ft >. . ft = |Et(<»; EQ(.) - функция анализа сопрягаемости /наследственности/ компонентов структуры .

Выделены две основные проблемы, ' которым посвящена первая глава:

1) Построение и исследование адекватных моделей описания ■ измерительного -' • канала и их взаимодействия ;ÜWp{)};{£}, {0} и др.).

2) Тесно связанная с первой задача выбора методов поиска оптимального варианта измерительного канала, на основе анализа свойств измерительного канала, поставленного технического задания и характеристик рассматриваемых методов оптимизации.

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

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

Наиболее перспективными для разработки прикладных алгоритмов поиска ИК оптимальной структуры представляются методы: ■" из точных - методы ПАиОВ (методы беспошаговой оптимизации); из приближенных - методы локальной оптимизации и методы случайного поиска.

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

Рассмотрены проблемы, связанные с выбором вида критерия

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

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

Пусть ИВ средство выполняет Oj измерительную операцию и имеет гипотетическую Rj г() , идеальную О и неидеальную RlH() нелинейную функцию преобразования, а сигнал на входе может быть истинный (идеальный) х, и реальный (неидеальный) х1н = xt + Axt- Тогда характеристика погрешности результата выполнения измерительного преобразования может быть представлена в виде собственной Äj (методической Д1м и инструментальной А1и) и А1т> трансформированной Через это преобразование:

Авих " + Л1т + Д1н + Alt.

где Д1х - Rlr (х1н) - Rt г ixt). с MW " »1г<*1н).

Ьи = RIH(Xih) " Rl (х1н)-

Суммирование составлявших погрешности проводится в соответствии с правилами суммирования случайных величин. Трансформированную погрешность Rt предлагается оценивать как функцию: Л, т « Н1Г1(Л1ВХ). где Д1ВХ - характеристика составляющей погрешности на входе Rt преобразования; Rirx0 -Функция трансформации Д1вх через Rlr() / для функциональных зависимостей предлагается восползоваться оценкой посредством максимума первой производной RlT по xt/.

Соответственно выдвигаются требования к погрешности на входе R,:

Ale* = Rirf вых ~ А1и - Al«).

где Rlri.О - фукнция трансформации Д1вых к входу /об-

ратная функция Rlrt()/.

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

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

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

В третьей главе приведены разработанные прикладные алгоритм поиска оптимального варианта структуры ИК.

Приведенные алгоритмы по принципу работы принадлежат к трем основным группам: 1) алгоритмы последовательного анализа и отсева вариантов: 2) алгоритмы беспошагового анализа и отсева;', 3) алгоритмы поиска приближенного решения на основе метода перестановок.

Первая группа включает в себя алгоритмы последовательного анализа и отсева вариантов PAV:

1. 1-1. заносим множество Е,- в массив частичных решений Е1.

2. Проведем процедуру отсева "бесперспективных" решений в массиве частичных решений на основе- условия оптимальности:

wp. (е1) < wp.' (ее1) wp (е1) < wp (ее1)', p£Q, wp (е1) > wp (ее1), peQ2 wp (е1) - wp (ее1), peQ3 CLiSouHe1 hSoutiee1)) = true.

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

3. 1=1+1, возьмем следующее Е, и применим процедуру

генерации нового массива частичные решений Е1 .на- основе перебора сочетаний элементов старого массива Е1"1 и множества Ei с учётом условий сопряжения компонентов.

4. Повторяем пл.2 и 3 пока не будут пройдены все блоки. Суть алгоритмов заключается в том, что область всех возможных решений разбивается на подобласти и производится попытка исключить "неперспективные" (доминируемые). Алгоритц усилен отсевом по введенным ограничениям (по типу Н см. ни--же)

Вторая, группа, включает в себя:, а) алгоритмы Н отсева заведомо ^ёдоцустимых решений по значениям введенных ограничений; б) алгоритм Hef отсева по введенному граничному значению целевой функции критерия .эффективности, аналогичные алгоритма^ Н; в) алгоритм HS отсева элементов смежных кмпо-нентор ИК|по параметрам входа и выхода и соответствующей им модели сопряжения.

В. основе алгоритмов второй группы лежит алгоритм Н,-

Алгоритм Н:

1. Производится 'последовательный отсев . элементов eul(l))€El (1 = U.n}), который состой? из |Q| /число ограничиваемых параметрор ИК/ элементарных процедур Нр (p€Q), каждая из которых, в свою очередь, заключается в отсеве по р - ограничению элементов eltl(U) . i = íl.n). 1(1) = íl,^}:

Wp (ep\Et. eiaun)^wp., pea,,

где ep = argmin wp(e). ee(E\Et )Uet (l (1), -

tf wp(ep\Ei, ei(Un)Xwp., p£Q2.

, где ep = argmax wp(e), e£(E\E! íl^ (1 U),

Отметим, что ep обеспечивает минимум функции wp(е) при фиксированном e1(l(U) для множества Et . Если вариант ер не единственный, то выбирается либо^' из них. Интервальные ограничения приводят *к•тому, что алгоритм отсева будет включать р себя проверку условий "не больше"- и "н& меньше"- одновременно.

2. После применения процедур Нр останутся усеченные множества Е/11 , причем Е^" Ех. Далее если ер отсевается хотя бы для одного р, то следует снова применить № и получить Е(2) и т.д. .Окончание применения Нр при условии, что ни один элемент больше не отсеивается.

Реализация конкретных алгоритмов отсева упирается в мо-

дели расчета суммарного параметра качества. ' В работе были рассмотрены алгоритмы для трех типов Моделей суммарного параметра качества: Н, - для аддитивной модели: Н* - для муль-" типликативлой модели; Н3 - для точностной.

По типу алгоритма Н построен'алгоритм отсева по введенному граничному значению целевой функции критерия эффективности V - НеГ (Hefj.Hef2.Hef3).

Третья группа включает в себя.,

а) Локальный поиск в ограниченной окрестности путем вхождения в допустимую область с(-"минимальными" потерями типа вектора спада \/зг.

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

Оператор перестановки алгоритма имеет вид:. ега' = аг^1п (»р.(е) - *гр.(е.)) . еб{0К, (е.) Л=(1,п)}

где е, - исходный вариант; ега* .- модифицированный вариант; ОК^е."), 1={1,п} - окрестность поиска модификаций по каждому компоненту.

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

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

б) Алгоритмы типа УБР не учитывают поведения функций суммарного параметра качества, на которые накладываются ог-

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

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

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

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

2) самыми критичными в отношении быстродействия и требований к выделяемым ресурсам памяти являются алгоритмы первой группы, но эти алгоритмы гарантируют получение реей совокупности оптимальных и близких к ним решений;

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

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

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

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

Основные этапы представленной методики:

1. Подготовка технического задания и технических огра-личений на систему.

2.■Формирование множеств, задающих пространство поиска оптимально го - 'решения.

3. .Анализ целесообразности применения алгоритмов мдо.

зД,-Анализ оперативной информации о ходе Процесса решения задачи.,

3,2. Анализ характеристик и условий применения,алгоритмов Мдо,

4. Применений алгоритмов выбранного ' МДО и накопление оперативной информации для последующих шагов..

5. Если решение найдено или не существует завершение с соответствующим сообщением иначе повтор п. 3 й к.

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАВОТЫ

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

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

3. Разработаны алгоритмы выбора структур и. состава ИК на основе Метода последовательного анализа и отсева йкриан-тов, обеспечивающие генерацию, отсев и расчет параметров всей 1 совокупности допустимых вариантов реализаций ИК и, в отличие от с »чествующих алгоритмов, направленные на оптимизацию характеристик погрешности канала

4. Разработаны два типа . алгоритмов поиска допустимых вариантов структуры и состава ИК на основе метода перестано-, вок, обеспечивающие нахождение пстгмлемых взр-ч» ов реализа-

ции и расчет их параметров. В основе оператор» перестановок алгоритмов используется принцип "жадного" цоиека.

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

6. Разработан пакет прикладных программ, осуществляющий поиск ИК оптимальной структуры"по предложенной методике-

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Алексеев В.В., Алин Г.Т. Многокритериальный обобщенный принцип оптимизации.измерительно - вычислительной цепи //Тезиры докл. 48-й научно - технич. конф. посвященной дню радио. Санкт-Петербург, 1993. - С. 97-98.

2. Алексеев В.В., Алин Г.Т. Применение комбинаторных методов в задачах структурного синтеза измерительно-вычислительных каналов // С-Петёрбург. электро-техн. ун-т. СПб.; 1993.-15 с. Деп в -Информприбор 02.10.93, N£131-^.93.

3. Алин Г.Т. _ Применение методов беспошаговой оптимизации в задачах структурного синтеза измерительно-вычислительных систем //СПб.:. радиоэлектроника и связь. 1993. - N1.. -' с. 67-72.

4. Алексеев В-В., Алин Г.Т. Применение метода динамического программирования в задачах структурного"синтеза измерительной цепи //Изв. С-Летербург. электротехн. ун-та им. В.И.Ульянова (Ленина): Сб. науч. тр. - СПб. ,1993. - Вып. 436. - С.88-92.

5. Алексеев В.В., Алин Г.Т.. Методы локального поиска в задачах структурного синтеза измерительно-вычислительных систем // Актуальные" проблемы радиотехники, электроники и связи. (Секция вычислительной техники")-. Теай^ы докл. 49-й научно - технич. конф. посвященной дню радио, Санкт-Петербург, 1994. - С. 8.