Learning automata-based solutions to stochastic nonlinear resource allocation problems
"Computational Intelligence" is an extremely wide-ranging and all-encompassing area. However, it is fair to say that the strength of a system that possesses "Computational Intelligence" can be quantified by its ability to solve problems that are intrinsically hard. One such class of NP-Hard problems concerns the so-called family of Knapsack Problems, and in this Chapter, we shall explain how a sub-field of Artificial Intelligence, namely that which involves "Learning Automata", can be used to produce fast and accurate solutions to "difficult" and randomized versions of the Knapsack problem (KP). Various increasingly complex versions of the KP have been discussed in the literature. The most complex of these is probably the stochastic Nonlinear Fractional Knapsack Problem (NFKP), which is a randomized version of the Fractional Knapsack Problem (FKP). The FKP concerns filling a knapsack of fixed volume with a mixture of n materials so as to attain a maximal value, where each material is characterized by its value per unit volume. Although the original problem can be posed in such abstract terms, we shall, at the outset, argue that it can be used to model a host of real-life problems. This Chapter introduces two novel solutions to the stochastic NFKP which involve a Team of deterministic Learning Automata (LA). The first solution is referred to as the decentralized Learning Automata Knapsack Game (LAKG). Using the general LA paradigm, this scheme improves a current solution in an online manner, through a series of informed guesses which move towards the optimal solution. The second solution is a completely new on-line LA system, namely, the Hierarchy of Twofold Resource Allocation Automata (H-TRAA) whose primitive component is a Twofold Resource Allocation Automaton (TRAA). The Chapter formally states the convergence properties of the TRAA and the H-TRAA, and also presents empirical results demonstrating "computationally intelligent" properties which are superior to those possessed by the traditional estimation-based methods.
|Keywords||Hierarchical Learning, Learning Automata, Nonlinear Knapsack Problems, Resource Allocation, Stochastic Optimization|
|Series||Studies in Computational Intelligence|
Granmo, O.-C. (Ole-Christoffer), & Oommen, J. (2009). Learning automata-based solutions to stochastic nonlinear resource allocation problems. Studies in Computational Intelligence. doi:10.1007/978-3-642-04170-9_1