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

سال انتشار: 1394
محل انتشار: سومین کنفرانس بین المللی پژوهشهای کاربردی در مهندسی کامپیوتر و فن آوری اطلاعات
کد COI اختصاصی: CITCONF03_641
زبان مقاله: فارسی
تعداد مشاهده: 624

نویسندگان

دانشجوی کارشناسی ارشد مهندسی نرم افزار ، دانشگاه آزاد اسلامی واحد میبد ، یزد ، ایران

استادیار کامپیوتر و عضو هیات علمی ، دانشگاه آزاد اسلامی واحد میبد ، یزد ، ایران

چکیده

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

کلیدواژه ها

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

مقالات مرتبط جدید

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.