موازی سازی الگوریتم بهینه سازی کلونی مورچه ها برای حل مسیله کوتاهترین مسیر به صورت ترکیبی با استفاده از OpenMP و MPI
Publish Year: 1396
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 711
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
CITCOMP02_226
تاریخ نمایه سازی: 7 اسفند 1396
Abstract:
مسیله مسیریابی و پیدا کردن کوتاهترین مسیر همواره یک مسیله مهم طی چند دهه اخیر بوده و بسیار مورد مطالعه قرار گرفته است. به طور کلی مسیله یافتن کوتاه ترین مسیر، یک مسیله بهینه سازی است که گاها می تواند بسیار دشوار و زمانبر باشد. از این رو الگوریتم های اکتشافی مختلفی برای این مسیله پیشنهاد شده است. این الگوریتم به خوبی قابل موازیسازی است چرا که هر مورچه می تواند به صورت مستقل عمل نموده و مسیری را به عنوان یک جواب مسیله ارایه کند. در این مقاله به موازی سازی الگوریتم بهینهسازی کلونی مورچگان (ACO ) به صورت ترکیبی با کمک OpenMP و MPI پرداخته شده است، که میتواند در زمانی بسیار کم تر نسبت به پیاده سازی سریال و همچنین پیاده سازی با OpenMP عمل نموده و بهترین مسیر بین دو نقطه تعیین شده را پیدا کند. در نهایت نسخه موازی شده الگوریتم بر روی چندین گراف برای یافتن کوتاهترین مسیر اعمال شده، و نتایج حاصل بهبود 13.9 برابر نسبت به پیادهسازی سریال و بهبود 1.4 برابر نسبت به حالت موازیسازی با OpenMP را بدست میدهد. تمرکز مقاله بر روی پیادهسازی بهینهسازی کلونی مورچگان به صورت ترکیبی و آنالیز نتایج بدست آمده نسبت به حالت پیاده سازی با OpenMP میباشد
Keywords:
Authors
امیرمحمد حاجی صادقی
دانشجوی کارشناسی ارشد دانشکده مهندسی کامپیوتر، دانشگاه صنعتی امیرکبیر