Область наук:

  • Математика

  • Рік видавництва 2000


    Журнал: Известия Південного федерального університету. Технічні науки


    Наукова стаття на тему 'Алгоритм адаптивного розміщення фрагментів топології НВІС'

    Текст наукової роботи на тему «Алгоритм адаптивного розміщення фрагментів топології НВІС»

    ?Известия ТРТУ

    Тематичний випуск

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

    Пропонується алгоритм отримання субоптимальних розкладів, заснований на субградієнтного процедурі рішення двоїстої завдання. В основу якого покладена ідея алгоритму Удзави [1]. Пропонований алгоритм не гарантує отримання точного рішення вихідної задачі, так як в силу її целочисленности може мати місце "стрибок подвійності". Однак, одержувані субоптимальних рішення є прийнятними.

    Створений на основі запропонованого алгоритму програмний продукт використаний в лабораторії ВДАУ.

    ЛІТЕРАТУРА

    1. 1. Uzawa H. Iterative methods for concave programming // Studies in linear and nonlinear programming (Arrow, Hurvies, Uzawa etc.). - Stanford University Press, 1958.

    УДК 681.1

    А. В. Мухлаев АЛГОРИТМ АДАПТИВНОГО РОЗМІЩЕННЯ ФРАГМЕНТІВ ТОПОЛОГІЇ НВІС

    Доцільним представляється деяка оптимізація початкового розміщення для осередків, що містять обмежене число под'ячеек (до 1000) за допомогою ітераційних алгоритмів перерозміщення. При цьому час роботи САПР в розрахунку на одну таку осередок збільшується на 20%, а в загальному обсязі не більше, ніж на 10%.

    В усіх промислово експлуатованих САПР використовуються ітераційні алгоритми розміщення, засновані на парних перестановках елементів. Однак, A-перестановочность алгоритми дають якісніші результати.

    Відзначимо, що під A-перестановочность алгоритмом будемо розуміти ітераційний алгоритм, який організовує одночасно перестановку A-елементів з метою підвищення значення деякого критерію. 3-перестановочность алгоритми дають, 2 -мів. Однак, для реальних завдань великої розмірності A>4 дає найкращий результат. Оптимальне значення A лежить в межах 3 * 5. Очевидно, що найбільш доцільним було б динамічне відстеження величини. Таке відстеження можливо шляхом застосування методів альтернативної адаптації. Постановка завдання в цьому випадку буде наступною Нехай є 4 альтернативних алгоритму покращення початкового розміщення Ai (A = 2, A = 3, A = 4, A = 5). Необхідно для вирішення потоку завдань розміщення Xi, ..., Xk динамічно вибирати один з алгоритмів Ai,

    m

    У Fk ^ max ,

    m 5

    k = 1

    Матеріали Міжнародної конференції

    "Інтелектуальні САПР"

    де Бк - показник якості рішення задачі.

    Для вирішення поставленого завдання застосуємо АА, описаний в розділі 2.1. так само, як і там, АА є четвірку А = {А, 8, У, Б} .

    Тільки безліч дій АА буде моделювати в даному випадку всі чотири ^ -перестановочних алгоритму (Л = 2, 3, 4, 5).

    Структуру алгоритму оптимізації результату розміщення, розрахованого на метод перетинів, можна представити таким чином:

    1. .

    2. Лічильник ітерацій 1 = 1.

    3. Л-перестановки елементів через лінії перетинів.

    4., .5, .

    5. Якщо 1<К, то 1 = 1 + 1 і до п.3.

    6. Оцінка АА результатів роботи Л-перестановочного алгоритму і прийняття рекомендацій за величиною Л на слідую щем кроці.

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

    УДК 681.3.001

    Е.Е. Малютіна

    Побудова АДАПТИВНИХ сіток ЗА ДОПОМОГОЮ ГЕНЕТИЧНОГО АЛГОРИТМУ

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

    мической адаптації сітки при вирішенні нестаціонарних задач.

    Розглядається задача апроксимації функції Дх), заданої на деякій множині В. На У задається разностная сітка {х,} 1 = 0 ... N-1. Потрібно знайти розташування точок сітки {х,} при фіксованому И, найкращим чином апроксимуючих функціюДх) в сенсі норми

    (

    | (/ - /) 2dx

    "_ \>г

    I / 2 ^ х

    В

    де / - ^ соковито-лінійна аппроксімаціяДх), задана на сітці {х,}.

    В якості тестової функції розглядається функція виду


    Завантажити оригінал статті:

    Завантажити