Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/85750
DC FieldValueLanguage
dc.contributorDepartment of Industrial and Systems Engineering-
dc.creatorXue, Fan-
dc.identifier.urihttps://theses.lib.polyu.edu.hk/handle/200/7203-
dc.language.isoEnglish-
dc.titleA suboptimum- and proportion-based heuristic generation method for combinatorial optimization problems-
dc.typeThesis-
dcterms.abstractAutomated 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.-
dcterms.accessRightsopen access-
dcterms.educationLevelPh.D.-
dcterms.extentxxxvii, 233 p. : ill. ; 30 cm.-
dcterms.issued2013-
dcterms.LCSHCombinatorial optimization -- Data processing.-
dcterms.LCSHAlgorithms.-
dcterms.LCSHHong Kong Polytechnic University -- Dissertations-
Appears in Collections:Thesis
Show simple item record

Page views

4
Citations as of Jun 26, 2022

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.