یافتن کوتاهترین مسیر شبکه با استفاده از الگوریتم بهینه سازی فاخته در سیستم اطلاعات مکانی
نویسنده:
چکیده:
امروزه مسیریابی در شبکه های شهری با افزایش حجم اتومبیل ها و نیز محدودیت های ترافیکی گوناگون امری ضروری محسوب می شود. روشی که در این پژوهش به منظور حل مساله کوتاهترین مسیر برای نخستین بار پیشنهاد شده است، استفاده از الگوریتم بهینه سازی فاخته می باشد. علت انتخاب این الگوریتم، جدید بودن و نیز پاسخ مناسبی است که این الگوریتم برای حل مساله مسیریابی، نسبت به سایر الگوریتمهای فراابتکاری داده است. در این راستا و برای انجام مسیریابی، با ایجاد تغییراتی در نسخه دودویی الگوریتم فاخته، از الگوریتم یاد شده استفاده گردید. بدین منظور، برای ایجاد جمعیت اولیه از یک روش کنترل شده استفاده شد، که از ایجاد جمعیت های تصادفی که درصد بسیار ناچیزی از آنها ممکن است مسیری را تشکیل دهند، جلوگیری می کند. به این صورت که متغیرهای جمعیت که در واقع همان نقاط شبکه و موقعیت های فاخته ها هستند، به صورت تصادفی انتخاب نشده بلکه به صورت کنترل شده انتخاب می شوند و انتخاب نقاط بعدی از میان نقاطی است که با نقطه مورد نظر ارتباط دارند. در تمام مراحل اجرای الگوریتم، موقعیت فاخته ها به صورت اعداد باینری درمی آیند و اگر نقطه ای در مسیر حضور داشته باشد عدد یک و در غیر اینصورت عدد صفر می گیرد. در فاز مهاجرت فاخته ها نیز، از یک تابع سیگموید استفاده شده است که موقعیت جدید فاخته ها را به بازه ی بین صفر و یک برده و در نتیجه موقعیت های جدید نیز تبدیل به اعداد صفر و یک می شوند. به منظور آزمون میزان کارایی الگوریتم پیشنهادی، از سه نوع شبکه فرضی، محلی و واقعی استفاده شده است. نتیجه اجرای این الگوریتم در دو نوع شبکه فرضی و محلی با تعداد نقاط 20 و 31، نتیجه ای مشابه یک الگوریتم قطعی بود، اما در شبکه ای که بخشی از یک شبکه شهری واقعی بود و از 617 نود و 995 یال تشکیل شده بود، با اختلاف اندکی بهتر از الگوریتم قطعی، توانست مسیر بهینه را نشان دهد. نتایج حاصله نشان داد که این الگوریتم توانایی انجام مسیریابی در شبکه را دارا می باشد و با ایجاد تغییراتی بر اساس ساختار شبکه، می تواند برای داده های بزرگ و شبکه های واقعی شهری مورد استفاده قرار گیرد.
کلیدواژگان:
زبان:
فارسی
صفحات:
231 تا 239
لینک کوتاه:
magiran.com/p1702277
دانلود و مطالعه متن این مقاله با یکی از روشهای زیر امکان پذیر است:
اشتراک شخصی
با عضویت و پرداخت آنلاین حق اشتراک یکساله به مبلغ 1,390,000ريال میتوانید 70 عنوان مطلب دانلود کنید!
اشتراک سازمانی
به کتابخانه دانشگاه یا محل کار خود پیشنهاد کنید تا اشتراک سازمانی این پایگاه را برای دسترسی نامحدود همه کاربران به متن مطالب تهیه نمایند!
توجه!
- حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران میشود.
- پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانههای چاپی و دیجیتال را به کاربر نمیدهد.
In order to view content subscription is required
Personal subscription
Subscribe magiran.com for 70 € euros via PayPal and download 70 articles during a year.
Organization subscription
Please contact us to subscribe your university or library for unlimited access!