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

قطره‌های آب موجود در رودخانه‌ها می توانند به طور هوشمندانه کوتاه‌ترین مسیر را در رسیدن به دریا پیدا کنند. الگوریتم قطره های هوشمند آب در سال 2007 بر اساس این رفتار ارائه شد. در این الگوریتم قطره های آب دارای دو ویژگی مهم سرعت و میزان خاکی هستند که از زمین دریافت کرده‌اند و با خود جابه‌جا می کنند. هرچه میزان خاک آن‌ها کمتر باشد سرعت آن‌ها می‌تواند بیشتر شود. میزان خاک در واقع اطلاعاتی است که بین زمین و قطره‌های آب مبادله می‌شود. چون هرچه تعداد قطره های بیشتری از یک زمین عبور کرده باشند میزان خاک آن کمتر است یک قطره مسیری را ترجیح می دهد که خاک کمتری داشته باشد. اگر گام‌های حرکت قطره‌ها به صورت گسسته باشد می‌توان فرض کرد قطره روی نودهای یک گراف در حال حرکت است. عملکرد الگوریتم که در آن قطره‌های آب نماینده پاسخ‌های مساله هستند و به صورت رندم بر هریک از نودهای گراف مقداردهی می‌شوند به این صورت است که در تعدادی تکرار برای هر قطره مراحل زیر انجام می شود :

1) به ازای هر نود بعدی آن نود با احتمال P طوری انتخاب می شود که قبلا مشاهده نشده باشد و ضمنا شروط مساله را نیز نقض نکند. P متناسب با معکوس میزان خاک بین دو نود مربوطه است.

2) سرعت قطره به روزرسانی می شود به طوری‌که هرچه خاک بیشتری بین دو نود وجود داشته باشد مقدار کمتری به سرعت آن افزوده می‌شود.

3) میزان  خاکی که قطره از مسیر جمع‌آوری می‌کند متناسب با مقدار هیوریستیک مساله و همچنین معکوس سرعت ذره محاسبه می‌گردد. (∆soil(i,j))

4) میزان خاک موجود بین دو نود و خاکی که توسط قطره حمل می‌شود  توسط ∆soil(i,j) به روزرسانی می‌شود.

در پایان هر تکرار بهترین مسیر پیموده شده توسط همه قطره ها از نظر کارایی پیدا شده و خاک موجود در مسیرهای آن با توجه به میزان مطلوبیت این مسیر به روز رسانی می شود. در این به روزرسانی ضمن کم شدن میزان خاک مسیر با توجه به خاک حمل شده توسط قطره و تعداد نودها مقداری به آن اضاف هم می شود تا شانس جست و جوی مسیرهای دیگر در تکرارهای بعدی از بین نرود.رابطه به روزرسانی بهترین مسیر در تکرار جاری به صورت زیر است:

soil(i,j) = (1+ρ_IWD).soil(i,j) – ρ_IWD .soil_IB^IWD/(N_IB-1)    (i,j) ϵ T^IB

که در آن ρ_IWD پارامتر به روزرسانی سراسری، N_IB تعداد نودهای بهترین مسیر در تکرار جاری و soil_IB^IWD قطره ای است که بهترین مسیر را پیموده است. soil(i,j) میزان خاک بین دو نود در بهترین مسیر جاری است.

همچنین بهترین مسیر سراسری با توجه به بهترین مسیر در تکرار جاری امکان دارد تغییر کند.

منبع

اصول iwd

الگوریتم مبتنی بر ذرات است. سوال اصلی چگونه پیچ و تابهای رودخانه ایجاد شده است. می خواهیم از این مکانیزم هوش طبیعی استفاده کنیم. Iwd با دو ویژگی مهم شناخته می شود:

1. سرعت(velocity)
2. شن(soil)

هر دو خاصیت بالا در طول عمر یک IWD بارها تغییر می کند. یک IWd از یک منبع به یک مقصد جریان می یابد. IWD سفر خود را با یک سرعت اولیه و Soil صفر آغاز می کند.در دوران سفر به سرعت خود می افزاید.

از موقعیت جاری IWD تا موقعیت بعدی سرعتش با مقدار متنایب غیر خطی تا معکوس Soilهای بین دو محل افزایش می یابد.

نابراین یک مسیر با شن کمتر iwd را با سرعت بیشتری از مسیر خاکی تر پیش می برد .مقدار شن اضافه شده به IWD خاصیت غیر خطی به معکوس زمان لازم برای iwd برای عبور از محل جاری به محل بعدی است. این بازه زمانی با قواعد ساده فیزیک برای حرکت خطی محاسبه می گردد .بنابراین زمان سپری شده متناسب با سرعت iwd و به طور معکوس با فاصله بین دو محل در نظر گرفته می شود.پس محل دارای iwd بیشتر شن کمتر دارد. پس در مورد شن حافظه دارند .یک iwd در مورد انتخاب مسیر محل بعدی یا مرحله بعدی به مکانیزم انتخاب نیاز دارد .که در این مکانیزم محل با شن کمتر ترجیح داده می شود .این رفتار انتخاب مسیر، بوسیله تحمیل یک توزیع تصادفی یکنواخت روی شنهای موجود در مسیر ، پیاده سازی می شود. پس رودخانه بهترین مسیر از بین مسیرهای ممکن از مبدأ به مقصد است .این مسیر بهینه یا نزدیک به بهینه از تراکنش قطرات آب باهم و با بستر رودخانه ایجاد می گردد.

