Symmetrical Hierarchical Stochastic Searching on the Line in Informative and Deceptive Environments
针对现有分层随机搜索算法无法在欺骗性环境中定位目标且无法识别环境类型的问题，提出对称分层随机搜索，通过扩展二叉树搜索结构为对称形式，使算法能在信息性和欺骗性环境中收敛到静态或动态目标参数。
A stochastic point location (SPL) problem aims to find a target parameter on a 1-D line by operating a controlled random walk and receiving information from a stochastic environment (SE). If the target parameter changes randomly, we call the parameter dynamic; otherwise static. SE can be 1) informative (p > 0.5 where p represents the probability for an environment providing a correct suggestion) and 2) deceptive (p <; 0.5). Up till now, hierarchical stochastic searching on the line (HSSL) is the most efficient algorithms to catch static or dynamic parameter in an informative environment, but unable to locate the target parameter in a deceptive environment and to recognize an environment's type (informative or deceptive). This paper presents a novel solution, named symmetrical HSSL, by extending an HSSL binary tree-based search structure to a symmetrical form. By means of this innovative way, the proposed learning mechanism is able to converge to a static or dynamic target parameter in the range of not only 0.6181 <; p <; 1, but also 0 <; p <; 0.382. Finally, the experimental results show that our scheme is efficient and feasible to solve the SPL problem in any SE.