آبجی
4th May 2010, 01:22 AM
الگوریتم بهینه سازی کلونی مورچه ها ACOبه وسیله ی Marco Dorigoدر پایان نامه ی دکترایش معرفی شد،روشی مبتنی بر احتمال برای حل مسائل الگوریتمی که می تواندبرای مسیری در گراف به خوبی مقدار کمینه را ارائه دهد.این روش از رفتار مورچه ها در پیدا کردن مسیری از خانه به سمت غذا ، الهام گرفته شده است.
مرور
در جهان واقعی مورچه ها{در ابتدا}به صورت تصادفی سرگردان هستند ، و به محض پیدا کردن غذا با به جای گذاشتن ردی از فرمون به سوی کلونی خود باز می گردند. اگر دیگر مورچه ها این ره{علامت گذارده شده با فرمون} را پیدا می کردند،خوشبختانه مجبور نبودندبه جستجوی تصادفی خود ادامه دهند، و در عوض دنبال کردن رد {فرمون} وبازگشت به خانه{از همان مسیر رفتن}، باعث تقویت رد فرمون میشود و این در صورتی است که در انتهای مسیر غذایی موجود باشد.
در هر صورت ، پس از مدتی رد فرمون شروع به بخار شدن می کند، بدین سان نیروی جذب کننده اش کاهش میابد. زمان زیادی طول می کشد تا یک مورچه مسیر را به طور کامل طی کند ودوباره باز گردد ، پس زمان بیشتری طول می کشد تا فرمون تبخیر شود.
یک را ه کوتاه در مقایسه با یک راه طولانی سریعتر پیموده می شود و بنا براین بقایای فرمونکه روی زمین باقی مانده ، به سرعت تبخیر می شود. تبخیر فرمون یک مزیت است چون از همگرایی به راه حل بهینه نسبی پیشگیری می کند. اگر هیچ گاه تبخیری رخ نمی داد،مسیر انتخابی مورچه های اولیه ، همین طور برای مورچه های پیرو خیلی جذب کننده باقی می ماند . در این صورت جستجوی فضای راه حل ها نیاز مند اعمال فشار {دستکاری} از خارج{انسان}است.
پس هنگامی که یک مورچه راه خوب(کوتاهی)از کلونی به منبع غذا پیدا کند، دیگر مورچه ها خوشبختانه از آن مسیر پیروی می کنند و باز خورد مثبت{تقویت اثر شیمیایی فرمون}سرانجام همه ی مورچه ها را به پیروی از آن مسیر هدایت می کند.
ایده ی الگوریتم کلونی مورچه این رفتار را با "مورچه های شبیه سازی شده"، پیرامون گرافی که مسئله را نمایش می دهد، تقلید می کند تا مسئله را حل کند.
الگوریتم بهینه سازی کلونی مورچه برای تولید راه حل های نزدیک به بهینه در مسئله ی "فروشنده دوره گرد"{traveling salesman problem} استفده می شود.
این الگوریتم نسبت به genetic algorithm و simulated annealing در حالتی که گراف ممکن است به صورت دینامیک تغییر کند، در روش نزدیک شدن به راه حل بهینه دارای مزیت است.
اگوریتم مورچه می تواند بطور پیوسته و اجرا شود و در لحظه{ real time} با تغییرات مطابقت پیدا کند.
ین ویژگی باعث شده است که اگوریتم مورچه مورد علاقه ی حل کنندگان مسائل مربوط به مسیر یابی شبکه و یا سیستم های حمل و نقل شهری باشد.
مرور
در جهان واقعی مورچه ها{در ابتدا}به صورت تصادفی سرگردان هستند ، و به محض پیدا کردن غذا با به جای گذاشتن ردی از فرمون به سوی کلونی خود باز می گردند. اگر دیگر مورچه ها این ره{علامت گذارده شده با فرمون} را پیدا می کردند،خوشبختانه مجبور نبودندبه جستجوی تصادفی خود ادامه دهند، و در عوض دنبال کردن رد {فرمون} وبازگشت به خانه{از همان مسیر رفتن}، باعث تقویت رد فرمون میشود و این در صورتی است که در انتهای مسیر غذایی موجود باشد.
در هر صورت ، پس از مدتی رد فرمون شروع به بخار شدن می کند، بدین سان نیروی جذب کننده اش کاهش میابد. زمان زیادی طول می کشد تا یک مورچه مسیر را به طور کامل طی کند ودوباره باز گردد ، پس زمان بیشتری طول می کشد تا فرمون تبخیر شود.
یک را ه کوتاه در مقایسه با یک راه طولانی سریعتر پیموده می شود و بنا براین بقایای فرمونکه روی زمین باقی مانده ، به سرعت تبخیر می شود. تبخیر فرمون یک مزیت است چون از همگرایی به راه حل بهینه نسبی پیشگیری می کند. اگر هیچ گاه تبخیری رخ نمی داد،مسیر انتخابی مورچه های اولیه ، همین طور برای مورچه های پیرو خیلی جذب کننده باقی می ماند . در این صورت جستجوی فضای راه حل ها نیاز مند اعمال فشار {دستکاری} از خارج{انسان}است.
پس هنگامی که یک مورچه راه خوب(کوتاهی)از کلونی به منبع غذا پیدا کند، دیگر مورچه ها خوشبختانه از آن مسیر پیروی می کنند و باز خورد مثبت{تقویت اثر شیمیایی فرمون}سرانجام همه ی مورچه ها را به پیروی از آن مسیر هدایت می کند.
ایده ی الگوریتم کلونی مورچه این رفتار را با "مورچه های شبیه سازی شده"، پیرامون گرافی که مسئله را نمایش می دهد، تقلید می کند تا مسئله را حل کند.
الگوریتم بهینه سازی کلونی مورچه برای تولید راه حل های نزدیک به بهینه در مسئله ی "فروشنده دوره گرد"{traveling salesman problem} استفده می شود.
این الگوریتم نسبت به genetic algorithm و simulated annealing در حالتی که گراف ممکن است به صورت دینامیک تغییر کند، در روش نزدیک شدن به راه حل بهینه دارای مزیت است.
اگوریتم مورچه می تواند بطور پیوسته و اجرا شود و در لحظه{ real time} با تغییرات مطابقت پیدا کند.
ین ویژگی باعث شده است که اگوریتم مورچه مورد علاقه ی حل کنندگان مسائل مربوط به مسیر یابی شبکه و یا سیستم های حمل و نقل شهری باشد.