2.1.3　基于物元蚁群聚类算法的客户需求群划分

为了对客户需求群进行细分，采用具有较强灵活性、鲁棒性和自组织性的蚁群聚类算法，以客户需求物元为聚类对象，通过对相似客户需求信息的挖掘，形成客户需求群的最优划分方案。

蚁群算法（ant colony algorithm）是意大利学者Dorigo等于20世纪90年代初期受到自然界中真实蚂蚁觅食行为启发而提出的一种新型仿生优化算法。蚂蚁在觅食过程中，会在所经路径上释放出一种具有挥发性的物质——信息素，以此反映和传递搜索到的路径信息，不同蚂蚁个体通过感知信息素的存在及其强度来指导自己的移动方向。

仿生学家研究表明，蚂蚁更倾向于选择信息素密度较大的路径移动。相对路径越短，则一定时间内经过的蚂蚁数量越多，在该路径释放的信息素密度越大，被后续蚂蚁选择的概率就越高，由此形成一种正反馈机制：较短路径上的信息素浓度越来越大，其他路径上信息素浓度则相对较少，最终整个蚁群在这种自组织作用下搜索出巢穴与食物源间的最短路径。Dorigo的“双桥实验”形象地说明了蚁群发现最短路径的原理和机制。

蚁群算法借鉴了自然界中真实蚁群的觅食行为特点，通过将所研究的问题抽象为节点模型，将人工蚂蚁在节点间的逐步选取过程表征为解的构建过程，不断向部分解添加符合定义的解成分，从而构建出一个完整的可行解，最终在信息素的正反馈作用下逐步收敛到所求问题的最优解。

实际应用中，蚁群算法中的人工蚂蚁被赋予了如下一些性质。

（1）人工蚂蚁是借鉴真实蚂蚁觅食机理而抽象的简单智能体，能够由起始状态（空序列）独立完成可行解的构建过程，彼此之间也可通过介质相互影响。

（2）人工蚂蚁都存在信息存储器以记录当前（历史）解的路径信息及性能状态，用以参与转移概率计算、可行解构建、解决方案质量评估等过程。

（3）为人工蚂蚁引入与拟求解问题空间特征相关的启发式信息，以引导其初始阶段的搜索过程，增加算法的时间有效性。

（4）人工蚂蚁完成一个完整可行解的构建后，根据构建的解决方案更新相关联的信息素指导后续蚂蚁搜索。

具备上述特性的人工蚂蚁作为蚁群算法的基本单元协同实现具有自组织特性的寻优过程，同时也体现了蚁群算法的以下特征。

（1）分布式计算。蚁群算法将全局寻优的问题分配给每只蚂蚁去独立解决处理，然后将所有结果进行综合处理分析，即每个个体独立求解问题，因为蚁群存在大量个体也就意味着有很强的随机性，通过所有个体求得的解来进行对比分析，最终蚁群总会找到一个最优解，并不会因为某个个体死亡或者求得的解太差而影响最终结果。

（2）自组织性。蚁群中的每个个体蚂蚁都随机地搜索路径，并没有来自外部的干扰，通过蚁群走过路径上的信息素来感知路径搜索是否最优，经过一段时间后，蚁群自发地倾向于选择路径上信息素最大的路径，即最短路径。

（3）正反馈。蚁群算法的搜索是围绕着信息素进行的，由于路线距离越短，信息素越多，进而吸引越多的蚂蚁来选择这条路线，蚂蚁越多来这条路线行走，信息素又累积增加，这个过程使得算法处于正反馈状态，最终蚁群会找到最短路线。

基于以上蚁群算法的原理和特征，设计基于物元蚁群聚类算法的客户需求群划分流程如下。

（1）客户需求群相似度。指某一待聚类客户的需求物元S_i与其所在的一定局部范围内所有其他客户需求物元的平均相似度。客户需求群相似度的计算公式如下：

式中，Neigh_l×l（r）表示位置r周围的边长为l的正方形邻域；SI_ij为需求物元S_i与S_j的物元相似度；n_r为位置r周围邻域内包含的需求物元个数；α为群体相似性参数；v为蚂蚁的移动速度；v_max为蚂蚁最大移动速度。

（2）概率转换函数。指将客户需求群相似度转化为个体移动待聚类需求物元S_i“拾起”或“放下”物体的概率函数。“拾起”概率P_pick与“放下”概率P_drop分别为

式中

其中λ为调节参数。λ取值越大，曲线饱和越快，算法收敛速度也越快。

（3）平均聚类适度。用于反映所有客户需求物元的聚类程度。其计算公式如下：

随着聚类过程的进行，平均聚类适度也将不断变化，当其值趋于最大值时，聚类程度为最佳。

客户需求物元的蚁群聚类算法具体如下。

步骤1　初始化各参数，包括α、λ、最大循环次数T_max、蚁群规模Num_ant、半径l等。

步骤2　将所有客户需求物元作为数据对象随机分布在设定的二维网格上。同时，将蚂蚁初始化为空载状态，且随机放置于网格空间中。

步骤3　蚁群在二维空间中移动，并按以下搬运规则进行拾放操作：

如果蚂蚁空载，且在当前位置发现需求物元S_i，则按式（2-11）计算“拾起”概率。判断是否大于随机数ρ（ρ∈[0，1]），若是，拾起物元S_i；否则，转步骤4。

如果蚂蚁负载S_i，且在当前位置为空，则按式（2-12）计算“放下”概率。判断是否大于随机数ρ（ρ∈[0，1]），若是，放下物元S_i；否则，转步骤4。

步骤4　随机选择网格空间中未被其他蚂蚁占据的网格作为下一站。

步骤5　判断是否每只蚂蚁已完成操作，若是，转步骤6；否则，转步骤3。

步骤6　令计数器T=T+1，检查是否达到终止条件（平均聚类适度ζ收敛于最优值或达到T>T_max），若是，转步骤7；否则，转步骤3。

步骤7　输出聚类结果，算法结束。