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

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

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

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

آشنایی

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

دَوَن-شناسه (pseudo-code)

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

    ۱) آغازدهی پارامترهای ایستا

        الف. بازنمایی پُرسمان در یک گراف

        ب. ارزش نهادن برای پارامترهای ایستا

    ۲) آغازدهی پارامترهای پویا: تندی و خاک چکاه ها

    ۳) پخش چکاه ها روی گراف پرسمان

    ۴) ساخت گشایش با چکاه ها به همراه به روزکرد تندی و خاک

        الف. به روزکرد خاک بَرزَنی

        ب. به روزکرد تندی و خاک روی چکاه ها

    ۵) جستجوی برزنی روی هر گشایش چکاه (این گام دلخواه هست)

    ۶) به روزکرد خاک سرتاسری

    ۷) به روزکرد گشایش آزگار-بهترین (total-best)

    ۸) به گام ۲ بروید مگر آنکه شرط پایاندهی، خشنود بشود

کاربردها

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

    مسئله کوله‌پشتی چند بعدی[۳]

    برنامه‌ریزی گذرگاه ربات هوایی[۴]

    مشکل راه یابی رسانگر[۵]

    الگوریتم راهیابیMANET[۶]

    گسیل بار اقتصادی[۷]

    مسئله فروشنده دوره‌گرد[۸]

    سرگزینی ویژگی بافت[۹]

    آستانه گیری خودکار چندتراز با یک سنجش بهبودیافته اتسو[۱۰]

    بهینه‌سازی پیوسته[۱۱]

    زمان‌ریزی فروشگاه کار[۱۲]

    مسئله درخت اشتاینر[۱۳]

    مشکل بیشینه همپالگان[۱۴]

    درخت گردآوری داده بهینه در شبکه‌های حسگر بی سیم[۱۵]

    زادگری داده آزمون بر پابه کاوش گذرگاه آزمون[۱۶]

    پوشش کد و شناسه[۱۷]

    بهینه کرد مدلهای فرایند زاد و کار[۱۸]

    بهینه سازی پیمان نامه راهیابی[۱۹]

    سرگزینی ویژگی بافه خشن[۲۰]

۴ Comments

  1. a فروردین ۲۷, ۱۳۹۴ در ۵:۰۱ ق.ظ - پاسخ دادن

    سلام. در زمینه الگوریتم چکه آب هوشمند پروژه انجام می دهید؟

  2. مهدی خانی مرداد ۲۶, ۱۳۹۴ در ۱۰:۱۵ ق.ظ - پاسخ دادن

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

ثبت ديدگاه

پرداخت

1-پرداخت آنلاین
برای پرداخت آنلاین از لینک زیر استفاده کنید
پرداخت آنلاین
2- پرداخت آفلاین
برای پرداخت آفلاین مبلغ مورد نظر را به یکی از شماره کارت
6037997245888723بانک ملی