From Wikipedia, the free encyclopedia

Mathematics desk
< December 30	<< Dec | December | Jan >>	January 1 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

Contents 1 December 31 1.1 computer network; finding correct matrix represents 1.2 Constraints in Genetic Algorithms

[edit] December 31

[edit] computer network; finding correct matrix represents

There are 5 nodes; A,B,C,D,E. The graph represents the connections between the nodes of a computer network. If a 1 indicates the existence of a direct path between two nodes of the network, how the matrix(5x5) represents this graph using 1s and 0s ? The nodes follows; at A node- A to B, A to D, E to A. at B node- B to E, C to B, A to B. at C node- C to B, C to E, D to C. at D node- D to C, D to E, A to D. at E node- E to A, D to E, C to E, B to E.

I need your help. —The preceding unsigned comment was added by Ml320 (talk • contribs) 14:58, 31 December 2006 (UTC).

Draw a 5x5 table. Label each the rows with a node name, from A to E. Label each of the columns with a node name, from A to E. Put a 1 in the cell where row X meets column Y if there is a direct path from node X to node Y. I would also put 1s in the five cells on the diagonal of the table (because each node is always connected to itself) - but you should check the convention used in your course or textbook. Put a 0 in every cell in the table where there is not a 1. This 5x5 table of 1s and 0s is the entries in the adjacency matrix for your network.

For example, there is a path from node A to node B, so put a 1 in row A column B. But there is not a direct path from node A to node C, so put a 0 in row A column C.

Note that if all of your paths are bidirectional (so if there is a path from node X to node Y, then there is always a path from node Y to node X) then your adjacency matrix will be symmetric. Gandalf61 16:08, 31 December 2006 (UTC)

[edit] Constraints in Genetic Algorithms

How do we handle constraints that can only be numerically evaluated (available as a black box) in optimization based on genetic algorithms. How can I do it using the GA Toolbox in Matlab. I know adding a penalty is one approach, but is there any more elegant solution? Thanks and Happy New Year! deeptrivia (talk) 23:18, 31 December 2006 (UTC)

You mean there's a constraint which the genome must satisfy, and the only practical way to sample the space of satisfactory genomes is to pick genomes from some larger set and test each one against the constraint? If so, I don't really see any solution that would be substantially better than adding a penalty for failing the constraint. In fact, I'd say using a genetic algorithm (or some other adaptive method) with a penalty is the clever solution — these are exactly the kinds of problems which adaptive Monte Carlo methods were invented for. Of course, if you can approximate the actual constraint with some more convenient function, you could try using the approximation to bias the evolution away from the constraint; in statistical jargon this is known as importance sampling. —Ilmari Karonen (talk) 03:09, 4 January 2006 (UTC)