A Duplication Analysis Based Evolutionary Algorithm for Bi-objective Feature Selection

最近看了一篇关于分类的特征选择进化算法的论文，记录一下。

改论文的链接如下：https://ieeexplore.ieee.org/document/9165863

1. 摘要

特征选择的目的：降低维数，提高分类的效率

然而现有的很多方法主要考虑的是单目标的优化，而现实中的问题具有多个目标，因此需要有效的进化算法去处理多目标的特征选择问题。

多目标特征选择的两个目标：1.最小化特征的数量2.最小化分类的错误率

这篇文章针对分类中的多目标的特征选择提出了DAEA（基于重复分析的进化算法）

该算法对基本的基于支配的EA框架进行了三个方面的改进：
1.修改繁殖过程提高后代的质量
2.重复分析的方法过滤冗余解
3.采用多样性选择的方法进一步保留解

在实验中，我们将所提出的算法与五种最新的多目标进化算法(MOEAs)进行了比较，并在20个分类数据集上测试了它们，使用了两个广泛使用的性能指标。从实证结果来看，DAEA在大多数数据集上的表现都是最好的，说明DAEA不仅获得了优异的优化性能，而且得到了良好的分类和泛化结果。

创新点：
1.在最初的选择中，提出复制分析方法判断需要在目标空间中过滤哪些重复解，主要思想就是通过解在决策空间的距离去估计他们的差异性，具有低差异的，解最可能被过滤，这种方式目标空间中的种群的多样行被维持，使得测试集上的潜在最优解得以被保留。

2.在处理重复后，提出了一种基于多样性的选择方法，进一步选择非主导排序后的解。与传统的拥挤距离方法不同，该方法忽略了特征选择的本质，将所选特征子集相同大小的解的个数作为第一选择准则，并结合拥挤距离作为补充准则。

3.改进了繁殖过程，采用小生境交配在目标空间中集合相邻解，采用k位交叉方法避免复制相同的子代，采用混合变异方法平衡已选特征和未选特征的变异率。

2. 介绍

与传统的搜索方法相比，EAs不需要领域知识和搜索空间假设。此外，它们的基于种群的搜索机制可以在一次运行中产生一组非主导解，在不同的冲突目标之间进行权衡，特别适合于多目标优化问题(MOPs)。这种EAs也可称为多目标进化算法(MOEAs)。

目前，根据环境选择策略的不同，MOEAs的主流可以大致分为四类。
MOEAs的第一类是基于Pareto优势关系，分析解在目标空间中的优势关系，通过非支配排序将解决方案划分为不同的非支配前沿。
第二类是基于分解方法，将一个多目标问题分解为一系列子问题，这些子问题分别与一个明确的和唯一的方向向量相关。
第三类是基于性能指标，采用一定的性能度量来估计解决方案的适应度。

第四类是指所有其他类型的MOEAs，如基于决策变量分析的EAs、基于距离测度的EAs、代用辅助的EAs或称为数据驱动的EAs，以及协同进化算法。

四类方式的特点：
基于分解方法：更易控制多样性和收敛性之间的平衡，但是对分解参数和方向向量的分布具有很高的依赖性

基于性能指标：与评估的性能度量高度相关，适应度的计算比较耗计算资源

基于pareto优势的方法：不需要额外的参数与较少的计算资源，但是难以在多目标搜索空间收敛，而在双目标特征选择中这个问题得到了解决。同时大多基于优势的EAs的多样性维护、复制过程需要加以改进才可以解决双目标特征选择问题。另外繁殖高质量的后代也是影响EA多样性和收敛性的重要因素，目前大部分采用的局部搜索等方法，易使种群陷入局部最优，基于GA的繁殖过程的研究比较少，本问基于GA进行研究。

特征选择的另一个重要问题是进化过程中，决策空间和目标空间经常发生重复，决策空间中发生的重复为决策向量的重复，可通过删除所有的重复，保留一个唯一解解决。目标空间的重复，即目标向量重复，对优化和分类性能的影响更为复杂，而且处理难度也更大，这是因为即使两种相同的解决方法，即使在训练数据上具有相同的性能，但是由于测试集未知，因此其性能可能会出现很大差异。

因此本文提出了DAEA对上述问题基于GA算法加以改进。

3. 算法

3.1 算法整体框架

初始化（代码1-5行） 繁殖（8） 环境选择（10-16）

1. 重复分析（12）
2. 非支配排序（13-15）
3. 多样性维护（16）

下面依次介绍上述框架中的各个部分：

3.2 初始化及终止条件

初始化：（实际上该算法是为大规模特征选择优化的）
当特征总数不超过种群规模3倍时，随机选择特征，不受约束。
当特征总数超过种群规模的3倍时，使用较少的规模进行初始化利于收敛，如果特征数量过少，很难覆盖整个决策空间，这里的3倍是一个权衡的选择，此时探索规模缩小到种群规模的三倍。

终止条件：
DAEA的终止准则是基于目标函数评价的次数，每代增加N次

3.3 繁殖

主要分为3个部分：

1. 小生境交配（1-12）
2. k位交叉（13-21）
3. 杂交突变（21）

小生境交配法：从领域（小环境）或全局（整体）中随机选择比例为80%或20%的亲本。采用该方法，是因为在目标向量相似的两个解之间交换进化信息是一种更稳定、更有效的方式。

在第2行中，邻域大小设置为人口大小的20%，考虑到客观空间的左、右、上、下四个方向，邻域大小至少设置为四个。
在第3行,目标向量在每个方向分别归一化到相同的规模,以保证选择相邻解的公平性(第4行)。
在13到20行算法,提出了k位交叉方法（仅对决策变量不同的位置进行交叉如：如果我们将下图中的解x1和x3作为两个父代来生成后代，我们将只在第1、4、5、6、7和8位随机交叉(因为这些位上的决策变量值不同)，而忽略第2和第3位。这样k-bit交叉法产生的后代更有可能与其亲本不同）。

图片说明：
以上四个不同的解(x1，…，x4)对于决策空间中共有8个特征的特征选择问题。

杂交突变

随机应用两种变异方法，分别20%和80%的比例采用下面两种变异方式 ：
改进的变异方法（2-10）
传统的变异方法（11-18）

代码说明：t1和t0不是解的指标，而是对应于已选择特征和未选择特征的某解决策向量中值为1或0的基因的指标。

算法5中详细介绍了混合变异方法，其中将改进的变异方法(第2 - 10行)与传统的变异方法(第11 - 18行)随机应用，分别约设20%和80%的比例。需要注意的是，我们并没有尝试寻找最佳的比例。使用传统变异算法如果选择的数量特征维数远小于D,添加新特征的概率将比删除旧特征的概率大很多，使用改进的变异算法，会使二者的概率缩小，使其更加公平。

举例说明：
让我们以两个选中特征(值1比特)的后代为例来说明上述观点，决策空间维数为10，未选中特征(值0比特)的数量为8。
因此，在传统的变异方法中，去除至少一个选中特征的概率为1−$(1-1/10{)}^2$= 0.19，而至少添加一个未被选中特征的概率为1−$(1-1/10{)}^8$= 0.57。改进的方法中，去除至少一个选中特征的概率为1−$(1-1/(1+2){)}^2$= 0.56，而至少添加一个未被选中特征的概率为1−$(1-1/(1+8){)}^8$=0.61

显然，在大约三倍的概率差的情况下，更有可能是添加特征而不是去除特征，这不利于后代的变异。而在修改后的变异方法中，去除至少一个选中特征的概率为0.56，而增加至少一个未选中特征的概率为0.61。可以看出，它们的概率差异大大缩小，概率几乎相同，这使得对0和1两个决策变量进行突变更加公平，增加了对所选特征进行刷新的机会。

