Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/6371
Title: A suboptimum- and proportion-based heuristic generation method for combinatorial optimization problems
Authors: Xue, Fan
Keywords: Combinatorial optimization -- Data processing.
Algorithms.
Hong Kong Polytechnic University -- Dissertations
Issue Date: 2013
Publisher: The Hong Kong Polytechnic University
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.
Description: xxxvii, 233 p. : ill. ; 30 cm.
PolyU Library Call No.: [THS] LG51 .H577P ISE 2013 Xue
URI: http://hdl.handle.net/10397/6371
Rights: All rights reserved.
Appears in Collections:Thesis

Files in This Item:
File Description SizeFormat 
b26526566_link.htmFor PolyU Users203 BHTMLView/Open
b26526566_ir.pdfFor All Users (Non-printable)2.51 MBAdobe PDFView/Open
Show full item record

Page view(s)

260
Last Week
2
Last month
Checked on May 28, 2017

Download(s)

229
Checked on May 28, 2017

Google ScholarTM

Check



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