1403/07/19
امیر علی زرین مهر

امیر علی زرین مهر

مرتبه علمی: استادیار
ارکید:
تحصیلات: دکترای تخصصی
اسکاپوس:
دانشکده: دانشکده مهندسی و فناوری
نشانی:
تلفن: 011-35302903

مشخصات پژوهش

عنوان
موازی سازی الگوریتم کلونی مورچگان در طراحی شبکه گسسته حمل و نقل
نوع پژوهش
مقاله چاپ شده
کلیدواژه‌ها
طراحی شبکه گسسته حمل ونقل، الگوریتم کلونی مورچگان، محاسبات موازی، الگوی ارباب-کارگر
سال 1394
مجله مهندسي عمران مدرس
شناسه DOI
پژوهشگران امیر علی زرین مهر ، مرتضی پرویزی عمران ، یوسف شفاهی ، سیداحسان سیدابریشمی

چکیده

طراحی شبکه گسسته حمل ونقل عبارت است از انتخاب زیرمجموعه ای امکان پذیر از پروژه ها (بزرگراه ها)ی پیشنهادی در یک شبکه حمل ونقل به منظور کمینه سازی زمان سفر کل کاربران شبکه. این مساله در کلاس پیچیدگی مسائل NP-Hard قرار دارد که هیچ الگوریتم موثری برای حل دقیق آنها در مقیاس بزرگ وجود ندارد. ازاین رو بیشتر مطالعات انجام گرفته، به منظور یافتن جوابی نسبتا خوب در مدت زمانی معقول، از طریق رویکردهای ابتکاری و فراابتکاری به مساله پرداخته اند. اما راه دیگری که همچنان برای افزایش سرعت رویکردهای حل مساله وجود دارد، محاسبات موازی است. مقاله پیش رو، در پی بررسی کاربرد محاسبات موازی در یک الگوریتم فراابتکاری در مساله طراحی شبکه گسسته حمل ونقل است. در این مقاله، یک الگوریتم موازی کلونی مورچگان، بر مبنای مطالعه پورزاهدی و ابوالقاسمی، با الگوی موازی سازی ارباب-کارگر پیشنهاد می گردد. برای مطالعه موردی، شبکه حمل ونقلی خلاصه شده شیکاگو با 16 پروژه پیشنهادی درنظرگرفته می شود. نتایج موازی سازی بر روی خوشه ای از 8 هسته پردازشی نشان دهنده آن است که الگوریتم های موازی می توانند ظرف مدت زمان 4 هزار ثانیه به جواب هایی با کیفیت بالا دست پیدا کنند، درحالی که همین دستیابی برای الگوریتم های تک هسته ای در مدت 10 هزار ثانیه اتفاق می افتد. نتایج نشان می دهند که در دو مورد از سه اجرا، الگوریتم موازی کلونی مورچگان به جواب دقیق مساله دست می یابد، و در مورد دیگر به جوابی با 07/0 درصد خطا نسبت به جواب دقیق همگرا می شود. عملکرد موازی الگوریتم کلونی مورچگان، همچنین در کنار الگوریتم شاخه وکرانه موازی گزارش خواهدشد. این گزارش نشان می دهد که الگوریتم موازی شاخه وکرانه، در مثال مورد نظر، به زمان بسیارزیادی، بیش از 32 هزار ثانیه، برای یافتن جواب دقیق مساله احتیاج دارد. البته قضاوت و مقایسه کلی، در خصوص رفتار الگوریتم های یادشده به اجراهای بیشتر بر روی شبکه های گوناگون نیازمند است.