[NP combinatorics] - A New Kind of Science: The NKS ForumA New Kind of Science: The NKS Forum
Pages:1
NP combinatorics
(Click here to view the original thread with full colors/images)
Posted by: Philip Ronald Dutton
A while ago I was watching the progression of some 2d CAs.. you know those that produce gliders, etc.? Of course, initially, there is all this 'junk activity' which eventually settles down to somekind of regular patterns (at least the CAs I was exploring did this).
Well it reminded me of simulated annealing or genetic algorithms and the way those kinds of processes eventually 'settle' ('settle'= no longer can get out of local search spaces).
Anyway I thought it would be cool to encode a typical graph (application of max clique, for example) as a limited 2d 'space of
cells' on which you could run some of those 2d CAs. My hope is
that when some of the CAs settle you could take that as a representation of the stalled global search and somehow decode the leftovers as your new solution to the combinatoric problem...
If there is something like a glider then maybe that means there are more than one solution but that they are all equivalent (or optimal, or approximately optimal, etc.)....
It sounds crazy but I really like the idea of a CA doing its thing (pattern growth, decay, whatever) and producing a combinatoric 'computation' simply by going from step to step....
In other words, if the CA is running, then maybe it's execution is a computation.... or something like that?
Posted by: Philip Ronald Dutton
(along similar lines of thought as the above post)
... What is the relation from Graph theory to CAs? Seems like a CA is operating on what is essentially a graph?
This is why i wondered about using CAs to compete against Genetic Algorithms and Simulated Annealing in the case of
searching for optimal solutions to NP type graph problems..
Posted by: Tony Smith
What is the relation from Graph theory to CAs? Seems like a CA is operating on what is essentially a graph?
In a CA, each node has an identical neat geometrical neighbourhood of adjacent nodes. CA's are an infinitesimal subset of possible graphs.
The reason some of us see more general graphs as a better candidate model of reality is that we can allow their geometry to evolve. This is seen as a possible way to account for quantum entanglement. A couple of other implications of the possibility of dynamically eliminating and/or generating nodes are addressed in the longish thread started by Mark Suppes to explore a Mechanical Gravity Theory. While CA's are much easier to program and much easier on human visual perception, they can't sensibly model changing geometries.
On your broader question as to whether an arbitrary CA might be answering some question, it seems we are starting to run into problems with presumed implications of terminology. Calling what simple (Class 4 or maybe other) mechanisms do a "computation" seems to ordinary users of the language to presume some kind of purpose, some question to be answered. In reality the mechanisms, singly and collectively, just do what they do. Any perceived purpose requires at least some history of selection, whether natural or engineered.
Posted by: Kovas Boguta
One can certainly take any graph and superimpose some CA on it. This is discussed on 930 and 936.
Certainly a computation is done by the CA, and it does reflect the structure of the graph.
It is another question if that computation corresponds to some graph property that has been traditionally investigated. It is certainly possible that for some particular automaton it does - or that some other automaton computes an interesting property that no one has noticed yet.
There are of course various graph algorithms that have been constructed to compute various properties of graphs. It would not at all surprised me that somewhere out there is a CA that happens to compute the same thing in a radically different way.
Sounds like someone should do some experiments!
Posted by: Tony Smith
Kovas, I think you are stretching things a bit to go from:Cellular automata can be set up so that each cell corresponds to a node in a network. (See page 936.) The only requirement is that around each node the network must have the same structure (or at least a limited number of possible structures). (930)
andThe cellular automata that we have considered so far all have cells arranged in regular arrays. But one can also set up generalizations in which the cells correspond to nodes in arbitrary networks. (936)
to "One can certainly take any graph and superimpose some CA on it."
The quoted passages of NKS do not appear to make any claim that cellular automata can represent networks which allow unlimited variation of node topology, both across the graph and across time, which is much more like what some of us expect of the network which will best model the underlying physics of the world we find ourselves in.
Simulating such truly general graphs is going to take some real ingenuity. Comprehending such simultations at more than the most basic level is going to take even more than that. Personally I don't expect to ever get comfortable experimenting with anything much beyond CAs, but I'm not about to stop thinking about certain other kinds of "simple mechanisms", especially graphs, which CAs cannot sensibly represent, the PCE notwithstanding.
Posted by: Philip Ronald Dutton
briefly back to combinatorics:
(i am thinking in pictures here guys/gals)
given some kind of general graph (perhaps restricted a bit
to ease the application of CA) we could let a 2d CA
run its course. Here is the fun part:
Say we are trying to find the INDEPENDENT SET of the graph.
Well, after the CA makes a progression (not sure the right word) we basically have an attempted solution to the IND. SET problem.
Why? because the CA 2d cells are either on or off... the cells themselves are an encoding of an attempt to provide a solution to the IND. SET. (if a cell is on then that node in the graph
was selected else not selected.)
So assign a fitness factor (like we do with genetic algorithms) to that "step" of the CA. Maybe keep track of average fitness... some will be invalid solutions to the IND. SET (obviously).
Let it run for awhile and record how well it did ...
then the program can use another rule... and then another...
and then another... all on the same graph, keeping track of
average fitness or best solution found, etc.
Sounds like it would be easy to do in Mathematica....
The next part is how do you generalize findings to different
graphs as apposed to just the one graph.??
Wish I could mess around with this...
Posted by: Kovas Boguta
With regard to Tony Smith's post:
I said you can put _some_ CA on any graph.
One can define a totalistic CA on any graph, which will simply total up the values of the nodes to which it is connected and apply the rule.
One thing that I should mention is that the way I think of CA's on graphs, the underlying graph does not change over time. Which means that you can know what the maximum value will be, and so can create a rule that will always work.
Posted by: Philip Ronald Dutton
Tony,
Being the amatuer in this field I recklessly claim that any undirected graph could easily be represented by a 1D CA (why do this? maybe i can explain an idea). I think it would be rather easy to start.
First: Given a graph G with say 12 nodes (undirected),
average 3 or 4 edges per node.
Construct a 1D CA simply by making each cell correspond to a node in the graph. Now, you can construct rules which represent the edge connections.
There, now the graph is represented by the CA.
But big deal!! So what? Well,
If you can really do this: I think one thing you can do is set the CA up with an initial cell (perhaps random) configuration. Now as the CA begins to process row by row, the rules (which encode the graph edge connections) could (if you set them up right) actually be shuffling the selection of graph nodes as it trys to find solutions for the INDEPENDENT SET (my favorite NP problem) .
I tried to do this by hand a long time ago. My idea was that the CA could act as the selection mechanism by changing the nodes selected based on node neighbors, etc.
Hard to explain but I will think about it more and perhaps restate my idea.
Posted by: Kovas Boguta
Im not familiar with the literature on the independent set problem... what kinds of algorithms are known for solving it?
One thing to keep in mind is that while an ordinary CA distinguishes between left and right cells, the graph CA cannot.. all edges are created equal, as it were. Which is why totalistic CAs are a good match. And for the purposes of the independent set problem, one probably only wants to update based on information like color total of the neighbor anyway.
Another important feature of CAs, in fact of the the defining features, is that the neighborhood looks exactly the same at every point. One of the things that makes me a bit nervous about the graph CAs is the possibility of having some nodes with different numbers of neighboors. One can create a rule definition that will happen to work, but it is sort of like mixing two different CA rules.
So at first i would start by looking at graphs with a uniform number of edges per node. Then just enumerate all the totalistic CAs of that class, and see if one of them solves the problem...
Posted by: Jason Cawley
Just a minor distinction that may be useful in this discussion. A graph is one pattern. An evolving network model is a linked series of graphs, such that each successive graph stems from the previous according to a definite re-write or substitution rule. CA to graph, and CA to network of successive graphs, are thus two different things.
Posted by: Philip Ronald Dutton
I am trying to set up for experimenting with 1D CA and max Independent Set problem for graphs. My initial idea was to use cell 1 to represent node A, cell 2 = node B, cell 3 = node C, etc.
Much frustration has resulted !
When I draw a small graph on paper I usually label the nodes from top to bottom and from left to right starting with 'A'. There is no reason why I should have to put them into the 1D CA in alphabetical left to right order which means there are very MANY ways I could lay the graph nodes into the 1D CA. For each one of these arrangements, the output of the CA (whatever it is) will be different! This seems inescapable!!
On top of that, you must essentially run the CA an N number of times (corresponding to num of graph nodes) because you always start with initial condition of one of the cells being selected (so as to be able to compare for which resulting set has the most independent nodes - which is hopefully more than what is produced by other algorithms).
:(
So,... how can it be done?
It is like a paradox: a CA is a graph, but a graph should not be embedded into a CA (using node to cell as above) because of spatial problems which become obvious when you try to interpret the CA run at any given step.... surely i am missing something here!
Posted by: Kovas Boguta
The basic answer is that of course one cannot just evolve a regular CA and claim that it corresponds to a CA on a network.
What one needs to do is write some code that directly encapsulates the idea.
Perhaps your idea is different from mine - my idea of this is you have a graph, and each node on the graph has a color. At each step you update the color of each node according to a rule that is based on the color of the node and the colors of the nodes it is connected to.
Thats the idea that needs to be implemented.
The fundamental characterstic of this automaton is that its topology can be vastly different from the traditional CA--and so it is not surprising that one cannot immediately reformulate it in the language of a traditional CA. Although i think it would be interesting one could find out how to emulate a network CA on a traditional CA.
Here is how i would approach the problem.
Start with graphs in which all nodes have 2 edges. Have the rule be something that operates on the total of the colors of the adjacent nodes+itself. (totalistic)
This particular system may not be promising for the particular problem you are interested in, but it is a minimal graph-ca. If you can implement that, then you can start fiddling with it more to get what you want.
Posted by: Jason Cawley
Actually, using a regular graph (i.e. same number of connections at each node) with 3 connections from each node, with the 256 nearest neighbor, 2 color CAs, Seth Chandler showed how this could be done already, in work he presented at NKS 2003. Might contact him to get his notebooks on the subject.
Visualization can be a problem, because a regular graph does not have the simple locality of a standard CA, making it harder to see what is going on just by reading down the page. He used animation, which helped.
But Kovas is correct that the 2 connection regular graph case is even simpler. In addition to looking at that case (which is somewhat like a topological generalization of 2 color block CAs, in a way, since only 2 previous values matter in both), one might next generalize Chandler's 3 connection case by adding a third color to a 3 connection regular graph.
Posted by: Todd Rowland
I have a couple points, but need to develop some background.
First observation is that 2-regular graphs are just one dimensional, either in a line or on a circle, and are trivial to color. Two colors, except in the case of an odd cycle which needs three.
Constraints, like the coloring problem on graph, are discussed in the book on pages 210-221, and the problem of satisfying them is discussed on pages 342-350. But to go in this direction belongs in a new thread, since the techniques there are not cellular automaton.
In the problem of graph coloring, one of the basic algorithms is called the greedy algorithm. The idea is that if one happens upon a miscolored node, then just replace that node's color with a valid color. One way to implement it is by applying it randomly.
Sometime last year, I tried the greedy algorithm using a determinstic CA approach. The net effect was that intrinsic randomness from the CA did just as well as forced randomness. From a practical point of view, it seemed better to first arbitrarily give each node an ordering of its edges. Most implementations of graphs come with such an ordering anyway. Then instead of the CA being a symmetric function of the colors of its neighbors, it would be a function of a list of colors, given by the ordering of its edges. This made it easier for the intrinsic randomness to kick in.
What is interesting to note about the 1D case, with 2-regular graphs, is that the greedy algorithm is not the best. Let me define a greedy CA to be one which forces the center cell to be the opposite of its neighbors when its neighbors agree, and restrict ourselves to the cyclic case. Here are the greedy ECA's:
{5, 7, 13, 15, 21, 23, 29, 31, 69, 71, 77, 79, 85, 87, 93, 95}
Here are the ones which work just as well as any other ECA when starting from a single black cell:
{13, 69, 77, 79, 93}
In a typical greedy-type algorithm, as well as the relaxation problem which started this thread, one starts from random initial conditions. Two ECA's stand out using random initial conditions:
{57, 99}
I find it surprising that neither of these is a greedy algorithm. Can one prove that these are better than the other ECA's in finding a valid coloring starting from random cyclic initial conditions?
I should say what I mean by "better", since none of them are guaranteed to find a valid coloring from random initial conditions. I was using
score[ls_]:= Apply[Plus,1-Abs[Subtract@@@Partition[ls, 2, 1,1]]]
A more difficult question would be how to perform a search for effective graph coloring CA's for higher valency. The number of rules grows fairly quickly, especially if one wants to consider rules which aren't of the greedy type. Do rules 57 and 99 have any properties which makes them so good? That might restrict such a search.
Posted by: Jon Awbrey
Todd, et al.,
Have only skimmed this discussion
rather lightly so far, but here are
the forms that ECA rules 57 and 99
take in so-called cactus syntax:
q_57. (( q , (p) r ))
Read q = ~p & r.
q_99. (( q , p (r) ))
Read q = p & ~r.
See the Table attached to Note 1 on this thread:
http://forum.wolframscience.com/sho...s=&threadid=256
Jon Awbrey
Posted by: Philip Ronald Dutton
Given a graph (undirected) for which we are interested in the independent set (or other combinatoric related information) perhaps we could use a mobile automaton as a selector of nodes.
If the mobile automaton is coded to run "on top" of the structure (data structure) of a graph then every time the mobile automaton "updates" then it selects (possibly) a new graph node (corresponding to the CA cell which just got turned on by the automaton). For every step in which a new graph node gets selected, we can check the list of currently selected nodes for independent set solution "compliance." As soon as the list goes out of compliance we just reset the list and let the automaton keep running (since it is acting like a random selector) and then continue checking the lists.
Obviously the results would depend on how you encode the graph nodes into a ca cell arrangement. For example: is cell 1 = graph node A or is cell 1 = to some other graph node. The Possible combinations of graph node to cell CA mappings is unfortunately large.
I think any scheme for which such graph node to CA cell mapping schemes are attempted are doomed because of the cell arrangement nature of CA's and the possible number of combinations of how the mapping can occur.
It appears that CA or Mobile Automaton or possibly other automatons which use neighbor cells and cell grids are not going to provide much graph probing capability due to the mapping problem described above.
Reiterated:
Such cell-grid automatons do not appear to offer any capability to probe graphs due to the mapping problem. The information in a graph is inaccessible (by efficient means) to probing attempts of cell/grid automatons. Weak probing is due to: graph node to grid cell mapping issues.
Forum Sponsored by Wolfram Research
© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. |
Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings