موازی سازی الگوریتم کلونی مورچگان در طراحی شبکه گسسته حمل و نقل | ||
| مهندسی عمران مدرس | ||
| Article 4, Volume 15, Issue 2, 1394, Pages 37-50 PDF (484.9 K) | ||
| Authors | ||
| امیرعلی زرین مهر* 1; مرتضی پرویزی2; یوسف شفاهی3; سید احسان سیدابریشمی4 | ||
| 1دانشگاه تربیت مدرس | ||
| 2دانشکده فنی دانشگاه تهران | ||
| 3دانشکده مهندسی عمران و محیط زیست دانشگاه صنعتی شریف | ||
| 4دانشکده مهندسی عمران و محیط زیست دانشگاه تربیت مدرس | ||
| Abstract | ||
| طراحی شبکه گسسته حملونقل عبارت است از انتخاب زیرمجموعهای امکانپذیر از پروژهها (بزرگراهها)ی پیشنهادی در یک شبکه حملونقل به منظور کمینهسازی زمان سفر کل کاربران شبکه. این مساله در رده مسائل NP-Hard است که هیچ الگوریتم موثری برای حل دقیق آنها در مقیاس بزرگ وجود ندارد. ازاینرو بیشتر مطالعات انجامگرفته، به منظور یافتن جوابی نسبتا خوب در مدت زمانی معقول، از طریق رویکردهای ابتکاری و فراابتکاری به مساله پرداختهاند. اما راه دیگری که همچنان برای افزایش سرعت رویکردهای حل مساله وجود دارد، محاسبات موازی است. مقاله پیشرو، به بررسی کاربرد محاسبات موازی در یک الگوریتم فراابتکاری در مساله طراحی شبکه گسسته حملونقل میپردازد. در این مقاله، یک الگوریتم موازی کلونی مورچگان، بر مبنای مطالعه پورزاهدی و ابوالقاسمی، با الگوی موازیسازی ارباب-کارگر پیشنهاد میگردد. برای مطالعه موردی، شبکه حملونقلی خلاصهشده شیکاگو با 16 پروژه پیشنهادی درنظرگرفته میشود. نتایج موازیسازی بر روی خوشهای از 8 هسته پردازشی نشاندهنده آن است که الگوریتمهای موازی میتوانند ظرف مدت زمان 4000 ثانیه به جوابهایی با کیفیت بالا دست پیدا کنند، درحالیکه همین دستیابی برای الگوریتمهای تکهستهای در مدت 10000 ثانیه اتفاق میافتد. از سه اجرای موازی، در دومورد الگوریتم موازی کلونی مورچگان به جواب دقیق مساله دست مییابد، و در مورد دیگر به جوابی با 07/0 درصد خطا همگرا میشود. عملکرد موازی الگوریتم کلونی مورچگان، همچنین با الگوریتم شاخهوکرانه مقایسه میشود. این مقایسه نشان میدهد که الگوریتم موازی شاخهوکرانه به بیش از 32000 ثانیه زمان اجرا برای یافتن جواب دقیق مساله نیاز دارد، درحالیکه الگوریتم موازی کلونی مورچگان عملکرد بسیار سریعتری را نشان میدهد. | ||
| Keywords | ||
| طراحی شبکه گسسته حملونقل; الگوریتم کلونی مورچگان; محاسبات موازی; الگوی ارباب-کارگر | ||
| References | ||
|
| ||
|
Statistics Article View: 369 PDF Download: 68 |
||
| Number of Journals | 45 |
| Number of Issues | 2,171 |
| Number of Articles | 24,674 |
| Article View | 24,447,983 |
| PDF Download | 17,555,117 |