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

مسیله فروشنده دوره گرد یکی ازمسایل بهینه سازی سخت و دشوار در علوم کامپیوتر محسوب می شود. یافتن جواب بهینه مسیله فروشنده دوره گرد درصورتی که اندازه گراف مسیله بزرگ باشد به زمان بسیار زیادی نیاز دارد. الگوریتم ژنتیک یک روش پرکاربرد برای یافتن جواب بهینه مسیله فروشنده دوره گرد می باشد. افزایش زمان اجرا در حالاتی که اندازه شهرها زیاد می شود یکی از ایرادات این الگوریتم ها برای حل مسیله فروشنده دوره گرد است. یکی از روش های کاهش زمان اجرای الگوریتم های تکاملی استفاده از روش های موازی سازی می باشد. استفاده از امکانات پردازنده گرافیکی جهت موازی سازی و تسریع محاسبات یکی از فناوری های جدید کاهش زمان اجرای الگوریتم های مختلف است. در روش پیشنهادی هر یک از اعضای جمعیت اولیه را به صورت جداگانه در یک هسته کودا و توسط یک نخ به اجرا گذاشته و هر عضو جمعیت به صورت موازی با سایر اعضاء قسمتی از فضای جستجوی مسیله را مورد جستجو قرار می دهد.

کلیدواژه ها:

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