2М. В. Куклінський icon

2М. В. Куклінський




Скачати 126.95 Kb.
Назва2М. В. Куклінський
Дата17.08.2012
Розмір126.95 Kb.
ТипДокументи


Вісник НАУ. 2004. №1

УДК 519.6 (045)

1Ю.К. Зіатдінов, д-р техн. наук

2М.В. Куклінський


МОДЕЛІ ТА МЕТОДИ ОПТИМІЗАЦІЇ СКЛАДНИХ СИСТЕМ

Інститут інформатики НАУ, e-mail: 1oberst@nau.edu.ua; 2maximum_inc@ua.fm

Розглянуто проблеми оптимізації складних систем і основні моделі та методи оптимізації. Наведено нелокальний підхід до проблем оптимізації.

Вступ

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

Мета системного аналізу – підготовка передумов для створення системи з потрібними нам властивостями (системний синтез). Головною операцією при цьому є прийняття рішень, тобто деякий формалізований чи неформалізований вибір, здійснюваний людиною чи технічним пристроєм на основі даних системного аналізу. Оскільки складна система, як правило, характеризується суперечливими властивостями [2; 3], то й оптимізація складних систем виконується як багатокритеріальна (векторна).

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

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

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

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

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

У загальному випадку показники називаються критеріями якості і утворюють вектор . Його компоненти кількісно виражають властивості об’єкта при заданій сукупності аргументів оптимізації .

Цільова функція зв’язує критерії якості з аргументами оптимізації [2].

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

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

^ Аналіз досліджень і публікацій

Аналіз праці показує [2], що в міру ускладнення задач можливості їх сутто аналітичного розв’язку різко звужуються. Розв’язати сучасну складну задачу оптимізації навіть за наявності докладного математичного опису можна тільки числовим методом. Тому, як це не парадоксально, але і при повному знанні механізмів, і при повній відсутності даних про них не можна
обійтися без експериментальних процедур.
Тільки у першому випадку це буде обчис-
лювальний експеримент із застосуванням імітаційного моделювання, а у другому – організація серії натурних експериментів безпосередньо на об’єкті.

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

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

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

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

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

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

Градієнтні методи спираються на локальні
(в околах поточної точки) моделі цільової функції і тому недостатньо ефективні. Застосування локальних властивостей змушує часто змінювати напрям пошуку, що і призводить у підсумку до неефективної обчислювальної процедури [4].

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

Нелокальний підхід передбачає апроксимацію цільової функції деякою моделлю не в околах якоїсь точки, а у всій області визначення. Чим краще нелокальна модель описує цільову функцію, тим ближче розрахунковий екстремум до істинного. Але у відомих модифікаціях не-локальні апроксимаційні методи великого практичного значення не мають, тому що критерії якості алгоритмів оптимізації й апроксимації істотно розрізняються [5].

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

^ Постановка завдання

Нехай задана деяка компактна підмножина X (множина аргументів оптимізації) скінченновимірного евклідового простору , де п  1, що складається з елементів , на якому визначена обмежена знизу цільова функція f(x), яка належить деякому класу функцій: f(x)  .
Потрібно, використовуючи скінченну кількість обчислень функції f(x), оцінити величину

(1)

і знайти точку x*X, в якій ця оцінка реалізується.

Серед задач оптимізації є такі, про які заздалегідь відомо, що

,

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

. (2)

З огляду на те, що х* може бути визначено лише приблизно, відшукаємо яку-небудь точку з множини:

,

де  – деяка метрика на X;  – припустима по-
хибка за аргументом.

Розглянута постановка завдання є досить загальною. Задача максимізації випливає з виразу (1) чи (2) заміною f на –f.

^ Нелокальний підхід до оптимізації

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

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

В ідеалі функція ^ F(x,a) настільки добре описує цільову функцію f(x), що їх екстремуми збігаються. На практиці так не буває, тому вирішити задачу оптимізації “за один раз”, як правило, не можна.

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

У більшості практичних випадків ці вимоги виконуються в класі апроксимуючих поліномів другого порядку:

, (3)

де – коефіцієнти.

Для спрощення обчислювальних процедур можливі різні зрізання функції (3).

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

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

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

Коефіцієнти а визначаються розв’язанням
системи рівнянь

,

де – вузли інтерполяції.

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

.

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

,

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

