آموزش الگوریتم مورچگان از صفر تا صد

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

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

این کلونی‌ها و تجمعات دارای یک ساختار اجتماعی فوق العاده هستند.
هر حشره معمولاً یک تنها یک یا چند وظیفه محدود رو انجام می‌ده
انجام کارهای بزرگ و پیچیده توسط این حشرات با کنار هم قرار گرفتن تک تک آنها قابل انجام است. کارهای که هر یک از حشرات به تنهایی نمی‌توانند انجام دهند. در واقع کار گروهی باعث موفقیت آنها در انجام فعالیت‌های بزرگ و پیچیده می‌شود.
اساس الگوریتم کلونی مورچگان بر روی “مشاهدات رفتار مورچه‌ها” استوار است. دانشمندان بسیاری رفتارهای مورچگان را به دقت بررسی نموده‌اند و بر اساس همین مشاهدات الگوریتم کلونی مورچگان را ابداع نموده‌اند. مهم‌ترین رفتارهای که از زندگی مورچگان مورد بررسی قرار گرفته است عبارت است از

فعالیت‌ها و رفتارهای مرتبط با حوزه تغذیه و غذا در مورچه ها
فعالیت‌ها و رفتارهای مرتبط با حوزه تقسیم کار بین مورچه‌ها
فعالیت‌ها و رفتارهای مرتبط با حوزه نوزادن و نگهداری از آنها
فعالیت‌ها و رفتارهای مرتبط با همکاری در حمل اجسام و مواد غذایی
الگوریتم کلونی مورچگان

همانطور که گفتیم رمز موفقیت مورچه‌ها از کار گروهی آنها ناشی می‌شه. مورچه‌ها از طریق stigmergy فعالیت‌های گروهی خودشون رو انجام می‌دن. Stigmergy به این معنا است که مورچه‌ها با یکدیگر به صورت غیر مستقیم ارتباط برقرار میکنن و وسیله برقراری ارتباط آنها با یکدیگر تغییراتی است که در محیط اطراف خود انجام می‌دهند. به عبارت دیگر مورچه‌ها از طریق تغییر محیط اطراف خودشون با یکدیگر ارتباط برقرار می‌کنند.

به عنوان مثال ، هر گاه مورچه ها احتمال وجود یک غذا را در یک منطقه بدهند، از یک ماده شیمایی که در بدن شون تولید میکنند برای نشانه گذاری محیط استفاده میکنند تا به سایر مورچه ها بگن که در این منطقه احتمال وجود غذا هست. هر چه این احتمال بیشتر باشد محیط با مقدار بیشتری از ماده شیمیایی نشانه گذاری میکنند. در این مثال سعی کردیم یک نمونه stigmergy  رو بررسی کنیم.

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

منبع (اطلاعات بیشتر)

http://mrmining.ir/2016/11/08/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85-%DA%A9%D9%84%D9%88%D9%86%DB%8C-%D9%85%D9%88%D8%B1%DA%86%D9%87-%D9%87%D8%A7-%DA%A9%D8%AC%D8%A7-%D8%A7%D9%84%D9%87%D8%A7%D9%85-%DA%AF%D8%B1/

الگوریتم بهینه‌ سازی کلونی مورچه‌ ها ACO -Ant Colony Optimization


یکی از موفق ترین مثال های الگوریتم مورچه ها (ant colony)، الگوریتم بهینه‌ سازی کلونی مورچه‌ ها (Ant Colony Optimization) است که به اختصار ACO نامیده می شود. با توجه به اینکه ACO نسبت به سایر سایر الگوریتم های مورچه ها بیشتر مورد توجه قرار گرفته است، تمرکز ما نیز بیشتر بر روی این الگوریتم است.
الگوریتم ACO از رفتار مربوط به پیدا کردن غذا (foraging) مورچه های الهام گرفته شده است. الگوریتم ACO برای مسئله های بهینه سازی گسسته (discrete) استفاده می شود.
همانطور که در مطلب قبلی بیان کردیم:

