Студопедия
Контакти
 


Тлумачний словник

Реклама: Настойка восковой моли




Градієнтний метод із дробленням кроку

 

З умови ( 9.3 ) видно, що при виборі малого кроку - можна досить довго (велика кількість ітерації пройде) йти до мінімуму. Великий крок може порушити умову ( 9.5) (перескочити оптимум).

Через те в градієнтному методі із дробленням кроку зменшення кроку на кожній ітерації робиться таким, щоб виконувалась умова:

(9.6)

де: 0 < h < 1 - коефіцієнт збіжності методу, постійна константа для всіх ітерацій.

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

Пошук оптимуму виконується по наступному алгоритму.

- Вибираємо крок h > 0 для всіх ітерацій;

- На k-тій ітерації перевіряємо виконання умови 9.6.

- Якщо вона не виконується, то зменшуємо hk до тих пір поки умова 9.6 не виконається і, знайшовши hk = h h, переходимо до наступної ітерації. Якщо умова виконується, то з тим самим кроком переходимо до наступної ітерації.

На k-тій ітерації знаходимо вектор Xk і виконуємо такі дії:

- залишаємо значення кроку незмінним hk = h ;

- рахуємо норму вектора градієнта при постійному значенні коефіцієнта збіжності метода: ; (9.7)

- далі знаходимо наступну точку пошуку ;

- якщо різниця значень цільової функції у попередній і наступній точках менша заданої умови то йдемо далі. У іншому випадку зменшуємо крок hk = С hk на коефіцієнт зменшення кроку ( 0 < С < 1 ) і повертаємось на попередню операцію;

- запам’ятовуємо наступну точкуі переходимо до виконання нової k = k + 1 ітерації.

Іноді крок зміни параметрів оптимізації вибирають таким, щоб виконувалась простіша умова (9.5). Але такий вибір кроку не завжди забезпечує збіжність методу оптимізації.

На рис. 9.2 показана схема алгоритму описаного методу. В даній схемі спочатку вводиться початкова точка пошуку, вектор на n параметрів X0, по­чаткове значення кроку h > 0, коефіцієнт зменшення кроку С, ( 0 < С < 1 ), коефіцієнт збіжності методу h, ( 0 < h < 1 ), точність обчислень опти­мального значення цільової функції e > 0, максимально допустиме число ітерацій km > 1, підпрограми обчислення цільової функції F(X) і градієнту цільової функції G(X).



Интернет реклама УБС

Далі , блоки 2, 3, задаються початковим значенням лічильника циклів k і поточним значенням вектора параметрів оптимізації Х. В цій точці знаходиться значення цільової функції FX і вектор градієнту GR. З блоків 4, 5, 6 починається зовнішній цикл, де включається лічильник циклів, повторно запам’ятовується точка Х, як точка Y (наступна і попередня точки пошуку), обчислюється сума квадратів вектору градієнта S і знаходиться d.

В блоках 7 – 10 підбирається значення кроку h його зменшенням на коефіцієнт С до виконання умови блоку 9.

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

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

. (9.8)

У випадку, коли точність не досягнута, то в блоці 14 порівнюється кількість циклів пошуку k з максимально допустимою кількістю km і виконується перехід на нову ітерацію. У випадку перевищення заданого числа, виводиться повідомлення про неефективність методу. Блоками 16 і 17 виводяться результати пошуку оптимуму.

Слід зауважити, що Х, Y, GR є векторами на n значень. В операціях з ними при програмуванні алгоритму необхідно використовувати цикли.

 


Читайте також:

  1. D) методу мозкового штурму.
  2. H) інноваційний менеджмент – це сукупність організаційно-економічних методів управління всіма стадіями інноваційного процесу.
  3. I Метод Шеннона-Фано
  4. I. Метод рiвних вiдрiзкiв.
  5. VII. Нахождение общего решения методом характеристик
  6. А. науковий факт, b. гіпотеза, с. метод
  7. Автоматизація водорозподілу на відкритих зрошувальних системах. Методи керування водорозподілом. Вимірювання рівня води. Вимірювання витрати.
  8. Агрегативна стійкість, коагуляція суспензій. Методи отримання.
  9. АгротехнІЧНИЙ метод
  10. Адаптовані й специфічні методи дослідження у журналістикознавстві
  11. Адміністративні (прямі) методи регулювання.
  12. Адміністративні методи - це сукупність прийомів, впливів, заснованих на використанні об'єктивних організаційних відносин між людьми та загальноорганізаційних принципів управління.

Загрузка...



<== попередня сторінка | наступна сторінка ==>
Лекція №9. Градієнтнi методи | Градієнтний метод найшвидшого спуску

Не знайшли потрібну інформацію? Скористайтесь пошуком google:


 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.001 сек.