| Many practical optimization problems can be transformed into knapsack problem.With the development of society and the complexity of real systems,this classical OR problems often have some special properties,such as dynamics,multi-dimension and multi-constraint.In recent years,the study of complex knapsack problems have attracted a lot of interest from scholars,dynamic knapsack problems,multi-dimensional knapsack problems and other new knapsack problems.It is becoming a popular research topic.However,it is noteworthy that solving the complex knapsack problems is a great challenge due to a variety of new features,the existing research work only consider a complex feature,very few research work considers a variety of complex features at the same time.Obviously,a variety of complex features of the knapsack problems will undoubtedly reflect the complexity of the real system better with better research value.Based on the theory of systems engineering and control engineering,this paper applies the theories and methods of operations research,computational science and applied mathematics to study the mathematical description and algorithm design of a dynamic constrained knapsack problem.An effective algorithm for solving dynamic constraint knapsack problem is proposed.The main research work of this paper includes the following three aspects:(1)Based on the research of multi-dimensional knapsack problems and dynamic knapsack problems,a new dynamic constrained knapsack problem is proposed.(2)By using the basic idea of primal-dual genetic algorithm,an improved primal-dual genetic algorithm is designed to solve the dynamic constraint knapsack problem.(3)A series of randomly generated experimental examples are used to test the effectiveness of the proposed algorithm on the dynamic constraint knapsack problem.It can be found that the improved primal-dual genetic algorithm can solve the dynamic constraint knapsack problem,especially in the environment with large change frequency and intensity. |
PDF Full Text Request