Алгори́тм гравітаці́йного по́шуку (англ. Gravitational Search Algorithm, GSA) — алгоритм пошуку, що базується на основі закону всесвітнього тяжіння і поняття масової взаємодії. Алгоритм ґрунтується на гравітаційних теоріях з фізики Ньютона і як пошукові агенти використовує гравітаційні маси.
За останні роки були розроблені різні евристичні методи оптимізації. Багато з цих методів базуються на аналогічних явищах у природі. Якщо порівнювати алгоритм гравітаційного пошуку з іншими алгоритмами, то даний метод є одним з найефективніших у розв'язуванні різноманітних задач оптимізації нелінійних функцій.
При розв'язуванні задач оптимізації з високою розмірністю простору пошуку, класичні алгоритми оптимізації не надають необхідне рішення, так як простір пошуку експоненціально зростає із складністю проблеми, тому розв'язок цих проблем з використанням точних методів (наприклад, перебору) на практиці досить обмежене або інколи навіть неможливе.
Протягом останніх десятиліть спостерігається зростаючий інтерес до алгоритмів, які ґрунтуються на особливостях поведінки природних явищ. І ці алгоритми добре підходить для вирішення складних обчислювальних проблем, таких як оптимізація цільових функцій, розпізнавання образів, організація управління, обробка зображення, моделювання тощо. Тим не менше, немає конкретного алгоритму для досягнення найкращого розв'язку для всіх задач оптимізації. Деякі алгоритми дають краще рішення для деяких конкретних проблем, ніж інші. Таким чином, пошук нових евристичних алгоритмів оптимізації є відкритою проблемою.
У даній статті представлений новий алгоритм оптимізації на основі закону всесвітнього тяжіння, а саме Алгоритм Гравітаційного Пошуку (англ. Gravitational Search Algorithm). Цей алгоритм заснований на законі гравітації Ньютона: «Кожна частка у Всесвіті притягує кожну іншу частку з силою, прямо пропорційною добутку їх мас і обернено пропорційною квадрату відстані між ними».
Слово «евристичний» з грецької означає «знати», «щоб знайти», «відкрити для себе». Евристичні алгоритми імітують фізичні або біологічні процеси. Найвідоміші алгоритми:
Всі вищезазначені евристичні алгоритми мають стохастичну поведінку. Тим не менш, був запропонований детермінований алгоритм евристичного пошуку на основі законів гравітаційної кінематики, що називається «Центральна оптимізація сил». У деяких стохастичних алгоритмах пошук починається з однієї точки і продовжується в послідовному порядку, однак, у більшості евристичних алгоритмах виконується паралельний пошук з кількома початковими точками.
Можна виділити два аспекти евристичних алгоритмів на основі популяції: розвідка і використання. Розвідка полягає в можливості розширення простору пошуку, щоб знайти нові рішення. Щоб мати високу ефективність пошуку, потрібно знаходити компроміс між розвідкою та використанням. Для того, щоб уникнути попадання в локальний оптимум, алгоритм повинен використовувати результати розвідки протягом перших декількох ітерацій. Такі евристичні алгоритми використовують розвідку і використання, але вони використовують різні підходи. Іншими словами, всі пошукові алгоритми схожі. Використовуючи ці алгоритми пошуку можна отримати гарні результати, але немає евристичного алгоритму, який може забезпечити вищу продуктивність, у порівнянні з іншими, і забезпечити вирішення всіх проблем оптимізації.
Гравітація або тяжіння — властивість тіл із масою притягатись одне до одного. Гравітаційна взаємодія найслабша із фундаментальних взаємодій, однак її характерною особливістю є те, що тіла, які мають масу, завжди притягаються одне до одного. Притягання дуже великих мас в астрономічних масштабах створює значні сили, завдяки яким світ є таким, яким людина його знає.
Ньютонів закон всесвітнього тяжіння стверджує:
Коефіцієнт пропорційності називається гравітаційною сталою. Її величина
У теоретичній фізиці розрізняють три види мас:
У запропонованому алгоритмі, агенти розглядаються як об'єкти, і їх ефективність вимірюється їх масою. Всі ці об'єкти притягує один до одного сила тяжіння, і ця сила викликає глобальний рух усіх об'єктів до об'єктів з більшими масами. Таким чином, маси об'єктів наче співпрацюють, використовуючи гравітаційну силу як форму спілкування.
Важкі маси — відповідають гарним рішенням, вони рухаються повільніше, ніж інші, і це гарантує наявність пошукового кроку алгоритму. В Алгоритмі Гравітаційного пошуку, кожна маса (агент) має чотири характеристики:
Положення маси відповідає рішенню завдання, а гравітаційна та інерційна маси визначаються за допомогою оцінки-придатності.
Іншими словами, кожна маса — це рішення, і алгоритм вибирає напрямок пошуку рішення шляхом правильного налаштування гравітаційної і інерційної мас. З плином часу очікується, що буде знайдена найважча маса. Ця маса представить оптимальне рішення в просторі пошуку.
Алгоритм Гравітаційного пошуку можна розглядати як ізольовану систему мас. Це як маленький штучний світ мас, що підкоряється Закону Гравітації і Руху.
Точніше, маси повинні дотримуватися таких законів:
Тепер, розглянемо систему з N агентами (N мас). Визначимо положення i-го агента: X i = ( x i 1 , . . . , x i d , . . . , x i n ) , i = 1 , 2... , N , {\displaystyle X_{i}=(x_{i}^{1},...,x_{i}^{d},...,x_{i}^{n}),i=1,2...,N,\,} де x i d {\displaystyle x_{i}^{d}\,} представляє позицію i-го агента в d-й вимір.
У певний час t, ми визначимо силу, що діє на масу i від J маси так: F i j d ( t ) = G ( t ) M p i ( t ) × M a j ( t ) R i j ( t ) + ϵ ( x j d ( t ) − x i d ( t ) ) , {\displaystyle F_{ij}^{d}(t)=G(t){\frac {M_{pi}(t)\times M_{aj}(t)}{R_{ij}(t)+\epsilon }}(x_{j}^{d}(t)-x_{i}^{d}(t)),\,} (1)
де M a j {\displaystyle M_{aj}} — активна гравітаційна маса, пов'язана з агентом j, M p i {\displaystyle M_{pi}} — пасивна гравітаційна маса, пов'язана з агентом i, G ( t ) {\displaystyle G(t)} — гравітаційна стала в момент часу t, R i j ( t ) {\displaystyle R_{ij}(t)} — евклідова відстань між двома агентами i і j:
R i j ( t ) =∥ X i ( t ) , X j ( t ) ∥ 2 {\displaystyle R_{ij}(t)=\parallel X_{i}(t),X_{j}(t)\parallel _{2}\,}
Щоб увести стохастичну характеристику в алгоритм, ми припускаємо, що загальна сила, що діє на агент i з боку агента j — це випадково зважена сума d-x компонент сил, що діють з боку інших агентів:
F i d ( t ) = ∑ j = 1 , j ≠ i N r a n d j F i j d ( t ) , {\displaystyle F_{i}^{d}(t)=\sum _{j=1,j\neq i}^{N}{rand_{j}F_{ij}^{d}(t)},\,}
де randj це випадкове число в інтервалі [0, 1].
Отже, за законом руху, прискорення агента i в час t, та в напрямку a i d ( t ) {\displaystyle a_{i}^{d}(t)} , задається так:
a i d ( t ) = F i d ( t ) M i i ( t ) , {\displaystyle a_{i}^{d}(t)={\frac {F_{i}^{d}(t)}{M_{ii}(t)}},\,} де Mii — маса i-го агента.
Крім того, наступна швидкість агента розглядається як сума поточної швидкості та прискорення. Тобто, положення і швидкість агента можна розрахувати так:
v i d ( t + 1 ) = r a n d i × v i d ( t ) + a i d ( t ) , {\displaystyle v_{i}^{d}(t+1)=rand_{i}\times v_{i}^{d}(t)+a_{i}^{d}(t),\,}
x i d ( t + 1 ) = x i d ( t ) + v i d ( t + 1 ) , {\displaystyle x_{i}^{d}(t+1)=x_{i}^{d}(t)+v_{i}^{d}(t+1),\,}
де randj це випадкове однорідне число в інтервалі [0, 1]. Ми використовуємо це випадкове число, щоб надати випадковості характеристикам пошуку.
Гравітаційна стала G, ініціалізується на початку і буде знижена з плином часу для того, щоб контролювати точність пошуку. Іншими словами, G є функцією від початкового значення (G0) і часу (t):
G ( t ) = G ( G 0 , t ) . {\displaystyle G(t)=G(G_{0},t).\,}
Гравітаційна і інерційна маси просто обчислюється за оцінкою-придатності. Найважча маса означає, що агент ефективніший. Це означає, що кращі агенти мають більше тяжіння і рухаються повільно. Якщо припустити рівність гравітаційної та інерційної мас, то значення мас розраховуються з використанням карти придатності. Ми змінюємо гравітаційну і інерційну маси за наступними рівняннями:
M a i = M p i = M i i = M i , i = 1 , 2 , . . . , N , {\displaystyle M_{ai}=M_{pi}=M_{ii}=M_{i},i=1,2,...,N,\,} m i ( t ) = f i t i ( t ) − w o r s t ( t ) b e s t ( t ) − w o r s t ( t ) , {\displaystyle m_{i}(t)={\frac {fit_{i}(t)-worst(t)}{best(t)-worst(t)}},\,} M i ( t ) = m i ( t ) ∑ j = 1 N m j ( t ) , {\displaystyle M_{i}(t)={\frac {m_{i}(t)}{\sum _{j=1}^{N}{m_{j}(t)}}},\,}
де f i t i ( t ) {\displaystyle fit_{i}(t)\,} — представляють значення оцінки-придатності агента i в час t, а worst(t) та best(t) визначаються так (для задачі мінімізації):
b e s t ( t ) = min j ϵ [ 1 , . . . , N ] f i t j ( t ) , {\displaystyle best(t)=\min _{j\epsilon [1,...,N]}{fit_{j}(t)},\,} (2) w o r s t ( t ) = max j ϵ [ 1 , . . . , N ] f i t j ( t ) , {\displaystyle worst(t)=\max _{j\epsilon [1,...,N]}{fit_{j}(t)},\,} (3)
Слід зазначити, що для задачі максимізації, рівняння (2) і (3) замінюються рівняннями (4) і (5), відповідно:
b e s t ( t ) = max j ϵ [ 1 , . . . , N ] f i t j ( t ) , {\displaystyle best(t)=\max _{j\epsilon [1,...,N]}{fit_{j}(t)},\,} (4) w o r s t ( t ) = min j ϵ [ 1 , . . . , N ] f i t j ( t ) , {\displaystyle worst(t)=\min _{j\epsilon [1,...,N]}{fit_{j}(t)},\,} (5)
Один із способів хорошого компромісу між розвідкою і використанням є зниження числа агентів з використанням скінченного часу. Таким чином, пропонуємо розглядати тільки набір агентів з більшою масою та як вони впливають на інші. Тим не менш, треба буди обережним у використанні цієї стратегії, оскільки це може зменшити потужність розвідки та збільшити здібність використання.
Нагадаємо, що для того, щоб уникнути попадання в локальний оптимум алгоритм повинен використовувати розвідку на початку. За хибної ітерації, розвідка повинна зникати, а використання повинні поступово посилюватися. При підвищенні продуктивність алгоритму гравітаційного пошуку, за рахунок управління розвідкою і використанням тільки Kbest агенти будуть притягати інших. Kbest є функцією від часу, з початковим значенням K0 на початку і зменшується з часом. Отже, на початку, всі агенти застосовують силу (впливають на інші тіла однаково), і з плином часу, Kbest зменшується лінійно, а в кінці буде тільки один агент, що впливає найбільше на інших. Таким чином, рівняння (1) може бути змінене так:
F i d ( t ) = ∑ j ϵ K b e s t , j ≠ i r a n d j F i j d ( t ) , {\displaystyle F_{i}^{d}(t)=\sum _{j\epsilon Kbest,j\neq i}{rand_{j}F_{ij}^{d}(t)},\,} (6) де Kbest — перші K агентів з найкращим співвідношенням оцінки-придатності і найбільшої маси.
Отже, можна виділити наступні етапи запропонованого алгоритму:
Щоб побачити, наскільки запропонований алгоритм є ефективним, слід розглянути наступні зауваження:
Порівняння з методом рою часток (Particle swarm optimization, PSO)
В основі методу — моделювання соціальної поведінки (зграї птахів). Цей оптимізаційний підхід змінює популяцію частинок (особин) шляхом застосування оператора відповідно до доречної інформації, отриманої з середовища. В результаті цього можна очікувати, що особина популяції буде рухатися в бік найкращого рішення. В методі рою часток x i d {\displaystyle x_{i}^{d}} та v i d {\displaystyle v_{i}^{d}} обчислюються так:
v i d ( t + 1 ) = w ( t ) v i d ( t ) + c 1 r i 1 ( p b e s t i d − x i d ( t ) ) + c 2 r i 2 ( g b e s t d − x i d ( t ) ) , {\displaystyle v_{i}^{d}(t+1)=w(t)v_{i}^{d}(t)+c_{1}r_{i1}(pbest_{i}^{d}-x_{i}^{d}(t))+c_{2}r_{i2}(gbest^{d}-x_{i}^{d}(t)),\,} (7)
де ri1 та ri2 — дві випадкові величини в інтервалі [0,1], c1 та c2 — додатні константи, w — інерції. X i = ( x i 1 , x i 2 , . . . , x i n ) {\displaystyle X_{i}=(x_{i}^{1},x_{i}^{2},...,x_{i}^{n})\,} та V i = ( v i 1 , v i 2 , . . . , v i n ) {\displaystyle V_{i}=(v_{i}^{1},v_{i}^{2},...,v_{i}^{n})\,} представляють положення та швидкість й частки, відповідно. p b e s t i = ( p b e s t i 1 , p b e s t i 2 , . . . , p b e s t i n ) {\displaystyle pbest_{i}=(pbest_{i}^{1},pbest_{i}^{2},...,pbest_{i}^{n})\,} та g b e s t = ( g b e s t 1 , g b e s t 2 , . . . , g b e s t n ) {\displaystyle gbest=(gbest^{1},gbest^{2},...,gbest^{n})\,} представляють найкраще попереднє положення і-ї частки і її найкраще попереднє положення серед усіх частинок в популяції, відповідно.
З рівняння (7), отримуємо, що кожна частка намагається змінити своє положення (Хі) використовуючи відстань між поточною позицією і pbesti, а також відстань між поточною позицією і gbest.
В обох алгоритмах оптимізація виконується за рахунок руху агентів в просторі пошуку, проте стратегії руху різні. Деякі важливі відмінності полягають в наступному:
Хоча алгоритм гравітаційного пошуку ще досить новий у порівнянні з іншими методами, його вже використовують для вирішення багатьох прикладних задач. Зокрема алгоритм можна використовувати в таких задачах: