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

مشخصات فایل

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

نحوه خرید

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

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

ارتقاء عضویت

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

چکیده

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

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

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

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

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

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

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

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

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

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

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

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

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

فصل ۱ کلیات

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[۱] Ant Colony System

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

در این فصل سعی خواهد شد که کارآمدی الگوریتم شرح داده شده در فصل قبل، از جنبـههـای مختلف مورد بررسی قرار گیرد و بهترین مقادیر پارامترها مشخص گردد. همچنـین کارآمـدی روشهـا و زیر ساختارهای بکار رفته مورد آزمایش قرار گیرد. معیارهای انتخاب بهینه بر اساس کوتاه ترین مـسیرهای یافت شده و متوسط طول مسیرهای ساخته شده در تعداد مشخصی تکرار و یـا تعـداد مشخـصی اجرای برنامه  (که هر اجرا شامل دفعاتی تکرار کلی خواهد بود) و یا بر حسب زمان پردازش مورد سـنجش قـرار خواهد گرفت . از آنجا که عملکرد الگوریتم در برخورد با مـسائل دارای سـاختار هندسـی نـسبتﹰا مـنظم و مسائل با ساختار چیدمان تصادفی ممکن است متفاوت باشد، نتایج حاصل از حل هر دو نوع مسأله مـورد بررسی قرار خواهد گرفت. برای مسأله با ساختار هندسی بخشی از نقشه سـادهسـازی شـده شـهر تهـران مورد بررسی قرار میگیرد که در آن مسیر خیابان حافظ بخشی از خیابان ولیعصر به صورت یـ ک طرفـه در نظر گرفته شده است. این شبکه دارای۸۶ گره و ۲۴۰ یال می باشد. نحوه پراکندگی گره ها و یال هـا بـه صورتی است که به کل شبکه ساختاری نسبتﹰا منظم می دهد. در شکل زیر نقشه، گره هـا و شـبکه مـشاهده می گردد.

شک ل ۶‐۱ : شبکه راه های بخشی از شهر تهران

شبکه دوم دارای ۸۰ گره میباشد که به صورت تصادفی در محـدوده تعریـف شـده قـرار گرفتهاند. در تعریف یالها سعی شده است که شبکه بـه جـای سـاختار هندسـی سـازه از سـاختار پیچیدهتری برخوردار باشد. شکل ۶‐۲ شبکه ایجاد شده را نمایش میدهد. تعداد یالهای این شبکه ۳۹۰ می باشد.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

نحوه خرید

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

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

ارتقاء عضویت

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

راهنمای سایت

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

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

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