Meta-memes for combinatorial optimization

• Main Author: Song, Liqin
• Other Authors: Lim Meng Hiot
• Format: Theses and Dissertations
• Language: English
• Published: 2012
• Subjects: DRNTU::Engineering::Electrical and electronic engineering::Computer hardware, software and systems
• Online Access: https://hdl.handle.net/10356/49050
• Institution: Nanyang Technological University

This research aims at establishing a framework for managing and coordinating optimization methods within a search algorithm. Each optimization method is viewed as a meme. The meme is therefore an algorithmic abstraction that dictates how solution search is carried out. At a higher level, the configuration of the entire search algorithm is dictated by a meta-meme. In this case, a meta-meme can be perceived as being a recipe that provides specifications on how the strategies or memes are coordinated during a search. This work uses a neural metaphor to capture the essence of meta-memes. Through a framework known as neural meta-memes framework (NMMF), the coordination of memes during a search can be established based on the instances of earlier problem-solving sessions. Specifically, smaller or simple instances of problems to be solved are used as the basis to train the neural network using back-propagation update rule. The trained neural network capturing the experience acquired through earlier problem-solving sessions provides linkages between problems and memes, significantly enhances the search capability when dealing with complex or large-scale problems. Additionally, a method is further established with which memes in the form of patterns or solution fragments can serve as a basis for generating potentially good quality initial solutions to enhance the efficiency of a meta-meme during a search. The entire scheme was validated on the quadratic assignment problems, arguably one of the hardest among all the combinatorial optimization problems. Experimental results achieved are highly competitive, the technique outperforming that of well-known published results. Although the efficacy of the scheme on combinatorial optimization problems has been shown, in principle the meta-meme approach can also be applied to continuous optimization. It is also worth noting that besides the neural meta-memes studied in this research, other well-established meta-memes manifestations such as fuzzy rules, graphs, heuristic rules, etc., are also potentially applicable.