Abstract
The vehicle routing problem (VRP) is one of the most challenging combinatorial optimization problems, which has been studied for several decades. The number of solutions for VRP increases exponentially while the number of points, which must be visited increases. There are 3.0×10^64 different solutions for 50 visiting points in a direct solution, and it is practically impossible to try out all these permutations. Some approaches like evolutionary algorithms allow finding feasible solutions in an acceptable time. However, if the number of visiting points increases, these algorithms require high performance computing, and they remain insufficient for finding a feasible solution quickly. Graphics Processing Units (GPUs) have tremendous computational power by allowing parallel processing over lots of computing grids, and they can lead to significant performance gains compared with typical CPU implementations. In this paper, it is aimed to present efficient implementation of Genetic Algorithm, which is an evolutionary algorithm that is inspired by processes observed in the biological evolution of living organisms to find approximate solutions for optimization problems such as Traveling Salesman Problem, on GPU. A 1-Thread in 1-Position (1T1P) approach is developed to improve the performance through maximizing efficiency, which then yielded a significant acceleration by using GPUs. Performance of implemented system is measured with the different parameters and the corresponding CPU implementation
چکیده
مساله ی مسیریابی وسیله ی نقلیه (VRP) یکی از چالش برانگیزترین مسائل بهینه سازی ترکیبیاتی است که به مدت چندین دهه بررسی شده است. وقتی تعداد نقطه هایی که باید ملاقات شود زیاد می گردد، تعداد جواب ها برای VRP به صورت نمایی افزایش می یابد. در یک جواب مستقیم تعداد3.0 * 10 ^ 64 جواب مختلف برای ملاقات 50 نقطه وجود دارد و آزمودن همه ی این جایگشت ها عملاً غیرممکن است. بعضی از رویکردها مثل الگوریتم های تکاملی پیدا کردن جواب های شدنی را در یک زمان قابل قبول میسر می سازند. با این حال اگر تعداد نقاط ملاقاتی افزایش پیدا کند، این الگوریتم ها به محاسبات بسیار کارا نیاز دارند و آن ها به سرعت برای پیدا کردن یک جواب شدنی ناکافی می شوند. واحدهای پردازش گرافیک (GPUها) با میسر کردن پردازش موازی در تعداد زیادی تور (grid) محاسباتی، توان محاسباتی سرشاری دارند و می توانند به بهره های کارایی مهمی نسبت به پیاده سازی های معمول روی CPU بینجامند. در این مقاله، هدف این است که پیاده سازی موثری از الگوریتم ژنتیک نمایش دهیم. الگوریتم ژنتیک یک الگوریتم تکاملی است که از فرایندهای مشاهده شده در تکامل بیولوژیکی ارگانیسم های زنده برای پیدا کردن جواب های تقریبی مسائل بهینه سازی مانند مساله ی فروشنده ی دوره گرد بر روی GPU الهام گرفته است. یک رویکردِ "یک نخ در یک موقعیت" (1T1P) برای بهبود کارایی با استفاده از بیشینه کردن بهره وری توسعه داده شده است که با استفاده از GPU ها تسریع مهمی ایجاد می کند. کارایی سیستم پیاده سازی شده با پارامترهای مختلف و پیاده سازی مشابه بر روی CPU اندازه گیری شده است.
کلمات کلیدی: TSP، GAموازی، CUDA، کارایی بالا،1T1P
1- مقدمه
مساله ی مسیریابی وسیله ی نقلیه (VRP) [1] یک مساله ی logestics ( مدیریت جریان محصولات بین نقطه ی منبع و نقاط مصرف کننده) مهم است که به مدت چندین دهه بررسی شده است و تلاش می کند کم ترین هزینه ی مسیرهای ترکیب شده را برای یک یا چند وسیله ی نقلیه بیابد تا تحویل محصولات را از یک مکان انبار به تعدادی مقصد تسهیل نماید. هزینه ی کل به طول مسیر توزیع شده وابسته است. بنابراین اگر یک تجارت خانه ی logestics بتواند طول این مسیر را کاهش دهد، می تواند سود و سهم خود از بازار را افزایش دهد. مساله ی فروشنده ی دوره گرد (TSP)، [2] [3] احتمالا بیشتر از مسائل دیگر VRP بررسی شده است و به عنوان یک بستر آزمایشی استاندارد برای ایده های الگوریتمیک جدید برای حل کردن VRP پذیرفته شده است.
تعداد جواب های TSP با افزایش تعداد نقاطی که باید ملاقات شوند، به طور نمایی زیاد می شود. بنابراین کنترل کردن همه ی جواب های ممکن در یک مساله ی TSP با تعداد نقاط زیادی که باید ملاقات شوند، غیرممکن است که تعداد جواب های ممکن در جدول 1 نشان داده شده است. همان طور که جدول 1 نشان می دهد، تعداد 3.0 * 10 ^ 64 جواب مختلف برای ملاقات 50 نقطه وجود دارد...