A study on memetic computation, with applications to capacitated vehicle routing problems

Abstract

Memetic computation, a paradigm that uses the notion of meme(s) as units of information encoded in computational representations for the purpose of problem-solving, represents one of the frontiers in the computational intelligence research, of today's optimization research. This dissertation takes an explorative attitude in the design of memetic computing frameworks and algorithms by leveraging the co-adaptive nature of meme complexes or memeplexes. The current research presented in this dissertation takes multi-memes and memeplexes as focal point of interest in the context of memetic computation and develop meme-centric computing frameworks for more effective problem-solving in the context of stochastic optimization of Capacitated Vehicle Routing Problems (CVRP) and Vehicle Routing Problem with Stochastic Demands (VRPSD). The presented research works follow a natural progression from multi-memes to memeplexes in simple and adaptive hybrids. Firstly, a simple hybrid with a multi-memes individual learning was developed to overcome the inherent risk associated with reliance on a single meme to be used for individual learning in memetic computation for solving CVRP. The proposed simple hybrid invests local search time budget among multiple memes with different search biases during individual learning, in order to reduce risks of failing on problems from different classes as well as make finding high quality solutions more likely. On this basis, an adaptive hybrid with the conceptual modeling of memeplexes was explored as a self-configuring methodology capable of learning and adapting multi-memes individual learning to the given problem of interests while the search progresses online. The connection topology network of the memeplex representation, credit assignment criteria for evaluating individual memes and meme co-adaptation, as well as the role of emergent memeplexes in the individual learning process were explored, with its application for solving CVRPs of diverse characteristics. Finally, a memeplex robust solution scheme which seeks to achieve greater level of adaptivity in problems with uncertainty was proposed and studied for VRPSD. Via robust solution search scheme, memeplex individual learning and gene-meme coevolutionary model, the scheme was demonstrated to be highly efficient and effective problem solver in environments with uncertainty such as VRPSD.