Локальний пошук (оптимізація)

Лока́льний по́шук — пошук, що здійснюється алгоритмами локального пошуку, групою алгоритмів, у яких пошук ведеться тільки на підставі поточного стану, а раніше пройдені стани не враховуються й не запам'ятовуються.

Основною метою пошуку є не знаходження оптимального шляху до цільової точки, а оптимізація деякої цільової функції, тому задачі, розв'язувані подібними алгоритмами, називають задачами оптимізації. Для опису простору станів у таких задачах використовують ландшафт простору станів, у цьому представленні задача зводиться до пошуку стану глобального максимуму (або мінімуму) на даному ландшафті.

Історія розробки локального пошуку

Ідеї локального пошуку при розв’язанні задач комбінаторної оптимізації є найбільш природними і наочними. Перші кроки з їх реалізації належать до кінця 50-х років XX століття. У СРСР першопрохідцями цього напряму були Ю.І. Журавльов, який запропонував алгебраїчну теорію локальних алгоритмів, і Л.А. Растригін, який досліджував ймовірнісні алгоритми локального пошуку. На Заході перші дослідження пов'язані переважно з задачею комівояжера. Пізніше ці ідеї використовувалися для задач розміщення, побудови мереж, розкладів та інших. Проте доволі швидко виявилося, що локальний пошук не гарантує знаходження глобального оптимуму задачі. Локальні алгоритми стали використовувати переважно в гібридних схемах, схемах декомпозиції і для отримання наближених рішень у складних дискретних задачах. Досліджувалися можливості побудови найкращої послідовності локальних алгоритмів, методи випадкового пошуку з локальної оптимізації і керованого випадкового пошуку. Тим не менше, відсутність концептуального прогресу послабило інтерес до даного напряму.

У останні 15-20 років спостерігається відродження цього підходу. Воно пов'язане як з новими алгоритмічними схемами, побудованими на аналогіях з живою і неживою природою, так і з новими теоретичними результатами в області локального пошуку. Змінився загальний погляд на побудову локальних алгоритмів. Вимога монотонного поліпшення цільової функції більше не є домінуючим. Найбільш потужні імовірнісні алгоритми допускають довільне її погіршення, і багато з них можуть розглядатися як спосіб породження кінцевих нерозкладних ланцюгів Маркова на відповідній множині станів. Поява мета евристик, таких як генетичних алгоритмів, локального пошуку з заборонами, імітації відпалу та інших, відкрило широкий простір для вирішення прикладних задач дослідження операцій. [3]

Алгоритми ітеративного покращення

• Алгоритм сходження на вершину
• Алгоритм імітації відпалу
• Генетичні алгоритми
• Табу-пошук
• Алгоритм променевого пошуку

Методи локального пошуку

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

Прямі методи

Методи нульового порядку (прямі методи) в своїй основі не мають визначеного математичного обґрунтування і будуються на основі слушних пропозицій та емпіричних даних. Найпростішим методом нульового порядку є метод покоординатного спуску (Гауса–Зейделя). На кожному кроці фіксуються всі змінні, крім однієї, за котрою визначається мінімум цільової функції. Послідовним перебором змінних досягається оптимізація. Цей алгоритм виявляється неефективним, якщо цільова функція містить вирази типу $x_{1}x_{2}$. Для задач технічного проектування, в котрих не вдається отримати аналитичного виразу цільової функції, характерна її складна залежність від компонентів схеми, і тому цей метод звичайно не застосовується. З методів нульового порядку у випадку ярних цільових функцій хороші результати дає метод Розенброка, в якому об'єднані ідеї покоординатного спуску та ідеї перетворення координат. Найкращим напрямом пошуку екстремуму є рух вздовж яру. Тому після першого циклу покоординатного спуску здійснюється поворот осей координат так, щоб одна з них збіглася з напрямом яру $X_{k}-X_{k}-n,k=n,2n,3n,\ldots$. Метод Розенброка не дає інформації про потрапляння у точку мінімуму. Тому рахунок зупиняється або після того, як зменшення F(X) стане менше деякого малого числа $\varepsilon$, або після певної кількості циклів.

Метод Гука — Дживса було розроблено у 1961 році, але він досі є доволі ефективним та оригінальним. Пошук мінімуму цільової функції складається з послідовності кроків досліджуючого пошуку навкруги базисної точки, за котрою у випадку успіху слідує пошук за зразком. Ця процедура складається з наступних кроків:

1. Обрати початкову базисну точку b1 і крок довжиною hj для кожної змінної xj, j=1,2,…,n скалярної цільової функції F(X).

