Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A math/algorithms question.

  1. Apr 23, 2010 #1
    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).

    2. Relevant 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.

    3. 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...
    [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.
    Last edited: Apr 23, 2010
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?