基于混合进化算法的子结构发现研究

发布时间：2020-05-01 00:19

【摘要】： 关系无处不在。近年来,学习数据中各种关系的结构数据挖掘得到了广泛的关注并成为了数据挖掘与机器学习领域的一个重要分支。结构数据含有更为丰富的信息,更能反映问题的本质,同时也会导致更大、更复杂的假设空间,从而向数据挖掘与机器学习领域提出了新的挑战。本文将在众多的复杂问题求解过程中表现突出的进化算法引入到结构数据挖掘的子结构发现之中,取得了较同类算法更好的实验结果。本文的主要工作包括如下内容: 1、依据混合进化算法理论提出了混合进化子结构发现算法HEASD。在HEASD中,给出了基于图的染色体表示和遗传算子,并将爬山算法的思想融于交叉和变异算子的设计之中,实验结果表明了该算法的有效性。同时我们还提出了一种新的子结构扩展方法—单标签扩展,并对其正确性和有效性进行了理论证明和实验验证。 2、子图同构问题是图数据挖掘的瓶颈问题,是造成问题复杂的根源所在。其表现之一就是它造成了进化的单向性,从而导致了查找的不完全性。为此我们提出了基于带回溯个体的混合进化子结构发现算法HEASDBT,将回溯机制融入到了进化过程之中,可以对假设空间中的某些关键区域进行密集搜索,实验结果表明了该算法的有效性。 3、实例丢失现象是结构数据挖掘中广泛存在的造成解质量降低的一个重要原因。为此我们提出了两个算法HEASDFI和HEASDCI,前者采取“预防”的策略,尽量避免实例的丢失;后者则采取“治疗”的办法,重新找回丢失的实例。实验结果表明了以上两种算法的有效性。在HEASDCI中,我们还提出了一个新的遗传算子—个体协同算子,使多个代表同一子结构的不同个体可以对同一目标进行协同查找,以提高解的质量。由于个体协同算子需要进行频繁的图同构操作,而图同构操作虽然不像子图同构那样已被证明是NP完全问题,但目前还没有多项式级的算法存在,为此本文提出了一个时间复杂度为多项式级的近似图同构算法以提高个体协同算子的执行效率。 4、将本文提出的算法应用于学科建设和区域经济研究。前者将各院校信息与计算科学学科的培养目标、课程设置等信息组织成为图数据,然后用本文提出的算法挖掘出典型模式作为新建专业的参考模型;后者将我国35个大中城市2005年的经济发展数据及城市之间的地域相邻关系建模为一个图,并用本文提出的算法挖掘出满足一定约束条件的经济发展模式。
【图文】：

带标签

<vertex1 #> <vertex2 #> <label>中，<vertex1 #>为该边第一个结点的编号，<vertex2 #>为该边第，<label>为该边的标签。d 表示该边为有向边，u 表示该边为示有向边，但当 Subdue 带“-undirected”选项运行时，e 即表外，当一行以%开始时，表示该行为注释行。图 2-5 一个由 10 个几何对象组成的图，虚线方框框住的部分为用 Subdue 发现的典型子结构

进化算法,搜索空间,约束优化问题,性能

局部查找可以改善进化算法对搜索空间的采样性能
【学位授予单位】：天津大学
【学位级别】：博士
【学位授予年份】：2008
【分类号】：TP18

【参考文献】