First: Genetic Algorithms. A GA is a program designed to find the solution to a problem via iterative searching - that is, the algorithm itself searches for a solution to a problem. GAs in particular use biologically-inspired methods to perform the search.
The analogy with biological systems is like so: a GA spawns multiple search 'organisms,' which 'live' in the algorithmic environment. With each generation, each organism is tested against a 'fitness' function, which determines how well the organism solves the problem we're looking for a solution for. Only the fittest of each generation survive, passing on their genes (parameters) to the next generation. Each of the survivors randomly selects a mate and mixes the genes (with some random mutation factors), with the expected outcome of iteratively evolving toward the best possible solution to the problem.
I've built a couple small GA systems in the past - nothing for anything in production, but mostly just to toy with - and I find them particularly interesting, especially given how very small changes in how the organisms select mates, mix genes, and mutate can result in large-scale changes in the search behavior.
Now the second part: Brainfsck (which is actually spelled with a 'u' instead of an 's', but I want to maintain some civility here) is a programming language in which there are only 8 legal characters - '>' '<' '+' '-' '.' ',' '[' and ']'. Each of these characters performs some function in the program, usually with regards to manipulating 8-bit memory locations called cells. Wikipedia has more information - but suffice it to say that Brainfsck has been proven to be Turing complete, which means it can be used to perform any computable function (provided it has infinite memory).
Here's how Genetic Algorithms and Brainfsck can come together: I mentioned earlier that GAs use digital organisms and 'genetic' parameters to evolve toward a solution. What if those parameters were snippets of Brainfsck programs, and the fitness function ran the Brainfsck programs to see what their output is, and check that output against an expected output? Wouldn't it, in theory, be possible to iteratively evolve toward the solution of any computation problem that way?
Just a random thought that's been plaguing me for the past couple of days. Don't think anything particularly interesting would come of this.
Subscribe to:
Post Comments (Atom)
Posts
1 comment:
I don't know whether you're familiar with the concept of Genetic Programming - it is a method of evolving computer program code based on a set of predefined functions via GA-like evolution of expression trees representing said programs, similar to what you suggest. Suffice to say, it does work better than one would expect beforehand. However, it is crucial to choose the set of symbols well suited to your task for the algorithm to show any measurable progress of evolved programs in solving that task.
So while it's entirely possible to evolve anything using the set of symbols 'brainfsck' uses, just looking at the code examples on wikipedia I'd say the chance of evolving organisms that would not only solve the task, but do antyhing meaningful that could be tested to measure their fitness would be infinitesimaly low.
Something like evolving intelligent life from inanimate molecules. Who would have thought that would work ;)
Post a Comment