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

به نظر می رسد که مورچه ها در برآورد تراکم مورچه های دیگر در همسایگی شان به شدت خوب هستند. به نظر می رسد که این توانایی نقشی در فعالیت های گروهی متعدد دارد، بخصوص در روند رأی گیری، که به وسیله آن، یک کلونی مورچه پست جدیدی را انتخاب می کند.

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

این نظریه جدیداً تأییدیه ای را از یک مقاله نظری دریافت می کند که محققان از آزمایشگاه هوش مصنوعی و علوم کامپیوتری ام آی تی در انجمنی برای محاسبه همایش ماشینی درباره اصول کنفرانس های محاسبات توزیع شده بعداً در این ماه ارائه می دهند. این مقاله نشان می دهد که مشاهدات از بررسی تصادفی محیط بسیار سریع به برآورد دقیقی از تراکم جمعیت می رسد.

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

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

قدم زدن تصادفی

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

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

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

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

برخوردهای مکرر

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

موسکو می گوید در ابتدا او و همکارانش فرض کردند که این یک احتمال بود که یک الگوریتم برای برآورد تراکم جمعیت پیروز شود. اما تلاش آن ها برای فیلتر کردن داده های نمونه برداری شده به نظر می رسید که عملکرد الگوریتم را به جای بهبودی بدتر می کرد. در نهایت آن ها توانستند دلیل آن را بصورت نظری توضیح دهند.

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

نتایج کلی

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

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

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

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

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

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

دورهاوس توضیح می دهد: "مردم همیشه بحث می کنند که آیا مورچه ها یا زنبورها می توانند افراد دیگر را تشخیص دهند؟ این مقاله نشان می دهد که حداقل در این بافت، این کار لزومی ندارد. برای من این اصلی ترین نتیجه حیرت آور است. اما البته، آن ها همچنین می توانند از نظر ریاضیاتی ثابت کنند که آن استراتژی تا چه حد دقیق است."