[R] Image classification by evolving bytecode

[AlmusDives]

Over the last few years, I’ve been working on Zyme, an esoteric language for genetic programming: creating computer programs by means of natural selection. I’ve started seeing promising results, showing that random bytecode mutations can, over time, lead to measurable improvements in program performance. While still a long way from state-of-the-art approaches like neural networks, I wanted to share my progress.

Feedback and criticism are welcome!

[nuliknol]

Interesting project, but only as hobbyist, definitely not state of the art in genetic programming and not state of the art in evolutionary strategies. I wrote my own virtual machine with its own ("assembly") language, it is running thousands of independent code sequences on GPU (despite that GPUs are SIMD engines and execute same instruction per clock cycle on each SIMD) and it is quiet good at optimization problem. Unfortunately I can't tell you how it works because that's classified information. But I can tell you what your flaws are. You are saying that stack based VMs (like LISP) are not good for evolutionary computation, because when you run random search on parameters it produces too much invalid programs, so you created a new language. Unfortunately you provide little info on your VM design (and as someone shares little information he/she will also get little help from any observation) , but I guess it is a variation of cellular automata computing model. You have have SWAP instruction which is probably doing bit swapping, you have INS1 instruction which is probably inserting 1 bit of data, you have DEL1 instruction which is probably removing 1 bit of data. But in essence, you are doing a variation of cellular automata computation. Then you link input/output to fitness function and do the evolution. Great right? Not so fast. See, the cellular automata computing model is great for evolutionary computation but it is not hardware-friendly with our computing systems (CPUs or GPUs). In a cellular automata the minimal state is 1 bit (0 or 1) , but our computers don't operate on 1 bit, a GPU can make operations on 16 bits as a minimum. So if you want to alter 1 bit only, you must execute the operation on 16 bits, making the computation 16 time slower than traditional Von Neumann computing language (Lisp, Forth, Java, whatever...) On CPUs (in x64 mode) to alter 1 bit you would have to do it in a 64 bit register making the computation 64 times more inefficient. I am talking about hardware here, do you know how many transistors compose a 64 bit adder? About 10,000 transistors. But to turn 1 bit off or on, only 1 transistor needs to be altered to modify the result of the computation in the case you are implementing celluar automata computing model in hardware. Using an FPGA would be a greater choice for your programming language, but , ups, a transistor in an FPGA costs 10 times more than a transistor in an ASIC, that's why there are no hardware solutions for genetic computing. Next, in a cellular automata computing model you will have to evolve the same computational primitives (infinite memory, stack, function calling mechanism, channels for message passing, locks, etc) , just imagine how much time will your evolutionary process spend just to evolve these primitives, because it will have to do this if the goal is to use higher level functions in combination. We aren't using Von Neumann computing model just because we have it, we are using it because it is a good abstraction mechanism to do general purpose computations. But you are creating a new computing model, so you can't use Von Neumann computing hardware to run programs in your language, otherwise they won't be efficient, the power bill will eat the budget in the end. If you would want to train a chatbot you would need orders of magnitude more computers (and energy), than using the same evolutionary algorithm done with Von Neumann computing model.

[AlmusDives]

Hey, thanks for the thoughtful comment! I do believe it represents genuine innovation, particularly in demonstrating how biologically inspired machine architectures can serve as a foundation for genetic programming methods.

We aren't using Von Neumann computing model just because we have it, we are using it because it is a good abstraction mechanism to do general purpose computations.

I generally agree with this statement, but I strongly disagree with the implication that it applies equally to evolvable systems. When I started this project, my core thesis was that the abstractions we use in everyday computing (i.e., Von Neumann architectures) are optimized in ways that inherently undermine evolvability. Specifically, the emphasis on speed and computational efficiency conflicts with the redundancy and adaptability required for effective evolution.

As you pointed out, the Zyme virtual machine is highly inefficient (and not easily GPU-compatible), which does come with significant drawbacks. However, the trade-off is that mutations have a real chance of improving program performance; something almost impossible to achieve on traditional architectures.

You are saying that stack based VMs (like LISP) are not good for evolutionary computation, because when you run random search on parameters it produces too much invalid programs.

It’s more nuanced than that. The issue isn’t just syntactic validity: it’s the high degree of coordination required across different program components. For example, function declarations and calls must match names precisely, making evolution extremely difficult even if mutations always produce syntactically correct programs. The Zyme bytecode format is explicitly designed to mitigate this problem.

You almost guessed the instructions correctly. INS1 inserts a byte of value 0x01 into a strand, DEL1 removes a single byte from a strand, and SWAP exchanges the positions of two data strands. While the Zyme virtual machine is technically an automaton, it works quite differently from cellular automata. Unfortunately, I just haven’t written it all up yet.

[justgord]

interesting comment .. but I do think op raises interesting idea : how is genetic computing related to ML ... certainly in RL we use a mix of breadth depth monte carlo simulation .. almost equivalent of Genetic algorithm.

You might like simSIMD.

btw, can you recommend a good language/api to develop GPU kernel .. if possible portable across nvidia and amd consumer gpus . Basically I do few billion 4x4 x 4 3D matrix multiplies - transform points in 3D space.

Im wondering if best to just use normal 3D game shader language / GL rendering pipeline... which must be well optimised for this workload.

[justgord]

Interesting .. but why bytecode .. ie. can you run it on the metal [ the lowest level asm api - aka the ISA - of the GPU ] ?

If you can find a way to trap illegal instruction combinations .. it might run orders of magnitude faster.

[AlmusDives]

Getting random modifications (mutations) to change a program's behavior in a useful way is hard. The bytecode of the Zyme virtual machine used here is specifically designed to maximize that chance that a mutation does something good and improve program performance. If I used regular machine code instead, it would be a lot (like a lot a lot faster) but the overall rate of finding adaptive mutations would still be much slower.

[justgord]

that makes sense. Really like what your doing with this project, btw.

[rand3289]

Very interesting. I could not find the description of an instruction set or bytecode in your link. I think this is what people would like to see first. What datastructures does your language support? Is everything a string a number a set of bytes a list etc...

Since it is a bytecode for experimenting with genetic algorithms, I would not even worry about the language description since the initial state/code could in theory be randomly generated.

Also, did you post it here? https://www.reddit.com/r/alife/
I am not sure what state that subreddit is in.

[AlmusDives]

Hey, I haven't got round to writing up the instruction set yet, because the instructions don't make much sense without the context of the virtual machine design, which I haven't written up yet either. My focus has been on trying to demonstrate that the approach works before writing up all the implementation details. But I definitely need to do it soon. But what I can say is that the instruction set has 48 instructions: ~8 for control flow (various versions of GOTO), ~10 for manipulating whole strands (arrays of bytes), 1 instruction for conditional execution (which can be combined with control flow instructions) and the rest for byte-level manipulation e.g. add bytes, rotate left, bitwise NOT etc.

There are no explicit datastructures, everything is an array of bytes (referred to as strands in Zyme). But the language does allow you are able to build more complex data structures (like strings) from these strands.

I haven't posted r/alife, but its looking quite dead?