Beyond memetic algorithms

I used to be a genetic algorithms enthusiast - but more recently I have come around to the idea that they are based on an old and out-of-date type of evolution - one that doesn't learn from its mistakes very efficiently. In the real world, genes invented brains that then led to culture and cultural evolution - which is a faster and better kind of evolution, one which is better able to approximate our ideals of inductive inference.

In this case, it seems sensible to follow nature's approach - and use virtual genes to control the parameters of neural networks (or a similar learning component) which are able to transmit their learned findings to each other via culture, bypassing their original genome. This is what is done in memetic algorithms.

Will nature go beyond this approach, and if so, can we help it along? One of the next steps seems fairly obvious: use a neural network (or a similar learning component) to help along the evolution of the virtual genes that control its own development by using intelligent design. In other words, use memetic and genetic engineering. This step finally closes the loop between brains and genes: first genes made brains and then brains learned how to do engineering and then became able to apply engineering techniques to their own genes.

There should be several benefits associated with using engineering techniques and intelligent design. Agents using self-directed evolution can select mutations deliberately, based on whether tests on them are likely to increase the knowledge base or otherwise lead to success. This eliminates some of the cost associated with testing random variants. Evaluation can be performed partly under simulation - which should be faster and cheaper than testing everything in real life. Interpretation of the results also changes as a result of being able to store a history of past successes and failures which can be processed using interpolation and extrapolation techniques in the development of new variants.

Why cultural evolution is faster

So far most comparisons of the rate of cultural evolution - relative to the evolution of DNA-based creatures - have failed to control for the shorter generation times of memes compared to their hosts. A failure to do this leaves open the possibility that cultural evolution is faster than mammal evolution simply because memes have shorter generation times than mammals do. This is a problem with Charles Perreault's 2012 article on the topic, for example, as I pointed out at the time.

John Wilkins laid down the gauntlet on this issue in 2009, here:

the speed of cultural evolution is pretty much the same as the speed of biological evolution. The problem is that the “rate” is not absolute. Speed in evolution is always relative to generations, not to years. I feel that cultural evolution will tend to be roughly the same relative rate as biological, if only because error rates tend to be at or about the same general level in transmission processes.

However, intuitively it seems as though cultural evolution has led to nuclear power and moon landings in a short period of time - while organic evolution stumbled around for billions of years without doing these things. It seems as though empirically, cultural evolution really is faster, contra-Wilkins.

There's no shortage of theoretical candidates that hope to explain why cultural evolution is faster. In cultural evolution, mutations take place in brains, rather than cells. Variation can arise as a result of intelligent design, using interpolation and extrapolation. Evaluation can be performed under simulation. If you consider brains as containing Darwinian or quasi-Darwinian processes then the generation time there is even faster than cultural generation times - faster even than bacterial generation times.

One of my favorite candidates for a factor that explains the increased speed of cultural evolution involves the distinction between supervised learning and reinforcement learning. In supervised learning, mistakes are corrected by a supervisor, that presents the correct solution. A common alternative to this is reinforcement learning - where actions are scored by a reward function or a utility function. Mistakes are scored, but not corrected.

In organic evolution, organisms are mostly scored - in terms of reproductive success. However, bad quality actions are mostly not corrected. Supervised learning is associated with having a brain. Once you have a nervous system you can often learn using supervised learning. An important function of the brain is predicting consequences of actions - and the most common case of supervised learning involves predicting future sensory inputs. Here, after predictions relating to future sensory inputs are made, sensory inputs are actually received. The predicted and actual perceptions can be compared and supervised learning techniques can be used to correct any mistakes. Though there's no actual supervising agent, this qualifies as supervised learning - since the correct output is presented to the learner on every timestep.

Where does culture come in? Culture makes individual learning add up over the lifetimes of multiple individuals. Without culture, learned information is lost when the individual dies and their brain is eaten by worms. In principle, learned information can still get into the germ line via the Baldwin effect - but that is still a pretty slow process. With cultural transmission, information acquired using supervised learning can directly be passed down the generations and it can accumulate over time.

