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

مسیله فروشنده دوره گرد بیش از 200 سال است که ذهن دانشمندان را به خود معطوف کرده است. اهمیت این مسیله از آنجا ناشی می شود که این مسیله جزء مسایل دشوار یا NP محسوب می شود واز آنجاییکه مسایل کاربردی زیادی در عمل وجود دارند که مشابه مسیله فروشنده دوره گرد می باشند بنابراین پیدا کردن یک راه حل مناسب برای این مسیله می تواند منجر به حل مسایل دیگری شود. روشهای الگوریتمی مانند بازگشت به عقب و برنامه نویسی پویا و ... دارای مرتبه پیچیدگی نمایی هستند. با معرفی روش برنامه نویسی ژنتیک افقی تازه ای جهت حل این مسیله فراروی محققان قرار گرفت. با وجود اینکه الگوریتم ژنتیک برای تعداد داده های کم بخوبی عمل میکند ولی اگر تعداد داده ها زیاد باشد الگوریتم ژنتیک نیز به کندی مسیله را حل میکند حتی ممکن است با تکرار کم بخواهیم سرعت اجرای الگوریتم را زیاد کنیم اما مشکل از اینجا شروع میشود اگر تکرارها را کم کنیم الگوریتم ژنتیک احتمال دارد جواب های نیمه بهینه را پیدا کند . اخیرا سبک نوینی از برنامه نویسی موازی توسط شرکت NVidia ارایه شده است . در این روش برنامه کاربر بر روی هزاران هسته ریز کارت گرافیک به شکل موازی اجراء میشود . این روش باعث میشود سرعت بسیاری از الگوریتم ها در GPU نسبت به اجراء در CPU بسیار زیاد شود . فریم ورکی که شرکت NVidia برای برنامه نویسی GPU تدارک دیده است CUDA نام دارد . در این مقاله مسیله فروشنده دوره گرد با استفاده از الگوریتم ژنتیک توسط تکنولوژی CUDA حل شده است و موازی سازی اجرای این الگوریتم بر روی واحد پردازش گرافیکی را با حالتی که برنامه به صورت سریال بر روی پردازنده اجرا می شود را مقایسه می کند. نشان داده می شود که اجرای الگوریتم به صورت موازی بر روی واحد پردازش گرافیکی نسبت به روش سریال بر روی پردازنده در این مقاله بهتر عمل کرده و امکانی را برای توسعه دهندگان فراهم می کند که از راه حل های مقیاس پذیر و کم هزینه برای اجرای موازی سازی پردازش های محاسباتی سنگین استفاده کنند.

Keywords:

فروشنده دوره گرد , الگوریتم ژنتیک , واحد پردازش گرافیکی , CUDA , موازی سازی