مقاله الگوریتم کلونی مورچگان Ant colony algorithm

مقاله

قیمت :   ۵۲۰۰ تومان ( پنج هزار و دویست تومان)

تعداد صفحات:

۵۲  ( پنجاه و دو )

دسته :

کامپیوتر و IT

نوع فایل:

Word

توضیحات:

مناسب جهت پروژه پایانی

فهرست مطالب :

۱-مقدمه

۱-۱ ؟

۱-۲

۱-۳ بهینه سازی مسائل بروش کلونی مورچه ACO

۱-۴ مورچه ها چگونه می توانند کوتاهترین مسیر را پیدا کنند؟

۱-۵ مزیتهای ACO

۱-۶ کاربردهای ACO

۱-۷ مسیر یابی شبکه های کامپیوتری با استفاده از ACO

۱-۸ ارائه الگوریتم فراابتکاری مبتنی بر سیستم کلونی مورچگان برای مسئله مکان یابی و فرض تخصیص چندین مسیر به هر وسیله نقلیه

۱-۹ تصمیمات مهم در مدیریت تولید و عملیات

۱-۱۰ ﺷﺮح ﻣﺴﺌﻠﻪ، ﺗﺪوﻳﻦ ﻣﺪل رﻳﺎﺿﻲ و اراﻳﻪ راهﺣﻞ

۱-۱۱ ﻣﺘﻐﻴﺮﻫﺎی ﺗﺼﻤﻴﻢ

۱-۱۲ اﻟﮕﻮرﻳﺘﻢ ﻓﺮااﺑﺘﻜﺎری ﭘﻴﺸﻨﻬﺎدی

۱-۱۳ اﻟﮕﻮرﻳﺘﻢﻫﺎی ﻣﻌﻤﻮل ﺑﻬﻴﻨﻪﻳﺎﺑﻲ ﻛﻠﻮﻧﻲ ﻣﻮرﭼﮕﺎن

۱-۱۴ شرح الگوریتم پیشنهادی

۱-۱۵ ﻣﺪل اراﻳﻪ ﺷﺪه ﺑﺮای

۱-۱۶ ﻧﺘﻴﺠﻪﮔﻴﺮی و اراﻳﻪ ﻧﺘﺎﻳﺞ

بخش دوم- برای حل

۲-۱ معرفی

۲-۲ مسئله فروشنده سیار

۲-۳

۲-۳-۱

۲-۳-۲

۲-۴ روش ارائه شده

۲-۴-۱

۲-۴-۲ تازه کردن پارامتر کشف شده

۲-۴-۳ الگوریتم ارائه شده

۲-۵ نتایج آزمایشی

۳-۶ نتیجه گیری

ﻣﻨﺎﺑﻊ و ماخذ

 

چکیده :

الگوریتم کلونی مورچه الهام گرفته شده از مطالعات ومشاهدات روی کلونی مورچه هاست. این مطالعات نشان داده که مورچه ها حشراتی اجتماعی هستند که در کلونی ها زندگی می کنند و رفتار آنها بیشتر در جهت بقاء کلونی است تادرجهت بقاء یک جزء از آن. بهینه‌سازی کلونی مسیریابی مورچه (ACO) یک الگوریتم اکتشافی است که یک تکنیک موفقیت‌آمیز را اثبات کرده است و برای تعدادی از مسائل بهینه‌سازی ترکیبی (CO) به کار رفته است. مسئله فروشنده سیار (TSP) یکی از مهم‌ترین مسائل ترکیبی می‌باشد. ACO به عنوان یکی از روش‌های محاسبه عملکرد بالا برای TSP در نظر گرفته شده است. این الگو هنوز دارای برخی اشکالات مثل عمل رکود، زمان محاسباتی طولانی و مسئله همگرایی (تقارب) نابهنگام مربوط به الگوریتم اصلی ACO بر روی TSP می‌باشد. این مسائل هنگامی واضح‌تر خواهد بود که میزان مسائل مورد ملاحظه واقع شده افزایش یابد. سیستم ارائه شده بر اساس الگوریتم اصلی ACO همراه با استراتژی توزیع مناسب و آنتروپی (بی‌نظمی) اطلاعاتی که درباره استراتژی پیکره‌بندی به منظور جدید کردن پارامتر اکتشافی در ACO برای بهبود عملکرد در حل TSP هدایت شده‌اند، می‌باشد. سپس ACO به واسطه TSP با یکی کردن کشف‌ کننده بهینه‌سازی داخلی اصلاح شده است. الگوریتم‌ها بر اساس مسائل بنچ‌مارک از طریق TSPLIB آزمایش شده‌اند و نتایج آزمایش ارائه شده است. طبق آزمایشات‌ها، الگوریتم ارائه شد ه نسبت به الگوریتم ACO از عملکرد بهتری برخوردار می‌باشد.

