Memetic computing

Memetic computing is a novel computational paradigm that incorporates the notion of meme(s)^[1] as basic units of transferable information encoded in computational representations for boosting the performance of artificial evolutionary systems in the domain of search and optimization.^[2]^[3]^[4]

The term memetic computing is often unassumingly misinterpreted to mean the same thing as memetic algorithms (MAs)^[5] that typically hybridize population-based global search algorithms with one or more local search schemes. Notably, memetic computing offers a much broader scope, perpetuating the idea of memes into concepts that pave the way towards simultaneous problem learning and optimization approaches.

Methods

There are two different methods that describe the history and rise of memetics in computing. These are human-crafted memes and machine-crafted memes.

Human-crafted memes

One of the most widely recognised instantiations of the memetic computing paradigm are the first-generation memetic algorithms (MAs). In particular, MAs are referred to as hybrid algorithms, prescribing a marriage between a population-based global search coupled with one or more local search schemes (interpreted as computational manifestations of memes) such as heuristic solution refinements, gradient descent procedures, etc. The specific choice of local search heuristics are handcrafted (manually specified) by a domain expert and often require a reasonably deep understanding of the problem at hand.

The second generation MAs focus on adaptive data driven selection and integration of memes from a manually specified catalogue of multi-memes (a pool of memes);^[6] gleaning patterns (knowledge) from the data generated during the course of a search/optimization run so as to ascertain promising combinations of memes at runtime.^[7]^[8]

Machine-crafted memes

It is only recently that the concept of memes were set free from the narrow scope of merely hand-crafted local search heuristics, paving the path towards fully automated extraction, dispersal and exploitation of knowledge memes. In this era of data-democratization with access to modern computing platforms, emerges an unmanned multi-meme setting; one in which memes, capturing diverse forms of higher-order problem-solving knowledge, are uncovered by machines. They are thereafter made available for reuse across various problems. As such, making it possible for advanced optimizers to automatically harness the transmitted memes and orchestrate custom search behaviours on the fly without human intervention.

Applications

The concept of memes have been exploited in various research fields, for example, robotics engineering, multi-agent systems, robotics, optimization,^[9] software engineering, and the social sciences etc.

References

^ Dawkins, R. (1976). The selfish gene. Oxford University Press.
^ Ong, Y. S., Lim, M. H., & Chen, X. (2010). Memetic computation—past, present & future [research frontier]. IEEE Computational Intelligence Magazine, 5(2), 24-31.
^ Chen, X., Ong, Y. S., Lim, M. H., & Tan, K. C. (2011). A multi-facet survey on memetic computation. IEEE Transactions on Evolutionary Computation, 15(5), 591-607.
^ Gupta, A., & Ong, Y. S. (2018). Memetic Computation: The Mainspring of Knowledge Transfer in a Data-Driven Optimization Era (Vol. 21). Springer.
^ Moscato, P. (1989). On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech concurrent computation program, C3P Report, 826, 1989.
^ Krasnogor, N., Blackburne, B. P., Burke, E. K., & Hirst, J. D. (2002, September). Multimeme algorithms for protein structure prediction. In International Conference on Parallel Problem Solving from Nature (pp. 769-778). Springer, Berlin, Heidelberg.
^ Krasnogor, N., Blackburne, B. P., Burke, E. K., & Hirst, J. D. (2002, September). Multimeme algorithms for protein structure prediction. In International Conference on Parallel Problem Solving from Nature (pp. 769-778). Springer, Berlin, Heidelberg.
^ Ong, Y. S., & Keane, A. J. (2004). Meta-Lamarckian learning in memetic algorithms. IEEE transactions on evolutionary computation, 8(2), 99-110.
^ Feng, L., Ong, Y. S., Lim, M. H., & Tsang, I. W. (2015). Memetic search with interdomain learning: A realization between CVRP and CARP. IEEE Transactions on Evolutionary Computation, 19(5), 644-658.

WIO
techitio

[1] Dawkins, R. (1976). The selfish gene. Oxford University Press.

[2] Ong, Y. S., Lim, M. H., & Chen, X. (2010). Memetic computation—past, present & future [research frontier]. IEEE Computational Intelligence Magazine, 5(2), 24-31.

[3] Chen, X., Ong, Y. S., Lim, M. H., & Tan, K. C. (2011). A multi-facet survey on memetic computation. IEEE Transactions on Evolutionary Computation, 15(5), 591-607.

[4] Gupta, A., & Ong, Y. S. (2018). Memetic Computation: The Mainspring of Knowledge Transfer in a Data-Driven Optimization Era (Vol. 21). Springer.

[5] Moscato, P. (1989). On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech concurrent computation program, C3P Report, 826, 1989.

[6] Krasnogor, N., Blackburne, B. P., Burke, E. K., & Hirst, J. D. (2002, September). Multimeme algorithms for protein structure prediction. In International Conference on Parallel Problem Solving from Nature (pp. 769-778). Springer, Berlin, Heidelberg.

[7] Krasnogor, N., Blackburne, B. P., Burke, E. K., & Hirst, J. D. (2002, September). Multimeme algorithms for protein structure prediction. In International Conference on Parallel Problem Solving from Nature (pp. 769-778). Springer, Berlin, Heidelberg.

[8] Ong, Y. S., & Keane, A. J. (2004). Meta-Lamarckian learning in memetic algorithms. IEEE transactions on evolutionary computation, 8(2), 99-110.

[9] Feng, L., Ong, Y. S., Lim, M. H., & Tsang, I. W. (2015). Memetic search with interdomain learning: A realization between CVRP and CARP. IEEE Transactions on Evolutionary Computation, 19(5), 644-658.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]