Memes as building blocks: a case study on evolutionary optimization + transfer learning for routing problems

• Main Authors: FENG, Liang, ONG, Yew-Soon, TAN, Ah-hwee, TSANG, Ivor W.
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2015
• Subjects: Memetic computation; Evolutionary optimization of problems; Learning from past experiences; Culture-inspired; Evolutionary learning; Transfer learning; Databases and Information Systems; Programming Languages and Compilers; Software Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/5201; https://ink.library.smu.edu.sg/context/sis_research/article/6204/viewcontent/Feng2015_Article_MemesAsBuildingBlocksACaseStud.pdf
• Institution: Singapore Management University

A significantly under-explored area of evolutionary optimization in the literature is the study of optimization methodologies that can evolve along with the problems solved. Particularly, present evolutionary optimization approaches generally start their search from scratch or the ground-zero state of knowledge, independent of how similar the given new problem of interest is to those optimized previously. There has thus been the apparent lack of automated knowledge transfers and reuse across problems. Taking this cue, this paper presents a Memetic Computational Paradigm based on Evolutionary Optimization + Transfer Learning for search, one that models how human solves problems, and embarks on a study towards intelligent evolutionary optimization of problems through the transfers of structured knowledge in the form of memes as building blocks learned from previous problem-solving experiences, to enhance future evolutionary searches. The proposed approach is composed of four culture-inspired operators, namely, Learning, Selection, Variation and Imitation. The role of the learning operator is to mine for latent knowledge buried in past experiences of problem-solving. The learning task is modelled as a mapping between past problem instances solved and the respective optimized solution by maximizing their statistical dependence. The selection operator serves to identify the high quality knowledge that shall replicate and transmit to future search, while the variation operator injects new innovations into the learned knowledge. The imitation operator, on the other hand, models the assimilation of innovated knowledge into the search. Studies on two separate established NP-hard problem domains and a realistic package collection/deliver problem are conducted to assess and validate the benefits of the proposed new memetic computation paradigm.