С І Яремчук - Визначення часових характеристик методів розена та g-проекції - страница 1

Страницы:
1  2 

ВІСНИК ЖДТУ № 2 (57)

Технічні науки

УДК 519.67

С.І. Яремчук, к.ф.-м.н., проф. Л.В. Рудюк, к.ф.-м.н., доц.

Житомирський державний технологічний університет

ВИЗНАЧЕННЯ ЧАСОВИХ ХАРАКТЕРИСТИК МЕТОДІВ РОЗЕНА ТА G-ПРОЕКЦІЇ

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

Вступ. Розглянемо таку задачу. В прямокутній області ££ необхідно знайти таке розміщення m геометричних об'єктів прямокутної форми Dj, j = 1,..., m, при якому обраний критерій якості досяг би екстремуму:

f (Z) -- extr, Z є G, (1) де fZ) - неперервна та неперервно-диференційована на G функція з градієнтом, що задовольняє на множині G умові Липшиця.

Основними характеристиками прямокутного об'єкта є його розміри та положення у

просторі, що визначається координатами його полюса Z(^b <^2,..., Цг), j = 1,..., m [1]. Полюсом прямокутника будемо називати точку перетину його діагоналей. Очевидно, розміщення m прямокутних об'єктів буде визначатись вектором

Z = (Zl, Z[1],Zm). Розміри області розміщення ££ визначаються вектором a(a1,a2,... an).

Система координат задається так, щоб початок координат знаходився в вершині n-вимірного паралелепіпеда ££, координатні осі співпадали з його ребрами і були спрямовані так, щоб точки ££ мали невід'ємні координати. Тоді область розміщення описується такою системою обмежень:

& > 0,

Ї2

І21

/2і

a1

&1

Рис. 1. Приклад розміщення прямокутників для двовимірного випадку

Мета. Множина припустимих розв'язків G поставленої задачі визначається:

1.   Умовами взаємного неперетинання прямокутників є:

- для кожної пари Ds, Dp прямокутників існує хоча б одне і є {1,...,n} таке, що:

/ГЦ;

2

р Л

s = 1,...,m-1; р = s +1,...,m.

2. Умовами належності прямокутників області розміщення ££ є: - для кожного прямокутника Dj виконується:

і = 1,...,n; j = 1,...,m .

(2)

(3)

Наведені обмеження (2), (3) описують множину, що є багатовимірною та має складну структуру Вона

1

/1

/1

120 © С.І. Яремчук, Л.В. Рудюк, 2011багатозв'язна, а також може бути незв'язною.

Використовуючи (2) та (3), множину припустимих розв'язків G можна представити у вигляді об'єднання підмножин Gk, кожна з яких є опуклою та описується системою лінійних нерівностей [2, 3]:

ls + lp

-PJ<LL

li

ls + lp

PP-PS<   i i Ь i      t> i —        - :

li

s = 1,..., m-1, p = s +1,..., m,

= 1,... , m.

Тобто виконується:

G = \jGk, де r = (2n)cm .

k=1

Кількість обмежень, що задають кожну з підмножин Gk, залежить від кількості прямокутників m та вимірності простору n і становить:

N = C2m + 2 • n m . (4) Тобто, розв'язання задачі оптимізації розміщення прямокутників у прямокутній області можна замінити розв'язанням r підзадач оптимізації тієї ж функції цілі на кожній з підмножин Gk (k = 1, 2,..., r), що являють собою опуклі багатогранники:

f {Zextr, Z є Gk, k = 1,..., r. (5) Викладення основного матеріалу. Метод проекції градієнта Розена

До розв'язання кожної з задач (5) можна застосувати метод проекції градієнта Розена, який полягає у такому [4, 5]:

1. Для поточного наближення до розв'язку задачі xk визначимо матрицю обмежень, активних у даному наближенні, А1.

2. Наступне наближення до розв'язку задачі xk+1 знаходиться за правилом:

xk+1 = xk + pkdk,dk = P(-Vf (xk)), (5) де Р - матриця проектування на множину припустимих розв'язків, яка визначається таким чином:

Р = Е - АГ1 АГУЧ. (6) Метод G-проекції

Для розв'язання задачі (5) було розроблено метод G-проекції, що враховує специфіку поставленої задачі. Основна ідея методу полягає в такому. Розглянемо матрицю активних обмежень:

- рядки цієї матриці, що відповідають обмеженням (3), описують умови належності прямокутників області розміщення і містять 2*m-1 нульових елементів та один одиничний елемент з відповідним знаком. Номер стовпчика, що містить одиничний елемент, визначає координату вектора розміщення прямокутників, на яку накладена умова належності прямокутника області розміщення;

- рядки матриці активних обмежень, що відповідають обмеженням (2), описують умови неперетинання прямокутників і містять 2*m-2 нульових елементів та два одиничних елементи з протилежними знаками. Номери стовпчиків, що містять одиничні елементи визначають координати вектора розміщення прямокутників, на які накладені умови неперетинання прямокутників.

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

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

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

- якщо k-ий стовпчик матриці активних обмежень нульовий, то обрана координата вважається «вільною», її зміна не виведе за множину припустимих розв'язків.

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

Алгоритм методу G-проекції

1.   Для поточного наближення до розв'язку задачі xk визначається матриця А1 - матриця обмежень,

v

2

l

2 2активних в даному наближенні.

2.   Наступне наближення до розв'язку задачі xk+1 знаходиться за правилом:

k+1        k   .   п ik

x    = x + pkd , де d визначається таким чином:

- якщо А1 для поточного наближення порожня, то покладемо dk = -Vf (xk);

- інакше (якщо А1 не порожня), то вектор спуска d будується за таким правилом.

Напочатку dk =-Vf (xk) для кожної координати антиградієнта функції цілі = 1,..., n*m) перевіряється відповідний стовпчик матриці А1.