کلید واژه‌ها: کلونی مورچگان- الگوریتم مورچه – ACO – بهینه‌سازی کلونی مورچه، مسئله فروشنده دوره گرد، آنتروپی (بی‌نظمی)

 

بخش اول – کلونی مورچگان
۱- مقدمه
انسان همیشه برای الهام گرفتن به جهان زنده پیرامون خود نگریسته است. یکی از بهترین طرح های شناخته شده، طرح پرواز انسان است که ابتدا لئورناردو داوینچی(۱۵۱۹-۱۴۵۲) طرحی از یک ماشین پرنده را بر اساس ساختمان بدن خفاش رسم نمود. چهار صد سال بعد کلمان آدر ماشین پرنده ای ساخت که دارای موتور بود وبجای بال از ملخ استفاده می کرد.
هم اکنون کار روی توسعه سیستم های هوشمند با الهام ازطبیعت از زمینه های خیلی پرطرفدار هوش مصنوعی است. الگوریتمهای ژنتیک که با استفاده از ایده تکاملی داروینی و انتخاب طبیعی مطرح شده، روش بسیار خوبی برای یافتن مسائل بهینه سازیست. ایده تکاملی داروینی بیانگر این مطلب است که هر نسل نسبت به نسل قبل دارای تکامل است و آنچه در طبیعت رخ می دهد حاصل میلیون ها سال تکامل نسل به نسل موجوداتی مثل مورچه است.

۱-۱ الگوریتم کلونی مورچه ها چیست؟
یک مورچه در حال حرکت، مقداری فرومون (در اندازه¬های مختلف) از خود بر زمین باقی می گذارد و بدین ترتیب مسیر را بوسیله بوی این ماده مشخص می سازد. هنگامی که یک مورچه به طور تصادفی و تنها حرکت می کند، با مواجه شدن با مسیری که دارای اثر فرومون بیشتری است، به احتمال زیاد مسیر فوق را انتخاب می کند و با فرومونی که از خود بر جای می گذارد، آن را در مسیر مذکور تقویت می نماید
الگوریتم کلونی مورچه الهام گرفته شده از مطالعات ومشاهدات روی کلونی مورچه هاست. این مطالعات نشان داده که مورچه ها حشراتی اجتماعی هستند که در کلونی ها زندگی می کنند و رفتار آنها بیشتر در جهت بقاء کلونی است تادرجهت بقاء یک جزء از آن. یکی از مهمترین و جالبترین رفتار مورچه ها، رفتار آنهابرای یافتن غذا است و بویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی وآشیانه. این نوع رفتار مورچه ها دارای نوعی هوشمندی توده ای است که اخیرا مورد توجه دانشمندان قرار گرفته است.باید تفاوت هوشمندی توده ای(کلونی) و هوشمندی اجتماعی راروشن کنیم.
در هوشمندی اجتماعی عناصر میزانی از هوشمندی را دارا هستند. بعنوان مثال درفرآیند ساخت ساختمان توسط انسان، زمانی که به یک کارگر گفته میشود تا یک توده آجررا جابجا کند، آنقدر هوشمند هست تا بداند برای اینکار باید از فرغون استفاده کند نه مثلا بیل!!! نکته دیگر تفاوت سطح هوشمندی افراد این جامعه است. مثلا هوشمندی لازم برای فرد معمار با یک کارگر ساده متفاوت است.
در هوشمندی توده ای عناصر رفتاری تصادفی دارند و بین آن ها هیچ نوع ارتباط مستقیمی وجود ندارد و آنها تنها بصورت غیرمستقیم و با استفاده از نشانه ها با یکدیگر در تماس هستند. مثالی در این مورد رفتارموریانه ها در لانه سازیست.
جهت علاقه مند شدن شما به این رفتار موریانه ها وتفاوت هوشمندی توده ای و اجتماعی توضیحاتی را ارائه می دهم :
فرآیند ساخت لانه توسط موریانه ها مورد توجه دانشمندی فرانسوی به نام گرس قرار گرفت. موریانه ها برای ساخت لانه سه فعالیت مشخص از خود بروز می دهند. در ابتدا صدها موریانه به صورت تصادفی به این طرف و آن طرف حرکت می کنند. هر موریانه به محض رسیدن به فضایی که کمی بالاتر از سطح زمین قرار دارد شروع به ترشح بزاق می کنند و خاک را به بزاق خود آغشته می کنند. به این ترتیب گلوله های کوچک خاکی با بزاق خود درست می کنند. علیرغم خصلت کاملا تصادفی این رفتار، نتیجه تا حدی منظم است. در پایان این مرحله در منطقه ای محدود تپه های بسیار کوچک مینیاتوری از این گلوله های خاکی آغشته به بزاق شکل می گیرد. پس از این،همه تپه های مینیاتوری باعث می شوند تا موریانه ها رفتار دیگری از خود بروز دهند. در واقع این تپه ها به صورت نوعی نشانه برای موریانه ها عمل می کنند. هر موریانه به محض رسیدن به این تپه ها با انرژی بسیار بالایی شروع به تولید گلوله های خاکی بابزاق خود می کند. این کار باعث تبدیل شدن تپه های مینیاتوری به نوعی ستون می شود. این رفتار ادامه می یابد تا زمانی که ارتفاع هر ستون به حد معینی برسد. در این صورت موریانه ها رفتار سومی از خود نشان می دهند. اگر در نزدیکی ستون فعلی ستون دیگری نباشد بلافاصله آن ستون را رها می کنند در غیر این صورت یعنی در حالتی که در نزدیکی این ستون تعداد قابل ملاحظه ای ستون دیگر باشد، موریانه ها شروع به وصل کردن ستونهاو ساختن لانه می کنند.
تفاوتهای هوشمندی اجتماعی انسان با هوشمندی توده ای موریانه را در همین رفتار ساخت لانه می توان مشاهده کرد. کارگران ساختمانی کاملا براساس یک طرح از پیش تعیین شده عمل می کنند، در حالی که رفتار اولیه موریانه هاکاملا تصادفی است. علاوه بر این ارتباط مابین کارگران ساختمانی مستقیم و از طریق کلمات و … است ولی بین موریانه ها هیچ نوع ارتباط مستقیمی وجود ندارد و آنها تنهابصورت غیر مستقیم و از طریق نشانه ها با یکدیگر در تماس اند. گرس نام این رفتار را Stigmergie گذاشت، به معنی رفتاری که هماهنگی مابین موجودات را تنهااز طریق تغییرات ایجاد شده در محیط ممکن می سازد

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

