Memetic search with interdomain learning : a realization between CVRP and CARP

• Main Authors: Feng, Liang, Ong, Yew-Soon, Lim, Meng-Hiot, Tsang, Ivor W.
• Other Authors: School of Computer Science and Engineering
• Format: Article
• Language: English
• Published: 2021
• Subjects: Engineering::Computer science and engineering; Evolutionary Optimization; Memetic Computing
• Online Access: https://hdl.handle.net/10356/148169
• Institution: Nanyang Technological University

In recent decades, a plethora of dedicated evolutionary algorithms (EAs) have been crafted to solve domain-specific complex problems more efficiently. Many advanced EAs have relied on the incorporation of domain-specific knowledge as inductive biases that is deemed to fit the problem of interest well. As such, the embedment of domain knowledge about the underlying problem within the search algorithms is becoming an established mode of enhancing evolutionary search performance. In this paper, we present a study on evolutionary memetic computing paradigm that is capable of learning and evolving knowledge meme that traverses different but related problem domains, for greater search efficiency. Focusing on combinatorial optimization as the area of study, a realization of the proposed approach is investigated on two NP-hard problem domains (i.e., capacitated vehicle routing problem and capacitated arc routing problem). Empirical studies on well-established routing problems and their respective state-of-the-art optimization solvers are presented to study the potential benefits of leveraging knowledge memes that are learned from different but related problem domains on future evolutionary search.