I’ve read some memetic algorithms papers, but I never read this one. You did me a favour by pointing to the right section among the 68 pages :)
Now, I don’t deny that Moscato and other MA people were inspired by memetics and Dawkins. What I’m saying is the difference between GAs and MAs fails to correspond to the difference between genes and memes. I’m not alone: p. 19 says “The GA community would like to say that MA are only a special kind of GA with local hill-climbing.” That is what I said before.
The essential difference between MAs and GAs is the extra local search. This is supposed to be analogous to the ability of a martial arts master to make not random changes to his/her memes (genetic mutations are random), but directed changes. There are two problems with this:
In MAs, the hill-climbing does, in all cases I have seen, boil down to using random mutations and discarding the bad ones. (How else would we do hill-climbing, on a black-box fitness function?) So the changes are not really directed any more than GA mutations are directed, when the GA uses selection.
I think there is a lot more to the idea of memes than just directed changes. What about their non-particulate nature, in Dawkins’ phrase? That has no analogue in MAs that is not already in GAs. What about their weird method of combination, which is more like compounding than crossover? That has no analogue in MAs, as far as I know.
Are there some other features that distinguish MAs from GAs? Moscato mentions non-”genetic” representations, meaning non-linear ones. That has been common in GAs for a long time. I use tree-based, grammatical, and real-valued representations all the time. Even if (using the example in the paper) two-dimensional representations were common in MAs and unheard of in GAs, memes are not more accurately represented by matrices of bits than they are by lists of bits. Neither representation is adequate for the almost unrepresentable space occupied by memes.
Any other distinguishing features? Cooperative versus competitive coevolution (p 20)? Common in GAs, and more importantly, common in real-world genetic evolution.
The essential difference between MAs and GAs is the extra local search. This is supposed to be analogous to the ability of a martial arts master to make not random changes to his/her memes (genetic mutations are random), but directed changes. There are two problems with this:
In MAs, the hill-climbing does, in all cases I have seen, boil down to using random mutations and discarding the bad ones. (How else would we do hill-climbing, on a black-box fitness function?)
That is an easy question. A “black-box fitness function” doesn’t mean the function is completely unknown. One is allowed to presume Occam’s razor. That means that a range of techniques are likely to work when designing the next generation of trials: linear interpolation, extrapolation, fourier analysis of the fitness landscape—and so on. You can also keep historical records of notable past successes and failures—to help guide your search, use inductive inference, and take advantage of the rest of standard scientific toolkit.
I think there is a lot more to the idea of memes than just directed changes. What about their non-particulate nature, in Dawkins’ phrase? That has no analogue in MAs that is not already in GAs.
Well that’s because there are already analog genetic algorithms—or at least real-valued ones—which are about as “non-particulate” as you can get while remaining inside a digital computer.
To simulate cultural evolution some of the more important things you need are individual learning and social learning in a population. Much depends on how good your learning algorithms are. Yes, there are other aspects of cultural evolution—but if we knew how to reproduce them all in machines, we would have advanced machine intelligence by now. Today’s memetic algorithms are necessarily a work in progress. However, the goal of simulating cultural evolution—and taking advantage of its obvious power—was the aim from the very beginning.
I’ve read some memetic algorithms papers, but I never read this one. You did me a favour by pointing to the right section among the 68 pages :)
Now, I don’t deny that Moscato and other MA people were inspired by memetics and Dawkins. What I’m saying is the difference between GAs and MAs fails to correspond to the difference between genes and memes. I’m not alone: p. 19 says “The GA community would like to say that MA are only a special kind of GA with local hill-climbing.” That is what I said before.
The essential difference between MAs and GAs is the extra local search. This is supposed to be analogous to the ability of a martial arts master to make not random changes to his/her memes (genetic mutations are random), but directed changes. There are two problems with this:
In MAs, the hill-climbing does, in all cases I have seen, boil down to using random mutations and discarding the bad ones. (How else would we do hill-climbing, on a black-box fitness function?) So the changes are not really directed any more than GA mutations are directed, when the GA uses selection.
I think there is a lot more to the idea of memes than just directed changes. What about their non-particulate nature, in Dawkins’ phrase? That has no analogue in MAs that is not already in GAs. What about their weird method of combination, which is more like compounding than crossover? That has no analogue in MAs, as far as I know.
Are there some other features that distinguish MAs from GAs? Moscato mentions non-”genetic” representations, meaning non-linear ones. That has been common in GAs for a long time. I use tree-based, grammatical, and real-valued representations all the time. Even if (using the example in the paper) two-dimensional representations were common in MAs and unheard of in GAs, memes are not more accurately represented by matrices of bits than they are by lists of bits. Neither representation is adequate for the almost unrepresentable space occupied by memes.
Any other distinguishing features? Cooperative versus competitive coevolution (p 20)? Common in GAs, and more importantly, common in real-world genetic evolution.
EDIT: added to second-last paragraph.
That is an easy question. A “black-box fitness function” doesn’t mean the function is completely unknown. One is allowed to presume Occam’s razor. That means that a range of techniques are likely to work when designing the next generation of trials: linear interpolation, extrapolation, fourier analysis of the fitness landscape—and so on. You can also keep historical records of notable past successes and failures—to help guide your search, use inductive inference, and take advantage of the rest of standard scientific toolkit.
Well that’s because there are already analog genetic algorithms—or at least real-valued ones—which are about as “non-particulate” as you can get while remaining inside a digital computer.
To simulate cultural evolution some of the more important things you need are individual learning and social learning in a population. Much depends on how good your learning algorithms are. Yes, there are other aspects of cultural evolution—but if we knew how to reproduce them all in machines, we would have advanced machine intelligence by now. Today’s memetic algorithms are necessarily a work in progress. However, the goal of simulating cultural evolution—and taking advantage of its obvious power—was the aim from the very beginning.