多重群体遗传算法在多选择背包问题中的应用

Multipe-choice knapsack problem using multi-group genetic

在解决多选择背包问题中,引入了多重群体遗传算法作为求解方法,根据此问题的特点,制定了具体的杂交、变异方法,设计了遗传算法。在算法中以目标函数加惩罚函数为适应值评价函数,采用新陈代谢的跨世代选择策略,以更好地保持进化过程中的遗传多样性。实践表明,引入了多重群体遗传算法之后,求解此问题效率有明显的改善与提高。

A new kind of optimization of multipe-choice knapsack problem and its sloving method by mult-group genetic algorithms were proposed. The complete method of crossover and mutation were designed according to the characteristic of the multipe-choice knapsack problem. In the algorithms, the fitness functions were divided into two parts, one is objective function and another is penalty function. In the process of selection, the strategy of metabolism which choosed the individual from multiple generations were used so as to keep the variation of the individual in the process of the evolution. The result of the simulation explains that the efficiency of the problem sloving has improved greatly after using the method of mult-group genetic algorithms.