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

مشخصات فایل

مقطع:کارشناسی ارشد
رشته تحصیلی:مهندسی عمران
نوع ارائه:پایان نامه
تعداد صفحات:168
قالب بندی:word قابل ویرایش

نحوه خرید

دانلود رایگان فایل
شما میتوانید تنها با یک کلید به راحتی فایل مورد نظر را دریافت کنید. 🙂

برای دسترسی به این فایل ابتدا باید اشتراک خریداری کنید. برای خرید اشتراک بر روی لینک زیر کلیک کنید.

ارتقاء عضویت

در صورت بروز هر گونه مشکل در روند خرید اینترنتی، بخش پشتیبانی کاربران آماده پاسخگویی به مشکلات و سوالات شما می باشد

چکیده

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

يافتن مسير بهينه از ميان مسيرهاي موجود يكي از مـسائل پايـهاي در برنامـهريـزي شـبكه حمل و نقل ميباشد كه ميتواند كاربردهاي وسيعي در هدايت هوشمند ترافي ك شلوي ، مـسيريابي اتوماتي ك وسائل نقليه، برنامهريزي تجهيزات ترافيكي و… داشته باشد . اين مـسأله بـا زيـاد شـدن تعداد ايستگاهها و مسيرهاي ارتباطي آنها تبديل به ي ك مسأله پيچيده ميگردد كه حل آن با اسـتفاده از روشهاي ش مارشي و ساير روشهاي مستقي م مستلزم پردازش حج م عظيمـي از داده هـا خواهـد بود. جهتدار بودن مسيرها و وجود گرههاي بنبست، حل مسأله را با پيچيدگيهاي ديگري مواجه ميسازد. در اين مسأله عامل تصمي مگير بايد از ميان كليه حالات امكانپذير، حالتي را انتخاب نمايد كه به ترين كارآئي را براي شبكه تأمين كند. به عبـارت ديگـر مجمـوع اوزان نـسبت داده شـده بـه مسيرها (بسته به معيار انتخاب) كمينه يا بيشينه گردد. اين معيارها ميتواند شامل مـسافت ، زمـان ، هزينه و يا تركيبي از آنها باشد.

در اين پاياننامه براي حل مسأله فوقالذكر از ي ك روش فرا ابتكـاري بـر پايـه بهينـهيـابي كولوني مورچهها استفاده شده است. روشهاي كولـوني مورچـههـا مجموعـهاي از الگـوريتمهـاي هوشمند ميباشند كه از رفتار مورچهها در طبيعت الهام ميگيرند. در اين راستا الگـوريتمACS  كـه يكي از الگوريتمهاي اجتماع مورچگان است به عنوان الگوريت م مرجع در نظر گرفته شـده و سـپس اين الگوريتم براي دستيابي به بهترين جوابها در مـسأله كوتـاهتـرين مـسير (يعنـي كمينـه كـردن مسافت هدف مسأله ميباشد) در شبكه جهتدار، اصلاح شده است. الگوريتمACS  پيشتر در حـل مسائلي چون فروشنده دورهگرد و طراحي شبكه نتايج قابل قبولي را ارائه داده اسـت. بـراي ارتقـاء اين الگوريتم در حل مسأله شرح داده شده، بعضي از بخشهاي آن تغيير كرده و بـا الگـوريتمهـاي مناسبتر جايگزين شده است. همچنين پارامترهاي مورد استفاده در اين الگوريتم به منظور دستيابي به نتايج بهتر و كوتاهتر كردن زمان پردازش مجـددﹰا بررسـي شـده و مقـداردهي شـدهانـد . صـحت تغييرات اعمال شده از طريق نتايج به دست آمده از حل مسائل آزمايشي مورد بررسي قـرار گرفتـه است.

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

