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 timing 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 front 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 timing 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 solution quality can be expected within a given solution time.
| Original language | English |
|---|---|
| Title of host publication | GECCO 2007: GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, VOL 1 AND 2 |
| Place of Publication | NEW YORK |
| Publisher | ACM |
| Pages | 150-157 |
| Number of pages | 8 |
| ISBN (Print) | 978-1-59593-697-4 |
| DOIs | |
| Publication status | Published - 2007 |
| Event | GECCO 2007 - London, England Duration: 7 Jul 2007 → 11 Jul 2007 |
Conference
| Conference | GECCO 2007 |
|---|---|
| City | London, England |
| Period | 7/07/07 → 11/07/07 |
Keywords
- Design of Experiments
- Minimum Run Resolution V Design
- Response Surface Model
- Overlay Plots
- Ant Colony Optimization
- ALGORITHMS