امیرمحمد حاجی صادقی - دانشجوی کارشناسی ارشد دانشکده مهندسی کامپیوتر، دانشگاه صنعتی امیرکبیر
مهدی افراد

مسیله مسیریابی و پیدا کردن کوتاهترین مسیر همواره یک مسیله مهم طی چند دهه اخیر بوده و بسیار مورد مطالعه قرار گرفته است. به طور کلی مسیله یافتن کوتاه ترین مسیر، یک مسیله بهینه سازی است که گاها می تواند بسیار دشوار و زمانبر باشد. از این رو الگوریتم های اکتشافی مختلفی برای این مسیله پیشنهاد شده است. این الگوریتم به خوبی قابل موازیسازی است چرا که هر مورچه می تواند به صورت مستقل عمل نموده و مسیری را به عنوان یک جواب مسیله ارایه کند. در این مقاله به موازی سازی الگوریتم بهینهسازی کلونی مورچگان (ACO ) به صورت ترکیبی با کمک OpenMP و MPI پرداخته شده است، که میتواند در زمانی بسیار کم تر نسبت به پیاده سازی سریال و همچنین پیاده سازی با OpenMP عمل نموده و بهترین مسیر بین دو نقطه تعیین شده را پیدا کند. در نهایت نسخه موازی شده الگوریتم بر روی چندین گراف برای یافتن کوتاهترین مسیر اعمال شده، و نتایج حاصل بهبود 13.9 برابر نسبت به پیادهسازی سریال و بهبود 1.4 برابر نسبت به حالت موازیسازی با OpenMP را بدست میدهد. تمرکز مقاله بر روی پیادهسازی بهینهسازی کلونی مورچگان به صورت ترکیبی و آنالیز نتایج بدست آمده نسبت به حالت پیاده سازی با OpenMP میباشد

موازی سازی، بهینه سازی کلونی مورچگان، مسیله کوتاه ترین مسیر، OpenMP، MPI