论文摘要
流程挖掘的目标是从事件日志发现流程模型,即从一些信息系统记录的事件日志中抽取活动间的关系和活动有关的信息。当前的大多数算法在处理复杂的控制流结构和噪音上存在着一些问题。遗传算法能一次处理除重复任务之外的所有结构,并且对噪音也是健壮的。但是该算法需要迭代很多代才能搜索到理想的模型。此外,只用适应度来评价遗传算法挖掘到的流程模型的质量并不全面反映模型的质量的好坏。本文提出了一种改进的遗传算法,能在相同运行代数内挖掘到质量更高的模型,并能提高原算法的效率;针对遗传算法的特点,组合了流程挖掘领域五个评价模型质量的标准来评价遗传算法挖掘到的模型质量。本文的具体工作如下:提出对交叉算子的改进方案:用个体解析日志中出现的问题来制定选择交叉点的启发式规则;对变异算子进行改进:给出了计算直接依赖关系和间接依赖关系的方法,然后利用活动间的依赖关系制订了指导变异的启发式规则;分析了算法的时间复杂度,给出了一种不改变时间复杂度级别的算法实现方案;针对遗传算法的特点,组合流程挖掘领域五个评价模型质量的标准:完整性要求(PFcomplete)、行为精确度(Bp)、行为重现度(Br)、结构精确度(Sp)、结构重现度(Sr)来评价遗传算法的结果。测试结果表明,改进后的算法效率更高,在同样的运行代数内挖掘的模型质量更高。用五个评价模型质量标准的组合评价遗传算法,不仅从行为上,也从结构上评价了算法挖掘到的模型的质量,能让我们更加详细地知道模型质量的好坏。