Analyzing heuristic performance with response surface models: prediction, optimization and robustness Export

@inproceedings{ridge07analyzing, abstract = {This research uses a Design of Experiments (DOE) approach to build a predictive model of the performance of a combinatorial optimization heuristic over a range of heuristic tuning parameter settings and problem instance characteristics. The heuristic is Ant Colony System (ACS) for the Travelling Salesperson Problem. 10 heurstic tuning parameters and 2 problem characteristics are considered. Response Surface Models (RSM) of the solution quality and solution time predicted ACS performance on both new instances from a publicly available problem generator and new real-world instances from the TSPLIB benchmark library. A numerical optimisation of the RSMs is used to find the tuning parameter settings that yield optimal performance in terms of solution quality and solution time. This paper is the first use of desirability functions, a well-established technique in DOE, to simultaneously optimise these conflicting goals. Finally, overlay plots are used to examine the robustness of the performance of the optimised heuristic across a range of problem instance characteristics. These plots give predictions on the range of problem instances for which a given solutionquality can be expected within a given solution time.}, address = {New York, NY, USA}, author = {Ridge, Enda and Kudenko, Daniel}, booktitle = {Proceedings of the 9th annual conference on Genetic and evolutionary computation (GECCO '07)}, citeulike-article-id = {1539534}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1276958.1276979}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1276958.1276979}, doi = {10.1145/1276958.1276979}, isbn = {978-1-59593-697-4}, keywords = {ant-colony, experimental-method}, location = {London, England}, pages = {150--157}, posted-at = {2009-08-12 10:33:26}, priority = {2}, publisher = {ACM}, title = {Analyzing heuristic performance with response surface models: prediction, optimization and robustness}, url = {http://dx.doi.org/10.1145/1276958.1276979}, year = {2007} }

TY - CONF ID - ridge07analyzing L3 - citeulike-article-id:1539534 N2 - This research uses a Design of Experiments (DOE) approach to build a predictive model of the performance of a combinatorial optimization heuristic over a range of heuristic tuning parameter settings and problem instance characteristics. The heuristic is Ant Colony System (ACS) for the Travelling Salesperson Problem. 10 heurstic tuning parameters and 2 problem characteristics are considered. Response Surface Models (RSM) of the solution quality and solution time predicted ACS performance on both new instances from a publicly available problem generator and new real-world instances from the TSPLIB benchmark library. A numerical optimisation of the RSMs is used to find the tuning parameter settings that yield optimal performance in terms of solution quality and solution time. This paper is the first use of desirability functions, a well-established technique in DOE, to simultaneously optimise these conflicting goals. Finally, overlay plots are used to examine the robustness of the performance of the optimised heuristic across a range of problem instance characteristics. These plots give predictions on the range of problem instances for which a given solutionquality can be expected within a given solution time. CY - London, England SN - 978-1-59593-697-4 AD - New York, NY, USA EP - 157 TI - Analyzing heuristic performance with response surface models: prediction, optimization and robustness PB - ACM T2 - Proceedings of the 9th annual conference on Genetic and evolutionary computation (GECCO '07) SP - 150 KW - ant-colony KW - experimental-method AU - Ridge, Enda AU - Kudenko, Daniel PY - 2007/// UR - http://dx.doi.org/10.1145/1276958.1276979 ER -