این سایت در حال حاضر پشتیبانی نمی شود و امکان دارد داده های نشریات بروز نباشند
مهندسی عمران مدرس، جلد ۱۵، شماره ۲، صفحات ۳۷-۵۰
عنوان فارسی موازی سازی الگوریتم کلونی مورچگان در طراحی شبکه گسسته حمل و نقل
چکیده فارسی مقاله طراحی شبکه گسسته حمل‌ونقل عبارت است از انتخاب زیرمجموعه‌ای امکان‌پذیر از پروژه‌ها (بزرگراه‌ها)ی پیشنهادی در یک شبکه حمل‌ونقل به منظور کمینه‌سازی زمان سفر کل کاربران شبکه. این مساله در رده مسائل NP-Hard است که هیچ الگوریتم موثری برای حل دقیق آنها در مقیاس بزرگ وجود ندارد. ازاین‌رو بیشتر مطالعات انجام‌گرفته، به منظور یافتن جوابی نسبتا خوب در مدت زمانی معقول، ‌از طریق رویکردهای ابتکاری و فراابتکاری به مساله پرداخته‌اند. اما راه دیگری که همچنان برای افزایش سرعت رویکردهای حل مساله وجود دارد، محاسبات موازی است. مقاله پیش‌رو، به بررسی کاربرد محاسبات موازی در یک الگوریتم فراابتکاری در مساله طراحی شبکه گسسته حمل‌ونقل می‌پردازد. در این مقاله، یک الگوریتم موازی کلونی مورچگان، بر مبنای مطالعه پورزاهدی و ابوالقاسمی، با الگوی موازی‌سازی ارباب-کارگر پیشنهاد می‌گردد. برای مطالعه موردی، شبکه حمل‌ونقلی خلاصه‌شده شیکاگو با 16 پروژه پیشنهادی درنظرگرفته می‌شود. نتایج موازی‌سازی بر روی خوشه‌ای از 8 هسته پردازشی نشان‌دهنده آن است که الگوریتم‌های موازی می‌توانند ظرف مدت زمان 4000 ثانیه به جواب‌هایی با کیفیت بالا دست پیدا کنند، درحالی‌که همین دستیابی برای الگوریتم‌های تک‌هسته‌ای در مدت 10000 ثانیه اتفاق می‌افتد. از سه اجرای موازی، در دومورد الگوریتم موازی کلونی مورچگان به جواب دقیق مساله دست می‌یابد، و در مورد دیگر به جوابی با 07/0 درصد خطا همگرا می‌شود. عملکرد موازی الگوریتم کلونی مورچگان، همچنین با الگوریتم شاخه‌وکرانه مقایسه می‌شود. این مقایسه نشان می‌دهد که الگوریتم موازی شاخه‌وکرانه به بیش از 32000 ثانیه زمان اجرا برای یافتن جواب دقیق مساله نیاز دارد، درحالی‌که الگوریتم موازی کلونی مورچگان عملکرد بسیار سریع‌تری را نشان می‌دهد.
کلیدواژه‌های فارسی مقاله
عنوان انگلیسی Parallelization of Ant Colony Algorithm in Transportation Discrete Network Design
چکیده انگلیسی مقاله Transportation Discrete Network Design Problem (TDNDP) is defined as the problem of selecting a subset of proposed projects (i.e. new highways) for construction, while holding the budget constraint, so as to minimize the total travel time of the network users. TDNDP has been often known as a problem with the bi-level programming formulation. At the upper level, this formulation allows for finding the optimal selection of the projects, while taking into account the route choice behavior of network users at its lower level. Such a formulation falls into the category of problems in the NP-Hard complexity class. These are resource-intensive problems which have not been exactly solved yet with any efficient algorithms. As a result, the main body of TDNDP related literature has ignored the exact solution of the problem and addressed TDNDP through heuristic and meta-heuristic approaches. These approaches contribute to find a rather high quality solution in a reasonable amount of time. Using heuristic and meta-heuristic algorithms is one way to overcome the complexity of NP-Hard problems like TDNDP. However, application of parallel computing still remains as another way to speed up the performance of such algorithms. Parallel computation aims at harnessing multiple computing resources, e.g. computer processors, to solve a certain problem. Different parallelization paradigms have been developed so far to parallelize solution algorithms. These paradigms generally address the two fundamental questions of how and when the required information should be exchanged among the processors. A master-slave (MS) parallelization paradigm is one of the basic paradigms in which one processor, namely the master, holds the main information of the problem. The master generates new jobs whenever needed, distributes them among other processors (i.e. slaves), and exploits them to work on the sent jobs. This paper is going to explore the application of parallel computation in a meta-heuristic algorithm in TDNDP. A parallel Ant Colony Algorithm (ACA), based on the study of Poorzahedy and Abulghasemi, is proposed with the MS parallelization paradigm. The Chicago Sketch transportation network is considered as a case study with 16 bi-directional proposed projects. The results are reported in three runs over a cluster of 8 processing cores for both single-core and parallel ACAs. According to the performances observed in this paper, parallel algorithms can achieve high quality solutions in 4000 seconds, while this happens for the single-core algorithms in 10000 seconds. The parallel ACA finds the exact solution of the problem in two instances out of three runs and in the other instance it converges to a solution with 0.07 percent error from the exact solution. The parallel performance of ACA is also reported along with that of the branch and bound algorithm. It is observed that the parallel branch and bound algorithm requires more than 32000 seconds running time to find the exact solution of the problem. More accurate comparisons, however, can only be achieved by running the single-core and parallel ACAs more than the three times used in this paper.
کلیدواژه‌های انگلیسی مقاله
نویسندگان مقاله امیرعلی زرین مهر |
دانشگاه تربیت مدرس
سازمان اصلی تایید شده: دانشگاه تربیت مدرس (Tarbiat modares university)

مرتضی پرویزی |
دانشکده فنی دانشگاه تهران
سازمان اصلی تایید شده: دانشگاه تهران (Tehran university)

یوسف شفاهی |
دانشکده مهندسی عمران و محیط زیست دانشگاه صنعتی شریف
سازمان اصلی تایید شده: دانشگاه صنعتی شریف (Sharif university of technology)

سید احسان سیدابریشمی | seyed ehsan سیدابریشمی
دانشکده مهندسی عمران و محیط زیست دانشگاه تربیت مدرس
سازمان اصلی تایید شده: دانشگاه تربیت مدرس (Tarbiat modares university)

نشانی اینترنتی http://mcej.modares.ac.ir/article_12846_c514215c56e6df0d52f499a18b304273.pdf
فایل مقاله اشکال در دسترسی به فایل - ./files/site1/rds_journals/1242/article-1242-225411.pdf
کد مقاله (doi)
زبان مقاله منتشر شده fa
موضوعات مقاله منتشر شده
نوع مقاله منتشر شده
برگشت به: صفحه اول پایگاه   |   نسخه مرتبط   |   نشریه مرتبط   |   فهرست نشریات