I won't lay out the case here for supervised learning being faster and better than reinforcement learning - that's part of machine learning folklore.

At first glance, this seems like an argument for psychological evolution being faster than DNA evolution. After all, brains have been around for 500 million years or so. They aren't a new phenomenon. So, how can supervised learning explain how it is only cultural evolution that seems faster? The idea is that psychological evolution is also faster, but that until the origin of culture, it couldn't really go anywhere. Without culture, information in brains is obliterated in every generation and can't really accumulate. As I mentioned, it can still affect evolutionary rates - via the Baldwin effect. No doubt the Baldwin effect does speed up evolution - but it does not do so as much as cultural transmission does.

I think these observations help to address some criticisms of cultural evolution. For example, here's Massimo:

The conclusion that biological and cultural evolution are different also nicely accounts for the fact that cultural evolution is so much more dynamic (it happens much faster) and unpredictable than its biological counterpart. If we think of both as instances of Darwinism that difference becomes more puzzling.

To start with, this is a bit of a straw man, practically nobody is saying that cultural evolution and biological evolution are exactly the same (excepting maybe Ben Cullen).

Anyway, according to the idea described on this page, one of the most significant differences is explained by learning theory - it is supervised learning. The impact of this on evolution dates back 500 million years or so - to the origin of brains. However before culture got started, its influence on the evolutionary process was somewhat muted - due to the regular destruction of information in brains in every generation.

Supervised learning represents a type of feedback from outcomes to the production of new variants to test. In the context of evolutionary theory, this is somewhat similar to Lamarckian inheritance: the inheritance of acquired characteristics. It is however important to note that this is not really a new effect - it dates back 500 million years. Nor can one say that such evolution is not "Darwinian" - since Darwin was an enthusiast for such feedbacks. Indeed, he promoted a theory of "gemmules" which featured feedback from somatic cells to the germ line. What we can say is that cultural evolution is not Weismannian. It features non-selective feedback from the phenotype to the genotype. However, we must also note that evolution in the organic realm is not really Weismannian either. Weismannian evolution - in which phenotypes only affect genotypes via selection and mate choice - was a product of Weismannian's choice of traits. He cut the tails off rats - and observed that this 'acquired characteristic' was not inherited. If Weismann had looked at rat fleas of rat pox instead he might have drawn the opposite conclusion - that acquired characteristics were inherited.

In computer science, lack of access to supervised learning helps to explain the limitations of genetic algorithms and genetic programming - and helps to explain why memetic algorithms are needed.

Tim Tyler: Memetic programming

Transcript: Hi. I'm Tim Tyler and this is a video about memetic programming.

The term "memetic programming" is often used to refer to mental software.

In computer science there is a hardware software divide - which is based on how easy systems are to upgrade: hardware is difficult to upgrade while upgrading software is easy. Much the same classification scheme maps pretty neatly onto animal nervous systems. In particular, brains are hard to upgrade, while learned information is easy to upgrade. Socially learned phenomena are a lot like a type of cultural software. Culture is easily hot-swapped and modified much like software is. As with computer software, there are memetic programs written in memetic codes - and there are memetic programmers and deprogrammers.

While this usage of the term "memetic programming" is interesting, it isn't the topic of this video. Instead, this video is about the subset of memetic algorithms that are based on using a computer program of some kind as their genome.

To recap, genetic algorithms were used to solve optimisation problems, starting in the 1960s. In the 1990s, genetic programming was popularised by John Koza. Koza used a computer program as a genome and developed programs with a tree-like structure, in an attempt to make the crossover operation more useful. Around the same time, memetic algorithms were conceived. Where genetic algorithms attempted to mimic organic evolution, memetic algorithms drew inspiration from cultural evolution. They typically featured individual or social learning in combination with more conventional aspects of genetic algorithms.

