A software framework for fast prototyping of meta-heuristics hybridization

• Main Authors: LAU, Hoong Chuin, Wan, W. C., Halim, S., Toh, K. Y.
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2007
• Subjects: Business; Computer Sciences; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/1290; http://dx.doi.org/10.1111/j.1475-3995.2007.00578.x
• Institution: Singapore Management University

Hybrids of meta-heuristics have been shown to be more effective and adaptable than their parents in solving combinatorial optimization problems. However, hybridized schemes are also more tedious to implement due to their increased complexity. We address this problem by proposing the meta-heuristics development framework (MDF). In addition to being a framework that promotes software reuse to reduce developmental effort, the key strength of MDF lies in its ability to model meta-heuristics using a “request, sense and response” schema, which decomposes algorithms into a set of well-defined modules that can be flexibly assembled through a centralized controller. Under this scheme, hybrid schemes become an event-based search that can adaptively trigger a desired parent's behavior in response to search events. MDF can hence be used to design and implement a wide spectrum of hybrids with varying degrees of collaboration, thereby offering algorithm designers quick turnaround in designing and testing their meta-heuristics. Such technicality is illustrated in the paper through the construction of hybrid schemes using ant colony optimization and tabu search.