الهام از طبيعت و نظام حاك م بر آن همواره راهگـشاي حـل بـسياري از مـسائل پيچيـده و دشوار پيشروي بشر بوده اسـت. در دهـههـاي  اخيـر بـا اسـتفاده از الگـوريتمهـاي فـرا ابتكـاري(متاهيوريستي ك١) بسياري از مسائل دشوار رياضي در زماني بسيار كوتاهتر حل شدهاند. بهينهسـازي كولوني مورچهها مجموعهاي از الگوريتمهاي فرا ابتكاري است كه از زندگي طبيعي مورچه ها الهام گرفته شده است. دقت در اين موضوع كه مورچهها تنها اندك زمـاني پـس از يـافتن منبـع غـذائي، همواره كوتاهترين راه را بدست لانه خود پيدا ميكنند، دانشمندان را بر آن داشت تا با تعمق بيـشتر در آن به شبيهسازي اين رفتار بپردازند . بنابراين مورچه هائي مصنوعي به گونه اي طراحي شـدند كـه رفتار مورچههايطبيعي را تقليد نمايند. همچنين حلقه ارتباطي مورچهها يعني مـاده شـيميايي بجـا مانده از مورچه ها (فرومون) نيز به صورت حافظه اي پويا و قابل اصلاح شبيه سازي گشت.

اين روش در حل بسياري از مسائل بهينهيابي كه در زمره مـسائل قـرار دارنـد مورد استفاده قرار گرفته و جوابهاي قابل قبولي با ميزان پردازش كمتر به دست داده است. در اين پاياننامه از الگوريتمACS  كه يكي از الگوريتمهـاي كولـوني مورچگـان اسـت بـراي حـل مـسأله كوتاهترين مسير در شبكهاي جهتدار استفاده شده است. در فصل اول پس از توضـيح مقـدمات و تعريف مسأله ، فرضيات و روش هاي تحقيق مورد اشاره قرار گرفته است.

در فصل دوم پس از ارائه توضيحاتي پيرامون مفهوم كلـي سيـست م مورچـهاي و چگـونگيپيدايش آن به مرور پژوهشهايي كه در اين زمينه صورت گرفته پرداختـه مـيشـود . در ايـن ميـان برخي از الگوريتمها و اصلاحات صورت گرفته به منظور بررسي بيـشتر شـيوه كـار مـورد بررسـي دقيق تر قرار گرفته و در پايان به فهرست كليه تحقيقات مرتبط اشاره شده است.

در فصل سوم روشها و مفاهي م بهينهسازي مـورد بررسـي قـرار گرفتـه و سـعي شـده تـا تفاوتهاي روشهاي ديگر مانند روشهاي شمارشي و غيره با متدهاي هوشمند مورد تحليل قـرار گيرد.

در فصل چهارم به بررسي دقيق و جزء به جـزء الگـوريتمACS  در حـل مـسأله فروشـنده دورهگرد پرداخته شده تا به عنوان مرجعي در پرداختن به مسأله كوتاهترين مسير مورد استفاده قـرار گيرد. در اين فصل قواعد گذار و بروز رسانيهاي محلي و عفوني به طور كامل تـشريح گرديـده و پس از آن چگونگي برآورد مقادير پارامترها و روشهاي مورد استفاده در اين برآوردها آورده شـده است. سپس به ميزان اهميت بخشهاي مختلف الگوريتم و نقشي كـه هـر يـ ك در كـارآئي دارنـد پرداخته ميشود. رفتار فرومون و ارتباط آن با كارآئي سيست م و نقش آن در همكـاري مورچـههـا  و نيز مقايسه نقش فرومون و تابع ابتكاري قسمتهائي از اين فصل مـيباشـند . در آخـر نيـز كـارآئي روش  ACS با ساير روش هاي ابتكاري مقايسه شده است.

فصل پنج م بخش اصلي پايان نامه ميباشد و در آن روش حل مسأله با استفاده از الگوريتم پيشنهادي به صورت گام به گام تشريح ميگردد. در اين فصل سـعي شـده اسـت ضـمن پرهيـز از تكرار كليات الگوريتمACS  كليه اصلاحات و اضافات انجام شده مطرح گـردد. الگـوريتم خلاصـه شده حل مسأله در انتهاي فصل آورده شده است.

