Постановка задач структурного синтезу;

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

Відповідно в САПР застосовують як засоби формального синтезу проектних рішень, які виконується в автоматичному режимі, так і допоміжні засоби, сприяючі виконанню синтезу проектних рішень в ітеративному режимі. До допоміжних засобів відносяться бази типових проектних рішень, системи навчання проектуванню, програмно-методичні комплекси верифікації проектних рішень, уніфіковані мови опису ТЗ і результатів проектування.

Завдання синтезу структур проектованих об'єктів відносяться до тих, які найважче формалізується.

Існує ряд загальних підходів до постановки цих завдань, проте практична реалізація більшості з них неочевидна. Тому є лише “острівці” автоматичного виконання процедур синтезу серед “моря” проблем, які очікують автоматизації.

Саме з цієї причини структурний синтез, як правило, виконують в ітеративному режимі при вирішальній ролі інженера-розробника, а ЕОМ грає допоміжну роль: надання необхідних довідкових даних, фіксація і оцінка проміжних і остаточних результатів.

Проте у ряді застосувань є і приклади успішної автоматизації структурного синтезу у ряді застосувань; серед них заслуговують згадки в першу чергу завдання конструкторського проектування друкарських плат і кристалів НВІС, логічного синтезу комбінаційних схем цифрової автоматики і обчислювальної техніки, синтезу технологічних процесів і керуючих програм, для механічної обробки в машинобудуванні і деякі інші.

Структурний синтез полягає в перетворенні описів проектованого об'єкту: початковий опис містить інформацію про вимоги до властивостей об'єкту, про умови його функціонування, обмеженнях на елементний склад і тому подібне, а результуючий опис повинен містити відомості про структуру, тобто про склад елементів, способи їх з'єднання і взаємодії.

Постановки і методи вирішення завдань структурного синтезу у зв'язку з труднощами формалізації не досягли ступеня узагальнення і деталізації, властивого математичному забезпеченню процедур аналізу. Досягнутий ступінь узагальнення виражається у встановленні типової послідовності дій і використовуваних видів описів при їх перетвореннях в САПР. Початковий опис, як правило, є ТЗ на проектування, по ньому складають опис на деякій формальній мові, що є вхідною мовою використовуваних підсистем САПР. Потім виконують перетворення описів, і отримуваний підсумковий для даного етапу опис документують - представляють у вигляді твердої копії або файлу у відповідному форматі для передачі на наступний етап.

Важливе значення для розвитку підсистем синтезу в САПР мають розробка і уніфікація мов представлення описів (специфікацій). Кожна мова, підтримуючи вибрану методику ухвалення рішень, формує у користувачів САПР - розробників технічних об'єктів певний стиль мислення; особливості мов безпосередньо впливають на особливості правил перетворення специфікацій. Прикладами уніфікованих мов опису проектних рішень є мова VHDL для радіоелектроніки, він поєднує в собі засоби для функціональних, поведінкових і структурних описів, або мова Express - універсальна мова специфікацій для уявлення і обміну інформацією в комп'ютерних середовищах.

Завдання прийняття рішення. Є ряд підходів для узагальненого опису завдань ухвалення проектних рішень в процесі структурного синтезу.

Завдання прийняття рішення (ЗПР) формулюють таким чином:

,

де — множина альтернатив проектного рішення, — множина критеріїв (вихідних параметрів), по яких оцінюється відповідність альтернативи поставленим цілям; Мод: — модель, що дозволяє для кожної альтернативи розрахувати вектор критеріїв, П - вирішальне правило для вибору найбільш відповідної альтернативи в багатокритерійній ситуації.

У свою чергу, кожній альтернативі конкретного застосування можна поставити у відповідність значення впорядкованої множини (набору) атрибутів , які характеризують властивості альтернативи. При цьому xi може бути величиною типу real, integer, boolean, string (у останньому випадку величину називають лінгвістичною або наочною). Множина Х називають записом (у теорії баз даних), фреймом (у штучному інтелекті) або хромосомою (у генетичних алгоритмах). Модель Мод називають структурно-крітеріальною, якщо серед Хi є параметри, які характеризують структуру модельованого об'єкту.

Основними проблемами в ЗПР є:

- компактне представлення множин варіантів (альтернатив);

- побудова моделі пристрою, який синтезується, зокрема вибір ступеня абстрагування для оцінки значень критеріїв;

- формулювання переваг в багатокритерійних ситуаціях (тобто перетворення векторного критерію К в скалярную цільову функцію);

- встановлення порядку (переваг) між альтернативами у відсутність кількісної оцінки цільової функції (що зазвичай є наслідком некількісного характеру всіх або частини критеріїв);

- вибір методу пошуку оптимального варіанту (скорочення перебору варіантів).

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

Вимірювальні шкали можуть бути:

1) абсолютними;

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

