On the use of CBR in optimisation problems such as the TSP
Metadata:Show full item record
Citation:Cunningham, P., Smyth, B., Hurley, N. 'On the use of CBR in optimisation problems such as the TSP'. - Dublin, Trinity College Dublin, Department of Computer Science, TCD-CS-95-19, 1995, pp10
The particular strength of CBR is normally considered to be its use in weak theory domains where solution quality is compiled into cases and is reusable. In this paper we explore an alternative use of CBR in optimisation problems where cases represent highly optimised structures in a huge highly constrained solution space. Our analysis focuses on the Travelling Salesman Problem where difficulty arises from the computational complexity of the problem rather than any difficulty associated with the domain theory. We find that CBR is good for producing medium quality solutions in very quick time. We have difficulty getting CBR to produce high quality solutions because solution quality seems to be lost in the adaptation process. We also argue that experiments with CBR on transparent problems such as the TSP tell us a lot about aspects of CBR such as; the quality of CBR solutions, the coverage that cases in the casebase offer and the utility of extending a case-base.
Publisher:Trinity College Dublin, Department of Computer Science
Series/Report no:Computer Science Technical Report