PaperlayerView exact revision on arXiv

Source-linked AI summary

TESO Tabu Enhanced Simulation Optimization for Noisy Black Box Problems

Bulent Soykan, Sean Mondesire, Ghaith Rabadi

arXiv:2512.24007v1cs.NEcs.AI

TL;DR

Noisy evaluations, costly simulations, and complex search spaces complicate simulation optimization. TESO combines adaptive search with tabu and elite memories to balance exploration and exploitation. On a queue optimization problem, it reached a final best mean objective value of 2.53 and showed complementary benefits from both memory components.

  • Problem

    Noisy simulation outputs, high evaluation costs, and complex landscapes make candidate quality difficult to assess and exploration–exploitation balance important.

    Source: §1 · p. 1, §2.1 · p. 3

  • Method

    TESO combines direct adaptive search with a Tabu List, stochastic aspiration, and Elite Memory to diversify and intensify search using mean estimates from replications.

    Source: §3.1 · p. 4

  • Results

    2.53 final best mean objective value was achieved by full TESO, close to the assumed true optimum of 2.52, with the lowest final-best-value standard deviation of 0.07 across macro-replications.

    Source: §4.5 · p. 8

  • Takeaways & Limitations

    On the queue problem, the Tabu List and Elite Memory played complementary roles, with the full TESO outperforming either component used alone.

    Source: §4.5 · pp. 8–9

    Validation is limited to a single, unimodal problem class, and TESO’s performance may be sensitive to internal parameters and its noise-decay schedule.

    Source: §5 · p. 10

Abstract

from arXiv · show

Simulation optimization (SO) is frequently challenged by noisy evaluations, high computational costs, and complex, multimodal search landscapes. This paper introduces Tabu-Enhanced Simulation Optimization (TESO), a novel metaheuristic framework integrating adaptive search with memory-based strategies. TESO leverages a short-term Tabu List to prevent cycling and encourage diversification, and a long-term Elite Memory to guide intensification by perturbing high-performing solutions. An aspiration criterion allows overriding tabu restrictions for exceptional candidates. This combination facilitates a dynamic balance between exploration and exploitation in stochastic environments. We demonstrate TESO's effectiveness and reliability using an queue optimization problem, showing improved performance compared to benchmarks and validating the contribution of its memory components. Source code and data are available at: https://github.com/bulentsoykan/TESO.

1 Introduction

Noisy, costly black-box simulations and complex search landscapes make reliable optimization difficult. The paper introduces TESO, integrating memory-based search strategies and adaptive noise control to balance exploration and exploitation, with an empirical demonstration of improved solution quality and reliability.

1 Introduction

  • Noisy evaluations, high computational costs, and complex, often multimodal landscapes make it difficult to distinguish genuine improvements and challenge gradient-based optimization.Black-box structure can also prevent direct derivative calculation.Source: §1 · p. 1
  • Surrogate methods can be computationally intensive to construct and tune, while Ranking and Selection is less directly suited to continuous or high-dimensional search spaces.The discussion also describes Genetic Algorithms, Simulated Annealing, and Particle Swarm Optimization as vulnerable to premature convergence and hyperparameter sensitivity.Source: §1 · pp. 1–2
  • The paper asks whether combining Tabu Search, Elite Memory, and adaptive perturbations can reliably balance exploration and exploitation in noisy, costly, potentially multimodal settings.It positions TESO’s novelty as adapting and integrating established memory structures for stochastic simulation optimization.Source: §1 · p. 2
  • TESO integrates Tabu Search principles, Elite Memory, and adaptive noise control for noisy black-box simulation optimization, with reported improvements in solution quality and reliability.Its tabu-driven diversification and elite-guided intensification are presented as a way to balance exploration and exploitation.Source: §1 · p. 2
  • The paper is organized into background, TESO methodology, numerical experiments, and a conclusion that discusses findings, limitations, and future research.Source: §1 · p. 2

2 Background and Related Work

Simulation optimization seeks decisions that optimize performance measured by stochastic simulations, often without accessible analytical objectives or gradients. The section reviews its budget and search challenges, metaheuristic trade-offs, and memory strategies for diversification and intensification.

2.1 Simulation Optimization (SO)

  • Simulation optimization searches feasible input decisions using expected performance from simulation outputs, although objective functions and gradients are often unavailable analytically.Source: §2.1 · pp. 2–3
  • A single stochastic simulation run gives only a noisy estimate of expected performance, so reliable assessment typically requires replications and greater computational effort.Source: §2.1 · p. 3
  • Limited simulation budgets force a trade-off between exploring new regions and refining promising ones; too much exploitation risks premature convergence to a suboptimal solution.Source: §2.1 · p. 3

2.2 Metaheuristics in Simulation Optimization

  • Metaheuristics search black-box landscapes without derivatives, but their problem-dependent parameters can require extensive tuning and finite-budget global-optimum guarantees are rare.Despite these difficulties, their flexibility and global-search capabilities make them useful when analytical or gradient-based methods are infeasible.Source: §2.2 · pp. 3–4
  • Simulation noise can obscure the landscape and mislead metaheuristic search, potentially worsening premature convergence or making superior solutions hard to distinguish.Source: §2.2 · p. 3