- якщо s-ий (s є {1,...,n m}) стовпчик матриці А1 містить хоча б один одиничний елемент, знак якого

збігається зі знаком антиградієнта функції цілі, то s-та координата вектора Z вважається «стримуваною» (тобто її зміну необхідно заборонити). У векторі спуску відповідна координата покладається рівною 0.

Планування статистичного експерименту

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

Оскліьки і побудований метод G-проекції, і класичний метод Розена є ітераційними методами, для яких важко передбачити необхідну кількість ітерацій для отримання стаціонарних точок, зробити такі оцінки можна засобами математичної статистики, шляхом проведення модельних експериментів [6].

Складемо план подальших статистичних експериментів. Оберемо основною метою плану:

• зменшення загального об'єму обчислень при збереженні вимог до достовірності та точності результатів;

• збільшення інформативності кожного окремого експерименту.

Пошук плану експерименту відбувається в так званому факторному просторі.

Факторний простір - це множина параметрів моделі, значення яких дослідник може контролювати під час проведення модельного експерименту.

Значення факторів зазвичай називається рівнями. Якщо під час проведення експерименту дослідник може змінювати рівень факторів, експеримент називається активним, в іншому випадку - пасивним.

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

При цьому вважається, що значення змінної, яка вимірюється, отримається в ході експерименту та складається з двох елементів: У = fx) + e(x),

де fx) - функція відклику (невипадкова функція факторів); e(x) - похибка експерименту; x - точка в факторному просторі (поєднання рівнів факторів).

Очевидно, що у є випадковою змінною, оскільки залежить від випадкової величини e(x).

Дисперсія Dy змінної, що вимірюється, характеризує точність вимірювань та дорівнює дисперсії похибки експерименту Dy = D,,.

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

Параметри модельного статистичного експерименту для оцінки часової складності алгоритмів розв 'язання задачі оптимізації:

1. Випадкова змінна у, що вимірюється, обрана як час розв'язання обраної задачі оптимізації.

2. Факторний простір експерименту включає в себе такий фактор, як кількість прямокутників для розміщення, рівень якого буде змінюватись під час проведення експериментів. Тому експеримент, що буде проводитись, є активним.

Тактичне планування статистичного експерименту

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

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

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

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

• розподілу випадкової змінної у, що вимірюється;

• корельованості між собою елементів вибірки.

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

Такий підхід називається «формування простої випадкової вибірки» (ПВВ). При використанні ПВВ статистичний експеримент повторюється визначену кількість разів, потім отримані результати усереднюються (обчислюються математичне очікування та дисперсія змінної, що вимірюється).

Розглянемо один з основних варіантів обчислення необхідного об'єму випробувань N для отримання результатів із заданою точністю.

Кількість випробувань, що необхідно провести для того, щоб значення математичного очікування отриманих результатів у знаходилося б в інтервалі довіри (y - b; y + b) з ймовірністю (1 - а ), визначається за такою формулою:

N =

Z2 Dy

b

(7)

де Z - значення щільності ймовірності нормального розподілу, що визначається залежно від обраного а ; Dy - дисперсія випадкової величини; 2b - довжина інтервалу довіри.

Якщо потрібне значення дисперсії Dy до початку експерименту невідомо, необхідно виконати пробну серію із L випробувань та розрахувати на основі цих випробувань вибіркову дисперсію D.

D =

1

-Z (у, - у,)2

(8)

L -11=г' ' де yL - вибіркове середнє за результатами L випробувань.

Отримане значення D підставимо в (7) та розрахуємо попередню оцінку кількості випробувань N. Потім виконаємо (N - L) випробувань, що залишилися.

Обробка отриманих результатів

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

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

Нехай є послідовність із m точок:

(xo, уо), (xb У1),     (xm-1, ym-1);  (x, Ф xj при І Ф j,  І, j = 0 .. m-1).

Серед функцій визначеного класу Р необхідно знайти функцію Р(х), для якої величина (евклідова норма):

Jm-1 (Z Уі - P(x, ))2, i=0

приймає найменше значення.

Р - це лінійні комбінації деяких обраних функцій gj(x) (j = 0 .. n-1, n < якщо m), що називаються базисними, тобто:

P(x) = Z Cj gj (x).

Нехай А - матриця значень базисних функцій в абсцисах точок, у - вектор ординат цих точок, а с -вектор коефіцієнтів, що шукаються:

 

' g 0( x0)

g1(x0) ...

gn-1(x0) ^

 

( С Л

 

( У0 '

 

g 0( x1)

g1(x1) ...

gn-1( x1)

 

c1

 

y1

=

 

 

 

, c =

 

, y =

 

 

ч g 0( xm-1)

g1( xm-1)

gn-1 (xm-1 ) )

 

I Cn-1 J

 

\ ym-1 J

Вектор с шукається як розв'язок матричного рівняння AT •A c = Лт • у.

Страницы:
1  2 


Похожие статьи

С І Яремчук - Визначення часових характеристик методів розена та g-проекції