I read about a really interesting idea called program evolution. Basically, to solve a problem the algorithm evolves programs, written in a way so that they can be coded as strings of numbers. Then a GA is applied to the string of numbers encoding the string while the fittness function checks how close the encoded program comes to the goal. For example: http://www.sover.net/~nichael/nlc-publications/icga85/index.html It seems like it'd be fun to see what programs the GA comes up with to solve different problems. My question is, after decoding the numbers to abtain the program, how do you run the program to try it out? Do you have to make your own compiler? Or is there an easier way? Thanks.

You could probably design it so that the encoding translated into an easy to interpret language, and just make an interpreter. The page you linked seems to use lisp type syntax, which is very consistent and so easy to interpret (especially in lisp).

Thanks, but how do you make an interpreter? Can you give me a general idea of how an interpreter works?
Thanks.

Use .Net DOM/compilers or reflection/emit.

(This allows you to dynamically write and execute new functions in memory at runtime)


I've thought about this before. The problem as I see it is that you have so many instructions and operands that tweaking even one jump destination off by one byte in memory instantly reduces the functionality of the code to zero.

A different/simpler language that doesn't allow 'bad' operations (such as branching to invalid locations) would reduce the 'dead zones' in your search space.

You could also have a system that detects which particular instructions cause an invalid operation and force them to be mutated.

[Edited by - Nypyren on October 5, 2007 1:56:35 AM]

Quote: Original post by daniel_i_l
Thanks, but how do you make an interpreter? Can you give me a general idea of how an interpreter works?
Thanks.

Yes. Its about 240 hours of college classes. But basically, you have three main distinct layers: a lexical analysis, which reads the input and convert it into symbols. A syntaxic analysis, which arrange this symbols into structures, and a semantic analysis, which in an interpreter case will perform the operations determined in the lexical analysis. In a compiler's case, this generates assembly code.

Lexical analysis is usually performed using regular expressions. But in this particular case, it is trivial since the input is already in lexical form.
Syntaxic analysis is typically performed using context-free grammars. The most popular form of grammar are LALR(1) grammars.
Semantic analysis is performed using semantic grammars. This part is a bitch for compilers, but is fairly straigforward for interpreters, if your syntaxic grammar make sense.

If you're still interested, you might want to take a look at the term parser.

Learning about interpreters would do a lot more good for you than getting into the hyped learning fad you are currently looking at, judging by your recent posts. Just my piece of advice :D

Steadler: Why would it be a better use of my time to learn about interpreters if I don't plan on making my own unique programming language (other than the extremely simple case i'm looking at now)? As it is I don't have much programming time so what would be the point of taking on some massive project (making an interpreter) that would give me little more than a pointless new language?
If I'm programming for fun isn't it better to focus on things I find interesting?
I'm not just ranting, I'm truly interested on your opinion here.
Thanks for your help,
Daniel

Quote: Original post by daniel_i_l
Thanks, but how do you make an interpreter? Can you give me a general idea of how an interpreter works?

An 'interpreter' is a wide concept encompassing many actual principles and programs. A pocket calculator or a CPU are technically interpreters, and so are virtual machines, web browsers, and so on. Depending on what you want to interpret, your task will be more or less complex.

Interpreting a human-read language is potentially difficult, as it implies lexing and parsing input to reach an in-memory representation of the program. Interpreting that representation (such as a LISP expression) is much easier.

Fundamentally, the work of an interpreter is described through operational semantics. You have access to several existing approaches: rewriting rules are generally the fundamental approach in functional languages, it explains how to transform an expression into a value (evaluation). Program state is the fundamental approach in imperative languages, it explains how every instruction modifies the state (which consists in the current execution pointer plus the contents of all variables). Depending on the language you want to interpret, one of these might be in order (for instance, the language in the article is imperative, and thus a world state approach would be better).

How about to create your own gene code, which will be decoded in terms of your task?

Genes could mean everything! What kind of problem do you wish to solve in evolutional way?

Quote: Original post by daniel_i_l
Steadler: Why would it be a better use of my time to learn about interpreters if I don't plan on making my own unique programming language (other than the extremely simple case i'm looking at now)? As it is I don't have much programming time so what would be the point of taking on some massive project (making an interpreter) that would give me little more than a pointless new language?
If I'm programming for fun isn't it better to focus on things I find interesting?
I'm not just ranting, I'm truly interested on your opinion here.
Thanks for your help,
Daniel

Parsers have a wide number of applications, for scripts, networking, IO, and yes, AI. But moreso, the mathematical and computer science principles they are build on, like regular expressions, have tons of other applications to. Finally, its a shining example of solid theory leading to very efficient applications: LALR(1) parsers have been used almost forever.

On the other hand, you are getting into hyped things with weak theoritical foundations and applying them to the wrong problems without realising what you are really doing. "Applying a GA" to "evolve a program" might sound very cool, but you describe it as "Perform a randomly re-seeded parallel gradient descent search on the space of all possible programs", you can see it is rather pointless. Kinda like having a thousand monkeys type in msdev and hope one of them comes up with a game.

Do NOT impliment or hijack a general purpose abstract language for Genetic Programming ..

The best program representations are graphs, or a subset of graphs such as trees.