ошуку
Показано, що у разі великої розмірності дуже ефективні методи, які відносяться до групи методів випадкового пошуку.
Ідея методу випадкового пошуку дуже проста. З поточної точки робиться крок у випадковому напрямку (використовується датчик випадкових чисел). Якщо крок вдалий, то нова точка приймається за поточну точку, і 7-7 з неї робиться новий крок. Інакше робиться нова спроба. Пошук закінчують, коли з даній точці за обмежене число спроб не вдається знайти точку з кращим значенням критерію оптимальності. Модифікації методу визначаються визначенням величини кроку, вибором чергового напрямки при невдачі і т.д.
Метод особливо ефективний для яружних функцій, т.к. властивості функції не роблять істотного впливу на характер пошуку.
Оцінка алгоритму по точності пошуку проводиться шляхом обчислення вже відомих локальних характеристик e, d, g після виконання заданого числа ітерацій N. Вони відображають ступінь наближення до оптимуму, як за координатами, так і за критерієм оптимальності. Характеристика g використовується лише в спеціальних випадках: облік обмежень у неявній формі, пошук за допомогою градієнтних методів, методів змінної метрики і т.д.
Так як багато алгоритми включають в себе на кожній ітерації, як вибір напряму пошуку, так і одновимірний пошук по ви лайки напрямку, як збіжності часто використовується така характеристика, як число одновимірних пошуків, необхідних для досягнення оптимуму із заданою точністю. Ця характеристика дозволяє досліджувати ефективність вибору напрямку при багатопараметричної оптимізації. Вона визначає, наскільки часто проводиться оцінка напрямку пошуку. Якщо часто, то знижується ефективність не тільки за рахунок великого числа звернень до моделі. Природно, що такі алгоритми не варто включати в систему.
Оцінка алгоритму по швидкості збіжності в деякому сенсі обратна оцінці їх точності. При її обчисленні фіксується точність e або d і проводиться порівняння алгоритмів за кількістю пробних кроків N, необхідних для точності. Ця характеристика не залежить від швидкодії ЕОМ (а лише від довжини розрядної сітки), складності моделі проектованого об'єкта і тому є показником ефективності алгоритму. Вона залежить від точності на кожній з двох стадій пошуку. Завдання високої точності може збільшити істотно загальне число звернень до моделі (пробних обчислень) навіть у сл. досконалого способу вибору напрямку. Необгрунтоване ж зниження точності може порушувати теоретичне припущення, покладені в основу вибору напрямку (наприклад, умова ортогональності в методі сполучених градієнтів). В якості компромісних варіантів м. б. використаний критерій із заданим числом проб в одновимірному пошуку.
Порівняння алгоритмів за часом рахунку дозволяє оцінити вартість обчислень при виборі напрямків пошуку і порівняти його із загальним часом рахунку. Зазвичай застосовують відносні оцінки часу. Нехай n - загальне число завдань, які вирішуються програмою А, а ns - число завдань, для яких було отримано оптимальної рішення. Вводиться умовний коефіцієнт:
- відносний час.
3. Практика організації та проведення обчислювальних експериментів
Обчислювальний експеримент - метод вивчення пристроїв або фізичних процесів за допомогою математичного моделювання. Він припускає, що слідом за побудовою математичної моделі проводиться її чисельну дослідження, що...
