Object partitioning using a hierarchy of stochastic automata

Abstract

Let Omega =(A/sub 1/,. . .,A/sub w/) be a set of W objects to be partitioned into R classes Pi =( Pi /sub 1/,. . ., Pi /sub R/) in such a way that the objects that are accessed (used) more frequently together lie in the same class. The elements of W are accessed by the users according to an unknown partitioning Theta . This problem, which is called the object partitioning problem (OPP) and has numerous applications in adaptive man-machine interface systems, is studied in its generality. The joint access probabilities of the objects are unknown, and the objective are accessed in groups of unknown size that may or may not be equal. A fast hierarchical stochastic learning automaton solution to the problem, which is known to be NP-hard, is proposed. The number of computations per iteration required by this method is logarithmic in the number of objects to be partitioned. Experimentally, the solution converges much faster than the best known algorithm that does not use learning automata.