Computer programs are an interesting and flexible target for evolutionary approaches to optimization problems. They typically help to provide a neat split between the genome, a developmental program and the resulting phenotype. The use of tree-shaped chromosomes has advantages in that recombination potentially becomes more wide-ranging. A tree-shaped genome makes it a bit harder to exchange functionally-corresponding modules between two trees - but this is a manageable problem.

One issue associated with most kinds of computer program is that they are often relatively poorly suited for parallel programming. You can fork execution threads - but this is a clumsy approach to parallel execution. Automatic parallelization is another possibility - but this also has serious limitations. Similar universal media which are more suitable for parallelization include neural networks, networks of logic gates and circuit board floorplanning. However attempts to make mutation and recombination-friendly versions of these have not been very successful so far. Consequently, these parallel representations tend to be treated as phenotypes - produced from computer programs by a developmental process - which brings us back to having a computer program as a genome again.

There are quite a few papers on memetic algorithms, genetic algorithms and genetic programming. However, memetic programming hasn't received much attention from academics yet. There are only a few papers on the topic so far. It ought to be a fertile mix of genetic programming and memetic algorithms.

Many picture a future in which teams of machine programmers collectively work on the source code of the next generation of machines. This is the essence of memetic programming. If these sorts of dynamics are going to be important in the future, then we should start studying them more seriously now.

Enjoy.

Tim Tyler: Memetic algorithms

Transcript:

Hi. I'm Tim Tyler and this is a video about memetic algorithms.

While social scientists have mostly ignored or misunderstood memetics, the topic has received much warmer welcome from computer scientists. Where social scientists lamented their complex, integrated cultures being atomized into isolated memes, the computer scientists shrugged and went on to use the idea to solve their engineering problems.

Computer scientists had previously employed genetic algorithms as a means of finding solutions to their problems. These involve virtual creatures who are rewarded for producing better solutions to whatever optimization problem their creators are trying to solve. The virtual creatures are iteratively modified using mutation operators, and are maintained in a breeding pool - allowing for recombination to take place.

Cultural evolution appears to have dramatically increased the rate of development of human civilization. If culture evolves faster than DNA does, perhaps we can improve the power of our computer optimization strategies by drawing of some aspects of cultural evolution. This led to the idea of memetic algorithms.

Memetic algorithms are similar to genetic algorithms - but in addition to mutation, recombination and selection, they make use of individual learning, social learning and teaching. Where genetic algorithms were inspired by organic evolution, memetic algorithms draw inspiration from cultural evolution.

Evolution took billions of years to produce creatures sophisticated enough to produce an open-ended type of cultural evolution based on behavioural imitation. This appears to have been because observing the actions of another and then recreating them is not a trivial task. Detailed imitation of behaviour is technically quite a difficult reverse-engineering task, which requires complex cognition to perform.

However, fortunately, we do not have to wait until we have human-level machine intelligence before machines can make use of social learning techniques. We can engineer virtual environments in which even the relatively dumb artificial agents that we can build today can enjoy the benefits of cultural transmission.

Rather than passing on cultural information by a clumsy process based on behavioural imitation, memetic algorithms can work with creatures which have been designed for direct thought transfer. Agents can can record their sense data and replay them for the benefit of other agents. Behaviours can be encoded in a portable format and ported directly between agents. Memories can be directly downloaded from one agent and uploaded into another. Cultural transmission is pretty easy for machines - it doesn't require advanced intelligence.

Memetic algorithms may include a genetic component - and thus may exhibit meme-gene coevolution. Not DNA genes - of course - but rather the same kinds of genes that are used with genetic algorithms. In cases where both memes and genes are involved, there is a tradeoff between the resources expended on each type of evolution.

So far memetic algorithms have become quite a popular technique, with many books and papers on the topic and a string of international conferences dealing with the subject.

Memetic algorithms lie directly on the path which leads towards machine intelligence. Cultural evolution in humans illustrates the process machines will need to master to continue their growth. Machines are masters of mind-to-mind thought transfer, which makes it easy for them to engage in social learning. If you have a partly-intelligent machine, one obvious thing you can do to boost its power is to network it together with other similar machines - and let them cooperate with each other. The dense environment provided inside modern data centers provides an ideal environment for machines to engage in social activity with each other.

