曾杰鹏,廖 芹,谷志元
(1.华南理工大学 理学院,广东 广州510640;2.广州铁路职业技术学院 应用数学教研室,广东 广州510430)
贝叶斯网络结构学习是贝叶斯网络研究的一个重要方向,尤其在没有先验网络结构的情况下,结构学习算法在建网上的作用尤为突出。贝叶斯结构学习主要有基于评分的启发式算法以及基于互信息等规则[1]的建网方法。其中,基于评分的启发式算法在当前的研究中最为活跃,主要包括爬山算法[2],蚁群算法[3],遗传算法[4],模拟退火算法[5]等。同时,通过对上述算法的优化组合,也生成了各种有效的组合算法,如遗传算法与模拟退火算法的组合算法[6],遗传算法与蚁群算法的组合算法[7]等。
遗传算法搜索范围大,寻优效率高,在贝叶斯网络结构学习中具有普遍的应用。然而由于传统的个体编码主要采用贝叶斯网络的邻接矩阵,导致种群初始化的过程中,可行解的生成概率较低,需要重复生成新个体,以保证其通过无环性检验[8]。其次,在种群的进化过程中,个体的可行性可能受到破坏。因此,对于新生成的个体,往往又需要重新进行无环性检验,进而将非法结构修正为有向无环图[9],或者为非法结构设置较低的适应度,从而降低了寻优的效率[10-11]。另外,之前的研究在计算新个体的结构得分时,往往需要计算整个新贝叶斯网络的得分。然而事实上,在遗传进化过程中,贝叶斯网络通常存在局部不变性。因此可以结合结构得分的可分解性与结构局部稳定性[12],从而进一步优化结构学习的效率。……