A suboptimum- and proportion-based heuristic generation method for combinatorial optimization problems

Abstract

Automated heuristic selection and heuristic generation have increasingly attracted attention in solving combinatorial optimization problems emerging from both theory and practice. This thesis presents a heuristic generation algorithm, called Suboptimum-and Proportion-based On-the-fly Training (SPOT), which can enhance existing heuristics with the aid of instance-specific information. By making use of the proposed "sample-learn-generate" framework, SPOT samples small-scale subproblems, initially. Then, it collects the instance-specific information from the suboptima of the subproblems by the means of machine learning. Lastly, it generates new heuristics by modifying existing heuristics and data structures. In the development of SPOT, two standards were incorporated to regulate the problem input and the machine learning data. The software implementation was done in Java, with two external development libraries, the HyFlex and the Weka. In terms of testing, two well-known NP-Complete combinatorial optimization problem domains were employed: the Traveling Salesman Problem (TSP) and the permutation Flow-Shop scheduling Problem (FSP). Each generated heuristic was tested with the TSP and the FSP domains. To verify the result of using SPOT, one of the winners of the international hyper-heuristic competition CHeSC 2011, named PHunter, was tested with the generated heuristics by SPOT. In the TSP, adapting SPOT gave little betterment, but in FSP, the improvements were significant. It increased the overall score of the PHunter from 20.5 to 43 (out of 50). Indeed, it also outperformed the best records in CHeSC 2011: 32 by AdaptHH, 29.5 by ML and 26 by VNS-TW.