An evolutionary search paradigm that learns with past experiences

• Main Authors: FENG, Liang, ONG, Yew-Soon, TSANG, Ivor, TAN, Ah-hwee
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2012
• Subjects: Databases and Information Systems; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/6697; https://ink.library.smu.edu.sg/context/sis_research/article/7700/viewcontent/Evolutionary_Search_CEC_2012__1_.pdf
• Institution: Singapore Management University

A major drawback of evolutionary optimization approaches in the literature is the apparent lack of automated knowledge transfers and reuse across problems. Particularly, evolutionary optimization methods generally start a search from scratch or ground zero state, independent of how similar the given new problem of interest is to those optimized previously. In this paper, we present a study on the transfer of knowledge in the form of useful structured knowledge or latent patterns that are captured from previous experiences of problem-solving to enhance future evolutionary search. The essential contributions of our present study include the meme learning and meme selection processes. In contrast to existing methods, which directly store and reuse specific problem solutions or problem sub-components, the proposed approach models the structured knowledge of the strategy behind solving problems belonging to similar domain, i.e., via learning the mapping from problem to its corresponding solution, which is encoded in the form of identified knowledge representation. In this manner, knowledge transfer can be conducted across problems, from differing problem size, structure to representation, etc. A demonstrating case study on the capacitated arc routing problem (CARP) is presented. Experiments on benchmark instances of CARP verified the effectiveness of the proposed new paradigm.