مساله فروشنده دورهگرد (Traveling Salesman Problem) و یا به اختصار TSP، یکی از مسائل مشهور بهینهسازی ترکیبی است. در این مسأله، یک فروشنده دوره گرد می خواهد به چند شهر سفر کند وکالای خود را به فروش برساند. اما می بایست از تمام شهرها عبور کند، از هر شهر فقطیک بار عبور کند و با طی کوتاه ترین مسیر، سفر خود را به پایان برساند. حل این مساله کاربردهای وسیعی در حوزه های مختلف مهندسی دارد. از جمله مسائلی که از نظرریاضی با مسأله TSP معادل هستند، می توان به حل انواع مسایل زمانبندی، مسیریابی،جایابی کالا در انبار، جایابی ماشینها در کارگاه ها، و طراحی مدارات چاپی اشاره نمود.

۱-۳ بهینه سازی مسائل بروش کلونی مورچه(ACO) :
همانطور که می دانیم مسئله یافتن کوتاهترین مسیر، یک مسئله بهینه سازیست که گاه حل آن بسیار دشوار است و گاه نیز بسیار زمانبر. بعنوان مثال مسئله فروشنده دوره گرد(TSP). در این مسئله فروشنده دوره گرد باید از یک شهر شروع کرده، به شهرهای دیگربرود و سپس به شهر مبدا بازگردد بطوریکه از هر شهرفقط یکبار عبور کند و کوتاهترین مسیر را نیز طی کرده باشد. اگر تعداد این شهرها n باشد در حالت کلی این مسئله از مرتبه (n-1)! است که برای فقط ۲۱ شهر زمان واقعا زیادی می برد:
روز۱۰۱۳*۷/۱ = S1016*433/2 = ms10*1018*433/2 = !20
با انجام یک الگوریتم برنامه سازی پویا برای این مسئله ، زمان از مرتبه نمایی بدست می آید که آن هم مناسب نیست. البته الگوریتم های دیگری نیز ارائه شده ولی هیچ کدام کارایی مناسبی ندارند. ACO الگوریتم کامل و مناسبی برای حل مسئله TSP است.

۱-۴ مورچه ها چگونه می توانند کوتاهترین مسیر را پیدا کنند؟