2.3 Memory-Based Heuristics: Tabu Search and Elite Memory

  • Tabu Search records recent moves or solution attributes and temporarily bars reversals to prevent cycling, while elite solutions provide long-term guidance for exploitation.The two memory forms support diversification and intensification, respectively.Source: §2.3 · p. 4

3 TESO: Algorithm Methodology

TESO adapts memory-based direct search to noisy, black-box simulation optimization, balancing diversification and elite-guided intensification. Its iterative method generates and filters candidates, evaluates eligible candidates through replications, updates memories, and stops at the trial budget or a no-improvement limit.

3.1 Framework Overview

  • TESO is direct search using replicated simulation outputs, with short-term Tabu List and long-term Elite Memory structures guiding the search without an explicit global objective model.Unlike standard Tabu Search, it uses probabilistic perturbations around elite solutions and bases comparisons on stochastic mean estimates.Source: §3.1 · p. 4

3.2 Algorithm Methodology

  • Candidates are generated by random sampling during initialization or diversification, and otherwise by perturbing a selected elite solution using the current noise level.If Elite Memory is empty, candidate generation falls back to random sampling.Source: §3.2 · pp. 5–6
  • A tabu candidate is skipped unless it meets the aspiration criterion; accepted candidates receive nrep independent evaluations, whose mean and standard deviation are calculated.The standard deviation is recorded but does not directly affect the current decision logic.Source: §3.2 · pp. 5–6
  • After evaluation, TESO updates its best solution and both memories, adjusts the perturbation noise on a predefined schedule, and stops at the trial budget or no-improvement limit.The returned output is the best solution and its estimated objective value.Source: §3.2 · pp. 5–6

4 Numerical Experiments

The experiments evaluate TESO on a noisy M/M/3 queue problem, comparing it with random sampling and ablations under a shared simulation budget. Full TESO achieves the best reported solution quality and reliability, with results indicating complementary roles for its Tabu List and Elite Memory.

4.1 Experimental Objectives

  • The experiments aim to assess convergence under budget constraints, isolate memory-component effects, benchmark solution quality and reliability, and examine exploration–exploitation behavior.The study evaluates these goals on a simulated queue optimization problem.Source: §4.1 · p. 6

4.2 Test Problem: M/M/k Queue Optimization

  • The test problem minimizes expected customer sojourn time plus a quadratic service-rate cost in a noisy, black-box M/M/3 queue, which is expected to be unimodal.The stated unimodal scope means the problem tests noise handling and search balance, not escape from distinct local optima.Source: §4.2 · pp. 6–7

4.3 Benchmark Algorithms for Comparison

  • Comparisons include Pure Random Sampling and TESO variants without the Tabu List or Elite Memory; SA and GA comparisons are omitted.The authors describe the ablations as a controlled analysis of TESO’s memory components.Source: §4.3 · pp. 7–8

4.4 Experimental Design

  • Each method receives 300 candidate evaluations, with 20 initialization trials, 30 simulation replications per candidate, and 30 independent macro-replications.TESO uses Tabu List capacity 15, Elite Memory capacity 10, and a perturbation-noise schedule decaying from 0.2 to 0.01.Source: §4.4 · p. 8

4.5 Results and Discussion

  • Without the Tabu List, TESO-noTabu reaches 2.72 with standard deviation 0.16, versus full TESO’s 2.53 and 0.07, respectively.The authors suggest the Tabu List mitigates revisiting explored areas or getting temporarily stuck near elite candidates.Source: §4.5 · p. 8
  • Without Elite Memory, TESO-noElite reaches a final mean objective of 2.89 with standard deviation 0.21, worse than both TESO-noTabu and full TESO.The results suggest that elite-guided intensification focuses and refines promising regions.Source: §4.5 · pp. 8–9
  • The convergence patterns suggest that Tabu diversification, Elite Memory intensification, and adaptive noise together manage the exploration–exploitation trade-off in this noisy problem.TESO-noTabu converges quickly initially but may plateau earlier, while TESO-noElite converges more slowly after the initial phase.Source: §4.5 · p. 9
  • Full TESO achieved the lowest final best mean objective value (2.53), near the assumed true optimum (2.52), and the lowest final-best-value standard deviation (0.07) across macro-replications, with faster convergence than other methods.Source: §4.5 · p. 8

5 Conclusion and Future Work

TESO combines adaptive random search with short-term tabu memory and long-term elite guidance, and the paper reports reliable, high-quality queue-optimization solutions with lower variance than PRS and memory-ablation variants. The authors note limits in validation scope, parameter sensitivity, and scalability, motivating broader tests and further development.

5 Conclusion and Future Work

  • TESO converged consistently to high-quality queue-optimization solutions with lower variance than PRS and variants lacking either memory component.The study attributes the result to integrating tabu restrictions and elite guidance to balance exploration and exploitation.Source: §5 · p. 9
  • Validation is limited to a single, unimodal problem class; parameter sensitivity and scalability in very-high-dimensional settings remain concerns.The authors state that a full sensitivity analysis was beyond the scope of this initial study.Source: §5 · p. 10
  • Future work will test broader, higher-dimensional and multimodal benchmarks, develop adaptive parameter mechanisms, explore surrogate hybrids, and analyze convergence theoretically.Source: §5 · p. 10
Loading 2512.24007v1…