این کلونی‌ها و تجمعات دارای یک ساختار اجتماعی فوق العاده هستند.
هر حشره معمولاً یک تنها یک یا چند وظیفه محدود رو انجام می‌ده
انجام کارهای بزرگ و پیچیده توسط این حشرات با کنار هم قرار گرفتن تک تک آنها قابل انجام است. کارهای که هر یک از حشرات به تنهایی نمی‌توانند انجام دهند. در واقع کار گروهی باعث موفقیت آنها در انجام فعالیت‌های بزرگ و پیچیده می‌شود.
همچنین بیان کردیم که ” همانطور که گفتیم رمز موفقیت مورچه‌ها از کار گروهی آنها ناشی می‌شه. مورچه‌ها از طریق stigmergy فعالیت‌های گروهی خودشون رو انجام می‌دن. Stigmergy به این معنا است که مورچه‌ها با یکدیگر به صورت غیر مستقیم ارتباط برقرار میکنن”
در رفتار مربوط به پیدا کردن غذا (foraging)، هر گاه مورچه ها احتمال وجود یک غذا را در یک منطقه بدهند، از یک ماده شیمایی که در بدن شون تولید میکنند برای نشانه گذاری محیط استفاده میکنند تا به سایر مورچه ها بگن که در این منطقه احتمال وجود غذا هست. هر چه این احتمال بیشتر باشد محیط با مقدار بیشتری از ماده شیمیایی نشانه گذاری میکنند. نام این ماده شیمیایی فرمون (pheromones) است.
نکته جالب این است که اکثر مورچه ها کور هستند و چشم ندارد، به همین خاطر برای برقراری ارتباط با یکدیگر از ترشح مواد شیمیایی در محیط اطراف خود استفاده میکنند
دنباله فرمون یا trail pheromone یک از مهم‌ترین انواع فرمون است که گونه های از مورچه ها مانند Lasius niger و Iridomyrmex humilis برای مشخص کردن مسیر غذا تا لانه استفاده میکنند. سایر مورچه ها از این مسیرهای مشخص شده برای رسیدن به غذا استفاده میکنند.

الگوریتم ACO از همین رفتار “به جا گذاشتن فرمون از مسیر لانه تا غذا توسط مورچه‌ها و دنبال کردن مسیر توسط سایر مورچه ها برای رسیدن به غذا” الهام گرفته شده است. شاید این رفتار به ظاهر بسیار ساده باشد اما میتوان مسائل پیچیده ای را با آن حل نمود. در مطالب بعدی چندین نمونه مسئله ساده و پیچیده که با الگوریتم بهینه‌ سازی کلونی مورچه‌ ها قابل حل است را بررسی خواهیم کرد.

منبع (اطلاعات بیشتر)

http://mrmining.ir/2016/11/11/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85-%D8%A8%D9%87%DB%8C%D9%86%D9%87%E2%80%8C-%D8%B3%D8%A7%D8%B2%DB%8C-%DA%A9%D9%84%D9%88%D9%86%DB%8C-%D9%85%D9%88%D8%B1%DA%86%D9%87%E2%80%8C-%D9%87%D8%A7-ac/

رفتار کلونی مورچه ها در آزمایش واقعی (مسیرهای برابر از لانه تا غذا)

در این مطلب قصد داریم تا رفتار کلونی مورچه ها را در زمان پیدا کردن غذا مورد بررسی قرار دهیم. این آزمایش به صورت واقعی توسط دسته ای از مورچه ها انجام شده است.

رفتار جستجوی غذا (foraging) در بسیاری از گونه های مورچه ها مانند I. humilis، Linepithema humile و Lasius niger وجود دارد. همان‌طور که در مطالب قبل بیان کردیم در این رفتار مورچه ها سعی می‌کنند از ماده فرمون که که از خود بر روی محیط قرار می‌دهند با یک دیگر ارتباط برقرار کنند. فرمون یک ماده شیمیایی است که مورچه ها آن را تولید می کنند. در صورتی که نیاز با اطلاعات بیشتر دارید این مطلب را مطالعه کنید

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

