一种多维背包问题的n进制编码遗传求解算法

针对传统二进制编码求解多维背包优化问题时算法复杂度高和容易早熟收敛等问题,提出了一种解决多维背包问题的n（n〉2）进制编码遗传算法。该算法采用n进制编码初始化种群,使用变异和交叉算子进化种群,通过修正算子修正不可行解,以保证解满足约束条件,然后利用非劣解集更新算法优化最优前端,使其扩大覆盖率,保证均匀性。20次随机试验结果表明,该算法可有效克服早熟收敛,能够保持种群多样性和求解精度,具有解决复杂多维背包问题的能力。

A Genetic Algorithm with Arbitrary Encoding for Multi-Dimensional Knapsack Problems

According to the problems(high diversity and premature convergence) of traditional binary code genetic algorithm when it was used to solve multi-dimensional knapsack optimization problems,a genetic algorithm with arbitrary encoding for multi-dimensional knapsack problems was proposed.The algorithm initializes population with arbitrary encoding,evolves population with mutation operator and crossover operator,and corrects infeasible solution with modified operator in order to make the solution satisfy the constrained condition,and then optimizes the optimization front end with pareto optimal set updating algorithm in order to enlarge its coverage and guarantee its homogeneity.The results of 20 times of random experiments showed that the algorithm could effectively overcome premature convergence and keep the population diversity and solving precision,which indicated that the algorithm had the ability of solving multi-dimensional knapsack problems.