应用改进遗传算法的自动配棉模型优化与应用

宋楚平, 李少芹

(江苏工程职业技术学院 机电工程学院, 江苏 南通 226007)

应用改进遗传算法的自动配棉模型优化与应用

宋楚平, 李少芹

(江苏工程职业技术学院 机电工程学院, 江苏 南通 226007)

针对配棉工艺具有多约束条件的特点和现有自动配棉的不足，提出将改进的遗传算法应用到线性规划优化求解问题中，通过改进遗传算法的初始种群生成策略、遗传算子和进化收敛条件，将配棉约束条件动态融合到种群进化过程中，在保证配棉约束条件的前提下，兼顾了求解的效率和有效性，以达到对自动配棉进行优化的目的。应用结果显示：用改进遗传算法对配棉模型的求解优于基本遗传算法，且配棉的各项指标值符合生产技术要求，在满足混棉质量的前提下，该方法能指导技术人员对候选棉和库存棉做出更合理的选择，有效降低了配棉成本。

自动配棉； 配棉模型； 改进遗传算法； 多约束条件

配棉是纺织企业的一项常规性技术工作，在自动配棉之前，由于原棉缺乏统一的性能指标数据，配棉工作主要采用传统的人工经验模式，配棉速度慢，成本较高，纱线质量不稳定。随着计算机、人工智能等技术的发展，以及HVI(high volume instrument，大容量棉花纤维测试仪)公检体制在我国的实施和推广，为自动配棉提供了数据基础和技术支撑。自动配棉一直是一个复杂的工作过程，由于原棉性能多样性和差异性的特点，另受每组棉花的配比、配棉品质指标、生产成本和纱线质量的多条件约束，目前纺织企业还没有完善的技术手段对配棉质量进行控制和预测，导致配棉成本和质量波动性较大，影响了企业的经济效益和生产竞争力。针对该问题，国内外学者和行业专家进行了大量的研究，如按棉台容量和混棉指标建立配棉模型[1]，用PSO(particle swarm optimization)算法对配棉目标函数进行优化[2]，用组合方案法构建配棉模型[3]等。现有的自动配棉系统主要采用线性规划法和组合方案法，当原棉种类数大于4时，组合的方案数显著增加，计算量十分庞大、耗时过长，难以对众多方案的成纱质量进行客观评价，可能会使该方法失去实用价值。线性规划实际是一种最优化问题，其决策变量、约束条件和资源参数的关系能较好地反映配棉的实际情况，通用性和适用性较强，计算精度高，但求解过程易陷入局部优先，可能无法寻到全局最优解[4]。

为解决线性规划法下自动配棉全局寻优能力不强的缺陷，本文利用遗传算法具有较强的鲁棒性和全局搜索能力[5]，在此基础上提出一种改进的遗传算法对自动配棉线性模型进行求解，以提高配棉的最优化和有效性。

1 应用HVI的配棉模型建立

1.1 HVI数据

HVI数据是采用HVI检测设备对原棉纤维成熟度、细度、棉结、单纤维强力、色泽、等级的指标数据，该数据表征了原棉的重要性能。随着我国棉花新标准的实施和HVI公检制度的推进，原棉的收购、加工、销售和使用各环节己经转向利用HVI检测，使得每个棉包都有1组HVI数据，利用公检HVI数据进行计算机配棉从根本上保证了HVI数据的权威性和一致性，为实现自动配棉奠定了数据基础。

自动配棉是根据纺纱质量要求对库存原棉进行混合，既要尽可能控制生产成本，又要满足混棉的质量指标要求的过程。无论是购棉还是配棉，都可以在HVI数据的支持下做到合理采购原料，科学设计配棉方案，并能有效预测纱线质量。

1.2 配棉模型

原料成本约占到棉纺企业整个成本的70%，因此，配棉的好坏将直接影响企业的生产效益和纱线质量，是一项经济性和技术性很强的工作。在配棉过程中，要考虑原棉的种类、原棉性能指标、纺纱的品质和工艺条件、经济指标等，研究彼此之间的关系，统筹规划，建立配棉目标模型。

