Конспект лекций case cals. Конспект_САСТ-2. Конспект лекций по дисциплине case и cals технологии по направлению подготовки
 Скачать 3.53 Mb.
|
|
Пример 2. Требуется описать с помощью сети Петри процессы возникно- вения и устранения неисправностей в некоторой технической системе, состоя- щей из М однотипных блоков; в запасе имеется один исправный блок; известны статистические данные об интенсивностях возникновения отказов и длительно- стях таких операций, как поиск неисправностей, замена и ремонт отказавшего блока. На рис. 11.4 представлена соответствующая сеть Петри. Отметим, что при числе меток в позиции, равном М, можно в ней не ставить М точек, а записать в позиции значение М. 218 М t 1 t 2 t 4 t 3 p 1 p 4 p 3 p 4 p 5 p 2 Рис. 11.4. Сеть Петри к примеру 2 В нашем примере значение М в позиции 2 p соответствует числу имею- щихся в системе блоков. Переходы отображают следующие события: 1 t – отказ блока, 2 t - обнаружение неисправного блока. 3 t – его замена, 4 t – окончание ре- монта. Очевидно, что при непустой позиции р 2 переход 1 t срабатывает, но с за- держкой, равной вычисленному случайному значению моделируемого отрезка времени между отказами. После выхода маркера из 1 t он попадает через 1 p в 2 t , если имеется метка в позиции р 6 , это означает, что обслуживающая систему бри- гада специалистов свободна и может приступить к поиску возникшей неисправ- ности. В переходе t 2 метка задерживается на время, равное случайному значению длительности поиска неисправности. Далее маркер оказывается в 3 p ,и если име- ется запасной блок (маркер в р 4 ), то запускается переход 3 t , из которого маркеры выйдут в р 2 р 5 и 6 p через отрезок времени, требуемый для замены блока. После этого в t 4 имитируется восстановление неисправного блока. Рассматриваемая модель описывает функционирование системы в услови- ях, когда отказы могут возникать и в рабочем, и в неисправном состояниях сис- темы. Поэтому не исключены ситуации, при которых более чем один маркер окажется в позиции p 6 . Анализ сетей Петри 219 Анализ сложных систем на базе сетей Петри можно выполнять посредст- вом имитационного моделирования СМО, представленных моделями сетей Пет- ри. При этом задают входные потоки заявок и определяют соответствующую ре- акцию системы. Выходные параметры СМО рассчитывают путем обработки на- копленного при моделировании статистического материала. Возможен и другой подход к использованию сетей Петри для анализа объ- ектов, исследуемых на системном уровне. Он не связан с имитацией процессов и основан на исследовании таких свойств сетей Петри, как ограниченность, безо- пасность, сохраняемость, достижимость, живость. Ограниченность (или К-ограниченностъ) имеет место, если число меток в любой позиции сети не может превысить значения К. При проектировании авто- матизированных систем определение К позволяет обоснованно выбирать емко- сти накопителей. Возможность неограниченного роста числа меток свидетельст- вует об опасности неограниченного роста длин очередей. Безопасность – частный случай ограниченности, а именно это 1-ограниченность. Если для некоторой позиции установлено, что она безопасна, то ее можно представлять одним триггером. Сохраняемость характеризуется постоянством загрузки ресурсов, т.е. const N A j j , где j N – число маркеров в j-и позиции, j A – весовой коэффициент. Достижимость M M y характеризуется возможностью достижения мар- кировки М из состояния сети, характеризуемого маркировкой М y Живость сети Петри определяется возможностью срабатывания любого перехода при функционировании моделируемого объекта. Отсутствие живости либо означает избыточность аппаратуры в проектируемой системе, либо свиде- тельствует о возможности возникновения зацикливаний, тупиков, блокировок. В основе исследования перечисленных свойств сетей Петри лежит анализ достижимости. Один из методов анализа достижимости любой маркировки из состояния М 0 – построение графа достижимости. Начальная вершина графа отображает М 0 , а остальные вершины соответствуют маркировкам. Дуга из M y в М означает со- 220 бытие M M y и соответствует срабатыванию перехода t. В сложных сетях граф может содержать чрезмерно большое число вершин и дуг. Однако при построе- нии графа можно не отображать все вершины, так как многие из них являются дублями (действительно, от маркировки M £ всегда порождается один и тот же подграф вне зависимости от того, из какого состояния система пришла в М А ). Тупики обнаруживаются по отсутствию разрешенных переходов из какой-либо вершины, т. е. по наличию листьев – терминальных вершин. Неограниченный рост числа маркеров в какой-либо позиции свидетельствует о нарушениях огра- ниченности. Приведем примеры анализа достижимости. Пример 3. Сеть Петри и граф достижимых разметок представлены на рис.11.5. На рисунке вершины графа изображены в виде маркировок, дуги помече- ны срабатывающими переходами. Живость сети очевидна, так как срабатывают все переходы, тупики отсутствуют. t 1 t 2 t 4 t 3 p 1 p 4 p 3 p 5 p 2 p 1 p 3 p 2 p 3 p 4 p 1 p 3 p 5 t 1 t 2 t 3 t 4 t 1 Рис. 11.5. Сеть Петри и ее граф достижимости к примеру 3 Пример 4. Сеть Петри и граф достижимых разметок представлены на рис. 11.6. Сеть, моделирующая двухпроцессорную вычислительную систему с общей памятью, является живой, все разметки достижимы. 221 t 1 t 2 t 4 t 3 p 1 p 4 p 3 p 5 p 2 p 8 p 9 p 6 p 7 t 5 t 7 t 6 p 1 p 2 p 3 p 4 p 2 p 3 p 4 p 7 p 2 p 3 p 6 p 3 p 4 p 8 p 2 p 3 p 9 p 3 p 4 p 5 Рис. 11.6. Сеть Петри и ее граф достижимости к примеру 4 11.3 Методы поиска оптимальных решений В САПР процедуры параметрического синтеза выполняются либо челове- ком в процессе многовариантного анализа (в интерактивном режиме), либо реа- лизуются на базе формальных методов оптимизации (в автоматическом режиме). В последнем случае находят применение несколько постановок задач оптимиза- ции. Наиболее распространенной является детерминированная постановка: за- даны условия работоспособности на выходные параметры Y и нужно найти поминальные значения проектных параметров X, к которым относятся пара- метры всех или части элементов проектируемого объекта. Назовем эту задачу оптимизации базовой. В частном случае, когда требования к выходным парамет- рам заданы нечетко, к числу рассчитываемых величин могут быть отнесены также нормы выходных параметров, фигурирующие в их условиях работоспо- собности. Если проектируются изделия для дальнейшего серийного производства, то важное значение приобретает такой показатель, как процент выпуска годных из- делий в процессе производства. Очевидно, что успешное выполнение условий работоспособности в номинальном режиме не гарантирует их выполнения при 222 учете производственных погрешностей, задаваемых допусками параметров эле- ментов. Поэтому целью оптимизации становится максимизация процента вы- хода годных, а к результатам решения задачи оптимизации относятся не только номинальные значения проектных параметров, но и их допуски, Базовая задача оптимизации ставится как задача математического про- граммирования , )) ( ( x f Extr D x (11.7) где F(X) – целевая функция, X – вектор управляемых (проектных) параметров; D – допустимая область в пространстве управляемых параметров. Запись (11.7) интерпретируется как задача поиска экстремума целевой функции путем варьирования управляемых параметров в пределах допустимой области. Таким образом, для выполнения расчета номинальных значений парамет- ров необходимо, во-первых, сформулировать задачу в виде (11.7), во-вторых, решить задачу поиска экстремума F(X). Сложность постановки оптимизационных проектных задач обусловлена наличием у проектируемых объектов нескольких выходных параметров, которые могут быть критериями оптимальности, но в задаче (11.7) целевая функция должна быть одна. Другими словами, проектные задачи являются многокритери- альными, и возникает проблема сведения многокритериальной задачи к одно- критериальной. Применяют несколько способов выбора критерия оптимальности. В частном критерии среди выходных параметров один выбирают в каче- стве целевой функции, а условия работоспособности остальных выходных пара- метров относят к ограничениям задачи (11.7). Эта постановка вполне приемлема, если действительно можно выделить один наиболее критичный выходной пара- метр. Но в большинстве случаев сказывается недостаток частного критерия (рис. 11.7). 223 На этом рисунке представлено двумерное пространство выходных пара- метров, для которых заданы условия работоспособности y 1 < T 1 и у 2 < Т 2 . Кривая АВ является границей достижимых значений выходных параметров. Это ограни- чение объективное и связано с существующими физическими и технологиче- скими условиями производства, называемыми условиями реализуемости. Об- ласть, в пределах которой выполняются все условия реализуемости и работоспо- собности, называют областью работоспособности. Множество точек простран- ства выходных параметров, из которых невозможно перемещение, приводящее к улучшению всех выходных параметров, называют областью компромиссов, или областью Парето. На рис. 7 участок кривой АВ относится к области Парето. В А Т 1 Т 2 y 1 y 2 Область работоспособности Область Парето Рис. 11.7. Области Парето и работоспособности Если в качестве целевой функции в случае, представленном на рис. 11.7, выбрать параметр у 1 , то результатом оптимизации будут параметры X, соответ- ствующие точке В. Но это граница области работоспособности и, следовательно, при нестабильности внутренних и внешних параметров велика вероятность вы- хода за пределы области работоспособности. Конечно, результаты можно улуч- шить, если применять так называемый метод уступок, при котором в качестве ограничения принимают условие работоспособности со скорректированной нормой в виде у 2 <Т 2 +A, где А – уступка. 224 Но возникает проблема выбора значений уступок, т. е. результаты оптими- зации будут иметь субъективный характер. Очевидно, что ситуация не изменит- ся, если целевой функцией будет выбран параметр y 2 , – оптимизация приведет в точку А. Аддитивный критерий объединяет (свертывает) все выходные параметры (частные критерии) в одну целевую функцию, представляющую собой взвешен- ную сумму частных критериев. Недостатки аддитивного критерия – субъективный подход к выбору весо- вых коэффициентов и неучет требований ТЗ. Аналогичные недостатки присущи и мультипликативному критерию. Более предпочтительным является максиминный критерий, в качестве це- левой функции которого принимают выходной параметр, наиболее неблагопо- лучный с позиций выполнения условий работоспособности. Для оценки степени выполнения условия работоспособности 2-го выходного параметра вводят запас работоспособности этого параметра S , и этот запас можно рассматривать как нормированный 2-й выходной параметр. Например, здесь и далее для лаконич- ности изложения предполагается, что все выходные параметры приведены к ви- ду, при котором условия работоспособности становятся неравенствами. Тогда целевая функция в максиминном критерии F(X)= min Z(X). Содержательную сторону оптимизации с учетом допусков поясняет рис. 11.8, на котором представлены области работоспособности и допусковая в двумерном пространстве управляемых параметров. 225 Э Х 1 Х 2 Допусковая область 0 Область Работо- способности Х ном Рис. 11.8. Области допусковая и работоспособности 11.4. Постановка задач структурного синтеза Процедуры синтеза проектных решений Принятие проектных решений охватывает широкий круг задач и процедур – от выбора вариантов в конечных и обозримых множествах до задач творческо- го характера, не имеющих формальных способов решения. Соответственно в АС применяют как средства формального синтеза про- ектных решений, выполняемого в автоматическом режиме, так и вспомогатель- ные средства, способствующие выполнению синтеза проектных решений в инте- рактивном режиме. К вспомогательным средствам относятся базы типовых про- ектных решений, системы обучения проектированию, программно-методические комплексы верификации проектных решений, унифицированные языки описа- ния ТЗ и результатов проектирования. Задачи синтеза структур проектируемых объектов относятся к наиболее трудно формализуемым. Существует ряд общих подходов к постановке этих за- дач, однако практическая реализация большинства из них неочевидна. Поэтому имеются лишь «островки» автоматического выполнения процедур синтеза среди «моря» проблем, ждущих автоматизации. Именно по этой причине структурный синтез, как правило, выполняют в интерактивном режиме при решающей роли инженера-разработчика, а ЭВМ иг- 226 рает вспомогательную роль: предоставление необходимых справочных данных, фиксация и оценка промежуточных и окончательных результатов. В ряде приложений, однако, имеются и примеры успешной автоматизации структурного синтеза; среди них заслуживают упоминания в первую очередь за- дачи конструкторского проектирования печатных плат и кристаллов БИС, логи- ческого синтеза комбинационных схем цифровой автоматики и вычислительной техники, синтеза технологических процессов и управляющих программ для ме- ханообработки в машиностроении и некоторые другие. Структурный синтез заключается в преобразовании описаний проектируе- мого объекта: исходное описание содержит информацию о требованиях к свой- ствам объекта, об условиях его функционирования, ограничениях на элементный состав и т. п., а результирующее описание должно содержать сведения о струк- туре, т. е. о составе элементов и способах их соединения и взаимодействия. Постановки и методы решения задач структурного синтеза в связи с труд- ностями формализации не достигли степени обобщения и детализации, свойст- венной математическому обеспечению процедур анализа. Достигнутая степень обобщения выражается в установлении типичной последовательности действий и используемых видов описаний при их преобразованиях в САПР. Исходное описание, как правило, представляет собой ТЗ на проектирование, по нему со- ставляют описание на некотором формальном языке, являющемся входным язы- ком используемых подсистем САПР. Затем выполняют преобразования описа- ний, и получаемое итоговое для данного этапа описание документируют – пред- ставляют в виде твердой копии или файла в соответствующем формате для пере- дачи на следующий этап. Важное значение для развития подсистем синтеза в САПР имеют разра- ботка и унификация языков представления описаний (спецификаций). Каждый язык, поддерживая выбранную методику принятия решений, формирует у поль- зователей САПР – разработчиков технических объектов определенный стиль мышления; особенности языков непосредственно влияют на особенности правил преобразования спецификаций. Примерами унифицированных языков описания 227 проектных решений являются язык VHDL для радиоэлектроники, он сочетает в себе средства для функциональных, поведенческих и структурных описаний, или язык Express – универсальный язык спецификаций для представления и обмена информацией в компьютерных средах. Задача принятия решений Имеется ряд подходов для обобщенного описания задач принятия проект- ных решений в процессе структурного синтеза. Задачу принятия решений (ЗПР) формулируют следующим образом: ЗПР =< А, К, Мод, П >, где А – множество альтернатив проектного решения, К = (К 1 , К 2 , ..., К т ) – мно- жество критериев (выходных параметров), по которым оценивается соответствие альтернативы поставленным целям; Мод: А -> К – модель, позволяющая для ка- ждой альтернативы рассчитать вектор критериев; П – решающее правило для выбора наиболее подходящей альтернативы в многокритериальной ситуации. В свою очередь, каждой альтернативе конкретного приложения можно по- ставить в соответствие значения упорядоченного множества (набора) атрибутов X= l ,x 2 ,---,x n >, характеризующих свойства альтернативы. При этом x t может быть величиной типа real, integer, Boolean, string (в последнем случае величину называют предметной или лингвистической). Множество X называют записью (в теории баз данных), фреймом (в искусственном интеллекте) или хромосомой (в генетических алгоритмах). Модель Мод называют структурно-критериальной, если среди Х i имеются параметры, характеризующие структуру моделируемого объекта. Основными проблемами ЗПР являются: • компактное представление множества вариантов (альтернатив); • построение модели синтезируемого устройства, в том числе выбор сте- пени абстрагирования для оценки значений критериев; • формулировка предпочтений в многокритериальных ситуациях (т. е. преобразование векторного критерия К в скалярную целевую функцию); • установление порядка (предпочтений) между альтернативами в отсут- ствие количественной оценки целевой функции (что обычно является следстви- 228 ем неколичественного характера всех или части критериев); • выбор метода поиска оптимального варианта (сокращение перебора вариантов). Присущая проектным задачам неопределенность и нечеткость исходных данных, а иногда и моделей, диктуют использование специальных методов ко- личественной формулировки исходных неколичественных данных и отношений. Эти специальные методы либо относятся к области построения измерительных шкал, либо являются предметом теории нечетких множеств. Измерительные шкалы могут быть: 1) абсолютными; 2) номинальными (классификационными), значения шкалы представляют классы эквивалентности, примером может служить шкала цветов; такие шкалы соответствуют величинам неколичественного характера; 3) порядковыми, если между объектами А и В установлено одно из сле- дующих отношений: простого порядка, гласящее, что если А лучше В, то В хуже А, и соблюдается транзитивность; или слабого порядка, т. е. либо А не хуже В, либо А не лучше В или частичного порядка. Для формирования целевой функции F(Х) производится оцифровка порядковой шкалы, т. е. при минимизации, если А предпочтительнее 5, то F(X a ) < F(X b ), где Х а и Х 6 – множества атрибутов объек- тов А и В соответственно; 4) интервальными, отражающими количественные отношения интервалов: шкала единственна с точностью до линейных преобразований, т. е. у = ах + b, a>0, x или у = ах, 0 a , или у = х + b . В большинстве случаев структурного синтеза математическая модель в виде алгоритма, позволяющего по заданному множеству X и заданной структуре объекта рассчитать вектор критериев К, оказывается известной. Например, такие модели получаются автоматически в программах анализа типа Spice, Adams или ПА-9 для объектов, исследуемых на макроуровне. Однако в ряде других случаев такие модели неизвестны в силу недостаточной изученности процессов и их взаимосвязей в исследуемой среде, но известна совокупность результатов на- 229 блюдений или экспериментальных исследований. Тогда для получения моделей используют специальные методы идентификации и аппроксимации (модели, полученные подобным путем, иногда называют феноменологическими). Среди методов формирования моделей по экспериментальным данным наиболее известны методы планирования экспериментов. Не менее популярным становится подход, основанный на использовании искусственных нейронных се- тей. Если же математическая модель |