genetic algorithm tool GA(tool) for all possible (or shortest ) paths found in topology

i want ga function to find all possible paths found in any topology

http://i.imgur.com/Lu4Ge.gif

for example for this topology if the source (1) and destination (6) where 1 & 6 is nodes and L is link . can be represent the L1 as 1 and L2 as 2 ...etc.

all possible paths =( 4,8) &(1,2,7) &(4,3,7)&(1,5,9)&(1,2,3,8)......etc

or any help about this function...

with my thanks.

[Walter Roberson]

We cannot see images that are stored on your computer.

http://www.mathworks.com/matlabcentral/answers/7924-where-can-i-upload-images-and-files-for-use-on-matlab-answers

[Walter Roberson]

There are an infinite number of possible paths unless you exclude loops.

[mohammed sportman]

i loaded the topology.

[Walter Roberson]

1-2-3-4-1-2-3-6-4-1-2-3-4-1-2-3-4-....

[mohammed sportman]

i don't understand i mean for fixed topology.

what is it ??????????

[mohammed sportman]

or for small topology .

[Walter Roberson]

One of the possible paths starts

L1 L2 L3 L4 L1 L2 L7 L8 L4 L1 L2 L3 L4 L1 L2 L3 L4

and keeps going for another 23454935674398923479332881 steps.

[mohammed sportman]

i mean one direction -----> with out to return to any point(node) two wise

[Walter Roberson]

GA functions need an output, a "fitness". What would be the fitness function in this case?

GA is for attempting to minimize something. A minimization is a single output (though other sets of inputs might have the same output.) GA is not suitable for finding all possibilities -- not unless the fitness function is somehow "number of possibilities not explored".

[mohammed sportman]

in this case i want just the shortest path

[Walter Roberson]

Your paths have no weight, so by convention the weight of each link is 1. Then since any number of nodes are allowed in the path, the shortest path will be to connect any two (allowed) nodes together and use that. More correctly, the shortest path will be to start at any node and go no-where in no steps, for a path length of 0.

[mohammed sportman]

No, i used (Hop - count Routing) that depend at the number of Node that is mean when we have 3 possible path the first have two *jumped node and the second have *five jumped node and the third have one jumped node.

in case two paths have the same jumped node . the function will select one of them Randomly (indiscriminately)

[Walter Roberson]

Your question does not impose any restrictions on where the paths must start or end: your question asks for "all possible paths" found in the topology.

[mohammed sportman]

for the topology above . it must start at source node then to destination node for example if the S=1 and D=2 then

how many paths found :-

     1 ---> 2 :-     1     0     0     0     0        
     1 ---> 2 :-     4     3     2     0     0     
     1 ---> 2 :-     4     3     6     5     0     
     1 ---> 2 :-     4     8     7     2     0     
     1 ---> 2 :-     4     8     9     5     0    
     1 ---> 2 :-     4     3     7     9     5     
     1 ---> 2 :-     4     8     7     6     5     
     1 ---> 2 :-     4     8     9     6     2

The shortest path must be the first .

i want the function that calculate that . i want just to input the Node number and Link and the ga function output must be the shortest .

Answer 1

[Walter Roberson]

It is unfortunate that your version of ga() does not have IntCon.

One technique that can be used:

Let your ga have as many virtual variables as there are nodes. Let the virtual variables represent nodes in a path. To evaluate any particular list of values, start from the beginning of it. If the first value is not the desired first node, then assign a high cost and return. If the value after that is not reachable from the first node, assign a high cost and return. If the value is the destination node, assign a low cost that is lower for shorter paths, and return. If the value is a destination node that has already occurred along the path, assign a high cost and return. Keep evaluating along the path like this, verifying topology first then whether the destination has been reached then whether a loop was found. If you get to the end of the virtual variables and have not reached the destination and have not had a loop then there must have been a programming error.

Note that the final returned path will have values that have been ignored, as the examination stops when the destination has been reached. This is not a problem.

Now as you do not have IntCon in your version of ga(), instead encode each virtual variable by a series of bits sufficiently wide to hold the maximum node number. Be sure to add a step to verify the decoded values are in range for node numbers as you go along (it does not matter if you get invalid node numbers after you have reached the destination.)

Now what you might want to consider is whether all those cases of "high cost" should be the same "high cost", or if some of them should be considered to be worse than others.

[mohammed sportman]

i can not understand .

i want practice example about that .

[mohammed sportman]

any help help help?????