I am working on a problem that has many different boolean functions involved, taking parameters defined in registers. I decided, for the fun of it (and to prevent me from including any bias), to try to evolve the optimal conjunction set, as WELL as the optimal instruction set. Now, I am running into some issues. First, I will have a limited number of registers and a limited number of possible instructions, each with a defined number of inputs. Inputs are register numbers. Each instruction will return either true or false given its inputs. Each instruction is included in a 'block' of other instructions, with boolean operators in between (AND, OR, XOR, etc) blocks and instructions. So (a and b or !d) or c would be two blocks, where (a and b or !d) is one block, and the full expression is the second, larger block. Boolean expressions are evaluated left to right. Now, my issue is, how do I 'evolve' these programs while still maintaining logical sense (meaning that it is still interpretable). I am thinking of having each instruction be its own sub block, and simply swap 'blocks' between two programs and arbitrarily mutating the boolean conjunctors, registers, and instructions. But this doesn't seem like it will necessarily converge to any sort of solution. Does anyone know any papers about this sort of topic? I have read the 'Efficient Evolutions of CISC Instructions' paper -- I was just wondering if anyone had any experience with this sort of work. Thanks!

hmmm

*all* boolean functions can be encoded as a lookup table.

All 1-input boolean functions can be encoded in a 2 bit table (2^1)
All 2-input boolean functions can be encoded in a 4 bit table (2^2)
All 3-input boolean functions can be encoded in an 8 bit table (2^3)

and so forth

Not-so-obvious is that the space of all N-input functions contains the space of all lower order functions.

So if you have 8 registers, any arbitrary boolean function of 8 or less inputs can be encoded in 2^8 = 256 bits

These boolean tables are relatively easy to convert into optimal boolean expressions which perform the same function.

Is this the sort of generalization you are after?

wooops, duped it.

This entry for Boolean Algebra (wikipedia) has some interesting information.

A block could consist of two inputs. Anything more can be simplified by mathematical manipulation into a series of two-input blocks.

(a and b or !d) or c
(((a ∧ b) ∨ ¬d) ∨ c)

Quote: Original post by AngleWyrm
A block could consist of two inputs. Anything more can be simplified by mathematical manipulation into a series of two-input blocks.

Rockoon1 said the same thing already...

Quote: Originaly post by Rockoon1
Not-so-obvious is that the space of all N-input functions contains the space of all lower order functions.

Proof that it is not so obvious ;)

That certainly makes work with blocks easier. Any thoughts on altering the sub block data to help conversion? Perhaps I can come up with someway to see how similar two blocks are in a given string...and mutate based on that. I dunno -- at the moment, I don't see how this thing will converge in a million years...

I am under the assumption that you plan on using traditional GA techniques... You really havent described your fitness function at all.

What does it mean to have both an "optimal conjuction set" and an "optimal instruction set"?

The first sounds to me like you simply want your problem functions to use a minimal number of 2-input Boolean function, in which case there are likely to be many equaly minimal solutions for any N > 2 problem function. Do you want the solutions to favor common sub-expressions for your set of probem functions?

I really don't know what the second thing is.. whats an optimal instruction set? Because when I think of optimal instruction sets, I think of 1 single instruction in the set which takes all the inputs and spits out an answer.

An instruction set is exactly what it says: a set of instructions. Instructions, in this case, would be a function taking any number of registers as inputs.

Assume that a task needs to be performed and the 'program' I am evolving determines whether or not to do a subtask based on any number of inputs. These inputs would be stored in the registers. So the overall expression would return a boolean stating whether or not to perform the subtask. The fitness function is based on the overall task needing to be performed, which is defined by how and when the subtask is called.

Sorry -- can't be much more specific than that...

But what does it mean to be an OPTIMAL instruction set?

A.I. generally doesnt throw the term Optimal around, instead prefering terms like Minimal and Maximal. That leads right to your cost or scoring function. What exactly is being minimized or maximized here?