0

I'm trying to figure out how to use scipy's dual_annealing function. My problem is the classic travelling salesperson problem: Given a list of coordinates of cities to visit, find the shortest distance when visiting all cities. I've already solved it with a brute force method. Now I'd like to solve it with scipy's dual_annealing.

This is my attempt:

import numpy as np
from scipy import optimize
from scipy import spatial


def total_distance(a):
    prev = None
    total_distance = 0
    for curr in a:
        if prev is None:
            prev = curr
            continue
        else:
            total_distance += spatial.distance.euclidean(prev, curr)
    return total_distance


# List of coordinates with cities to visit. 
inputs = [(485, 475), (1150, 750), (1008, 480), (1562, 134), (1155, 523)]
a = np.array(inputs)
min_distance = optimize.dual_annealing(total_distance, a)

The last line gives this error:

Exception has occurred: ValueError Bounds are not consistent min < max

The dual_annealing function takes the required argument bounds. From the documentation:

bounds : sequence or Bounds
Bounds for variables. There are two ways to specify the bounds:
    Instance of Bounds class.
    Sequence of (min, max) pairs for each element in x.

Given the array of input coordinates to choose from, what do I need to do to fit this requirement? I don't understand what the documentation means when it mentions pairs.

Link to the dual_annealing documentation: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.dual_annealing.html#scipy.optimize.dual_annealing

johanrex
  • 389
  • 5
  • 18
  • Looks like you're confusing a few things. First of all, dual_annealing expects a function f(x), where `x` is a vector. Consequently, `bounds` is just a sequence of lower and upper bounds lb and ub for the *i*-th variable, such that `lb[i] <= x[i] <= ub[i]`. Your main problem is that your function f basically just calculates the total distance for *arbitrary* passed points `a`, i.e. the points are your variable `x`. Instead, your objective function must just *decide* in which order you visit the fixed given points `input` and then return the total distance. – joni Oct 23 '22 at 08:49
  • @joni I probably still misunderstand things. I assume the output of the func argument should be a number, i.e. the total distance that should be minimized, right? Regarding the bounds argument. If I want to visit the whole array then I could create the bounds argument like this: bounds = (a[0], a[len(a)-1]) Am I supposed to mutate the order of cities in the array myself? I thought that's what the annealing algorithm was supposed to do for me. – johanrex Oct 23 '22 at 09:30
  • Reread the docs. The function is supposed to be `func(x,*args)`, `where x is the argument in the form of a 1-D array`. The optimizer tweaks the values of this `x` within bounds, and the function is supposed to return the "cost" of those values. You have a very different problem, a search one involving the `order` of `n` points. You aren't moving the points around. Where did you get the idea that "double annealing" would be applicable? – hpaulj Oct 23 '22 at 15:01
  • I don't think `scipy` has any modules to help with search problems like this. – hpaulj Oct 23 '22 at 15:39
  • @hpaulj I've used simulated annealing to solve the travelling salesperson problem in the past. The way I read the documentation is that double annealing is an improvement over simulated annealing. So naturally I thought this particular implementation could be used. But perhaps that's not the case. – johanrex Oct 23 '22 at 16:14
  • Don't just go by the names. In your working code, what are you changing with each try? Values of a 1d array? Or order of a list of `points`. In other words what's the problem domain? Position of the points in space or order of traversal? – hpaulj Oct 23 '22 at 16:49
  • @hpaulj Well, my code doesn't change the order. That's what I assumed the algorithm did for me. I guess I will need to implement that myself. But if I need to implement the function that should be minimized AND the algorithm that mutates the order then there is no place for the dual_annealing function at all in this problem. – johanrex Oct 23 '22 at 20:35
  • 1
    https://machinelearningmastery.com/dual-annealing-optimization-with-python/ is a tutorial about this scipy function. Maybe its example will give you a better idea of the problem space it is working with. – hpaulj Oct 23 '22 at 20:51

0 Answers0