基于遗传编程的流程挖掘方法与遗传算法多样性优化研究

### 基于遗传编程的流程挖掘方法与遗传算法多样性优化研究 在流程挖掘和优化领域，如何高效准确地挖掘流程模型以及提升算法的搜索最优解能力是关键问题。本文将介绍一种基于遗传编程（GP）的流程挖掘方法，以及一种改进遗传算法（GA）多样性以提高最优解搜索能力的新方法。 #### 基于ECM的复杂度度量 传统的流程挖掘方法大多从行为角度出发，而本文提出的GP方法不仅从行为视角，还从结构视角挖掘流程模型。为了实现从结构视角挖掘，需要引入基于扩展因果矩阵（ECM）的流程复杂度度量。 在流程复杂度度量方面，我们选择了结构化度量（SM）。SM聚焦于模型结构，并且GA挖掘算法和SM都已在ProM框架中实现，这为改进GP方法提供了便利。 为了计算基于ECM的SM，我们首先定义了一些基于ECM的结构属性和组件类型： - **自由选择**：对于任意两个任务t1和t2，如果I(t1) ∩ I(t2)≠null，则I(t1) = I(t2)，这样的ECM称为自由选择ECM。 - **状态机**：对于每个任务t，其输入条件I(t)和输出条件O(t)中不存在AND/OR操作的ECM是状态机。 - **标记图**：对于每个任务t，其输入条件I(t)和输出条件O(t)中不存在XOR操作的ECM是标记图。 组件对应于一种行为模式，本质上是一个ECM。组件的定义用于迭代识别模式，为了定义不同的模式，还引入了一些组件符号和类型： - **组件符号**：ECM||C是将组件映射到ECM的函数，[ECM]是ECM的非平凡组件集合。 - **组件类型**：包括最大序列组件、选择组件、循环组件、最大标记图组件、最大状态机组件、结构良好组件、非结构化组件等。 计算基于ECM的SM的步骤如下： 1. 识别上述定义的组件类型形式的原子模式。 2. 迭代地将这些组件替换为任务，每次移除一个组件时，计算该组件的惩罚值并与新任务关联。 3. 重复上述步骤，直到ECM简化为只有一个任务的平凡ECM，此时该任务的惩罚值即为SM。 组件类型的优先级顺序为：最大序列组件 > 选择组件 > 循环组件 > 最大标记图组件 > 最大状态机组件 > 最大结构良好组件 > 其他组件。不同组件类型的惩罚值计算如下表所示： | C (Component) | ρECM(C) | | --- | --- | | MAXIMAL SEQUENCE | ∑t∈T τ(t) | | CHOICE | 1.5 ⋅ ∑t∈T τ(t) | | WHILE | 2 ⋅ {∑t∈I(C) τ(t) + ∑t∈O(C) τ(t)} | | MAXIMAL MARKED GRAPH | 2 ⋅ diff(T) ⋅ ∑t∈T τ(t) | | MAXIMAL STATE MACHINE | 2 ⋅ diff(P) ⋅ ∑t∈T τ(t) | | MAXIMAL WELL STRUCTURED | 2 ⋅ diff(P) ⋅ diff(T) ⋅ ∑t∈T τ(t) | | otherwise | 5 ⋅ diff(P) ⋅ diff(T) ⋅ ∑t∈T τ(t) | 其中，diff(P)是O(T)中XOR的总数与I(T)中XOR的总数之差的绝对值，diff(T)是O(T)中AND/OR的总数与I(T)中AND/OR的总数之差的绝对值。 计算基于ECM的SM的算法如下： ```plaintext (i) X := (ECM, τ), 其中 τ(t) = 1, ∀t∈T (ii) 当 [X] ≠ ∅（即X未简化为只有一个任务的ECM） (iii) 选择C，使得C是[X]中每个组件的最高优先级组件 (iv) 通过从ECM中移除C并用新任务tc替换它，得到ECM’ (v) τ’(tc) = ρX(C)，并且对于所有其他任务t，τ’(c) = τ(c) (vi) X := (ECM’, τ’) (vii) 输出SM(ECM) = τ(t) （ECM简化后T = {t}） ``` #### 遗传流程挖掘算法 遗传流程挖掘算法包含六个主要阶段： 1. **读取工作流日志**：获取流程执行的相关数据。 2. **计算任务间的依赖关系**：通过依赖度量确定任务之间的因果关系，该度量通过计算一个任务直接先于另一个任务的次数来确定任务关系的强