الگوریتم چکه‌آب‌های هوشمند

الگوریتم چکه آب‌های هوشمند یا چکاه ، یک الگوریتم بهینه‌سازی بر پایه هوش گروهی است. الگوریتم چکاه، الگوریتمی است که به گونه گروهی کار می‌کند و الهام گرفته از طبیعت است. این الگوریتم در اصل برای بهینه‌سازی ترکیبیاتی (Combinatorial optimization) به کار برده می‌شود ولی می‌توان آن را برای بهینه‌سازی پیوسته (Continuous optimization) نیز آماده ساخت. این الگوریتم نخستین بار در سال ۲۰۰۷ میلادی، برابر ۱۳۸۶ خورشیدی برای یافتن گشایش و راه حل برای مسأله فروشنده دوره‌گرد پیشنهاد شد. از آن پس، شماری از پژوهشگران در پی بهبود و به کار بستن این الگوریتم برای مشکل‌ها و مسئله‌های گوناگون بوده‌اند.

آشنایی 
کم و بیش، هر الگوریتم چکاه از دو بخش درست شده است: یک گرافی که نقش یک حافظه گسترده (distributed memory) را بازی می‌کند که بر روی آن خاک‌های لبه‌ها نگهداری می‌شود. بخش دیگر، که چندین چکه آب هوشمند (چکاه‌ها) هستند که روی لبه‌ها جاری شده و از گره‌ای از گراف به گره‌ای دیگر می‌روند و با این کار خاک لبه‌های گذر کرده را دگرگون کرده و کمی به خاک در خود دارنده می‌افزایند. این چکاه‌ها با همکاری و همچنین رقیبگری کاری می‌کنند تا گشایش‌های بهتری بیابند. این کار با دگرگونی خاک‌های روی گراف به گونه‌ای پیش می‌رود که گشایش‌های بهتر دسترس پذیرتر شوند. می دانیم که الگوریتم چکاه دست کم نیاز به دو چکاه دارد تا بتواند کار کند.

شبه-کد (pseudo-code) 
الگوریتم IWD دارای دو گونه پارامتر هست: پارامترهای ایستا (static) و پویا (dynamic). پارامترهای ایستا در هنگام پردازش الگوریتم IWD، پایا (constant) هستند. پارامترهای پویا پس از هر بار تکرار  الگوریتم، مقداردهی اولیه می‌شوند. میتوان شبه-کد یک الگوریتم چکاه-پایه را در هشت گام زیر بیان کرد:

1) مقداردهی اولیه‌ی پارامترهای ایستا
 الف. بازنشانی مسئله در قالب یک گراف
 ب. مقدار‌دهی برای پارامترهای ایستا 
2) مقداردهی اولیه‌ی پارامترهای پویا: سرعت و خاک چکاه‌ها
3) پخش کردن چکاه ها روی گراف مسئله
4) ساخت راه‌حل با چکاه‌ها به همراه به روزکردن سرعت و خاک
 الف. به‌روزرسانی محلی خاک در گراف
 ب. به‌روزرسانی سرعت و خاک روی چکاه‌ها
5) جستجوی محلی روی هر راه‌حل چکاه(این گام دلخواه هست) 
 6) به‌روزکردن خاک سراسری
 7) به‌روزکردن  بهترین راه‌حل کلی
 8) به گام ۲ برو تا زمانی‌که شرط خاتمه ارضا شود

کاربردها 
برخی از کاربردهایی که با الگوریتم‌های چکاه-پایه پیاده‌سازی شده‌اند در زیر آورده شده‌اند:
   مسئله کوله‌پشتی چند بعدی
 برنامه‌ریزی گذرگاه ربات هوایی
   مشکل راه یابی رسانگر
 الگوریتم راهیابیMANET
 گسیل بار اقتصادی
   مسئله فروشنده دوره‌گرد
   مسئله مسیریابی وسایل نقلیه
 سرگزینی ویژگی بافت
 آستانه گیری خودکار چندتراز با یک سنجش بهبودیافته اتسو
 بهینه‌سازی پیوسته
 زمان‌ریزی فروشگاه کار
 مسئله درخت اشتاینر
  مشکل بیشینه همپالگان
 درخت گردآوری داده بهینه در شبکه‌های حسگر بی سیم
 زادگری داده آزمون بر پابه کاوش گذرگاه آزمون
 پوشش کد و شناسه
 بهینه کرد مدلهای فرایند زاد و کار
 بهینه سازی پیمان نامه راهیابی
 سرگزینی ویژگی بافه خشن
 برنامه‌ریزی تولید و زمانبندی 
 زنجیره تأمین و مدیریت موجودیها

جستارهای وابسته 
 هوش گروهی
 هوش راینشی

منابع

پیوند به بیرون 
  شناسه چشمه (source code) برای الگوریتم چکاه فروشنده دوره گرد با زبان #C
  دیمه‌ای برای نظرجویی همگانی

الگوریتم‌های بهینه‌سازی
روش‌های بهینه‌سازی
سامانه‌های چندعامله
هوش جمعی
هوش مصنوعی