پیاده سازی الگوریتم بهینه سازی کلنی مورچه با CUDA
Publish Year: 1395
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 606
This Paper With 9 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
COMCONF02_182
تاریخ نمایه سازی: 5 بهمن 1395
Abstract:
مورچه ها در طبیعت برای یافتن غذا با یکدیگر از طریق جاگذاری فرومون 3 به عنوان راهنمایی به سمت منبع غذایی همکاری میکنند. الگوریتم بهینه سازی کلنی مورچه ها بر اساس همین اصل کار میکند. در این الگوریتم مورچه های شبیه سازی شده، راه حلی را برای جواب مسئله می سازند و مقادیر فرومون برای دستیابی به جواب بهتر بروزرسانی میشوند. ما این الگوریتم را برای مسئله فروشنده دوره گرد 4 به کار می گیریم. در این مسئله هدف پیدا کردن کوتاه ترین مسیر بین یک مجموعه از شهرها است، به گونه ای که از هر شهر باید دقیقا یک بار عبور کرد. الگوریتم بهینه سازی کلنی مورچه برای این مسئله با توجه به فضای بزرگ جستجوی آن بسیار مناسب است. به عنوان مثال با وجود مسئله ای با تعداد 50 شهر تعداد مسیرهای ممکن بیشتر از تعداد اتم های کشف شده در جهان میباشد. ما الگوریتم بهینه سازی کلنی مورچه را با استفاده از Nvidia CUDA اجرا میکنیم. تا بتوانیم از مزایای واحدهای پردازش گرافیکی 0 در اجرای موازی الگوریتم بهرهمند شویم. GPU ها اجازه میدهند که چندین نخ اجرایی به صورت موازی اجرا شوند و این نخها در داخل بلوکهای نخ سازماندهی میشوند. به ازای هر مورچه ای که مسئول نگهداریاطلاعات حالت و وضعیت تولید کننده مسیر است یک بلوک نخ ایجاد میکنیم. تعداد نخهای موجود در هر بلوک نخ یک فاکتور حیاتی میباشد. به عنوان مثال تعداد 64 نخ در هر بلوک نسبت به 32 نخ در کاربردهای CUDA بهتر عمل میکند. برای مسئله ای با حدود 1291 شهر، بیش از ده فاکتور برای سرعت عملکرد و تسریع وجود دارد.
Keywords:
Authors
مراجع و منابع این Paper:
لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :