I’ve been writing a hill-climbing algorithm for decrypting a couple of ciphers, and it’s dawned on me that decrypting a cipher, either a transposition or a substitution cipher, is in some sense a conjugate of the travelling salesman problem. Both decrypting a cipher and travelling salesman require finding the best permutation. Because the number of permutations increases as the factorial of the number of elements being permuted, a search through all possible permutations is very slow.

Two much faster algorithms are hill-climbing and grid-refinement. What has just percolated through my thick skull is that a hill-climbing algorithm for decrypting a cipher becomes a grid-refinement algorithm on the travelling salesman problem, and a hill-climbing algorithm on the travelling salesman problem becomes a grid-refinement algorithm for decrypting a cipher.

In a hill-climb, we approach the optimum step by step, improving the result with every step until no more improvement is possible. In grid-refinement, we start with representatives as far apart as possible, and then shrink the choice of representatives down towards the representative that has the best result. For anyone familiar with simulated annealing, grid refinement is similar to simulated annealing with the difference that simulated annealing uses quasi-random numbers and doesn’t require a grid.

This begs the question of when is one permutation close to another. The answer depends on the concepts of ‘switch’ and ‘cycle’. A switch is when we switch two numbers in a permutation, as 123456 → 213456, 163452, etc. A cycle is when we loop numbers, as 123456 → 234561, 345612, etc. For decrypting cipher, a switch defines neighbouring permutations and a cycle finds permuations that are a long way from the original. For the travelling salesman problem, because the aim is to find a loop of towns, a cycle defines neighbouring permutations and a switch finds permutations that are a long way from the original. This is the sense in which decripting a cipher is conjugate to the travelling salesman problem. The word ‘conjugate’ is a generalisation of the concept of ‘perpendicular’, and in a sense means ‘opposite approach’.

So let’s look at the algorithms in more detail. Starting with 123456 we next try all the permutations that can be obtained by one switch, looking for the best. Then repeat. Or using cycles, we freeze one of the numbers and cycle the rest, looking for the best. Then repeat.

Which is best, hill-climbing or grid-refinement? Most functions will have a global best value and very many will also have local good values. The risk is that hill climbing will tend to end up at a local good value rather that global best. One way around that is to start with grid-refinement and then switch to hill-climbing when we’re convinced that we’re approaching the global best.

The genetic algorithm lies somewhere between the two, like hill-climbing it too can get stuck at local good values rather than the global best.

mollwollfumble said:

I’ve been writing a hill-climbing algorithm for decrypting a couple of ciphers, and it’s dawned on me that decrypting a cipher, either a transposition or a substitution cipher, is in some sense a conjugate of the travelling salesman problem. Both decrypting a cipher and travelling salesman require finding the best permutation. Because the number of permutations increases as the factorial of the number of elements being permuted, a search through all possible permutations is very slow.

Two much faster algorithms are hill-climbing and grid-refinement. What has just percolated through my thick skull is that a hill-climbing algorithm for decrypting a cipher becomes a grid-refinement algorithm on the travelling salesman problem, and a hill-climbing algorithm on the travelling salesman problem becomes a grid-refinement algorithm for decrypting a cipher.

In a hill-climb, we approach the optimum step by step, improving the result with every step until no more improvement is possible. In grid-refinement, we start with representatives as far apart as possible, and then shrink the choice of representatives down towards the representative that has the best result. For anyone familiar with simulated annealing, grid refinement is similar to simulated annealing with the difference that simulated annealing uses quasi-random numbers and doesn’t require a grid.

This begs the question of when is one permutation close to another. The answer depends on the concepts of ‘switch’ and ‘cycle’. A switch is when we switch two numbers in a permutation, as 123456 → 213456, 163452, etc. A cycle is when we loop numbers, as 123456 → 234561, 345612, etc. For decrypting cipher, a switch defines neighbouring permutations and a cycle finds permuations that are a long way from the original. For the travelling salesman problem, because the aim is to find a loop of towns, a cycle defines neighbouring permutations and a switch finds permutations that are a long way from the original. This is the sense in which decripting a cipher is conjugate to the travelling salesman problem. The word ‘conjugate’ is a generalisation of the concept of ‘perpendicular’, and in a sense means ‘opposite approach’.

So let’s look at the algorithms in more detail. Starting with 123456 we next try all the permutations that can be obtained by one switch, looking for the best. Then repeat. Or using cycles, we freeze one of the numbers and cycle the rest, looking for the best. Then repeat.

Which is best, hill-climbing or grid-refinement? Most functions will have a global best value and very many will also have local good values. The risk is that hill climbing will tend to end up at a local good value rather that global best. One way around that is to start with grid-refinement and then switch to hill-climbing when we’re convinced that we’re approaching the global best.

The genetic algorithm lies somewhere between the two, like hill-climbing it too can get stuck at local good values rather than the global best.

Interesting.

Why isn’t grid refinement also prone to the local optimum problem?

The Rev Dodgson said:

mollwollfumble said:

I’ve been writing a hill-climbing algorithm for decrypting a couple of ciphers, and it’s dawned on me that decrypting a cipher, either a transposition or a substitution cipher, is in some sense a conjugate of the travelling salesman problem. Both decrypting a cipher and travelling salesman require finding the best permutation. Because the number of permutations increases as the factorial of the number of elements being permuted, a search through all possible permutations is very slow.

Two much faster algorithms are hill-climbing and grid-refinement. What has just percolated through my thick skull is that a hill-climbing algorithm for decrypting a cipher becomes a grid-refinement algorithm on the travelling salesman problem, and a hill-climbing algorithm on the travelling salesman problem becomes a grid-refinement algorithm for decrypting a cipher.

