На головну

АЛГОРИТМ Хука - Дживса

  1. I-й алгоритм покаяння
  2. I. Програмування лінійних алгоритмів.
  3. II. Програмування розгалужених алгоритмів.
  4. III. Програмування циклічних алгоритмів.
  5. RADIX ?дісімен с?риптау алгорітмі.
  6. алгоритм
  7. алгоритм

ПРЯМІ МЕТОДИ БЕЗУМОВНОГО МІНІМІЗАЦІЇ

Цей алгоритм містить дві основні процедури:

а) досліджує покоординатно пошук в околиці даної точки, призначений для визначення напрямку убування f (х);

б) переміщення в напрямку зменшення.

Наведемо алгоритм досліджує покоордінатного пошуку з заданої точки х з приростами по кожній координаті Dj , j = 1, ..., n

Крок 1. покласти  = X, i = 1.

Крок 2. Зробити пробний крок y =  - Dje j, Де e j -j-й базисний вектор. якщо f (  ) ? f (Y), то перейти до кроку 3, інакше - до кроку 4.

Крок 3. Зробити пробний крок y =  + Dje j . якщо f (  ) ? f (Y), то перейти до кроку 5, інакше - до кроку 4.

Крок 4. покласти  = У.

Крок 5. покласти j = j + 1. Якщо j ? n, То перейти до кроку 2. В іншому випадку досліджує пошук закінчено - отримана точка  для котрої f (  ) < f (Y), якщо  ? х.

Зауваження. В результаті досліджує пошуку може виявитися, що  = Х. Тоді досліджує пошук вважається невдалим. Якщо при цьому норма збільшення D = (D1, .., Dn ) Мала, т. Е. || D || ? e, де e - задана точність, то вважають х *  = Х. Якщо задана точність не досягнута, то вважають D = D / g (постійна g >1 - коефіцієнт зменшення кроку) і повторюють досліджує пошук.

Наведемо тепер повний алгоритм Хука - Дживса.

Крок 0. Вибрати початкову точку х0 , Вектор збільшень D = (D1, .., Dn ), Коефіцієнт зменшення кроку g >1, параметр закінчення пошуку e> 0.

Крок 1. Провести досліджує покоординатно пошук з точки х0, Т. Е. Знайти точку  . якщо  ? х, то перейти до кроку 3, інакше - до кроку 2.

Крок 2. Перевірка на закінчення пошуку. Якщо || D || * = х0. Інакше - покласти D = D / g і перейти до кроку 1.

Крок 3. Переміщення з точки х в напрямку зменшення  - х0 : Покласти х1 =  + (  - х0) = 2  - х0 .

Крок 4. Провести досліджує пошук в точці х1 , Т. Е. Знайти точку  . Якщо f (  ) 0 = , =  і перейти до кроку 3. Інакше - покласти х0 =  і перейти до кроку 1.

Приклад 3.7. Розглянемо графічну ілюстрацію рішення задачі f (х) = (x1+ 1)2+х22 ®min методом Хука - Дживса з початкової точки х0 = (2,3), вектор переміщень D = (1 / 2,1).

Цільова функція f (х) являє собою квадрат відстані між точками х і х *  = (- 1,0). Лінії рівня f (х) - це кола з центром в точці х * . Тому значення f (х) в проміжних точках алгоритму легко порівнювати, оцінюючи їх відстані від точки х *  на рис. 3.9. На малюнку пунктиром виділені траєкторії досліджує пошуку, суцільними лініями - переміщення в напрямку зменшення. Переконайтеся у відповідності графічної ілюстрації описаного алгоритму.

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

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

Мал. 3.9. Приміром 3.7.

 



| Некомерційне акціонерне товариство
© um.co.ua - учбові матеріали та реферати