Metaheuristic framework improves discrete optimization within strict time limits
A Metaheuristic Optimization Framework for Discrete Optimization under Strict Time Limits
Neural and Evolutionary Computing
Summary
Finding the best solution quickly to hard problems is important in real-time systems. The authors created a new metaheuristic optimization framework called STILO, combining different algorithms to work well when there is very little time for computing. They tested it on various problems and found that some techniques worked better depending on how much time was available. Their work shows that what method is best depends on the problem, the specific case, and the time you have to solve it.
What this means in practice
- •For industrial scheduling teams: Generate near-optimal scheduling solutions rapidly when only milliseconds are available for decision making.
- •For embedded systems engineers: Integrate STILO’s time-aware optimization methods to improve performance in devices with very limited computing time.
Authors
Umut Çalıkyılmaz, Nitin Nayak, Sven Groppe
Abstract
Real-time applications often rely on optimization approaches that can find high-quality solutions to hard problems on the order of milliseconds. Metaheuristic optimization frameworks (MOFs) are useful tools for such tasks, as they provide large sets of general-purpose search mechanisms that can return solutions under different computational budgets. However, existing work largely overlooks the available computation time as an explicit dimension of analysis. In this work, we introduce STILO, a MOF specifically designed for optimization under strict time limits. STILO integrates fine-grained configuration spaces for ant colony optimization (ACO), genetic algorithm (GA), and simulated annealing (SA), combining existing and novel operators. We performed experiments using both synthetic and benchmark instances of various discrete optimization problems. The results indicate that the proposed discrete distance calculation mechanism for SA is useful for optimization under strict time limits. They also show that the relative effectiveness of the proposed problem-independent graph structures for ACO can vary across time limits, even for the same instance characteristics. More generally, the results demonstrate that the effectiveness of algorithm families and operators depends not only on the problem type, but also on the characteristics of the instance and the available computational budget.