سلام خدمت همه دوستان
توی این مطلب قصد دارم موضوع الگوریتم مورچگان رو از صفر تا صد آموزش بدم
امیدوار مفید واقع بشه
Printable View
سلام خدمت همه دوستان
توی این مطلب قصد دارم موضوع الگوریتم مورچگان رو از صفر تا صد آموزش بدم
امیدوار مفید واقع بشه
از موضوعات مورد علاقه من الگوریتم های متاهیوریستیک و همچنین بیشتر از اون هوش مصنوعی 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) و مسئله کوتاهترین مسیر در گراف ، ایجاد کنیم و نیز یک چالش مهم در حل مسئه که گیر افتادن توی حلقه است رو یک اشاره بهش کنیم. به نظر شما این مسئله چطوری باید حل بشه؟
منبع(اطلاعات بیشتر)
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
همانطور که در مطلب قبل بیان کردین حل مسئله کوتاه ترین مسیر در یک گراف با کمک كلوني مورچه ها و روش های که مورچه ها در حل کوتاه ترین مسیر در آزمایش های قبلی انجام می دادند امکان دارد باعث ایجاد یک چالش می شود. این چالش ایجاد حلقه در مسیر حرکت مورچه ها است. حلقه چگونه در حل مسئله کوتاه ترین مسیر در یک گراف رخ می دهد
شکل زیر را در نظر بگیرید
فرض کنید مورچه ها از نقطه شروع (لانه) خود حرکت را به برای پیدا کردن غذا آغاز میکنند. زمانی که مورچه های دارند مسیر ها را بررسی میکنند، ممکن است یک حلقه را ایجاد کنند، زمانی که حلقه ایجاد می شود، باعث می شود که مورچه ها همانطور که در این حلقه می چرخند میزان فرمون بیشتری در مسیر می پاشیند و به مرور میزان فرمون بیشتر و بیشتر خواهد شد و همه مورچه این حلقه را دور خواهند زد. در این صورت حتی اگر یک مورچه از حلقه خارج شود چون مورچه های بیشتری در حلقه در حال چرخش هستند حتی این انحراف های کوچک نیز باعث حل مشکل حلقه نمی شوند (مسئله احتمال انتخاب مسیر تصادفی را در این آزمایش به صورت کامل بررسی کردیم). در نتیجه این حلقه مانند یک تله عمل کند و همه مورچه ها را در خود گرفتار کند.
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
كلوني مورچه ها و چالش ایجاد حلقه در گراف
خوب چه راه حلی پیشنهاد میشه برای این مسئله؟
راه حل اینه که ما بیاییم و یک سری قابلیت جدید به مورچه های که داریم اضافه کنیم. به این مورچه های ، مورچه های مصنوعی می گوییم. به این معنا که اونها مهمترین ویژگی های مورچه های واقعی رو دارن بعلاوه یک سری قابلیت اضافه که باعث بهبود الگوریتم كلوني مورچه ها میشه.
قابلیتی که ما به مورچه های مصنوعی خودمون اضافه میکنیم، یک حافظه کوچیک هستش. این حافظه به مورچه های مصنوعی کمک میکنه تا بتونن به مشکل حلقه در پیدا کردن مسیر در یک گراف غلبه کنن.
مشکل ایجاد حلقه و راه حل آن را در این مطلب مورد بررسی قرار دادیم. در مطلب بعدی جزییات کاملتری را در مورد مورچه های مصنوعی ارائه خواهیم نمود.
منبع (اطلاعات بیشتر)
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
ما در مطلب قبلی مسئله ایجاد حلقه در پیدا کردن کوتاهترین مسیر در گراف با کمک الگوریتم کونی مورچه ها بررسی کردیم و راه حلی که پیشنهاد دادیم اضافه کردن یک قابلیت به مورچه ها بود. این قابلیت داشتن حافظه محدود در مورچه ها است. (ما این مورچه ها را مورچه های مصنوعی نام گذاری کردیم، این مورچه ها مهمترین ویژگی های مورچه های واقعی رو دارن بعلاوه یک سری قابلیت اضافه که باعث بهبود الگوریتم كلوني مورچه ها میشه)
پیش از ادامه مطلب در صورتن نیاز مطلب که در مورد مسئله حلقه در گراف را قبلا مطرح کردیم یک بار مرورو کنید تا ابهامی به وجود نیاید.
خوب بریم سراغ سوال اصلی: چطوری اضافه کردن حافظه محدود، مسئله حلقه در کوتاهترین مسیر در گراف رو حل میکنه؟
مورچه های مصنوعی از این حافظه برای نگهداری دو نوع اطلاعات استفاده میکنند
نگهداری مسیری که تا حالا آمده اند: از آنجایی که این حافظه محدود است ممکن است مورچه ها نتواند همه مسیر را در حافظه خود نگهداری در نتیجه مورچه های مصنوعی در هر لحظه بخشی از مسیری (نه لزوما همه مسیر) که تا کنون آمده اند را در حافظه خود ذخیره دارند.
نگهداری هزینه مسیر که تا حالا آمده اند: یک اطلاع دیگری که مورچه ها در حافظه نگهداری می کنند، هزینه ای مسیرهای است که تا کنون از آنها عبور کرده اند. مانند مسیر، این اطلاعات نیز ممکن است شامل هزینه تمام مسیر طی شده نباشد و ممکن است تنها هزینه های بخشی از مسیر را نگهداری کند.
با توچه به این اطلاعات مورچه ها حلقه ها را شناسایی میکنند و با استفاده از حافظه ای که دارند مسیرهای که باعث ایجاد حلقه می شوند را انتخاب نخواهد کرد. حافظه محدود در مورچه های مصنوعی، آنها مجهز به یک سری قابلیت میکند که می توانند مسئله پیدا کرده کوتاهترین مسیر در گراف را با کیفیت بهتری حل کنند. این قابلیت ها عبارت است از :
حذف کردن مسیرهای که در آنها حلقه وجود دارد.
ارزیابی کیفیت مسیرهای که که توسط مورچه ها برای رسیدن به غذا (مقصد) ایجاد شده است – دقت داشته باشید این ارزیابی کاملا تخمینی است، و ممکن است دقیق نباشد. نکته مهم این است که این تخمین کمک می کند تا راه حل بهتری پیدا شود.
اضافه کردن قابلیت حافظه محدود به مورچه ها و تبخیر فرمون (که قبلا معرفی کردیم) به الگوریتم ACO ، نسخه جدیدی از الگوریتم ACO می شود که با عنوان Simple ACO یا به اختصار S-ACO شناخته می شود. در مطلب بعدی این الگوریتم را با جزییات بیشتری توضیح می دهیم.
منبع(اطلاعات بیشتر)
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
آموزش الگوریتم کلونی مورچه گان S-ACO – قسمت اول
در مطلب قبلی الگوریتم S-ACO رو به عنوان یکی از پایه ای ترین الگوریتم های ACO معرفی کردیم. الگوریتم S-ACO به عنوان یکی از الگوریتم های آموزشی برای کسانی که می خواهند با الگوریتم کلونی مورچه گان آشنا شوند، ارائه می شوند. به همین منظور در این مطلب و چند مطلب آینده اجزاء این الگوریتم را به جزییات دقیق و کامل بررسی میکنیم.
الگوریتم S-ACO دارای 4 گام است که عبارتند از:
حرکت مورچه از سمت لانه به سمت غذا برای پیدا کردن مسیر
حرکت مورچه از سمت غذا به سمت لانه و به روز رسانی فرمون مسیر
به روز رسانی فرمون ها بر اساس میزان کیفیت مسیر
تبخیر فرمون
در این مطلب، بخش اول الگوریتم که “حرکت مورچه از سمت لانه به سمت غذا برای پیدا کردن مسیر” را بررسی می کنیم.
در الگوریتم S-ACO مورچه ها دو نوع رفتار حرکتی دارند 1- حرکت رو به جلو و 2-حرکت رو به عقب. در حرکت رو به جلو مورچه ها سعی می کنند از لانه خود تا غذا یک مسیر را پیدا کنند، در حرکت رو به عقب مورچه های سعی می کنند از غذا تا لانه خود را برگردند. هر کدوم از این رفتارهای حرکتی را “مد حرکتی” نامگذاری میکنیم. یعنی وقتی مورچه در حال حرکت از لانه به سمت غذا است می گوییم مورچه در مد حرکتی رو به جلو است و وقتی مورچه در حال بازگشت از محل غذا به لانه است می گوییم مورچه در مد حرکتی برگشت هستند.
به عبارت دیگر وقتی یک مورچه از لانه شروع به حرکت می کند در مد حرکتی رو به جلو، است تا زمانی که به غذا برسد و بخواهد برگردد در این لحظه، مد حرکتی مورچه عوض می شود و به مد حرکتی برگشت تغییر میکند و سعی می کند تا مسیر رفته را برگردد.
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
گراف بالا را در نظر گیرید: وقتی مورچه در مد حرکتی رو به جلو است، به صورت احتمالی یکی از گره های گراف که از مکان فعالی (گره فعلی) قابل دسترس است را انتخاب میکند. گره قابل دسترسی، گرهی است که مسیر مستقیم به آن وجود داشته باشد (به عبارت دیگر در گراف یک یال بین آنها موجود باشد).
همانطورکه بیان شد انتخاب یکی از گره های قابل دسترسی، به صورت احتمالی می باشد که بر اساس میزان فرمون موجود در مسیرها می باشد که توسط مورچه ها بر روی آنها پاشیده شده است (اطلاعات کامل در مورد این بحت را می توانید در این مطلب مطالعه کنید).
تا اینجا تمام اطلاعاتی که در مورد گام اول الگوریتم S-ACo به عنوان پایه ای ترین الگوریتم کلونی مورچه گان رو بیان کردیم در مطالب بعدی سایر گام ها را بررسی میکنیم.
یک نکته که بد نیست بدونید اینه که : در الگوریتم S-ACO وقتی مورچه ها در مد حرکتی رو به جلو هستند بر روی مسیر فرمون نمی پاشند. عدم پاشیدن فرمون در مسیر لانه تا غذا (وقتی مورچه ها در مد حرکتی روبه جلو هستند) و مکانیزم تبخیر فرمون (که در مطالب بعدی توضیح میدهیم) کمک میکند تا از ایجاد حلقه در گراف جلوگیری شود. برای کسب اطلاعات کامل در مورد مسئله حلقه این مطلب رو مطالعه کنید.
منبع (اطلاعات بیشتر)
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
MrMining در جشنواره وب ایران
امسال سایت MrMining.ir در جشنواره وب ایران شرکت کرده است. در این جشنواره هر ساله از میان سایت های فعال در تمامی حوزه های وب و در گروه های مختلف یک سایت را به عنوان سایت برتر سال معرفی می شود. سایت MrMining.ir در شاخه اطلاع رسانی و محتوا و زیر شاخه کامپیوتر و فناوری اطلاعات شرکت کرده است.
برندگان این جشنواره به دو دسته هستند
1- سایت های منتخب از دیدگاه کاربران
2-سایت های منتخب از دیدگاه دوران (که متخصصین هر حوزه را شامل می شود)
در صورت مفید بودن سایت و مطالب ارائه شده در سایت می توانید، می توانید با رای دادن به سایت MrMining.ir ما در ارائه محتوای هر چه بهتر یاری کنید. مراحل رای دادن به سایت MrMining.ir نمایش داده شده است.
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
1- ابتدا بر روی بنر مشخص شده کلیک کنید (یا بر روی این لینک [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ] کلیک کنید تا مستقیم به صفحه رای گیری وارد شوید)
2- بر روی قلب مشخص شده در تصویر کلیک کنید
3- برای رای دادن می توانید از طریق اکانت گوگل و یا یاهو خود اقدام کنید
4- اطلاعات اکانت خود را وارد کنید
5-در صورت نیاز دکمه Allow را فشار دهید
6-رای شما ثبت شد
آموزش الگوریتم کلونی مورچگان S-ACO – قسمت دوم
در مطلب قبلی الگوریتم S-ACO رو به عنوان یکی از پایه ای ترین الگوریتم کلونی مورچگان ACO معرفی کردیم. همین طور گام اول این الگوریتم رو بررسی کردیم در این مطلب قصد داریم گام دوم اون رو مورد بررسی قرار بدیم.
الگوریتم S-ACO دارای 4 گام است که عبارتند از:
حرکت مورچه از سمت لانه به سمت غذا برای پیدا کردن مسیر
حرکت مورچه از سمت غذا به سمت لانه و به روز رسانی فرمون مسیر
به روز رسانی فرمون ها بر اساس میزان کیفیت مسیر
تبخیر فرمون
در این مطلب، بخش دوم الگوریتم کلونی مورچگان S-ACO که “حرکت مورچه از سمت غذا به سمت لانه و به روز رسانی فرمون مسیر” را بررسی می کنیم.
همانطور که در بیان کردیم مورچه های مصنوعی ما، دارای یک حافظه کوچک هستند که ای حافظه ها با آنها کمک میکند تا از وقتی مسیر لانه تا غذا را پیدا کنند، از بعضی از مشکلات مانند ایجاد حلقه در مسیر جلوگیری کند. حذف حلقه کمک زیادی بهبود کارایی الگوریتم میکند. (مورچه مصنوعی و تفاوت اون با مورچه ها واقعی در این مطلب بیان شده است)
وقتی مورچه ها به غدا می رسند و آماده برگشت به خانه می شوند، به عبارت دیگر مد حرکتی برگشت هستند. با استفاده از حافظه خود مسیری که از لانه تا غذا را طی کرده اند به یاد می آوند و با کمک آن مسیر برگشت را پیدا میکنند. مورچه ها مسیری که در مد حرکتی رو به جلو، طی کرده اند را در مد حرکتی برکشت برعکس طی میکنند تا به خانه برسند.(اطلاعات کامل در مورد انواع مد حرکتی مورچه ها در این مطلب می تونید مطالعه کنید)
مهم ترین نکته در مورد مد حرکتی برگشت آن است که مورچه در مسیر برگشت خود بر روی مسیر فرمون می پاشند. (قبلا گفتیم که مورچه های مصنوعی در مسیر لانه تا غذا فرمونی بر روی مسیر نمی پاشند).
در مطلب بعدی در مورد مکانیزم پاشیدن فرمون در مسیر بیشتر توضیح میدیم (گام سوم الگوریتم کلونی مورچگان S-ACO).
منبع(اطلاعات بیشتر)
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
آموزش الگوریتم کلونی مورچگان S-ACO – قسمت سوم
همانطور که در مطالب قبلی بیان کردیم ، الگوریتم SACO دارای 4 گام است که عبارتند از:
• حرکت مورچه از سمت لانه به سمت غذا برای پیدا کردن مسیر
• حرکت مورچه از سمت غذا به سمت لانه و به روز رسانی فرمون مسیر
• به روز رسانی فرمون ها بر اساس میزان کیفیت مسیر
• تبخیر فرمون
گام اول رو در این مطلب به تفصیل بهش پرداختیم و گام دوم را نیز در این مطلب کامل توضیح دادیم
در این مطلب، گام سوم الگوریتم SACO که “به روز رسانی فرمون ها بر اساس میزان کیفیت مسیر” را بررسی می کنیم.
همانطورکه بیان کردیم در الگویتم SACO مورچه های مصنوعی هنگام برگشت مسیری رو که از لانه تا غذا طی کرده اند را به یاد دارند (آن را در حافظه خود ذخیره کرده اند). مورچه های مصنوعی همچنین هزینه این مسیر را نیز محاسبه کرده اند و آن را نیز ذخیره کرده اند . (هزینه هر چیزی می تونه باشه، مثلا طول مسیر طی شده از لانه تا غذا)
با استفاده از این داده ها مورچه های مصنوعی می توانند هزینه مربوط به مسیرهای متفاوتی که تا حالا طی نموده اند و به غذا رسیده اند را با یکدیگر مقایسه کنند و کیفیت یک مسیر را نسبت به بقیه مسیرهای که تا حالا کشف کرده اند را تعیین کنند. همانطور که قبلا بیان کردیم وقتی مورچه ها تنها در مد حرکتی برگشت هستند بر روی مسیر فرمون می پاشن. میزان پاشیدین فرمون روی مسیر به کیفیت مسیر که محاسبه کردن بستکی داره. هر چه کیفیت مسیر بهتر باشه میزان فرمونی که روی مسیر می پاشن بیشتر و برعکس هر چه کیفیت پایین تر باشه، میزان فرمون کمتری روی مسیر می پاشن. (اطلاعات کامل در مورد انواع مد حرکتی مورچه ها در این مطلب می تونید مطالعه کنید)
از آنجایی که پاشیدن فرمون بر روی مسیر وابسته به کیفیت مسیر است، باعث می شود که مورچه های مصنوعی به سمت بهترین مسیر (کوتاه ترین مسیر) از لانه تا غذا متمایل شوند. به عبارت دیگر هر چه یک مسیر کوتاهتر باشد، در نتیجه کیفیت مسیر بهتر است و مقدار بیشتری فرمون روی آن می پاشند و در به تبع آن احتمال انتخاب آن مسیر توسط سایر مورچه های مصنوعی بیشتر می شود، که این امر باعث می شود که در نهایت کوتاه ترین مسیر توسط مورچه های مصنوعی انتخاب گردد.
منبع (اطلاعات بیشتر)
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]