- knapsack+%281%29.pdf (14M)
Applied Intelligence;November 2018, Volume 48, Issue 11
This paper deals with the Stochastic Non-linear Fractional Equality Knapsack (NFEK) problem which is a fundamental resource allocation problem based on incomplete and noisy information [7, 8]. The NFEK problem arises in many applications such as in web polling under polling constraints, and in constrained estimation. The primary contribution of this paper is a continuous Learning Automata (LA)-based, optimal, efficient and yet simple solution to the NFEK problem. Our solution is distinct from the first-reported optimal solution to the problem due to Granmo and Oommen [7, 8] which resorts to utilizing multiple two-action discretized LA, organized in a hierarchical manner which comes with extra implementation and computational complexity. In this work, we present an optimal solution to the problem using a continuous LA which does not involve mapping the materials onto a binary hierarchy. As opposed to the traditional family of Reward-Inaction (R-1) LA, our scheme is modified in order to accommodate non-absorbing barriers, thus guaranteeing convergence to the optimal allocation. The experimental results that we have presented for numerous simulations demonstrate the efficiency of our scheme and its superiority compared to the state-of-the-art in terms of peak performance.
Permanent URL (for citation purposes)