Запропонована декомпозиція складної задачі оптимізації являє собою ітераційну послідов-ність більш простих нелокальних задач, причому кожна наступна обчислюється в меншій області визначення аргументів, чим попередня. Так зменшується протиріччя між критеріями якості алгоритмів апроксимації й оптимізації і використовуються переваги нелокального підходу. До нелокальної моделі F(x,а) ставлять вимоги унімодальності у відкритій області аргументів і диференційованості по цих аргументах. Апроксимаційній моделі ^ F(x,a) надається властивість адаптації за рахунок вибору коефіцієнтів а на кожній ітерації в області визначення аргументів меншої ніж на попередній ітерації. Основна ідея побудови алгоритму полягає в такому. На першій ітерації здійснюється апроксимація функції f(x) нелокальною моделлю F(x,a) на всій заданій множині аргументів X. У цій області виконаємо N обчислень функції f(x) у різних точках (вузлах апроксимації), що складають систему базисних точок . За отриманими даними обчислимо заданий набір коефіцієнтів що дозволяє перейти від моделі F(x,a) до вираження F(x). Далі, спираючись на вимогу унімодальності наближеної моделі, у відкритій області скористаємося необхідною умовою мінімуму функції

(4)

і знайдемо першу оцінку шуканої сукупності

аргументів як розв’язок системи рівнянь (4). Дискретна система базисних точок є гомео-морфним відображенням заданої неперервної області X. Отримана нова точка вводиться в систему базисних точок замість виключеної
старої (звичайно в ній f(x) максимальна).
Далі розрахунок повторюється для отриманої в такий спосіб нової системи базисних точок . За властивості гомеоморфізму

(5)

у тому розумінні, що гіперобсяг, зайнятий компактною підмножиною у просторі ,
менше ніж гіперобсяг, що відповідає підмножині (зазначені підмножини не обов'язково
вкладені). Оскільки в меншій області функція
^ F(x,a) точніше описує функцію f(x), то вираженню (5) відповідає послідовність нелокальних моделей з уточнюючими коефіцієнтами Звідси, згідно з функцією (4), випливає послідовність оцінок, які збігаються до точки х* істинного мінімуму функції f(x).

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

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

Висновки

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

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

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

Список літератури

1. Губанов В.А., Захаров В.В., Коваленко А.Я. Введение в системный анализ. – Л.: Ленинград. ун-т, 1988. – 232 с.

2. Воронин А.Н. Многокритериальный синтез динамических систем. – К.: Наук. думка, 1992. – 160 с.

3. Воронин А.Н., Зиатдинов Ю.К., Харченко А.В. Сложные технические и эргатические системы: методы исследования. – Харьков: Факт, 1997. – 240 с.

4. Банди Б. Методы оптимизации. – М.: Радио и связь, 1988. – 128 с.

5. Жиглявский А.А., Жилинскас А.Г. Методы поиска глобального экстремума. – М.: Наука, 1991. – 248 с.

Стаття надійшла до редакції 13.02.04.


Ю.К. Зиатдинов, М.В. Куклинский

Модели и методы оптимизации сложных систем

Рассмотрены проблемы оптимизации сложных систем и основные модели и методы оптимизации. Приведен нелокальный подход к проблемам оптимизации.

Yu.K. Ziatdinov, M.V. Kuklinskyy
Models and methods of optimisation of complex systems

The article considers the problems of optimization of complex systems. The main models and methods of optimization are considered as well. And unlocal approach to the problem of optimization was applied.


^ Куклінський Максим Володимирович (1979). Закінчив Національний авіаційний університет. Аспірант. Асистент кафедри інформаційних технологій Інституту інформатики Національного авіаційного університету. Напрям наукової діяльності – оптимізація складних систем.


^ Куклинский Максим Владимирович (1979). Окончил Национальный авиационный университет. Аспирант. Ассистент кафедры информационных технологий Института информатики Национального авиационного университета. Направление научной деятельности – оптимизация сложных систем.


^ Kuklinskyy Maxym (1979) graduated from the National Aviation University. Post-graduate student. Assistant of Faculty of Information Technologies of the Institute of Informatics of the National Aviation University. Optimization of complex systems.


Зіатдінов Юрій Кашафович (1955). Закінчив Харківський державний університет. Доктор
технічних наук, професор кафедри інформаційних технологій Інституту інформатики Національного авіаційного університету. Напрям наукової діяльності – оптимізація складних систем.


Зиатдинов Юрий Кашафович (1955). Окончил Харьковский государственный университет.
Доктор технических наук, профессор кафедры информационных технологий Інститута информатики Национального авиационного университета. Напрвление научной деятельности – оптимизация сложных систем.


Ziatdinov Yuriy (1955) graduated from the Kharkov State University. The Doctor of technical sciences, professor of Faculty of Information Technologies of the Institute of Informatics of the National Aviation
University. Optimization of complex systems.



Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи