基于改进遗传算法的棉花异性纤维目标特征选择

２０１０年４月农业机械学报第４１卷第４期ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００１２９８．２０１０．０４．０３５基于改进遗传算法的棉花异性纤维目标特征选择杨文柱１，２　李道亮２　魏新华３　康玉国４　李付堂４（１．河北大学数学与计算机学院，保定０７１００２；２．中国农业大学信息与电气工程学院，北京１０００８３；３．江苏大学现代农业装备与技术省部共建教育部重点实验室，镇江２１２０１３；４．北京中棉机械成套设备有限公司，北京１０００８９）　　【摘要】　为提高基于机器视觉的棉花异性纤维在线分类的精度和速度，提出了一种基于改进遗传算法的特征选择方法。采用分段式染色体管理方案实现对多质特征空间局部化管理；利用分段交叉和变异算子避免出现无效染色体，提高搜索效率；通过自适应调整交叉和变异概率实现强搜索能力和快收敛速度的动态平衡。实验结果表明，该方法比基本遗传算法搜索能力更强、收敛速度更快，所得最优特征子集较小，更适用于棉花异性纤维在线分类。关键词：棉花　异性纤维　特征选择　改进遗传算法中图分类号：ＴＰ３９１．４１文献标识码：Ａ文章编号：１０００１２９８（２０１０）０４０１７３０６收稿日期：２００９０６１５　修回日期：２００９０６２６国家自然科学基金资助项目（３０９７１６９３）和“十一五”国家科技支撑计划资助项目（２００６ＢＡＤ１１Ａ１４１）作者简介：杨文柱，副教授，中国农业大学博士生，主要从事机器视觉和数据库研究，Ｅｍａｉｌ：[e-mail]通讯作者：李道亮，教授，博士生导师，主要从事智能系统研究，Ｅｍａｉｌ：[e-mail]ｔｏｎＦｏｒｅｉｇｎＦｉｂｅｒＯｂｊｅｃｔｓＢａｓｅｄｏｎＩｍｐｒｏｖｅｄＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍＹａｎｇＷｅｎｚｈｕ１，２　ＬｉＤａｏｌｉａｎｇ２　ＷｅｉＸｉｎｈｕａ３　ＫａｎｇＹｕｇｕｏ４　ＬｉＦｕｔａｎｇ４（１．ＣｏｌｌｅｇｅｏｆＭａｔｈｅｍａｔｉｃｓ＆ＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＨｅｂｅｉＵｎｉｖｅｒｓｉｔｙ，Ｂａｏｄｉｎｇ０７１００２，Ｃｈｉｎａ２．ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎａｎｄＥｌｅｃｔｒｉｃａｌＥｎｇｉｎｅｅｒｉｎｇ，ＣｈｉｎａＡｇｒｉｃｕｌｔｕｒａｌＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ１０００８３，Ｃｈｉｎａ３．ＫｅｙＬａｂｏｒａｔｏｒｙｏｆＭｏｄｅｒｎＡｇｒｉｃｕｌｔｕｒａｌＥｑｕｉｐｍｅｎｔａｎｄＴｅｃｈｎｏｌｏｇｙ，ＭｉｎｉｓｔｒｙｏｆＥｄｕｃａｔｉｏｎ＆ＪｉａｎｇｓｕＰｒｏｖｉｎｃｅ，ＪｉａｎｇｓｕＵｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｊｉａｎｇ２１２０１３，Ｃｈｉｎａ４．ＣｈｉｎａＣｏｔｔｏｎＭａｃｈｉｎｅｒｙ＆ＥｑｕｉｐｍｅｎｔＣｏ．，Ｌｔｄ．，Ｂｅｉｊｉｎｇ１０００８９，Ｃｈｉｎａ）ＡｂｓｔｒａｃｔＡｎｏｐｔｉｍａｌｆｅａｔｕｒｅｓｕｂｓｅｔｓｅｌｅｃｔｉｏｎｍｅｔｈｏｄｂａｓｅｄｏｎｉｍｐｒｏｖｅｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ（ＩＧＡ）ｗａｓｐｒｅｓｅｎｔｅｄ．ＡｎｏｖｅｌｓｃｈｅｍｅｎａｍｅｄｓｅｇｍｅｎｔｅｄｃｈｒｏｍｏｓｏｍｅｍａｎａｇｅｍｅｎｔｗａｓａｄｏｐｔｅｄｉｎＩＧＡ．Ｔｈｉｓｓｃｈｅｍｅｅｎｃｏｄｅｓｔｈｅｃｈｒｏｍｏｓｏｍｅｉｎｂｉｎａｒｙａｓａｗｈｏｌｅｗｈｉｌｅｓｅｐａｒａｔｅｓｉｔｌｏｇｉｃａｌｌｙｉｎｔｏｔｈｒｅｅｓｅｇｍｅｎｔｓｆｏｒｌｏｃａｌｍａｎａｇｅｍｅｎｔ．ＴｈｅｓｅｔｈｒｅｅｓｅｇｍｅｎｔｓａｒｅｓｅｇｍｅｎｔＣｆｏｒｃｏｌｏｒｆｅａｔｕｒｅ，ｓｅｇｍｅｎｔＳｆｏｒｓｈａｐｅｆｅａｔｕｒｅａｎｄｓｅｇｍｅｎｔＴｆｏｒｔｅｘｔｕｒｅｆｅａｔｕｒｅｓｅｐａｒａｔｅｌｙ．Ａｓｅｇｍｅｎｔｅｄｃｒｏｓｓｏｖｅｒｏｐｅｒａｔｏｒａｎｄａｓｅｇｍｅｎｔｅｄｍｕｔａｔｉｏｎｏｐｅｒａｔｏｒａｒｅｄｅｓｉｇｎｅｄｔｏｏｐｅｒａｔｅｏｎｔｈｅｓｅｓｅｇｍｅｎｔｓｔｏｇｅｎｅｒａｔｅｎｅｗｃｈｒｏｍｏｓｏｍｅｓ．Ｔｈｅｓｅｔｗｏｏｐｅｒａｔｏｒｓａｖｏｉｄｉｎｖａｌｉｄｃｈｒｏｍｏｓｏｍｅｓ，ｔｈｕｓｉｍｐｒｏｖｅｔｈｅｓｅａｒｃｈｅｆｆｉｃｉｅｎｃｙｅｘｔｒｅｍｅｌｙ．Ｔｈｅｐｒｏｂａｂｉｌｉｔｉｅｓｏｆｃｒｏｓｓｏｖｅｒａｎｄｍｕｔａｔｉｏｎａｒｅａｄｊｕｓｔｅｄａｕｔｏｍａｔｉｃａｌｌｙａｃｃｏｒｄｉｎｇｔｏｔｈｅｇｅｎｅｒａｔｉｏｎｎｕｍｂｅｒａｎｄｔｈｅｆｉｔｎｅｓｓｖａｌｕｅ．Ｂｙｔｈｉｓｗａｙ，ｔｈｅＩＧＡｃｏｕｌｄｏｂｔａｉｎｓｔｒｏｎｇｓｅａｒｃｈａｂｉｌｉｔｙａｔｔｈｅｂｅｇｉｎｎｉｎｇｏｆｔｈｅｅｖｏｌｕｔｉｏｎａｎｄａｃｈｉｅｖｅａｃｃｅｌｅｒａｔｅｄｃｏｎｖｅｒｇｅｎｃｅａｌｏｎｇｅｖｏｌｕｔｉｏｎ．ＴｈｅｅｘｐｅｒｉｍｅｎｔｒｅｓｕｌｔｓｉｎｄｉｃａｔｅｔｈａｔＩＧＡｈａｓｓｔｒｏｎｇｅｒｓｅａｒｃｈａｂｉｌｉｔｙａｎｄｆａｓｔｅｒｃｏｎｖｅｒｇｅｎｃｅｓｐｅｅｄｔｈａｎｔｈｅｓｉｍｐｌｅｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ（ＳＧＡ）．ＴｈｅｏｐｔｉｍａｌｆｅａｔｕｒｅｓｕｂｓｅｔｔｈａｔｔｈｅＩＧＡｏｂｔａｉｎｅｄｈａｓｍｕｃｈｓｍａｌｌｅｒｓｉｚｅｔｈａｎｔｈａｔｏｆｔｈｅＳＧＡｄｉｄ，ｓｏｉｔｉｓｍｏｒｅｓｕｉｔａｂｌｅｆｏｒｔｈｅｏｎｌｉｎｅｃｌａｓｓｉｆｉｃａｔｉｏｎｏｆｆｏｒｅｉｇｎｆｉｂｅｒｓ．Ｋｅｙｗｏｒｄｓ　Ｃｏｔｔｏｎ，Ｆｏｒｅｉｇｎｆｉｂｅｒ，Ｆｅａｔｕｒｅｓｅｌｅｃｔｉｏｎ，Ｉｍｐｒｏｖｅｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ　　引言棉花中的异性纤维含量虽少，但对棉纺织品的质量影响严重。解决异性纤维问题主要有异性纤维剔除［１］和异性纤维防范［２］２种途径。通过自动视觉检测技术在籽棉收购或交易环节快速准确地分析籽棉中的异性纤维含量，据此给销售的籽棉分等定级，并按等级定价，可以促使棉花销售者自觉防范异性纤维混入［３～５］。异性纤维分类是异性纤维含量计量的基础和关键，而从原始特征集合中选择出分类能力最强的最小特征子集则是异性纤维在线分类的前提和保障。特征选择是指从一组原始特征中挑选出最有效的特征子集，以达到降低特征空间维数、简化分类器设计、提高分类速度的目的。特征选择主要涉及２个关键技术：搜索策略和评价函数［６］。搜索策略主要有穷举搜索、顺序搜索和随机搜索３种。理论上只有穷举搜索可以保证所得结果是最优的，但对高维特征空间，由于计算量巨大而无法完成。当评价函数具有单调性时，某些非穷举搜索，如分支定界等，也可以获得最优解；但在很多情况下，评价函数并不具有单调性［７］。遗传算法是一种随机搜索算法，适合对较大特征空间进行搜索，不要求评价函数具有单调性，因此在特征选择、参数寻优、系统控制等多个领域都有成功应用［８～１１］。遗传算法具有天然的并行结构，但本质上其运行仍是串行的。为了提高遗传算法运行速度，并行遗传算法受到了广泛关注［１２～１３］。但是目前的遗传算法还存在一些不足之处，如早熟收敛等，尤其是没有考虑对由多种不同性质的特征组成的多质特征空间进行局部化管理的合理性和必要性。为解决上述问题，受“段式内存管理”和“子集划分”［１４］思想的启发，本文提出了一种改进的遗传算法（ｉｍｐｒｏｖｅｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ，简称ＩＧＡ），该算法通过分段式染色体管理方案实现对棉花异性纤维多质特征空间的局部化管理，通过分段交叉和分段变异算子避免产生无效染色体，提高搜索效率；通过自适应调整交叉和变异概率，实现算法搜索能力与收敛速度的动态调整。１　棉花异性纤维目标特征提取棉花异性纤维种类很多，在可见光波段成像可以较容易地识别深色异性纤维，但却无法检测白色和无色异性纤维。部分含荧光物质的白色异性纤维经过紫外线照射可以发出荧光，因此也可以实现视觉检测［４～５］。对于其余异性纤维，理论上可以通过多光谱成像进行检测，但由于目前的实验条件所限，还无法展开研究，故本文只涉及在可见光波段能够识别的异性纤维。对图像分割得到的异性纤维目标，单独使用某种特征几乎无法对其进行准确分类；通过组合使用颜色、形状和纹理特征，则可以提高异性纤维分类的准确率。１１　颜色特征提取颜色是区分棉花异性纤维类别的一种重要特征。采用不同的彩色空间，可以得到不同的颜色特征表示。棉花异性纤维图像采用ＲＧＢ彩色空间，考虑到将ＲＧＢ彩色空间转换到其他彩色空间会影响系统的实时性，故直接在ＲＧＢ彩色空间对异性纤维目标进行颜色特征提取，包括：红色均值、绿色均值、蓝色均值、红绿蓝总均值以及红绿蓝３个分量的标准差，记为Ｃ１～Ｃ５。１．２　形状特征提取不同种类的异性纤维经过开松后，在棉层中呈现不同的形状，典型的是片状、绒状和线状［３］。异性纤维目标的形状特征可以由其几何属性（如长短、面积、凹凸等）和拓扑属性（如连通性、欧拉数等）进行描述。提取的形状特征包括：形状因子、外观比、扩展比例、充实度、偏心率、球状性和欧拉数，记为Ｓ１～Ｓ７。１．３　纹理特征提取纹理反映了图像亮度的空间变化情况。描述纹理的参量包括纹理的强度、密度、方向、粗糙度等。纹理分析方法包括统计纹理分析法和结构纹理分析法［１５］，其中统计纹理更适合描述含有异性纤维的棉层纹理。提取的纹理特征包括：基于灰度直方图的平均亮度、平均对比度、平滑度、三阶矩、一致性和熵，以及基于灰度共生矩阵的角二阶矩、熵和对比度，记为Ｔ１～Ｔ９。１．４　特征数据描述从采集的异性纤维图像中选择有代表性的图像７９幅，其中头发１７幅，黑色塑料布１４幅，红色布条１２幅，麻绳１２幅，红色丙纶丝１２幅，鸡毛１２幅。对这些图像进行手工处理，去掉图像中棉花叶、棉花籽屑等伪异性纤维，保证图像中异性纤维的单一性以简化图像处理过程。经过图像分割，得到３５６个异性纤维目标，其中头发３０个，黑色塑料布７７个，红色布条５５个，麻绳１１８个，红色丙纶丝２７个，鸡毛４９个。对３５６个异性纤维目标逐个进行特征提取，得到每个异性纤维目标的５个颜色特征Ｃ１～Ｃ５，７个形状特征Ｓ１～Ｓ７，９个纹理特征Ｔ１～Ｔ９，组成２１维４７１农　业　机　械　学　报　　　　　　　　　　　　　　　　　２０１０年的特征向量。将此３５６个特征向量分成参考集和测试集，其中参考集包含２０６个异性纤维目标，分别是：头发１５个，黑色塑料布４７个，红色布条３０个，麻绳６８个，红色丙纶丝１７个，鸡毛２９个。测试集包含１５０个异性纤维目标，分别是：头发１５个，黑色塑料布３０个，红色布条２５个，麻绳５０个，红色丙纶丝１０个，鸡毛２０个。为消除由于不同特征取值范围不同造成的影响，所有特征数据都进行了归一化。２　基于改进遗传算法的特征选择基本遗传算法（ｓｉｍｐｌｅｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ，简称ＳＧＡ）由于采用固定的交叉和变异概率，因此容易出现种群早熟现象而无法得到最优解。棉花异性纤维目标的特征空间由颜色、形状和纹理３种完全不同性质的特征组成，且３种特征在棉花异性纤维分类中都不可或缺。目前的遗传算法没有考虑对多质特征空间进行局部化管理的合理性和必要性，也没有考虑利用进化代数来动态调整交叉和变异概率。因此，无法满足棉花异性纤维目标的特征选择需要。本文提出的改进遗传算法通过分段式染色体管理方案，实现对棉花异性纤维目标多质特征空间的局部化管理；通过分段交叉和分段变异算子避免产生无效染色体，进而提高搜索效率；通过自适应调整交叉和变异概率，避免产生早熟收敛。算法流程如图１所示。图１　改进遗传算法流程图Ｆｉｇ．１　ＦｌｏｗｃｈａｒｔｏｆＩＧＡ　２．１　分段式染色体管理方案采用分段式染色体管理的目的是为了实现对多质特征空间进行局部化管理，避免产生无效染色体，提高搜索效率。该方案包含分段式二进制编码和分段式染色体管理两部分内容。如图２ａ所示，根据棉花异性纤维目标的特征空间组成，分段式二进制编码方案将整个染色体在逻辑上分为３个子段，其中第１个子段实现对颜色特征的基因编码，表示为Ｃ１～ＣＫ，Ｋ为颜色特征的个数。Ｃｉ为１或０表示第ｉ个颜色特征被选中或落选。第２个子段实现对形状特征的基因编码，表示为Ｓ１～ＳＭ，Ｍ为形状特征的个数。Ｓ