求解装箱问题的一种混合分组遗传算法  

A Hybrid Group Genetic Algorithm to Solve the Bin-Packing Problem

作　　者：王秀清[1,2] 邱洪泽[1] 徐法升[2] 

机构地区：[1]山东大学计算机科学与技术学院,山东济南250101 [2]济南大学理学院,山东济南250022

出　　处：《济南大学学报（自然科学版）》2010年第2期172-175,共4页Journal of University of Jinan(Science and Technology)

基　　金：山东省科技攻关项目(2008GG30009008)

摘　　要：通过设计一种适应度函数,利用分组遗传算法结合BF算法和FFD算法来对此适应度函数进行优化,从而求得一个优化的装箱结果。用C++实现该算法并对装箱实例进行仿真实验与比较,结果表明:在遗传算子的交叉操作过程中采用FFD+GGA的混合分组遗传算法是一种解决装箱问题的有效方法,在大部分情况下用很短的时间都可求得最优解。A fitness function is designed and optimized using group genetic algorithm combining with the BF algorithm and FFD algorithm so that an available bin-packing result is obtained.By experimenting and comparing based on the algorithm realized by C＋＋,it shows that using FFD＋GGA hybrid group genetic algorithm in the process of crossing genetic operator is an available method to solve the bin-packing problem,and in most cases,its optimal solution can be obtained in the shortest time.

关 键 词：装箱问题 近似算法 最佳适应算法 降序首次适应算法 分组遗传算法 

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