TSP: Generating N unique random indices in tricky set
Hi! I'm working on a type of the euclidian travelling salesman problem, and I'm going to try to solve it using an Genetic Algorithm.
One solution may be a route like this: 1-2-4-3-7-6-5. This means travel from town 1 to 2 etc up to city number 5 and also implies travelling
back to town 1 after town 5. Since the distances between cities are symmetrical, the above given solution is equal to the solution
1-5-6-7-3-2 (since the route 1-2-4-3-7-6-5-1 is equal (in travelling distance) to 1-5-6-7-3-4-2-1 due to symmetry).
I need to create an initial population of N solutions. These need to be unique, preferrably totally random solutions in the set of possible
solutions (wich is this case does not consist of all possible permutations!). Is there a way of doing this without running the risk of
getting stuck in a loop (generating the same solutions many times and retrying)? I don't want to risk this, since speed is an issue.
I've thought about ranking solutions and unranking them, but this involves computing faculties, and that may be very time consuming
and does not seem to be the optimal solution, although i've seen some implementations running in time complexity O(N).
Note: the number of cities may vary.
Any thoughts?
Regards
Alex
[1329 byte] By [
ArneWeisea] at [2007-10-2 15:16:36]
To get rid of this symmetry, I'd always make the second index smaller than the last one:
Always start at 1.
Pick two random indizes a, b from 2 to N, such that a<b.
Your tour will be 1-a -...-b.
Randomly fill in the remaining indices.
You still have the problem, that you might generate a tour multiple times, but this chance is so small, that I would just discard these and try again.
With n cities, (n-1)! / 2 such tours exist.The chance for the mth generated tour to be an existing one is 2 * (m-1) / (n-1)!. Or, more generally, the chance, that you have to calculate the mth tour p times is ( 2 * (m-1) / (n-1)! )^p>
Generating a random order of indices is not that difficult.
int[] arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = i;
for (int i = 0; i < n; i++) {
int k = (int) (Math.random() * n);
int x = arr[k];
arr[k] = arr[i];
arr[i] = x;
}
However, when dealing with a graph this approach probably doesn't
make that much sense, since it's unlikely there is an edge between
every node.
You probably want to generate an initial population where sequential
indices are adjacent nodes.
An alternative to GA is to determine the minimum spanning tree, and
traverse that. The MST appoach is within a factor of 2 of optimal. If
you're stuck on GA for this problem, then I think the hardest part is to
determine a good appoach for combining two solutions.
