Performance analysis of randomised search heuristics operating with a fixed budget.

*(English)*Zbl 1360.68781Summary: When for a difficult real-world optimisation problem no good problem-specific algorithm is available often randomised search heuristics are used. They are hoped to deliver good solutions in acceptable time. The theoretical analysis usually concentrates on the average time needed to find an optimal or approximately optimal solution. This matches neither the application in practice nor the empirical analysis since usually optimal solutions are not known and even if found cannot be recognised. More often the algorithms are stopped after some time. This motivates a theoretical analysis to concentrate on the quality of the best solution obtained after a pre-specified number of function evaluations called budget. Using this perspective two simple randomised search heuristics, random local search and the \((1+1)\) evolutionary algorithm, are analysed on some well-known example problems. Upper and lower bounds on the expected quality of a solution for a fixed budget of function evaluations are proven. The analysis shows novel and challenging problems in the study of randomised search heuristics. It demonstrates the potential of this shift in perspective from expected run time to expected solution quality.

##### MSC:

68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |

68W20 | Randomized algorithms |

68W40 | Analysis of algorithms |

##### Keywords:

runtime analysis; fixed budget computation; random local search; \((1+1)\) EA; OneMax; leading ones; jump; ridge
PDF
BibTeX
XML
Cite

\textit{T. Jansen} and \textit{C. Zarges}, Theor. Comput. Sci. 545, 39--58 (2014; Zbl 1360.68781)

Full Text:
DOI

##### References:

[1] | Jansen, T.; Zarges, C., Fixed budget computations: A different perspective on run time analysis, (Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012), (2012), ACM Press), 1325-1332 |

[2] | (Auger, A.; Doerr, B., Theory of Randomized Search Heuristics, (2011), World Scientific) · Zbl 1233.90005 |

[3] | Yu, Y.; Yao, X.; Zhou, Z.-H., On the approximation ability of evolutionary optimization with application to minimum set cover, Artificial Intelligence, 180-181, 20-33, (2012) · Zbl 1238.68152 |

[4] | Troutman, N. P.; Eskridge, B. E.; Hougen, D. F., Is “best-so-far” a good algorithmic performance metric?, (Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2008), (2008), ACM Press), 1147-1148 |

[5] | Cantu-Paz, E.; Goldberg, D. E., Are multiple runs of genetic algorithms better than one?, (Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2003), Part 1, Lecture Notes in Comput. Sci., vol. 2723, (2003), Springer), 801-812 · Zbl 1028.68699 |

[6] | Jansen, T.; Zarges, C., Analysis of evolutionary algorithms: from computational complexity analysis to algorithm engineering, (11th ACM SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA 2011), (2011), ACM Press), 1-14 · Zbl 1369.68313 |

[7] | Doerr, B.; Jansen, T.; Klein, C., Comparing global and local mutations on bit strings, (Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2008), (2008), ACM Press), 929-936 |

[8] | Doerr, B.; Neumann, F.; Sudholt, D.; Witt, C., Runtime analysis of the 1-ANT ant colony optimizer, Theoret. Comput. Sci., 412, 17, 1629-1644, (2011) · Zbl 1219.68143 |

[9] | Droste, S.; Jansen, T.; Wegener, I., On the analysis of the \((1 + 1)\) evolutionary algorithm, Theoret. Comput. Sci., 276, 1-2, 51-81, (2002) · Zbl 1002.68037 |

[10] | Sudholt, D.; Witt, C., Runtime analysis of a binary particle swarm optimizer, Theoret. Comput. Sci., 411, 21, 2084-2100, (2010) · Zbl 1190.90292 |

[11] | Quick, R. J.; Rayward-Smith, V. J.; Smith, G. D., Fitness distance correlation and ridge functions, (Proceedings of the 5th International Conference on Parallel Problem Solving from Nature (PPSN 1998), Lecture Notes in Comput. Sci., vol. 1498, (1998), Springer), 77-86 |

[12] | Doerr, B.; Fouz, M.; Witt, C., Sharp bounds by probability-generating functions and variable drift, (Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2011), (2011), ACM Press), 2083-2090 |

[13] | Witt, C., Optimizing linear functions with randomized search heuristics — the robustness of mutation, (Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), (2012)), 420-431 · Zbl 1245.68178 |

[14] | Motwani, R.; Raghavan, P., Randomized algorithms, (1997), Cambridge University Press |

[15] | Jansen, T.; Wegener, I., On the analysis of evolutionary algorithms — a proof that crossover really can help, Algorithmica, 34, 1, 47-66, (2002) · Zbl 1016.68030 |

[16] | Doerr, B., Analyzing randomized search heuristics: tools from probability theory, (Auger, A.; Doerr, B., Theory of Randomized Search Heuristics, (2011), World Scientific), 1-20, (Ch. 1) · Zbl 1235.90185 |

[17] | Mitzenmacher, M.; Upfal, E., Probability and computing: randomized algorithms and probabilistic analysis, (2005), Cambridge University Press · Zbl 1092.60001 |

[18] | Böttcher, S.; Doerr, B.; Neumann, F., Optimal fixed and adaptive mutation rates for the leadingones problem, (Proceedings of the 11th International Conference on Parallel Problem Solving from Nature (PPSN 2010), Part 1, Lecture Notes in Comput. Sci., vol. 6238, (2010), Springer), 1-10 |

[19] | Doerr, B.; Jansen, T.; Witt, C.; Zarges, C., A method to derive fixed budget results from expected optimisation times, (Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2013), (2013), ACM Press), in press |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.