Download local_minimum.py Here
Download my_src.py Here
In this post we will look at an example of a cycle that is a local minimum for the moves that are allowed for the standard simulated annealing approach to the Travelling Salesman Problem (see this post). Note that the Travelling Salesman Problem is actually a convex integer programming problem; so how do we encounter a local minimum? The answer is that in some sense the simulated annealing process relies on moving in “directions” of the cycle state space that are limited enough that relative to these restricted moves, we encounter local minima. Now, actually finding an explicit example of how this occurs is a little tricky.
In particular, we show that the following cycle is a local minimum:
The dimensions of this cycle have been carefully chosen to give a local minimum; e.g. if we chose the top vertices to have a y-value of 3.0, then the cycle is no longer a local minimum.
Note, that this cycle is not a global minimum. In fact, the following cycle actually has smaller length:
However, it takes MORE than one of our simulated annealing flips to go from the local minimum to the smaller cycle.
In the following sections, we will use a brute force check to verify that the local minimum is in fact a local minimum. That is, we will check every cycle that is obtained from our local minimum by one flip has a cycle length at least as large as the local minimum.
Creating the Local Minimum
Now let’s look at creating the local minimum. We use the following from ‘my_src.py’.
# From my_src.py.
def make_local_minimum(heights, separation, return_shorter = False):
'''
Local minimum cycle looks like the following:
---------------------------------
heights[1] | |
| separation |
| ---------------------- |
| | | |
| |heights[0] | |
|_____| |_____|
1 1
A shorter cycle connects upper corners using diagonal segments and connects the bottom
inside corners using a horizontal segment.
Parameters
----------
heights : Numpy array of heights of size 2
The vertical heights as represented in the diagram.
separation : Int or Float
The horizontal separation as depicted in the diagram.
return_shorter : Boolean
Whether to return a shorter cycle too.
Returns
-------
local_minimum : Numpy array of shape (n_vertices, 2)
The vertices of the local minimum cycle in order.
shorter_cycle : Numpy array of shape (n_vertices, 2)
Returned ONLY when return_shorter is True. The vertices in the order of a shorter cycle.
'''
local_min = np.array([[0, heights[1]], [0, 0], [1, 0], [1, heights[0]],
[1 + separation, heights[0]], [1 + separation, 0],
[2 + separation, 0], [2 + separation, heights[1]]])
if not return_shorter:
return local_min
shorter = local_min[[0, 1, 2, 5, 6, 7, 4, 3]]
return local_min, shorter
def find_length(cycle):
'''
Find the length of the cycle. Make sure to include the distance between the first vertex and
the last vertex.
Parameters
----------
cycle : Numpy array of shape (n_vertices, 2)
The vertices of the cycle in the order of the cycle.
Returns
-------
length : Float
The length of the cycle.
'''
length = np.linalg.norm(cycle[1:] - cycle[:-1], axis = -1).sum()
length += np.linalg.norm(cycle[0] - cycle[-1])
return lengthLet’s get the local minimum and the shorter cycle.
# From local_minimum.py.
# Make the local minimum cycle and the shorter cycle.
local_min, shorter = my_src.make_local_minimum(heights = [1, 2.5], separation = 6, return_shorter = True)
lengths = {'local_min' : my_src.find_length(local_min),
'shorter' : my_src.find_length(shorter)}
print('lengths = ', lengths)
# Plot the local minimum cycle.
my_src.plot_cycle(local_min)
plt.title('Local Minimum, Length = ' + str(lengths['local_min']))
plt.tight_layout()
plt.savefig('local_min.svg')
plt.close()
# Plot the shorter cycle.
my_src.plot_cycle(shorter)
plt.title('Shorter Cycle, Length = ' + '{:.2f}'.format(lengths['shorter']))
plt.tight_layout()
plt.savefig('shorter_cycle.svg')
plt.close()We saw the graphs of the two cycles and their lengths at the beginning of the post.
Verify the Local Min is a Local Min
Now let’s verify that the local minimum is actually a local minimum. We will simply compute every possible flip, and find its length. For example, here is a graph of random flip of the local minimum:
Let’s now get all of the lengths of the local moves. We will be making use of the following
function from my_src.py:
# From my_src.py.
def flip_segment_order(cycle, i, j):
'''
Flip the order of the cycle between two indices (inclusive).
Parameters
----------
cycle : Numpy array of shape (n_vertices, 2)
The vertices of the cycle in the original order.
i : Int
Smaller end point. Should satisfy i < j.
j : Int
Larger end point. Should satisfy i < j.
'''
new_cycle = np.concatenate([cycle[:i],
np.flip(cycle[i:j+1], axis = 0),
cycle[j+1:]], axis = 0)
return new_cycle Let’s now get the lengths of the local moves, and let’s make some graphs of some interesting examples. Also, let’s raise an exception if we see any local move that has a length less than that of the local minimum.
# From local_minimum.py
# Get all possible local moves from the local minimum cycle and find their lengths.
# Note, that any flip is always equivalent to flipping the order for the segment
# of vertices contained in the array.
local_lengths = []
for i in range(0, len(local_min) - 1):
for j in range(i + 1, len(local_min)):
new_cycle = my_src.flip_segment_order(local_min, i, j)
new_length = my_src.find_length(new_cycle)
local_lengths.append(new_length)
# Get a plot of what one of the moves looks like.
if i == 0 and j == 4:
my_src.plot_cycle(new_cycle)
plt.title('Random Example Move for i = ' + str(i) + ', j = ' + str(j) +
', Length = ' + '{:.2f}'.format(new_length))
plt.tight_layout()
plt.savefig('local_move.svg')
plt.close()
# Make a plot if the length of the cycle is the same as the local min cycle.
if new_length == lengths['local_min']:
print('Move for i = ', i, ', j = ', j, 'has the same length as the local minimum cycle.')
my_src.plot_cycle(new_cycle, mark_begin_end = True)
plt.title('Move for i = ' + str(i) + ', j = ' + str(j) + ', Length is Same as Local Min')
plt.tight_layout()
plt.savefig('same_' + str(i) + '_' + str(j) + '.svg')
plt.close()
# If we see a cycle that is smaller, make a plot of the cycle and raise an exception. This
# shouldn't ever happen.
if new_length < lengths['local_min']:
my_src.plot_cycle(new_cycle)
plt.title('Move for i = ' + str(i) + ' j = ' + str(j) + 'has Smaller Length = ' +
'{:.2f}'.format(my_src.find_length(new_cycle)))
plt.savefig('error.svg')
raise Exception('Found a local move with SHORTER length! i = ' + str(i) + ', j = ' + str(j))
# Look at the differences in the lengths for the cycles local to the local minimum cycle.
diff_lengths = [l - lengths['local_min'] for l in local_lengths]
print('Minimal difference of lengths is ', min(diff_lengths))
# Plot the local lengths.
plt.scatter(local_lengths, np.zeros(len(local_lengths)))
plt.axvline(lengths['local_min'], color = 'red')
plt.title('Lengths of the Local Cycles')
plt.xlabel('Lengths')
plt.yticks([]) # Hide the y-axis.
plt.legend(['Local Min', 'Locals'])
plt.tight_layout()
plt.savefig('local_lengths.svg')We get the following output:
lengths = {'local_min': 23.0, 'shorter': 22.605551275463988}
Move for i = 0 , j = 6 has the same length as the local minimum cycle.
Move for i = 0 , j = 7 has the same length as the local minimum cycle.
Move for i = 1 , j = 7 has the same length as the local minimum cycle.
Minimal difference of lengths is 0.0So we see that all of the local moves are at least as long as the local minimum. Some have the same length; graphing these we infact see that these cycles have the same shape but are an order preserving permutation of the original vertices. Here are their graphs:
Now, let’s take a look at all of the local move lengths.
So we see that the local minimum is in fact a local minimum when we restrict to the flips used for simulated annealing in the travelling salesman problem.