ACO یا Ant Colony Oprimization یک راه حل برای مسئله های با فضای حالت بزرگ یا NP است که تقریبا همانند الگوریتمهای Genetic است ولی در عمل نسبت به آن بهتر است. آنچه در ادامه می آید قسمتی از یک مقاله در مورد کاربردهای Data Mining و ACO است.
مورچه ها حشره های مستقلی هستند كه فعالیت اشتراكی دارند به ظاهر یك از مورچه فعال در یك كلونی مستقل از دیگری فعالیت می كند ولی در واقع كلیه مورچه ها در قالب یك سیستم جهت حل یك مسئله پیچیده با هم همكاری می كنند . مسئله مهم دررابطه مورچه ها و به طور كلی حشرات مسئله وابستگی بقا است. مورچه ها غذا را جستجو می كنند و آن را به شكل مناسب نگهدار و انبار می كنند حل این مسئله نیاز به برنامه ریزی پیشرفته دارد مورچه ها این عملیات را بدون هر گونه كنترل مركزی و نظارت متمر كز انجام می دهند به همین دلیل به حشرات به طور كلی گروه هوشمند می گویند.
در این مقاله ما به بررسی رفتار مورچه های واقعی، در زمان جستجو ی غذا تمركز می كنیم. مورچه ها قادرند كوتاه ترین مسیر را برای یافتن غذا از لانه خود به منبع غذا جستجو نمایند. .هر این فرآیند بدون هیچ گونه اطلاعات تصویری از مسیر غذا صورت می گیرد.
مورچه ها به صورت غیر مستقیم و از طریق ماده ای به نام فرومون با هم ارتباط بر قرار می كنند و اطلاعات مربوط به مسیر ها را در اختیار یكدیگر قرار می دهند مورچه ها با ترشح مقدار معینی فرومون مسیر خود را مشخص و علامت گذاری می كنند سایر مورچه ها با بررسی و مشاهده فرومون موجود در مسیر، راه یافتن غذا را پیدا می كنند این فرایند می تواند باز خورد حلقه مثبت را شرح دهد، به این ترتیب كه یك مورچه می تواند با استفاده از یك تابع احتمالی مسیر خود را انتخاب كند. هر چه تعداد مورچه های عبور كرده از یك مسیر بیشتر باشد آنگاه احتمال آنكه آن مسیر توسط مورچه بعدی انتخاب شود ، بیشتر است. در ابتدا مو رچه ها پس از خارج شدن از لانه خود با احتمال مساوی به جهات مختلف، برای یافتن غذا حركت می كنند . مورچه ها در مسیر های نا هموار با سرعت مساوی حركت می كنند، در مسیر خود فرومون ترشح می كنند . بعد از اینكه یك مورچه در مسیر خود غذایی پیدا كرد به سرعت از همان مسیر به سمت لانه مراجعت می كنند و میزان ترشح فرومون را در مسیر افزایش می دهد . به این ترتیب سایر مو رچه ها كه مسیر های دیگر را تجربه كرده اند به تدریج به یك مسیر هدایت خواهند شد .
1- مشخصات اصلی بهینه سازی به روش كلونی مورچه ها
الگوریتم بهینه سازی كلونی مورچه ها بر اساس یك سری عامل بنا نهاده شده است، بطوریكه رفتار این عامل ها از رفتار طبیعی مورچه ها الهام گرفته شده است نكته اساسی در رفتار عامل ها و یا مورچه ها همان همكاری و انطباق است با استفاده از این سیستم و الگوریتم می توان یك روش فرا اكتشافی برای حل مسائل بهینه سازی تركیبی ارائه كرد این روش فرا اكتشافی دارای دو ویژگی قدرت و تنوع است . به این ترتیب می توان به طور موفقیت آمیزی از آن در حل مسائل بهینه سازی پیچیده استفاده كرد .
الگوریتم ACO شامل بخشهای زیر است :
هر مورچه در زمان حل مسئله با مسیرهای مختلف بر خورد می كند. هنگامی كه یك مورچه از یك مسیر عبور می كند میزان فرومون جدید در آن مسیر را متناسب با كیفیت مسیر افزایش می دهد هنگامی كه یك مورچه با چند مسیر مختلف مواجه می شود . احتمال انتخاب مسیری كه میزان فرومون آن نسبت به سایر مسیرها بیشتر باشد افزایش می یابد. بنابر این مورچه ها همواره كوتاهترین مسیر را برای پیدا كردن غذا جستجو می كنند . كه این حالت می تواند حالت بهینه یا نزدیك به حالت بهینه باشد .
2- مشخصات و ماهیت الگوریتم های ACO
چنانچه بتوان ساختار مسئله را به صورت یك گراف نمایش داد آنگاه می توان از الگوریتم های ACO برای یافتن كوتاه ترین مسیر در گراف كه همانا پاسخ مسئله است استفاده كرد. هر مورچه بصورت تکاملی اقدام به تغییر یا ساخت بخشی از پاسخ مسئله می نماید ، علکرد کلی مورچه ها وابسته به یک تابع احتمالی و یک تابع اکتشافی وابسته به مسئله است. ساختار و ماهیت الگوریتم های ACO بصورت زیر است 2 :
ایجاد یک متد برای ارزیابی پاسخهای تولید شده . این متد بر اساس ساختار مسئله تعریف می شود.
ارائه یک تابع اکتشافی H) وابسته به مسئله ،این تابع میزان کیفیت item های قابل اضافه کردن به پاسخ مسئله را ارزیابی می کند .
یک روتین جهت بهمگام سازی میزان فرومون مسیرها(P)
ارائه یک تابع احتمالی که به کمک آن بتوان مسیرها را جهت تولید پاسخ جستجو کرد .در این تابع از تابع اکتشافی و میزان فرومون موجود در مسیرها استفاده می شود
منبع :cloob
سیستم های خبره
