基于遗传算法的多头组合秤称重优化

丁威涛，苏宇锋

（郑州大学机械与动力工程学院，河南 郑州 450001）

1 引言

近年来，食品工业对中小定量包装的需求越来越大。传统的单头包装秤存在称重精度不高、包装速度慢、抗干扰能力差等弊病，特别是在称量形状不规则、单体重量不平均的物料如速冻水饺、汤圆时，称量的误差较大，导致产品不合格率升高。多头组合秤非常适用于称量各种不规则形状和单体重量不平均又需定量称重的物品，具有精确度高、可靠性强、抗干扰能力强等优势［1］。多头组合秤的应用不但降低企业人力成本，还明显提高产品生产效率，增加了企业的经济效益。

目前，用于多头组合秤的算法有穷举法和动态规划法。穷举法是列举出所有组合的可能性，从所有列举出的组合中选取最优解的方法。当组合秤有n个称重斗时，一共就有2n种组合的方式。穷举法要求把所有的组合方式都列举和存储起来，虽然这种方法的准确性很高，但每一次都要列举和存储所有的组合结果，这势必会造成内存资源的浪费，因此这种算法只适合小规模组合。

动态规划算法依据最优子结构和状态转移方程能很好的实现组合问题，但动态规划算法的输入只能是整数［2］，这与实际称重传感器的精度相差很大，降低了组合的精度。传统算法虽然算法原理简洁、求解方法简单，但只适合于小规模组合问题，对于复杂问题会花费大量的时间，特别在处理多目标函数问题时，往往都得不到满意的结果。

2 多头组合秤称重原理分析

多头组合秤主要包括储料槽、线振盘、进料斗、称重斗，称重传感器和集料槽等［3］，有的高档组合秤还有记忆斗，如图1所示。

图1 多头组合秤结构图Fig.1 Structure Diagram of Multi-Head Combination Weigher

储料槽中的物料在线振盘的振动作用下均匀的散落到各个进料斗中，进料斗每隔固定的时间把一定量的物料输送到称重斗中，称重斗中的称重传感器对物料进行称量，得到的物料重量经由电脑组合配重选择出最接近目标重量的称重斗组合，被选中的称重斗将物料送到集料槽中，进料斗再为空缺的称重斗补料，依次循环组合。拥有记忆斗的组合秤，称重斗会把称量好的物料先送到记忆斗中，在电脑组合配重时是记忆斗和组合斗一起参与组合，因此拥有记忆斗的组合秤里称重斗一般设置两个出口，一个出个用于为记忆斗供料，另一个出口为集料槽供料，这里不考虑带有记忆斗的组合秤。

3 多头组合秤数学模型

多头组合秤的配重问题是一个典型的组合优化问题。该问题可以简单的描述为：一个由n个称重斗组成的多头组合秤，每一个称重斗i（i=1，2，3，…，n）中都有独立的重量ωi（i=1，2，3，…，n），选中其中的m（m≤n）个称重斗式（4），组合出来的重量最接近给定的目标重量T的问题。该问题也是典型的0-1规划问题：xi表示称重斗被选中的状态：xi=0表示第i个称重斗没有被选中；xi=1表示第i个称重斗被选中，并且同一时间同一称重斗只能满足以上一种状态。

食品行业的企业为了赢得消费者的青睐，往往在包装食品的实际重量不会少于包装袋上标注的重量，与此同时企业为了获得最大的利润也不希望实际重量超出标注重量太多，因此组合秤配重问题的第一个目标函数是要求配重在大于目标重量T的前提下最小式（1）、式（3）。这里研究的包装物料是速冻水饺、速冻汤圆等不易长时间保存的食物，为了保障此类食物在配重时不会因为时间过长融化影响食物的品质，就要求物料在称重斗中的时间不能过长，也就是称重斗不能长时间不被选中，这里针对此问题引进优先级θi=A-λi+ 1（i=1，2，3，…，n）的概念，A表示总的组合次数，λi表示第i个称重斗被选中时的组合次数，优先级θi越大表示第i个称重斗未被选中的时间越长，这里要求每个称重斗的优先级都不能太大，优先级越大的称重斗越容易被选中，因此组合秤配重问题的第二个目标函数是要求选中的称重斗的优先级之和最大式（2）［4-6］。数学模型入归纳下：

式中：xi—称重斗被选中的状态；ωi—称重斗中的重量；θi—称重斗的优先级；T—目标重量；m—被选中称重斗的个数。

4 遗传算法

就传统算法所存在的问题，提出了基于遗传算法的多头组合秤程序设计，并针对种群在进化过程中出现的违反约束的个体提出了基于“重量优先”的修复方法。遗传算法是一种抽象于生物进化过程的基于自然选择和生物遗传机制的优化技术，是一种高度并行、随机性强和适应全局优化搜索的优化算法，其具有简单通用、鲁棒性强、易于并行处理以及高效、实用等显著特点［7］。基于遗传算法求解的步骤如下。

4.1 编码

遗传算法首先要对求解种群中个体进行编码处理，常用的编码方式有：二进制编码，格雷码编码，浮点数编码等。这里采用二进制编码，个体编码的长度为称重斗的数量。设种群中有t个个体，种群编码为X=｛X1，X2，X3，…，Xt｝，个体编码Xa=｛x1，x2，x3，…，xn｝（1 ≤a≤t），xi（1 ≤i≤n）表示种群中第a个个体的第i个称重斗选中状态，xi=1表示第i个称重斗被选中，xi=0表示第i个称重斗未被选中。例如种群编码Xa=｛1，0，0，1，0，0，0，1，1，0｝，表示组合秤有10个称重斗，种群中第a个个体的第1、4、8和9个称重斗被选中，其余的称重斗未被选中［8］。

