مقاله #128

چکیده

مساله­ ی مسیریابی وسیله ی نقلیه (VRP) یکی از چالش برانگیزترین مسائل بهینه سازی ترکیبیاتی است که به مدت چندین دهه بررسی شده است. وقتی تعداد نقطه هایی که باید ملاقات شود زیاد می گردد، تعداد جواب ها برای VRP به صورت نمایی افزایش می یابد. در یک جواب مستقیم تعداد3.0 * 10 ^ 64  جواب مختلف برای ملاقات 50 نقطه وجود دارد و آزمودن همه ی این جایگشت ها عملاً غیرممکن است. بعضی از رویکردها مثل الگوریتم های تکاملی پیدا کردن جواب های شدنی را در یک زمان قابل قبول میسر می سازند. با این حال اگر تعداد نقاط ملاقاتی افزایش پیدا کند، این الگوریتم ها به محاسبات بسیار کارا نیاز دارند و آن ها به سرعت برای پیدا کردن یک جواب شدنی ناکافی می شوند. واحدهای پردازش گرافیک (GPUها) با میسر کردن پردازش موازی در تعداد زیادی تور (grid) محاسباتی، توان محاسباتی سرشاری دارند و می توانند به بهره های کارایی مهمی نسبت به پیاده سازی های معمول روی CPU بینجامند. در این مقاله، هدف این است که پیاده سازی موثری از الگوریتم ژنتیک نمایش دهیم. الگوریتم ژنتیک یک الگوریتم تکاملی است که از فرایندهای مشاهده شده در تکامل بیولوژیکی ارگانیسم های زنده برای پیدا کردن جواب های تقریبی  مسائل بهینه سازی مانند مساله ی فروشنده ی دوره گرد بر روی GPU الهام گرفته است. یک رویکردِ "یک نخ در یک موقعیت" (1T1P) برای بهبود کارایی با استفاده از بیشینه کردن بهره وری توسعه داده شده است که با استفاده از GPU ها تسریع مهمی ایجاد می کند. کارایی سیستم پیاده سازی شده با پارامترهای مختلف و پیاده سازی مشابه بر روی CPU اندازه گیری شده است.