Scholarlink

<p>Tabu Search is a promising approach for solving quadratic unconstrained binary optimization (QUBO) problems. A key parameter in Tabu Search is tabu tenure, which governs the balance between intensification and diversification in the search process. In this work, we aim to develop a systematic method for determining the effective tabu tenure tailored to each QUBO instance, thereby enhancing overall solver performance. To achieve this, we focus on the statistics obtained during the search, which we term “trajectory metrics.” We consolidate existing trajectory metrics from the literature with newly proposed ones and analyze their responses to variations in tabu tenure using three criteria: suitability for tuning, noise robustness, and classification potential. Based on this analysis, we introduce a method for determining the effective tabu tenure and evaluate its performance across several problem instances. Experimental results demonstrate that the proposed approach improves solving performance compared to a well-known standard Tabu Search-based method.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Automated Tabu Tenure Tuning by Trajectory Metrics for Quadratic Unconstrained Binary Optimization

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年12月27日

查看全文
  • Masahiko Sugimura,
  • Keiichiro Yamamura,
  • Hiroki Ishikura,
  • Akihiro Yoshida,
  • Ken Kawano,
  • Matthieu Parizy,
  • Katsuki Fujisawa

摘要

Tabu Search is a promising approach for solving quadratic unconstrained binary optimization (QUBO) problems. A key parameter in Tabu Search is tabu tenure, which governs the balance between intensification and diversification in the search process. In this work, we aim to develop a systematic method for determining the effective tabu tenure tailored to each QUBO instance, thereby enhancing overall solver performance. To achieve this, we focus on the statistics obtained during the search, which we term “trajectory metrics.” We consolidate existing trajectory metrics from the literature with newly proposed ones and analyze their responses to variations in tabu tenure using three criteria: suitability for tuning, noise robustness, and classification potential. Based on this analysis, we introduce a method for determining the effective tabu tenure and evaluate its performance across several problem instances. Experimental results demonstrate that the proposed approach improves solving performance compared to a well-known standard Tabu Search-based method.