0 引言

在实际生活中，很多问题并不能用简单的线性相加解决，比如工人的工作效率问题，工人A和工人B一同工作，两人的工作效率不能简单地用工人A的效率和工人B的效率相加，因为他们之间会相互影响。模糊测度^[1]，也称为非可加测度，能够很好地表示各个特征以及特征组合对决策的贡献度。每一个模糊测度对应一个特征集合的子集，对于有n个特征的数据集，模糊测度的个数为2ⁿ-1。

模糊积分^[2]是近20 a来出现的新的有效的分类器，尤其适用于特征之间存在相互影响的情况，它是基于模糊测度的非线性积分。1991年，文献[3]提出Choquet模糊积分。2000年，文献[4]提出Zhenyuan模糊积分。模糊积分理论不断扩展延伸。Choquet积分是Lebesgue积分的严格推广，而且计算相对简单，因此广泛应用于实际问题中。在疾病分类^[5]、害虫预测^[6]、物流供应商选择决策^[7]以及企业的效绩评估^[8]等实际问题中取得很好的效果。文献[9]提出基于Choquet积分的非线性回归模型，并在往后的研究中给出一个基于遗传算法的求解方案^[10]。使用遗传算法搜索Choquet积分模型的解是一个确定模糊测度的过程，虽然能取得一定的效果，但是收敛速度慢，搜索十分耗时。因此本研究提出使用蚁群算法来求解Choquet积分模型参数，给出搜索过程的算法，最后使用几个经典的疾病分类的数据集，通过试验来比较蚁群算法和遗传算法的结果差异，并且也和其他常用的分类器进行比较。

1 模糊积分概述 1.1 模糊测度

经典测度也称可加测度，具有可加性，比如容器A和容器B的体积，他们的总体积等于两者之和。与可加测度相对，模糊测度具有不可加性，这里给出模糊测度的严格定义^[1]。

定义1  设Χ是任意集合，$\mathscr{F} $是Χ的子集构成的σ代数，集函数μ: $\mathscr{F}$ →[0, 1]当且仅当满足以下条件时，称为定义在$\mathscr{F}$的模糊测度：

(1) 平凡性 若∅∈ $\mathscr{F}$，那么μ(∅)=0；

(2) 单调性 若E∈ $\mathscr{F}$，F∈ $\mathscr{F}$，E⊂F，则有μ(E)≤μ(F)；

(3) 下连续性 如果E_n∈ $\mathscr{F}$ (n=1, …, ∞)，E₁⊂E₂⊂…，$\bigcup\limits_{n = 1}^\infty {{E_n} \in } \mathscr{F}$，那么$\mathop {\lim }\limits_n \mu \left( {{E_n}} \right) = \mu \left( {\bigcup\limits_{n = 1}^\infty {{E_n}} } \right)$；

(4) 上连续性 如果E_n∈ $\mathscr{F}$(n=1, …, ∞)，E₁⊃E₂⊃…，μ(E₁)＜∞，$\bigcap\limits_{n = 1}^\infty {{E_n} \in \mathscr{F}} $，那么有$\mathop {\lim }\limits_n \mu \left( {{E_n}} \right) = \mu \left( {\bigcap\limits_{n = 1}^\infty {{E_n}} } \right)$。

定义2^[11]  给定集函数μ: $\mathscr{F}$→(-∞, +∞)，如果μ(∅)=0，则称作符号型模糊测度。

定义1中模糊测度的非负性会对一些实际问题产生限制，定义2定义更一般的模糊测度，允许模糊测度为负数，因此，模糊测度可以看成是符号型模糊测度的一个特例。

1.2 Choquet模糊积分

常见的模糊积分有Sugeno模糊积分^[2]、Choquet模糊积分^[3]和Zhenyuan模糊积分^[4]。这里只对Choquet模糊积分做介绍，并且后面提到模糊积分不加说明都是指Choquet模糊积分。

定义3^[11]  设(Χ, $\mathscr{F}$)是可测空间，μ是$\mathscr{F}$上符号型模糊测度，实值函数f:Χ→(-∞, +∞)关于μ的Choquet模糊积分定义如下：

$ \left( c \right)\int {f{\rm{d}}\mu } = \int_{- \infty }^0 {\left[{\mu \left( {{F_\alpha }} \right)-\mu \left( X \right)} \right]{\rm{d}}\alpha } + \int_0^\infty {\mu \left( {{F_\alpha }} \right){\rm{d}}\alpha }, $

