多背包问题求解及其在网络化制造中的应用

Solution of multiple-knapsack problem and Its application in networked manufacturing

给出了多背包问题及其数学描述;讨论了网络化制造中的最优制造伙伴选择问题,将其归结为一种复杂的多目标、多选择、多约束背包问题并提出了一种并行多目标妥协遗传算法进行求解;算法采用基于排列的编码方式,由多个种群独立进化并定期交换最佳个体,而适应度计算采用自适应权重方法及基于距离度量的妥协方法,通过基于小生境技术的适应度共享保持种族多样性,最终求得决策者可接受的妥协解。

The multiple-knapsack problem and its mathematical description are analyzed.The selection of optimum manufacturing partners in networked manufacturing is discussed.The problem is ranged to a complicated multiple-objective,multiple-choice,and multiple-constraint knapsack problem,and a compromise-based parallel multiple-objective genetic algorithm is proposed to solve it.The algorithm uses the coding method based on permutation,and it has a number of subpopulations which evolve independently and exchange the best chromosomes with each other.The adaptive weights approach and the compromised approach based on distance are used for determining the fitness of chromosomes,and fitness sharing method is also used for keeping the population diversity.Finally,the compromised solution is obtained for the decision-maker.