Методи випадкового пошуку

Основна ідея методів випадкового пошуку полягає в тім, що

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

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

Загальним для всіх методів випадкового пошуку є застосування випадкових чисел у процесі пошуку. Розглянемо лише основні поняття про випадкові числа.

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

Випадковий вектор, визначений у n-мірному просторі

α = (α₁, α₂,..., α_n)

може з рівною імовірністю приймати будь-як напрямок у n-мірному просторі і має довжину, рівну 1. Такий вектор може бути отриманий з послідовності випадкових чисел β_j (j = 1, 2,..., n), рівномірно розподілених на інтервалі [-b, b].

Для перебування випадкового вектора a за допомогою послідовності випадкових чисел β, виразимо компоненти випадкового вектора α_j наступними співвідношеннями:

(5.67)

Вектор α, компоненти якого розраховуються по (5.67), характеризує випадковий напрямок у n-мірному просторі.

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

Нехай область простору нормованих перемінних

U_j (j = 1, 2,..., n) задана умовами:

0 < U_j < 1 (j = 1, 2,...,n) (5.68)

Для визначення координат випадкової крапки можна використовувати наступні співвідношення:

X_j = (b_j +b)/ (2.b) (j = 1, 2,... n) (5.69)

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

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

5.8.1. Метод сліпого пошуку

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

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

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

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

Так, наприклад, навіть при n=2 і з імовірністю P =0.5 для того, щоб положення крапки оптимуму визначити з точністю? = 0,001 необхідно виконати не менш S виборів випадкових крапок. Число виборів S можна оцінити по формулі

(5.70)

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

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

5.8.2. Метод випадкових напрямків

Алгоритм цього методу полягає в тім, що з крапки n-мірного простору, для якої цільова функція розрахована, виробляється крок у випадковому напрямку, обумовленому випадковим вектором α^(k). Величина кроку задається параметром h. У результаті знаходиться наступна крапка

U^(k+1) = U^(k) + h.α^(k) (5.71)

У новій крапці обчислюється значення цільової функції. Якщо при виконанні випадкового кроку h.α^(k), що приводить у крапку U^(k+1), виходить менше значення цільової функції, то крок вважається вдалим (у випадку пошуку мінімуму) і нове значення цільовий

функції запам'ятовується разом з координатами крапки U^(k+1). Потім робиться новий h.α^(k+1) у випадковому напрямку і т.д.

Якщо випадковий крок h.α^(k) виявляється невдалим, то продовжується вибірка наступного випадкового вектора α і з крапки U^(k) знову виконується крок. Спробні кроки з крапки U^(k) робляться доти, поки не буде знайдена крапка U^(k+1), у якій цільова функція буде мати менше значення. Потім спробні кроки виконуються з крапки U^(k+1).

Пошук закінчується, якщо після виконання серії з S кроків

меншого значення цільової функції знайти не удалося.

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

Критерієм закінчення пошуку служить мінімальний розмір кроку h_min, яким і задається точність визначення екстремуму.

5.8.3. Метод випадкових напрямків зі зворотним кроком

Цей метод випадкового пошуку власне кажучи являє собою поліпшення алгоритму випадкових напрямків. Відмітною його особливістю є те, що при невдалому кроці h.α^(k) із крапки U^(k) відразу ж виробляється крок у зворотному напрямку - h.α^(k). При достатнім видаленні від крапки оптимуму така стратегія пошуку виявляється дуже ефективною.

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

5.8.4. Одержання випадкових чисел

Послідовність випадкових чисел можна одержати одним з наступних способів:

- шляхом вибірки зі спеціальних таблиць;

- використовуючи датчики випадкових чисел;

- програмними методами.

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

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

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

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

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

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

5.8.4.1. Метод добутків

Довільно вибираються два числа β₀ і β₁, що мають однакове число значущих цифр m. Знаходиться їхній добуток

q₂ =β₀ * β_1. Якщо m > 1, то число значущих цифр у q₂ буде більше, ніж m. Тоді з усіх значущих цифр добутку q₂ вибирається m цифр, розташованих у середині числа q₂, і ці цифри використовують як випадкове β_2.Наступне випадкове число β₃ виходить аналогічно з добутку β₁ * β₂ і т.д.

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

5.8.4.2. Метод відрахувань

Застосування методу відрахувань засноване на тім, що кожне наступне випадкове число β_k+1 утвориться з попереднього β_k згідно рекурентному співвідношенню:

β_k+1 = λ*.β_k (mod N) (5.72)

яке означає, що число β_k+1 дорівнює залишку від розподілу на N числа β_k на постійний множник λ.

Очевидно, що залишок від розподілу на N у загальному випадку має ту

же розрядність, що і число N, тобто вибором числа N власне кажучи визначається розрядність одержуваних випадкових чисел.

З використанням цього алгоритму була, наприклад, знайдена

Залежність для одержання послідовності псевдовипадкових чисел d_k рівномірно розташованих на інтервалі [0;1]:

d_k+1 =5¹⁷ *.d_k (mod 2⁴²); d₀ = 1; (5.73)

β_k = 2^-42.d _k (5.74)

Рівняння (5.73) є записом алгоритму (5.72), а (5.74) застосовується для того, щоб привести випадкові числа до інтервалу [0;1].

Період послідовності, одержуваний по (5.73) приблизно дорівнює 10¹²

Інша послідовність псевдовипадковихчисел може бути отримана при використанні рекурентного співвідношення (5.72), якщо прийняти

λ= 5¹³; N = 2³⁶ (5.75)

Одержувана при цих значеннях послідовність має період, оцінюваний числом 22.10¹⁰.

З цих оцінок величини періоду випливає справедливість раніше

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

5.8.4.3. Одержання псевдовипадкових послідовностей з

ірраціональних чисел

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

Β_k = {K.Z} K=1; 2; 3;... (5.76)

Фігурні дужки в (5.76) означають, що з добутку K.Z береться тільки дробова частина, що повинна обчислюватися з необхідним ступенем точності, що характеризує розрядність що знаходяться псевдовипадкових чисел.

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

5.9. Порівняння різних методів рішення задач

оптимізації методами нелінійного програмування

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

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

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

б) Метод найшвидшого спуска удалині від крапки экстремума виявляється більш вигідним, чим метод градієнта.

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

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

Варто мати на увазі, що ці оцінки відносяться до тих випадкам,

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

ЛІТЕРАТУРА

1. Царьова З.М., Товажнянський Л,Л, Орлова Е.І. Основи теорії хімічних реакторів (комп’ютерний курс). - Харків: НТУ ХПІ, 2002. - 615 с.

2. Закгейм А.Ю. Введение в моделирование химико-технологических процессов. - М.: Химия, 1993. - 288 с.

3. Кафаров В.В., Глебов М.Б. Математическое моделирование основных процессов химических производств: Учеб. пособие для вузов. –М.: Высш. шк.,1991.–400 с.

4. Бояринов А.И., Кафаров В.В. Методы оптимизации в химической технологии - М.: Химия, 1992. – 576 с.

5. Смирнов Н.Н., Волжинский А.И., Плесовских В.А. Химические реакторі в примерах и задачах: Учеб. пособие для вузов. –СПб: Химия, 1994. – 280 с.

6. Бесков В.С., Сафронов В.С. Общая химическая технология и основы промышленной экологии: Учебник для вузов. – М.:Химия, 1999. – 472 с.

ЗМІСТ

..............................................................................................................................

Дата добавления: 2014-11-18