Доцент Клочко О. В., студентка Побережна Л. В.

Вінницький національний агарний університет, Україна

МЕТОД СКАНУВАННЯ

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

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

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

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

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

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

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

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

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

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

Далі послідовно визначаються значення функції f (x) у всіх точках розбиття аргументу і в точках a і b і запам'ятовується найменше значення. Таким чином, мінімум може бути знайдений з точністю до h [1].

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

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

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

Література:

1. Івасюк Т. А. Методи випадкового пошуку і сканування / Т. А. Івасюк // [Електронний ресурс]. – Режим доступу: http://wiki.tntu.edu.ua/Метод_випадкового_пошуку_і_сканування

2. Математическая энциклопедия

3. Учебно-методический центр кафедры информационных технологий. [Електронний ресурс]. – Режим доступу: http://dit.isuct.ru/ivt/sitanov/Literatura/M171_1.html