در فصل ششم كليه ادعاهاي مطرح شده در فصل۵ از طريق نتايج بدست آمده از نرم افزارتحقيق مي گردد. همچنين پارامترهاي در نظر گرفته شده نيز با توجه به تغيير صورت مسأله ، مـورد بازبيني مجدد قرار گرفته و مقاديري براي آن پيشنهاد ميگردد. نتايج ارائه شده در اين فصل از حـلمسائل گوناگون حاصل ميگردد. و سعي بر ايـن بـوده تـا عملكـرد الگـوريتم در مـورد مـسائل بـا چيدمان منظ م تصادفي مورد بررسي قرار گيرد.

در فصل هفتم نيز ضمن نتيجهگيري از كليه نتايج حاصله پيـشنهاداتي بـراي ادامـه تحقيـق ارائه شده است. همچنين اين پايان نامه داراي دو پيوست ميباشد. در پيوست اول متن كـد ورودي برنامه عينﹰا آورده شده است. اين برنامه در محيط ويژوال بيـسي ك(Visual Basic)  ويـرايش۶ كـد نويسي شده است. همچنين لوح فشرده حاوي فايل ايـن برنامـه نيـز بـه پيوسـت پايـان نامـه ارائـه مي گردد.

ضميمه دوم در حقيقـت راهنمـاي اسـتفاده از برنامـه مـيباشـد و در آن نحـوه تعريـف وبازخواني شبكهها، انتخاب نقاط مبداء و مقصد، تعريف مسيرهاي يـ ك و دو طرفـه، تعيـين مقـاديرپارامترها، چگونگي اعمال يا عدم اعمال اصلاحات ، مشاهده و مقايسه نتايج و مرور نتايج از طريق مشاهده نمودار توضيح داده شده است.   در اينجا لازم است مراتب تشكر خود را نسبت به استادان گرامي و ارجمند دكتـر رعايـتصنعتي، دكتر افندي زاده، دكتر سيد حسيني و نيز ساير كساني كـه مـرا در گـردآوري ايـن مطالـب ياري نموده اند، ابراز دارم.

فصل ۱ کلیات

۱ !۱! مقدمه ……………………………………………………………………………………………………………۴

حمل و نقل در تمامي كشورهاي جهان يكي از اركان توسعه يـافتگي بـه شـمار مـيرود و تأثيري كه حمل و نقل بر ساير صنايع دارد انكارناپذير است. تأثير حمل و نقل بـر اقتـصاد، محـيط زيست و نيز اثر بخشي عمـده آن بـر ميـزان رضـايت عمـومي بـه گونـهاي اسـت كـه جـستجوي روش هايي براي هرچه بهتر كردن سيست م هاي حمل و نقل را اجتناب ناپذير مي نمايد.

يكي از مسائل بسيار مهم در برنامهريزي حمل و نقل تـشخيص و انتخـاب مـسير بهينـه بـراي حمل و نقل كالا و يا مسافر است. مفهوم مسير بهينه با توجه به هدف مورد نظر  ميتواند متفاوت باشـد . اگر در بسياري از موارد حداقل كردن زمان سفر مهمترين فاكتور در بالا بردن مطلوبيت به شمار ميرود، كاهش هزينه و به حداقل رساندن آن عامل اصلي در گروه ديگري از انتخاب ها ميباشـد . در ايـن ميـان تشخيص كوتاهترين مسير موجود بين مبدأ و مقصد با در نظر گرفتن كليه محدوديتها و ممنوعيـتهـا مي تواند گام مهمي در تعيين مسير بهينه در ميان آلترناتيوهاي موجود باشد.

مسأله انتخاب كوتاهترين مسير در نگاه اول با توجه به ساختار قابل درك و تابع هدف روشن آن ممكن است چندان پيچيده به نظر نرسد. اما با گسترش روز افزون شبكههاي درون شهري و برون شهري، براي انتخاب مسير با چنان حجمي از گزينهها مواجه خواهيم بود كه يافتن راه حل بهينه و يـا نزديـ ك بـه بهينه جز با استفاده از روش هاي هدف دار پردازشي و پردازشگر هاي توانمند امكان پذير نخواهد بود.

