Abstract
This papers deals with the Stochastic Non-linear Fractional Equality Knapsack (NFEK) problem which is a fundamental resource allocation problem based on incomplete and noisy information [2, 3]. 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 reckoned as the Two-timescale based Learning Automata (T-TLA) solves the NFEK problem by performing updates on two different timescales. To the best of our knowledge, this is the first tentative in the literature to design an LA that operates with two-time scale updates. Furthermore, the T-TLA solution is distinct from the first-reported optimal solution to the problem due to Granmo and Oommen [2, 3] which resorts to utilizing multiple two-action discretized LA, organized in a hierarchical manner, so as to be able to tackle the case of multi-materials. Hence, the T-TLA scheme mitigates the complexity of the state-of-the-art solution that involves partitioning the material set into two subsets of equal size at each level. We report some representative experimental results that illustrate the convergence of our scheme and its superiority to the state-of-the-art [2, 3].
A. Yazidi—The author gratefully acknowledges the assistance of his PhD supervisor, Dr. John Oommen, a Chancellor’s Professor from Ottawa, Canada. John helped a lot with the style and language of this paper. He also very graciously provided me with some of the text when it concerned the introductory sections and the background material. These portions have been included here, in some cases verbatim, with his kind permission. Thank you John!!.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We hereafter use \(f_i'(x_i)\) to denote the derivative of the expected value function \(f_i(x_i)\) with respect to \(x_i\).
References
Benveniste, A., Métivier, M., Priouret, P.: Adaptive Algorithms and Stochastic Approximations, vol. 22. Springer, Heidelberg (2012)
Granmo, O.-C., Oommen, B.J.: Optimal sampling for estimation with constrained resources using a learning automaton-based solution for the nonlinear fractional knapsack problem. Appl. Intell. 33(1), 3–20 (2010)
Granmo, O.-C., Oommen, B.J.: Solving stochastic nonlinear resource allocation problems using a hierarchy of twofold resource allocation automata. IEEE Trans. Comput. 59(4), 545–560 (2010)
Granmo, O.-C., Oommen, B.J., Myrer, S.A., Olsen, M.G.: Learning automata-based solutions to the nonlinear fractional knapsack problem with applications to optimal resource allocation. IEEE Trans. Syst. Man Cybern. Part B Cybern. 37(1), 166–175 (2007)
Sastry, P.S., Magesh, M., Unnikrishnan, K.P.: Two timescale analysis of the alopex algorithm for optimization. Neural Comput. 14(11), 2729–2750 (2002)
Yazidi, A., Hammer, L.H., Jonassen, T.M.: On two-timescale approach for solving resource allocation problems. Unabridged Journal version of this paper (2017). (To be submitted for publication)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Yazidi, A., Hammer, H.L., Jonassen, T.M. (2017). Two-Timescale Learning Automata for Solving Stochastic Nonlinear Resource Allocation Problems. In: Benferhat, S., Tabia, K., Ali, M. (eds) Advances in Artificial Intelligence: From Theory to Practice. IEA/AIE 2017. Lecture Notes in Computer Science(), vol 10350. Springer, Cham. https://doi.org/10.1007/978-3-319-60042-0_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-60042-0_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-60041-3
Online ISBN: 978-3-319-60042-0
eBook Packages: Computer ScienceComputer Science (R0)