Fast Estimations of Hitting Time of Elitist Evolutionary Algorithms from Fitness Levels
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908884687388672 |
|---|---|
| author | He, Jun Chong, Siang Yew Yao, Xin |
| author_facet | He, Jun Chong, Siang Yew Yao, Xin |
| contents | The fitness level method is a widely used technique for estimating the mean hitting time of elitist evolutionary algorithms on level-based fitness functions. However, this paper identifies its main limitation: the linear lower bound derived from traditional fitness level partitioning is not tight when applied to many non-level-based fitness functions. A new subset level method is introduced to address this limitation. It selects a subset of non-optimal solutions, partitions them into levels, and then estimates linear bound coefficients based on drift analysis. Explicit expressions are proposed to compute the lower bound on the mean hitting time of elitist evolutionary algorithms. The proposed method is validated using six instances of the knapsack problem. Results show that the new method can be used to quickly estimate the lower bound on the mean hitting time of elitist evolutionary algorithms. This expands the application scope of the fitness level method to non-level-based functions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_10502 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Fast Estimations of Hitting Time of Elitist Evolutionary Algorithms from Fitness Levels He, Jun Chong, Siang Yew Yao, Xin Neural and Evolutionary Computing The fitness level method is a widely used technique for estimating the mean hitting time of elitist evolutionary algorithms on level-based fitness functions. However, this paper identifies its main limitation: the linear lower bound derived from traditional fitness level partitioning is not tight when applied to many non-level-based fitness functions. A new subset level method is introduced to address this limitation. It selects a subset of non-optimal solutions, partitions them into levels, and then estimates linear bound coefficients based on drift analysis. Explicit expressions are proposed to compute the lower bound on the mean hitting time of elitist evolutionary algorithms. The proposed method is validated using six instances of the knapsack problem. Results show that the new method can be used to quickly estimate the lower bound on the mean hitting time of elitist evolutionary algorithms. This expands the application scope of the fitness level method to non-level-based functions. |
| title | Fast Estimations of Hitting Time of Elitist Evolutionary Algorithms from Fitness Levels |
| topic | Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2311.10502 |