Informed Heuristics For Guiding Stem-and-Cycle Ejection Chains
Daniel Harabor (SoCS CECS)
CS HDR MONITORING AI Research GroupDATE: 2010-04-15
TIME: 13:30:00 - 14:00:00
LOCATION: RSISE Seminar Room, ground floor, building 115, cnr. North and Daley Roads, ANU
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
The state of the art in local search for the Traveling Salesman Problem is dominated by edge exchange algorithms such as Lin-Kernighan and the Subpath Ejection Chain algorithm. Though effective such methods employ very little information in their successor selection strategy, typically seeking only to minimise the cost of a move.
I will describe an alternative approach inspired from the AI literature and show how an admissible heuristic can be used to guide successor selection. I present results showing that this technique consistently produces better results than an uninformed strategy albeit at the cost of running in higher polynomial time. I will discuss why this result is important and outline some ideas for future work.
BIO:
PhD student in Computer Science.
