Publication Date

2010

Document Type

Thesis

Committee Members

Yan Liu (Committee Member), Pratik Parikh (Committee Member), Xinhui Zhang (Advisor)

Degree Name

Master of Science in Engineering (MSEgr)

Abstract

In this study, an improved genetic algorithm (GA) is presented to solve the multidimensional 0-1 knapsack problem (MKP). The MKP is a well-known combinatorial optimization problem and has received wide attention from the operations research community for decades. Although recent advances in computing and optimization technologies have made the solution of small and medium size instances possible, this NP-hard problem, in general, still remains one of the challenging problems yet to be solved.

Of the various algorithms developed to solve the MKP, GA seems to be one of the best methods pointed out in the literature. A GA is an iterative search procedure that simulates the evolution process of a population of individuals based on natural selection and genetics. A GA typically starts with a random initial population and uses genetic operators such as crossover and mutation to yield new offspring to replace individuals of current population. GAs, though have been successful in solving MKPs, could be slow in converging to an optimal or near optimal solution.

An improved GA is proposed in this study that aims at exploring the use of greedy heuristics and methods to generate multiple diverse solutions to speed GA convergence. Path re-linking (PR), a method to generate new solutions by exploring trajectories that connect high quality solutions, is used to combine elite solutions to further improve the quality of solutions. The combination of uniform crossover and PR allows the integration of randomization and elite solutions analysis to achieve a balance of intensification and diversification to further improve the quality of solutions.

Computational studies of benchmark problems suggest that the proposed algorithm was able to quickly achieve good solutions while avoiding being trapped in premature convergence and is on par with some of the state-of-the-art algorithms in the literature. This study demonstrates a systematic method to explore heuristics to generate population generation with diversity, which could significantly influence the convergence of a GA to best solutions. Nevertheless, as our computational results suggest, randomization in crossover is critical for a GA in its overall performance to achieve better quality solutions.

Page Count

82

Department or Program

Department of Biomedical, Industrial & Human Factors Engineering

Year Degree Awarded

2010

Download


Share

COinS