2. Вирахувати F(X) у базисній точці b1 з метою отримання відомостей про локальну поведінку функції F(X). Ці відомості будуть використовуватися для знаходження напряму пошуку за зразком, за допомогою якого можна сподіватися досягнути більшого спадання значення функції F(X). Значення функції F(X) у базисній точці b1 знаходиться наступним чином: a) вираховується значення функції F(b1) у базисній точці b1;

б) кожна змінна по черзі змінюється зміною кроку. Таким чином, вираховується значення F(b1 he1), де e1- одиничний вектор у напрямі осі x1. Якщо це призводить до зменшення значень функції, то b1 замінюється на b1 he1. В іншому випадку вираховується значення функції F(b1 — he1), і якщо її значення зменшилось, то b1 замінюється на b1 — he1. Якщо ні один зі зроблених кроків не призводить до зменшення значень функції, то точка b1 залишається незмінною і розглядають зміни у напрямі осі x2, тобто знаходиться значення функції F(b1 h2e2) і. т. д. Коли будуть розглянуті всі n змінні, визначається нова базисна точка b2;

в) якщо b2 = b1 , тобто зменшення функції F(X) не було досягнуто, то дослідження продовжується навколо тієї ж базисної точки b1 , але зменшеною довжиною кроку. Як правило, на практиці крок зменшують у 10 разів від початкової довжини;

г) якщо b2 > b1 , то здійснюється пошук за зразком.

3. При пошуку використовується інформація, отримана в процесі дослідження, і мінімізація цільової функції завершується пошуком у напрямку, заданому зразком. Ця процедура здійснюється наступним чином: а) рух здійснюється з базисної точки b2 у напрямку b2 — b1 , оскільки пошук в цьому напрямку вже призвів до зменшення значення функції F(X). Тому вираховується значення функції в точці зразку P1 = b2 (b2 — b1).

В загальному випадку

Pi = 2bi 1 — bi;

б) здійснюється дослідження навколо точки P1(Pi);

в) якщо найменше значення на кроці 3,б менше значення у базисній точці b2 (у загальному випадку bi 1), то отримують нову базисну точку b3(bi 2), після чого повторюється крок 3,а. В іншому випадку не відбувається пошук за зразком з точки b2 (bi 1).

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

Градієнтні методи оптимізації першого порядку

Методи відшукування екстремуму, які використовують похідні, мають строге математичне обґрунтування. Відомо, що при відшукуванні екстремуму не існує кращого напряму, ніж рух по градієнту. З градієнтних методів одним з найбільш ефективних є метод Флетчера–Пауелла (сполучених градієнтів), які є різновидністю методу найшвидшого спуску.

Метод найшвидшого спуску складається з наступних етапів:

1) задається початкова точка (вектор Xk k=0);

2) вираховуються F(Xk) и F(Xk);

3) здійснюється зміна X у напрямку Sk = -F(Xk) до тих пір, поки F(X) перестане спадати;

4) покладається k = k 1, вираховується нове значення F(Xk) і процес повторюється з 3–го етапу.

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

Суть методу Флетчера–Пауелла полягає в тому, що при всіх ітераціях, починаючи з другої (на першій ітерації методи Флетчера–Пауелла і найшвидшого спуску є однаковими), використовуються попередні значення F(X) та F(X) для визначення нового вектора напряму. Тим самим виключається зигзагоподібний характер спуску і прискорюється збіжність. Цей алгоритм простий для програмування, і при цьому вимагається помірний об’єм машинної пам’яті (необхідно заповнити тільки попередній напрям пошуку і попередній градієнт).[1]

Застосування локального пошуку

Області застосування

• Пошук локального мінімуму з заданої точки з урахуванням обмежень;

• Ефективне уточнення наближених оцінок глобально-оптимального рішення;

• Стеження за дрейфом локально-оптимального рішення при зміні параметрів;

• Швидке попереднє дослідження структури розв'язуваної багатовимірної задачі;

• Наближене розв’язання задач високої розмірності (у поєднанні з простими методами покриттів

області пошуку). [4]

Обчислення складності локального пошуку

Аналіз обчислювальної складності локального пошуку в останні роки інтенсивно ведеться в двох напрямах: емпіричному та теоретичному. Ці напрями дають істотно різні оцінки можливостям локального пошуку.

• Емпіричні результати