در اینجا قصد داریم یکی از جذاب‌ترین این آزمایش‌های مرتبط با کلونی مورچه ها را که در سال 1989 انجام شده است را بررسی کنیم.
آزمایش به شکل زیر بود (این ازمایش شامل دو بخش بود):
بخش اول : همانطور که در شکل بالا مشخص است بین لانه مورچه‌ها و منبع غذا دو مسیر متفاوت وجود دارد که باهم برابر هستند.
بخش دوم: همانطور که در شکل بالا مشخص است بین لانه مورچه‌ها و منبع غذا دو مسیر متفاوت وجود دارد که یکی کوتاهتر از دیگری است.

بررسی بخش اول آزمایش (رفتار کلونی مورچه ها) :

مورچه‌ها ازادانه در در نقطه شروع (خانه) قرار داده شده بودند. مورچه‌ها شروع به حرکت کردند و نتیجه بسیار عجیب و شگفت انگیز بود. به نظر شما از هر یک از این دو مسیر برابر چه تعداد مورچه‌عبور می کردند؟

(چقدر فکر میکنید جواب تون درسته؟) ابتدا امر که هیچ فرمونی رو هیچ یک از مسیرها وجود ندارد. در این حالت وقتی مورچه‌ها به دوراهی می‌رسند و هیچ فرمونی روی مسیرها نیست، مورچه‌ها به احتمال برابر ممکن است هر یک از دو مسیر را انتخاب کند. از آنجایی که انتخاب به صورت احتمالی است، در یک مسیر  چندین مورچه ممکن است بیشتر از مسیر دیگر حرکت کنند. از آنجایی که مورچه‌ها در مسیر حرکت خود فرمون به جای می‌گذارند، در نتیجه همین حرکت چند مورچه باعث می‌شود که میزان فرمون در یک مسیر کمی بیشتر از مسیر دیگه شود و در نتیجه احتمال انتخاب مسیر توسط سایر مورچه ها بیشتر میشود و به مرورو زمان باعث می‌شود که همه مورچه‌ها از یک مسیر حرکت کنند.

خوب اگر یک مسیر بزرگ‌تر از مسیر دیگر باشد چه اتفاقی می افتد؟ در مطلب بعدی به این موضوع می‌پردازیم. (بخش دوم آزمایش رفتار کلونی مورچه ها)

منبع

http://mrmining.ir/2016/11/18/%D8%B1%D9%81%D8%AA%D8%A7%D8%B1-%DA%A9%D9%84%D9%88%D9%86%DB%8C-%D9%85%D9%88%D8%B1%DA%86%D9%87-%D9%87%D8%A7-%D8%A2%D8%B2%D9%85%D8%A7%DB%8C%D8%B4-%D9%88%D8%A7%D9%82%D8%B9%DB%8C-%D9%85%D8%B3/

رفتار کلونی مورچگان در آزمایش واقعی (مسیرهای نابرابر از لانه تا غذا)

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

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

رفتار کلونی مورچگان در مسیر های نابرابر

خوب مورچه ها در این آزمایش کدوم مسیر رو انتخاب کردن؟
مهمترین تفاوت این آزمایش با قبلی این است که دو مسیر با هم برابر نیستند. در ادامه بررسی دقیقی رو نحوه انتخاب مسیر توسط مورچه ها ارائه خواهیم کرد.

