مقایسه الگوریتم کلونی مورچگان و الگوریتم پریم در مسئله فروشنده دوره گرد

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

مقایسه الگوریتم کلونی مورچگان و الگوریتم پریم در مسئله فروشنده دوره گرد

مقدمه مقایسه الگوریتم کلونی مورچگان و الگوریتم پریم :

در این پروژه هدف مقایسه کارایی الگوریتم ACO (الگوریتم بهینه سازی کلونی مورچگان) ، با الگوریتم پریم در حل مسئله TSP (فروشنده دوره گرد) می‌باشد. الگوریتم پریم از دسته الگوریتم‌های حریصانه بوده و برای پیدا کردن درخت پوشای کمینه به کار می‌رود.

این الگوریتم برای حل مسله TSP مناسب نمی‌باشد اما در این پروژه کارایی این الگوریتم در حل این مسئله با الگوریتم ACO مورد مقایسه مقایسه قرار گرفته است. با توجه به اینکه در الگوریتم Prime عملیات پیدا کردن MST ، با یک راس خاص شروع می‌شود.

در این پروژه راس مذکور به صورت تصادفی انتخاب می‌شود. و پس از اینکه MST از این راس به دست آمد، حلقه ای تشکیل داده که یکی از راه حل های مسئله TSP می‌باشد. که این راه حل الزاما بهینه نمی‌باشد.

فرآیند پیدا کردن دور برای TSP با استفاده از الگوریتم Prime مطابق بالا بیان شد. پس از این کار با استفاده از روش ACO مسئله TSP را حل کرده و نتایج را مورد مقایسه قرار می‌دهیم.

الگوریتم پریم:

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

این الگوریتم در سال ۱۹۳۰ توسط ریاضیدانی به نام جارنیک داده شد وسپس در سال ۱۹۵۷ پریم، دانشمند علوم کامپیوتر آن را مستقل از جارنیک کشف کرد و در سال ۱۹۵۹ دایکسترا دوباره به آن دست یافت. ازاین رو این الگوریتم گاهی با نام الگوریتم DJP نیز شناخته میشود که برگرفته از اسامی دایکسترا، جارنیک و پریم است.

الگوریتم پریم، الگوریتمی برای پیدا کردن درخت پوشای کمینه یک گراف وزن‌دار است که مشابه الگوریتم دایکسترا برای درخت کوتاه‌ترین مسیر است.(اطلاعات بیشتر در گزارش پروژه به صورت مفصل آورده شده است)

الگوریتم کلونی مورچگان:

الگوریتم کلونی مورچه برای اولین بار توسط دوریگو (Dorigo) و همکارانش به عنوان یک راه حل چند عامله (Multi Agent) برای مسائل مشکل بهینه سازی مثل فروشنده دوره گرد ارائه شد.عامل هوشند (Intelligent Agent) موجودی است که از طریق حسگر ها قادر به درک پیرامون خود بوده و از طریق تاثیر گذارنده ها می تواند روی محیط تاثیر بگذارد.

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

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

الگوریتم مورچه ها، یک مثال بارز از هوش جمعی هستند که در آن عامل هایی که قابلیت چندانبالایی ندارند، در کنار هم و با همکاری یکدیگر می توانند نتایج بسیار خوبی به دست بیاورند.

این الگوریتم برای حل و بررسی محدوده وسیعی از مسائل بهینه سازی به کاربرده شده است. از این میان می توان به حل مسأله کلاسیک فروشنده دوره گرد و همچنین مسأله راهیابی در شبکه های مخابرات راه دور اشاره نمود.

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

نتایج به دست آمده :

قیمت پروژه : ۶۵۰۰۰ تومان

حجم : ۲۵ کیلوبایت
منبع : مطلب دی ال
رمز فایل : www.matlabdl.com