4.2 选择操作

选择操作是种群根据适应度函数值进化的过程，在进化的过程中生命力强（适应度值高）的个体被选择到下一代的概率高，生命力弱（适应度值低）的个体被选择到下一代的概率低。选择操作是种群中个体进行优胜劣汰的过程，也是目标函数不断接近最优解的过程。常用的选择操作有：轮盘赌、随机竞争、最佳保留等［9］。这里采用轮盘赌选择操作，轮盘赌选择操作是一种放回式随机采样方法，这种方式下的个体进入下一代的概率就等于它的适应度值与整个种群中个体适应度值之和的比例，比例越高，被选中的可能性就越大，进入下一代的概率就越大。这里把要求解的目标函数设置为种群的适应度函数。对于有两个及两个以上目标函数的问题称为多目标函数问题。对于多目标函数的求解常用权重系数变换法、并列选择法、排列选择法等。这里采用并列选择的方式求解多目标函数，首先将完整的种群平均分为两个子种群，每个子种群随机分配一个目标函数作为该种群的适应度函数，两个子种群独立的根据适应度函数值进行选择操作，产生的新的子种群再合并为这一代的完整新种群，再将新种群进行交叉和变异操作，进而生成下一代完整的种群，如此的不断“分割—并列选择—合并”操作，最终可求出多目标化问题的Pareto最优解。

4.3 交叉和变异操作

交叉和变异操作是在遗传算法中产生新的个体的主要方式，新个体增加了种群的多样性，使算法有很好的全局搜索能力［9］。交叉操作也是遗传算法区别其他算法的重要特征。这里的交叉和变异操作方法都是随机生成法：交叉操作中要交叉个体和交叉位置都是随机确定，随机选出的两个交叉个体在交叉位置被截断，再分别和对应的个体进行交换；变异个体和变异位置也是随机确定，随机选出的变异个体的变异位置原来是0则变异为1，原来是1则变异为0。完全随机的方式可以最大化的提高遗传算法的全局搜索能力，保证遗传算法能收敛于全局最优解。

4.4 修复操作

遗传算法每次迭代的过程中，交叉操作和变异操作都会产生新的个体，这虽然增强了种群的多样性，提高了算法的全局搜索能力，但也会产生违背原问题约束条件的个体，称为不可行解［10］。对于不可行解的处理一般会采用罚函数法，通过罚函数把约束条件添加到目标函数当中，从而把有约束问题转化为无约束问题求解。罚函数直接决定了目标函数的精确程度，但是罚函数的确定比较困难，这里提出了基于“重量优先”的修复策略来处理不可行解。所谓的“重量优先”是把不可行解中选中的称重斗按重量大小递增排序，未选中的称重斗按重量大小递减排序，进行修复操作时把两个序列按序号交换直到满足约束条件。被选中称重斗的最小重量和未被选中称重斗的最大重量进行交换使不可行解能最快满足约束条件，减少运算时间。

4.5 遗传算法的具体流程

遗传算法的流程，如图2所示。其中gen表示遗传算法的迭代次数，MAXGEN表示遗传算法的最大迭代次数。

图2 遗传算法流程图Fig.2 Flow Chart of Genetic Algorithm

5 仿真

由文献［11-12］研究可知，多头组合秤下料的重量满足正态分布的规律，其中多头组合秤称重斗总数越大，每个称重斗中重量分布的标准差越小，组合合格的概率越大［12］。这里仿真选取10头的组合秤，选取其中4 个称重斗组合目标重量。这里研究的对象为速冻饺子、速冻汤圆，这些物料都由机器进行制作，每一个的重量差别不会特别大，一般每个重量在25g左右，考虑到包装袋上的重量是整数，称重传感器的测量精确到小数点后一位即可，这里仿真物料的重量由满足N～（25，2）的正态分布精度为小数点后一位的随机数替代，目标重量设置为100g，遗传算法中最大迭代次数MAXGEN=100，交叉操作的概率Ps=0.7，变异操作的概率Pm=0.2，每一代种群中个体数量设置为100个。考虑到产生随机数的随机性和不均匀性，本仿真的组合重量误差小于1g就算合格。

仿真中遗传算法组合一次的收敛情况，如图3 所示。横坐标表示种群的迭代次数，纵坐标是组合的最终组合得重量，图中：实线—种群最小值的变化；虚线—种群平均值的变化。

图3 遗传算法收敛情况图Fig.3 Convergence Graph of Genetic Algorithm

本仿真共设置4组，分别为组合100、500、1000和5000次，分别记录下每组实验的合格数、不合格数、最大优先级和总计算时间。根据合格数和不合格数可以得到组合成功率；根据最大优先级和总计算时间可以得出每组合所需时间和物料在称重斗中存放的最长时间，具体组合结果，如表1所示。

表1 组合结果Tab.1 Result of Combination

6 结论

根据仿真数据可以知道，基于遗传算法的多头组合秤称重算法收敛迅速平稳，组合合格概率大于98%，平均完成一次组合分析的时间小于0.15s，称重斗的最大优先级控制在20以内，保证了物料在称重斗中的时间不会高于10s。仿真数据表明，基于遗传算法的多头组合秤既能确保组合合格率也能保证物料的新鲜度，能很好的满足组合要求。