目标随机移动情形下的随机搜索首达问题研究

Note that stochastic search can be found in many different fields, such as foraging behavior of animals, target search in ad-hoc network and big-data environments, and the targets also randomly move in many cases. We analyze the first-passage problems in stochastic search with mobile targets. Our interest focuses on the effect of network topology, network size, the location of the searchers or targets on the search efficiency. Firstly, we model stochastic search with mobile targets by random collision of two different particles on complex networks, which can be depicted with multidimensional random processes. Then we reduce the dimension and the complexities of the random processes by means of function transformation for the location variables. For the low-dimensional random processes which obtained from function transformation, we analyze the efficiency of random search from easy to difficult by comprehensively using the classic methods, such as Laplace transform, Fourier transform, spectral decomposition, and etc. Finally, we compare the results just obtained with the results of stochastic search with immobile targets and disclose the effects of target moving on the search time and the probability of finding the target successfully.

基于动物觅食、ad-hoc网络、大数据环境中都会呈现出随机搜索行为，且很多场合目标位置也会随机移动。本课题拟在目标随机移动情形下，对随机搜索中搜索者首达目标位置的时间、概率等首达问题展开研究。重点分析网络拓扑、网络规模、搜索者及目标数量、初始位置分布等因素对搜索效率的影响。首先，我们把目标移动情形的随机搜索首达问题抽象为两种不同粒子的随机游走相遇问题，并用多维随机过程来描述。随后通过对位置变量的变换处理，对多维随机过程进行降维处理，降低问题的复杂度。 对于降维以后的随机过程，我们拟组合应用拉普拉斯变换、傅里叶变换和谱分解等经典随机游走分析方法，按照粒子数量先少后多的顺序分析研究影响随机搜索效率的因素，并把所得到的结果与目标静止结果进行比较，考查目标移动搜索时间以及搜索成功概率的影响。

随机搜索是自然界和人类社会活动中很常见行为，随机搜索的首达问题研究成果对于随机搜索的优化、化学反应的控制有着重要研究意义。本课题在目标随机移动情形下，对随机搜索中搜索者与目标的首次相遇时间、概率等首达属性展开研究。重点分析网络拓扑、网络规模、搜索者及目标数量、初始位置分布等因素对搜索效率的影响。我们选取有代表性的网络（如B-A无标度网络、E-R随机网络、W-S小世界网络、规则格、规则分支网络、comb结构等等），并在这些网络上建立随机搜索的马尔科夫模型，通过理论解析结合计算机模拟的方法，对搜索者首达目标的时间、概率进行分析，得到了一些有意义的结论。. 我们发现并证明了广泛存在于通用网络上两粒子首次相遇问题的通用规律。若搜索者和目标都同时起始于同一位置，对二部图，平均意义下，目标移动情形的平均首达时间恰为目标静止情形的1/2；对非二部图，目标移动情形的平均首达时间与目标静止情形的结论完全相等。我们的研究还发现若搜索者和目标起始位置服从稳态分布，总体上平均而言，目标移动会加速目标搜索过程。但在不同的网络结构上，这种加速程度是很不相同的。若目标起始位置固定，搜索者起始位置服从稳态分布，目标随机移动有时会加速搜索者发现目标的过程，有时会减慢搜索者发现目标的过程。因而可利用初始位置、网络结构参数，来优化随机搜索。. 我们还对随机游走策略、搜索者与目标的数量、网络结构参数等因素对随机搜索的效率的影响进行了深入研究，在一定的条件下，基于以上因素，进一步对随机搜索的效率进行优化。我们也对随机搜索在计算机及网络安全领域的应用展开了研究。本项目的成果对于随机搜索的优化，具有重要的研究意义。. 本项目的成果主要以公开发表论文的形式来体现，到目前为止，共发表标注论文19篇，其中17篇SCI检索。申请和获批国家发明专利1件。培养博士后、博士生、研究生多名。