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

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

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

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

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

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

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

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

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

http://mrmining.ir