Алгоритм інтелектуальних крапель

Алгори́тм інтелектуа́льних кра́пель (англ. IWD) — алгоритм рою (колективного інтелекту) на основі алгоритму оптимізації, який використовує методи природних річок і способи, якими вони знаходять майже оптимальні шляхи до місця призначення. Він знаходить оптимальні, або близькі до оптимальних шляхи, які випливають з реакції, що протікають між краплями води, коли вода тече руслом річки. В IWD алгоритмі, кілька штучних крапель води, що залежать одна від одної здатні змінювати своє оточення таким чином, що знаходять оптимальний шлях по шляху найменшого опору. IWD алгоритм це конструктивний популяційно-орієнтований алгоритм оптимізації.

Застосування

Цей алгоритм можна використовувати в задачах:

• Комівояжера
• Багатовимірні задачі про ранці (MKP)
• Автомобіль маршрутизації
• Задача про вісім ферзів

Історія

Алгоритм був вперше винайдений (Шах-Хоссейні, 2007), та використовувався для вирішення завдання комівояжера (TSP). Потім його було використано стосовно багатовимірної задачі про ранці (MKP) (Шах-Хоссейн, 2008a), та задачі про Н ферзів (Шах-Хоссейн, 2008b), і планування шляху робота (Дуань та співавт., 2008).

Суть алгоритму

Природна поведінка крапель води

У природі краплі води спостерігаються в основному в річках, де вони утворюють величезні маси (рої крапель води). Шляхи, якими течуть природні ріки були створені роями з крапель води. Для рою крапель води, річки, в яких вони протікають є частиною навколишнього середовища, яке було значно змінене роєм, а також буде змінено в майбутньому. Більш того, саме середовище має суттєвий вплив на шлях слідування крапель води. Їм чинять опір берега річки. Наприклад, проти рою крапель води, ті частини навколишнього середовища, з яких складається жорсткий ґрунт, чинять опір більше, ніж частини з м'якого ґрунту. Насправді, природне русло річки є результатом конкуренції між краплями води, та навколишнього середовища, який чинить опір руху крапель води. Більшість русел річок мають багато несподіваних поворотів. Хоча краплі води і не мають очей, вони завжди можуть знайти своє призначення, якими часто є озеро або море. Якщо поставити себе на місце води, що тече в річці, ми відчуємо, що якась сила тягне нас до себе. Це сила тяжіння, яка тягне всі предмети ближче до центру землі. Таким чином, без перешкод і бар'єрів, краплі води повинні слідувати прямим шляхом до пункту призначення, який є найкоротшим шляхом від джерела води до цілі, який в ідеалі мав би знаходитися в центрі Землі.

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

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

Три очевидних зміни відбудеться протягом цього перехідного періоду:

• Швидкість краплі води збільшується.
• Насиченість ґрунтом краплі води збільшується.
• Між цими двома точками, кількість ґрунту в руслі зменшується.

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

• Крапля води з високою швидкістю збирає більше ґрунту, чим повільніша крапля води.

Таким чином, краплі води з великою швидкістю видаляють більше ґрунту з дна річки, ніж інші краплі води з меншою швидкістю. Вилучення ґрунту, таким чином, пов'язана з швидкістю краплі води.

• Швидкість краплі води зростає на шляху з низьким рівнем ґрунту більше, ніж на шляху з високим рівнем ґрунту.

Таким чином, шлях з невеликою кількістю ґрунту дозволяє поточній краплі води зібрати більше ґрунту і отримати більшу швидкість в той час як шлях з великими рівнями ґрунту пручається більше. Ще одна властивість природних крапель води, — вона часто вибирає легший шлях. Отже:

• Крапля води віддає перевагу шляху з меншою кількістю ґрунту, ніж шляху з більшою кількістю ґрунту
• Крапля води віддає перевагу більш легкому шляху, коли доводиться вибирати між кількома маршрутами, які існують на шляху від джерела до місця призначення.
• Легкість або Твердість шляху визначається кількістю ґрунту на цьому шляху. Шлях з більшим рівнем ґрунту

вважається важким шляхом, тоді як шлях з меншим рівнем ґрунту вважається легкий шляхом.

Словесний опис середовища алгоритму

Алгоритм інтелектуального руху крапель води, формується так:
Кожна крапля води (IWD) володіє двома важливими властивостями:

• ґрунт що в ній знаходиться, позначають рівнем ґрунту (МЗ).
• Швидкість, що вона володіє, позначається швидкістю (МЗ).

Для кожного IWD, значення і властивості ґрунту (МЗ) і швидкості (МЗ) може змінитися іншими IWD в його оточенні. З інженерної точки зору, середовище являє собою проблему, яка бажає бути вирішена. Річка з потоком (роєм) IWDs шукає оптимальний шлях для даної проблеми.

Кожен IWD передбачається рух від джерела до місця призначення. В навколишньому середовища, існує безліч шляхів від даного джерела до місця призначення. Місця призначення можуть бути невідомі. Якщо місцезнаходження шуканого призначення відомо, що вирішення проблеми необхідно знайти найкращі (часто найкоротші) шляхи кожної краплі від джерела до місця призначення.

Виконання алгоритму

IWD алгоритм використовує ряд IWDs, щоб знайти оптимальне рішення даної проблеми. Проблема являє собою граф (N, E) з набором вузлів N і безліччю ребер E. Цей граф є середовищем для IWDs і їх потоку по ребрах графа.

Кожен IWD починає будівництво свого рішення поступово, подорожуючи між вузлами графу поки, нарешті, завершує IWD її рішення Одна ітерація IWD алгоритму завершується, коли всі IWDs завершити їх прохід по ребрах графа. Після кожної ітерації, знаходиться найкраще рішення Т. T- це найкраще рішення на основі функції якості серед усіх рішень, отриманих IWDs в поточній ітерації. T використовується для виконання наступних ітерацій. Найкраще рішення Т — це найкраще рішення з початку роботу IWD алгоритму, яке було знайдено у всіх ітераціях.

Застосування

IWD алгоритм здатен до рішення 4х задач: TSP (Задача комівояжера), задача Н ферзів, MKP (багатовимірна задача про ранці), та AMT (автоматичний багаторівневий поріг). Експерименти показують, що IWD алгоритм здатний знайти оптимальне або близьке до оптимального рішення. Тим не менш, є місце для внесення змін в стандарт IWD алгоритму для вкладення інших механізмів, які існують в природних річках, винаходячи найкращу евристику, яка найкраще вписується в дану проблему, IWD алгоритм показує, що природа є прекрасним керівництвом для розробки та винаходів нового стилю алгоритмів оптимізації.

Посилання

• Інтелектуальний алгоритм Краплі води (Хамед Шах-Хоссейні) [Архівовано 2 грудня 2013 у Wayback Machine.]