بخشی از مقاله
چکیده طراحی شبکه گسسته حمل و نقل عبارت است از انتخاب زیرمجموعه ای امکان پذیر از پروژه های پیشنهادی در یک شبکه حمل و نقل به منظور کمینه سازی زمان سفر کل کاربران شبکه . این مسئله در کلاس پیچیدگی مسائل NP-Hard قرار دارد که هیچ الگوریتم موثری برای حل دقیق آنها در مقیاس بزرگ وجود ندارد . مقاله پیش رو در پی بررسی و کاربرد یک الگوریتم فراابتکاری در مساله طراحی شبکه گسسته حمل و نقل است . در این مقاله نکاتی جهت اجرای بهتر الگوریتم کلونی مورچگان پیشنهاد می شود . به نظر می رسد با رعایت موارد گفته شده در مقاله سرعت و زمان اجرای الگوریتم بهبود پیدا کند .البته قضاوت و مقایسه کلی ، در خصوص رفتار الگوریتم و موارد مطرح شده در مقاله به اجرای بیشتر بر روی شبکه های گوناگون نیازمند است .
مقدمه
مجموعه مسائل طراحی شبکه شامل دسته وسیعی از مسائل زیربنایی ، در حوزه برنامه ریزی حمل و نقل ، مخابرات ، صنایع ، و علوم نظامی است . این مسائل ، به شکل معمول با یک گراف ، به عنوان نمادی از شبکه ، نمایش داده می شوند که دارای تعدادی گره و یال جهت دار یا بدون جهت است و هریک از یال ها ، خصوصیاتی همچون طول ، ظرفیت و هزینه را به همراه دارند . هدف مسائل طراحی شبکه انتخاب تعدادی یال در گراف به منظور ساخت یا توسعه ظرفیت است ، به گونه ای که نتیجه خاصی همچون کمینه سازی هزینه انتقال تقاضای بین مبدا و مقصدها تامین شود . مقاله پیش رو از میان مجموعه مسائل طراحی شبکه ، بر روی طراحی شبکه گسسته حمل و نقل به عنوان یک مساله تصمیم گیری زیر ساختی متمرکز می شود .
به طور خاص مسائل طراحی شبکه گسسته حمل و نقل را می توان به صورت انتخاب زیرمجموعه ای امکان پذیر از پروژه های پیشنهادی ساخت بزرگراه در یک شبکه بزرگراهی حمل و نقل به منظور دستیابی به هدفی مشخص تعریف کرد . این هدف به طور معمول کمینه سازی کل زمان سفر کاربران از شبکه است . اغلب مسائل طراحی شبکه، از جمله مسئله طراحی شبکه گسسته حمل و نقل ، مسائلی ترکیبی در رده پیچیدگی NP-Hard هستند ، که دستیابی به جواب دقیق آنها در نمونه های بزرگ ناممکن است . برای حل اینگونه مسائل ترکیبی در مقیاس واقعی دو رویکرد اساسی می تواند مورد توجه قرار گیرد :
· استفاده از الگوریتم های ابتکاری - فراابتکاری
· بهره گیری از محاسبات موازی
اگرچه در برنامه ریزی حمل و نقل تاکنون پژوهش های فراوانی با استفاده از الگوریتم های ابتکاری - فراابتکاری به مساله طراحی شبکه گسسته حمل و نقل پرداخته اند ، اما روش پیش رو نیز راهی جدید جهت حل بهتر این گونه مسائل را ارائه داده است . این مطالعه با توجه به ضرورت حل مسائل بزرگ طراحی شبکه ، به دنبال بررسی حل مساله یاد شده از طریق الگوریتم کلونی مورچگان است.
روش تحقیق - فونت - B Nazanin اندازه - 12 پررنگ -
پژوهش های پیشین به شکل نظری نشان داده اند که مساله طراحی شبکه گسسته حمل و نقل ، حتی در ساده ترین شکل آن - با فرض خطی بودن مسائل سطوح بالا و پایین - به لحاظ پیچیدگی در رده مسائل NP-Hard قرار دارد . از این رو ، بیشتر مطالعات اخیر از حل دقیق این مسئله چشم پوشی کرده ، به راه حل های ابتکاری - فراابتکاری روی آورده اند . الگوریتم های فرا ابتکاری ، اگرچه هرگز تضمینی برای بهینگی جواب خود ارائه نمی دهند ، اما همواره به صورت راهی برای به دست آوردن جواب های نسبتا خوب در مدت زمانی معقول مطرح است .
تاکنون الگوریتم های فراابتکاری فراوانی همچون ژنتیک ، جستجوی ممنوعه ، گرم و سرد کردن شبیه سازی شده ، کلونی مورچگان و اجتماع ذرات در حل مسئله طراحی شبکه حمل و نقلی به کار گرفته شده اند . در الگوریتم کلونی مورچگان ، ارائه شده به وسیله آقایان پورزاهدی و ابوالقاسمی ، تعداد K مورچه - برابر با تعداد پروژه های مورد انتخاب - هریک به طور تصادفی بر مبنای احتمالات حاص از دید پذیری و فرمون گذاری ، زیرمجموعه ای امکان پذیر از پروژه ها را برگزیده و جواب بدست آمده را با حل یک مساله تخصیص ترافیک ارزیابی می کنند .
سپس نتایج ارزیابی مورچگان از طریق افزایش سطح فرمون و احتمال انتخاب در پروژه های دارای جواب برتر ، الگوریتم را بسوی انتخاب پروژه های برتر - دارای فرمون و دیدپذیری بیشتر - هدایت می کند . این روند تاجایی ادامه پیدا می کند که در عملکرد الگوریتم رفتار توقف مشاهده شود . در این شرایط ، آقایان پورزاهدی و ابوالقاسمی ، با تغییر مصنوعی فرمون گذاری به نفع پروژه های ضعیف - دارای فرمون کمتر - ، حرکت الگوریتم را به سوی فرار از توقف در جواب های بهینه سوق می دهند.
محاسبات موازی
به شکل کلی به استفاده همزمان از چندین منبع محاسباتی در حل یک مساله ، محاسبات موازی گفته می شود ، که منظور از منبع محاسباتی در این تعریف ، بیشتر هسته های پردازشی رایانه ها است . محاسبات موازی یا چند هسته ای ، در مقابل محاسبات ترتیبی یا تک هسته ای ، قرار می گیرد که به طور سنتی رواج داشته است . در محاسبات تک هسته ای عملیات محاسبات ، نه به طور همزمان ، بلکه به ترتیب ، یکی بعد از دیگری با گذشت زمان و هزینه قابل توجه انجام می گرفته است . نیاز به صرفه جویی و زمان و هزینه ، به علاوه ضرورت حل مسائل محاسباتی بزرگ ، موجب شد تا در دهه های اخیر ، طراحی الگوریتم های موازی با اقبال گسترده ای روبرو شود .
الگوهای گوناگونی برای طراحی یک الگوریتم به طور موازی وجود دارد که در یک طبقه بندی کلی می توان این الگوها را ناشی از پاسخ به دو پرسش دانست :
• پردازنده ها چه هنگام با یکدیگر ارتباط برقرار کنند .
