ناب لرنینگ |
بزرگترین بانک اطلاعاتی پروژه های دانشجویی الگوریتم چکه آب های هوشمند یا چکاه ، یک الگوریتم بهینه‌سازی بر پایه هوش گروهی است. الگوریتم چکه، الگوریتمی است که به گونه گروهی کار می‌کند و الهام گرفته از طبیعت است. این الگوریتم در اصل برای بهینه‌سازی ترکیبیاتی (Combinatorial optimization) به کار برده می‌شود ولی می‌توان آن را برای بهینه‌سازی پیوسته (Continuous optimization) نیز آماده ساخت. این الگوریتم نخستین بار در سال ۲۰۰۷ میلادی، برابر ۱۳۸۶ خورشیدی برای یافتن گشایش و راه حل برای مسأله فروشنده دوره‌گرد پیشنهاد شد. از آن پس، شماری از پژوهشگران در پی بهبود و به کار بستن این الگوریتم برای مشکل‌ها و مسئله‌های گوناگون بوده‌اند.
قطره‌های آب موجود در رودخانه‌ها می توانند به طور هوشمندانه کوتاه‌ترین مسیر را در رسیدن به دریا پیدا کنند. الگوریتم قطره های هوشمند آب در سال ۲۰۰۷ بر اساس این رفتار ارائه شد. در این الگوریتم قطره های آب دارای دو ویژگی مهم سرعت و میزان خاکی هستند که از زمین دریافت کرده‌اند و با خود جابه‌جا می کنند. هرچه میزان خاک آن‌ها کمتر باشد سرعت آن‌ها می‌تواند بیشتر شود. میزان خاک در واقع اطلاعاتی است که بین زمین و قطره‌های آب مبادله می‌شود. چون هرچه تعداد قطره های بیشتری از یک زمین عبور کرده باشند میزان خاک آن کمتر است یک قطره مسیری را ترجیح می دهد که خاک کمتری داشته باشد. اگر گام‌های حرکت قطره‌ها به صورت گسسته باشد می‌توان فرض کرد قطره روی نودهای یک گراف در حال حرکت است. عملکرد الگوریتم که در آن قطره‌های آب نماینده پاسخ‌های مساله هستند و به صورت رندم بر هریک از نودهای گراف مقداردهی می‌شوند به این صورت است که در تعدادی تکرار برای هر قطره مراحل زیر انجام می شود :
۱- به ازای هر نود بعدی آن نود با احتمال P طوری انتخاب می شود که قبلا مشاهده نشده باشد و ضمنا شروط مساله را نیز نقض نکند. P متناسب با معکوس میزان خاک بین دو نود مربوطه است.
۲- سرعت قطره به روزرسانی می شود به طوری‌که هرچه خاک بیشتری بین دو نود وجود داشته باشد مقدار کمتری به سرعت آن افزوده می‌شود.
۳- میزان خاکی که قطره از مسیر جمع‌آوری می‌کند متناسب با مقدار هیوریستیک مساله و همچنین معکوس سرعت ذره محاسبه می‌گردد. (∆soil(i,j))
۴- میزان خاک موجود بین دو نود و خاکی که توسط قطره حمل می‌شود توسط ∆soil(i,j) به روزرسانی می‌شود.
در پایان هر تکرار بهترین مسیر پیموده شده توسط همه قطره ها از نظر کارایی پیدا شده و خاک موجود در مسیرهای آن با توجه به میزان مطلوبیت این مسیر به روز رسانی می شود. در این به روزرسانی ضمن کم شدن میزان خاک مسیر با توجه به خاک حمل شده توسط قطره و تعداد نودها مقداری به آن اضاف هم می شود تا شانس جست و جوی مسیرهای دیگر در تکرارهای بعدی از بین نرود.رابطه به روزرسانی بهترین مسیر در تکرار جاری به صورت زیر است:
که در آن ρIWD پارامتر به روزرسانی سراسری، NIB تعداد نودهای بهترین مسیر در تکرار جاری و soilIBIWD قطره ای است که بهترین مسیر را پیموده است. soil(i,j) میزان خاک بین دو نود در بهترین مسیر جاری است.
