Evolutionary Strategies For Solving Multiple-choice Multidimensional Knapsack Problems

The Knapsack Problem (KP) is a classical NP-Hard combination optimization problem in Operations Research. It is widely used in financial arrangements, project selection. The Multiple-choice Multidimensional Knapsack problem has extensive research value as a complex variant of the KP in real applications.In real-world applications, there are a lot of dynamic optimization problems. It will be dynamic constraint optimization problem if the dynamic optimization problem constrained Dynamic Multiple-choice Multidimensional Knapsack problem belongs to dynamic constraint optimization problems.Evolutionary algorithm is mimic natural biological evolution mechanism and the formation of adaptive global optimization algorithm, is widely used in solving the combinatorial optimization problem. In static environment and dynamic environment, the research on the evolutionary algorithm to solve the Multiple-choice Multidimensional Knapsack problem has great significance.This paper includes the following two aspects.(1) A novel Multi-Population Genetic Algorithm (MPGA) is proposed to solve Multiple-choice Multidimensional Knapsack Problem (MMKP). The proposed MPGA has two evolutionary populations and an archive population to balance search biases between feasible space and infeasible space. As two evolutionary populations evolve in different targets, two evolutionary populations not only evolve independently but also evolve mutually. Archive population preserves the best feasible and infeasible individual species when current algebra ceases. When evolutionary populations are discovered into a local optimal, enable archive population available in order to covering the local optimum population, so as to keep diversity. Experimental results show that the proposed MPGA is better than existing algorithms, particularly when the strength of constraints is stronger.(2) A novel Evolution Strategy is proposed to solve the Dynamic Multiple-choice Multidimensional Knapsack Problem (DMMKP). In this algorithm, two points was improved. One is the mutation operator, and another is selection operator. Firstly, a new hybrid mutation operator is proposed. According to the state of the individual that is feasible or infeasible, different class orderings are applied in the mutating process and searching to promote. At last, according to the class ordering, item is replaced in class by probabilistic. In the evolutionary process, when the individual is an infeasible solution, the groups orders related to constraints are enabled; when the individual is a feasible solution, the value related to groups orders are enabled. Secondly, a new strategy of dynamic stochastic ranking as selection operator is also proposed, if no feasible solutions of the algorithm exist , the probability of selection remains constant ,that is zero; If feasible individual exists, the selection strategy algorithm changes and the probability of selection rises gradually, and then the searching for unfeasible space is expanded step by step. In contrast of constraint processing methods of technical penalty function method and Deb standards, the experimental results demonstrate that the new Evolution Strategy is more effective in solving dynamic constraint optimization problems. The paper discusses performance of three dynamic stochastic ranking in solving dynamic knapsack problem, and further the new dynamic stochastic ranking strategy is proved to be more excellent. Finally different merits and disadvantages of some heuristic class ordering are discussed.This paper is researching about Multiple-choice Multidimensional Knapsack Problem. And two algorithms are proposed. One is a novel Multi-Population Genetic Algorithm is proposed to solve the MMKP. The other is A novel Evolution Strategy is proposed to solve the DMMKP These efforts not only have great significance to static environment's knapsack problem, and also has important guiding role to the knapsack problem of application dynamic environment.