Abstract
In computational intelligence, the term ‘memetic algorithm’ has come to be associated with the algorithmic pairing of a global search method with a local search method. In a sociological context, a ‘meme’ has been loosely defined as a unit of cultural information, the social analog of genes for individuals. Both of these definitions are inadequate, as ‘memetic algorithm’ is too specific, and ultimately a misnomer, as much as a ‘meme’ is defined too generally to be of scientific use. In this paper, we extend the notion of memes from a computational viewpoint and explore the purpose, definitions, design guidelines and architecture for effective memetic computing. Utilizing two conceptual case studies, we illustrate the power of high-order meme-based learning. With applications ranging from cognitive science to machine learning, memetic computing has the potential to provide much-needed stimulation to the field of computational intelligence by providing a framework for higher order learning.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Abramson M, Wechsler H (2001) Competitive reinforcement learning for combinatorial problems. In: International joint conference on neural networks proceedings. IJCNN ’01
Agarwal A, Lim M-H, Er M-J, Chew C-Y (2005) ACO for a new TSP in region coverage. IEEE/RSJ Int Conf Intel Robot Syst
Agarwal A, Lim M-H, Er MJ, Nguyen TN (2007) Rectilinear workspace partitioning for parallel coverage using multiple UAVs. Adv Robot 21(1)
Angeline PJ (1993) Evolutionary algorithms and emergent intelligence. Doctoral thesis, Ohio State University, Columbus
Applegate D, Cook W, Rohe A (2003) Chained Lin-Kernighan for large traveling salesman problems. INFORMS J Comput 15(1): 82–92
Arnold DV, Salomon R (2007) Evolutionary gradient search revisited. IEEE Trans Evol Comput 11(4): 480–495
Baraglia R, Hidalgo JI, Perego R (2001) A hybrid heuristic for the traveling salesman problem. IEEE Trans Evol Comput 5(6): 613–622
Beinenstock EL, Cooper L, Munro P (1982) Theory for the development of neuron selectivity: orientation specifity and binocular interaction in the visual cortex. J Neurosci 2(1): 32–48
Burke E, Cowling P, Causmaecker PD, Berghe G (2001) A memetic approach to the nurse rostering problem. Appl Int 15(3): 199–214
Caponio A, Cascella GL, Neri F, Salvatore N, Sumner M (2007) A fast memetic algorithm for off-line and on-line control design of PMSM drives. IEEE Trans Syst Man Cybern Part B Spec Issue Memetic Algorithms 37(1): 28–41
Dang J, Zhang Z (2005) A polynomial time evolutionary algorithm for the traveling salesman problem. Int Conf Neural Netw Brain
Dawkins R (1989) The selfish gene. Oxford University Press, USA
Francois O, Lavergne C (2001) Design of evolutionary algorithms-A statistical perspective. Evol Comput IEEE Trans on 5(2): 129–148
Gaudiot J-L, Kang J-Y, Ro WW (2005) Techniques to improve performance beyond pipelining: superpipelining, superscalar, and VLIW. Adv Comput (63)
Gutin G, Karapetyan D (2009) A selection of useful theoretical tools for the design and analysis of optimization heuristics. Memetic Comput 1(1)
Hart WE (1994) Adaptive global optimization with local search. University of California, California
Hasan SMK, Sarker R, Essam D, Cornforth D (2008) Memetic algorithms for solving job-shop scheduling problems. Memetic Comput J
Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor
Ishibuchi H, Yoshida T, Murata T (2003) Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Trans Evol Comput 7(2): 204–223
Johansson C, Lansner A (2007) Towards cortex sized artificial neural systems. Neural Netw 20(1): 48–61
Kazarlis SA, Papadakis SE, Theocharis JB, Petridis V (2001) Microgenetic algorithms as generalized hill-climbing operators for GA optimization. Evol Comput IEEE Trans on 5(3): 204–217
Kendall G, Soubeiga E, Cowling P (2002) Choice function and random hyperheuristics. In: 4th Asia Pac Conf Simul Evol Learn, pp 667–671
Kolodner J (1993) Case-based reasoning. Morgan Kaufmann Publishers Inc., San Francisco
Koza JR (1989) Hierarchical genetic algorithms operating on populations of computer programs. In: International joint conference on artificial intelligence. Morgan Kaufman Publishers
Koza JR (1991) Evolution and co-evolution of computer programs to control independent-acting agents. In: From animals to animats: proceedings of the first international conference on simulation of adaptive behavior
Koza JR (1992) The genetic programming paradigm: genetically breeding populations of computer programs to solve problems. Dynamic, genetic and chaotic programming. Wiley, London, pp 201–321
Koza JR (1992) Hierarchical automatic function definition in genetic programming. Foundations of genetic algorithms, vol 2. Morgan Kaufmann, San Francisco, pp 297–318
Krasnogor N (2002) Studies on the theory and design space of memetic algorithms. PhD, Faculty Comput Math Eng Bristol, UK, University West of England
Krasnogor N, Blackburne B, Hirst JD, Burke EK (2002) Multimeme algorithms for the structure prediction and structure comparison of proteins. In: Proc. parallel problem solving from nature. Lecture notes in computer science. Springer, Heidelberg
Krasnogor N, Gustafson S (2004) A study on the use of self-generation in memetic algorithms. Nat Comput 3(1): 53–76
Krasnogor N, Smith J (2005) A tutorial for competent memetic algorithms: model, taxonomy, and design issues. Evol Comput IEEE Trans 9(5): 474–488
Kuncheva LI, Jain LC (2000) Designing classifier fusion systems by genetic algorithms. Evol Comput IEEE Trans 4(4): 327–336
Land MWS (1998) Evolutionary algorithms with local search for combinatorial optimization. University of California, California
Lee JT, Lau E, Yu-Chi H (2001) The Witsenhausen counterexample: a hierarchical search approach for nonconvex optimization problems. Automat Control IEEE Trans 46(3): 382–397
Lenat D, Guha RV (1989) Building large knowledge-based systems. Addison-Wesley, Reading
Lim M-H, Gustafson S, Krasnogor N, Ong Y-S (2009) Editorial to the first issue. Memetic Comput 1(1)
Lin S, Kernighan BW (1973) An effective heuristic algorithm for the traveling salesman problem. Oper Res 21(2): 498–516
Merz P (2004) Advanced fitness landscape analysis and the performance of memetic algorithms. Evol Comput 12(3): 303–325
Merz P, Freisleben B (1997) Genetic local search for the TSP: new results. IEEE Conf Evol Comput
Meuth RJ, Wunsch DC II (2008) Divide and conquer evolutionary Tsp solution for vehicle path planning. In: Congress on evolutionary computation (WCCI’08)
Milano M, Roli A (2004) MAGMA: a multiagent architecture for metaheuristics. Syst Man Cybern Part B IEEE Trans 34(2): 925–941
Minsky M (1986) The society of mind. Simon & Schuster Inc, New York
Moscato P (1989) On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms, caltech concurrent computation program, C3P Report, 826
Mulder S, Wunsch DC (2003) Million city traveling salesman problem solution by divide and conquer clustering with adaptive resonance neural networks. Neural Netw
Neri F, Toivanen J, Cascella GL, Ong Y (2007) An adaptive multimeme algorithm for designing HIV multidrug therapies. IEEE ACM Trans Comput Biol Bioinform 4(2): 264
Nguyen HD, Yoshihara I, Yamamori K, Yasunaga M (2000) Modified edge recombination operators of genetic algorithms for the traveling salesman problem. In: 26th Annual conference of the IEEE industrial electronics society
Nguyen HD, Yoshihara I, Yamamori K, Yasunaga M (2007) Implementation of an effective hybrid GA for large scale traveling salesman problems. IEEE Trans Syst Man Cybern Part B 37(1): 92–99
Nguyen Q-H, Ong Y-S, Lim M-H (2008) Non-genetic transmission of memes by diffusion. In: 10th Annual conference on genetic and evolutionary computation (GECCO’08), Atlanta, GA
Nguyen QH, Ong YS, Krasnogor N (2007) A study on the design issues of memetic algorithm IEEE congress on evolutionary computation singapore. IEEE 2390–2397
Norman MG, Moscato P (1989) A competitive and cooperative approach to comple combinatorial search, caltech concurrent computation program, C3P Report 790
O’Neill M, Ryan C (1999) Automatic generation of high level functions using evolutionary algorithms. In: 1st International workshop on soft computing applied to software engineering. Limerick University Press, Limerick
O’Neill M, Ryan C (2001) Grammatical evolution. IEEE Trans Evol Comput 5(4): 349–358
Ong Y-S, Lim M-H, Zhu N, Wong K-W (2006) Classification of adaptive memetic algorithms: a comparative study. IEEE Trans Syst Man Cybern Part B 36(1)
Ong YS, Keane AJ (2004) Meta-Lamarckian learning in memetic algorithms. IEEE Trans Evol Comput 8(2): 99–110
Ong YS, Nair PB, Keane AJ (2003) Evolutionary optimization of computationally expensive problems via surrogate modeling. AIAA J 41(4): 687–696
Ong YS, Nair PB, Lum KY (2006) Max-Min surrogate-assisted evolutionary algorithm for robust aerodynamic design. IEEE Trans Evol Comput 10(4): 392–404
Poli R (2001) Exact schema theory for genetic programming and variable-length genetic algorithms with one-point crossover. Genet Program Evolvable Mach 2(2): 123–163
Rosca JP (1995) Genetic programming exploratory power and the discovery of functions. Conference on Evolutionary Programming. MIT Press, Cambridge
Rumelhart DE (1980) Schemata: the building blocks of cognition. Theoretical issues in reading and comprehension. B. B. R.J. Sprio & W.F. Brewer, Erlbaum
Shahaf D, Amir E (2007) Towards a theory of AI completeness. In: 8th Interational symposium on logic formalizations of commonsense reasoning
Smart W, Zhang M (2004) Applying online gradient descent search to genetic programming for object recognition. In: Second workshop on Australasian information security, data mining and web intelligence, and software internationalisation, Dunedin, New Zealand
Smith JE (2007) Coevolving memetic algorithms: a review and progress report. IEEE Trans Syst Man Cybern Part B 37(1): 6–17
Tang J, Lim MH, Ong YS (2007) Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems. Soft Comput 11(9): 873–888
Topchy A, Punsch WF (2001) Faster genetic programming based on local gradient search of numeric leaf values. Genet Evol Comput Conf
Tsai H-K, Yang J-M, Kao C-Y (2002) Solving traveling salesman problems by combining global and local search mechanisms. Conf Evol Comput
Tsai H-K, Yang J-M, Kao C-Y (2004) An evolutionary algorithm for large traveling salesman problems. IEEE Trans Syst Man Cybern Part B 34(4): 1718–1729
Ullah ASSMB, Sarker RA, Cornforth D, Lokan C (2007) An agent-based memetic algorithm (AMA) for solving constrained optimazation problems. In: IEEE congress on evolutionary computation, Singapore
Wang H, Wang D, Yang S (2009) A memetic algorithm with adaptive hill climbing strategy for dynamic optimization problems. Soft Comput
Wang L, Maciejewski AA, Seigel HJ, Roychowdhury VP (1998) A comparitive study of five parallel genetic algorithms using the traveling salesman problem. In: First merged international conference and symposium on parallel and distributed processing
Wills LM, Kolodner J (1994) Towards more creative case-based design systems. In: Proceedings of the twelfth annual national conference on artificial intelligence (AAAI-94):50–55
Woldpert DH, Macready WG (1997) No free lunch theorms for optimization. IEEE Trans Evol Comput 1(1): 67–82
Wunsch DC, Mulder S (2003) Using adaptive resonance theory and local optimization to divide and conquer large scale traveling salesman problems. Int Joint Conf Neural Netw
Xin Y (1999) Evolving artificial neural networks. Proc IEEE 87(9): 1423–1447
Xu R, Wunsch D II (2005) Survey of clustering algorithms. Neural Netw IEEE Trans 16(3): 645–678
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Meuth, R., Lim, MH., Ong, YS. et al. A proposition on memes and meta-memes in computing for higher-order learning. Memetic Comp. 1, 85–100 (2009). https://doi.org/10.1007/s12293-009-0011-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12293-009-0011-1