面向装箱问题的组合优化方法

摘要

本发明公开了一种面向装箱问题的组合优化方法。它针对工业生产中的组合优化和作业调度问题，采用了以组为对象的适合组合问题结构的编码方式，使得遗传算法可以通过染色体遗传与问题相关的信息。将染色体分为物品部分和组部分，生成不定长的染色体；运用根据组合问题特点设计的变异算子和逆序算子，经过算法的多次迭代，得到问题的近似最佳组合解。本发明针对装箱问题难以得到精确的全局最优解的特点，采用以组为对象的组合优化方法，有效地实现了装箱问题的优化设计，解决了快速装箱的设计问题，提高了设计效率。

主权项

一种面向装箱问题的组合优化方法，其特征在于包括如下步骤：1)使用组合优化方法的染色体编码方法编码装箱问题的解，将组合优化算法的染色体编码分为物品部分和组部分，对于有m个物品的装箱问题，物品分别从0到m编号，0 1 2 3 4 5…m，该装箱问题的一个染色体可以写成A D B C E B…X:A…X，表示物品0装在名字为A的箱子中，1装在D，2和5装在B，3在C，4在E，m在X，物品部分列出了该染色体使用的箱子名字；2)建立适应度函数： f BPP = Σ i = 1 N ( F i C ) k N 其中N是箱子数，Fi是箱子i中物品的大小之和，C是箱子的容量，k是一个常数，k＞1，表示对装满的箱子的重视程度，在此设定k为2；3)设定进化代数值、种群规模值、交叉概率值、变异概率值和逆序概率值；4)采用首次适应下降算法产生初始种群，其中种群规模为步骤3)中设定的值；5)根据步骤2)建立的适应度函数对种群进行评估，计算染色体的适应度值；6)使用轮盘法对种群进行选择操作，产生新种群，种群规模为步骤3)中设定的值；7)将新种群的染色体两两配对形成父染色体对，根据步骤3)中设定的交叉概率值进行两点交叉操作，使用首次适应下降算法对新染色体进行调整，对换两个父染色体的位置产生另一个新染色体，用两个新染色体替换两个父染色体；8)对新种群中的染色体进行变异操作，根据步骤3)中设定的变异概率值进行变异，形成新的染色体，替换原染色体；9)根据步骤3)中设定的逆序概率值对新种群中的染色体进行逆序操作，形成新的染色体，替换原染色体；10)重复步骤5)到步骤9)，直到进化代数值达到步骤3)中的设定值，得到最终的种群，将种群中适应度值最大的染色体解码，得到此次计算的最佳组合解；所述的步骤7)为：(a)限定交叉区域：在染色体物品部分随机选择两对交叉点，分别为两个父代染色体限定交叉区域；(b)插入交叉区域基因：把第二个父代染色体的交叉区域的基因插入到第一个父代染色体的第一个交叉点；(c)删除重复物品所在箱子，使物品旧的组合给插入的新组合让位；(d)调整产生的新染色体，用首次适应下降算法将在步骤(c)中被删除的物品重新装到箱子中；(e)对换两个父代染色体的角色，重复步骤b)到步骤d)来产生第二个后代，用两个新染色体替换两个父染色体。