Determining Whether a Problem Characteristic Affects Heuristic Performance Export

@incollection{citeulike:4313268, abstract = {This chapter presents a rigorous Design of Experiments (DOE) approach for determining whether a problem characteristic affects the performance of a heuristic. Specifically, it reports a study on the effect of the cost matrix standard deviation of symmetric Travelling Salesman Problem (TSP) instances on the performance of Ant Colony Optimisation (ACO) heuristics. Results demonstrate that for a given instance size, an increase in the standard deviation of the cost matrix of instances results in an increase in the difficulty of the instances. This implies that for ACO, it is insufficient to report results on problems classified only by problem size, as has been commonly done in most ACO research to date. Some description of the cost matrix distribution is also required when attempting to explain and predict the performance of these heuristics on the TSP. The study should serve as a template for similar investigations with other problems and other heuristics.}, author = {Ridge, Enda and Kudenko, Daniel}, citeulike-article-id = {4313268}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-70807-0_2}, citeulike-linkout-1 = {http://www.springerlink.com/content/g22v456585405444}, doi = {10.1007/978-3-540-70807-0_2}, journal = {Recent Advances in Evolutionary Computation for Combinatorial Optimization}, keywords = {algorithm-engineering, ant-colony-optimization, cost-matrix, metaheuristic, performance-assessment, travelling-salesman-problem}, pages = {21--35}, posted-at = {2009-04-15 14:06:24}, priority = {5}, title = {Determining Whether a Problem Characteristic Affects Heuristic Performance}, url = {http://dx.doi.org/10.1007/978-3-540-70807-0_2}, year = {2008} }

TY - CHAP ID - citeulike:4313268 L3 - citeulike-article-id:4313268 N2 - This chapter presents a rigorous Design of Experiments (DOE) approach for determining whether a problem characteristic affects the performance of a heuristic. Specifically, it reports a study on the effect of the cost matrix standard deviation of symmetric Travelling Salesman Problem (TSP) instances on the performance of Ant Colony Optimisation (ACO) heuristics. Results demonstrate that for a given instance size, an increase in the standard deviation of the cost matrix of instances results in an increase in the difficulty of the instances. This implies that for ACO, it is insufficient to report results on problems classified only by problem size, as has been commonly done in most ACO research to date. Some description of the cost matrix distribution is also required when attempting to explain and predict the performance of these heuristics on the TSP. The study should serve as a template for similar investigations with other problems and other heuristics. JF - Recent Advances in Evolutionary Computation for Combinatorial Optimization EP - 35 TI - Determining Whether a Problem Characteristic Affects Heuristic Performance SP - 21 KW - algorithm-engineering KW - ant-colony-optimization KW - cost-matrix KW - metaheuristic KW - performance-assessment KW - travelling-salesman-problem AU - Ridge, Enda AU - Kudenko, Daniel PY - 2008/// UR - http://dx.doi.org/10.1007/978-3-540-70807-0_2 ER -