In a hill-climb, we approach the optimum step by step, improving the result with every step until no more improvement is possible. In grid-refinement, we start with representatives as far apart as possible, and then shrink the choice of representatives down towards the representative that has the best result. For anyone familiar with simulated annealing, grid refinement is similar to simulated annealing with the difference that simulated annealing uses quasi-random numbers and doesn’t require a grid.

This begs the question of when is one permutation close to another. The answer depends on the concepts of ‘switch’ and ‘cycle’. A switch is when we switch two numbers in a permutation, as 123456 → 213456, 163452, etc. A cycle is when we loop numbers, as 123456 → 234561, 345612, etc. For decrypting cipher, a switch defines neighbouring permutations and a cycle finds permuations that are a long way from the original. For the travelling salesman problem, because the aim is to find a loop of towns, a cycle defines neighbouring permutations and a switch finds permutations that are a long way from the original. This is the sense in which decripting a cipher is conjugate to the travelling salesman problem. The word ‘conjugate’ is a generalisation of the concept of ‘perpendicular’, and in a sense means ‘opposite approach’.

So let’s look at the algorithms in more detail. Starting with 123456 we next try all the permutations that can be obtained by one switch, looking for the best. Then repeat. Or using cycles, we freeze one of the numbers and cycle the rest, looking for the best. Then repeat.

Which is best, hill-climbing or grid-refinement? Most functions will have a global best value and very many will also have local good values. The risk is that hill climbing will tend to end up at a local good value rather that global best. One way around that is to start with grid-refinement and then switch to hill-climbing when we’re convinced that we’re approaching the global best.

The genetic algorithm lies somewhere between the two, like hill-climbing it too can get stuck at local good values rather than the global best.

Interesting.

Why isn’t grid refinement also prone to the local optimum problem?

It is, but to a much smaller extent. If the outer edge of the grid was a true bounding box, which is almost possible in 1-D, then it would always find the global optimum. But as the number of grid dimensions increases it becomes less able to avoid local good points.

I like to think of the function describing goodness in Fourier space. As we get out outer box smaller than the Fourier half-wavelength we can be guaranteed of a global optimum.

mollwollfumble said:

The Rev Dodgson said:

mollwollfumble said:

I’ve been writing a hill-climbing algorithm for decrypting a couple of ciphers, and it’s dawned on me that decrypting a cipher, either a transposition or a substitution cipher, is in some sense a conjugate of the travelling salesman problem. Both decrypting a cipher and travelling salesman require finding the best permutation. Because the number of permutations increases as the factorial of the number of elements being permuted, a search through all possible permutations is very slow.

Two much faster algorithms are hill-climbing and grid-refinement. What has just percolated through my thick skull is that a hill-climbing algorithm for decrypting a cipher becomes a grid-refinement algorithm on the travelling salesman problem, and a hill-climbing algorithm on the travelling salesman problem becomes a grid-refinement algorithm for decrypting a cipher.

In a hill-climb, we approach the optimum step by step, improving the result with every step until no more improvement is possible. In grid-refinement, we start with representatives as far apart as possible, and then shrink the choice of representatives down towards the representative that has the best result. For anyone familiar with simulated annealing, grid refinement is similar to simulated annealing with the difference that simulated annealing uses quasi-random numbers and doesn’t require a grid.

This begs the question of when is one permutation close to another. The answer depends on the concepts of ‘switch’ and ‘cycle’. A switch is when we switch two numbers in a permutation, as 123456 → 213456, 163452, etc. A cycle is when we loop numbers, as 123456 → 234561, 345612, etc. For decrypting cipher, a switch defines neighbouring permutations and a cycle finds permuations that are a long way from the original. For the travelling salesman problem, because the aim is to find a loop of towns, a cycle defines neighbouring permutations and a switch finds permutations that are a long way from the original. This is the sense in which decripting a cipher is conjugate to the travelling salesman problem. The word ‘conjugate’ is a generalisation of the concept of ‘perpendicular’, and in a sense means ‘opposite approach’.

So let’s look at the algorithms in more detail. Starting with 123456 we next try all the permutations that can be obtained by one switch, looking for the best. Then repeat. Or using cycles, we freeze one of the numbers and cycle the rest, looking for the best. Then repeat.

Which is best, hill-climbing or grid-refinement? Most functions will have a global best value and very many will also have local good values. The risk is that hill climbing will tend to end up at a local good value rather that global best. One way around that is to start with grid-refinement and then switch to hill-climbing when we’re convinced that we’re approaching the global best.

The genetic algorithm lies somewhere between the two, like hill-climbing it too can get stuck at local good values rather than the global best.

Interesting.

Why isn’t grid refinement also prone to the local optimum problem?

It is, but to a much smaller extent. If the outer edge of the grid was a true bounding box, which is almost possible in 1-D, then it would always find the global optimum. But as the number of grid dimensions increases it becomes less able to avoid local good points.

I like to think of the function describing goodness in Fourier space. As we get out outer box smaller than the Fourier half-wavelength we can be guaranteed of a global optimum.

When do we get to the travelling salesman?

so basically what some call grid refinement is better called by others as multipoint hill climbing in extended neighbourhood

roughbarked said:

mollwollfumble said:

The Rev Dodgson said:

Interesting.

Why isn’t grid refinement also prone to the local optimum problem?

It is, but to a much smaller extent. If the outer edge of the grid was a true bounding box, which is almost possible in 1-D, then it would always find the global optimum. But as the number of grid dimensions increases it becomes less able to avoid local good points.

I like to think of the function describing goodness in Fourier space. As we get out outer box smaller than the Fourier half-wavelength we can be guaranteed of a global optimum.

When do we get to the travelling salesman?

when N = 1 or P = 0 easy

I see.