Show simple item record

dc.contributor.advisorHorsch, Michael C.en_US
dc.creatorDai, Chenen_US
dc.date.accessioned2006-08-30T15:22:21Zen_US
dc.date.accessioned2013-01-04T04:55:52Z
dc.date.available2006-08-31T08:00:00Zen_US
dc.date.available2013-01-04T04:55:52Z
dc.date.created2006-08en_US
dc.date.issued2006-08-23en_US
dc.date.submittedAugust 2006en_US
dc.identifier.urihttp://hdl.handle.net/10388/etd-08302006-152221en_US
dc.description.abstractHard combinatorial optimization (CO) problems pose challenges to traditional algorithmic solutions. The search space usually contains a large number of local optimal points and the computational cost to reach a global optimum may be too high for practical use. In this work, we conduct a comparative study of several state-of-the-art metaheuristic algorithms for hard CO problems solving. Our study is motivated by an industrial application called the Fertilizer Blends Optimization. We focus our study on a number of local search metaheuristics and analyze their performance in terms of both runtime efficiency and solution quality. We show that local search granularity (move step size) and the downhill move probability are two major factors that affect algorithm performance, and we demonstrate how experimental tuning work can be applied to obtain good performance of the algorithms. Our empirical result suggests that the well-known Simulated Annealing (SA) algorithm showed the best performance on the fertilizer problem. The simple Iterated Improvement Algorithm (IIA) also performed surprisingly well by combining strict uphill move and random neighborhood selection. A novel approach, called Delivery Network Model (DNM) algorithm, was also shown to be competitive, but it has the disadvantage of being very sensitive to local search granularity. The constructive local search method (GRASP), which combines heuristic space sampling and local search, outperformed IIA without a construction phase; however, the improvement in performance is limited and generally speaking, local search performance is not sensitive to initial search positions in our studied fertilizer problem.en_US
dc.language.isoen_USen_US
dc.subjectcombinatorial optimizationen_US
dc.subjectmetaheuristic algorithmen_US
dc.titleA comparative study of metaheuristic algorithms for the fertilizer optimization problemen_US
thesis.degree.departmentComputer Scienceen_US
thesis.degree.disciplineComputer Scienceen_US
thesis.degree.grantorUniversity of Saskatchewanen_US
thesis.degree.levelMastersen_US
thesis.degree.nameMaster of Science (M.Sc.)en_US
dc.type.materialtexten_US
dc.type.genreThesisen_US
dc.contributor.committeeMemberSpiteri, Raymond J.en_US
dc.contributor.committeeMemberOsgood, Nathanielen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record