[Don't cares] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


Don't cares

(Click here to view the original thread with full colors/images)


Posted by: Ed Meier

I was experimenting with searching for patterns using varying CA rules (I hope I'm using these terms correctly). That is, I would apply say, rule 86, see how close it got to what I was looking for, then apply rule 30, see how close it got me, and so on.

I set it up so that each input pattern was tied to a rule that generate the next output pattern. Then I would match that output pattern to another input pattern, apply the CA rule, and so on, trying to find the end pattern I was looking for.

I needed to be able to match output patterns to input patterns. To do that in a useful way I had to identify "don't care" bits. I did that by looking at the input pattern and output pattern and applying the boolean logic XOR operator. Anything that didn't change came out as a zero, which I made into a "don't care". This gave me the largest chance to chain together CA rules to get to the output I wanted.

Has anyone else experimented with this kind of thing?


Posted by: Kovas Boguta

Hi,

Ive played around a tiny bit with this sort of thing - First applying CA X for n steps, then applying CA Y for m steps. Because of the number of variations for the parameters i havent reached any good conclusions.

I dont quite understand the details of your setup. It seems like you are somehow trying to narrow your search space by figuring out parameters that dont matter. I guess i dont understand what you mean by the matching of the input patterns to output patterns. Presumabely input patterns (is this the same as initial conditions) are unconstrained, and they are what determine the output patterns.

It would be helpful to know what you are trying to achieve - are you trying to get the CAs to compute a particular bit sequence, or just exploring?

It is worth noting that certain kinds of rule compositions are themselves equivalent to CAs with more colors. So one can


Posted by: Ed Meier

Yeah, ok, now that I re-read this I used the word pattern too much. I'm trying to match output from a CA rule to an input pattern to continue processing it. That is given an output

101101

I could match it to input pattern:

x01x01 (not that it has to be symmetric)

This pattern would be associated with a specific CA rule, say 86.
I would then process those bits with CA rule 86 and see what output I got, then look for an input pattern to match, execute the CA rule for that pattern, say 30, and so on.

To come up with a new rule I run a bit pattern through a CA rule, then XOR the bits as described in my previous email, 0 become "don't-care" bits.

In this particular case I'm looking for optimal paths in a traveling salesman type problem.

What I'm doing is trying to use CA rules in Genetics Based Machine Learning (GBML) as described in Genetic Algorithms in Optimization and Search (or something like that) (Goldberg '84). In his book Goldberg never comes up with a good application of the "bucket brigade" part of his machine learning system. I think applying CA rules sequentially would be the perfect application for it.

I'm just exploring this because it's fun. Most of my applications are whimsy or trivial problems.

I have the GBML engine written. I just now am creating the fitness function and establishing values for the other parameters defined by Goldberg, life tax, reward, etc.

What was your application? Maybe it will work in the GBML bucket brigade also.


Posted by: Ed Meier

Oh, and right now I'm sticking with binary colors. I understand what Kovas Boguta said about certain rules combinations are equivalent to CA rules with multiple colors. That's good to know but the binary colors tie in well with the binary nature of genetic algorithms.

The multi-color CA rule might be good to explore as an optimization method. If the multi-color rules are optimizations of binary color rules, in certain cases, then we can explore the entire solution space with the binary CA rules. That's all I really want to do right now. We have to walk before we can run.


Posted by: Kovas Boguta

I understand the dont care bits now. Perhaps in a few days i will understand the rest of it too :)

The reason i was interested in the composition of rules is that I read a paper about using genetic algorithms to discover a cellular-automata based system to compute some common problems.

The two variables in their system were the number of steps each rule was evolved, and the rule numbers used.

I was very skeptical about their claims that the genetic programming was resulting finding optimal parameters.

My guess is that they sampled enough combinations that they were bound to find some rules that were more fit than others. An exhaustive analysis of the rule space would show what a typical random walk through it would discover -- and how it compared to the actual winning program. But i never got around to carrying out this experiment.


Posted by: Ed Meier

I'm throwing this at you kind of fast. I've been studying and working with this stuff for years so I apologize for not being considerate.

Your theory on randomly walking through the solution space and coming up with the same results as a GA would could be right. It depends on how they set up their fitness function. With a proper fitness function a GA will generate an answer in the top 5% of the best answer.

If the fitness function is bad or inappropriate, then yes a random walk through the solution space will give equally good results.


Posted by: Ed Meier

Yeah see, that won't work. My idea to simply XOR the input and output patterns to generate don't-cares neglects the surrounding bits in the input. The surrounding bits determine the output bit according to the CA rule, as we all should know by now.

No, the real solution to finding don't-cares for pattern matching is to run the input string through the CA rule, then invert the input string and run that through the CA rule. Any bits that are the same in those to bit strings can be considered don't-cares. No matter what the input, the output will be the same.

Or am I missing something else?

BTW, for the end bits position I use all four possibilities; 0s on both ends, 1s on both ends, 1 then 0, and 0 then 1. It's the only way since I'm searching in the middle of CA output for a certain pattern.


Posted by: Ed Meier

Ok so it turns out that this won't work at all. Sigh. I finally realized that the only way to declare a dont-care bit is if all permutations of the neighbor bits are the same. That is, whether the bit is on or off, the rule generates the same output. If the bit in question is 1, then no matter what the sidebits are the rule generates a 1. The same for zero.


Posted by: Ed Meier

Sorry, I hit enter there before I was finished.

So after a lot of analysis, I came to the conclusion that the only rules for which I could generate a don't-care condition were 0 and 256. Only in those cases will the current center bit come out the same regardless of what was input. That doesn't help.

I post this here just in case somebody else pursues this and can find the answer in the archives.


Posted by: Ed Meier

My declaration of defeat was premature. This can work, but there is a gotcha.

This may seem obvious to those of you who have worked with these rules for a long time. I feel dumb for taking so long to figure it out.

To find don't-care bits for CA rules the input string must first be run through the CA rule. Then each individual bit must be inverted and the rule run on that string. If the output is the same as the original input string then the inverted bit on the input string is a don't-care bit. It doesn't matter what it is coming in, the output will be the same.

For example:
Suppose my input string, I, is 23 and the rule, R, is 30. I use 6 bits to represent I like so:

I: 010111

When I run rule 30 against it I get output, O:
O: 110100 (I assume zeroes on both sides of I)

So now to check for don't-care bits in the input stream invert the first bit like so:
I^1: 110111

run rule 30 against it and the output is:
O^1: 110100

It didn't change! O matches O^1.

So the first bit in the input stream doesn't matter. It could be zero or one. Either way the output comes out the same.

So the pattern to match other inputs to starts out looking like this:
P^1: X10100

After inverting each bit and testing against O, the original output, the pattern to match other inputs to is:
P: X1XXX1

However, there is a gotcha! You can't have two don't-care bits in a row. The CA rule uses, as we all know well, the two bits on either side to determine the output bit.

The way to solve this problem is to create a separate rule whenever consecutive pattern bits come out as don't-care bits.

For example, to properly capture input string 23 we need two patterns to match to:
P1: X1X1X1
P2: X10X11

With these we can take random six bit input strings and compare them to these two patterns. All that match will be collected as "the same output as input string 23, rule 30."

(Again, this assumes that there are zeroes on both sides of the input string and the input pattern.)

That's how you find don't care bits!




Forum Sponsored by Wolfram Research

© 2004-2009 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