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

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Feng, Liang, Ong, Yew-Soon, Tan, Ah-Hwee, Tsang, Ivor W.
Other Authors: School of Computer Science and Engineering
Format: Article
Language:English
Published: 2021
Subjects:
Online Access:https://hdl.handle.net/10356/148168
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-148168
record_format dspace
spelling sg-ntu-dr.10356-1481682021-04-19T01:01:22Z Memes as building blocks : a case study on evolutionary optimization + transfer learning for routing problems Feng, Liang Ong, Yew-Soon Tan, Ah-Hwee Tsang, Ivor W. School of Computer Science and Engineering Engineering::Computer science and engineering Memetic Computation Evolutionary Optimization of Problems 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. Agency for Science, Technology and Research (A*STAR) Nanyang Technological University Accepted version This work is partially supported under the A*StarTSRP funding, by the Singapore Institute ofManufacturing TechnologyNanyang Technological University (SIMTech-NTU) Joint Laboratory and Collaborative research Programme on Complex Systems, and the Computational Intelligence Graduate Laboratory at NTU. 2021-04-19T01:01:22Z 2021-04-19T01:01:22Z 2015 Journal Article Feng, L., Ong, Y., Tan, A. & Tsang, I. W. (2015). Memes as building blocks : a case study on evolutionary optimization + transfer learning for routing problems. Memetic Computing, 7(3), 159-180. https://dx.doi.org/10.1007/s12293-015-0166-x 1865-9284 https://hdl.handle.net/10356/148168 10.1007/s12293-015-0166-x 2-s2.0-84939414786 3 7 159 180 en Memetic Computing © 2015 Springer-Verlag Berlin Heidelberg. This is a post-peer-review, pre-copyedit version of an article published in Memetic Computing. The final authenticated version is available online at: http://dx.doi.org/10.1007/s12293-015-0166-x. application/pdf
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic Engineering::Computer science and engineering
Memetic Computation
Evolutionary Optimization of Problems
spellingShingle Engineering::Computer science and engineering
Memetic Computation
Evolutionary Optimization of Problems
Feng, Liang
Ong, Yew-Soon
Tan, Ah-Hwee
Tsang, Ivor W.
Memes as building blocks : a case study on evolutionary optimization + transfer learning for routing problems
description 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.
author2 School of Computer Science and Engineering
author_facet School of Computer Science and Engineering
Feng, Liang
Ong, Yew-Soon
Tan, Ah-Hwee
Tsang, Ivor W.
format Article
author Feng, Liang
Ong, Yew-Soon
Tan, Ah-Hwee
Tsang, Ivor W.
author_sort Feng, Liang
title Memes as building blocks : a case study on evolutionary optimization + transfer learning for routing problems
title_short Memes as building blocks : a case study on evolutionary optimization + transfer learning for routing problems
title_full Memes as building blocks : a case study on evolutionary optimization + transfer learning for routing problems
title_fullStr Memes as building blocks : a case study on evolutionary optimization + transfer learning for routing problems
title_full_unstemmed Memes as building blocks : a case study on evolutionary optimization + transfer learning for routing problems
title_sort memes as building blocks : a case study on evolutionary optimization + transfer learning for routing problems
publishDate 2021
url https://hdl.handle.net/10356/148168
_version_ 1698713742999552000