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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

آشنایی[ویرایش]

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

شبه-کد (pseudo-code)[ویرایش]

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

1) آغازدهی پارامترهای ایستا
الف. بازنمایی پُرسمان در یک گراف
ب. ارزش نهادن برای پارامترهای ایستا
2) آغازدهی پارامترهای پویا: تندی و خاک چکاه ها
3) پخش چکاه ها روی گراف پرسمان
4) ساخت گشایش با چکاه ها به همراه به روزکرد تندی و خاک
الف. به روزکرد خاک بَرزَنی
ب. به روزکرد تندی و خاک روی چکاه ها
5) جستجوی برزنی روی هر گشایش چکاه (این گام دلخواه هست)
6) به روزکرد خاک سرتاسری
7) به روزکرد گشایش آزگار-بهترین (total-best)
8) به گام 2 بروید مگر آنکه شرط پایاندهی، خشنود بشود

کاربردها[ویرایش]

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

جستارهای وابسته[ویرایش]

منابع (فرگاه‌ها)[ویرایش]

  1. Shah-Hosseini, H. (2009). "The intelligent water drops algorithm: a nature-inspired swarm-based optimization algorithm". International Journal of Bio-Inspired Computation 1 (1/2): 71-79. 
  2. Shah-Hosseini, H. (2007). "Problem solving by intelligent water drops". Proceedings of the IEEE Congress on Evolutionary Computation: 3226-3231. 
  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 1 (2): 193-212. 
  4. Duan, et al. (2009). "Novel intelligent water drops optimization approach to single UCAV smooth path planning". Aerospace Science and Technology 13 (8): 442-449. 
  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: 4142-4146. 
  6. Fan, et al. (2010). "The Intelligent-Water-Drop Based Routing algorithm for MANET". Int. Conf. on Future Information Technology: 253-255. 
  7. Rayapudi, S. R. (2011). "An intelligent water drop algorithm for economic load dispatch". International Journal of Electrical and Electronics Engineering 5 (1): 43-49. 
  8. Msallam, et al. (2011). "Improved intelligent water drops algorithm using adaptive schema". International Journal of Bio-Inspired Computation 3 (2): 103-111. 
  9. 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 77 (2): 214-228. 
  10. 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 15 (4): 241-249. 
  11. Shah-Hosseini, H. (2012). "An approach to continuous optimization by the Intelligent Water Drops algorithm". Procedia - Social and Behavioral Sciences 32: 224-229. 
  12. Niu, et al. (2012). "An improved Intelligent Water Drops algorithm for achieving optimal job-shop scheduling solutions". International Journal of Production Research 50 (15): 4195-4205. 
  13. Noferesti, et al. (2012). "A Hybrid Algorithm for Solving Steiner Tree Problem". International Journal of Computer Applications 41 (5): 14-20. 
  14. 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): 142-151. 
  15. Hoang, et al. (2012). "Optimal data aggregation tree in wireless sensor networks based on intelligent water drops algorithm". IET Wireless Sensor Systems 2 (3): 282-292. 
  16. Srivastava, et al. (2012). "Test Data Generation Based on Test Path Discovery Using Intelligent Water Drop". International journal of applied metaheuristic computing 3 (2). 
  17. agarwal, et al. (2012). "Code coverage using intelligent water drop (IWD)". International Journal of Bio-Inspired Computation 4 (6): 392-402. 
  18. Luangpaiboon, P. (2012). "Optimisation of Manufacturing Process Models via Intelligent Water Drop Algorithm". Applied Mechanics and Materials 217-219: 1501-1505. 
  19. 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 4 (4): 227-234. 
  20. Alijla, et al. (2013). "Intelligent Water Drops Algorithm for Rough Set Feature Selection". Intelligent Information and Database systems 7803: 356-365. 

پیوند به بیرون[ویرایش]

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