5.2. Методи випадкового пошуку з навчанням

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

Маючи на увазі цю обставину, ітераційний процес (5.1) зручніше записати в вигляді

к = \,2,- (5.2)

тим самим підкреслюючи залежність випадкового вектора £ від

номеру ітерації к.

На початку пошуку закон розподілу випадкового вектора 4 = 4$

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

починають з випадкового вектора   £0 = (^,...,^), компоненти якого

с незалежними випадковими величинами, розподіленими рівномірно на відрізку [-1;1].

Для навчання алгоритму в процесі пошуку часто беруть сімейство випадкових векторів £ = %(о)), які залежать від параметрів

а) = (о}1,..,а)п) і при переході від к -ї ітерації до (к +1) -шої значення

параметрів сок замінюють новими значеннями з урахуванням

результатів попереднього пошуку.

Наведемо два варіанта методу випадкового пошуку з навчанням для безумовної мінімізації функції У(и) .

Алгоритм покоординатного навчання

Нехай маємо сімейство випадкових векторів % = %{<») = (£',...,£"), кожна координата яких приймає два значення: = 1 з вірогідністю р' і = -1 з вірогідністю 1 —р', де вірогідності р' залежать від параметра Ф1 наступним чиномр =

0, (0і <-\,

1, й>'>-1, <1,   і = 1.....п. (5.3)

Нехай початкове наближення н0 вже вибране. Тоді, для визначення наступного наближення и, в формулі (5.2) при к = 0 береться будь-яка реалізація випадкового вектора ^0 = ^(0), який відповідає значенню параметрів <о = (о^ = (0,0,...,0). Наближене значення щ визначається за формулою (5.2) при к = 1 за допомогою вектора  £=£(0). Нехай вже відомі наближення  и0,и1,...,иІ! і

значення параметрів щс_1=(а^_1,..,еок_1) при деякому к>0. Тоді покладемо

і = 1,2,.., в,  £ = 2,3,...

Де величина /? > 0 називається параметром спадання, £> > 0 -параметром інтенсивності навчання, /? + £ > 0. При визначенні наступного наближення иі+1в формулі (5.2) беремо будь-яку реалізацію випадкового вектора £,к = %(в}к), щ = .

З (5.3), (5.4) видно, що якщо перехід від точки ик_2 до привів  до  спадання  функції,  то  вірогідність  вибору напряму зменшення ик_1— щ_2 на наступному кроці збільшується. І навпаки,

якщо при переході від точки ик_2 до ик_1 значення функції збільшилось, то вірогідність вибору напряму Щ-і-Щ-2 на наступному кроці зменшується. Таким чином, формули (5.4) здійснюють навчання алгоритму. Величина 6 > 0 в (5.4) регулює швидкість навчання: чим більше <5>0, тим швидше навчається алгоритм; при 3 = 0 очевидно навчання відсутнє. Величина /ї £ 0 вформулах (5.4) регулює вплив попередніх значень параметра на навчання алгоритму; при  /? = 0   алгоритм «забуває» попереднє

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

цих обмежень вони замінюються найближчим з чисел с( або - с(, і = \,...,п. Величини /?,<5,с, являються параметрами алгоритму.

Замість формул     (5.4), за допомогою яких здійснюється навчання алгоритму, часто користуються іншими формулами

4=М-1-^^К-,)-^К-г))к-1-«и), (55)

/ = 1,2,..,и,  Аг = 2,3,...

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

проходять лише по одному з 2і" напрямів з  ^ = (^1,...,^я), де або

= 1  або      = — 1. Відсутність «проміжних» напрямків робить

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

Алгоритм безперервного навчання

Нехай маємо сімейство випадкових векторів £, = %(со) = -

де 0) = (в>1 ,..,<о")- параметри навчання, 7] = (ц1,..,7]я) - випадковий

вектор, координати якого Т]' є незалежними випадковими величинами, рівномірно розподілені на відрізку [-1;1]. Пошук починається з розгляду випадкових векторів ^ = ^(0) і ^=^(0),

реалізації яких використовуються при визначенні наближень и0, Ы,

за формулами (5.2). Навчання алгоритму при к > 2 здійснюється так, як і в алгоритмі покоординатного навчання, за допомогою формул (5.4) або    (5.5). При великих значеннях ІодІ  вплив випадковоївеличини щ зменшується, і напрям £h = £(фк) стає більш детермінованим і ближчим до напряму сок. Щоб уникнути такої детермінованості методу на параметри <ок = {(о\,..,(ОІ) накладаються обмеження \в)к\ <с = const, і коли вони порушуються сок замінюється Щ

на |—■ с .

N

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

Загальні зауваження

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

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

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

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

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

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