目前配棉模型主要有2种函数表达方式：一种是成本最小化，另一种是混棉质量指标误差最小化。2种方式都要考虑成本与质量的统一，二者本质是一致的，因为原棉的技术品质与价格是密切相关的，界定了原棉品质，也就确定了其价格，反之亦然。本文采用配棉成本达到最小为目标函数[6]。

(1)

式中：Pi为第i种原料的价格；Xi为第i种原料在配棉中所占的比重；n为不同批次原棉的种类数。

显然，根据配棉原理，配棉后混棉的各项品质(如平均马克隆值、纤维平均长度、纤维平均强度、平均黄度、疵点总数等)必须在规定的范围内，以满足成纱质量约束，即有以下约束。

1)批棉权重约束。

(2)

式中：各批棉所占比重之和为1，maxi和mini分别为第i批棉所占比重的上限值和下限值。

通常根据已纺纱线的线密度，从实验室数据中选取第i批棉的占比参数作为Xi的上下限参考值。

2)主体成分约束。

(3)

式中：ki为主体成分因子，若i原料被选中，ki取值为1，否则为0；C为原棉主体成分要求值。

3)原棉品质指标约束。

(4)

式中：Pij为第j种棉的第i项品质指标值；Ai、Bi分别指混棉的第i项平均品质指标值的下限和上限。

2 改进遗传算法对模型的求解

尽管基本遗传算法(简称BGA)具有鲁棒性和全局搜索能力强的特点，但在求解配棉问题时，由于基本遗传算法使用随机生成的个体种群进行遗传操作，从而可能出现大量无效个体参与运算，导致寻优过程失效[7]。另外，基本遗传算法直接采用适应度的大小或迭代次数作为进化终止条件，在种群进化过程中缺乏对约束条件的监控，这意味着单纯以成本为适应度计算的进化过程会过早收敛，但又不符合求解要求。在基本遗传进化的后期，数量稀少的适应度高的个体由于概率低没被选中，而它们可能部分或全部是最优解，从而出现算法效率低或在一定时间内得不到最优解。

针对上述问题，本文利用一种改进的遗传算法(简称IGA)求解多条件约束的自动配棉问题。改进的遗传算法流程描述如下。

1)采用整数编码。企业在配棉时会根据库存原棉和生产情况，设定棉批种类数m和限定混棉总包数n、以及各批棉使用包数的上限ki(i=1,2,…,m)。虽然待求解的Xi为(0,1)间的实数，但由于实际配棉方案中各批棉的包数皆为整数，故基因编码采用整数编码，1组参数(x1、x2、…、xi)为1个染色体，xi代表每种配棉的包数，在[0,n-1]取值。采用上述编码不仅能有效满足实际整包抓棉的要求，而且能明显缩小xi的搜素空间，提高求解效率。

2)初始种群生成策略。如果没有任何条件约束，采用随机在[0,n-1]生成的k个基因构成的个体绝大部分是无效个体，这是因为它们都不能满足式(2)、(3)的约束。为此，本文采取以下策略生成初始种群。

步骤1：染色体(x1、x2、…、xi)中的xi随机在[0,n-1]取值，如果xi>ki，则舍弃，继续取，最后按式(5)对xi进行缩放。

(5)

步骤2：每生成1个个体，就放在集合X中，且计数器count+1(count初值=0)，然后回到步骤1，直至集合X的长度等于种群大小S。这样，不仅保证了个体都满足式(2)、(3)，而且在较短时间生成初始种群。

3)适应度函数。适应度是衡量个体优劣程度的值，该函数的好坏对遗传操作有重要的影响，也直接影响求解的效率。采用式(1)计算个体的适应度函数fit(y)=1/F。为消除不同量纲数据因变化幅度带来的影响，式(1)中Pi的单位采用元/kg，保留2位小数。

4)选择操作。为避免最优个体在杂交操作中被破坏，此处引入精英保留策略[8]，用上一轮的最优个体替代本轮中的最差个体，对其余个体利用赌轮选择法随机选择组成新的种群，从而在保留最优个体的同时也保证了新种群中的个体有较大的适应度和个体优势。

5)交叉操作。为扩大搜素范围，增大种群离散度，提高跳出局部优先的能力，此处采用随机单点头-头、头-尾交叉法生成新的个体。头-头、头-尾交叉的概率分别为Pc和(1-Pc)，Pc为交叉系数。

6)变异操作。显然近邻变异操作更符合各批棉在配棉中的变化情况，且每段基因的变化受式(2)的限制，参考文献[9]，按概率Pm对随机选定的某位基因gj进行如下操作。

7)收敛条件。适应度大小的变化反映了混棉价格相对标准棉价格的变化幅度，为监控种群进化收敛程度，并提高算法的效率，必须设置合适的收敛终止条件。在种群进化过程中,当部分最优个体适应度的变化小于某一确定的临界值e时，即通过式(6)来决定收敛是否终止。

(6)

式中：s为精英策略中前10%最优个体的大小；Y为最优个体的适应度；e为这些最优个体收敛的临界值，e的经验取值为[5×10-6，5×10-5]。

若最优个体群的收敛值变化很小，并符合式(4)的约束条件，停止进化，输出最优解；否则，继续迭代，直至达到最大迭代次数。

3 应用实例

根据上述配棉方法和算法思想，利用Java和MySQL在Win7平台上开发出自动配棉应用程序。实验数据来自南通某大型国营纺织企业，原棉价格、HVI主要数据如表1所示。

在配棉工艺中，根据实际生产情况和专家经验，主要考虑短绒率、断裂比强度、马克隆值、黄度和杂质等主要技术指标[10]。本次配棉的混用上限和新的品质指标要求如表2所示。

在上述约束条件下，求解目标是混棉的最低价格。利用配棉应用程序求解最低成本前，先设定本次计算的各个参数，如表3所示。

表1 原棉基本数据

表2 配棉技术要求

注：混用上限分别为1#、2#、…、6#候选棉的混合上限值。

表3 算法基本参数

为测试改进遗传算法求解的有效性，在应用程序中分别选用本文算法和标准遗传算法对目标函数F(x)进行10次最优求解后取平均值，实验结果如表4所示。表5示出最低成本配棉方案对应的混棉技术指标值。

表4 2种算法计算结果

表5 配棉方案对应的技术指标

由表4、5可以看出，采用基本遗传算法配棉的价格虽然比标准棉的价格要低，但混棉的断裂比强度、黄度达不到品质指标要求，虽短绒率要优于标准棉，但高于该项的配棉技术指标，不能满足实际配棉的需要，故有必要对其进行改进。采用本文改进的遗传算法进行配棉，不仅配棉价格比标准棉低，且短绒率、强度和杂质要优于标准棉，马克隆值和黄度的指标值与标准棉相当，各项指标值均在配棉技术要求的范围内，所以改进遗传算法给出的配棉方案合理有效，符合棉纺厂实际生产要求。根据应用结果，可得出如下结论：

1)基本遗传算法由于本身的缺陷导致配棉寻优能力差，所求解往往不符合配棉的约束条件，甚至找不到最优解；而改进算法通过算子的巧妙设计和多约束条件的处理，保证了求解的最优化和实用性。

2)只要在配棉应用程序中改变染色体的长度参数，就能自动适应不同批次种类棉的求解要求，这样有利于技术人员在配棉时对候选棉做出更多的选择。

3)想要提高改进算法的效率，可在合理范围内适当增大收敛临界值e，这时的相对最优解也能满足配棉要求，虽然可能价格不是最低，但对于企业来说，可以根据实际情况对库存批棉做出灵活的选用，来降低整个库存成本。

4 结 语

针对传统配棉手段的缺点和其他配棉模型在求解方面的不足，本文将线性规划与遗传算法相结合，通过改进种群生成策略、遗传操作和收敛条件，解决了配棉多约束条件下的寻优问题。实际应用结果显示，基于本模型开发的应用程序能为企业的纱线生产提供配棉控制和决策。本文在建模过程中只考虑了混棉的平均品质指标，没有考虑混棉与后续产品纱线的质量关系，后续的研究将把混棉质量与纱线质量一并进行综合考虑，在应用系统中能根据求解结果预测纱线的质量，来进一步提高自动配棉的适应性和精度，为实际生产提供更多的技术手段和参考价值。

FZXB

