A Clustering-Based Adaptive Hybrid Algorithm for the Stochastic Resource Allocation Problem With Time Windows
针对资源可能随机失败且需在时间窗内分配的问题，提出一种混合变量优化算法，用聚类保持种群多样性，在大量实例上优于现有算法。
The stochastic resource allocation (SRA) problem is widely encountered in complex systems, where the resource may probabilistically fail to complete its assigned task. In practical scenarios, the assignment of resources to tasks should be handled within specified time windows, and the success probability of each assignment changes over time. Such a problem can be represented as the SRA problem with time window (SRA-TW). Both the discrete assignment relationship and the corresponding continuous-valued assignment time are indispensable in the decision scheme of SRA-TW. This mixed-variable nature poses a great challenge for optimization. Based on these requirements, SRA-TW is formulated as a mixed-variable optimization problem (MVOP) with temporal constraints. To solve this problem, an adaptive hybrid algorithm with clustering-based diversity preservation (<roman xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">AHA</roman><sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><roman>CDP</roman></sub>) is proposed. Firstly, a variable-length hybrid encoding method with constructive decoding is proposed for incremental constraint handling. Secondly, a hybrid search mechanism incorporating a matching-similarity-guided adaptive selection method is proposed to balance the search in discrete and continuous subspaces. Then, a clustering-based diversity preservation strategy is developed, facilitating a good distribution of the population. Finally, an SRA-TW instance generator considering various problem features is designed, so as to comprehensively validate the algorithm’s performance. The statistical results over numerous instances demonstrate the superiority of <roman xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">AHA</roman><sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><roman>CDP</roman></sub> over prevailing algorithms in addressing SRA-TW.