3) порядковими, якщо між об'єктами K і I встановлене одне з наступних відносин: простого порядку, що свідчить, що якщо K краще B, то B гірше A, і дотримується транзитивність; або слабкого порядку, тобто або A не гірше B, або A не краще B; або часткового порядку. Для формування цільової функції F(X) проводиться оцифрування порядкової шкали, тобто при мінімізації, якщо A переважно B, то - множина атрибутів об'єктів А і В відповідно;

4) інтервальними, такими, що відображають кількісні відносини інтервалів: шкала єдина з точністю до лінійних перетворень, тобто , або y=ax при , або .

В більшості випадків структурного синтезу математична модель у вигляді алгоритму, який дозволяє по заданій множинаі Х і заданій структурі об'єкту розрахувати вектор критеріїв К, виявляється відомою. Наприклад, такі моделі виходять автоматично в програмах аналізу типу Spice, Adams або ПА-9 для об'єктів, досліджуваних на макрорівні. Проте у ряді інших випадків такі моделі невідомі через недостатню вивченість процесів і їх взаємозв'язків в досліджуваному середовищі, але відома сукупність результатів спостережень або експериментальних досліджень. Тоді для отримання моделей використовують спеціальні методи ідентифікації і апроксимації (моделі, отримані подібним шляхом іноді називають феноменологічними).

Серед методів формування моделей за експериментальними даними найбільш відомі методи планування експерименту. Не менш популярним стає підхід, який базується на використанні штучних нейронних мереж.

Якщо ж математична модель X __K залишається невідомою, то прагнуть використовувати підхід на базі систем штучного інтелекту (експертних систем).

Можливості практичного вирішення завдань дискретного математичного програмування (ДМП) вивчаються в теорії складності завдань вибору, де показано, що завдання навіть помірного розміру, що відносяться до класу NP-повних завдань, в загальному випадку вдається вирішувати тільки приблизно.

Тому більшість практичних завдань структурного синтезу вирішують за допомогою наближених (евристичних) методів. Це методи, що використовують специфічні особливості того або іншого класу завдань і не гарантуючі отримання оптимального рішення. Часто вони приводять до результатів, близьких до оптимальних, при прийнятних витратах обчислювальних ресурсів.

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

Нарешті, у відсутність обгрунтованих моделей Мод їх створюють, грунтуючись на експертних знаннях у вигляді деякої системи штучного інтелекту.

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

Простий спосіб завдання множина C - явне перерахування всіх альтернатив. Семантика і форма опису альтернатив істотно залежать від застосування. Для представлення таких описів в пам'яті ЕОМ і доступу до них використовують інформаційно-пошукові системи (ІПС). Кожній альтернативі в ІПС відповідає пошуковий образ, що складається із значень атрибутів xi і ключових слів вербальних характеристик.

Явне перерахування альтернатив при представленні множина альтернатив можливо лише при малій потужності А. Тому в більшості випадків використовують неявний опис А у вигляді способу (алгоритму або набору правив Р) синтезу проектних рішень з обмеженого набору елементів Q. Тому тут А = <P,q>, а типовий процес синтезу проектних рішень складається з наступних етапів:

1) формування альтернативи Ki (це може бути вибір з бази даних ІПС по сформованому пошуковому розпорядженню або генерація з Q відповідно до правил Р);

2) оцінка альтернативи за наслідками моделювання за допомогою моделі Мод;

3) ухвалення рішення (виконується ЛПР - особою, що ухвалює рішення, або автоматично) щодо переходу до наступної альтернативи або припинення пошуку.

Для опису множинаі Р і Q використовують наступні підходи.

1. Морфологічні таблиці і альтернативні І-АБО-ДЕРЕВА.

2. Представлення знань в інтелектуальних системах- фрейми, семантичні мережі, продукції.

3. Генетичні методи.

4. Бази фізичних ефектів і евристичних прийомів, вживані при вирішенні завдань винахідницького характеру.

Морфологічні таблиці. Морфологічна таблиця (М) є узагальненою структурою у вигляді множинаі функцій, виконуваних компонентами об'єктів даного класу, що синтезуються, і підмножин способів їх реалізації. Кожній функції можна поставити у відповідність один рядок таблиці, кожному способу її реалізації - одну клітку в цьому рядку. Отже, в морфологічних таблицях елемент Mij означає j-й варіант реалізації i-й функції в класі технічних об'єктів, що описується матрицею E.

Іншими словами, множина альтернатив можна представити у вигляді відношення М, званого морфологічною таблицею М = <X, R>, де X - множина властивостей (характеристик або функцій), властивих об'єктам даного типу, n - число цих властивостей, R = < R1, R2...,Rn>, Ri - множина значень (способів реалізації) iго властивості, потужність цієї множини далі позначена Ni. При цьому власне множина альтернатив А представлено композицією множинаі Ri, тобто кожна альтернатива включає по одному елементу (значенню) з кожного рядка морфологічної таблиці. Очевидно, що загальне число альтернатив до, що представляються морфологічною таблицею, рівно