الگوریتم IWD

الگوریتم با نمایش گرافی (N,E) است. با نودهای N و یالهای E است. پس هر IWD شروع به ساختن راه حل تدریجی بوسیله گردش در راسهای گراف در طول یالها می کند. و تا آنجا که راه حلش را کامل کند ادامه می دهد .یک تکرار الگوریتم با کامل شدن همه IWDها راه حلها تمام می شود .بعد از هر تکرار، راه حل بهترین تکرار که  نامیده می شود، یافت می شود که برای بروز رسانی بهترین راه حل کلی  به کار می رود .مقدار خاک در روی لبه های راه حل بهترین تکرار  بر مبنای کیفیت راه حل کاهش می یابد. سپس الگوریتم با تکرار دیگر با IWDهای جدید شروع می شود .ولی با خاکهای همانند روی مسیرهای گراف و همه فرآیندها تکرار می شود .الگوریتم وقتی به ماکزیمم تکرار iter(max) می رسد و یا به کیفیت مورد نظر رسید، پایان می یابد. الگوریتم IWD دو نوع پارامتر دارد. یکی در طول عمر الگوریتم ثابت و استاتیک است. دیگری در هر تکرار الگوریتم دوباره شروع می شود و پویا است.

مراحل الگوریتم IWD عبارت است:

1- مقدار دهی اولیه پارامترهای ثابت .گراف (N,E) مساله به الگوریتم داده می شود. کیفیت راه حل کلی بهتر یعنی  در ابتدا به بدترین تنطیم می شود.   Iter(max) بوسیله کاربر تعیین می شود .که مقدارش ابتدا به صفر مقداردهی اولیه می شود. مقدار قطرات آب  یک مقدار مثبت صحیح می گیرد که معمولا تعداد نودها  گراف است .برای بروز رسانی سرعت پارامترها cv=1 و bv=0.01 و av=1 . برای بروز رسانی پارامتر شن  cs=1 و bs=0.01 و as=1 و  پارامتر بروزرسانی شن محلی است که یک عدد مثبت کوچک کمتر از یک است که  می گیرند .پارامترهای بروز رسانی شن کلی  است .که در بازه [0,1] انتخاب می شود مثل 0.9 . همچنین مقداردهی اولیه خاک در مسیر (لبه-یال )با ثابت InitSoil مشخص میشود. مانند خاک مسیر بین هر دو نود i,j که با  initsoil=soil(i,j) سرعت اولیه هر IWD با initvel مشخص می شود. هر دو پارامتر مذکور به انتخاب کاربر و تجربی بسته به کاربرد است مثلاً ما initsoil=10000 و initvel=200 می گیریم.

2- مقداردهی اولیه پارامترهای پویا. هر IWD یک لیست نودهای ملاقات شده Vc(IWD) که ابتدا تهی است. همه IWDها به مقدار شن اولیه صفر تنطیم شده اند.

3- IWDها را به طور تصادفی در رئوس گراف به عنوان اولین نود ملاقات شده پخش می کنیم.

4- بروزرسانی لیست ملاقات شده هر IWD برای شامل کردن نودهای ملاقات شده

5- مراحل زیر یعنی 5-1 تا 5-4 را برای همه IWDها با راه حل های جزئی تکرار می شود.

   1-5- برای هر IWD مقیم در نود i، نود بعدی j  را انتخاب می کنیم. به طوری که محدودیت های پر شده را نقض نکند و در لیست نودهای ملاقات شده Vc(IWD) نباشد. با احتمال زیر :

سپس نود j تازه ملاقات شده به لیست Vc(IWD) اضافه می شود.

    2-5- برای هر IWD در حال حرکت از i به j سرعتش با فرمول زیر بروزرسانی می شود.

    3-5- برای هر حرکت IWD روی مسیر از i به j شن از فرمول زیر بارگذاری می شود.

که میزان نامطلوبیت اکتشافی با تقریب مناسب برای مسأله تعیین می شود.

بروزرسانی شن در مسیر از i به j پیمایش شده و شن حمل شده بوسیله IWD با فرمول زیر:

6- پیدا کردن بهترین راه حل تکرار جاری در بین همه راه حل های بوسیله بقیه IWDها با فرمول زیر:

که تابع q کیفیت مسیر را نشان می دهد.

7- بروزرسانی شن ها در مسیرهایی که از راه حل بهتر تکرار جاری حاصل می شود.

که N تعداد نودها در راه حل بهینه محلی کنونی است.

8- بروزرسانی راه حل کلی بهتر بوسیله بهترین راه حل کنونی با استفاده از فرمول زیر:

9- افزایش مقدار شمارنده:

10- توقف الگوریتم با مقدار بهترین راه حل کلی 

این نشاندهنده این است که IWDها همگرایی دارند. یعنی قدرت همگرایی برای یافتن بهینه در مسائل با تکرار بسیار بالا دارد .مانند الگوریتم مورچه که فرومون بخار می شود اینجا نیز شنها در مسیر حرکتی پاک می شوند .ولی برخلاف فرمون اینجا مقدار شن ثابت نیست و به سرعت و مقدار شن موجود در مسیر بستگی دارد .همچینین سرعت IWD به الگوریتم بستگی دارد ولی در مورچه وابسته به الگوریتم نیست.

منابع

1.https://fa.wikipedia.org

2.http://fumblog.um.ac.ir