该小节基础知识补充：
小生境交配
自于生物学的一个概念，是指特定环境下的一种生存环境，生物在其进化过程中，一般总是与自己相同的物种生活在一起，共同繁衍后代。把这种思想提炼出来，运用到优化上来的关键操作是：当两个个体的海明距离小于预先指定的某个值(称之为小生境距离)时，惩罚其中适应值较小的个体。
海明距离（Hamming Distance
在信息编码中，两个合法代码对应位上编码不同的位数称为码距，又称海明距离。例如，10101和00110从第一位开始依次有第一位、第四、第五位不同，则海明距离为3。

参考链接https://blog.csdn.net/SZU_Hadooper/article/details/78212092

3.4 重复分析

代码说明：
randi(k，|k|−1)表示从数组k(第15行)中随机选择(|k|−1)成员

如算法2所示，重复分析的主要思想是利用决策空间中解之间的曼哈顿距离来估计它们的不同程度，从而决定需要去除目标空间中的哪些重复解。

在第14 - 15行中，将重复解决方案按其不同程度分为两组:不同程度大于或等于去除阈值的远程解决方案和不同程度小于去除阈值的集群解决方案。其中，所有的大于阙值的方案保留，小于阙值的方案随机保留一个。

例如：

以上四个不同的解(x1，…，x4)对于决策空间中共有8个特征的特征选择问题，首先计算各自与所有解决方案的曼哈顿距离的最小值，然后作为评估所选特征的不同度（代码8-12行）
通过计算阙值为0.543（代码13行）
因此x3直接保留，其他三个解只保留一个（代码14-18行）

曼哈顿距离可参考：
https://blog.csdn.net/qq_38048756/article/details/107640915

3.5 多样性的维护

多样性选择准则：
拥挤距离（2-4）（补充准则）
多样性得分（5-11）（主要准则）

第4行中的排序使得具有较大拥挤距离的解决方案优先出现。
第7-8行中将未选择的解决方案的多样性得分设置为已经选择的具有相同数量选择特征的解决方案的个数。
最后，选择多样性得分最小的解(第10 - 11行)，而拥挤距离仅在有多个具有相同多样性得分最小的解的情况下，根据事先的排序(第4行)才起作用。

举例说明：

灰色点为非支配前沿已经选择的解，同一虚线上表示特征个数相同的解，一个红色圆圈表示一个相同解，{x1,x2,x3,x4,x5,x6,x7,x8}表示非支配排序未选择的解。

此时多样性得分别为{2,4,1,2,2,1,1,1}，因此x3,x6,x7,x8在多样性得分排名比较靠前，考虑其拥挤距离，因为边界解的拥挤距离为无穷大，因此x6,x7,x8拥挤距离大于x3，而三者的多样性得分相同，此时随机选择一个解如:x8。

另外需要注意的一点是选择的过程是动态的，每轮只选择一个解，比如下一轮应该选择x3，这是因为之前x8的选择使得x3的多样性得分高于x6,x7.

该小节基础知识补充：

支配与非支配：当A所有目标都优于B时，就说A支配了B，否则A和B就是一个非支配的关系。（比如A车价格30万，外观A等，性能A等；汽车B价格40万，外观A-等，性能A-等，就说汽车A支配了汽车B。如果有一辆汽车C价格20万，外观B等，性能B等，相较于汽车A，虽然C的外观和性能都比汽车A要差，但是其价格上比汽车A要低，从价格这个评价标准上来看，汽车C是要优于汽车A的，所以说汽车C和汽车A是属于一个非支配的关系。）种群中所有不被任何其他解支配的解构成了非支配前沿(Pareto最优解)

拥挤距离主要是维持种群中个体的多样性。具体而言，一般来说是指种群按照支配关系进行非支配排序后,单个Rank层中个体的密集程度。

遗传算法有自动收敛的性质，所以为了保证解的多样性，我们往往希望同一Rank层中的解能够相互分开，所以设置了 拥挤度 这个概念，认为 解之间距离大的解比解之间距离小的解更好 拥挤距离排序用于保持解的多样性。 每个个体的拥挤距离是通过计算与其相邻的两个个体在每个子目标函数上的距离差之和来求取，即下图中虚线四边形的长和宽之和。

参考链接： https://blog.csdn.net/u013555719/article/details/82936554

该篇论文的实验结果部分请自行查看。