بر اساس تحقيقاتي كه در علوم طبيعي صورت گرفته به اثبات رسيده است كه مورچههـاي طبيعي قادر هستند كوتاهترين مسير را از ي ك منبع غذا تا آشيانه خود بدون استفاده از قدرت بينايي بيابند. در اين خصوص دو طبيعي دان به نامهاي ويلسون  و ايلدابلر٣ در سال ۱۹۹۰ اثبات كردند كه مورچههاي طبيعي از قدرت بينايي خود براي مسيريابي استفاده نميكنند. ضمنﹰا محققان بـسياري از سالها پيش اعتقاد داشتند كه مورچههاي طبيعي، كوتاهترين مسير را براي انتقال مواد از منبع غذا به آشيانه طي ميكنند كه از آن جمله پاستيلز و دنهبـورگ ٤ در سـال ۱۹۸۹ و آرون و گـاس٥ در سـال۱۹۹۲ مي توان نام برد [۱].

بر اساس اين رفتار غريزي مورچههاي طبيعي، در حوزه علوم بر پايه طبيعت٦ الگوريتمي ابداع شده است كه قابليتهاي بسياري در حل مسائل مشكلساز رياضي عرضه كـرده اسـت. ايـن الگـوريتم براي او لين بار توسط دانشمندي به نام دريگو٧ در سال۱۹۹۱ تحت عنوان”الگـوريتم مورچگـان 8(AA) معرفي شد . اين محقق در پايان نامه دكتراي خود اصول اين الگوريتم را بنـا نهـاد و سـپس در مقـالات خود، مسير گام به گام ايـن الگـوريتم و زمينـههـاي كـاربرد آن را تـشريح كـرد. در ايـن روش، رفتـار مورچههاي طبيعي در انتخاب مسير براي مجموعهاي از مورچههاي مصنوعي شبيهسازي ميشـود تـا از اين طريق بتوان به كوتاهترين مسير در شبكه دست يافت. بنابراين مورچههاي مصنوعي مـورد اسـتفاده در الگوريتم مورچگان نيز  ميبايست رفتاري مشابه مورچگان طبيعي داشته باشند.

از مهمترين مزاياي اين گونه روشها اين است كه همان گونه كـه در طبيعـت چنانچـه محـيط پيرامون مورچگان طبيعي تغيير كند، به عنوان مثال مسيري مسدود و يا مسير ديگري ايجـاد شـود، ايـن مورچگان قادرند خود را با شرايط جديد تطبيق داده و كوتاهترين مسير جديد را بيابند (اين موضـوع در تحقيقات دندبورگ و گاس در سال ۱۹۹۲ به اثبات رسيده) اين انعطافپذيري در اين روشها نيـز بـه چشم ميخورد. چنانچه شبكه راههاي ما به هر دليل دچار تغيير شود و مسيرهاي جديد ايجـاد گـردد و يا مسيرهاي قبلـي مـسدود گرديـده و يـا جهـت حركـت مجـاز در آن تغييـر كنـد، بـا اسـتفاده از تصمي م گيري پويا خللي در انتخاب به وجود نخواهد آمد.از سوي ديگر، براي بكارگيري الگوريتم مورچگان در مسائل كاربردي مختلـف لازم اسـت كه با افزودن، حذف يا اصلاح اصول و قوائد الگوريتم، شرايط اسـتفاده از آن فـراهم گـردد. بـدين لحاظ مي بايست درك عميقي نسبت به محيط مسائل كاربردي وجود داشته باشد.  با شباهت دادن مشكل مسيريابي وسايل نقليه به مشكل تعيين مسير مورچگان طبيعي مـي تـوان باكمي تغيير در قوائد الگوريتم مورچگان پاسخهاي مناسبي براي مسئله طرح شده بدست آورد.

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

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

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

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

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

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

