A Fuzzy-Evaluation-Based Constructive Heuristics Generation Framework for Stochastic Resource Allocation

The stochastic resource allocation (SRA) problem, commonly seen in the decision-making of complex systems, is a typical combinatorial optimization challenge that seeks optimality, quickness, as well as generality. Among various SRA algorithms, constructive heuristics (CH) such as greedy algorithms construct feasible solutions by prioritizing optional resource-task allocation pairs based on a predefined evaluation criterion. They are very suitable for real-time decision-making due to their simplicity and low computational complexity. However, relying on a single fixed criterion can impair optimality and generality. To achieve a generalized expression for the criterion, this paper establishes a fuzzy evaluation system that determines the component priorities by leveraging SRA problem features, enabling diversified and flexible solution construction. Furthermore, for the sake of generality, this paper proposes a fuzzy-evaluation-based constructive heuristics generation framework (FCHG), which generates an ensemble of complementary CHs through automatic training. FCHG adopts an adversarial coevolution mechanism, using the SRA instance generator and evolutionary algorithms to realize competition-based coevolution between the SRA instances and CHs. For SRA problem-solving, the CH ensemble obtained by FCHG can construct multiple SRA solutions efficiently, and the best one will serve as the final solution. Comparative experiments against state-of-the-art algorithms, covering instances with varying scales and structural characteristics, demonstrate the comprehensive superiority of the CH ensemble in solving the SRA problem in terms of optimality, quickness, generality, and numerical stability.