%0 Conference Paper %1 friedrich2017analyzing %A Friedrich, Tobias %A Kötzing, Timo %A Melnichenko, Anna %B Genetic and Evolutionary Computation Conference (GECCO) %D 2017 %K testing typo3 %P 313-314 %T Analyzing Search Heuristics with Differential Equations %X Drift Theory is currently the most common technique for the analysis of randomized search heuristics because of its broad applicability and the resulting tight first hitting time bounds. The biggest problem when applying a drift theorem is to find a suitable potential function which maps a complex space into a single number, capturing the essence of the state of the search in just one value. We discuss another method for the analysis of randomized search heuristics based on the Theory of Differential Equations. This method considers the deterministic counterpart of the randomized process by replacing probabilistic outcomes by their expectation, and then bounding the error with good probability. We illustrate this by analyzing an Ant Colony Optimization algorithm (ACO) for the Minimum Spanning Tree problem (MST).

@inproceedings{friedrich2017analyzing, abstract = {Drift Theory is currently the most common technique for the analysis of randomized search heuristics because of its broad applicability and the resulting tight first hitting time bounds. The biggest problem when applying a drift theorem is to find a suitable potential function which maps a complex space into a single number, capturing the essence of the state of the search in just one value. We discuss another method for the analysis of randomized search heuristics based on the Theory of Differential Equations. This method considers the deterministic counterpart of the randomized process by replacing probabilistic outcomes by their expectation, and then bounding the error with good probability. We illustrate this by analyzing an Ant Colony Optimization algorithm (ACO) for the Minimum Spanning Tree problem (MST).}, added-at = {2017-09-19T19:29:15.000+0200}, author = {Friedrich, Tobias and Kötzing, Timo and Melnichenko, Anna}, biburl = {https://www.bibsonomy.org/bibtex/2b9a5a50406bfee144d22d94891097e00/typo3tester}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, interhash = {afb974c863aa182945018e52f5ea4df0}, intrahash = {b9a5a50406bfee144d22d94891097e00}, keywords = {testing typo3}, pages = {313-314}, timestamp = {2017-09-19T19:29:15.000+0200}, title = {Analyzing Search Heuristics with Differential Equations}, year = 2017 }