در اين فصل روند پژوهشهايي كه در زمينه موضوع تحقيق جاري انجام شده است، مـورد بررسي قرار ميگيرد. براي اين منظور ابتدا توضيح مختصري در باره طبقهبندي و موضـوعات كلـي هريك از اين تحقيقات و نتايج حاصله از آنها ارائه خواهد گشت و سپس فهرستوار به بعـضي از پژوهشهاي مرتبط اشاره ميگردد. ذكر اين نكته حائز اهميت است كـه هريـ ك از تحقيقـات ارائـه شده در اين بخش شرايط و فرضيات خاص خـود را داراسـت و مقايـسه همزمـان ايـن تحقيقـات امكانپذير نخواهد بود. در اين ميان بعضي از تحقيقات موجود، به دليل شباهتها و نزديـ ك بـودن موضوع مورد بحث به تحقيق جاري مورد بررسي و شرح دقيق تري قرار مي گيرند. به عنوان مثال، تحليل روشهاي مختلف حل مسأله فروشنده دورهگرد به دليل شباهت زياد اين مسأله با مسأله مسيريابي بهينه و نيز تلاشهاي گستردهاي كـه بـه منظـور حـل ايـن مـسأله بـا روشهاي مختلف تاكنون صورت پذيرفته است، ميتواند علاوه بر زمينهسازي در جهـت شـناخت روند ارتقاء مرحله به مرحله ي ك الگوريتم، آخرين پيشرفتهاي حاصله در روشهاي حل را نمايان سازد. به طور كلي در تنظي م اين فصل سعي شده كه تا حد امكان خطوط اصلي و آخرين وضـعيت تحقيقات صورت گرفته، معرفي گردد.

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

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

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

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

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

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

بهينه سازي يك فعاليت مهم و تعيين كننده در طراحي ساختاري است. طراحان زماني قـادرخواهند بود طرحهاي بهتري توليد كنند كه بتوانند با روشهاي بهينه سازي در مصرف زمان و هزينه طراحي صرفه جويي كنند . بسياري از مسائل بهينه سازي در مهندسي، طبيعت پيچيده تر و مشكلتـر ازآن هستند كه با روشهاي موسوم بهينه سازي نظير روش برنامه ريزي رياضي و نظاير آن قابـل حـل باشند. از دهه ۱۹۶۰، علاقه به تقليد از طبيعت براي حل مسائل مشكل بهينه سـازي، روبـه افـزايش گذاشته است . الگوريتم ژنتيك، شبكه هاي عصبي، شبيه سـازي آنلينـگ، كلـوني مورچـه هـا و غيـره رويكردهاي برجسته اي هستند كه در سال هاي اخير به سرعت رشد كرده اند.

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

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

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

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

با توجه به اين كه در اين تحقيق از الگوريتم ACS بـه عنـوان الگـوريتم اصـلي در حـل مسأله پيدا كردن مسير بهينه استفاده شده است. ضروري است كه مباني و ويژگيهاي اين الگـوريتم و نيز نحوه و روش مقداردهي به پارامترها و مقادير اوليه متغيرها تشريح گردد. از اين رو به بررسي الگوريتمACS  در حل مسأله فروشنده دوره گرد(TSP)  پرداخته و نتايج حاصل از اين الگوريتم بـا الگوريتم هاي ديگر مقايسه مي گردد تا دلايل انتخاب اين الگوريتم مشخص گردد.

درACS ، مجموعهاي از عوامل همكار كه اصطلاحﹰا مورچه ناميده مـيشـوند، بـا يكـديگر براي رسيدن به راه حلهاي مناسب براي حل مسأله همكاري مـيكننـد . همكـاري ايـن عوامـل بـه صورت غير مستقي م و از طريق نشانهگذاري بر روي يالهاي گراف مسأله و در خـلال سـاخت راه حل مي باشد.

الگوريت مACS  كه در اين بخش مورد تجزيه و تحليل قرار ميگيرد بـر اسـاس روشهـاي قبلي اجتماع مورچگان و به منظور ارتقاي كارائي اين الگوريتمها در برخورد با مسألهTSP  متقـارن يا غيرمتقارن، طراحي شده است. در حقيقت هر عامل (مورچه) راه حلي را به صورت تكراري به اين شكل ايجـادمـي كنـد كـه نقاط جديدي را به راه حل موضعي ايجاد شده با بهرهبرداري از اطلاعات حاصـله از تجربيـات گذشـته(نشانهگذاري به وسيله فرومون) و كشفيات حريصانه جديد اضافه مينمايد. تجربيان مورچههاي پيشين به صورت اثرگذاري بر روي يالها حفظ ميگردد و اطلاعات ابتكاري به سادگي با استفاده از طول يالبه دست ميآيد. ايده درخشاني كه به وسيله اين الگوريتم ارائـه مـيگـردد، همكـاري هـدفدار مـابين عواملي با ساختار بسيار ساده است كه از طريق اثرگذاري تـدريجي بـر يـ ك حافظـه مـشترك صـورت مي پذيرد.  الگوريتم ACS داراي تفاوت هاي با سيست م AS معمولي به شرح زير است:

