So the algorithm I spoke of in my last post is actually very similar to an algorithm known as v-opt. The difference between 2/3 swing and v-opt is that in v-opt, before ensuring that the solution is an n-opt minima, first ensures that it is also a k-minima for all k < n. So then, the solution is guaranteed to be gets to a 2-opt minima, then a 3-opt minima, and stops, whereas mine swings back and forth. This difference is further seen when 4-opt is introduced. Then, v-opt would find a 2-opt minima, then a three-opt minima, then ensure it is at a two-opt minima again, then ensure it is in a three-opt minima again, etc. Finally, when both 2-opt and 3-opt minima is found, it ensures it is in a four-opt minima, then a two-opt minima, then a three-opt minima, then a two-opt minima again, until it is in both 2- and 3-opt minimas before it checks for 4-opt minima, etc. I know, kinda confusing.
Mine just ensures it's in a 2-opt minima, and goes round-robin instead of making sure the solution is a minima of all opt's below the current one (both 2- and 3- opt before we ensure 4-optimality). It just goes round and round - 2-opt, then 3-, then 4-, then 2-, then 3-, then 4-,... I found this approach did alot better than conventional v-opt as I understand it.
That may have been a little confusing, but I wanted to make sure I tied in my own research with what's already out there.
Wednesday, April 18, 2012
Tuesday, February 28, 2012
The TSP Refinement Solution, Continued: 2/3 Swing
The work on the algorithm I spoke of in my last post bore fruit! It works very well and uses perhaps previously-unbeknownst-insight. The outline of the finished product I lay before you now.
The attached contains the empirical data I gathered about how well my algorithm works.
I received some surprises, and other things did not surprise me. I guessed my algorithm would perform somewhere around O[(n^3)log(n)], and as you can see by the graph, it is quite possible that it did. I was surprised to find, however, that the relationship between how well the greedy algorithm did versus how well my solver did (I call it the "2/3 swing" algorithm) was linear - about 1.3x better than greedy. Perhaps this is because I started out with greedy and can only get so far refining any given solution. Perhaps if I started out with a closer approximation, I might get closer to optimality.
You see, the way my algorithm works is that it takes an initial arbitrary solution - in the case of the data provided, the algorithm started out with a random greedy solution - and, essentially, then gets into a 2-opt local minima. But the insight I gained in creating this algorithm is that a 2-opt local minima is not necessarily a 3-opt local minima. In fact, it rarely is. This is like multi-dimensional gradient descent - as there is rarely a minima across all dimensions in gradient descent, so there is rarely a minima across all opt's. At least, that is the idea of the algorithm.
Here's another clincher: getting into a 2-opt minima for assymetric, incomplete graphs (TSP city maps) has roughly the same complexity as getting into a 3-opt minima, since a linearly-large portion of the path must be reversed for each check to see if the change is an improvement. This makes a thorough 2-opt check, whose search space is in O(n^2), take O(n^3) time. To find a 3-opt local minima, the search space is in O(n^3) and the check is in O(1), so finding a local 2-opt minima, then trying to find a local 3-opt minima, doesn't cost much more by way of complexity, residing only in a constant factor increase in time.
The way that this algorithm gets itself into O(n^3*log(n)) time (or O(n^3.22), if the graph's regression line is to be believed) is by continually "swinging" back and forth between using 2-opt and 3-opt to find the next minima, so that a series of operations in O(n^3) time is looped over a few times. Between using 2-opt and 3-opt, city swapping is employed (taking two arbitrary cities on the best route so far and switching their places as far as order of visitation if such a switch improves the route's score) so as to "mix the bag" between swings. This operation is a small subset of 4-opt, and because it is only in O(n^2) it does not hurt complexity much. Additionaly, since this algorithm works on asymmetric city maps, a reversal of the direction of the route is checked to see if it improves the score on each "swing". This check is linear in time and also does not greatly affect the complexity of the algorithm. Thus the algorithm follows:
best route so far = (initial-approximation-solution)
best cost = infinity
while best cost > best route so far's cost
best cost = best route so far's cost
reverse best route so far if that improves it's score
best route so far = (next 2-opt local minima)
best route so far = (next swap-cities local minima)
best route so far = (next 3-opt local minima)
best route so far = (next swap-cities local minima)
return best route so far
As I cannot post the original data, I will only post the graphs. Original data upon request.
Technical Data:
Platform used: C# on .NET 4, running on an Acer Aspire One 532 netbook
Initial solution (used in refinement): random greedy
City Map: Assymetric, Incomplete
Acknowledgements:
I used the C# TSP Framework provided by the CS department of Brigham Young University.
Code was used in studying this problem which was written by Jimmy Hales (see previous post), although all the code used in the 2/3 swing algorithm is original to the author of this post. Dr. Tony Martinez of Brigham Young University served as adviser during my study of this algorithm, and thanks to him I continued to work on it.
The attached contains the empirical data I gathered about how well my algorithm works.
I received some surprises, and other things did not surprise me. I guessed my algorithm would perform somewhere around O[(n^3)log(n)], and as you can see by the graph, it is quite possible that it did. I was surprised to find, however, that the relationship between how well the greedy algorithm did versus how well my solver did (I call it the "2/3 swing" algorithm) was linear - about 1.3x better than greedy. Perhaps this is because I started out with greedy and can only get so far refining any given solution. Perhaps if I started out with a closer approximation, I might get closer to optimality.
You see, the way my algorithm works is that it takes an initial arbitrary solution - in the case of the data provided, the algorithm started out with a random greedy solution - and, essentially, then gets into a 2-opt local minima. But the insight I gained in creating this algorithm is that a 2-opt local minima is not necessarily a 3-opt local minima. In fact, it rarely is. This is like multi-dimensional gradient descent - as there is rarely a minima across all dimensions in gradient descent, so there is rarely a minima across all opt's. At least, that is the idea of the algorithm.
Here's another clincher: getting into a 2-opt minima for assymetric, incomplete graphs (TSP city maps) has roughly the same complexity as getting into a 3-opt minima, since a linearly-large portion of the path must be reversed for each check to see if the change is an improvement. This makes a thorough 2-opt check, whose search space is in O(n^2), take O(n^3) time. To find a 3-opt local minima, the search space is in O(n^3) and the check is in O(1), so finding a local 2-opt minima, then trying to find a local 3-opt minima, doesn't cost much more by way of complexity, residing only in a constant factor increase in time.
The way that this algorithm gets itself into O(n^3*log(n)) time (or O(n^3.22), if the graph's regression line is to be believed) is by continually "swinging" back and forth between using 2-opt and 3-opt to find the next minima, so that a series of operations in O(n^3) time is looped over a few times. Between using 2-opt and 3-opt, city swapping is employed (taking two arbitrary cities on the best route so far and switching their places as far as order of visitation if such a switch improves the route's score) so as to "mix the bag" between swings. This operation is a small subset of 4-opt, and because it is only in O(n^2) it does not hurt complexity much. Additionaly, since this algorithm works on asymmetric city maps, a reversal of the direction of the route is checked to see if it improves the score on each "swing". This check is linear in time and also does not greatly affect the complexity of the algorithm. Thus the algorithm follows:
best route so far = (initial-approximation-solution)
best cost = infinity
while best cost > best route so far's cost
best cost = best route so far's cost
reverse best route so far if that improves it's score
best route so far = (next 2-opt local minima)
best route so far = (next swap-cities local minima)
best route so far = (next 3-opt local minima)
best route so far = (next swap-cities local minima)
return best route so far
As I cannot post the original data, I will only post the graphs. Original data upon request.
Technical Data:
Platform used: C# on .NET 4, running on an Acer Aspire One 532 netbook
Initial solution (used in refinement): random greedy
City Map: Assymetric, Incomplete
Acknowledgements:
I used the C# TSP Framework provided by the CS department of Brigham Young University.
Code was used in studying this problem which was written by Jimmy Hales (see previous post), although all the code used in the 2/3 swing algorithm is original to the author of this post. Dr. Tony Martinez of Brigham Young University served as adviser during my study of this algorithm, and thanks to him I continued to work on it.
Wednesday, January 4, 2012
An Idea for the Refinement of a TSP Solution
Although I found through experiment that my probabilistic approach to finding a good TSP solution didn't work so well, I did manage to find a polynomial time algorithm that can take an arbitrary solution to the Traveling Salesperson Problem (TSP) and refine it to the optimal solution (with what I have tested so far). I do not know if this polynomial refinement-to-optimality is possible for solutions bigger than 20, as the exponential branch-and-bound solver at my disposal can't do very much given the hardware I have on which to run it.
Now, I think what I have found here MIGHT be awesome.
At any rate, I can explain what it does.
First, we assume an asymmetric directed graph of cites, wherein not every possible edge exists -- i.e. The number of edges in the graph |E| < |V|^2, where |V| is the number of vertices (cities) in the graph (map of cities). For simplicity, if an edge does not exist from one city to another, the reverse edge also does not exist. It can be quickly checked that this problem is still NP-Complete.
We may take this graph to be a map of roads between cities, and the weights on the edges (roads) to be a score of them based on the distance between the cities and the elevation difference between the cities, i.e. if one city is higher in elevation than another, the edge going from the higher to the lower is going to be scored lower than the edge which goes from the lower to the higher, because it is easier to go downhill. Looking at such a real map of cities and creating a graph from it, by scoring the edges as above, we find a distinct pattern in the optimal solution to the traveling salesman tour of the cities considered:
In some sense, the solution forms a "polygon" in the sense that no loops are created. So, this:
would be a better solution than this:
Provided we are looking at the "actual" city map, this is a fairly good heuristic for "goodness" of a solution, if not a requirement for optimality. Looking at the actual city map is important because the actual euclidean distance between cities is taken into account in the scoring of edges, and so these "twists" show up on the actual map, whereas if we just have the graph information, this intuition would not make sense since placement of the node on paper of the equivalent graph has nothing to do with the edge weight. Again, it should be noted that the graph (city map) upon which we consider is asymetric and incomplete, and so is still worthy of discussion.
To further shed light on this discussion, it will be assumed that the optimal tour through a given number of cities will be represented by a list of cities, with the order that the city appears in the list being the order of its visitation on the TSP tour. I now take from an excerpt of an email I sent to my CS professor Dr. Tony Martinez on the subject.
Now, I think what I have found here MIGHT be awesome.
At any rate, I can explain what it does.
First, we assume an asymmetric directed graph of cites, wherein not every possible edge exists -- i.e. The number of edges in the graph |E| < |V|^2, where |V| is the number of vertices (cities) in the graph (map of cities). For simplicity, if an edge does not exist from one city to another, the reverse edge also does not exist. It can be quickly checked that this problem is still NP-Complete.
We may take this graph to be a map of roads between cities, and the weights on the edges (roads) to be a score of them based on the distance between the cities and the elevation difference between the cities, i.e. if one city is higher in elevation than another, the edge going from the higher to the lower is going to be scored lower than the edge which goes from the lower to the higher, because it is easier to go downhill. Looking at such a real map of cities and creating a graph from it, by scoring the edges as above, we find a distinct pattern in the optimal solution to the traveling salesman tour of the cities considered:
In some sense, the solution forms a "polygon" in the sense that no loops are created. So, this:
would be a better solution than this:
To further shed light on this discussion, it will be assumed that the optimal tour through a given number of cities will be represented by a list of cities, with the order that the city appears in the list being the order of its visitation on the TSP tour. I now take from an excerpt of an email I sent to my CS professor Dr. Tony Martinez on the subject.
To refine a given approximate solution, I observed (as explained above) that approximate solutions often have "twists" in them - that is, they were not polygons since their vertices crossed. So I take the solution and try untwisting any arbitrary segment of the solution (that is, reversing that segment - e.g. take the segment # 2, 3, 4, 1, 5 and change it to # 5, 1, 4, 3, 2) and see if that operation improves the score. If it does, I return the improved route, else I return the route the untwisting method was given. [author's comment: if done properly, this part of the algorithm can be done in O(n^2) time.]
Now (empirically) I have observed that the approximate solution is now a polygon (no twists). But it may not be the "right" polygon. To try a different polygon, I simply take an arbitrary subsegment of the solution and splice it into a different part of the whole solution. Example: If we have a solution of Cities # 2, 4, 7, 5, 8, 1, we take an arbitrary sub segment of cities # 4, 7, 5 and try the solution where they are inserted in between 8 and 1 to produce # 2, 8, 4, 7, 5, 1. I try all such possible splice combinations, and see if they improve the score, returning any improvements. This search space, though it be search by brute force, is only O(n^3) large (what's more, being a brute force search, this and other improvement spaces given below can be searched in parallel). I find (again, empirically with our CS312 TSP [Framework] code) that this operation changes the "polygon" to a more optimal one.Finally, for sugar, I take this new and improved solution and select two arbitrary cities along its path and swap them, so that a tour which was city # 2, 3, 8, 7, 1, 4 becomes # 2, 1, 8, 7, 3, 4 if we swap the cities 1 and 3, thus changing the order in which they are visited.
I repeat these three steps - untwisting, segment swapping, and city swapping - for as long as they "help", or as long as any one of them return an improved solution. I find that the number of repetitions is usually small - 3 or 4 times for 50 cities (when it is given a best-of-greedy initial approximate solution, which is an algorithm in O(n^2) time). [author's comment: these were my results when, instead of stopping during untwisting/segment splicing/city swapping at the first improvement found, I tried all available twists/splices/swaps at one time and used the best of those. The results might be higher if the suggested stop-at-first-improvement approach is taken.]
For 20 Cities, I have verified that it spits out the optimal solution over and over again, and in much faster time than branch and bound. I do not have the resources to try for the optimal solution for more than 20 cities using C# code on my laptop [which is a netbook. Details: Acer AspireOne 532h, 2GB RAM, 1.66 GHz processor, running C# .NET executable under Windows 7 Starter].
Thus, I believe this whole algorithm runs in O(N^4) time, which is certainly not exponential. The inner loop (untwisting, splicing, swapping) can be done in O(N^3) time and O(N) space, and it is entirely possible that in fact this algorithm is in O(n^3*log N) time, more empirical study needs to be done to decide if that is indeed the case. While largely untested for bigger N, in the tests I have run it finds the optimal solution every time for city maps with city counts < 20. I know, it's not a big number, but this may still be a very good refinement of a given solution, if not a way to find the optimal solution.
I wonder if anyone could try this method of solution refinement and corroborate my results. Thank you all so much for your comments. I hope someone can further this effort by trying this refinement solution out themselves and comparing their results to known optimal solutions of the graphs upon which they are testing this refinement solution.
Acknowledgments: The code for the Branch-and-Bound solver I used is authored by Jimmy Hales. The C# framework out of which I performed the empirical tests was given to me by the CS Department of Brigham Young University as part of a class assignment for CS312, mentioned in the above letter excerpt as the CS312 TSP (Framework) code.
Update on the Probabilistic TSP Algorithm
Basically?
It failed. Miserably. If we rated the edges based on what I said below, it may have even given us the worst possible path (a great achievement if it were so!) and if we took the edge weights into account in the ratings, the algorithm pretty much spat out roughly what a greedy solution would have anyway. However, I am glad to have done it. It gave me a lot to think about with the Traveling Salesperson problem.
It failed. Miserably. If we rated the edges based on what I said below, it may have even given us the worst possible path (a great achievement if it were so!) and if we took the edge weights into account in the ratings, the algorithm pretty much spat out roughly what a greedy solution would have anyway. However, I am glad to have done it. It gave me a lot to think about with the Traveling Salesperson problem.
Tuesday, November 22, 2011
An Idea for a Probabilistic Approximation of the Solution to the Travelling Salesman Problem
In one of my classes here at Brigham Young, our group has been asked to come up with a unique idea for getting a good approximation to an optimal tour in the traveling salesman problem. Here's the idea I came up with.
I wanted to bring statistics to the table, knowing about such algorithms as Monte Carlo Integration and others which took an unsolvable or hard problem and managed its size simply by taking samples of the bigger problem. The question was: How do you take a "sample" of an optimal traveling salesman tour?
The idea came to select three cities at random, and then use Djikstra's Algorithm (or the Bellman-Ford Algorithm, in the case of negative edges) to find the shortest path from the first to the second, the second to the third, and the third back to the first again, making sure these paths do not cross. If there is no such path, we start over and pick three other random cities until we find a cycle in the way just described which connects them. Such a cycle we would call a subcycle, and it would represent a sub-optimal approximation to the optimal tour (it takes the shortest route across a subset of the cities in the graph).
Then, we rate the edges that were used in this subcycle. Initially, all the ratings associated with all the edges are 0. Each time we find a subcycle, we add k/N to each edge that is used in that subcycle, where k is the number of cities in the subcycle, and N is the total number of cities in the graph.
We then repeat this rating process hundreds or thousands of times, accumulating ratings for the edges that fall in these random subcycles as described above. In our group project, we have 30 seconds to find a solution for an arbitrarily-sized graph, so we just decided to run the rating process described above for 28 seconds, so that many samples could be taken.
All that is left to do now is to take this information and create a solution. This is easily done by finding the first tour through all the cities, trying first the edges with the highest rating. The hope is that this final solution will be a good approximation to the optimal solution.
We have not yet coded this up, but we are in the process of doing so. I'll post here to let the world know how well it worked out. I'm very excited to see how well this works!
I welcome any comments any of you may have on how well this may or may not work. Please feel free to respond to this post!
I wanted to bring statistics to the table, knowing about such algorithms as Monte Carlo Integration and others which took an unsolvable or hard problem and managed its size simply by taking samples of the bigger problem. The question was: How do you take a "sample" of an optimal traveling salesman tour?
The idea came to select three cities at random, and then use Djikstra's Algorithm (or the Bellman-Ford Algorithm, in the case of negative edges) to find the shortest path from the first to the second, the second to the third, and the third back to the first again, making sure these paths do not cross. If there is no such path, we start over and pick three other random cities until we find a cycle in the way just described which connects them. Such a cycle we would call a subcycle, and it would represent a sub-optimal approximation to the optimal tour (it takes the shortest route across a subset of the cities in the graph).
Then, we rate the edges that were used in this subcycle. Initially, all the ratings associated with all the edges are 0. Each time we find a subcycle, we add k/N to each edge that is used in that subcycle, where k is the number of cities in the subcycle, and N is the total number of cities in the graph.
We then repeat this rating process hundreds or thousands of times, accumulating ratings for the edges that fall in these random subcycles as described above. In our group project, we have 30 seconds to find a solution for an arbitrarily-sized graph, so we just decided to run the rating process described above for 28 seconds, so that many samples could be taken.
All that is left to do now is to take this information and create a solution. This is easily done by finding the first tour through all the cities, trying first the edges with the highest rating. The hope is that this final solution will be a good approximation to the optimal solution.
We have not yet coded this up, but we are in the process of doing so. I'll post here to let the world know how well it worked out. I'm very excited to see how well this works!
I welcome any comments any of you may have on how well this may or may not work. Please feel free to respond to this post!
Tuesday, November 15, 2011
.vimrc Goodies: Literal Lambda
I recently took to programming in racket after starting to take a class from Jay McCarthy (twitter: @jeapostrophe). Racket is a scheme-based language constructed specifically with industrial use in mind, which means it is based on some pretty solid theory while also posessing, like perl and php, a package management system (PLaneT), a JIT compiler, and other goodies that make it a great language to use in the real world.
This language, along with perl (given that 'use lambda' is invoked), allows the programmer to insert an acutal unicode lambda instead of the keyword 'lambda'. DrRacket, racket's native IDE, allows you to insert this character by pressing 'CTRL+\' . After looking at this page and others, I found I could do this in vim, too.
I put the following lines in my .vimrc file (this same entry worked in my _vimrc file, for the windows version, as well):
if has("multi_byte")
if &termencoding == ""
let &termencoding = &encoding
endif
set encoding=utf-8
setglobal fileencoding=utf-8
"setglobal bomb
set fileencodings=ucs-bom,utf-8,latin1
endif
map! ^\ ^Qu03bb
I inserted the special characters '^\' (CTRL-\) and ^Q (CTRL-Q) by using the normal vim way: in insert mode, type CTRL-V, then whatever control character you need to. For example, I inserted '^\' by typing CTRL-V, CTRL-\. For CTRL-Q, it was trickier. CTRL-Q is usually a specially bound command, so in order to insert it I had to use its octal number ordinal: CTRL-V, 017, were the keys I typed to insert that character.
Now whenever I'm editing a file, I type CTRL-\ and out pops a bonefied lambda!
This language, along with perl (given that 'use lambda' is invoked), allows the programmer to insert an acutal unicode lambda instead of the keyword 'lambda'. DrRacket, racket's native IDE, allows you to insert this character by pressing 'CTRL+\' . After looking at this page and others, I found I could do this in vim, too.
I put the following lines in my .vimrc file (this same entry worked in my _vimrc file, for the windows version, as well):
if has("multi_byte")
if &termencoding == ""
let &termencoding = &encoding
endif
set encoding=utf-8
setglobal fileencoding=utf-8
"setglobal bomb
set fileencodings=ucs-bom,utf-8,latin1
endif
map! ^\ ^Qu03bb
I inserted the special characters '^\' (CTRL-\) and ^Q (CTRL-Q) by using the normal vim way: in insert mode, type CTRL-V, then whatever control character you need to. For example, I inserted '^\' by typing CTRL-V, CTRL-\. For CTRL-Q, it was trickier. CTRL-Q is usually a specially bound command, so in order to insert it I had to use its octal number ordinal: CTRL-V, 017, were the keys I typed to insert that character.
Now whenever I'm editing a file, I type CTRL-\ and out pops a bonefied lambda!
Friday, July 29, 2011
Tag Cloud of Programming Languages Based on Popularity
The following tag cloud was made by creating a text file with a given programing language's name repeated over and over, with one occurrence of the language's name appearing in the text file for each 100,000 results Google yielded for the phrase '"" programming language'. It has some interesting results. Please feel free to comment on its accuracy/inaccuracy, as I am very interested to know exactly how accurate the Google searches are. Enjoy!
Subscribe to:
Posts (Atom)