پیاده سازی موازی الگوریتم زنبور عسل بر روی GPU
چکیده مقاله پاورپوینت
الگوریتم زنبور عسل، یک روش جمعیت بنیان ، یک الگوریتم کران محاسباتی است که با الهام گرفتن از رفتار طبیعی زنبور عسل به جستجوی یک راهکار شبهبهینه برای مسئله جستجو میپردازد. اخیراً الگوریتمهای موازی گروهبنیان متعددی برای اجرا بر GPU ارائه شدهاند. چرا که امروزه ساخته یک الگوریتم زنبور عسل موازی برای اجرا در GPU از اهمیت بسیار بالایی برخوردار است.
در این مقاله الگوریتم زنبورهای عسل CUBA (یعنی الگوریتم زنبور عسل مبتنی بر CUDA) را برای اجرا در(الگوریتم زنبو مبتنی بر CUDS CUDA.CUBA (معماری دستگاه یکپارچه محاسباتی) بسط میدهیم. عملکرد CUBA را با انجام آزمایشهایی براساس مسائل بیشمار و معروف بهینهسازی مورد بررسی قرار خواهیم داد. نتایج نشان از آن دارند که CUBA به میزان قابل توجهی در بسیاری از مسائل بهینهسازی بهتر از الگوریتم زنبور عسل استاندارد عمل میکند.
الگوریتم زنبور عسل
الگوریتم زنبور عسل یک روش جمعیت بنیان برای جستجوی بهینهسازی مسائل است و از رفتار زنبورهای عسل الهام گرفته است. این الگوریتم نوعی جستجوی همسایگی را همراه با جستجوی تصادفی انجام میدهد و میتوان از آن برای بهینه سازی ترکیبی و بهینه سازی عاملی استفاده کرد. محققان براساس BA به چندین کاربرد حقیقی مبتنی بر الگوریتم زنبورعسل مانند داده کاوی، کنترلربات، مهندسی الکترونیک، زمانبندی کاری، ازمایش مجازی، تخصیص وظایف و …. دست یافتهاند. الگوریتمهای بهینهسازی گروهبنیان در سطح گستردهای برای شتابدادن به عملکرد مسائل جستجو بکار برده شدهاند. تکنیک موازیسازی غالباً در مسائل مختلف هوش گروهی مانند پیادهسازی موازی بهینهسازی کلونی مورچه، الگوریتم ژنتیک موازی(PGA) ، بهینهسازی جهانی موازی با الگوریتم گروه ذرات، الگوریتم زنبور عسل موازی(PBA)، و کلونی مصنوعی زنبورعسل موازی (PABC) و … بکار برده میشود. راهبرد موازیسازی پیشنهادی نه تنها کیفیت راهکار بدست آمده را پایین میاورد بلکه باعث افزایش سرعت به میزان قابل توجهی میگردد.
الگوریتم کلونی زنبورها
الگوریتم کلونی زنبورها یک روش جمعیتبنیان برای یافتن یک پاسخ شبهبهینه برای مسائل جستجوست. این الگوریتم از رفتار زنبورهای عسل در طبیعت الهام گرفته است و لازم است که پیشاپیش چند پارامتر برای آن تعیین گردند: n(تعداد زنبورهای پیشاهنگ، m(تعداد سایتهای انتخاب شده از بین n سایت بازدید شده)، e(تعداد بهترین سایتها از بین mسایت انتخاب شده)، nep(تعداد زنبورهای استخدامشده برای بهترین سایتهاe)، nsp(تعداد زنبورهای استخدامشده برای(m-e) سایت انتخاب شده دیگر)،ngh(اندازه اولی دستههایی که شامل سایت و همسایگی آن میباشند) و معیار توقف. الگوریتم با n زنبور پیشاهنگ آغاز میشود که بطور تصادفی در دامنه جستجو قرار داده میشوند. الگوریتم پایه در بخشهای بعدی توضیح داده خواهد شد. فلوچارت متناظر آن در شکل ۱ نمایش یافته است.