РОЗДІЛ 2
ВИПАДКОВИЙ ПОШУК ЯК МЕТОД ВИРІШЕННЯ ЗАДАЧ НЕЛІНІЙНОГО ПРОГРАМУВАННЯ
2.1. Постановка задачі пошукової оптимізації.
Сформулюємо задачу пошукової оптимізації як багатоетапний процес збирання інформації й ухвалення рішення на базі отриманої інформації. З цією метою введемо поняття про простір пошуку й область пошуку. На відміну від реального уявлення про простір (одне-, двох-, або тривимірного) математика оперує з - вимірним простором або гіперпростором. Об'єкт, що зазнає оптимізації, як правило, являє собою систему з входами і виходами. Входи визначаються ? вимірним вектором керування . Розмірність простору визначається кількістю незалежних керуючих змінних, що варіюються в процесі пошуку. У графічному змісті кожна з керуючих змінних вектора визначає одну з осей координат, початок яких міститься в деякій вихідній точці простору параметрів, і яка може переміщатися в допустимій області в процесі пошуку.
Об'єкт, що зазнає оптимізації, характеризується скалярним виходом Q, величина якого визначається вектором керуючих змінних :
, (2.1)
де F ? деяка скалярна детермінована функція векторного аргументу. Ця функція визначає показник якості об'єкта і її прийнято називати функцією цілі. Функція цілі може через вектор керуючих змінних виражати якість досліджуваного процесу на різних етапах пошуку. Тому функцію цілі інакше називають критерієм якості. Як правило, функція цілі являє собою математичну модель фізичного, енергетичного, економічного і т.п. стану досліджуваного об'єкта або процесу.
Допустима область керуючих змінних виділяється в просторі набором обмежень. Обмеження можуть бути геометричними, фізичними, економічними, енергетичними або нести в собі будь-який інший зміст, обумовлений постановкою задачі. Введемо вектор обмежень .
Під пошуком надалі будемо припускати процес виділення з заданої множини елементів одного , що задовольняє визначеній умові
, (2.2)
де ? ? наперед задане число.
Ціллю пошуку є досягнення екстремального стану об'єкта і визначення такого вектора керуючих змінних , котрий доставить цей стан.
Процес пошуку поділяється на етапи. На кожному етапі виконується збирання інформації і приймається рішення про подальший напрямок пошуку. Таким чином, пошук є багатоетапным процесом збирання інформації й ухвалення рішення на базі отриманої інформації [166].
Задача математичного програмування може бути сформульована таким чином: знайти вектор керуючих змінних
, (2.3)
який доставить мінімум (максимум) функції цілі:
(2.4)
при виконанні обмежень:
, (2.5)
де обмеження можуть приймати вигляд: ; = 0 або .
Ціль пошуку ? стан Х* ? не завжди досягається. Однак цей стан характеризує межу, що можлива при вирішенні задачі.
На рис.2.1 наведений приклад графічного уявлення двовимірної задачі математичного програмування. Тонкими лініями зображені лінії рівня цільової функції, більш товстими - обмеження. Тут же показана траєкторія переміщення системи пошуку до екстремуму функції.
В процесі збирання інформації пошук може адаптуватися. Роль адаптації виконує навчання, тобто встановлення наступності між двома наступними один за одним робочими кроками. Навчання системи пошуку відбувається в результаті урахування фактора передісторії, що визначає вплив попередніх кроків на вибір наступних кроків пошуку. Процес навчання може відбуватися за такою схемою: на ?му етапі з точки виконуються спробні кроки і визначається цільова функція в точках , обраних деяким чином навколо точки .
Рис.2.1. Переріз простору керуючих
параметрів оптимізованої системи
Отримана таким чином інформація про поведінку цільової функції в районі вихідної точки дозволяє прийняти рішення про перехід системи в іншу точку , причому зменшення або збільшення керуючої змінної визначається відповідно до обраної функції рішення:
, (2.6)
де ? фактор передісторії.
Випадковий вибір стану, у якому визначається значення функції якості, відбувається відповідно до вимірного закону розподілу
, (2.7)
який може формуватися в процесі пошуку.
Процес збирання інформації також може адаптуватися. Адаптація виявляється в зміні щільності розподілу (2.6) протягом збирання інформації. Це означає, що наступні кроки в просторі параметрів розташовуються таким чином, щоб нести найбільшу інформацію про градієнтний напрямок.
Під час пошуку урахування обмежень (2.5) може виконуватися різними методами. Один з універсальних методів називається методом "штрафних" функцій [181]. Метод полягає в тому, що оптимізований об'єкт "штрафується" шляхом відповідного збільшення функції якості в зоні обмежень при порушенні обмежень, причому, чим більш порушуються обмеження, тим більшим є "штраф". Для цього формується новий показник якості, мінімізація якого при порушенні обмежень призводить до мінімізації обмежень, тобто
(2.8)
Розрив функції на межі обмежень, коли , може бути усунутий таким чином:
(2.9)
Тут ? вагові коефіцієнти відповідних обмежень, що вибираються досить великими.
2.2. Моделі об'єкта, що зазнає оптимізації
Ефективність пошукової процедури визначається декількома показниками, серед яких найбільш важливими є швидкодія і збіжність. Звичайно ефективність пошуку визначають, порівнюючи різні алгоритми, що працюють в однакових умовах. При визначенні однакових умов йдеться про вид цільової функції й обмежень, район