Page 368 - 《软件学报》2024年第4期

1946 软件学报 2024 年第 35 卷第 4 期

是多视角和多层次 [1,2] . 多视角强调从多个不同的角度对问题进行描述和处理. 多层次强调从多个粒度层次对问题
进行理解和描述, 在不同应用中, 不同的层次可被解释为不同的抽象度、不同的复杂度、不同的尺度、不同的细
节. 人们在实际问题求解时, 通常是综合考虑多视角与多层次进行问题求解 [1] . 下面以胃病诊断为例, 说明将多视
角和多层次结合起来的重要性. 在胃病诊断中, 为了获得准确的诊断结果, 病人通常需要做不同类型的检查, 如常
规检查, 通常包括: 是否腹痛、呕吐、出血等; 生化检查, 通常包括: 血常规、糖化血红蛋白、甲状腺功能等; 影像
学检查, 通常包括: 腹部泌尿彩超、CT、胃肠镜检查等. 不同类型的检查从不同的角度给出病人的信息, 可以将每
一种类型的检查作为一个视角. 在每个视角中, 随着具体检查项目的增加, 病人的信息会越来越详细, 从而构成多
个层次. 首先, 如果医生仅通过单一类型的检查, 即单一视角往往很难得到准确的结论. 因此, 医生会将不同类型的
检查结合起来进行诊断, 即综合多个视角的信息进行决策. 其次, 在某一视角中, 如生化检查, 医生一般不会让病人
一次做完全部的检查项目, 然后给出诊断结果. 而是让病人先做血常规, 然后根据血常规的结果尝试得出诊断结
论, 若无法确诊, 再进一步进行糖化血红蛋白等检查. 因此, 在每个视角中, 医生通常从多个层次逐步进行决策. 最
后, 实际诊断过程中, 医生会根据实际情况灵活地让病人进行不同视角和不同层次的检查. 例如, 病人可以先进行
腹痛、呕吐、血常规以及腹部泌尿彩超检查. 如果通过这些检查无法得出诊断结论, 则再进行糖化血红蛋白检查、
CT 检查等. 也就是说, 医生在对病人进行诊断时通常是在不同视角和视角的不同层次之间灵活选择和变换, 会将
多个视角、多个层次的检查结果结合起来考虑, 从而获得更加准确的诊断结果．但是现有的粒计算模型大都是分
别独立的研究多视角粒结构或者多层次粒结构, 没有将多视角和多层次结合起来. 多视角粒结构往往包含多个视
角, 但每个视角仅包含一个层次. 基于多视角粒结构主要有以下研究工作. Qian 等人 [3,4] 对 Pawlak 粗糙集进行拓
展, 采用一簇等价关系取代一个等价关系对论域进行分类和近似未知概念, 提出了多粒度粗糙集. 多粒度粗糙集
中, 每个粒度相当于一个视角, 其本质上是多视角粒结构. 之后, Qian 等人 [5] 将多粒度粗糙集与三支决策相结合, 提
出了多粒度三支决策. 利用多源近似空间表示多粒度空间, Khan 等人 [6] 提出了强弱上下近似集的概念. Sang 等人 [7]
提出了基于多源决策系统的决策粗糙集模型, 每个信息源均对应问题的一个视角. Chen 等人 [8] 基于多种形式的数
据操作, 提出了智能数据分析的多视角框架. 多层次粒结构往往仅包含一个视角, 但视角由多个层次构成. 基于多
[9]
层次粒结构主要有以下研究工作. Yao 基于一个嵌套的等价关系序列诱导出多层次粒结构, 提出层次粗糙集.
Hong 等人 [10] 基于粗糙集, 提出了从具有层次属性值的数据中学习多层次确定规则和可能规则的算法. Feng 等人 [11]
研究了具有层次属性值的层次信息系统, 提出了从不同的属性概念层自上而下挖掘层次决策规则的策略. Wu 等
人 [12] 提出多尺度决策信息系统, 将每个对象在每个属性下的属性值表示为多尺度值, 每个尺度对应一个层次. 在
此基础上, 很多学者对多尺度决策信息系统进行了深入研究 [13−22] .
划分序乘积空间作为一种新的粒计算模型 [23] , 将多层次粒结构和多视角粒结构相结合, 能够从多个视角和多
个层次对问题进行描述和求解, 符合人类的认知习惯. 划分序乘积空间的解空间是格结构, 格结构中的每个节点是
一个问题求解层. 在实际问题求解中, 如何在划分序乘积空间中找到合适的问题求解层进行问题求解, 是一个非常
重要的研究问题. 由于划分序乘积空间的解空间较大, 如何在划分序乘积空间中找到合适的问题求解层是一个
NP 难问题. 而遗传算法是处理 NP 难问题的常用方法, 因此本文采用遗传算法在划分序乘积空间中选择问题求解
层. 考虑到经典遗传算法存在收敛速度慢、容易陷入局部最优等问题. 我们对经典遗传算法进行改进, 提出一种两
阶段自适应遗传算法 TSAGA (two stage adaptive genetic algorithm), 使其能够有效地从划分序乘积空间中选择问
题求解层. 首先, 在算法第 1 阶段利用具有较少迭代次数的经典遗传算法对划分序乘积空间中问题求解层进行预
选取, 并将其作为第 2 阶段初始种群的一部分, 从而使第 2 阶段获得较优的初始种群, 缩小解空间范围优化解空
间. 然后, 在第 2 阶段中, 考虑种群的多样性会随着种群进化迭代次数的增加而变化, 我们定义随当前种群进化迭
代次数动态变化的自适应选择算子、自适应交叉算子和自适应大变异算子, 从而在优化的解空间中进一步选择问
题求解层, 实验结果证明了所提方法的有效性. 相比于其他遗传算法, 论文所提出的两阶段自适应遗传算法的优势
主要体现在以下 4 个方面.
(1) 通过两个阶段对解空间进行优化, 缩小了解空间的范围.
(2) 所提的自适应选择算子, 在种群进化的前期, 能够保证最优个体得以保留的同时加快算法收敛速度. 在种
群进化的后期, 能够在保留最优个体的同时降低对种群多样性的破坏.