Symmetrical Hierarchical Stochastic Searching on the Line in Informative and Deceptive Environments

Junqi Zhang, Yuheng Wang, Cheng Wang, Mengchu Zhou

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

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.10.618 is an approximate value of the golden ratio conjugate [1].Yazidi et al. [2] demonstrated that HSSL's effective range must be greater than the value of golden ratio and they use 0.618 to substitute the value of golden ratio. Hereinafter, we also use quantity 0.618 to denote the conjugate of the golden ratio.

Original languageEnglish (US)
Article number7428922
Pages (from-to)626-635
Number of pages10
JournalIEEE Transactions on Cybernetics
Volume47
Issue number3
DOIs
StatePublished - Mar 2017

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering

Keywords

  • Binary search
  • discretized learning
  • learning mechanism (LM)
  • stochastic point location (SPL) problem
  • stochastic search
  • symmetrical tree

Fingerprint Dive into the research topics of 'Symmetrical Hierarchical Stochastic Searching on the Line in Informative and Deceptive Environments'. Together they form a unique fingerprint.

Cite this