بخشی از مقاله
پیادهسازی موازی الگوریتم ژنتیک برای حل مسئله فروشنده دورهگرد با استفاده از CUDA
چکیده- با گسترش روزافزون جوامع، نیاز به صرفهجویی و یافتن روشهایی برای به حداقل رساندن زمان و هزینه، بیشتر ضرورت پیدا میکند. جهت نیل به این مقصود از روشهای بهینهسازی استفاده میشود. یکی از مسائل مهم بهینهسازی، مسئله فروشنده دورهگردمیباشد. در این مقاله یک پیادهسازی موازی برای حل مسئله فروشنده دورهگرد با استفاده از الگوریتم ژنتیک که سرعت بالای محاسباتی در یافتن راهحلهای بهینه را دارد در محیط CUDA ارائه میشود.
کلید واژه- الگوریتم ژنتیک، مسئله فروشنده دورهگرد، CUDA، GPU
-1 مقدمه
الگوریتم ژنتیک و دیگر الگوریتمهای جستجوی تصادفی معمـولاً در حل مسائل NP1 مورد استفاده قرار میگیرند. مسئله فروشنده دورهگرد یکی از مسائل معروف NP سخت میباشد. هدف از ایـن مسئله به دست آوردن کوتاهترین پوشش اطراف مسیر سفر، برای گروهی از شهرها میباشد. ازآنجاکه مسائل NP سخت نمیتواننـد در زمان قابل قبـولی حـل شـوندبنابراین افـراد سـعی بـر یـافتن راه حلهای قابلقبول در زمان مناسـب دارنـد. بـرای ایـن منظـور الگوریتمهای اکتشافی مختلفی از قبیل الگوریتم ژنتیک طراحـی شدند.[1]
الگوریتم ژنتیک، تکنیکی اسـت کـه از تکامـل ژنتیکـی و اصـول انتخاب طبیعی دارویـن بـهعنـوان الگـوی حـل مسـئله اسـتفاده میکند.[2] قانون انتخاب طبیعی بیانگر ایـن مسـئله اسـت کـه تنها گونههایی از یک جمعیت میتوانند نسل خود را ادامه دهند، که بهترین خصوصیات را داشته باشند و همچنین قادر به انتقـال خصوصیات برتر به نسلهای بعدی میباشند.[3]
الگوریتم ژنتیک از مفاهیم علم زیسـتشناسـی همچـون وراثـت، جهش و انتخاب طبیعی برگرفتهشده است، در مسـئله فروشـنده دورهگرد با مشاهدهی کروموزومها راهحلهای کراسآور2 و جهش بهعنوان مراحل تغییر کروموزوم ها محسوب میشوند. درحالی کـه انتخاب طبیعی، بـهعنـوان یـک مرحلـهی غربـالگـری شـناخته میشود. این مرحله قادر به جدا نمـودن راهحـلهـای مناسـب از راهحلهای نامناسب است.[1]
بنابراین با افزایش اندازه مسئله، زمان بیشتری نیز برای رسـیدن به یک راهحل مطلوب نیـاز اسـت. بـرای حـل مسـئله فروشـنده دورهگرد 2 –opt، یک اپراتور ویژه طراحی شـده اسـت کـه زمـان بیشتری نسبت به اپراتورهای معمولی صرف مـیکنـد امـا دارای همگرایی ثابت و سریعتـری اسـتاخیـراً. الگـوی برنامـهنویسـی NVIDIA CUDA، GPU را بــهعنــوان یــک برنامــه محاســباتی معرفی میکند.
GPUبــا تعــداد هســتههــای بســیار، مــیتواننــد تشــابه را درون الگوریتمهای ژنتیک برای تسریع اجرا پیگیری کنند و یـک روش مقرون به صرفه از اجرای راهحلهای نوع SIMD را فراهم آورند. در این مقاله سعی در پیادهسازی مسئله فروشنده دورهگرد به کمک الگوریتم ژنتیک در محـیط CUDA را داریـم. البتـه بایـد توجـه داشت که الگوریتم ژنتیک، رسیدن به بهترین جـواب را تضـمین نمیکند. ولی با صرف زمانی محدود میتوان به جوابی قابل قبـول برای مسئله رسید. این جواب ممکن اسـت بهتـرین جـواب و یـا نزدیکترین جواب به آن باشد.
بخشهای بعدی مقاله بهصورت زیر میباشد:
در بخش دو، معمـاری CUDA، بخـش سـه، الگـوریتم ژنتیـک و مراحــل آن موردبررســی قــرار مــیگیــرد. بخــش چهــار شــامل مــوازیســازی الگــوریتم ژنتیــک، بخــش پــنج مســئله فروشــنده دورهگــرد، بخــش شــش الگــوریتم ژنتیــک در مســئله فروشــنده دورهگـرد، بخــش هفـتم شــامل کارهــای مـرتبط، بخــش هشــتم پیادهسازی و نتایج تجربی و بخش نهـم نتـایج و کارهـای آتـی را شامل میشود.
-2 معماری CUDA
امروزه GPUبه عنوان یک پردازنده با منابع محاسباتی بسیار زیـاد موردتوجه قرار گرفته اسـت.[4] تعـداد هسـتههـای فـراوان ایـن پردازنــده و همچنــین پهنــای بانــد زیــاد حافظــهی کــارتهــای گرافیکی، قابلیت اجرای تعداد نخهای موازی بسـیار زیـادی را در مقایسه با CPU به این پردازنده داده اسـت. بـهطـورکلی سـاختار
GPUبه گونه ای است کـه بـا پـردازش دسـتهای دادههـا، بـازدهی محاسبات را افزایش میدهد.
GPUها در ابتدا به صورتسختافزارهایی با کـارکرد ثابـت و بـرای محاسبات گرافیکی به وجود آمدند. تبدیل مسئلهی هدف به یـک مسئلهی گرافیکی، خود موضوعی چالش برانگیز بود کـه اسـتفاده از GPUهــا را مشــکل و درنتیجــه محــدود مــیکــرد. درنهایــت سازندگان این تراشهها به فکر ارائهی یک معماری عـام بـههمـراه یک زبان سطح بالای برنامه نویسی افتـاده و مفهـوم GPU همـه-منظوره یـاGPGPU را معرفـی کردنـد. ازجملـه مهـمتـرین ایـن معماریها CUDA است که در آن هر GPU شامل چندین واحـد پردازشی مستقل به نام جریانهای چندپردازنده ای3 است. هر یک از این واحدها نیز به نوبهی خـود حـاوی چنـدین هسـته اجرایـی هستند.[5]
برنامهای که مطابق با معماری CUDA نوشته شـده باشـد شـامل دو جز سری و موازی است که قسمت سـری آن بـر روی CPU و قسمت موازی آن بر روی GPU در قالب توابع خاصی به نام کرنل اجرا میگردند. در حین اجرا، ابتدا برنامه توسـط CPUشـروع بـه کار کرده و به صورت سری و خط به خط جلـو مـیرود. اگـر یـک
خط خاص شامل یک فراخوانی کرنل باشد. درنهایتGPUوارد عمل شده و تعداد زیادی نخ مـوازی را کـه تمـامی آنهـا تـابع کرنل را اجـرا مـیکننـد؛ ایجـاد مـیگـردد. در معمـاری CUDA فراخوانی یک تابع کرنل در قالب ایجاد یک تور از نـخهـا صـورت میگیرد که هر تور حاوی چندین بلوک بوده کـه هـر بلـوک نیـز حاوی چندین نخ است.
-3 مروری بر الگوریتم ژنتیک
الگوریتم ژنتیک، بهعنوان روش جستجویی جهـت یـافتن جـواب برتر و نه الزاماً بهینه است. این الگوریتم ابزاری اسـت کـه توسـط آن، ماشــین مــیتوانــد مکــانیزم طبیعــی را شــبیهســازی نمایــد. الگوریتمهای ژنتیک معمولاً بهعنوان یک شبیهساز کامپیوتر، برای دستیابی به راهحل بهتر، پیادهسازی میشـوند.[6] رونـد اجـرای الگوریتم ژنتیک به شرح زیر میباشد:
1. شروع با یک جمعیت متشکل از تعدادی کروموزوم تصادفی
2. محاسبه شایستگی برای هر کروموزوم
3. انتخاب در کروموزوم براساس شایستگی
4. اعمال ترکیب و ایجاد کروموزوم جدید
5. اعمال جهش با ضریب P
6. تغییر دادن جمعیت اولیه همراه با ورود نسل جدید
7. بررسی شرایط پایان برنامه
8. رفتن به مرحله 2
-1-3 مراحل الگوریتم ژنتیک
کدگــذاری: منظــور از کــدگــذاری، ارائــه یــک شــبیهســازی و جایگــذاری خــوب بــرای کلیــه جــوابهــای ممکــن اســت. ایــن جایگذاری به سه صورت کدگـذاری بـاینری، جایگشـت و مقـدار حقیقی میباشد.
روشهای انتخاب: یکی از روشهای انتخـاب والـدین قـراردادن کروموزومها در شرایط رقابتی میباشد. بـدینصـورت کـه در هـر مرحلــه تعــداد چهــار کرومــوزوم را در نظــر گرفتــه و از بــین کرومــوزومهــا، دو کرومــوزوم را کــه دارای بهتــرین شایســتگی میباشند، بهعنوان والدین انتخاب میشوند.
جهش: منظور از جهش، تغییر تصادفی یک ژن میباشد. فرآینـد جهش در الگوریتم ژنتیک بر روی یک کروموزوم اعمال میشود و ژنهایی از کروموزوم را به صورت تصـادفی تغییـر مـیدهـد. ایـن فرآیند به سـه دسـتهی جهـش بیتـی، جهـش پشـتک و جهـش شیفت چرخشی مطرح میباشند.
انتخاب نخبه: در این روش مناسبترین عضو انتخاب میشـود و مستقیماً به نسل بعد انتقال پیدا میکنـد. ایـن امـر باعـث حفـظ همگرایی مسئله میشود.[7]
-4 موزای سازی الگوریتم ژنتیک
موازیسازی الگوریتم ژنتیک راهبردی است که اغلب برای بهبـود کارایی این الگوریتمها مطرح میشـود. در سـالهـای اخیـر ایـن راهبرد به شدتموردتوجه قرار گرفته و نتـایج قابـلتـأملی در ایـن زمینه به دست آمده است.[8] الگوریتمهای های ژنتیک اغلب در مورد کارایی زمانی، به دلیل عملیات زمان برشـان، مشـکل دارنـد. راهبرد موازیسازی امکان استفاده از منابع گستردهتر و دسـتیابی به سرعت قابلقبولتری برای الگوریتم را فراهم میسازد.[9]
-1-4 مدلهای موازیسازی الگوریتم ژنتیک
مدلهای موازیسازی الگوریتم ژنتیک را میتوان بـه سـه دسـته اصـلی مــدلهــای فرمانـده-فرمــانبــر، مـدلهــای دانــهدرشــت و مدلهای دانـهریـز تقسـیم نمـود.[10] در انـدازهگیـری کـارآیی الگوریتمهای ژنتیک موازی معیارهـایی چـون زمـان محاسـباتی، زمان ارتباط، CTCو PTCمطرح هسـتند.[11] بـرای هـر یـک از مدلهای موازیسازی توپولوژیهای معینی استفاده میشود.
-2-4 معماری مدل موازی مبتنی بر عامل
زمانی که از عاملهـا بـرای مـوازیسـازی الگـوریتمهـای ژنتیـک استفاده میکنیم، توپولوژی عاملها نیز از مکانیزم ارتباطی میـان عامــلهــا برحســب نــوع الگــوریتم ژنتیــک اســتفاده مــیشــود. محدودیتها و قابلیتهای هر یک از این روشها، بـه نقشـی کـه عامل در آنها میتواند عهدهدار شود، بستگی دارد. .[12] با توجه به این که هدف بهره گرفتن از خاصـیت تحـرک عامـلهـا اسـت. بنابراین از میان مدلهای مختلف موازیسازی الگـوریتم ژنتیـک، مدل دانهدرشت مناسبترین مدل برای کار با عاملهااست.[2]
-5 مسئله فروشنده دورهگرد
مسئله فروشنده دورهگرد یکی از مسائل مهم بهینهسازی است که بر اساس آن، یک فروشنده دورهگرد میخواهد به N شهر رفته و کالای خود را به فروش برساند. بهطوریکه فروشندهی دورهگرد از تمام شهرها تنها یک بار عبور کند، البته به شرطی کوتاهترین مسیر را طی کرده باشد. فضای حل مسئله فروشنده دورهگرد با زیاد شدن تعداد شهرها به سرعت افزایش مییابد و با روشهای خطی نمیتوان جواب بهینه آن را به دست آورد. به همین دلیل است که این مسئله جزء گروه مسائل NP سخت قرار میگیرد.[10] مسائل NP سخت مسائلی هستند که با روشهای تحلیلی بهسختی حل میشوند.
-6 الگوریتم ژنتیک در مسئله فروشنده دورهگرد
ورودی الگوریتم ژنتیک معمولاً تعدادی نقاط مسیر و یک جـدول فاصله است. این ورودی میتواند یـک زنجیـره از کرومـوزومهـای بهینهشده باشد. این زنجیره، ترتیب شهرهایی را نشان مـیدهـد که فروشنده دورهگرد بایستی دنبال کنـد. مرحلـه مـوازیسـازی همانگونـه در شـکل (1) نشـان داده شـده اسـت، یـک گـروه از کروموزومها را ایجاد میکند. اندازه گروه میتواند کیفیت نتیجهی پایانی و زمان اجرایی را تحت تأثیر قرار دهد. وقتـی انـدازه گـروه افزایش مییابد، نتایج بهطور بالقوه بهتـر مـیباشـند. درحـالیکـه زمان اجرا کاهش مییابد.
شکل.1 توالی کروموزوم اولیه تولیدشده از الگوریتم ژنتیک
در مسئله فروشنده دورهگرد متأسفانه، تعداد کروموزوم مشـابه در یک زنجیره وجود ندارد. بنابراین انجام کراس آوربهطـور مسـتقیم همانند کروموزومهـا در دنیـای واقعـی امکـانپـذیر نمـیباشـند. همانگونه کـه در شـکل (2) نشـان داده شـده اسـت، کـراسآور بخش انتخاب شده کروموزوم به طور معقولانه صورت گرفته است. از آنجایی که کروموزومهای خوب مجبور میباشند در جمعیـت باقی بمانند و اطلاعات موروثی خود را به کراسآور انتقال دهنـد. پس از تولید نسل، کروموزومها یکدیگر را جذب میکنند.
شکل.2 کراس آور در الگوریتم ژنتیک بر روی مسئله فروشنده دورهگرد
مراحل جهـش، جهـت ایجـاد تغییـرات غیرقابـل پـیشبینـی در کروموزومها طراحی شدهاند. برخـی اپراتورهـای جهـش، فرآینـد همگرایی را کند میکنند. 2-optمی تواند هـمگرایـی الگـوریتم را سریعتر کند و تکامل تنوع و ثبات را متضـمن شـود. جزئیـات در 2-opt در شکل (3) نشان داده شده است.[14 ,13]
