A study of search algorithms’ optimization speed |
| |
Authors: | Andrea Valsecchi Leonardo Vanneschi Giancarlo Mauri |
| |
Institution: | 1. European Centre for Soft Computing, 33600, Mieres, Spain 2. DISCo, Università di Milano-Bicocca, 20126, Milan, Italy 3. ISEGI, Universidade Nova de Lisboa, 1070-312, Lisbon, Portugal
|
| |
Abstract: | Search algorithms are often compared by the optimization speed achieved on some sets of cost functions. Here some properties of algorithms’ optimization speed are introduced and discussed. In particular, we show that determining whether a set of cost functions F admits a search algorithm having given optimization speed is an NP-complete problem. Further, we derive an explicit formula to calculate the best achievable optimization speed when F is closed under permutation. Finally, we show that the optimization speed achieved by some well-know optimization techniques can be much worse than the best theoretical value, at least on some sets of optimization benchmarks. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|