Page 174 - 5637

(тут – число поєднань з елементів по: = !/ ! ( − )!).

Процедура породження всіх рішень рівнянь (8.11) складається з наступних
операцій: вводиться сукупність − 1 індексів , … , , приймаючих значення із

сукупності {1, 2, … , + − 1} і задовольняють умові < <. . . < . Пересуваючи

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

послідовно отримуємо всі рішення рівняння (8.11). Кожне з рішень перетворюється на

точки околиці Хеммінга ( , ) за допомогою обертання в просторі щодо

початку координат і лінійним переносом.

Використовуючи властивості околиць (8.9), (8.10), можна скласти співвідношення

для розрахунку ( , ) – кількості елементів околиці Хеммінга ( , ) ( ∈ ,

≥ 0):

⎡ 2 ( , ) + 2 ( − 1, ) − 2 ( − 1) ( −
⎢
⎢

( , ) = ⎢
⎢ −2, ) + 2 ( − 2) ( − 3, ) + ⋯ + (−1) (0, ) , ≥ 2
⎢
⎢ 2 + 1, = 1,
⎣ 1, = 0

(8.13)

Перебір елементів околиці Хеммінга ( , ) проводиться шляхом послідовного

породження елементів поверхонь Хеммінга ( , ) = { : ( , ) = } ( = 1, … , ).

Метод вектора спаду ґрунтується на обчисленні координат вектора спаду ∆ ( ),
які дозволяють визначити напрямок, за яким значення функції ( ) в околиці ( , )

для кожної точки ∈ зменшуються. Різні форми вектора спаду наведено в [69].
Слід зазначити, що часто координати вектора спаду обчислюються простіше, ніж

значення функції (∙), а для локальної оптимізації можна обмежитися лише частиною

з усіх координат вектора ∆ ( ). Проте однією з основних і найбільш часто

зустрічаються при вирішенні практичних завдань форм вектора спаду є наступна:

∆ ( ) = ( ) − ( ), ⋳ , ⋳ ( , ). (8.14)

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

Будемо також вважати, що на задана метрика Хеммінга ( , ) = ∑ | − |,

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