حل مسئله TSP با استفاده از الگوریتم تکاملی کلونی مورچگان ACO با فرمونهای مختلف

نوع فایل :PDF

تعداد صفحات :6

سال انتشار :1394

چکیده

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

واژگان کلیدی

کلونی مورچگان، الگوریتم مورچه، ACO ، مسئله فروشنده دوره گرد، TSP