۱‐ قاعده انتقال حالت جديد كه راه مستقيمي براي ايجاد تعادل ميان جستجوي يالهاي جديد و بهره برداري از دانش جمع آوري شده فراه م مي سازد.

۲‐ قاعده به هنگام سازي عمومي فقط بر روي يالهايي انجام ميشود كه متعلق به بهتـرين راه حل باشند.  

۳‐  قاعده به هنگام سازي محلي فرومون، هم زمان با گردش  مورچهها روي  يالها اعمال ميشود. شيوه عملكرد ACS ك ﹰلا به اين صورت است:

m مورچه ابتدا بر رويn  شهر كه بنابر قاعدهاي (مث ﹰلا تصادفي ) انتخاب مـيگردنـد ، قـرارداده ميشوند. هر مورچه با استفاده از قاعده انتخاب تصادفي حريصانه ي ك تور ايجاد ميكنـد . ايـن مورچه در خلال ايجاد مسير، ميزان فرومون موجود بر روي يالها را بـا اسـتفاده از قاعـده بـه روز رساني محلي اصلاح ميكند هنگامي كه تمامي مورچهها مسير گردش خود را كامـل كردنـد ميـزان فرومون يالها با توجه به قانون بروز رساني عمومي مجددﹰا تغييرميكند. همانگونه كه پـيشتـر در سيست مAS  نيز توضيح داده شد، مورچهها در خلال ايجاد مسير خود با استفاده از داده هاي ابتكـاري(طول يالها) و ميزان فرومون هدايت ميگردند: مسير با ميزان بالاي فرمون مسيري مطلوبي خواهد بود. قواعد بروز رساني فرومون به نحوي طراحي ميگردند كه فرومون بيشتري بـه يـالهـايي كـه بايد توسط مورچه ها انتخاب شود، داده شود.

[1] Ant Colony System

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

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

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

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

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

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

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

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

۵ !۱! مقدمه …………………………………………………………………………………………………………۵۱

با بهرهوري از امكانات وسيعي كه عل م كامپيوتر در دو دهـه اخيـر در اختيـار مـا قـرار داده مسير حركت محاسبات دچار تحولي شگرف گشت و با استفاده از آن روشهاي ابتكـاري برگرفتـه از طبيعيت با ويژگيهاي انطباقپذيري ، پويايي و توانائي در حل مـسائل بـا پيچيـدگي زيـاد مـورد توجه خاص قرار گرفت.

يافتن بهترين مسير و يا بهترين مسيرهاي عبور در چارچوب مهندسي حمل و نقل ميتواند كاربردهاي فراواني داشته باشد كه بنابر وسعت ديد و محدوده مـورد نظـر مـيتوانـد در مـسيريابي شهري و جادهاي و در سيست مهاي خودكار مسيريابي مورد استفاده قرار گيرد و نيز با انجام تغييراتي در شكل و نحوه ارائه خروجي در محيطهاي صنعتي مد نظر قرار گيرد. با توجـه بـه حجـ م بـسيار بالاي پردازش در صورت استفاده از ر وش هاي شمارشي كه استفاده از اين روش هاي دقيق را بـراي حل اين گونه مسائل تقريبﹰا ناممكن ميسازد (با توجه به محدوديت زمان تصمي مگيـري در بـسياري از موارد ) استفاده از روشهاي ابتكاري اجتنابناپذير خواهد بود. به منظور ارتقاء كارآئي سيـستم وبالا بردن كيفيت نتايج حاصله سيست م بايستي داراي قابليت هاي زير باشد:

۱‐ حافظه (به منظور ذخيره سازي الگوهاي گذشته براي پيش بيني شرايط آينده)

