多重群体遗传算法在装箱问题中的应用研究  

Application Study of Multi-Group Genetic Algorithms in Bin-Packing Problem

作　　者：李荣[1] 

机构地区：[1]忻州师范学院计算机系,山西忻州034000

出　　处：《计算机技术与发展》2007年第9期247-249,F0003,共4页Computer Technology and Development

基　　金：山西省忻州师范学院科研基金资助项目(200623)

摘　　要：装箱问题是一个有很强应用背景的组合优化问题,求解极为困难。为有效解决该问题,提出了多重群体遗传算法,给出了具体的遗传算法步骤。在算法中采用新陈代谢的选择策略,以更好地保持进化过程中的遗传多样性。实践表明,引入多重群体遗传算法后,装箱效率有明显的改善和提高。Bin- packing problem is a combinatorial optimization problem having very strong application background and its solution is extremely difficult. In order to solve bin - packing problem efficiently, multi - group genetic algorithm is proposed and the complete algorithm procedures are described. In the algorithm, the selection strategy of metabolism which chooses the individual from multiple genera- tion is used so as to keep the variation of the individual in the process of the evolution. The result of simulation indicates that the efficiency of the packing has improved greatly after using the method of multi- group genetic algorithms.

关 键 词：多重群体遗传算法 装箱问题 NP-完备 种群 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] O221.7[自动化与计算机技术—计算机科学与技术]