{"ID":2898635,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.02381","arxiv_id":"2507.02381","title":"Running-time Analysis of ($μ+λ$) Evolutionary Combinatorial Optimization Based on Multiple-gain Estimation","abstract":"The running-time analysis of evolutionary combinatorial optimization is a fundamental topic in evolutionary computation. However, theoretical results regarding the $(μ+λ)$ evolutionary algorithm (EA) for combinatorial optimization problems remain relatively scarce compared to those for simple pseudo-Boolean problems. This paper proposes a multiple-gain model to analyze the running time of EAs for combinatorial optimization problems. The proposed model is an improved version of the average gain model, which is a fitness-difference drift approach under the sigma-algebra condition to estimate the running time of evolutionary numerical optimization. The improvement yields a framework for estimating the expected first hitting time of a stochastic process in both average-case and worst-case scenarios. It also introduces novel running-time results of evolutionary combinatorial optimization, including two tighter time complexity upper bounds than the known results in the case of ($μ+λ$) EA for the knapsack problem with favorably correlated weights, a closed-form expression of time complexity upper bound in the case of ($μ+λ$) EA for general $k$-MAX-SAT problems and a tighter time complexity upper bounds than the known results in the case of ($μ+λ$) EA for the traveling salesperson problem. Experimental results indicate that the practical running time aligns with the theoretical results, verifying that the multiple-gain model is an effective tool for running-time analysis of ($μ+λ$) EA for combinatorial optimization problems.","short_abstract":"The running-time analysis of evolutionary combinatorial optimization is a fundamental topic in evolutionary computation. However, theoretical results regarding the $(μ+λ)$ evolutionary algorithm (EA) for combinatorial optimization problems remain relatively scarce compared to those for simple pseudo-Boolean problems. T...","url_abs":"https://arxiv.org/abs/2507.02381","url_pdf":"https://arxiv.org/pdf/2507.02381v1","authors":"[\"Min Huang\",\"Pengxiang Chen\",\"Han Huang\",\"Tongli He\",\"Yushan Zhang\",\"Zhifeng Hao\"]","published":"2025-07-03T07:23:57Z","proceeding":"cs.NE","tasks":"[\"cs.NE\"]","methods":"[]","has_code":false}