Are there deterministic algorithms that generate a sequence of Hamilton Tours that is superior to a sequence of randomly chosen tours, when applied to the TSP (by applying to the TSP, I understand summing up a tour's edge weights)?
Whether Low Discrepancy is better that Random Generation is decided via the index of the Optimal Tour in the Low Discrepancy sequence of all tours.
If it is more likely to encounter the Optimal Tour in the Low Discrepancy sequence earlier than in the Random Generation sequence, then Low Discrepancy is conidered superior.
That measure of superiority is only one concrete example; other ways of defining it are also possible, while eventually yielding a different decision.
Background of my question is to learn whether similar improvements as in multidimensional integration are possible when switching from Monte Carlo to Low Discrepancy.
Note however, that multidimensional integration only serves as an example for the beneficial use of Low Discrepancy but is otherwise considered as being completely unrelated to TSP
I also appreciate any further information as well, like how to define a discrepancy measure for tours, estimates for performance gains, etc.
I know that there are methods for generating Low Discrepancy permutations, but I want information dedicated to tours and not to permutations in general.
What I have tried so far, is to combine the ability to calculate the n-th permutation via factoradic numbers with n taken from an appropriately chosen van der Corput sequence.
I'm not quite satisfied with that approach because:
-the calculation of the n-th permutation is based on lexicographical ordering but, I would prefer the order generated by the Steinhaus-Trotter algorithm (because of the minimal change from one permutation to the next)
-the van der Corput sequence corresponds to inverting the sequence of bits and is thus tailored for value ranges that are powers of two; numbers ranges that are factorials do not fit that pattern and one has to reject certain values of the van der Corput sequence because they are outside the valid range
-cyclicity and symmetry are not taken into account
all that adds some bias, which worries me