Overall, it seems highly likely that memetic algorithms will play a key role in the development of machine intelligence. Memetic algorithms will thus probably prove to be the most important application of memetics - in the long term.

Enjoy,

---

References

• Tyler, Tim (2013) Memetic algorithms

Collective intelligence meets universal Darwinism

There's a substantial community of machine intelligence researchers which are oriented around the concepts of "collective intelligence" and "swarm intelligence". Memetic algorithm enthusiasts have been trying to spread the word about memes to these folk for a long time. We've already had four International Conferences on "Swarm, Evolutionary, and Memetic Computing", for example.

Memetic algorithms are, by their nature, parallel, distributed systems - based on a population of interacting agents - the whole field is based on the concepts of collective intelligence and collective wisdom.

What I want to say in this post, is that the opposite is also true. Part of the reason why the concepts of "collective intelligence" and "swarm intelligence" are interesting is because they involve a sprinkling of cultural transmission - which sets up a behavioural evolutionary process. The ants in ant colony optimisation are copying the behaviour of other ants - via selectively-laid pheremone trails. The birds in a flock are selectively copying the behaviour of other birds. This kind of selective behavioural copying is also the basis of memetics. That is no accident, the fields have the same basic foundation - in universal Darwinism.

Behavioural Darwinism isn't the only reason why collective intelligence exists. Part of the effect involved arises through sheer aggregation. When a hundred agents guess at the number of beans in a jar, the average of their guesses is better than the opinion of any individual. There are some different effects involved there.

Memetic algorithms

One of the standard optimization strategies in computer science is genetic algorithms. These emulate organic evolution by using mutation and selection to identify the solutions of optimization problems.

Memetic algorithms are similar - but in addition to mutation and selection, they make use of individual learning, social learning and teaching. As Moscato (1989) put it:

While genetic algorithms have been inspired in trying to emulate biological evolution. Memetic algorithms would try to mimic cultural evolution.

Memetic algorithms were inspired by the observation that cultural evolution appears to have dramatically increased the rate of evolution of human civilization. If memevolution is, in some sense, faster than genevolution, maybe we can harness the power of memevolution to solve optimisation problems.

Direct thought transfer

Evolution took billions of years to produce creatures sophisticated enough to produce an open-ended type of cultural evolution based on behavioural imitation. This is because observing the actions of another and then recreating them is not a trivial task. Detailed imitation of behaviour is technically quite a difficult reverse-engineering task, which requires complex cognition to perform.

Do we have to wait until we have human-level machine intelligence before memetic algorithms can make useful contributions? No. we can engineer virtual environments in which even the relatively dumb artificial agents that we can build today can enjoy the benefits of cultural transmission. This effectively bypasses the whole problem.

Rather than passing on cultural information by clumsy processes based on behavioural imitation, memetic algorithms can work with creatures which have been designed for direct thought transfer. This can take a variety of forms. One possibility is the ability to directly pass on experiences. We can imagine the creatures have a recording device, and a device to replay the recordings to other creatures. This would be broadly similar to how humans can help each other to learn by sharing audio-visual experiences with video cameras. Other possibilities include knowledge and skill transfer. If the virtual creatures can be persuaded to represent their knowledge and skills in a portable format, this information can be transmitted directly from one creature to the next.

Collective intelligence

Groups of virtual agents being involved can potentially result in the effects associated with collective intelligence. Group-related dynamics are possible in more traditional genetic algorithms too - but social learning forces the creatures together, encouraging cooperation, and hopefully resulting in group dynamics that facilitate solving collective action problems.

Cooperation

Genetic algorithms are normally considered to be a type of competitive process - but one of the aims of memetic algorithms is to harness the power of cooperation. Letting the creatures to learn from each other encourages them to form social groups, and to work together.

Coevolution

