استفاده از الگوریتم کلونی مورچه گان برای یافتن سریع کوتاه ترین مسیر در گراف های جهت دار فازی با وزن های مختلف

مساله یافتن کوتاه ترین مسیر از یک مبدا مشخص به یک مقصد مشخص از شناخته شده ترین مسایل بهینه سازی به شمار می رود. در چند دهه ی گذشته به خاطر کاربردهای فراوان آن در مسایلی مانند مسیریابی، مخابرات و حمل و نقل بسیاری از توجهات را به خود جلب کرده است. در دنیای واقعی طول هر یال در یک شبکه ممکن است بیانگر فاصله، زمان یا هزینه باشد. از آنجایی که در عمل از عدم قطعیت نمی توان اجتناب کرد، معمولا به یال ها، نمی توان مقدار قطعی تخصیص داد. بنابراین استفاده از اعداد فازی برای طول یال ها لازم به نظر می رسد. در این مقاله قصد داریم تا با استفاده از الگوریتم کلونی مورچه گان به عنوان یک روش بهینه سازی فرا ابتکاری مسیله ی یافتن کوتاه ترین مسیر را سریعتر از کارهای گذشته حل نماییم. طول هر مسیر از جمع تک تک یال های آن مسیر بدست می آید. از آنجایی که در این مسیله یال های فازی از انواع مختلفی هستند پس برای جمع آنها از روش جمع تقریبی و برای رتبه بندی مسیرها نیز از روش Dpq استفاده خواهد شد. برای انجام پیاده سازی دو گراف با پیچیدگی های متفاوت در نظر گرفته شده است. نتایج حاصل از پیاده سازی را با نتایج مقالات اخیرا منتشر شده در این حوزه، که از الگوریتم های ژنتیک، الگوریتم بهینه سازی اجتماع پرندگان و الگوریتم کلونی زنبور عسل مصنوعی استفاده کرده اند، مقایسه می کنیم. نتایج حاصل از پیاده سازی نشان داده است که الگوریتم کلونی مورچه گان توانسته در زمانی حدود 50 ٪ کوتاهتر نسبت به الگوریتم های ذکر شده همگرا شود و زمان اجرای بسیار سریعتری نسبت به آن الگوریتم ها داشته باشد.

Keywords:

مسیله ی کوتاه ترین مسیر , الگوریتم کلونی مورچه گان , اعداد فازی , بهینه سازی , گراف های جهت دار فازی