مقاله کامل الگوريتم كلوني مورچگان

Preface:

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

چكيده :

بهينه يابي كلوني مورچگان يكي از روشهاي فرا ابتكاري است كه به ساختن جواب مسايل بهينه يابي تركيبي سخت مي پردازد.

كه برگرفته از رفتار مورچگان در پيروي از مسيرهاي پيموده شده توسط مورچه هاي  قبلي شكل گرفته وبراي  يافتن جواب

مسايل بهينه يابي تركيبي  بكار ميرود. مسايل بهينه يابي تركيبي گونه اي از مسايل  ميباشندكه تعداد جوابهاي موجه متناهي

ليكن زياد  دارند وبه  صورت طبيعي شمارش همه آنها مقدور و يا به صرفه نيست.

در سالهاي اخير يكي از مهمترين زمينه هاي تحقيقاتي كشف رو شهاي ابتكاري از طبيعت بوده است كه از آنها براي بدست

آوردن نتايج  خوب در مسايل بهينه سازي تركيبي استفاده شده است .روش هاي ابتكاري با انجام چندين تكرار ويا با انجام

ميزان مشخصي آزمايش ويا بكارگيري يك يا چندين عامل نظير عصب ها- كروموزوم ها- مورچه ها ومانند آن بدست مي آيند.

مقدمه:

بهينه يابي كلوني مورچگان يكي از روشهاي فرا ابتكاري است كه با الهام از طبيعت به ساختن جواب مسايل بهينه يابي تركيبي

سخت مي پردازد.

اين سيستم اولين بار توسط ماركودوريگو در سال 1991براي حل مسايل مذكور معرفي گرديد و اولين كاربرد آن در مورد

شناخته شده ترين مسئله بهينه يابي مسايل تركيبي يعني مسئله فروشنده دوره گرد بود.

مشاهده جستجوي مورچگان واقعي جهت يافتن غذا و انتخاب كوتاه ترين مسير با مشاركت  جمعي مورچگان يك كلوني ,

سر منشا پيدايش اين روش براي حل مسايل بهينه يا بي تركيبي بود.مورچه هاي واقعي قادر به تبادل اطلاعات مربوط به منابع

غذايي ازطريق ماده اي شيميايي به نام فرمون مي باشد.

آنها با به جا گذاشتن فرومون در مسير ي كه طي مي كنند باعث ميشوند تا ديگر مورچه ها با مشاهده اثرات فرومون بجامانده

در مسير به آن جذب مي شوند و همان راه رابراي رسيدن به منابع غذايي دنبال كنندبا افزايش  حركت مورچه ها در يك مسير

ميزان  اثر فرومون افزايش يافته وخود عاملي براي جذب بيشتر مورچه ها به پيمودن اين مسير مي گردد.

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

مورچگان تا كنون براي حل مسايل تركيبي گوناگوني از جمله مسئله  برنامه ريزي كارگاه- مسئله رنگ آميزي گراف- مسئله  كوادراتيك ومسئله مسيريابي وسيله نقليه به كار رفته است.

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

فایل : 20 صفحه

فرمت : Word