۲‐ ديد كلي بر شبكه (قابليت شناخت نقاط بحراني در شبكه و يافتن راه حل)

۳‐ قابليت ارتباط

روشي كه در اين تحقيق براي حل مسأله پيدا كردن مسير بهينه مورد استفاده قرار مي گيـرد، استفاده از الگوريتم قدرتمندACS  و اصلاح و تغيير اين الگوريتم به منظـور بكـارگيري آن در حـلمسأله مورد نظر است. پيش از اين عمدتﹰا در حل اين مسأله از الگوريتمهاي كلي و يا اصلاح شـدهACO استفاده شده است كه به عنوان عمده ترين كار مي توان به مرجع ۱۰ اشاره نمود. دليل انتخـاب الگوريتمACS  به عنوان الگوريتم مرجع كلي توانمندي هاي اين روش در حـل مـسائل مختلـف بـه نسبت ساير روش هاست كه در بخش قبل به پاره اي از اين توانمندي ها مفص ﹰلا پرداخته شد.

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

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

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

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

در اين فصل سعي خواهد شد كه كارآمدي الگوريتم شرح داده شده در فصل قبل، از جنبـههـاي مختلف مورد بررسي قرار گيرد و بهترين مقادير پارامترها مشخص گردد. همچنـين كارآمـدي روشهـا و زير ساختارهاي بكار رفته مورد آزمايش قرار گيرد. معيارهاي انتخاب بهينه بر اساس كوتاه ترين مـسيرهاي يافت شده و متوسط طول مسيرهاي ساخته شده در تعداد مشخصي تكرار و يـا تعـداد مشخـصي اجراي برنامه  (كه هر اجرا شامل دفعاتي تكرار كلي خواهد بود) و يا بر حسب زمان پردازش مورد سـنجش قـرار خواهد گرفت . از آنجا كه عملكرد الگوريتم در برخورد با مـسائل داراي سـاختار هندسـي نـسبتﹰا مـنظم و مسائل با ساختار چيدمان تصادفي ممكن است متفاوت باشد، نتايج حاصل از حل هر دو نوع مسأله مـورد بررسي قرار خواهد گرفت. براي مسأله با ساختار هندسي بخشي از نقشه سـادهسـازي شـده شـهر تهـران مورد بررسي قرار ميگيرد كه در آن مسير خيابان حافظ بخشي از خيابان وليعصر به صورت يـ ك طرفـه در نظر گرفته شده است. اين شبكه داراي8۶ گره و 240 يال مي باشد. نحوه پراكندگي گره ها و يال هـا بـه صورتي است كه به كل شبكه ساختاري نسبتﹰا منظم مي دهد. در شكل زير نقشه، گره هـا و شـبكه مـشاهده مي گردد.

شك ل ۶‐۱ : شبكه راه هاي بخشي از شهر تهران

شبكه دوم داراي 80 گره ميباشد كه به صورت تصادفي در محـدوده تعريـف شـده قـرار گرفتهاند. در تعريف يالها سعي شده است كه شبكه بـه جـاي سـاختار هندسـي سـازه از سـاختار پيچيدهتري برخوردار باشد. شكل ۶‐۲ شبكه ايجاد شده را نمايش ميدهد. تعداد يالهاي اين شبكه 390 مي باشد.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

نحوه خرید

دانلود رایگان فایل
شما میتوانید تنها با یک کلید به راحتی فایل مورد نظر را دریافت کنید. 🙂

برای دسترسی به این فایل ابتدا باید اشتراک خریداری کنید. برای خرید اشتراک بر روی لینک زیر کلیک کنید.

ارتقاء عضویت

در صورت بروز هر گونه مشکل در روند خرید اینترنتی، بخش پشتیبانی کاربران آماده پاسخگویی به مشکلات و سوالات شما می باشد

راهنمای سایت

برخلاف سایت های دیگر که فایل ها را به صورت تکی می فروشند روال سایت ما این است که شما با عضویت در سایت ما میتوانید از تمام فایل های موجود استفاده کنید.

تمام مطالب سایت فقط برای اعضای سایت رایگان است.

نحوه عضویت در سایت