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

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

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

آشنایی

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

شبه-کد (pseudo-code)

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

۱) مقداردهی اولیه‌ی پارامترهای ایستا

الف. بازنشانی مسئله در قالب یک گراف
ب. مقدار‌دهی برای پارامترهای ایستا
۲) مقداردهی اولیه‌ی پارامترهای پویا: سرعت و خاک چکاه‌ها
۳) پخش کردن چکاه ها روی گراف مسئله
۴) ساخت راه‌حل با چکاه‌ها به همراه به روزکردن سرعت و خاک

الف. به‌روزرسانی محلی خاک در گراف
ب. به‌روزرسانی سرعت و خاک روی چکاه‌ها
۵) جستجوی محلی روی هر راه‌حل چکاه(این گام دلخواه هست)
۶) به‌روزکردن خاک سراسری
۷) به‌روزکردن بهترین راه‌حل کلی
۸) به گام ۲ برو تا زمانی‌که شرط خاتمه ارضا شود

کاربردها

برخی از کاربردهایی که با الگوریتم‌های چکه-پایه پیاده‌سازی شده‌اند در زیر آورده شده‌اند:

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

منبع


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

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

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

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

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

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

soil(i,j) = (1+ρIWD).soil(i,j) – ρIWD .soilIBIWD/(NIB-1)    (i,j) ϵ TIB

که در آن ρIWD پارامتر به روزرسانی سراسری، NIB تعداد نودهای بهترین مسیر در تکرار جاری و soilIBIWD قطره ای است که بهترین مسیر را پیموده است. 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 عبارت است:

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

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

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

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

۵- مراحل زیر یعنی ۵-۱ تا ۵-۴ را برای همه IWDها با راه حل های جزئی تکرار می شود.

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

فرمول 6

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

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

فرمول 8

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

فرمول 9

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

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

فرمول 10

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

فرمول 11

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

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

فرمول 12

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

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

فرمول 13

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

فرمول 14

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

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

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


منابع

۱٫https://fa.wikipedia.org

۲٫http://fumblog.um.ac.ir

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *