论文摘要
最优树分解是Bayesian网理论和应用研究中的基本问题之一,不仅与Bayesian网的理论分析以及诸多实际算法关系密切,而且在计算理论中也占有重要地位。针对最小团树宽度、最小团树加权宽度和最小团树费用等不同的优化目标,分为treewidth、weighted treewidth、treecost三类不同的最优树分解问题。其中treewidth问题也是图论中的一个经典问题。虽然图论中对treewidth问题的研究由来已久,但对全部三类最优树分解问题,尤其是消去排序、三角化与最优树分解的关系,尚没有比较完整、严格的系统论述。在求解算法方面,启发式和智能优化是解决此类组合优化问题的两种主要方法,启发式适合在线实时快速求得可行解,智能优化则适合离线获取近似最优解。目前所提出的启发式求解结果大多比较差,而且面对不同具体问题表现并不稳定；针对treecost问题的智能优化方法虽然求解质量好于快速启发式,但与真正最优值相差仍比较大,同时鲁棒性并非足够好；而针对treewidth问题的智能优化方法,大多也存在着求解时间过长的缺点,距离实际应用要求还有很大差距。本文一方面从集合论和图论的角度,定义子集族评价函数及其稳定性,并在此基础上,对Bayesian网中的消去排序、三角化和treewidth、weighted treewidth、treecost三类树分解问题的若干性质以及相互间关系,在理论上进行系统阐述和严格证明；另一方面,针对现有求解方法缺点,从启发式、迭代局部搜索以及智能优化等角度进行研究,并首次将协同进化机制引入树分解问题,给出Bayesian网树分解问题的一些有效求解算法以及算法框架。研究工作主要内容如下：1.基于子集族评价函数及其稳定性的定义,对最优树分解与最优三角化、最优消去排序的关系进行严格、系统的论述,厘清三者问关系,用fmaxsize、fmaxweight、ftotalweight三种子集族评价函数定义treewidth、weighted treewidth、treecost树分解,为这三种树分解问题提供统一刻画方式。同时,基于评价函数,对Bayesian网树分解中的预处理等问题进行阐释。2.针对treecost问题,提出若干新的求解方法：（1）首先,对求解treecost问题的启发式和迭代搜索方法进行研究。针对现有启发式稳定性不强的缺点,提出可直接求解消去排序的启发式MinFillWeightProduct和MinLinearWeight Sum,同时提出可用于求解三角化的启发式MinLBWeightSum、MinLBFillWeightSum、MinLBFillWeightProduct;针对简单贪心方法虽然执行速度快、但求解质量不高的缺陷,提出迭代搜索方法IRT和多启发式搜索方法kHR,根据Bayesian网树分解的性质,给出时间复杂度比IRT低一个数量级的加速版本FAST-IRT,同时也对FAST-IRT与IRT的等价性进行证明。最后,通过实验对这些方法进行测试分析,在典型Bayesian网上的实验表明,与现有启发式方法相比,这些方法在整体性能上具有明显优势,非常适合在线求解。同时,这些方法也可以与如群智能等其他求解方法相结合,以获得更好的优化效果。（2）其次,针对现有求解treecost问题的智能优化方法存在的缺点,提出可用于求解treecost问题的两种蚁群方法。混合极大极小蚁群算法MMMAS-SA用伪随机比例规则来构造单个解,以加强全局搜索能力,并采取动态调节信息素下限阈值的方式,使蚁群能够在可行域内进行更多探索；同时,采用复合式模拟退火机制,以提高蚁群的局部搜索能力：MHC-ACS则能充分利用现有启发式优点,通过自适应筛选合适启发式、动态定量控制启发式作用、利用启发式增强局部搜索能力等手段,将启发式有效融入蚁群系统。在一些具有代表性的Bayesian网上进行测试表明, MMMAS-SA和MHC-ACS是解决treecost司题的有效方法,不仅求解质量高、速度快,而且稳定性强于其他方法。（3）本文还首次将协同进化机制应用于treecost问题求解。提出两个协同进化算法框架FGCC和VNGCC,给出了可用于这两种框架的多种变量分组方案。同时,为FGCC和’VNGCC框架构造了三种基本优化求解器DGHGA、MDPSO和DDE。DGHGA针对一般遗传算法中变异操作并未充分利用具体问题特点的缺点,将启发式引入遗传算法求解过程,使用复合启发式变异操作提高求解稳定性,同时,采用一种易于计算的准则判定群体多样性,度量算法停滞和收敛状态,避免群体进化中的早熟收敛现象；MDPSO以离散方式定义粒子位置和速度的运算,为提高粒子探索能力,采取改进变异操作,并且随机重置全局最好位置上的粒子,防止其停滞于局部极优；DDE是一种离散版本微分进化算法,用交换序列方法执行个体间差分运算,具有控制参数少、自组织性强的特点。实验表明,FGCC和VNGCC协同进化框架下的18种求解算法,均能有效求解treecost问题,从而为进一步利用协同进化机制的分布式、并行性特征求解树分解问题奠定了研究基础。3.针对现有方法在求解treewidth问题上的不足,本文提出一种离散版本的改进人工蜂群求解方法IDABC,将一般人工蜂群算法从连续论域移植到离散论域,修改蜂群组织结构,增加后备食物源和专职雇佣蜂、迭代搜索蜂、启发式搜索蜂、智能守望蜂等新的蜂种,进一步提高系统全局搜索和开发能力。在与最近提出的迭代搜索和智能优化方法对比测试中,IDABC在求解时间上远快于其他对比算法,而且求解结果也十分具有竞争力。Bayesian网最优树分解是Bayesian网相关研究中的重要方向,其中treewidth问题还是图论和计算理论中的一个关键问题。对于Bayesian网树分解,无论是理论刻画还是算法求解方面的研究由来已久,但目前解决方法尚不足够成熟和完善,距离实际应用要求尚有很大距离。本文从集合分解和评价函数的角度讨论树分解与消去排序、三角化的关系,抽象程度较高,具有很好的适用性,体现出一定理论意义。同时,本文在启发式、迭代搜索和群智能方法等方面展开算法研究工作,并首次利用协同进化构造有效求解treecost问题的算法框架,为Bayesian网最优树分解问题的在线和离线求解提供多种新的有效方法,具有较强实际应用价值。