کلونی مورچه ها : این بار مورچه ها الگوی انسانها میشوند ! ” بخش دوم “

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

کلونی مورچه ها : این بار مورچه ها الگوی انسانها میشوند ! ” بخش دوم “ : نمونه دیگر و بارزی از Stigmergy را می توان در پیدا کردن کوتاهترین مسیر توسط مورچه ها مشاهده کرد. یکی از مسائلی که به وسیله پژوهشگران مطالعه شده است این است که بسیاری ازحیوانات نابینا مانند مورچه ها چگونه می توانند کوتاه ترین مسیر را از لانه تا منبع غذایی بیابند.

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

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

با توجه به شکل 1 چون در مسیر ها هیچ فرمونی وجود ندارد مورچه ها به صورت تصادفی مسیری از F بهN  را انتخاب می کنند و در مسیر ماده فرمون را بر جای می گذارند. مورچه های دیگر مسیری را انتخاب می کنند که دارای ماده ی فرمون بیشتری است. نکته ای که در اینجا حائز اهمیت است مسئله تبخير شدن فرمون بر جاي گذاشته شده است که بر این اساس مسیر هایی که طولانی تر هستند به علت اینکه رفت و برگشت در این مسیر ها  زمان زیادی صرف می کند بنابراین فرمون تیخیر می شود یا از شدت ماده فرمون کاسته می شود و مورچه ها دیگر این مسیر ها را انتخاب نمی کنند، اما مسیر هایی که کوتاه تر هستند و زمان عبور از این مسیر ها کم است بنابراین دارای فرمون بیشتری هستند چون عبور و مرور در این مسیر در زمان کمتری اتفاق می افتد،بنابراین مورچه های دیگر این مسیر برای عبور انتخاب می کنند.

استفاده از رفتار مورچه ها در مسیریابی شبکه های کامپیوتری
اطلاعات بر روي شبکه بصورت بسته هاي اطلاعاتي کوچکي (Packet) منتقل مي شوند. هر يک از اين بسته ها بر روي شبکه در طي مسير از مبدا تا مقصد بايد از گره هاي زيادي که مسيرياب (Router) نام دارند عبور مي کنند. برای پیدا کردن کوتاه ترین مسیر بین گره مبدا و گره مقصد ابتدا تعداد مشخصی بسته (مورچه) را بطور تصادفی در گره های موجود قرار می دهیم و بسته ها (مورچه ها) طبق مقدار فرمونی که در مسیر منتهی به گره بعدی وجود دارد، گره بعدی را انتخاب می کنند. در ابتدای الگوریتم فرمون موجود در تمامی مسیرها برابر فرض می شود. با حرکت مورچه ها مقدار فرمون در مسیرهای پیموده شده ، تغییر می کند.
برای مثال ساده شکل 2 را در نظر بگیرید: در ابتدا از گره  S بسته ها را ارسال می کنیم، هر بسته مقدار مشخصی فرمون (شمارنده) در مسیر بر جای می گذارد اگر طول مسیر بیشتر از 2 باشد به تدریج از شدت فرمون (شمارنده) کاسته می شود و اگر طول مسیر از 10 بیشتر باشد فرمون حذف می شود. بسته ای که از  S به A می رسد مقدار زمانی (هزینه) که مصرف می کند 2 است، سپس در گره A  با  صرف مقدار زمان 1 به گره B می رسد از گره B با صرف مقدار زمان 1 به G (مقصد) می رسد(مقدار زمان طی شده 4=1+1+2)، بسته ارسال شده دوباره از همان مسیر برگشت داده می شود که در مسیر برگشت هم مقدار مشخصی فرمون در مسیر بر جای می گذارد.  همزمان با این اعمال بسته ای  از مسیر S به B و از آن به G  با مقدار زمان 6=1+5 را طی می کند و بر گردد و همچنین بسته ای از S به C و از C به G  با مقدار زمان 5=2+3  ارسال می شود و برمی گردد در مرحله بعدی بسته ی دیگری را می خواهیم از S به G ارسال کنیم در این صورت مسیرS>A>B>G را انتخاب می کنیم زیرا عبور و مرور در این مسیر در زمان کمتری صورت می گیرد و دارای مقدار فرمون بیشتری است. در این مثال فرض بر این است که بسته ها و گره ها هیچ اطلاعاتی از قبیل طول مسیر ها، زمان ارسال از یک گره به گره دیگر و … در خود ذخیره نمی کنند، و تنها اطلاعاتی که در خود ذخیره می کنند مقدار فرمون هر مسیر است.    

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

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