2006 | OriginalPaper | Chapter
On Allocating Limited Sampling Resources Using a Learning Automata-based Solution to the Fractional Knapsack Problem
Authors : Ole-Christofier Granmo, B. John Oommen
Published in: Intelligent Information Processing and Web Mining
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper, we consider the problem of allocating limited sampling resources in a “real-time” manner with the purpose of estimating multiple binomial proportions. This is the scenario encountered when evaluating multiple web sites by accessing a limited number of web pages, and the proportions of interest are the fraction of each web site that is successfully validated by an HTML validator [11]. Our novel solution is based on mapping the problem onto the so-called nonlinear fractional knapsack problem with separable and concave criterion functions [3], which, in turn, is solved using a
Team
of deterministic Learning Automata (LA). To render the problem even more meaningful, since the binomial proportions are unknown and must be sampled, we particularly consider the scenario when the target criterion functions are
stochastic
with
unknown
distributions. Using the general LA paradigm, our scheme improves a current solution in an online manner, through a series of informed guesses which move towards the optimal solution. At the heart of our scheme, a team of deterministic LA performs a controlled random walk on a discretized solution space. Comprehensive experimental results demonstrate that the discretization resolution determines the precision of our scheme, and that for a given precision, the current resource allocation solution is consistently improved, until a near-optimal solution is found – even for periodically switching environments. Thus, our scheme, while being novel to the entire field of LA, also efficiently handles a class of resource allocation problems previously not addressed in the literature.