How Can Genetic Algorithms Optimize Traveling Salesman Paths in Weighted Graphs?

[lawtonfogle]

I hope this is the best place to put this question, as mathematics of weighted graphs, though this is part of a larger genetics algorithm I am working on. I am quite unsure if this belongs in the math section or the computer science section though.

1. The problem statement
There is a 50 node fully connected graph. I have two paths that go though each node once and only once, except one node which is the very first and last node visited, so basically a traveling salesman path. Now, I am trying to figure a way to combine these two paths to generate a 3rd traveling salesman path that takes the best portion of each parent.

I am not currently concerned with computationally efficient algorithms (just nothing NP please).

Homework Equations

Mostly algorithms, not equations. If it is useful, I have 50 integers between 0-49 non-repeating stored as the order of the nodes. So 23, 7, 39 means go to node 23, then node 7, then node 39. I also have a 50x50 matrix with the weights from each node to every other node.

The Attempt at a Solution

My first attempt is that I look at node 1 and randomly choose the city it goes through from either of the 'parents path'. I then look at the next node not considered as a start or finish (2, unless I picked a path that went from 1 to 2). This creates 25 paths of length two that do have any repeating nodes. I then randomly link them.

The problem with this solution is that it has both an extreme element of randomness to it and that it does not insure getting the good paths from the parents.

The solution I am currently entertaining is to look at the path between the first and second nodes visited on the path and pick the path with lowest weight. I then repeat for the third and fourth nodes visited on the path, expect I check to make sure either possible third node has not yet been visited. I am not sure what to do if a given node has been visited already though.For example, let consider this following paths.

Mom = [23, 44, 8, 11, 2, 12...
Dad = [46, 17, 12, 43, 9, 23...

Check and see that 23 -> 44 is lower weight than 46 -> 17
So Child = [23, 44]
Then we check and see that 12 -> 43 is the lower weight than 8 -> 11.So Child = [23, 44, 12, 43]
Then we encounter a problem because both 2->12 and 9->23 have nodes previously visited.

I'm unsure what to do here. Possibly skip over this section and keep going, then come back and randomly refill using all nodes not yet picked.
Anyways, after doing the above and creating the array, I plan on look at every other pair of elements added and seeing which order creates the smallest distance.

So let say our path becomes [23, 44, 12, 43, 18, 37...

I would then check to see if
[23, 44, 12, 43, 18, 37...
or
[23, 44, 43, 12, 18, 37...
is the better (lower weighted) combination, and then pick the lower weight.

Once I have done this, I would then add that path to my population of nodes.

Also as a second question, when I 'mutate' my population, I switch two nodes and switch them. Do you think it would be better to only switch them if the resulting distance is lower, or just switch them. I would think just switching them, even if worse, adds more variety to the population, but I am quite unfamiliar in these sorts of problems.

 

[lippyka]

For your second question, it depends on what your goal is. If you want to maximize the overall fitness of the population, then only switching them if the resulting distance is lower makes more sense. On the other hand, if your goal is to explore a wider range of solutions, then it might be beneficial to switch them even if the resulting distance is worse, as this allows for more exploration. Ultimately, it's up to you to decide which approach best suits your goals.