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

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

نقل قول:

---

نوشته شده توسط mahdi bg [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

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

---

از موضوعات مورد علاقه من الگوریتم های متاهیوریستیک و همچنین بیشتر از اون هوش مصنوعی ANN هستش
امیدوارم قدر این آموزش رو دوستان بدونن 5 سال پیش هیچی نبودش همش زبان اصلی باید می خوندی
:n12::n16::n16::n16:

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

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

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

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

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

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

منبع (اطلاعات بیشتر)
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

الگوریتم بهینه‌ سازی کلونی مورچه‌ ها 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 از همین رفتار “به جا گذاشتن فرمون از مسیر لانه تا غذا توسط مورچه‌ها و دنبال کردن مسیر توسط سایر مورچه ها برای رسیدن به غذا” الهام گرفته شده است. شاید این رفتار به ظاهر بسیار ساده باشد اما میتوان مسائل پیچیده ای را با آن حل نمود. در مطالب بعدی چندین نمونه مسئله ساده و پیچیده که با الگوریتم بهینه‌ سازی کلونی مورچه‌ ها قابل حل است را بررسی خواهیم کرد.

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

[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

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

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

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

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



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

[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

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

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

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

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

منبع
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

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

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

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

[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
رفتار کلونی مورچگان در مسیر های نابرابر

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

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

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

[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
رفتار کلونی مورچگان پس از گذشت زمان

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

منبع (اطلاعات بیشتر)
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

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

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

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

[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

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



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

[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

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

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

منبع (اطلاعات بیشتر)
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

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

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

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

[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

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

پیش از اینکه این آزمایش رو توضیح بدیم نیاز است تا مفهوم اکتشاف مسیر یا ” path exploration” رو بدونید، توی این مطلب درباره این مطلب توضیح داده شده است.

با توجه به ” path exploration” ، در ابتدای اضافه شدن مسیر کوتاهتر، تعداد خیلی کمی از مورچه ها مسیر کوتاه تر را انتخاب می کنند. (هنوز تعداد زیادی از مورچه ها مسیر بلند تر رو انتخاب میکنند. چون حجم فرمون پاشیده شده بر روی اون بیشتر است در نتیجه احتمال انتخاب آن توسط مورچه ها بیشتر است). چون این مسیر جدید کوتاهتر است در نتیجه مورچه های که آن را انتخاب میکنند سریعتر به غذا می رسند و بر می گردند و این امر باعث می شود که سرعت افزایش فرمون در این مسیر جدید بیشتر و بیشتر شود.
برای درک بهتر یک مثال رو بررسی میکنیم.
فرض کنید ما 10 تا مورچه داریم که 8 تا شون از مسیر بلند تر می رن و 2 تاشون از مسیر کوتاه تر، و همچنین زمان رفت و برگشت در مسیر بلند 6 دقیقه است و در مسیر کوتاه 3 دقیقه. خوب توی 3 دقیقه چه اتفاقی خواهد افتاد؟ دو تا مورچه مسیر غذا تا لانه رو می رن و بر می گردن در نتیجه 4 واحد فرمون روی مسیر پاشیده خواهد شد. (دو واحد هنگام رفت مورچه ها و دو واحد هنگام برگشت مورچه ها). توی این3 دقیق اون 8 تا مورچه، 8 واحد به مسیر فرمون پاشیدن (مورچه ها مسیر لانه تا غذا را طی کرده اند).

حالا فرض کنید اون دوتا مورچه برای بار دوم هم مسیر کوتاهتر رو انتخاب کنن، در این صورت تا دقیقه 6، 4 واحد دیگه هم فرمون به مسیر کوتاهتر اضافه خواهد شد و مجموعه فرمون ها میشه 8 تا، ولی در مسیر بلند تر توی این 6 دقیقه 16 واحد فرمون پاشیده شده است. یعنی در 6 دقیقه، مسیر کوتاهتر توانست نصف فرمون مسیر بلند فرمون داشته باشد. همانطور که مشخص است سرعت پاشیدن فرمون در مسیر کوتاه تر بیشتر از مسیر بلند تر است در نتیجه احتمال انتخاب مسیر در دور بعد توسط مورچه ها بیشتر می شود در نتیجه سرعت پاشیده شدن فرموون هم به همان نسبت بالاتر می رود تا جایی که همه مورچه ها مسیر کوتاهتر را انتخاب خواهند کرد.
یک مفهوم دیگه در مورد الگوریتم کلونی مورچه ها می مونه به اسم مفهوم تبخیر فرمون ” Pheromone evaporation” که توی مطلب بعدی در مورد اون بیشتر توضیح میدیم. در واقع این مفهوم تکمیل کننده رفتار کلونی مورچه ها است

منبع (اطلاعات بیشتر)
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

مفهوم تبخیر فرمون یا Pheromone evaporation در الگوریتم کلونی مورچگان

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

• الگوریتم بهینه‌ سازی کلونی مورچه‌ ها ACO -Ant Colony Optimization
• رفتار کلونی مورچه ها در آزمایش واقعی (مسیرهای برابر از لانه تا غذا)
• رفتار کلونی مورچه ها در آزمایش واقعی (مسیرهای نابرابر از لانه تا غذا)
• یک آزمایش واقعی و فوق العاده : پیدا کردن کوتاهترین مسیر توسط مورچه ها

تا اینجا ما تقریبا تمام نکات مربوط به الگوریتم کلونی مورچه ها رو بیان کردیم یک بخشی که مونده، مبحث تبخیر فرمون یا Pheromone evaporation هستش. اینکه تا حالا در مورد این قضیه صحبت نکردیم به این معنا نیست که بحث تبخیر فرمون کم اهمیت است بر عکس بلکه بسیار در الگوریتم تاثیر گذار است. در ادامه یک تعریف از تبخیر فرمون و اهمیت اون رو بیان خواهیم کرد.
همانطور که قبلا بیان کرده بودیم مورچه ها همین طور که حرکت میکنند، در مسیر یک ماده شیمیایی به اسم فرمون روی مسیر می پاشن. هر چه میزان فرمون در یک مسیر بیشتر باشد احتمال انتخاب مسیر توسط سایر مورچه ها بیشتر می شود. یک نکته آیا فرمون به صورت دائمی بر روی مسیر خواهد ماند؟ اگر فرمون مسیر از بین نرود چه اتفاقی خواهد افتاد؟

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

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

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

منبع (اطلاعات بیشتر)
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

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

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

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

فرض کنید ما گراف زیر رو داریم
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]


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

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

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

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

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

منبع(اطلاعات بیشتر)
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]