Memetic algorithms may include a genetic component - and thus may exhibit meme-gene coevolution. Not DNA genes - of course - but rather the same kinds of genes that are involved with genetic algorithms. In cases where both memes and genes are involved, there needs to be a tradeoff made between the resources expended on each type of evolution. Managing this trade-off is a non-trivial problem.

Hybrid systems

Of course, machines don't need to have their own virtual world to be able to participate in cultural evolution. They can participate directly - by coevolving with humans on the internet. This is sometimes known as the man-machine symbiosis. It produces a kind of "impure" memetic algorithm - in which the components involved are a messy mixture of organic and machine elements. Of course such "messy memetic algorithms" are currently of great importance. This is partly because the humans and the machines can usefully compensate for each others' weaknesses. However in the future, it seems likely that we will increasingly see more machine dominated spaces - in which humans are too slow and stupid to be able to usefully contribute. Ultimately, it seems likely that we will see a memetic takeover.

Cultural algorithms

Cultural algorithms appear to be a subsequent reinvention of memetic algorithms by different researchers. The names appear to be close synonyms and the subject area appears to be the same. As far as I can tell, these were independent inventions.

Success story

Memetic algorithms has been one of the success stories of memetics in academia. There have been a long series of books, conferences and papers on memetic algorithms and memetic computing. Geeks tend to be meme-friendly, I have noticed.

Machine intelligence

Memetic algorithms lie directly on the path which leads towards machine intelligence. Cultural evolution in humans represents the process machines will need to master if they are to make very much progress. Machines are masters of mind-to-mind thought transfer, which makes it easy for them to engage in social learning. If you have a partly-intelligent machine, one obvious thing you can do to boost its power is to network it together with other similar machines - and let them cooperate with each other. The dense environment provided by modern data centers provides an ideal environment for machines to engage in social activity with each other.

Overall, it seems highly likely that memetic algorithms will play a key role in the development of machine intelligence. Memetic algorithms will thus probably prove to be the most important application of memetics - in the long term.

References

• Ferrante Neri, ‎Carlos Cotta, ‎Pablo Moscato (2011) Handbook of Memetic Algorithms
• Chi-Keong Goh, ‎Yew-Soon Ong, ‎Kay Chen Tan (2009) Multi-Objective Memetic Algorithms
• William E. Hart, ‎Natalio Krasnogor, ‎J.E. Smith (2004) Recent Advances in Memetic Algorithms
• Bijaya Ketan Panigrahi, ‎Ponnuthurai Nagaratnam Suganthan, ‎Swagatam Das (2010) Swarm, Evolutionary, and Memetic Computing: First International Conference
• Bijaya Ketan Panigrahi, ‎Ponnuthurai Nagaratnam Suganthan, ‎Swagatam Das (2011) Swarm, Evolutionary, and Memetic Computing: 2nd International Conference (Part 1)
• Bijaya Ketan Panigrahi, ‎Ponnuthurai Nagaratnam Suganthan, ‎Swagatam Das (2012) Swarm, Evolutionary, and Memetic Computing: 2nd International Conference (Part 2)
• Bijaya Ketan Panigrahi, ‎Ponnuthurai Nagaratnam Suganthan, ‎Swagatam Das (2012) Swarm, Evolutionary, and Memetic Computing: 3rd International Conference
• Bijaya Ketan Panigrahi, ‎Ponnuthurai Nagaratnam Suganthan, ‎Swagatam Das (2013) Swarm, Evolutionary, and Memetic Computing: 4th International Conference
• Bijaya Ketan Panigrahi, ‎Ponnuthurai Nagaratnam Suganthan, ‎Swagatam Das (2014) The 5th Joint International Conference on Swarm, Evolutionary and Memetic Computing (SEMCCO 2014) & Fuzzy and Neural Computing (FANCCO 2014)
• Wikipedia (n/a) Memetic algorithms
• Liang Feng, Yew Soon Ong, Ah Hwee Tan, Ivor Wai-Hung Tsang (2012) Meme as Building Block for Evolutionary Optimization of Problem Instances