ارایه یک روش جدید موازی مبتنی بر الگوریتم کلونی مورچه ها در حل مسایل بهینه سازی با استفاده از واحد پردازش کارت گرافیک

الگوریتم های فرااکتشافی یکی از انواع الگوریتم های بهینه سازی هستند که در طیف گسترده ای از مسایل سخت مهندسی بکار گرفته می شوند. یکی از الگوریتم های فرا اکتشافی موفق در حل مسایل بهینه سازی، الگوریتم کلونی مورچه ها است که روشی الهام گرفته از رفتار مورچه ها در پیدا کردن کوتاهترین مسیر بین لانه و یک منبع غذایی می باشد. در این الگوریتم هر راهحل مسیله به صورت یک مورچه کدگذاری شده و مورچه ها با پیمایش فضای مسیله مقداری فرومون از خود منتشر نموده و در نهایت مسیرهای پرتردد با داشتن مقدار بیشتری فرومون بهینهتر و کوتاهتر بود و از این جهت مورد توجه سایر مورچه ها قرار گرفته میشوند. در مسیله فروشنده دورهگرد هدف یافتن تور یا مسیر بهینه و کوتاهی است که کل راسهای گراف را یک مرتبه ملاقات نماید. مسیله فروشنده دورهگرد یک مسیله بهینهسازی سخت و دشوار است و راهحل قطعی در زمان کمتر از نمایی برای آن وجود ندارد و این عامل باعث میشود با افزایش اندازه گراف مسیله الگوریتم بهینهسازی کلونی مورچه ها برای یافتن تور بهینه به زمان قابل توجهی نیاز داشته باشد. الگوریتم کلونی بهینهسازی مورچه ها به دلیل آنکه یک الگوریتم مبتنی بر جمعیت است و هر راهحل میتواند مستقل از سایر راهحل ها فضای مسیله را پیمایش نماید دارای ماهیت موازی بوده و میتوان آن را در بسترهای موازی نظیر پردازنده گرافیکی کودا موازی نمود و زمان اجرای آن را کاهش داد. عمده ترین مشکل الگوریتم های فرااکتشافی بطور عموم و الگوریتم کلونی مورچگان بطور خاص، نیاز به تکرارهای زیاد برای رسیدن به جواب بهینه مساله می باشد. در این مقاله از معماری پردازنده گرافیکی برای شتاب دادن به الگوریتم کلونی بهینهسازی مورچه ها برای حل مسیله فروشنده دورهگرد استفاده شده و نتایج حاصل ازاجرای موازی آن در پردازنده گرافیکی با حالت اجرای غیرموازی آن بر روی پردازنده اصلی مقایسه می کنیم.در پیاده سازی موازی خود از تکنولوژی کودا و نخ های همزمان بهره می بریم ودر انتخاب تعداد نخ سعی بر آن داشتیم که تعادل مناسبی بین افزایش سرعت الگوریتم در مقابل سربار تبادل پیام بین نخ ها ایجاد کنیم. هر یک از راهحل ها یا مورچه ها به صورت جداگانه در یک هسته پردازشی کودا مسیرهای بهینه در گراف را جستجو مینمایند. نتایج آزمایشات ما بر روی پردازنده گرافیکی Gforce 710 شرکت انویدیا نشان میدهد اجرای موازی با افزایش اندازه گراف یا تعداد شهرها منجر به کاهش قابل ملاحظه تکرارها در کشف مسیر شده، و درحالیکه زمان اجرای پردازنده اصلی و گرافیکی را افزایش میدهد این افزایش در پردازنده گرافیکی کمتر بوده و نسبت زمان اجراء در پردازنده اصلی به پردازنده گرافیکی یا شتاب محاسبات با افزایش گراف نیز افزایش مییابد، به گونهای که در گرافی به اندازه تقریبی 100 شتاب روش پیشنهادی حدودا برابر 33,58 میشود.

Keywords:

الگوریتم فرااکتشافی , الگوریتم کلونی بهینه سازی مورچه ها , مسیله فروشنده دوره گرد , پردازنده گرافیکی , کودا , موازی سازی , شتاب