A Method for Estimating the Computational Complexity of Multimodal Functions
| Autor: | JJ Merelo, Juan Julián Merelo, Carlos Fernandes, Eric Sanlaville, Juan Luis Jiménez Laredo |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Zdroj: | Applications of Evolutionary Computation ISBN: 9783030437213 EvoApplications |
| Popis: | This paper addresses the issue of estimating the computational complexity of optimizing real-coded multimodal functions where the aim is to find all global optima. The proposed complexity method provides a partial answer to this question in the form of the estimated sample size needed to sample all basins of attraction of all global optima at least once. The rationale behind the approach is that, in optimization, in order to locate all possible optima of a multimodal function, we should first locate all its basins of attraction and then exploit them using, e.g., gradient information. Therefore, estimating the cost of locating all basins of attraction provides a lower bound on the computational budget necessary to optimize a multimodal function. This lower bound can serve as a measure of the computational complexity of the problem. From the conducted experimentation, we show that the proposed model can be very useful in determining the computational complexity of specialized benchmarks and can also be used as a heuristic in case of having some partial knowledge of the features of the targeted function. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|