الگوریتم چکه‌آب‌های هوشمند: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
افزودن pseudo code |
|||
خط ۱:
'''الگوریتم چکه آب‌های هوشمند''' یا '''چکاه''' {{انگلیسی|Intelligent Water Drops}}، یک الگوریتم برای بهینه‌سازی [[هوش ازدحامی|هوش گروهی]] است.<ref name=shah-hosseini2009/> الگوریتم چکاه، الگوریتمی است که به گونه گروهی کار می‌کند و پرهام-گرا (طبیعت-گرا) می‌باشد. این الگوریتم در نهاد برای بهینه‌سازی آمیختاری (Combinatorial optimization) به کار برده می‌شود ولی میتوان آن را برای بهینه‌سازی پیوسته (Continuous optimization) نیز آماده ساخت. این الگوریتم نخستین بار در سال ۲۰۰۷ میلادی، برابر ۱۳۸۶ خورشیدی برای یافتن گشایش و راه حل برای [[مسئله فروشنده دوره‌گرد|مساله (پرسمان) فروشنده دوره‌گرد]] پیشنهاد شد.<ref name=shah-hosseini2007 /> از آن پس، شماری از پژوهشگران در پی بهبود و به کار بستن این الگوریتم برای مشکل‌ها و مساله‌های گوناگون بوده‌اند.
== آشنایی ==
کم و بیش، هر الگوریتم چکاه از دو پاره درست شده است: یک گرافی که نقش یک حافظه گسترده (distributed memory) را بازی می‌کند که بر روی آن خاک‌های لبه‌ها نگهداری می‌شود. پاره دیگر، که چندین چکه آب هوشمند (چکاه‌ها) هستند که روی لبه‌ها می شارند و از گره‌ای از گراف به گره‌ای دیگر می‌روند و با این کار خاک لبه‌های گذر کرده را دگرگون کرده و کمی به خاک در خود دارنده می‌افزایند. این چکاه‌ها با همکاری و همچنین رقیبگری کاری می‌کنند تا گشایش‌های بهتری بیابند. این کار با دگرگونی خاک‌های روی گراف به گونه‌ای پیش می‌رود که گشایش‌های بهتر دسترس پذیرتر شوند. می دانیم که الگوریتم چکاه دست کم نیاز به دو چکاه دارد تا بتواند کار کند.
==دون-شناسه (pseudo-code)==
الگوریتم IWD دارای دو گونه پارامتر هست: پارامترهای ایستا (static) و پویا (dynamic). پارامترهای ایستا در هنگام پردازش الگوریتم IWD، پایا (constant) هستند. پارامترهای پویا پس از هر دگرار (iteration، تکرار) الگوریتم، بازآغازدهی میشوند. میتوان دون-شناسه (pseudo-code) یک الگوریتم چکاه-پایه را در هشت گام زیر بیان کرد:
:'''1)''' آغازدهی پارامترهای ایستا
:: الف. ''بازنمایی پرسمان در یک گراف''
:: ب. ''ارزش نهادن برای پارامترهای ایستا''
:'''2)''' آغازدهی پارامترهای پویا: تندی و خاک چکاه ها
:'''3)''' پخش چکاه ها روی گراف پرسمان
:'''4)''' ساخت گشایش با چکاه ها به همراه به روزکرد تندی و خاک
:: الف. ''به روزکرد خاک برزنی''
:: ب. ''به روزکرد تندی و خاک روی چکاه ها''
:'''5)''' جستجوی برزنی روی هر گشایش چکاه (این گام دلخواه هست)
: '''6)''' به روزکرد خاک سرتاسری
: '''7)''' به روزکرد گشایش آزگار-بهترین (total-best)
: '''8)''' به گام 2 بروید مگر آنکه شرط پایاندهی، خشنود بشود
== کاربردها ==
| |||