I wrote a 2-opt algorithm to be used in a program and noticed (using profile) that the 2-opt is eating up a lot of time. I have tried a few things to make it run faster, but I am out of ideas. Any tips on making it run faster, or a better way to write a 2-opt algo?
def twoOpt(self): '''Peforms 2-opt search to improve route''' for index, route in enumerate(self.routes): for element in xrange(len(route.fields)): i = element + 1 k = i + 1 while k <= len(route.fields): newRoute = Route(route.scout) for field in self.twoOptSwap(route.fields, i, k): newRoute.addField(field) newRoute.calcRouteCost() if newRoute.cost < route.cost: self.routes[index] = newRoute k += 1 def twoOptSwap(self, fields, i, k): start = fields[0:i] middle = fields[i:k] middle = middle[::-1] end = fields[k:] newFields = start + middle + end return newFields
Each route object contains a list of fields (
route.cost with a value.