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

徐怡 等: 基于遗传算法的划分序乘积空间问题求解层选择 1947

(3) 所提的自适应交叉算子, 能够保证在种群进化的前期, 采用较大的交叉概率, 提高算法的收敛速度. 在种群
进化的后期, 采用较小的交叉概率, 降低适应度值高的染色体被破坏的可能性. 同时适应度值较小的染色体能够取
较高的交叉概率来优化其基因型, 适应度值较大的染色体能够取较低的交叉概率来保留其基因型.
(4) 所提的自适应大变异算子, 基于大变异操作, 能够保证在种群进化的前期, 采用较小的变异概率来防止优
良基因被破坏. 在种群进化的后期, 采用较大的变异概率来增强算法跳出局部最优解的能力.
本文第 1 节介绍划分序乘积空间的相关知识. 第 2 节介绍本文提出的两阶段自适应遗传算法. 第 3 节通过仿
真实验验证所提算法的有效性. 第 4 节总结全文.
1 划分序乘积空间

划分序乘积空间同时考虑多层次和多视角 [23] , 因此可以更加全面地理解和描述问题, 从而更加合理地解决问
题. 给定一个论域, 首先, 划分序乘积空间将论域上的一个划分定义为一个层次. 其次, 使用一个嵌套的划分序定义
一个层次结构, 表示为一个视角. 最后, 给定多个视角, 则定义了多个线性序关系, 基于多个线性序关系的笛卡尔乘
积定义划分序乘积空间. 划分序乘积空间是一个格结构, 格结构中的每个节点都是问题求解的一个解决方案, 称为
问题求解层, 每个问题求解层均是多个单层次视角的集合.
定义 1 [24] . 一个决策系统定义为一个四元组 DS = (U,AT =C ∪ D,V, f) , 其中, U = {x 1 , x 2 ,..., x n } 为一个非空有
限对象集, 称为论域. AT 为一个非空有限属性集, 其中 C 为条件属性集, D 为决策属性, C ∩ D = ∅ , V 是属性集 AT
∪
的值域, V = a∈AT V a . f : U × AT → V 为信息函数, f(x,a) ∈ V a 表示对象 x ∈ U 在属性 a ∈ AT 上的取值.
定义 2 [23] . 给定一个决策系统 π = {A 1 ,A 2 ,...,A k } 是论域 U ∪ k A i ∩ A j =
DS,
上的一个非空子集簇. 若
i=1 A i = U 且
π 为 U 上的一个划分.
∅(i , j) , 则称
[23]
定义 3 . 给定一个决策系统 DS, π 1 = {A 1 ,A 2 ,...,A k } 和 π 2 = {B 1 ,B 2 ,...,B t } 是论域 U 上的两个划分. 如果 ∀B i ∈ π 2 ,
A j ∈ π 1 满足 B i ⊆ A j , 则称 π 2 比 π 1 细, 或称 π 1 比 π 2 粗, 记为 π 2 ≼ π 1 . 若 π 2 ≼ π 1 且 π 2 , π 1 , 则称 π 1 严格粗于 π 2 , 记为
π 2 ≺ π 1 .
[23]
定义 4 . 给定一个决策系统 DS, 划分序定义为论域 U 上的一簇划分 P = {π 1 ,π 2 ,...,π n } , 满足 π n ≼ π n−1 ≼ ... ≼ π 1 .
定义 5 [23] . 给定一个决策系统 DS, P = {π 1 ,π 2 ,...,π n } 是论域 U 上的一个划分序. 全序集合 (P,≼) 定义为一个视
角, 记为 v . 其中任一划分 π i 定义为一个层.
R = {E 1 ,E 2 ,...,E n } 是论域 U 上的一个嵌套的等价关系序,
一个划分序可由一个嵌套的等价关系序来构造, 假设
满足 . |x ∈ U} 是一个划分, 其中 = {y ∈ U|(x,y) ∈ E i } 是 x 关于 E i 的等价类, 1 ⩽ i ⩽
E n ⊆ E n−1 ⊆ ... ⊆ E 1 U/E i = {[x] E i [x] E i
n . 如果我们将 U/E i 作为 π i , 就可以得到一个划分序 P = {π 1 ,π 2 ,...,π n } .
因此, 视角由划分序定义, 划分序可由嵌套的等价关系序来构造. 现有很多方法可以用来构建嵌套的等价关系
序 [25−27] . 例如给定一个决策系统, 基于嵌套的属性集序列 C 1 ⊂ C 2 ⊂ ... ⊂ C n ⊆ C 可以构建一个嵌套的等价关系序. 给
I
1
k [26] V ≺ V I−1 ≺ ... ≺ V ,
定一个多尺度信息系统 S = (U,A) = (U,{a |k = 1,2,...,I, j = 1,2,...,m}) , 基于嵌套的属性值序列
j
也可以构建一个嵌套的等价关系序.
给定 m 个视角, 由 m 个视角构成的划分序乘积空间定义如下.
定义 6 [23] . 给定一个决策系统 DS, m 个视角 v i = (P i ,≼) 1 ⩽ i ⩽ m , 其中 P i = {π ,π ,...,π } π 表示第 个视角的
j
1
2
i
n i
,
,
i i i i
第 j 个层次, n i 表示视角 v i 的层次数, 1 ⩽ j ⩽ n i . 由 m 个视角构成的划分序乘积空间 POPS m 定义为 (P i ,≼) 的笛卡尔乘积:
m
POPS m = (× P i ,≼ P ) (1)
i=1
m
j 12
j 22
j m2
j 21
j m1
j 11
j i
j 1
j m
j 2
,
其中, × P i = {(π ,π ,...,π m )|π ∈ P i ,1 ⩽ i ⩽ m,1 ⩽ j i ⩽ n i } . 偏序关系 ≼ P 定义为: ∀(π ,π ,...,π m ) (π ,π ,...,π m ) ∈
2
1
2
2
1
i
1
i=1
m j 11 j 21 j m1 j 12 j 22 j m2 j i1 j i2
× P i (π ,π ,...,π m )≼ P (π ,π ,...,π m ) , 当且仅当 ∀1 ⩽ i ⩽ m π ≼ π i .
,
,
2
1
2
i
1
i=1
m
通常, 划分序乘积空间 POPS m = (× P i ,≼ P ) 可简记为 POPS m = (×P i ,≼ P ) .
i=1
定理 1 [23] . 划分序乘积空间 POPS m = (×P i ,≼ P ) 是一个格结构.
详细证明见文献 [23], 由定义 6 和定理 1 可以看出划分序乘积空间是通过多个视角的笛卡尔乘积定义的. 多