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

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

Основна ідея цього методу полягає в наступному. За допомогою генератора випадкових чисел одержують деяку реалізацію випадкового   вектора    £    і   визначають   точку    vk = щ + сс£,

a = const>0. Якщо vkeU і J(yk)<J(uk), то зроблений крок

вважається вдалим і в цьому випадку покладаємо ui+1 = vt. Якщо

vk є U, a J(vk) > J(uk), або ж vt g U, то зроблений крок вважається

невдалим, і покладаємо иі+1 = ик.

Якщо ж виявиться, що  ик = uktl =... = uh+/j  для достатньо

великих N, то точка ик може бути прийнятою в якості наближення

точки мінімуму функції J(u) .

Алгоритм найкращої спроби

Тут беруться будь-які s реалізацій вектора ,.■■>£* випадкового вектора ^ і обчислюються значення функції J(u) в тих точках

и = ик+а£', i=l,...,s, які належать множині U.   Затим покладаємо

ut+1 = ик + а%'", де індекс if, визначається з умови:

J(ик + а%к ) = min J(ик + а% ).

Величини s > 0 і се = const > 0 являються параметрами алгоритму.

Алгоритм статистичного градієнта

Беруться будь-які s реалізацій вектора випадкового вектора £, і обчислюються різниці ДУЙ = J(uk +        J(uk) для всіхик + у%' є 17. Затим покладаємо рк= — У\  ДЛ,, де сума береться

у і

по тим індексам / , для яких ик + у%' є ІЗ. Якщо ик + урк є ІЗ, то

приймаємо = ик + арк . В протилежному випадку повторюємо описаний процес з новим набором з в реалізацій випадкового вектора £. Величини 5>0, се > 0, у>0 - являються параметрами алгоритм.

Вектор рк називають статистичним градієнтом. Якщо С/ = Еп, $ = п і

вектори <*:1,...,<*:і не с випадковими і співпадають з відповідними

одиничними векторами є' =(0,...,0,1Д...,0), / = 1,2,..., п, то описаний алгоритм перетворюється в різницевий аналог градієнтного методу.

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

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