Traveller Milestone:
Solves Koch Snowflake of 3072 Nodes

[Rats! The checkboxes, visible when I did the screen captures, don't show (in my browser) when I view the result on the net. Boxes checked will be _annotated_ rather than shown. Grumble.]

As much to preserve the event for my own amazement, and so I don't forget how I did this and that I did this, as for any other purposes, here are the usual runtime windows open or in control as Traveller 1.21 (with KPD mods) solved a problem size I thought far outside the capabilities of my laptop: a Traveling Salesman Problem instance of 3072 nodes, in 10,351 seconds after 351 seconds of problem setup effort. This is for Traveller version "zeta", which is a work in progress not yet published, I have lots of features in mid-development at this point, and more than a few introduced bugs to squash, and then there's that ever nagging documentation...

Let me race to admit that there is less here than meets the eye. The instance solved was a Koch Snowflake fractal, which has two very nice properties: in the solved version, all the edge lengths are the same, and the problem has no local optima: there is always a downhill path from the current state to the minimum length state, backtracking is never necessary. Nevertheless, the heuristics used don't take any particular advantage of either of these helpful features.

Also important was that in solving a problem of this size, I took advantage of every tool at Traveller's command, in particular using my best seeding method, a greedy approximate solver, rather than my worst, random seeds, and using sighted cheat and local optimization heuristics in the mix with classical "blind" ones.

Enough disclaimers, on to the bragging! This is also a way to introduce the much modified screen interface for the upcoming "zeta" release, though since it supports around a hundred different windows (most repetitive, I hasten to add), this is just a small sample.

Here is the solved Koch Snowflake. Since the "Draw All Always" visual debugging aid is enabled, you should (just) be able to see a few tiny red edges still left from the members of the population that weren't quite solutions yet; the usual gold "best current genome" (in this case, "solved genome") path is completely overlaid by the dense cyan nodes of the familiar fractal snowflake graph, since Traveller draws edges before nodes (in the usual case, it was the nodes that were getting lost, not the edges).


Here is the status panel bragging to the user that the problem has been solved. Check out that brute force solution time to see why this accomplishment is worth a brag.


Notice the statistics for the "at last improvement", which is where the problem was solved. Traveller just kept running afterwards; I haven't yet got working an automatic stop when the problem is solved, one of the focuses of my current development efforts for multi-run logging for Traveller. Note especially the number of city to city distances calculated, over two-thirds of a billion, related to the classical effort metric "fitnesses calculated". Since Traveller doesn't always compute full fitnesses in inner loops, the city to city distances taken are a more fair measure of effort. Time isn't a very good measure, because with solution times in the hours, I'm often doing development in parallel with testing while the problem runs. Generations and population size are also not good measures, because both random use of heuristics and particular heuristics enabled for a run change dramatically how much work per genome a "generation" entails. In particular, for this run, the first generation took twelve seconds, the second generation took 15 minutes, just because different heuristics were selected in the random heuristic loop, and the very small population size (6 genomes) didn't smooth out those differences.

Here is the workload setup: big problem, small population, no mutation, and Tabu Search to a "modest" depth.


Frankly that Tabu setting was a blunder, that is a huge number of copies of such a big genome to keep around, but as the problem was solved after considering only 60 genome instances (discounting the three generations run before I noticed it was done), it never became an issue.

Here is the push button control panel, showing that I had paused Traveller to capture the screen images for this document after I looked up from reading the newspaper in the Fresno State University Student Union long enough to notice that the problem, amazingly, had been solved.


[Imagine the "Koch Snowflake Layout?" box to be checked.] The layout panel shows that the Koch Snowflake was selected for solution. The "zeta" release of Traveller will have, as seen here, several more layout options than the "epsilon" release had.


[Imagine the "Greedy Seeder?" box to be checked.] To speed up the solution, a good first seed genome set was chosen; the greedy seeder starts by selecting three random points, then adds to the triangle they form randomly chosen nodes one by one into the edge where their addtion causes the smallest gain in tour length. This is an amazingly effective approximation, better than my flawed minimal spanning tree seeder, to my sorrow, considering how much effort I put into the MST seeder to have it so easily beaten.


Somewhat surprisingly, even starting with random seed genomes wouldn't have made this problem intractible for my laptop; a couple of heuristics (Snowplow, for example, was one in use during this run) really slog down on randomly seeded genomes, but they do eventually come out the other side, and in a handful of generations, randomly seeded Traveller using these expensive heuristics catches up to intelligently seeded Traveller. It is getting past the usual stall point at the other end, the one close to the solution, that is cause for celebration.

[Imagine the "Draw All Always?" box to be checked.] Only the "Draw All Always" debugging / visualization capability was enabled, it produced the few flecks of red in the route window. On big problems, best practice is to turn off even the seemingly cheap text progress displays; they can add lots of time to runs with complex heuristics enabled; speed of painting screen graphics is one of Java's sore points.


[Imagine the "Roulette Wheel?" box to be checked.] This controls setting window is still just a promise of future effort, since only the original choice inherited from Scott Robert Ladd's Traveller is developed yet.


[Imagine the "Anneal?", "Single Elitism?", and "Tabu?" boxes to be checked.] Here is where Traveller gets smartest, choosing metaheuristics to modify or enhance the heuristics being used to attack the problem.


For this run, single elitism was enabled to assure that a solution once found didn't get clobbered by simulated annealing and then lost for a very long time while it flushed out of the Tabu Search array of forbidden "recent" fitness landscape paths already explored.

Simulated annealing was enabled, too, but the problem was solved before a single annealing event occurred! Tabu Search prevented 42 walks down already explored paths, probably some of which were seen after the problem was solved but before I noticed it was solved.

[Imagine the "Disable automatic run and logging?" and "* Show run set summary logs only?" boxes to be checked.] Here is the focus of current development effort, a logging capability for Traveller to cut down the hand efforts the experimenter must do to check the effectiveness of new heuristics and metaheuristics.


Traveller "zeta", if all goes well, will be able to run a series of similar problem setups, gather statistics, log selected information from the runs, and produce an analysis of the performance of Traveller for the experimenter. As of this writing, logging works, statistics gathering works, statistics analysis hasn't been addressed but will be easy, and the thread issues, which are hard, of doing runs in a loop, with control information coming in fairly asynchronously from various classes, are the current specific work focus.

[Imagine the "Cyclic Xover?", "Ordered Xover?", "Partial Match Xover?", "Inver-over?", and "Ordered Slide?" boxes to be checked.] Here are the heuristics enabled from the classical "blind" heuristics set for this run.


[Imagine the "Edge Preserving Xover?", "Rolling Xover?", "Dewrinkler?", "Smoother?", and "Snow Plow?" boxes to be checked.] Here are the "sighted cheat" heuristics enable for this run.


[Imagine the "Best Cuts Near A Random Point Once?", "Best Edges Near A Random Point Once?", "Best Nodes and Edges Near A Random Point Once?", "Best Nodes Near A Random Point Once?", "Best Cuts Near Cities In Random Order Once?", "Best Edges Near Cities In Random Order Once?", "Best Nodes and Edges Near Cities In Random Order Once?", and "Best Nodes Near Cities In Random Order Once?" boxes to be checked.] Here are the local optimization "sighted cheats" enabled for this run. These local optimizations are very effortful, many being cubic or worse in problem size in the worst case. The ones selected in the right column for this run are at least of square order in the problem size.


This size of this list of new heuristics ("monstrosity" wouldn't be too strong a term) , all written in one day after a refactoring epipheny, is what forced me to shred out Traveller's checkbox controls window into what are now nine such windows, to keep Traveller as something that would fit on a screen, preferably an 800x600 screen, granted with all the windows stacked in a heap.

And that's pretty much the state of the art for Traveller as of May 24th, 2002. Of course, having solved the fully populated Koch Snowflake of size 3072 nodes, I instantly kicked off a run to solve the next fully populated larger one, size 12288. The first generation may finish before I expire. Or not. [Actually, it did. After 1875 seconds of setup (to do the greedy seeding workload), the first generation took merely an additional 4967 seconds to run, with otherwise the identical setup as shown here except for "number of cities".]