Морфологічні таблиці зазвичай вважають засобом неавтоматизованого синтезу, що допомагає людині проглядати компактно представлені альтернативи, долати психологічну інерцію. Останнє пов'язане з тим, що увага ЛПР звертається на варіанти, які без морфологічної таблиці залишалися б поза його полем зору.

Власне таблиця М не містить відомостей про спосіб синтезу. Проте на базі М можлива побудова методів синтезу з елементами алгоритмізації. У таких методах вводиться метризація морфологічного простору. Морфологічний простір складають можливі закінчені структури, приймається, що відстань між структурами С1 і С2 є число неспівпадаючих елементів (кожна клітка М є один елемент). Тому можна говорити про околиці рішень. Далі виходять з припущення про компактність “хороших” рішень, яке дозволяє замість повного перебору обмежуватися перебором в малій околиці поточної точки пошуку. Таким чином, гіпотеза про “компактність” і метризація простору рішень фактично приводять до побудови математичної моделі, до якої можна застосувати методи дискретної оптимізації, наприклад локальні методи.

До недоліків М відносяться неврахування заборонених поєднань елементів в закінчених структурах і віддзеркалення складу елементів в структурах без конкретизації їх зв'язків. Крім того, морфологічні таблиці будують в припущенні, що множина Ri взаємно незалежна, тобто склад способів реалізації i-й функції не міняється при зміні значень інших функцій. Очевидно, що припущення про взаємну незалежність множин Ri виправдане лише в порівняно простих структурах. Останній недолік усувається шляхом узагальнення методу морфологічних таблиць - при використанні методу альтернативних (І-АБО) графів.

Альтернативні графи. Будь-яку морфологічну таблицю можна представити у вигляді дерева (мал. 4.12). На малюнку функції представлені вершинами І (темні кухлі), значення функцій - вершинами АБО (світлі кухлі). Очевидно, що таблиця представляє множина однотипних об'єктів, оскільки всі вони характеризуються одним і тим же множинам функцій.

Для різнотипних об'єктів застосовують багатоярусні альтернативні графи. Наприклад, на мал. 4.13 показаний двох'ярусний граф, в якому для різних типів об'єктів передбачені різні підмножини функцій.

Якщо допустити деяку надмірність при зображенні І-АБО- графа, то його можна перетворити на І-АБО-ДЕРЕВО, що веде до певних зручностей. Очевидно, що І-АБО-ДЕРЕВО можна представити як сукупність морфологічних таблиць. Кожна І вершина дерева відповідає приватній морфологічній таблиці, тобто множинаі функцій так, що i-я гілка, що виходить, відображає i-ю функцію. Кожна АБО вершина, інцидентна i-й гілки, відповідає множині варіантів реалізації i-й функції, при цьому j-я витікаюча з АБО вершини гілку відображає j-й варіант реалізації.

Алгоритмізація синтезу на базі І-АБО-ДЕРЕВ вимагає введення правил вибору альтернатив в кожній вершині АБО. Ці правила найчастіше мають евристичний характер, пов'язані з вимогами ТЗ, можуть відображати заборони на поєднання певних компонентів структур.

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

де :ij = true, якщо до оцінюваного варіанту увійшов елемент Еij, інакше :ij = false. Умова (4.29) означає, що в допустиму структуру не можуть входити одночасно елементи Еij і Еpq. Сукупність обмежень типу (4.29) можна представити як систему логічних рівнянь з невідомими :ij. Тоді задачу синтезу можна вирішувати еволюційними методами, якщо заздалегідь або одночасно з нею вирішувати систему логічних рівнянь (завдання про здійснимість).

Числення. Очевидно, що в більшості випадків структурного синтезу замість явного представлення всієї множини проектних рішень, що не реалізовується, задають множина елементів і сукупність правил об'єднання цих елементів в допустимі структури (проектні рішення).

Ця множина елементів і правил часто представляє у вигляді формальної системи (числення), тобто завдання синтезу має вигляд

,

де — алфавіт числення (алфавіт представлений базовими елементами, з яких синтезується структура);

— множина букв, не співпадаючих з буквами алфавіту і службовців для позначення змінних; — множина аксіом числення, під якими розуміються початкові формули (слова), що задаються, в алфавіті (наприклад, відповідності функцій і елементів); — множина правил виведення нових формул в алфавіті з аксіом і раніше виведених коректних формул.

Кожну формулу можна інтерпретувати як деяку структуру, тому синтез - це процес виведення формули, що задовольняє початковим вимогам і обмеженням.

Інші приклади компактного завдання множинаі альтернатив через множини зв'язаний з використанням систем штучного інтелекту, в яких є база даних, — база знань, або еволюційних методів, в яких — також база даних, — множина евристик, послідовність застосування яких визначається еволюційними і генетичними принципами.