3 ms·

People have these odd ideas about what a "GA" is. The Genetic Algorithm is an algorithm, not a particular representation of candidate solutions (vectors, lists

People have these odd ideas about what a "GA" is. The Genetic Algorithm is an algorithm, not a particular representation of candidate solutions (vectors, lists, trees, whatever). Likewise Koza-style Genetic Programming isn't an algorithm at all: but largely a representation. That seems pedantic, since of course GAs have certain classic representations and GP has a certain traditional algorithm. But it's important in this case, because (1) non-tree representations can be used handily to evolve code: for example, see machine-code GP or Grammatical Evolution, both of which use GA-style lists. And (2) because to my knowledge there's little in GP which would support the claim that "every part of the replication process is simultaneously optimizing". Or maybe he meant that Koza-style tree GP was providing "redundancy" (in the form of introns), which is odd since this is hardly viewed as a positive: but at any rate, introns exist in all sorts of GA representations, such as machine-code GP lists. At any rate, there seems to be a lot of confusion there.

mdda 16y ago
Ok - just to be clear, I was talking about GA in its standard bit-twiddling setting, rather than as an overall approach. Also, I'm not really saying GP (again, the original Koza-style tree manipulation type) is a magic cure-all : I just like the way it's more 'meta' than bit-twiddling GA. Are introns bad? An outside observer might think so, but something about the overall algorithm must like them... As to being confused : I'm surprised that anyone would think that this whole representation problem has any kind of cut-and-dried answer yet. There's still a lot of room for innovation here - and which directions to explore are pretty much a question of taste.
- mfukar 16y ago
  You make an interesting case, which I think is backed up by two things, in the special case of the x86 instruction set: - Instruction opcodes and arguments don't occupy a fixed space or position. This leads to a significant increase in lethality of mutations. Some other factors that contribute to this is the large instruction set, and the fact that opcodes and arguments are directly connected (context-specific). Straight-up GA does provably not perform well, unless there's a meta-language involved, as the article shows. I'd dare say this is very close to Koza's approach, and it also seems to be close to Michael Korns' approach, which is more recent. - "Instruction set" put aside, mutations in a x86 system (or in any other computing environment, for that matter) happens on a bit granularity. The sort of natural redundancy that would allow GA to operate on a sufficient population for robust mutations to appear is not there, without a metalanguage. (even ECC in memory tends to not be favoured, so resistance against bit flips, ie. point mutations) Also, it seems to me that without a "natural" redundancy mechanism within an instruction set, it is impossible for other types of mutations, namely deletion/insertion/duplication, to produce survivable offspring. As a (probably not very good) metaphor one should consider what would happen to aminoacids if we were to consider codons as their building blocks (disregarding nucleotides).
- SeanLuke 16y ago
  > Are introns bad? An outside observer might think so, but something about the overall algorithm must like them... Just because an algorithm tends to produce an unwanted result does not mean it's suddenly desirable. Yes, introns are bad. Credentials: My dissertation and several subsequent publications were on the subject of introns.

mdda 16y ago

Ok - just to be clear, I was talking about GA in its standard bit-twiddling setting, rather than as an overall approach. Also, I'm not really saying GP (again, the original Koza-style tree manipulation type) is a magic cure-all : I just like the way it's more 'meta' than bit-twiddling GA. Are introns bad? An outside observer might think so, but something about the overall algorithm must like them... As to being confused : I'm surprised that anyone would think that this whole representation problem has any kind of cut-and-dried answer yet. There's still a lot of room for innovation here - and which directions to explore are pretty much a question of taste.

mfukar 16y ago
You make an interesting case, which I think is backed up by two things, in the special case of the x86 instruction set: - Instruction opcodes and arguments don't occupy a fixed space or position. This leads to a significant increase in lethality of mutations. Some other factors that contribute to this is the large instruction set, and the fact that opcodes and arguments are directly connected (context-specific). Straight-up GA does provably not perform well, unless there's a meta-language involved, as the article shows. I'd dare say this is very close to Koza's approach, and it also seems to be close to Michael Korns' approach, which is more recent. - "Instruction set" put aside, mutations in a x86 system (or in any other computing environment, for that matter) happens on a bit granularity. The sort of natural redundancy that would allow GA to operate on a sufficient population for robust mutations to appear is not there, without a metalanguage. (even ECC in memory tends to not be favoured, so resistance against bit flips, ie. point mutations) Also, it seems to me that without a "natural" redundancy mechanism within an instruction set, it is impossible for other types of mutations, namely deletion/insertion/duplication, to produce survivable offspring. As a (probably not very good) metaphor one should consider what would happen to aminoacids if we were to consider codons as their building blocks (disregarding nucleotides).
SeanLuke 16y ago
> Are introns bad? An outside observer might think so, but something about the overall algorithm must like them... Just because an algorithm tends to produce an unwanted result does not mean it's suddenly desirable. Yes, introns are bad. Credentials: My dissertation and several subsequent publications were on the subject of introns.