Крок 4. Словесний опис евристичного алгоритму

Крок 1.

Словесний опис евристичного алгоритму

Задаються

х ₀,

e ₁, e ₃,

d ₁, d ₂,

a ₁ — постійний крок пункту 1,

a ₂ — постійний крок пункту 2 (a ₁< a ₂).

Привласнюється к =0.

Крок 2. (Перший етап).

Із точки х_к здійснюється спуск на «дно яру» з постійним кроком a ₁. При спуску обчислення чергової точки здійснюється з використанням формул:

, де ,

Нехай цей процес зупиниться в точці x_l.

Крок 3. (Другий етап).

Із точки x_l здійснюється спуск уздовж «дна яру» з постійним кроком a ₂. При спуску використовуються формули: x_{j +1}= x_j – a ₂ g (x_j), де

,

Нехай цей процес зупинився в точці x_m.

Якщо і , то приймаємо:

і пошук мінімуму закінчується.

Інакше k = m і переходимо до кроку 2.

Рис. 6.

Схема евристичного алгоритму

1.5.3. Яружні методи (Метод Гельфанда)

Ідея методу Гельфанда

Друга евристична схема, запропонована И.М. Гельфандом, полягає в наступному.

Нехай х ₀ і — дві довільні близькі точки. З х ₀ роблять звичайний градієнтний спуск із постійним кроком і після декількох ітерацій з малим кроком a потрапимо в точку u ₀. Аналогічно робимо для точки , одержуючи точку . Дві точки u, лежать в околиці «дна яру». З'єднуючи їх прямою, робимо «великий крок» l в отриманому напрямку, переміщаючись «уздовж дна яру» (крок l називають яружним кроком). У результаті одержуємо точку х ₁. У її околиці вибираємо точку й повторюємо процедуру.

	х0

Рис. 6.

Схема алгоритму яружного методу 1

Дата добавления: 2015-05-23