Abstract
The stochastic resource allocation (SRA) problem is an extensive class of combinatorial optimization problems widely existing in complex systems such as communication networks and unmanned systems. In SRA, the ability of a resource to complete a task is described by certain probability, and the objective is to maximize the reward by appropriately assigning available resources to different tasks. This paper is aimed at an important branch of SRA, that is, stochastic SRA (SSRA) for which the probability for resources to complete tasks is also uncertain. Firstly, a general SSRA model with multiple independent uncertain parameters (GSSRA-MIUP) is built to formulate the problem. Then, a scenario-based reformulation which can address multi-source uncertainties is proposed to facilitate the problem-solving process. Secondly, in view of the superiority of the differential evolution algorithm in real-valued optimization, a discrete version of this algorithm was originally proposed and further combined with a specialized local search to create an efficient hybrid optimizer. The hybrid algorithm is compared with the discrete differential evolution algorithm, a pure random sampling method, as well as a restart local search method. Experimental results show that the proposed hybrid optimizer has obvious advantages in solving GSSRA-MIUP problems.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Saki H, Shojaeifard A, and Martini M G, Stochastic resource allocation for hybrid spectrum access OFDMA-based cognitive radios, Proceedings of the IEEE International Conference on Communications (ICC), London, England, June 8–12, 2015, 7750–7755.
Xu L, Yang Y, and Li Y, Resource allocation of limited feedback in clustered wireless mesh networks, Wirel. Person. Comm., 2014, 75(2): 901–913.
Li X, Shi Y, Wang X J, et al., Efficient link scheduling with joint power control and successive interference cancellation in wireless networks, Science China Information Sciences, 2016, 59(12): No.122301.
Wang X and Giannakis G B, Resource allocation for wireless multiuser OFDM networks, IEEE Trans. Infor. Theor., 2011, 57(7): 4359–4372.
Wang L Y, Lin F, and Yin G, Network robustness depth and topology management of networked dynamic systems, J. Syst. Sci. Complex., 2016, 29(1): 1–21.
Chu H Y, Xu P P, Wang W, and Yang C C, Joint relay selection and power control for robust cooperative multicast in mmWave WPANs, Science China-Information Sciences, 2016, 59(8): No.082301.
Yin L B and Han L Y, Risk management for international portfolios with basket options: A multi-stage stochastic programming approach, Journal of Systems Science & Complexity, 2015, 28(6): 1279–1306.
Li M H, Huang G M, Wu X L and Zhou D, A yield-enhanced global optimization methodology for analog circuit based on extreme value theory, Science China-Information Sciences, 2016, 59(8): No.082401.
Melouk S H, Fontem B A, Waymire E, et al., Stochastic resource allocation using a predictorbased heuristic for optimization via simulation, Comput. Oper. Res., 2014, 46: 38–48.
Plamondon P and Chaib-Draa B, Stochastic resource allocation in multiagent environments: An approach based on distributed Q-values and bounded real-time dynamic programming, Int. J. Artif. Intell. Tool., 2012, 21(1): 1250003.
Kuo W and Wan R, Recent advances in optimal reliability allocation, IEEE Trans. Syst. Man, Cybern. A — Syst. Human., 2007, 37(2): 143–156.
Chen J, Xin B, Peng Z H, et al, Evolutionary decision-makings for dynamic weapon-target assignment problem, Sci. China Ser. F: Inf. Sci., 2009, 52(11): 2006–2018.
Castanon D A and Wohletz J M, Model predictive control for stochastic resource allocation, IEEE Trans. Autom. Contr., 2009, 54(8): 1739–1750.
Xin B, Chen J, Peng Z H, et al, An efficient rule-based constructive heuristic to solve dynamic weapon-target assignment problem, IEEE Trans. Syst. Man Cybern. A — Syst. Human., 2011, 41(3): 598–606.
Xin B, Chen J, Zhang J, Dou L H, and Peng Z H, Efficient decision-makings for dynamic weapontarget assignment by virtual permutation and tabu search heuristics, IEEE Trans. Syst. Man Cybern. C — Appl. Rev., 2010, 40(6): 649–662.
Li J, Chen J, Xin B, et al., Solving the uncertain multi-objective multi-stage weapon target assignment problem via MOEA/D-AWA, Proceedings of the 2016 IEEE Congress on Evolutionary Computation (CEC 2016), Vancouver, Canada, July 24–29, 2016, 4934–4941.
Liu B D, Zhao R Q, and Wang G, Uncertain Programming with Applications, Tsinghua University Press, Beijing, 2003.
Das S, Mullick S S, and Suganthan P N, Recent advances in differential evolution — An updated survey, Swarm Evol. Comput., 2016, 27: 1–30.
Xin B, Chen J, Zhang J, et al, Hybridizing differential evolution and particle swarm optimization to design powerful optimizers: A review and taxonomy, IEEE Trans. Syst. Man Cybern. C — Appl. Rev., 2012, 42(5): 744–767.
Onwubolu G C and Davendra D, Differential Evolution: A Handbook for Global Permutation- Based Combinatorial Optimization, Springer-Verlag, Berlin, 2009.
Wang L and Liu B, Particle Swarm Optimization and Scheduling Algorithms, Tsinghua University Press, Beijing, 2008.
Chen J, Xin B, Peng Z H, et al, Optimal contraction theorem for exploration-exploitation tradeoff in search and optimization, IEEE Trans. Syst. Man Cybern. A — Syst. Human., 2009, 39(3): 680–691.
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported by the National Natural Science Foundation of China under Grant No. 71361130011.
This paper was recommended for publication by Editor SUN Jian.
Rights and permissions
About this article
Cite this article
Fan, G., Huang, H. Scenario-based stochastic resource allocation with uncertain probability parameters. J Syst Sci Complex 30, 357–377 (2017). https://doi.org/10.1007/s11424-017-6178-5
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11424-017-6178-5