پایان نامه بهینه سازی مسیر جا به جایی در شبكه های شهری با استفاده از الگوریتم مورچگان در گراف های جهت دار

پایان نامه بهینه سازی مسیر جا به جایی در شبكه های شهری با استفاده از الگوریتم مورچگان در گراف های جهت دار

چکیده

یافتن مسیر بهینه از میان مسیرهای موجود یکی از م̂سائل پای̂Oه ای در برنام̂ه ری̂زی ش̂بکه حمل و نقل می باشد که می تواند کاربردهای وسیعی در هدایت هوشمند ترافیک شلوی · م̂سیریابی اتوماتیک وسائل نقلیه · برنامه ریزی تجهیزات ترافیکی و ... داشته باشد. این م̂سأله ب̂ا زی̂اد ش̂دن تعداد ایستگاه ها و مسیرهای ارتباطی آنها تبدیل به یک مسأله پیچیده می گردد که حل آن با اس̂تفاده از روش های شمارشی و سایر روش های مستقیم مستلزم پردازش حجم عظیم̂ی از داده ه̂ا خواه̂د بود. جهت دار بودن مسیرها و وجود گره های بن بست · حل مسأله را با پیچیدگی های دیگری مواجه می سازد. در این مسأله عامل تصمیم گیر باید از میان کلیه حالات امکان پذیر· حالتی را انتخاب نماید که بهترین کارآئی را برای شبکه تأمین کند. به عب̂ارت دیگ̂ر مجم̂وع اوزان ن̂سبت داده ش̂ده ب̂ه مسیرها (بسته به معیار انتخاب ) کمینه یا بیشینه گردد. این معیارها می تواند شامل م̂سافت · زم̂ان · هزینه و یا ترکیبی از آنها باشد. 

مقدمه

حمل و نقل در تمامی کشورهای جهان یکی از ارکان توسعه ی̂افتگی ب̂ه ش̂مار م̂ی رود و تأثیری که حمل و نقل بر سایر صنایع دارد انکارناپذیر است . تأثیر حمل و نقل ب̂ر اقت̂صاد· مح̂یط زیست و نیز اثر بخشی عم̂ده آن ب̂ر می̂زان رض̂ایت عم̂ومی ب̂ه گون̂ه ای اس̂ت ک̂ه ج̂ستجوی روش هایی برای هرچه بهتر کردن سیستم های حمل و نقل را اجتناب ناپذیر می نماید. 

پژوهش استاتزل و هوس [٢٧]

این پژوهش به معرفی الگوریتم سیستم مورچه ای بیش – ک̂م ̧cMMAS( e) م̂Oی پ̂Oردازد. در این مطالعه پژوهش گران ابتدا به تاریخچه الگوریتم های بهینه سازی کلونی مورچه ه̂ا نظی̂ر ACS و AS اشاره می کند و کاربرد این الگوریتم ها و نتایج محاس̂باتی آن ه̂ا ب̂ر روی م̂سئله TSP و QAP بیان می کنند. سپس با بر شمردن نقاط قوت و ضعف این الگ̂وریتم ه̂ا ب̂ه معرف̂ی الگ̂وریتم خ̂ود می پردازند.

فهرست مطالب

چکیده ................................................................................................................................................الف

پیشگفتار ............................................................................................................................................۱ 

فصل ۱‐ کلیات

۱ !۱! مقدمه ...........................................................................................................................۴

۱!۲! تعریف مسأله ...............................................................................................................۶

۱!۳! هدف تحقیق ................................................................................................................۸

۱!۴! روش تحقیق ................................................................................................................۸

۱!۵! فرضیات تحقیق ...........................................................................................................۹

فصل ۲‐ مروری بر ادبیات موضوع

۲ !۱! مقدمه ..........................................................................................................................̈۱y

۲ !۲! الگوریتم مورچه ها......................................................................................................۱۱

۲ !۳! شرح مختصر مفهوم سیستم مورچه ای (AS) .............................................................۱۲

۲ !۴! مروری بر پژوهش های پیشین ....................................................................................۱۳

۲ !۵! جمع بندی ...................................................................................................................̈۳y 

فصل ۳‐ روش های بهینه سازی

۳ !۱! مقدمه ........................................................................................................................۳۲

۳ !۲! مفاهیم بهینه سازی .......................................................................................................۳۳

۳ !۳! بررسی روش های بهینه سازی .....................................................................................۳۴ 

فصل ۴‐ بررسی دقیق الگوریتم ACS به عنوان الگوریتم مرجع

۴ !۱! مقدمه ........................................................................................................................۳۷

۴ !۲! قواعد گذار در ACS .................................................................................................۳۹

۴ !۳! قواعد بروز رسانی .....................................................................................................̈۴y

۴ !۴! تنظیم پارامترها در ACS ............................................................................................۴۲

۴ !۵! رفتار فرومون و ارتباط آن با کارآئی سیستم ..............................................................۴۳

۴ !۶! همکاری بین مورچه ها ..............................................................................................۴۵

۴ !۷! اهمیت فرومون و تابع ابتکاری .................................................................................۴۸

۴ !۸! مقایسه ACS با سایر روش های ابتکاری ...................................................................۴۹

فصل ۵‐ شرح الگوریتم پیدا کردن مسیر بهینه با استفاده از ACS

۵ !۱! مقدمه ........................................................................................................................۵۱

۵ !۲! کلیاتی در باره الگوریتم طرح شده و روش شرح .....................................................۵۲

۵ !۳! شرح الگوریتم ...........................................................................................................۵۳ 

فصل ۶‐ تعیین مقادیر پارامترها و تحقیق اعتبار اصلاحات

۶ !۱! مقدمه ........................................................................................................................۷۲

۶!۲! تعیین مقدار بهینه مورچه ها .......................................................................................۷۳

۶ !۳! تعیین پارامتر B .........................................................................................................۷۵

۶ !۴! بررسی اثر همکاری مورچه ها دریافتن مسیر بهینه ....................................................۷۸

۶ !۵! بررسی اثرات تابع مسافت در یافتن مسیر بهینه ........................................................۸۱

۶!۶! مقای̂OOسه روش اس̂OOتفاده از نزدی̂OOکت̂OOرین هم̂OOسایگی و روش اس̂OOتفاده از

نزدیکترین نقطه به مقصد .......................................................................................۸۲

۶!۷! مقای̂OOسه روش ج̂OOای گ̂OOذاری مورچ̂OOه ه̂OOا در مب̂OOداء و مق̂OOصد ب̂OOا روش

جای گذاری در مبداء .................................................................................................۸۳ 

فصل ۷‐ نتیجه گیری و پیشنهاد برای مطالعات آتی

۷ !۱! جمع بندی نتایج ........................................................................................................۸۶

۷ !۲! پیشنهاد برای مطالعات آتی .........................................................................................۸۷ 

فهرست منابع و مآخذ .....................................................................................................................۸۹

ضمیمه ۱! متن ورودی برنامه ........................................................................................................۹۲

ضمیمه ۲! نحوه کار با نرم افزار ....................................................................................................۱۱۹ì