Abstract
Ant Colony Optimisation (ACO) is an effective population-based meta-heuristic for the solution of a wide variety of problems. As a population-based algorithm, its computation is intrinsically massively parallel, and it is therefore theoretically well-suited for implementation on Graphics Processing Units (GPUs). The ACO algorithm comprises two main stages: Tour construction and Pheromone update. The former has been previously implemented on the GPU, using a task-based parallelism approach. However, up until now, the latter has always been implemented on the CPU. In this paper, we discuss several parallelisation strategies for both stages of the ACO algorithm on the GPU. We propose an alternative data-based parallelism scheme for Tour construction, which fits better on the GPU architecture. We also describe novel GPU programming strategies for the Pheromone update stage. Our results show a total speed-up exceeding 28x for the Tour construction stage, and 20x for Pheromone update, and suggest that ACO is a potentially fruitful area for future research in the GPU domain
چکیده
بهینه سازی کلونی مورچگان (ACO) را میتوان یکی از راه حل های عمده و مبتنی بر جمعیت دانست که برای حل مسائل زیادی کاربرد دارد. بهینه سازی کلونی مورچگان که یک نوع الگوریتم میباشد، از ماهیت موازی برخوردار بوده و بنابراین از نظر تئوری میتوان آنرا برای پیاده سازی واحد های پردازش گرافیکی(GPU) ایده آل دانست. این الگوریتم از دو گام اصلی تشکیل شده است: ساخت تور یا مسیر و بروز رسانی فرمون. گام اول قبلاً بر روی GPU پیاده سازی شده است که البته از یک روش موازی سازی مبتنی بر وظیفه برای این پیاده سازی استفاده شده است. اگرچه امروزه میتوان پیاده سازی گام دوم را نیز بر روی GPU مشاهده کرد. در این مقاله، چندین استراتژی موازی سازی برای هر دو مرحله ی مربوط به الگوریتم ارائه خواهیم داد. یک شِمای موازی سازی را برای ایجاد تور پیشنهاد خواهیم کرد که با معماری GPU سازگاری بهتری دارد. همچنین استراتژی های برنامه نویسی جدیدی را برای مرحله ی بروز رسانی فرمون ارائه خواهیم داد. نتایج ما یک افزایش سرعت 28 برابری را برای گام ایجاد مسیر و افزایش سرعت 20 برابری را برای بروز رسانی فرمون نشان میدهد و حاکی از این است که ACO را میتوان یک دامنه ی غنی برای پژوهش های آینده مرتبط با GPU ها دانست
1-مقدمه
بهینه سازی کلونی مورچگان(ACO) را میتوان یک متد جستجوی مبتنی بر جمعیت دانست که ایده ی آن از رفتار واقعی مورچه ها نشأت گرفته است. این متد ممکن است در مسائل سخت عمده ای بکار گرفته شود[2],[3] که اغلب آنها ماهیتی گراف-تئوریک دارند. این متد در ابتدا در مسئله ی فروشنده ی دوره گرد (TSP) و در سال 1991 میلادی صورت گرفت[5],[6]. در اصل، مورچه های شبیه سازی شده راه حل هایی را برای مسئله ی TSP و به شکل تور هایی ایجاد میکنند. مورچه های مصنوعی را میتوان عامل های ساده ای دانست که تور ها را به صورت موازی و به صورت احتمالاتی ایجاد میکنند. آنها به وسیله ی مسیر های فرمون و اطلاعات هیروستیک اقدام به ایجاد این تور ها میکنند. مسیر های فرمون را میتوان یکی از مؤلفه های اساسی الگوریتم دانست، زیرا محاوره ی غیر مستقیم الگوریتم ها را با استفاده از محیط آسان کرده که چنین روشی، Stigmergy نام دارد[7]. یک مبحث کاملی از بهینه سازی کلونی مورچگان و Stigmergy را نمیتوان در این مقاله مورد پوشش قرار داد، ولی خوانندگان میتوانند برای یک بازبینی کامل از این موضوع به [1] مراجعه کنند...