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

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

آشنایی

ویرایش

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

شبه-کد (pseudo-code)

ویرایش

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

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

کاربردها

ویرایش

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

جستارهای وابسته

ویرایش

منابع

ویرایش
  1. Shah-Hosseini, H. (2009). "The intelligent water drops algorithm: a nature-inspired swarm-based optimization algorithm". International Journal of Bio-Inspired Computation. ۱ (۱/۲): ۷۱–۷۹.
  2. Shah-Hosseini, H. (2007). "Problem solving by intelligent water drops". Proceedings of the IEEE Congress on Evolutionary Computation: ۳۲۲۶–۳۲۳۱.
  3. Shah-Hosseini, H. (2008). "Intelligent water drops algorithm: a new optimization method for solving the multiple knapsack problem". Int. Journal of Intelligent Computing and Cybernetics. ۱ (۲): ۱۹۳–۲۱۲.
  4. Duan; et al. (2009). "Novel intelligent water drops optimization approach to single UCAV smooth path planning". Aerospace Science and Technology. ۱۳ (۸): ۴۴۲–۴۴۹. {{cite journal}}: Explicit use of et al. in: |author= (help)
  5. Kamkar; et al. (2010). "Intelligent water drops a new optimization algorithm for solving the Vehicle Routing Problem". IEEE International Conference on Systems, Man and Cybernetics: ۴۱۴۲–۴۱۴۶. {{cite journal}}: Explicit use of et al. in: |author= (help)
  6. Fan; et al. (2010). "The Intelligent-Water-Drop Based Routing algorithm for MANET". Int. Conf. on Future Information Technology: ۲۵۳–۲۵۵. {{cite journal}}: Explicit use of et al. in: |author= (help)
  7. Rayapudi, S. R. (2011). "An intelligent water drop algorithm for economic load dispatch". International Journal of Electrical and Electronics Engineering. ۵ (۱): ۴۳–۴۹.
  8. Msallam; et al. (2011). "Improved intelligent water drops algorithm using adaptive schema". International Journal of Bio-Inspired Computation. ۳ (۲): ۱۰۳–۱۱۱. {{cite journal}}: Explicit use of et al. in: |author= (help)
  9. Teymourian, E., Kayvanfar, V., Komaki, GH.M., Mostafa, M (۲۰/3/۲۰۱۶). "Enhanced intelligent water drops and cuckoo search algorithms for solving the capacitated vehicle routing problem". Information Sciences (به انگلیسی). Elsevier. {{cite journal}}: Check date values in: |تاریخ= (help)نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)
  10. Hendrawan; et al. (2011). "Neural-Intelligent Water Drops algorithm to select relevant textural features for developing precision irrigation system using machine vision". Computers and Electronics in Agriculture. ۷۷ (۲): ۲۱۴–۲۲۸. {{cite journal}}: Explicit use of et al. in: |author= (help)
  11. Shah-Hosseini, H. (2012). "Intelligent Water Drops algorithm for automatic multilevel thresholding of gray-level images using a modified Otsu's criterion". Int. J. of Modelling, Identification and Control. ۱۵ (۴): ۲۴۱–۲۴۹.
  12. Shah-Hosseini, H. (2012). "An approach to continuous optimization by the Intelligent Water Drops algorithm". Procedia - Social and Behavioral Sciences. ۳۲: ۲۲۴–۲۲۹.
  13. Niu; et al. (2012). "An improved Intelligent Water Drops algorithm for achieving optimal job-shop scheduling solutions". International Journal of Production Research. ۵۰ (۱۵): ۴۱۹۵–۴۲۰۵. {{cite journal}}: Explicit use of et al. in: |author= (help)
  14. Noferesti; et al. (2012). "A Hybrid Algorithm for Solving Steiner Tree Problem". International Journal of Computer Applications. ۴۱ (۵): ۱۴–۲۰. {{cite journal}}: Explicit use of et al. in: |author= (help)
  15. al-Taani; et al. (2012). "SOLVING THE MAXIMUM CLIQUE PROBLEM USING INTELLIGENT WATER DROPS ALGORITHM". The International Conference on Computing, Networking and Digital Technologies (ICCNDT2012): ۱۴۲–۱۵۱. {{cite journal}}: Explicit use of et al. in: |author= (help)
  16. Hoang; et al. (2012). "Optimal data aggregation tree in wireless sensor networks based on intelligent water drops algorithm". IET Wireless Sensor Systems. ۲ (۳): ۲۸۲–۲۹۲. {{cite journal}}: Explicit use of et al. in: |author= (help)
  17. Srivastava; et al. (2012). "Test Data Generation Based on Test Path Discovery Using Intelligent Water Drop". International journal of applied metaheuristic computing. ۳ (۲). {{cite journal}}: Explicit use of et al. in: |author= (help)
  18. agarwal; et al. (2012). "Code coverage using intelligent water drop (IWD)". International Journal of Bio-Inspired Computation. ۴ (۶): ۳۹۲–۴۰۲. {{cite journal}}: Explicit use of et al. in: |author= (help)
  19. Luangpaiboon, P. (2012). "Optimisation of Manufacturing Process Models via Intelligent Water Drop Algorithm". Applied Mechanics and Materials. ۲۱۷–۲۱۹: ۱۵۰۱–۱۵۰۵.
  20. Khaleel; et al. (2013). "Using intelligent water drops algorithm for optimisation routing protocol in mobile ad–hoc networks". International Journal of Reasoning-based Intelligent Systems. ۴ (۴): ۲۲۷–۲۳۴. {{cite journal}}: Explicit use of et al. in: |author= (help)
  21. Alijla; et al. (2013). "Intelligent Water Drops Algorithm for Rough Set Feature Selection". Intelligent Information and Database systems. ۷۸۰۳: ۳۵۶–۳۶۵. {{cite journal}}: Explicit use of et al. in: |author= (help)
  22. Kayvanfar, V., and Teymourian, E. (۴/06/۲۰۱۴). "Hybrid intelligent water drops algorithm to unrelated parallel machines scheduling problem: a just-in-time approach". International Journal of Production Research (به انگلیسی). Taylor and Fransis. {{cite journal}}: Check date values in: |تاریخ= (help)نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)
  23. Kayvanfar, V., Zandieh, M., Teymourian, E (March 2017). "An intelligent water drop algorithm to identical parallel machine scheduling with controllable processing times: a just-in-time approach". Computational and Applied Mathematics (به انگلیسی). Springer. doi:DOI: 10.1007/s40314-015-0218-3. {{cite journal}}: Check |doi= value (help)نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)
  24. Teymourian, E., Kayvanfar, V., Komaki, GH. M., Khodarahmi, M (2016/3). "An enhanced intelligent water drops algorithm for scheduling of an agile manufacturing system". International Journal of Information Technology & Decision Making (به انگلیسی). World Scientific Publishing Company. doi:DOI: http://dx.doi.org/10.1142/S0219622016500024. {{cite journal}}: Check |doi= value (help); Check date values in: |تاریخ= (help); External link in |doi= (help)نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)
  25. Kayvanfar, V., Moattar Husseini, SM., Karimi, B., Sajadieh, M (۲۰۱۷/7/۳۱). «Bi-objective intelligent water drops algorithm to a practical multi-echelon supply chain optimization problem». Journal of Manufacturing Systems. Elsevier. تاریخ وارد شده در |تاریخ= را بررسی کنید (کمک)

پیوند به بیرون

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