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

摘要

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

主权项

1.一种面向装箱问题的组合优化方法，其特征在于包括如下步骤：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_{\mathrm{BPP}}=\frac{{\Sigma }_{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)中的设定值，得到最终的种群，将种群中适应度值最大的染色体解码，得到此次计算的最佳组合解。$