Memetic algorithm for real-time combinatorial stochastic simulation optimization problems with performance analysis.

Area of Science:

• Operations Research
• Computer Science
• Engineering Optimization

Background:

• Combinatorial Stochastic Simulation Optimization (CSSO) problems present significant computational challenges due to large discrete solution spaces.
• Real-time decision-making in complex systems requires efficient optimization algorithms capable of handling uncertainty and scale.

Purpose of the Study:

• To propose a novel three-phase memetic algorithm (MA) for addressing real-time CSSO problems.
• To enhance the search for suboptimal solutions in large discrete spaces.
• To validate the algorithm's performance on a real-world problem.

Main Methods:

• Phase 1: Genetic algorithm with an offline global surrogate model to identify diverse initial solutions.
• Phase 2: Probabilistic local search with an online surrogate model to find local optima.
• Phase 3: Optimal computing budget allocation to select the best solution from identified local optima.

Main Results:

• The proposed MA was applied to an assemble-to-order problem, a representative CSSO challenge.
• Extensive simulations demonstrated superior performance compared to existing methods.
• The algorithm achieved solutions within 1% of the true optimum with 99% probability.

Conclusions:

• The three-phase memetic algorithm is effective for real-time CSSO problems.
• The method offers a robust approach for finding high-quality solutions in complex optimization landscapes.
• The rigorous analysis confirms the algorithm's efficiency and accuracy.