مانند آزمایش قبل مورچه در ابتدا به صورت تصادفی ممکن است هر یک از میسرها رو انتخاب کنند. نکته مهم این است که مورچه های که مسیر کوتاه‌تر رو انتخاب میکنند زودتر به غذا می رسند و در نتیجه زودتر شروع به برگشت به لانه رو انجام می دهند. از اونجای که مورچه ها بر روی مسیری که میرن فرمون می‌پاشند در نتیجه حجم فرمون در مسیر کوتاه تر بیشتر میشه.
بزارید با یک مثال بهتر توضیح بدیم. فرض کنید 20 تا مورچه داریم که از 10 تای اول 5 تا شون از مسیر بلند تر رفتن و 5 تا شون از مسیر کوتاه تر. حال فرض کنید اونایی که از مسیر کوتاه‌تر رفتن به غذا رسیدن و بر گشتن به لانه ولی مورچه های که مسیر بلندتر رو انتخاب کردن هنوز به لانه بر نگشتن. خوب توی این مورد چه اتفاقی افتاده، توی مسیر کوتاه‌تر، مورچه ها یک بار توی مسیر رفت فرمون پاشیدن و یک بار هم موقع برگشت فرمون پاشیدن در نتیجه 10 واحد فرمون توی مسیر قرار داده (5 واحد در برکشت و 5 واحد رفت) ولی توی مسیر بلندتر هنوز مورچه ها برنگشتن در نتیجه 5 واحد فرمون توی مسیر وجود داره. خوب حالا اگر مورچه 11 ام بخواد مسیر رو انتخاب کنه چون مسیر کوتاه‌تر فرمون بیشتری ریخته شده پس در نتیجه به احتمال زیاد اون مسیر رو انتخاب میکنه با این شرایط پس از مدتی فرمون مسیر کوتاه‌تر بسیار بیشتر از فرمون مسیر بلندتر میشه طوری که همه مورچه‌ها از مسیر کوتاه‌تر میرن.

نتیجه آزمایش رفتار کلونی مورچگان در مسیرهای نابرابر : بعد از گذشت مدتی تمام  مورچه ها از مسیر کوتاه تر برای رسیدن به غذا استفاده می‌کنند.

رفتار کلونی مورچگان پس از گذشت زمان

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

منبع (اطلاعات بیشتر)

http://mrmining.ir/2016/11/23/%D9%81%D8%AA%D8%A7%D8%B1-%DA%A9%D9%84%D9%88%D9%86%DB%8C-%D9%85%D9%88%D8%B1%DA%86%D9%87-%D9%87%D8%A7-%D8%A2%D8%B2%D9%85%D8%A7%DB%8C%D8%B4-%D9%88%D8%A7%D9%82%D8%B9%DB%8C-%D9%85%D8%B3%DB%8C/

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

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

آزمایش اول کلونی مورچه ها : در این آزمایش دوتا مسیر هم اندازه از لانه تا غذا وجود داشت. و از آنجایی که دوتا مسیر با هم یکی بودند چندان فرقی نمی کرد کدوم مسیر توسط مورچه ها انتخاب بشه. نکته مهم در این مسئله تاثیر حرکت تصادفی مورچه‌ها در مسیر است. ابتدا که هیچ فرمونی رو هیچ یک از مسیرها وجود ندارد. وقتی مورچه‌ها به دوراهی می‌رسند و هیچ فرمونی روی مسیرها نیست، مورچه‌ها به احتمال برابر ممکن است هر یک از دو مسیر را انتخاب کند. از آنجایی که انتخاب به صورت احتمالی است، در یک مسیر  چندین مورچه ممکن است بیشتر از مسیر دیگر حرکت کنند. از آنجایی که مورچه‌ها در مسیر حرکت خود فرمون به جای می‌گذارند، در نتیجه همین حرکت چند مورچه  بیشتر باعث می‌شود که میزان فرمون در یک مسیر کمی بیشتر از مسیر دیگه شود و در نتیجه احتمال انتخاب مسیر توسط سایر مورچه ها بیشتر می‌شود و به مرورو زمان باعث می‌شود که همه مورچه‌ها از یک مسیر حرکت کنند. (اگر ابهامی در مورد آزمایش دارید در پست های قبلی، آزمایش با جزییات در اینجا بیان شده است)

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

