大家好，欢迎来到IT知识分享网。
(图片来源于: Christine Daniloff/麻省理工学院)
引言
蚂蚁，是一种典型的社会性昆虫，一蚁蚂蚁群会进行明确地分工协作。它们非常擅于发现自己附近的其他蚂蚁的浓度。在一些公共活动，特别是蚁群蚂蚁选择新的蚁巢的表决程序中，这项能力起到至关重要的作用。生物学家一直都具有这样的怀疑：蚂蚁会基于种群密度，估算探索环境的过程中遇到其他蚂蚁的频率。来自麻省理工学院计算机科学和人工智能实验室的研究人员，发表的一项新的理论论文，支持了这一理论。论文于这个月发表在计算机协会的分布式计算研讨会上。论文展示了对于环境的随机探索的观察值，迅速的收敛于对于种群密度的精准估算。实际上，他们按照理论上的可能性，尽快地收敛。除了支持了生物学家的假设，理论框架，也应用于社交网络的分析，机器人群的集体决策，自组织网络的通讯，例如分布在恶劣环境中的低成本传感器网络。
“如果，一群人在某个区域周围随机行走，凭直觉我们会认为，他们相互遇到的次数，取决于人口密度，”Cameron Musco，麻省理工学院电气工程和计算机科学的研究生，这项论文的合著者称。“我们现在所做的，正是是直觉后面的严谨分析，结果也认为估算是很好的，并不是一些粗糙的估算。作为一个时间函数，它将变得越来越精确，并且达到你所希望的速度。”
(图片来源于：Christine Daniloff/麻省理工学院)
随机游走
Musco和他的合著者，NEC软件和工程学教授Nancy Lynch，以及Lynch小组的一位博士后，将蚂蚁的环境概括为一个网格，让一些数量的蚂蚁随机分布其中。所关注的蚂蚁，被称为探索者 ，开始在一些网格中，以同样的概率，移动到相邻的单元格。然后，以同样的概率，一个一个的单元格移动，如此往复。在统计学上，这个被称为“随机游走”。探索者计算着每个单元格中居住的其他蚂蚁的数目。
在他们的论文中，研究人员对比了随机游走和随机采样，从网格中随机的选择单元格，计算蚂蚁的数量。这两个策略的精准性，随着每个附加的样本而提高，但是，随机游走和随机采样一样，事实上，显著地随着真实的种群密度而收敛。
这个十分重要，在许多实践案例中，随机采样并不是一个好的选择。例如，假定你需要写一个算法分析在线社交网络，分析有多少人自称是喜欢科技的。如果没有公开可以获得的网络成员列表，唯一的探索途径，就是选择单个成员并且追踪连接数。一那个样
相似地，在自组织网络中，一个给定的设备，只知道在它附近的设备的位置；它不知道整个网络的布局。使用随机游走算法，从多个设备上聚集信息，比实现一个描述整个网络的算法，要容易得多。
重复遭遇
研究人员的结果，让人很吃惊，因为，在每一步的随机游走中，探索者，具有很大的可能性，返回到他们已经访问过的某个单元。随机游走可能比随机采样，具有更高的概率，“过采样”特殊的单元。
一开始，Musco就说，他和他的同事，假定评估种群密度的算法必须克服这种“重复遭遇”的可能性。但是，他们尝试过滤掉“过采样”的数据，似乎算法性能并没有改善，反而更差。
最终，他们终于解释了这一原因。理论上，“如果你在一个网格中随机游走，你不会碰到每个人，因为你不会穿越整个网格，”Musco说。“所以，在远端的网格中的某人，我几乎没有可能碰到。但是，随着我碰见那些人机会更少，意味着我碰见附近的人机会更多。因为有些远方的人，我可能永远无法碰见。所以作为这一事实的一种补偿，我需要计算所有附近的我接触过的人。它在某种程度进行了完美地平衡。但是，这不是很直观，我们需要有一段时间才能实现。”
总结
研究人员用来对蚂蚁的环境进行建模的网格，是一种特殊的数据结构，称为“图”。图，由“节点”和“边”组成。“节点”以圆圈表示，“边”以连接节点的线段表示。在一个网格中，每个单元都是一个节点，并且只和它直接相邻的单元分享边。
然而，研究人员的分析技术，可以应用于任何的图。例如，描述社交网络中，哪些成员是连接的，或者自组织网络中，哪些设备在相互通信范围内。
如果一个图没有很好的连接，例如，它只是一个节点的链，每个节点只和两个相邻的节点连接，那么“过采样”的问题就出现了。例如，在一个100个节点的链中，一个探索者采取随机游走策略，可能在穿过5到6个相同节点的时候不断地卡住。
但是，一旦从同样的节点开始，进行两个随机游走，就可能向两个方向扩张，就像描述通信网络的图一样，随机游走实质上就是保持和随机采样一样。
更进一步的说，在新论文中，研究人员分析了由单个探索者进行的随机游走。然而，对于多个探索者的联合观察，可能更快的得到一个更精准的估算。“如果他们是机器人，而不是蚂蚁，他们可能从相互交谈中受益，这就是我的看法。“Musco说。
“Nancy的领域是分布式计算，具有不同的策略和方法，对于生物学家来说都是未知的，”亚利桑那大学，研究社会性昆虫的生态学和进化生物学副教授，Anna Dornhaus说。“Nancy [Lynch]实现这些前沿工具，实际上，对于生物学家来说，十分有价值。她的跨学科研究尝试，让我们可以真正理解这些生物学系统。”
“人们，经常争论蚂蚁或者蜜蜂是否能够识别其他个体，”Dornhaus解释道，“这项研究展示了至少在这个情境下，结果很明显。对于我来说，这就是这项研究的惊人之处。并且，他们能够在数学上证明，这个策略有多么精准。”
消息来源：
http://news.mit.edu/2016/ant-colony-behavior-better-algorithms-network-communication-0713
更多精彩内容，请关注微信公众号： IntelligentThings
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/181938.html
