Автоматизація проектування компютерних систем. Автоматизація проектування комп'ютерних систем Модуль I. Конспект лекцій з дисципліни Автоматизація проектування комп'ютерних систем

• Название: Конспект лекцій з дисципліни Автоматизація проектування комп'ютерних систем
• Анкор: Автоматизація проектування компютерних систем
• Дата: 30.05.2022
• Размер: 0.86 Mb.
• Имя файла: Автоматизація проектування комп'ютерних систем Модуль I.doc
• Тип: Конспект; #557364
• страница: 6 из 16

2.4Методи синтезу

2.4.1Метод послідовних наближень

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

Суть цього методу полягає у використанні циклу, що є послідовним чергуванням кроків генерації чергового варіанту і аналізу його якості (P -описів) на міру наближення до бажаного результату. Такий аналіз дозволяє визначити "напрям", в якому можуть бути отримані S -описів з більшою мірою відповідності шуканому результату, а зворотний напрям можна з розгляду виключити.

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

2.5Завдання оптимізації

Оптимальними вважаються ті значення, які задовольняють ТЗ і є кращими з досяжних.

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

Критерії - правила переваги порівнюваних варіантів. Основу критеріїв оптимізації складає цільова функція F(x), де х - безліч керованих параметрів. Вектори х з фіксованими значеннями визначають один з варіантів об'єкту і його характеристики.

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

Окрім цільової функції F(X) і переліку керованих параметрів (X) в постановку завдання оптимізації можуть входити обмеження типу рівності H(X) = 0 і нерівностей H(X)<>0. Часткою випадком обмежень типу нерівностей є прямі обмеження a_i<=x_i<=b_i, де a_i і b_i - гранично допустимі значення параметра x_i.

Область простору керованих параметрів, в якій виконуються задані обмеження, називає допустимою областю XD.

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

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

За наявності обмежень завдання оптимізації називається умовною оптимізацією, інакше - безумовною.

Область, в якій виконуються як прямі обмеження, так і умови працездатності, називається областю працездатності.

Таким чином, підсумкове формулювання завдання оптимізації при проектуванні має вигляд: экстремизировать цільову функцію F(X) в області XD, заданій обмеженнями H(X) = 0 і Ф(X)> 0.

Завдання оптимізації в такій постановці є завдання математичного програмування. При лінійності функцій F(X), H(X), Ф(X) - завдання лінійного програмування. Якщо хоч би одна з них нелінійна - завдання нелінійного програмування.

Якщо усе (чи частина) X - дискретні, то завдання дискретного (чи частково дискретного) програмування.

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

Завдання структурної оптимізації зводиться до побудови оптимальної структури S = (E, H). При цьому під оптимальним розумітимемо такий варіант структури, параметри якої задовольняють усім системним, конструктивним, технологічним, електричним і економічним вимогам ТЗ. При цьому критерій оптимальності, що описує якість проектованої структури, набуває екстремального значення.

2.5.1Критерії оптимізації

Приватні критерії оптимізації

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

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

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

Якщо критерій не враховує імовірнісний розкид параметрів - він детермінований, інакше - статистичний.

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

Можливі декілька підходів до вибору нормуючого дільника.

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

Другий підхід припускає приймати як нормуючих дільників те оптимальне значення, кіт. задано в ТЗ.

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

Цільова функція: F(x) = П Fi(x)

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

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

Цільова ф-ция: F(x) = П F_i(x)

У разі нерівноцінності приватних критеріїв необхідно ввести ваговий коефіцієнт C_i і тоді мультиплікативний критерій набере вигляду:

або

Гідністю мультиплікативного критерію є те, що при його використанні не вимагається нормування приватних критеріїв.

Недоліком - критерій може компенсувати надмірні зміни одних критеріїв за рахунок зміни інших.

Мінімаксний критерій.

Формально принцип максміна формулюється таким чином:

Необхідно вибирати таку безліч X0 е X, на якій реалізується максимум з мінімальних значень приватних критеріїв F(x₀) = max min {f_i(x)}.

Якщо приватні критерії f_i(x) слід мінімізувати, то використовується принцип мінімакса

F(x0) = min max {fi(x)}.

Аддитивні критерії вибирають, коли істотне значення мають абсолютні числові значення критеріїв при вибраному векторі X.

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

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

2.5.2Експертні оцінки як критерії

Метод приписування балів - експерти приписують бали кожному параметру в діапазоні {1,10} балів. Можливі і дробові значення і однакові оцінки.

Тоді H_i, k = h_i, k/((i=1, n) h_i, k;

C_i = (((k=1, L) H_i, k)/( ((i=1, n) ((k=1, L) H_i, k)

Метод ранжирування - Кожен з I експертів розставляє n критеріїв по порядку (в порядку убування значущості). На основі цієї оцінки кожному з параметрів привласнюється ранг, рівний n - 1. Це значення називається перетворений ранг i -го критерію, тоді

Сi = ((k=1, L)(ri, k/((i=1, n)((k=1, L) ri, k).