Name
Abstract | ||
|---|---|---|
The approximation error of an evolutionary algorithm is the fitness difference between the optimal solution and a solution found by the algorithm. In this paper, an initial error analysis has been made to evolutionary algorithms for discrete optimization. First, the order of convergence and asymptotic error constant are defined. Then it is proven that for any EA, under particular initialization, its order of convergence is 1 and its asymptotic error constant equals to the spectral radius of the transition probability sub-matrix; if its transition probability sub-matrix is primitive or upper triangular with unique diagonal entries, then under random initialization, its order of convergence is 1 and its asymptotic error constant equals to the spectral radius of the transition probability sub-matrix. Our study reveals that evolutionary algorithms converge linearly to the optimal solution and the spectral radius of the transition probability sub-matrix is the main factor in affecting the approximation error. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1145/3067695.3075981 | GECCO (Companion) |
Keywords | Field | DocType |
evolutionary algorithms, algorithm analysis, convergence rate, approximation error | Mathematical optimization,Spectral radius,Evolutionary algorithm,Discrete optimization,Round-off error,Rate of convergence,Initialization,Triangular matrix,Mathematics,Approximation error | Conference |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| He Jun | 1 | 617 | 42.32 |
| Yuren Zhou | 2 | 721 | 49.79 |
| Guangming Li | 3 | 4 | 3.10 |