(1)

其中：μ(F_α)为符号型模糊测度, F_α={x|f(x)≥α, x∈Χ}，对任意的α∈(-∞, +∞)称作α截集。

当X是一个有限集合时候，即X={x₁, x₂, …, x_n}，为了方便计算，将f(x₁)，f(x₂)，…，f(x_n)按照非递减的顺序排列，如f(x₁^*)≤f(x₂^*)≤…≤f(x_n^*)，其中(x₁^*, x₂^*, …，x_n^*)是(x₁, x₂, …，x_n)的一个重排列，Choquet模糊积分可以表示成：

$ \left( c \right)\int {f{\rm{d}}\mu } = \sum\limits_{i = 1}^n {\left[{f\left( {x_i^*} \right)-f\left( {x_{i-1}^*} \right)} \right]\mu \left( {\left\{ {x_i^*, x_{i + 1}^*, \cdots, x_n^*} \right\}} \right)}, $

(2)

其中：f(x₀^*)=0。为了方便计算，文献[10]提出等价公式计算Choquet模糊积分：

$ \left( c \right)\int {f{\rm{d}}\mu } = \sum\limits_{j = 1}^{{2^n}-1} {{z_j}{\mu _j}}, $

(3)

式中：

$ {z_j} = \left\{ \begin{array}{l} \mathop {\min }\limits_{i:{\rm{frc}}\left( {\frac{j}{{{2^i}}}} \right) \in \left[{\frac{1}{2}, 1} \right]} f\left( {{x_i}} \right) - \mathop {\max }\limits_{i:{\rm{frc}}\left( {\frac{j}{{{2^i}}}} \right) \in \left[{0, \frac{1}{2}} \right]} f\left( {{x_i}} \right)\;\;\;\;\;{\rm{if}}\;\;{\rm{it}}\;{\rm{ > 0}}\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;0\;\;\;\;\;\;\;\;\;{\rm{otherwise}} \end{array} \right., $

其中，j=1, 2, …, 2ⁿ-1，${\rm{frc}}\left( {\frac{j}{{{2^i}}}} \right)$是分数$\frac{j}{{{2^i}}}$的小数部分的数值。

1.3 Choquet模糊积分分类

对于给定的一组样本各个特征值，和一组模糊测度值，利用式(3)即可求出每一个样本对应的Choquet模糊积分值。对于这组模糊积分值，可以使用Fisher线性判别进行判别分类^[5]，其基本思想是寻找一个最佳的投影方向，使得样本在投影后，类内方差尽可能小，类间的方差尽可能大。Fisher判别函数

$ g\left( x \right) = {\mathit{\boldsymbol{w}}^{\rm{T}}}x + b, $

(4)

式中:w^T是分类面的法向量，b为分类面的偏移量。当g(x)＞0时，模糊积分值归类为第一类；当g(x)＜0时，模糊积分值归类为第二类

2 蚁群算法

文献[12]通过模拟蚁群的觅食行为提出蚁群算法。除了在离散空间问题，在连续空间优化问题也适用。本研究参考已有的求解连续空间约束优化问题的蚁群算法^[13]，对蚁群算法做进一步改进，并应用于基于Choquet模糊积分模型的模糊测度的求解，再代入到Choquet模糊积分公式中，进行分类。

2.1 算法流程

(1) 初始化蚁群算法相关变量，设置蚂蚁数目m，m只蚂蚁随机分布，作为各自蚂蚁搜索的起点，第i只蚂蚁所代表的解为M_i=(μ₁ⁱ, μⁱ₂, …，μⁱ_j, …，μ_nⁱ)，其中μ_jⁱ∈[a, b]，j=1, 2, …, n。对每一只蚂蚁的具体值进行初始化：

$ \mu _j^i = a + \left( {b-a} \right) \times {\rm{rand}}\left( 1 \right), $

(5)

式中：a表示模糊测度的最小取值; b表示模糊测度的最大取值; rand(1)表示区间[0, 1]之间的随机数。设置蚂蚁i所在位置的信息素强度初始值

$ T\left( {i, 1} \right) = {\rm{fitness}}\left( {{M_i}} \right), $

(6)

fitness()是一个适应度函数，信息素强度初始值直接取决于蚂蚁对应的适应度。这个适应度函数是按照以下步骤进行计算的。

① 根据当前蚂蚁M(i)所表示的模糊测度，计算出每个样本对应的Choquet模糊积分值；

② 使用Fisher线性判别对Choquet模糊积分值进行分类；

③ 根据分类结果计算出分类的准确度accuracy和灵敏度sensitivity，fitness()函数值由这两个指标按照一定的权重比例决定

$ {\rm{fitness}}\left( {{M_i}} \right) = {w_1} \times {\rm{accuracy}}\left( {{M_i}} \right) \times {\rm{sensitivity}}\left( {{M_i}} \right), $

(7)

式中:w₁∈[0, 1]，w₂∈[0, 1]，w₁+w₂=1。

(2) 计算第t次迭代蚂蚁i的状态转移概率

$ P\left( {i, t} \right) = \frac{{\exp \left( {T_{{\rm{best}}}^t-T\left( {i, t} \right)} \right)}}{{\exp \left( {T_{{\rm{best}}}^t} \right)}}, $

(8)

式中：T_best^t表示当前第t次迭代中，信息素强度的最大值。由式(8)可知，蚂蚁所在点的信息素强度T(i, t)越强，状态转移概率P(i, t)越小。状态转移概率实际上是控制着蚂蚁搜索下一个解的策略。状态转移概率大，则会以较大的概率使用全局搜索的策略；状态转移概率小，则会以较大的概率使用局部搜索的策略。

(3) 根据状态转移概率P搜索各个蚂蚁的下一个位置，将搜索结果保存到临时数组temp。首先需要预先设置一个状态转移阈值P₀，搜索步长step，和步长参数λ。步长参数λ是由当前迭代次数决定的：

$ \lambda = \frac{1}{t}, $

(9)

随着迭代次数的增加，步长参数越来越小，蚂蚁搜索的跨度也就变小，利于收敛。对于蚂蚁i，若P(i, t)≤P₀，则进行局部搜索，局部搜索的步长为step，局部搜索算法如下：

$ {\rm{temp}}\left( {i, j} \right) = \left\{ \begin{array}{l} M\left( {i, j} \right) + {\rm{step}} \times \lambda {\rm{, rand}}\left( 1 \right) < 0.5\\ M\left( {i, j} \right)-{\rm{step}} \times \lambda, {\rm{else}} \end{array} \right., $

(10)

若P(i, t)≥P₀则进行全局搜索，全局搜索算法如下：

$ {\rm{temp}}\left( {i, j} \right) = \left\{ \begin{array}{l} M\left( {i, j} \right) + \left( {b-a} \right) \times {\rm{0}}{\rm{.5, rand}}\left( 1 \right) < 0.5\\ M\left( {i, j} \right)-\left( {b-a} \right) \times 0.5, {\rm{else}} \end{array} \right., $

(11)

值得注意的是，无论在全局搜索还是在局部搜索，若temp(i, j)的搜索结果超出[a, b]范围，则需要做越界处理，比a小则重置成a，比b大的则重置成b。从式(10)(11)可以看出，蚂蚁的状态转移概率比较小的时候，当前点的信息素强度较大，进行局部搜索，有利于能够在该点附近找到更优解；蚂蚁的状态转移概率比较大的时候，当前点的信息素强度较低，进行全局搜索，加快搜索的步长和随机性，加快寻优。

(4) 蚂蚁的位置更新。搜索出下一个位置后，还需要判断蚂蚁i需不需要移动到该位置，判断的式子如下：

$ {M_i} = \left\{ \begin{array}{l} {M_i}, \;\;{\rm{fitness}}\left( {{M_i}} \right) < {\rm{fitness}}\left( {{\rm{tem}}{{\rm{p}}_i}} \right)\\ {\rm{tem}}{{\rm{p}}_i}, \;{\rm{fitness}}\left( {{\rm{tem}}{{\rm{p}}_i}} \right) \ge {\rm{fitness}}\left( {{M_i}} \right) \end{array} \right., $

(12)

如果搜索的下一个位置蚂蚁的适应度比当前的适应度还要低，则放弃移动；否则就会移动到下一个位置。

(5) 信息素强度更新。信息素挥发系数ρ，ρ∈(0, 1)。参数ρ的取值直接影响到整个蚁群算法的收敛速度和全局搜索性能。ρ较小时，搜索的随机性就会增强；ρ较大时，能够加快收敛速度。当蚂蚁i移动后，需要进行信息素强度更新的操作。信息素强度更新公式：

$ T\left( {i, t + 1} \right) = \left( {1-\rho } \right) \times T\left( {i, t} \right) + {\rm{fitness}}\left( {{M_i}} \right), $

(13)

信息素挥发系数更新公式：

$ \rho = 0.1 \times \exp \left( {\left( {\frac{t}{T}} \right)*\ln 9} \right)。$

(14)

(6) 经过T次迭代后，选出适应度最大的蚂蚁M_best，M_best表示当前符合Choquet模糊积分模型的一组最优模糊测度。

2.2 算法总结

根据2.1描述的具体算法流程，这里对算法进行步骤总结:

(1) 初始化参数，包括蚂蚁数量m，需要估计的模糊测度个数n，模糊测度区间[a, b]，迭代次数times，状态转移阈值P₀，搜索步长step，信息素挥发系数ρ；

(2) 使用式(5)(6)(7)初始化蚂蚁集合M(i, j)和信息素强度T(i, 1)，其中i=1, 2, …, n；j=1, 2, …, m；

(3) 迭代times次，更新状态转移概率，蚂蚁集合，信息素强度；

① 使用式(8)计算状态转移概率P(i, t)，其中t=1, 2, …, times；

② 计算temp(i, j)，使用式(10)(11)进行局部搜索或全局搜索；

③ 使用式(12)更新集合M(i, j)；

④ 使用式(13)更新信息素强度T(i, t+1)，式(14)更新信息素挥发系数；

(4) 迭代结束，使用式(7)选出适应度最大的蚂蚁M_best。

2.3 算法改进思路

对于本研究改进的蚁群算法中，最大的改进是每一只蚂蚁都能进行全局搜索和局部搜索，这取决于状态转移概率。而改进前的蚁群算法^[13]，只允许当前最优的蚂蚁进行局部搜索。在实践过程中发现，除了当前最优解，当前次优解如果也进行局部搜索，会有很大可能解搜索到一个更优解。因此，本研究中的算法允许每一只蚂蚁根据状态转移概率随机选用局部搜索，是为了尽可能地找出更优解。

3 仿真试验

Choquet模糊积分模型模糊测度的求解也是一个在连续空间上的优化问题。为了分析遗传算法和改进后的蚁群算法在连续空间上的优化问题，使用如下简单的二元函数做仿真测试：

$ f\left( x \right) = 100 \times {\left( {{x_2}-x_1^2} \right)^2} + {\left( {1-{x_1}} \right)^2}, $

式中:x₁∈[-0.5, 0.5];x₂∈[-0.5, 0.5]，已知最小值为0.25。分别使用遗传算法和本研究使用的蚁群算法寻找这个二元函数的最小值。

试验中，遗传算法中个体编码使用实数编码，迭代次数取100，种群规模取100，交叉概率取0.7，变异概率取0.2；蚁群算法中迭代次数取100，蚂蚁数目取100，搜索步长取0.1。试验结果见图 1，遗传算法在100次迭代内仅能找到一个近似的最优值，而蚁群算法在第10次迭代就找到最优值，收敛性要好于遗传算法。虽然遗传算法可以通过增加迭代次数和群体规模获取更优解，但运算量大大增加。在同等条件下，由于蚁群算法的收敛性要好于遗传算法，因此蚁群算法在连续空间上寻找最优值的搜索效率要比遗传算法高，用时更少。

4 试验设计与分析 4.1 试验数据集

本试验将Choquet模糊积分应用在癌症分类问题上，并使用改进后的蚁群算法求解模型中的模糊测度。选用DLBCL^[14]、prostate^[15]和colon^[16]这3组经典癌症基因数据集作为试验分析对象，数据集情况请见表 1、2、3。

本研究使用R语言的Bioconductor工具箱对芯片癌症数据集进行一系列预处理^[17]，包括背景校正、标准化和汇总，预处理后会得到一个基因表达矩阵。然后进行基因表达差异的显著性分析，使用经验贝叶斯的分析方法^[18]，最后识别出显著变化的基因，并根据变化程度进行降序排列。对于这些显著变化的基因，这里分别取前3个、前5个、前8个特征进行重复试验。

数据集分组使用10折交叉，把数据随机分成10份，每次使用9份进行模型训练，剩下1份进行模型的试验验证，获取准确度，循环进行10次试验，最后取平均值。

4.2 算法参数

蚁群算法中不同参数的取值组合对试验结果影响很大，受数据集类型的影响。本试验中蚁群算法的参数取值见表 4。

4.3 试验结果与分析

试验中，使用决策树(DT)^[19]，SVM^[20]，KNN^[21]等分类算法和模糊积分(分别基于遗传算法实现的FI-GA和基于蚁群算法实现的FI-ACO)，模糊积分中模糊测度的求解分别使用改进的遗传算法^[10]和蚁群算法两种方案。在使用遗传算法解决模糊积分问题中，文献[9]提出针对此类问题的染色体编码方法，适应度评价方法和遗传算子。对本研究中使用的癌症基因数据集分类，只会出现4种结果^[5]：真正类，诊断结果为患病，实际情况也是患病；假正类，诊断结果为患病，实际情况是正常；真负类，诊断结果为正常，实际情况也是正常；假负类，诊断结果为正常，实际情况是患病。令TP、FP、TN和FN分别表示真正类、假正类、真负类和假负类的数目，本研究将采用准确度和敏感度作为分类指标，公式如下：

$ \begin{array}{l} {\rm{accuracy = }}\frac{{{\rm{TP + TN}}}}{{{\rm{TP}} + {\rm{TN}} + {\rm{FP}} + {\rm{FN}}}}, \\ \;\;\;\;\;{\rm{sensitivity = }}\frac{{{\rm{TP}}}}{{{\rm{TP}} + {\rm{FN}}}}, \end{array} $

和准确度相比，灵敏度在癌症分类中具有更加积极的意义，因为高灵敏度代表着对患病样本误判的概率很低。针对不同的数据库，测试结果分别如表 5、6、7所示。

表 5为DLBCL数据集试验结果，从表格数据中，可以分析出以下几点：

(1) 在DLBCL数据集中，模糊积分CPU时间是要比另外3种算法要长。但是，模糊积分的测试准确度和测试灵敏度明显高于另外3种分类算法；

(2) 使用蚁群算法求解的模糊积分准确性要比使用遗传算法略高，同时速度也比遗传算法快。

表 6为prostate数据集试验结果，这个表格中的数据显示，模糊积分总体性能比另外3种分类算法略高，这方面优势不明显，模糊积分仍然能够保持着高灵敏度。这意味着更少地将患者分类为正常，因此，模糊积分表现出的高灵敏度在这个领域中有积极作用。在模糊积分的实现上，蚁群算法和遗传算法的分类结果差异不大，但是蚁群算法的CPU运算时间明显低于遗传算法。

表 7为colon数据集试验结果，这个试验中可以发现，从总体来说，使用蚁群算法实现模糊积分的分类效果更好。而使用遗传算法实现的模糊积分仅仅表现出灵敏度上的优势，而没有在准确度上体现优势。

从这几个试验中可以发现，模糊积分运算时间较长，但表现出较好的准确度和较高灵敏度，在特征数量较少时模糊积分是一个很好的选择。而在实现方式上，分别使用蚁群算法和遗传算法求解模糊测度，在分类结果中，没有必然性，也就是说使用蚁群算法未必比使用遗传算法实现的分类效果好，因为分类结果有可能很接近。但是在收敛性方面，蚁群算法要比遗传算法的收敛性更好，因此时间消耗明显比遗传算法少。

5 结论

本研究在已有的蚁群算法上进行改进，并应用到Choquet模糊积分中模糊测度的求解。实际运算中发现, 在非最优解的基础上做全局搜索也可能得到更优解，因此在算法中做出改进，允许每一只蚂蚁有一定的概率做全局搜索。试验中分别基于遗传算法和改进后的蚁群算法构建Choquet模糊积分的分类器，应用于癌症基因数据集，结果表明，在求解模糊测度这个问题上，蚁群算法比遗传算法具有更快的搜索解的速度，甚至会得到更好的分类结果。仿真试验证明，蚁群算法的收敛性要好于遗传算法，大大降低搜索的迭代次数。在后续的工作中，将研究更多的不同领域的数据集，尝试用不同的参数值组合进行测试，研究参数对分类效果的具体影响。