第3章〓高维数据特征选择的多目标蚁群算法 3．1引言 高维数据的特征选择是多目标无序组合优化问题，多目标优化问题的研究由来已久，它是指多个目标不分主次的优化问题［1］。多目标优化一般是NP难问题，即不能在多项式时间得出最优解，常用的解决多目标优化问题的一类算法称为多目标演化算法(Multiobjective Evolutionary Algorithm)，对多目标演化算法的研究一直是学术界的热点问题［23］，如基于分解的多目标演化算法、非支配排序遗传算法Ⅲ、两档案算法以及多目标蚁群优化(Multiobjective Ant Colony Optimization，MOACO)算法等［27］。其中MOACO在解决多目标组合优化问题方面具有信息正反馈、内在分布式和易于与其他算法结合等特点，吸引了众多研究人员的关注。 多目标组合优化问题包含两种类型： 一类是以多目标旅行商问题为代表的有序组合优化问题； 另一类是以多目标特征选择问题为代表的无序组合优化问题(多目标子集问题)。由于多目标旅行商问题的解是有序的路径，符合蚂蚁顺序选择路径的过程，因此通过MOACO求解多目标旅行商问题是最早的成功案例，对MOACO的改进也常以多目标旅行商问题为背景［89］。然而在处理多目标子集问题方面，当前的MOACO算法存在两点局限性： 一是多目标子集问题的解是元素的集合，与蚂蚁选择路径的次序无关，目前的MOACO算法是将信息素放在物品(元素)上，蚂蚁根据物品上的信息素浓度和启发式信息有序选择路径，从而导致解的无序性和蚂蚁选择物品的有序性之间存在矛盾，即更新信息素对蚂蚁的影响具有不确定性［1011］； 二是多数MOACO算法解决二目标优化问题，在扩展到三个以上目标的优化问题时其参数较难设置，导致MOACO算法难以处理具有较高目标维度的子集问题［12］。 本章提出基于等效路径更新的两档案多目标蚁群优化(Multiobjective Antcolonyoptimization Based on Two Archives and Equivalent Routes Update，MATA&ERU)算法，使用等效路径信息素增强策略，消除解的无序性与蚂蚁求解有序性之间的矛盾，将原目标转换为收敛性目标和多样性目标并设置对应的帕累托档案，提升MOACO的扩展性。 3．2理论方法 3．2．1两档案设置 首先介绍多目标优化的相关概念，以最小化优化问题为例，多目标优化问题可由式(31)描述 minF(x)=（f1(x),f2(x),…,fm(x)）T,x∈Ω(31) 式(31)中，决策向量x=(x1,x2,…,xn)属于非空决策空间Ω，目标函数向量F： Ω→Λ由m(m≥2) 个目标组成，Λ是目标空间［13］。 帕累托支配(Pareto Dominance)，给定两个解x,y∈Ω以及它们对应的目标向量F(x),F（y）∈Rm，当且仅当i∈{1,2,…,m}，fi(x)≤fi(y)且j∈{1,2,…,m}，fj(x)σ do 4.当前位置值取反； 5.end if 6.end for 7.若变异结果为不可行解，则调整为可行解并转换为路径解 表31中第1行是将蚂蚁的路径解转换为染色体，第2~6行是逐位访问染色体并进行变异操作，第3、4行是变异操作，即若当前随机值大于设定阈值，则对当前位的值取反(1变为0，0变为1)，第7行是将变异解调整为可行解并转换为蚂蚁的路径解进行输出，可行解的调整过程采用Li K等使用的方法［23］。 3．3．3两档案更新 每轮迭代后，需要更新全局收敛性档案与多样性档案中的帕累托解，MATA&ERU固定档案规模，档案中解的个数超过设定规模时，需要删除多余解。当前存在一类能够综合反映解集质量的指标函数，其中最具代表性的是hypervolume指标和epsilon指标，这些指标与帕累托关系存在严格的单调性，即指标数值越高，帕累托解在收敛性与多样性方面的质量越好［2425］。但是由于hypervolume指标计算复杂度较高，因此在实际中常用于评估解集的质量，而epsilon指标的计算复杂度较低，因此MATA&ERU将epsilon指标作为收敛性目标函数，评估收敛性档案中解的适应度，保留具有较好收敛性的解。epsilon指标的定义如式(38) Iε+(x1,x2)=minε(fi(x1)-ε≤fi(x2)),i∈{1,…,m}(38) 式(38)表示解x1弱支配解x2需要移动最短距离值ε。根据epsilon指标定义，为个体解x1分配适应度的方法如式(39) Θ(x1)=∑x2∈P\\{x1}-e-Iε+(x2,x1)/k(39) 式(39)中，k是算法运行参数，一般设置为0．05。 综上，收敛性档案中的帕累托解更新伪代码如表32所示。 表32收敛性档案更新伪代码 输入： 待更新的收敛性档案Ac，收敛性档案规模Nca 输出： 经过更新的收敛性档案Ac 1.while |Ac|>Nca do 2.选择Θ(x*)值最小的解x*； 3.将个体解x*从收敛性档案Ac中删除； 4.通过式Θ（x）=Θ(x)+e-Iε+(x*,x)/k更新档案中剩余个体解的适应度值； 5.end while 表32中，第1行循环判断当前档案中个体解的规模是否超过设定阈值，第2~4行是通过计算个体适应度值逐一删除档案中的个体解。 多样性档案使用本章提出的多样性度量指标γ进行更新，与收敛性档案逐个删除多余解的方式不同，多样性档案通过逐一选择个体解的方式进行更新，其伪代码描述如表33所示。 表33多样性档案更新伪代码 输入： 待更新的多样性档案Ad，多样性档案规模Nda 输出： 经过更新的多样性档案Ad 1.if |Ad|>Nda do 2.计算档案Ad中每个解在多样性指标γ上的值； 3.按照γ值对Ad中的每个解进行降序排列，并选择前Nda个解； 4.清空档案Ad并使用选择的Nda个解组成新的多样性档案Ad； 5.end if 表33中，第1行判断当前档案中的个体解规模是否超过设定阈值，第2~4行通过计算个体解的多样性评估值，选择满足档案规模的个体解组成新的多样性档案。 3．3．4信息素更新方式 收敛性档案与多样性档案更新完成后，需要更新全局收敛性信息素矩阵和多样性信息素矩阵，MATA&ERU使用收敛性档案中的解更新收敛性信息素矩阵，多样性档案中的解更新多样性信息素矩阵。 档案中的路径解按照3．2．2节等效路径信息素增强策略更新信息素矩阵，若在l时刻拟对路径tabut上的信息素值进行更新，更新方法如式(310) τij(t)=(1-ρ)τij(t-1)+Δ′(tabut),eij∈Ψ(tabut) (1-ρ)τij(t-1),其他(310) 式(310)中，ρ是信息素挥发系数，Δ′(tabut)是信息素更新增量，Ψ(tabut)是tabut的等效路径，Δ′(tabut)的计算通过式(311)实现 Δ′(tabut)=Q×Sg(tabut)/NA(311) 式(311)中，NA表示档案中解的个数(为Nca或Nda)，Sg为路径tabut的评估值(收敛性评估值或多样性评估值)，Q是常数，根据ρ值确定。 3．3．5算法伪代码及时间复杂度分析 综上所述，MATA&ERU算法的伪代码描述如表34所示。 表34MATA&ERU伪代码 输入： 收敛性档案Ac，收敛性档案规模Nca，多样性档案Ad，多样性档案规模Nda，蚂蚁数量Na，变异阈值σ，最大迭代次数NC 输出： 多样性档案Ad 1.while迭代次数iter