Font Size: a A A

Research On Optimization Method For Complex Knapsack Problem Model Based On Genetic Algorithm

Posted on:2022-06-02Degree:MasterType:Thesis
Country:ChinaCandidate:L TaoFull Text:PDF
GTID:2518306518994649Subject:Statistical information technology
Abstract/Summary:PDF Full Text Request
The knapsack problem is a kind of classical NP-hard combinatorial optimization problem.There are many models for the knapsack problem,and most of them can be transformed into the basic 0-1 knapsack problem.Currently,the researches on the 0-1 knapsack problem mainly focused on algorithm exploration and model extension,especially the research of model extension has always been a hot topic.In this thesis,we consider the real-world application and studies the following extended model:(1)To meet the real application demands,the constraints in the 0-1 knapsack problem are divided into two kinds,including subjective constraints and objective constraints.(2)To establish a dynamic problem model,we change certain item information(i.e.,value)into uncertain item information.For the first problem,the constraints of the knapsack problems usually compose of objective factors,such as the capacity of the knapsack.However,the subjective demands of the decision-maker are also vital as a constraint.Based on this,we introduce the concept of “the subjective demands” to construct a new 0-1 knapsack problem model,which considers the subjective demands of decision-makers.Then,a hybrid greedy genetic algorithm for solving this model is proposed.In this model,we designed a greedy search operator,and it optimizes and modifies the initial population by considering both subjective demands and objective constraints.Then,a local search operator is designed to improve the selection of disturbance sites.The operator disturbs the local optimal and helps the algorithm to escape from the local optimal solution.Finally,a comparative experiment is carried out on 9 randomly generated examples with different scales and correlations.The proposed method is compared with the Simple Genetic Algorithm(SGA)and Greedy Genetic Algorithm(GGA)in the experiment.Experimental results show that,compared with the other two algorithms,the Hybrid Greedy Genetic Algorithm(HGGA)has certain advantages in the solution accuracy and algorithm robustness.To tackle the second problem,we combine the variable information and traditional 0-1knapsack problem.Thus,a new model of 0-1 knapsack problem with the uncertain value of items is proposed.Based on a common dynamic problem strategy,we designed a value prediction operator.This operator uses a normal distribution prediction model to preprocess the historical value of the item and obtains the predicted current value for the items.Then,the dynamic problem is transferred into a static problem.To account for the characteristics of the0-1 knapsack problem,we designed two search strategies.The strategies maximized the knapsack space utilization under certain conditions,by swap items inside and outside the knapsacks,increasing the total value,and maintains the overall weight.Finally,we embed the operator into the genetic algorithm.In order to verify the effectiveness of the algorithm and predictive model,the simulations are carried out for 9 typical 0-1 knapsack cases and 2 sets of prediction cases in this thesis.The results show that the designed enhanced genetic algorithm can obtain satisfactory solutions with high efficiency,and the prediction of value by the predictive model is valid and credible as well.
Keywords/Search Tags:0-1 knapsack problem, dynamic value, subjective demands, objective constraints, Genetic Algorithm, local search
PDF Full Text Request
Related items