A study on probabilistic memetic algorithm and meme-centric framework

• Main Author: Liang, Feng
• Other Authors: Ong Yew Soon
• Format: Theses and Dissertations
• Language: English
• Published: 2014
• Subjects: DRNTU::Engineering::Computer science and engineering
• Online Access: http://hdl.handle.net/10356/61950
• Institution: Nanyang Technological University

As with genes in genetics, a meme is synonymous to memetics as being the building block of cultural evolution that is transmissible and replicable. While genes form the “instructions for building proteins”, memes are ”instructions for carrying out behavior, stored in brains (or other objects)” and passed on by means such as imitation. The term meme which can be traced back to Dawkins in his book “The Selfish Gene”, has inspired the new science of memetics that today represents the mind universe analog to genetics in cultural evolution, stretching across the fields of anthropology, biology, cognition, psychology, sociology and socio-biology. In computer science and engineering, the meme-inspired computing methodology or more concisely memetic computation has become an increasing focus of research in recent years. Memetic computation is a paradigm that uses the notion of meme(s) as units of information encoded in computational representations for the purpose of problem solving. It covers a plethora of potential meme-inspired computing methodologies, frameworks and operational algorithms. In the last decades, a meme has been typically perceived as a form of individual learning procedure or local search operator to enhance the capability of population based search algorithm. This integration has been established as an extension of the canonical evolutionary algorithm, by the names of hybrid, adaptive hybrid or Memetic Algorithm (MA). However, falling back on the basic definition of a meme (i.e., as the fundamental building blocks of culture evolution), research on memetic computation can perhaps be more meme-centric focus by treating memes as the building blocks of a given problem domain, much like gene serving as the building blocks of life. This thesis summarizes the ongoing investigations on the study of advances in memetic computation. In particular, as majority of the MAs are designed based on heuristics that comes with little theoretical rigor, we first present a formal Probabilistic Memetic Algorithm or PMA in short for combinatorial optimization problem. This algorithm can adaptively balance the exploration and exploitation of the evolutionary search by a theoretical upper bound of local search while the search progresses online. Subsequently, by treating memes as the building block for problem solving, we embark on a study towards a new Memetic Computation Paradigm: Evolutionary Optimization + Transfer Learning for search. This paradigm models how human solves problems. In contrast to conventional evolutionary search, the proposed approach takes advantage of the possible relations among problem instances of the same domain, i.e., topological properties, data distribution or otherwise. This allows the effective assessments of future unseen problem instances, without the need to perform an exhaustive search each time or start the evolutionary search from a ground-zero knowledge state. On this basis, further study on evolutionary paradigm which is capable of learning and evolving knowledge meme that traverses different but related problem domains is presented.