基于蚁群聚类算法的板式定制家具订单聚类分析∗

陶 涛 王 洁 刘忠会 陈星艳 冯万福

（1.中南林业科技大学，长沙 410004；2. 欧派家居集团股份有限公司，广州 510000； 3. 江苏凯蒂家居用品有限公司，邳州 221300)

在现代家具企业中，传统的大批量生产模式已不适用，取而代之的是家具企业的大规模定制生产模式。大规模定制的核心就是以大规模的生产模式满足客户个性化需求[1-3]。目前，定制家具企业的生产是以订单为核心。定制化背景下家具订单的差异性较大，导致设备调整时间和企业生产成本增加，交货期延长[4-5]。因此，定制家具企业在排产前考虑订单的相似性，做好订单的管理工作，合理安排生产是企业降低生产成本的前提[6-8]。

蚁群算法是一种寻找最优路径的人工智能算法，有较强的鲁棒性和自适应性，目前，蚁群算法被大量运用于数据挖掘、机器人、电力、通信、交通等多个领域[9-16]。本文针对定制家具订单多品种小批量的情况，将蚁群算法应用于定制家具订单的聚类问题研究。通过模拟蚁群的觅食行为将算法应用于定制家具订单聚类问题分析中，以所有聚类类别中材料种类总和最小为聚类目标对定制家具订单进行聚类分析。

1 模型构建

1.1 问题描述

本文研究某定制家具企业在某一时间段内到达的多个订单，具有相同的交货期。由于板式定制家具企业在开料环节需要对原料板进行切割，不同的订单所需原料板的种类及数量各不相同。若对单个订单进行单独排产开料，会导致某些原料板的利用率较低，从而增加企业的生产成本。因此。现代的定制家具企业将几个相似订单组合在一起进行揉单生产。订单的聚类问题描述为：在某一时间段内有N个订单{O1,O2,…ON}，每一个订单有若干数量的板件，每个订单的板件材料种类不定。假设第i个订单Xi(i=1,2,3…N)中有t（t=1，2，3…n）种板件材料，每一种材料的总面积分别为{S1, S2…St}，则订单i的总面积为Si=S1+S2+…St。对这N个订单进行聚类，使得聚类完成后所有类别中的材料种类总和最少。

1.2 订单表示

由于定制家具订单中某些信息是非结构化信息，需将订单中材料文本数据转换成计算机能够识别的语言以便进行订单的管理工作。本文选取定制家具订单中订单名称，材料描述、订单面积作为关键信息对订单进行预处理。定制家具订单i可以表示为：

式中，tj表示材料j，Oij表示在订单i中材料j的出现情况。Si为订单i的板材总面积。由于板式家具开料工序是根据板件的材料种类进行开料，影响订单聚类的主要因素为材料种类。因此对于Oij值的表示为：若此材料在该订单文本中出现，则该值为1，若订单文本中该材料未出现，则该值为0。将定制家具订单集合转化为一个N×(n+1)的高维矩阵X，矩阵X表示: 总共有N个订单，每一行代表一个订单，该订单集合总共有n种材料种类，每一列代表一个材料种类。

1.3 订单相似度

为了对家具订单进行聚类，需要对各订单的相似程度进行描述。由于定制家具的生产特点，对于定制家具订单间的相似度的计算只考虑材料的出现情况，订单向量描述值为0 或1。Jaccard距离常用来处理仅包含非对称的二元(0-1)属性的对象，不考虑各属性的实际值[17]。因此，本文通过Jaccard距离对订单相似度进行计算。公式如下：

式中，Jij为杰卡德系数，表示订单向量Xi与订单向量Xj的交集元素的个数与订单向量Xi与订单向量Xj并集的元素个数的比例。Dij为杰卡德距离。Dij的取值范围为[0,1]，当值为1 时表示两个订单所需材料种类完全不相同;当值为0 时表示两个订单所需材料种类一致。

1.4 目标函数

本文以聚类完成后所有类别中的材料种类总和最少为目标函数。求解公式如下：

式中，Zj为第j类中订单包含的材料种类数，j为类别编号，K为聚类类别数目。

2 蚁群算法

2.1 蚁群算法原理

蚁群算法(ACA, Ant Colony Algorithm)是模拟蚂蚁觅食过程形成的搜寻算法。最早由Marco Dorigo提出[18]。算法的主要思想是蚂蚁在寻找路径的途中会释放一种信息素，信息素浓度与路径长度有关，路径越长，信息素浓度越低。每一只蚂蚁搜寻路径都会留下信息素，当下一个蚂蚁搜寻路径时选择信息素浓度较高的路径的概率较大。

基于蚁群算法觅食原理的聚类算法思路如下：将数据视为具有不同属性的蚂蚁，聚类中心则是蚂蚁搜寻的“食物源”，因此，数据的聚类过程就是蚂蚁寻找食物源的过程,通过模拟蚂蚁觅食行为将数据进行聚类分析的算法即为蚁群聚类算法（ACCA，Ant Colony Clustering Algorithm）[19]。

1）蚂蚁信息素矩阵表示为：τij（t）是t时刻ωi到ωj路径上残留的信息素量，路径（i，j）上的信息素定义为：

其中，r为聚类半径，本文选取r=1。

2)计算类别ωj合并到类别ωi的概率：

其中，τij为信息素浓度，ηij为启发式函数, ηij=1/Dij。α表示信息素启发因子的相对重要性; β表示启发式信息的相对重要性。

2.2 基于蚂蚁觅食的蚁群聚类算法

本文所运用的基于蚂蚁觅食的蚁群聚类算法是聚类数目未知的聚类算法。由于定制家具板材种类众多，对定制家具订单进行聚类时，无法在初始时设置聚类数目。该算法的目标是通过蚂蚁遍历所有的订单数据点，建立一条使目标函数值最小的路径，提高聚类的准确性。聚类过程描述如下：

假设第i个订单Xi(i=1,2,3…n)中有t（t=1，2，3…）种板件材料：

1）初始化算法参数，包括：蚂蚁个数，聚类半径r,直接转移阈值p0。

2）初始分配N个样品各自为一类（ω1, ω2, ω3…ωN）。

3）根据公式（3）计算类ωi与类ωj之间的杰卡德距离Dij。

4）根据公式（5）计算路径上的信息素量， 再根据公式（6）求解类i与类j之间的转移概率。

5）判断若Pij＞p0，则将类ωj归为类ωi，记下参加合并的订单序号，类别数减1。p0 为转移阈值。

6）当所有蚂蚁完成一次聚类之后，更新聚类中心和路径上的信息素。

7）判断各聚类中心之间的信息素值是否都为0，若否，转至步骤3）循环；若是，则表示聚类类别无法归并，计算各类别中订单的板材总面积。

8）判断是否存在各类别的板材总面积小于工厂规定的一个批次的板件生产的最小面积数，若否，则表示聚类完成。若是，将总面积数较少的类别两两归并。

由于各订单板件的材料种类不同及各订单的总面积数不同，对于同一个聚类，总面积数过小不利于后期的排产时原材料的优化，总面积数过大后续排产还需进行再分批，且若同一类别中材料种类过多，后期排产时会增加机器调整时间从而导致生产成本升高。因此为使聚类结果更符合实际生产，在算法中需设定一个类别的总面积数的范围。本文将其设定为工厂规定的一个批次的板件生产的最小面积数。

3 算法应用

本文以板式家具企业实际接受的订单数据为数据基础，随机选取50 个同一天交货期的定制家具订单，分别用编号1～50 表示家具订单。通过MATLAB软件进行仿真实验。对订单的聚类要求是使所有聚类类别的材料种类总和最小，且各类别的总面积大于工厂规定的一个批次生产的最小面积数。

3.1 订单预处理

对50 个家具订单进行预处理，这50 个家具订单总共包括30 种板材种类。生成50×31 的订单集合矩阵，其中，订单矩阵的最后一列为订单的面积，用于聚类的订单面积归并，在订单相似度计算时忽略该列。如表1所示。

表 1 定制家具订单向量矩阵示例 Tab.1 Example of vector matrix for customized furniture orders

3.2 相似距离确定

将每个订单作为一类，构成大小为50×50 的距离矩阵,通过距离矩阵计算信息素矩阵,继而计算类别之间的转移概率,根据转移概率对订单进行聚类，根据公式（6）求得类间转移概率矩阵。将类别之间的转移概率与转移阈值进行比较，进行类别归并循环迭代，直至满足聚类要求为止。

3.3 聚类算法结果

经过多次试验比较，最终确定本文算法的参数值如表2 所示。

表2 参数设置 Tab.2 Parameter setting

针对以上的50 个订单，运用传统的聚类数目已知的蚁群算法以及经典的聚类算法K-means算法进行聚类求解，与本文中的聚类数目未知的蚁群算法的结果进行对比，其结果如表3 所示。

表3 不同算法的聚类结果 Tab.3 Clustering results of different algorithms

3.4 算例结果分析

由于材料种类数决定了定制家具生产时机器调整总时间，对订单聚类要求是使所有类别中订单材料种类总和最少，使得参与聚类的所有订单的生产时机器调整总时间最少，从而提高企业的生产效率。假设板材材料更换导致机器的调整时间固定，用tm表示。

对比三种聚类算法的聚类结果可知，本文提出的未知聚类数目的蚁群聚类算法聚类完成后，所有聚类类别材料种类总和为30，聚类类目为7，算法计算时间为32.83 s。则对这50 个订单生产时机器调整的总时间为30×tm。而已知聚类数目的蚁群聚类算法在聚类之前需要找到一个较合适的聚类类目值，才能得到较好的聚类效果，增加了算法计算时间。根据本文算法的结果得到最优的聚类类别数为7，因此，预先设定聚类数目为7，通过聚类数目已知的蚁群聚类算法迭代得到所有聚类类别材料种类总和为42，大于原有订单的材料种类总数30，说明存在着具有不同板材种类的订单聚为一类的情况，使得所有类别中材料种类增多，机器调整的总时间为42×tm。经典的K-means算法计算快速，通过K-means算法聚类完成后所有类别中的材料种类总数为84，远大于这50 个订单的材料种类总数30，说明其不适用于定制家具订单聚类分析。

综上所述，对于定制家具订单的聚类分析，本文根据定制家具生产特点提出的蚁群聚类算法的聚类效果较好，结果更符合实际生产。

4 结论

本文结合定制家具的生产特点，根据蚁群的觅食行为，将聚类数目未知的蚁群算法应用于定制家具订单的聚类问题研究中。根据蚁群算法的特点计算类间转移概率，将类别进行归并，将本文提出的聚类数目未知的蚁群聚类算法，与聚类数目已知的蚁群聚类算法和经典的k-means算法进行比较，结果表明：本文算法能有效提高订单聚类的准确性，降低了定制家具订单生产时机器调整总时间，提高企业生产效率。