Для багатьох NP-складних задач локальний пошук дозволяє знаходити наближені рішення, близькі до глобального оптимуму по цільовій функції. Трудомісткість алгоритмів часто виявляється поліномінальною, причому ступінь полінома досить мала. Для задач комівояжера алгоритми локального пошуку є високо ефективними з практичної точки зору. Один з таких алгоритмів з околицею Ліна-Керніган для класичної задачі комівояжера має похибку в середньому біля 2% і максимальна розмірність вирішуваних завдань досягає 1 000 000 міст. На випадково згенерованих завданнях такої колосальної розмірності ітераційної процедури Джонсона дозволяє знаходити рішення з відхиленням близько 0,5% на сучасних комп'ютерах за кілька хвилин.

Для задач теорії розкладів, розміщення, покриття, розфарбування та багатьох інших NP-складних задач алгоритми локального пошуку показують гарні результати. Їх гнучкість при зміні математичної моделі, простота реалізації і наочність перетворюють локальний пошук в могутній інструмент для розв’язання NP-складних задач.

• Теоретичні результати

Дослідження локального пошуку з точки зору гарантованих оцінок якості показують межі його можливостей. Побудовані важкі для локального пошуку приклади, яких випливає, що:

1. мінімальна точна околиця може мати експоненційну потужність;
2. число кроків для досягнення локального оптимуму може виявитися експоненціальним;
3. значення локального оптимуму може як завгодно сильно відрізнятися від глобального оптимуму;
4. мінімальна відстань між локальний оптимум може бути як завгодно великим.[3]
   

Застосування локального пошуку для розв'язання задач

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

Алгоритми локального спуску широко застосовуються для вирішення NP-важких задач дискретної оптимізації. Багато поліноміальних розв'язні завдання можуть розглядатися як завдання, легко розв'язувані таким способом. При відповідному виборі полиноміальної околиці відповідна теорема може бути сформульована в наступному вигляді: допустиме рішення не є глобальним оптимумом, якщо і тільки якщо може бути покращено деяким локальним чином.

• Лінійне програмування. Геометрично симплекс метод можна інтерпретувати як рух по вершинах багатогранника допустимої області. Вершина не є оптимальною, якщо і тільки існує суміжна з нею вершина з меншим значенням цільової функції. Алгебраїчно, в припущенні не виродженого завдання базисне допустиме рішення не є оптимальним, якщо і тільки якщо воно може бути покращено локальним зміною базису, тобто заміною однієї базисної змінної на небазисну. Отримана таким чином околиця є точною і має поліноміальну потужність.

• Мінімальне остовне дерево. Остовне дерево не є оптимальним, якщо і тільки якщо локальною перебудовою, додаючи одне ребро і видаляючи з циклу утворилося інше ребро, можна отримати нове остовне дерево з меншою сумарною вагою. Операція локальної перебудови задає відношення сусідства на безлічі основних дерев. Околиця будь-якого дерева має поліноміальну потужність, а сама околиця є точною.

• Максимальне паросполучення. Паросполучення не є максимальним, якщо і тільки якщо існує збільшуваний шлях. Два паросполучення називають сусідніми, якщо їх симетрична різниця утворює шлях. Визначена таким чином околиця є точною і має поліноміальну потужність. Аналогічні твердження справедливі для зважених паросполучень, здійснених паросполученнями мінімальної ваги та завдань про максимальний потік.[3]

Застосування локального пошуку для розв'язування таких задач:

- задача про вершинне покриття,в якому рішення є вершиною графа, а метою є знаходження розв’язку з мінімальною кількістю вузлів;

- задача комівояжера, в якій рішенням є цикл, що містить всі вузли графа, і метою є мінімізації загальної довжини циклу;

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

- задача на планування роботи медсестер, у якій рішення є завдання медсестер працювати зі змінами, що задовольнить усі встановлені обмеження. [5]

Література

1. Кийков В.В., Кочкина В.Ф., Вдовкин К.А. Параметрическая оптимизация радиоэлектрических схем. Екатеринбург, 2005. 21 стр.: [1]

2. Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации: [2] [Архівовано 13 лютого 2016 у Wayback Machine.]

3. Кочетов Ю.А. Методы локального поиска для дискретних задач размещения. Новосибирск, 2009. 261 стр.:[3] [Архівовано 11 вересня 2011 у Wayback Machine.]

4. Методи та системи штучного інтелекту. Тама 4. Локальний пошук [4]^{[недоступне посилання з липня 2019]}

5. Vijay Arya and Naveen Garg and Rohit Khandekar and Adam Meyerson and Kamesh Munagala and Vinayaka Pandit, (2004): Local Search Heuristics for k-Median and Facility Location Problems [Архівовано 27 липня 2013 у Wayback Machine.], Siam Journal of Computing 33(3).