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

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

شکل زیر را در نظر بگیرید

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

كلوني مورچه ها و چالش ایجاد حلقه در گراف

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

خوب چه راه حلی پیشنهاد میشه برای این مسئله؟
راه حل اینه که ما بیاییم و یک سری قابلیت جدید به مورچه های که داریم اضافه کنیم. به این مورچه های ، مورچه های مصنوعی می گوییم. به این معنا که اونها مهمترین ویژگی های مورچه های واقعی رو دارن بعلاوه یک سری قابلیت اضافه که باعث بهبود الگوریتم كلوني مورچه ها میشه.
قابلیتی که ما به مورچه های مصنوعی خودمون اضافه میکنیم، یک حافظه کوچیک هستش. این حافظه به مورچه های مصنوعی کمک میکنه تا بتونن به مشکل حلقه در پیدا کردن مسیر در یک گراف غلبه کنن.

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

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

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

ما در مطلب قبلی مسئله ایجاد حلقه در پیدا کردن کوتاهترین مسیر در گراف با کمک الگوریتم کونی مورچه ها بررسی کردیم و راه حلی که پیشنهاد دادیم اضافه کردن یک قابلیت به مورچه ها بود. این قابلیت داشتن حافظه محدود در مورچه ها است. (ما این مورچه ها را مورچه های مصنوعی نام گذاری کردیم، این مورچه ها مهمترین ویژگی های مورچه های واقعی رو دارن بعلاوه یک سری قابلیت اضافه که باعث بهبود الگوریتم كلوني مورچه ها میشه)
پیش از ادامه مطلب در صورتن نیاز مطلب که در مورد مسئله حلقه در گراف را قبلا مطرح کردیم یک بار مرورو کنید تا ابهامی به وجود نیاید.

خوب بریم سراغ سوال اصلی: چطوری اضافه کردن حافظه محدود، مسئله حلقه در کوتاهترین مسیر در گراف رو حل میکنه؟

مورچه های مصنوعی از این حافظه برای نگهداری دو نوع اطلاعات استفاده میکنند

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

حذف کردن مسیرهای که در آنها حلقه وجود دارد.
ارزیابی کیفیت مسیرهای که که توسط مورچه ها برای رسیدن به غذا (مقصد) ایجاد شده است – دقت داشته باشید این ارزیابی کاملا تخمینی است، و ممکن است دقیق نباشد. نکته مهم این است که این تخمین کمک می کند تا راه حل بهتری پیدا شود.
اضافه کردن قابلیت حافظه محدود به مورچه ها و تبخیر فرمون (که قبلا معرفی کردیم) به الگوریتم 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 مورچه های مصنوعی هنگام برگشت مسیری رو که از لانه تا غذا طی کرده اند را به یاد دارند (آن را در حافظه خود ذخیره کرده اند). مورچه های مصنوعی همچنین هزینه این مسیر را نیز محاسبه کرده اند و آن را نیز ذخیره کرده اند . (هزینه هر چیزی می تونه باشه، مثلا طول مسیر طی شده از لانه تا غذا)
با استفاده از این داده ها مورچه های مصنوعی می توانند هزینه مربوط به مسیرهای متفاوتی که تا حالا طی نموده اند و به غذا رسیده اند را با یکدیگر مقایسه کنند و کیفیت یک مسیر را نسبت به بقیه مسیرهای که تا حالا کشف کرده اند را تعیین کنند. همانطور که قبلا بیان کردیم وقتی مورچه ها تنها در مد حرکتی برگشت هستند بر روی مسیر فرمون می پاشن. میزان پاشیدین فرمون روی مسیر به کیفیت مسیر که محاسبه کردن بستکی داره. هر چه کیفیت مسیر بهتر باشه میزان فرمونی که روی مسیر می پاشن بیشتر و برعکس هر چه کیفیت پایین تر باشه، میزان فرمون کمتری روی مسیر می پاشن. (اطلاعات کامل در مورد انواع مد حرکتی مورچه ها در این مطلب می تونید مطالعه کنید)

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

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