مورچه ها هنگام راه رفتن از خود ردی از ماده شیمیایی فرومون(Pheromone) بجای میگذارند البته این ماده بزودی تبخیر می شد ولی در کوتاه مدت بعنوان رد مورچه بر سطح زمین باقی می ماند. یک رفتار پایه ای ساده در مورچه های وجود دارد :
آنها هنگام انتخاب بین دو مسیربصورت احتمالاتی( Statistical) مسیری را انتخاب می کنند که فرومون بیشتری داشته باشد یا بعبارت دیگر مورچه های بیشتری قبلا از آن عبور کرده باشند. حال دقت کنید که همین یک تمهید ساده چگونه منجربه پیدا کردن کوتاهترین مسیر خواهد شد :
همانطور که در شکل ۱-۱ می بینیم مورچه های روی مسیر AB در حرکت اند (در دو جهت مخالف) اگر درمسیر مورچه ها مانعی قرار دهیم(شکل ۲-۱) مورچه ها دو راه برای انتخاب کردن دارند. اولین مورچه ازA می آید وبهC می رسد، در مسیر هیچ فرومونی نمی بیند بنابر این برای مسیر چپ و راست احتمال یکسان می دهد و بطور تصادفی و احتمالاتی مسیر CED را انتخاب می کند. اولین مورچه ای که مورچه اول را دنبال می کند زودتر از مورچه اولی که ازمسیر CFD رفته به مقصد می رسد. مورچه ها در حال برگشت و به مرور زمان یک اثر بیشتر فرومون را روی CED حس می کنند و آنرا بطور احتمالی و تصادفی( نه حتما و قطعا)انتخاب می کنند. در نهایت مسیر CED بعنوان مسیر کوتاهتر برگزیده می شود. درحقیقت چون طول مسیر CED کوتاهتراست زمان رفت و برگشت از آن هم کمتر می شود و در نتیجه مورچه های بیشتری نسبت به مسیر دیگر آنرا طی خواهند کرد چون فرومون بیشتری در آن وجوددارد.
نکه بسیار با اهمیت این است که هر چند احتمال انتخاب مسیر پر فرومون ت توسط مورچه ها بیشتر است ولی این کماکان احتمال است و قطعیت نیست. یعنی اگر مسیر CED پرفرومون تر از CFD باشد به هیچ عنوان نمی شود نتیجه گرفت که همه مورچه ها از مسیرCED عبورخواهند کرد بلکه تنها می توان گفت که مثلا ۹۰% مورچه ها از مسیر کوتاهتر عبورخواهند کرد. اگر فرض کنیم که بجای این احتمال قطعیت وجود می داشت، یعنی هر مورچه فقط و فقط مسیر پرفرومون تر را انتخاب میکرد آنگاه اساسا این روش ممکن نبود به جواب برسد. اگر تصادفا اولین مورچه مسیرCFD)مسیر دورتر) را انتخاب می کرد و ردی از فرومون بر جای می گذاشت آنگاه همه مورچه ها بدنبال او حرکت می کردند و هیچ وقت کوتاهترین مسیر یافته نمی شد. بنابراین تصادف و احتمال نقش عمده ای در ACO بر عهده دارند.
نکته دیگر مسئله تبخیر شدن فرومون بر جای گذاشته شده است. برفرض اگر مانع در مسیر AB برداشته شود و فرومون تبخیر نشود مورچه ها همان مسیرقبلی را طی خواهند کرد. ولی در حقیقت این طور نیست. تبخیر شدن فرومون و احتمال به مورچه ها امکان پیدا کردن مسیر کوتاهتر جدید را می دهند.

۱-۵ مزیتهای ACO :
همانطور که گقته شد «تبخیر شدن فرومون» و «احتمال-تصادف» به مورچه ها امکان پیدا کردن کوتاهترین مسیر را می دهند. این دو ویژگی باعث ایجادانعطاف در حل هرگونه مسئله بهینه سازی می شوند. مثلا در گراف شهرهای مسئله فروشنده دوره گرد، اگر یکی از یالها (یا گره ها) حذف شود الگوریتم این توانایی را دارد تابه سرعت مسیر بهینه را با توجه به شرایط جدید پیدا کند. به این ترتیب که اگر یال)یا گره ای) حذف شود دیگر لازم نیست که الگوریتم از ابتدا مسئله را حل کند بلکه ازجایی که مسئله حل شده تا محل حذف یال (یا گره) هنوز بهترین مسیر را داریم، از این به بعد مورچه ها می توانند پس از مدت کوتاهی مسیر بهینه(کوتاهترین) رابیابند.

فایل کامل این تحقیق ۵۲ صفحه بصورت ورد WORD مرتب و فونت بندی شده می باشد.
در تمامی ساعات شبانه روز >> پرداخت آنلاین و دانلود آنلاین پروژه

 

Related posts

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

Translate »