Determining Optimal Polling Frequency Using a Learning Automata-based Solution to the Fractional Knapsack Problem

General Information

Download Determining Optimal Polling Frequency Using a Learning Automata-based Solution to the Fractional Knapsack Problem as PDF (724 KB) .

Title: Determining Optimal Polling Frequency Using a Learning Automata-based Solution to the Fractional Knapsack Problem.
Author(s): Ole-Christoffer Granmo, B. John Oommen, Svein Arild Myrer, Morten Goodwin.
Published date: June 2006.
Published at: IEEE International Conferences on Cybernetics & Intelligent Systems (CIS) and Robotics, Automation & Mechatronics (RAM), Bangkok, Thailand 2006

Abstract


Previous approaches to resource allocation in Web monitoring target optimal performance under restricted capacity constraints (Pandey et al., 2003; Wolf et al., 2002). The resource allocation problem is generally modelled as a knapsack problem with known deterministic properties. However, for practical purposes the Web must often be treated as stochastic and unknown. Unfortunately, estimating unknown knapsack properties (e.g., based on an estimation phase (Pandey et al., 2003; Wolf et al., 2002)) delays finding an optimal or near-optimal solution. Dynamic environments aggravate this problem further when the optimal solution changes with time. In this paper, we present a novel solution for the nonlinear fractional knapsack problem with a separable and concave criterion function (Bretthauer and Shetty, 2002). To render the problem realistic, we consider the criterion function to be stochastic with an unknown distribution. At every time instant, our scheme utilizes a series of informed guesses to move, in an online manner, from a "current" solution, towards the optimal solution. At the heart of our scheme, a game of deterministic learning automata performs a controlled random walk on a discretized solution space. Comprehensive experimental results demonstrate that the discretization resolution determines the precision of our scheme. In order to yield a required precision, the current resource allocation solution is consistently improved, until a near-optimal solution is found. Furthermore, our proposed scheme quickly adapts to periodically switching environments. Thus, we believe that our scheme is qualitatively superior to the class of estimation-based schemes.

BIBTEX


@article{graoommyrolspolling2006,
author{Ole-Christoffer Granmo, B. John Oommen, Svein Arild Myrer and Morten Goodwin Olsen},
title{Determining Optimal Polling Frequency Using a Learning Automata-based Solution to the Fractional Knapsack Problem},
booktitle{IEEE CIS-RAM},
year{2006},
month{June}
}

The author of this document is:
Morten Goodwin
E-mail address is:
morten.goodwin [at] uia.no
Phone is:
+47 95 24 86 79