A comparative study of metaheuristic algorithms for the fertilizer optimization problem
| dc.contributor.advisor | Horsch, Michael C. | en_US |
| dc.contributor.committeeMember | Spiteri, Raymond J. | en_US |
| dc.contributor.committeeMember | Osgood, Nathaniel | en_US |
| dc.creator | Dai, Chen | en_US |
| dc.date.accessioned | 2006-08-30T15:22:21Z | en_US |
| dc.date.accessioned | 2013-01-04T04:55:52Z | |
| dc.date.available | 2006-08-31T08:00:00Z | en_US |
| dc.date.available | 2013-01-04T04:55:52Z | |
| dc.date.created | 2006-08 | en_US |
| dc.date.issued | 2006-08-23 | en_US |
| dc.date.submitted | August 2006 | en_US |
| dc.description.abstract | Hard 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.identifier.uri | http://hdl.handle.net/10388/etd-08302006-152221 | en_US |
| dc.language.iso | en_US | en_US |
| dc.subject | combinatorial optimization | en_US |
| dc.subject | metaheuristic algorithm | en_US |
| dc.title | A comparative study of metaheuristic algorithms for the fertilizer optimization problem | en_US |
| dc.type.genre | Thesis | en_US |
| dc.type.material | text | en_US |
| thesis.degree.department | Computer Science | en_US |
| thesis.degree.discipline | Computer Science | en_US |
| thesis.degree.grantor | University of Saskatchewan | en_US |
| thesis.degree.level | Masters | en_US |
| thesis.degree.name | Master of Science (M.Sc.) | en_US |