Page 175 - 5637

допустимою, тобто належала безлічі (про пошук таких допустимих початкових

наближень див. нижче, §8.4).

Таким чином, алгоритм методу вектора спаду складається з наступних основних

етапів:

1. Задаємо деяке початкове наближення ∈ , а також і – мінімальний

і максимальний радіуси околиці Хеммінга локальної мінімізації.

2. Вважаємо = 0, = .

3. На ( + 1)-му кроці виконуємо наступні дії:

3.1. Виробляємо перебір всіх -елементів в околиці Хеммінга ( , ).

3.2. Знаходимо ∈ ∈ ∩ ( , )/{ }, таке, що ( ) = min ∈ ( ).

3.3. Якщо безліч пусто або якщо − ( ) ≤ 0 (тобто якщо даний

компонент вектора спаду негативний), переходимо до п. 4, в іншому випадку, якщо

< , значення радіуса замінюється на + 1 і переходимо до п.3.1, в іншому

випадку до п.5.

4. Замінюємо на + 1, задаємо = , = і переходимо до П.З.

5. Значення оголошуємо локальним (по відношенню до околиці Хеммінга

( , − 1)) мінімумом функцій .

При переході до перебору елементів (п.3) округа Хеммінга ( , ) з >

досить розглядати точки, що належать безлічі ( , )/ ( , − 1), тобто поверхні

Хеммінга ( , ).

Алгоритм, що реалізує метод вектора спаду, сходиться до точного рішення задачі
цілочисельного програмування при досить широких припущеннях про структуру

оптимізується цільової функції. Зокрема, збіжність алгоритму (при відповідному

виборі радіуса ) має місце при остаточному безлічі визначення цільових функцій.

Якщо вирішується оптимізаційна задача з функцією, не задовольняє отриманим

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

критерієм може бути кількість кроків пошуку або тривалість його за часом, а також

оцінка min ( ), отримана за допомогою алгоритму статистичної оцінки
∈

екстремальних значень (див. §8.6).

Результати машинного експерименту [69] щодо вирішення завдань

цілочисельного програмування показали високу ефективність застосування методу