Running-time Analysis of ($μ+λ$) Evolutionary Combinatorial Optimization Based on Multiple-gain Estimation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909674601709568 |
|---|---|
| author | Huang, Min Chen, Pengxiang Huang, Han He, Tongli Zhang, Yushan Hao, Zhifeng |
| author_facet | Huang, Min Chen, Pengxiang Huang, Han He, Tongli Zhang, Yushan Hao, Zhifeng |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_02381 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Running-time Analysis of ($μ+λ$) Evolutionary Combinatorial Optimization Based on Multiple-gain Estimation Huang, Min Chen, Pengxiang Huang, Han He, Tongli Zhang, Yushan Hao, Zhifeng Neural and Evolutionary Computing 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. |
| title | Running-time Analysis of ($μ+λ$) Evolutionary Combinatorial Optimization Based on Multiple-gain Estimation |
| topic | Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2507.02381 |