[1] 邱兆宝．配棉混包排列优化模型与效果评价[J]．棉纺织技术，2013，41(4)：218-219. QIU Zhaobao. Cotton assorting blended bale arrangement optimized model and its effect evalua-tion[J]. Cotton Textile Technology, 2013, 41(4): 218-219.

[2] 陈怀忠，何仁初，史桂丽．基于改进PSO算法的自动配棉工艺参数优化设计[J]．纺织学报，2014，35(6)：142-143． CHEN Huaizhong, HE Renchu, SHI Guili. Parameter optimization design for automatic cotton assorting based on improved PSO algorithm [J]. Journal of Textile Research, 2014, 35(6): 142-143.

[3] 丁志荣．改进的方案组合配棉方法研究[J]．纺织学报，2005，26(3)：38-39． DING Zhirong. Method research on improved schemes combination for cotton assorting[J]. Journal of Textile Research, 2005, 26(3): 38-39.

[4] 杜兆芳，刘小平，韩江洪．基于改进微分进化算法的优化配棉[J]．纺织学报，2011，32(7)：35-36． DU Zhaofang, LIU Xiaoping, HAN Jianghong. Cotton blending optimization based on improved differential evolution algorithm[J]. Journal of Textile Research, 2011, 32(7): 35-36.

[5] 宋楚平，蔡彬彬，李少芹．基于SVM的纱线生产工艺智能优化研究[J]．毛纺科技，2015，43(7)：14-15． SONG Chuping, CAI Binbin, LI Shaoqin. Intelligent optimization study of yarn production processes based on SVM[J]. Wool Textile Journal, 2015, 43(7): 14-15.

[6] 郭光振．基于HVI公检数据的配棉技术和案例分析[J]．棉纺织技术，2014，42(4)：11． GUO Guangzhen. Cotton assorting technology and case analysis based on HVI notary inspection data[J]. Cotton Textile Technology, 2014, 42(4): 11.

[7] 李成国，范秀娟．改进混合遗传算法在自动配棉上的应用[J]．纺织学报，2009，30(3)：29． LI Chengguo, FAN Xiujuan. Application of improved hybrid genetic algorithm on automatic cotton-blending[J]. Journal of Textile Research, 2009, 30(3):29.

[8] RUDOLPH G. Convergence analysis of canonical genetic algorithms[J]. IEEE Transactions on Neural Networks, 1994, 5(1): 97-98.

[9] LEITNER P, HUMMER W, DUSTAR S. Cost-based optimization of service compositions[J]. IEEE Transactions on Services Computing, 2013,6(2): 240-245.

[10] 何银官．2012棉花标准中各质量指标在配棉中的应用[J]．棉纺织技术，2014，42(11)：1-3． He Yinguan. Application of 2012 cotton standard quality index in cotton assorting [J]. Cotton Textile Technology, 2014, 42(11): 1-3.

Optimum and application of automatic cotton blending by improved genetic algorithm

SONG Chuping, LI Shaoqin

(CollegeofMechanicalandElectricalEngineering,JiangsuCollegeofEngineeringandTechnology,Nantong,Jiangsu226007,China)

Aiming at the characteristics of multi-constraints condition and the deficiency of the existing automatic cotton blending, the improved genetic algorithm is applied to linear programming optimization problem. By improving generation strategy of the initial population, genetic operators and evolutionary convergence condition, constraint conditions of cotton blending will be fused dynamically with the evolution process. The efficiency and effectiveness of the solution are considered in the premise of ensuring the constraint conditions of cotton blending so as to optimize automatic cotton blending. The experimental results show that the solution of the improved genetic algorithm is superior to that of the basic genetic algorithm and all index values of cotton blending are in line with the requirements of production technology. Under the premise of meeting the quality of mixed cotton, the method can guide technicians to make a more reasonable choice for the candidate cotton and stock cotton and the cost of cotton blending can be reduced effectively.

automatic cotton blending; cotton blending model; improved genetic algorithm; multi-constraints condition

10.13475/j.fzxb.20150801205

2015-08-07

2016-01-31

江苏省高等职业院校国内高级访问学者计划资助项目(2014FX)；江苏工程职业技术学院科研计划项目(FYKY/2014/3)

宋楚平(1972—)，男，副教授，硕士。研究方向为计算机应用、教育信息化。E-mail：ntscp@sina.com。

TP 399

A