آزمایش دوم  کلونی مورچه ها : در ازمایش دوم یکی از مسیرها بلدتر از دیگری بود. مانند آزمایش قبل مورچه در ابتدا به صورت تصادفی ممکن است هر یک از میسرها رو انتخاب کنند. نکته مهم این است که مورچه های که مسیر کوتاه‌تر رو انتخاب میکنند زودتر به غذا می رسند و در نتیجه زودتر شروع به برگشت به لانه رو انجام می دهند. از اونجای که مورچه ها بر روی مسیری که میرن فرمون می‌پاشند در نتیجه حجم فرمون در مسیر کوتاه تر بیشتر میشه. و مورچه های بیشتری مسیر کوتاه تر رو انتخاب می کنند. (اگر ابهامی در مورد آزمایش دارید در پست های قبلی، آزمایش با جزییات در اینجا بیان شده است)

در این آزمایش تاثیر حرکت تصادفی مورچه ها در اول ازمایش ، بر روی خروجی تاثیری ندارد و در نتیجه هر چند بار هم آزمایش را تکرار کنیم  مورچه ها مسیر کوتاه تر را انتخاب میکنند. (بر خلاف آزمایش قبلی که انتخاب مسیر تصادفی در اول آزمایش بر روی خروجی نهایی تاثیر داشت)

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

منبع (اطلاعات بیشتر)

http://mrmining.ir

کوتاهترین مسیر در گراف و الگوریتم کلونی مورچگان

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

مسئله کوتاهترین مسیر در گراف : فرض کنید ما یک گراف داریم که شامل چندین گره است و مسیرهای نیز بین  این گره ها وجود دارد که آنها را یال می نامیم. هر یال در واقع فاصله بین دوتا گره است. در این گراف دو گره خاص وجود دارد ، گره مبدا (source ) و گره مقصد (destination). هدف مسئله این است که مسیری را از گره مبدا به گره مقصد پیدا کنیم که کمترین مسافت را داشته باشد. مسافت برابر است با مجموع طول یال های که از گره مبدا تا گره مقصد طی می کنیم. دقت داشته باشید ممکن است بین بعضی از گره ها در گراف مسیر (یالی) وجود نداشته باشد

فرض کنید ما گراف زیر رو داریم

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

اگر ما بخواهیم مسئله کوتاهترین مسیر در گراف رو با الگوریتم کلونی مورچگان حل کنیم، گره مبدا معادل لانه مورچه ها هستش و گره مقصد معادل غذا هستش. مورچه ها باید سعی کنن از بین مسیرهای زیادی که بین لانه تا غذا است کوتاهترین مسیر رو پیدا کنن.

مهمترین تفاوت این مسئله با مثال های که قبلا بیان کردیم این بوده که توی اونا ما دو تا مسیر کاملا مجزا از هم داشتیم و این مسیر ها غیر از دو نقطه یعنی منبع و مقصد هیچ نقطه مشترکی با هم نداشتن. به عبارت دیگر مسیرها کاملا از هم مجزا بودند.

همین تفاوت باعث میشه که یک سری چالش برای مورچه های که قصد دارن این مسئله رو حل کنن به وجود بیاد. مهمترین این چالش ها ایجاد حلقه است. یعنی ممکن است مورچه ها توی یک حلقه بیفتن ودور خودشون بچرخن.

توی این مطلب خواستیم نگاشتی بین آزمایش های مرتبط با الگوریتم کلونی مورچه ها که قبلا بیان کردیم (آزمایش 1 ، آزمایش2، آزمایش 3) و مسئله کوتاهترین مسیر در گراف ، ایجاد کنیم و نیز یک چالش مهم در حل مسئه که گیر افتادن توی حلقه است رو یک اشاره بهش کنیم. به نظر شما این مسئله چطوری باید حل بشه؟

منبع (اطلاعات بیشتر)

MrMining.ir