基于顶点冲突学习的最大公共子图算法

Maximum common induced subgraph algorithm based on vertex conflict learning

针对最大公共子图(MCS)的传统分支策略依赖于图的静态属性,缺少学习历史搜索信息的问题,提出了基于顶点冲突学习的分支策略。首先,把上界的减少值作为分支点完成匹配动作的奖励;其次,由于当最优解被更新时,得到的最优解是分支点不断推理产生的结果,因此给予在完整的搜索路径上的分支点适当的奖励,从而强化这些顶点对搜索的积极作用;最后,设计了匹配动作的价值函数,并选择具有最大累计奖励的顶点作为新的分支点。在McSplit算法基础上,提出了糅合新分支策略的McSplitRLR算法。实验结果表明,除去均可以被所有对比算法在10 s之内解决的简单算例,在相同机器和求解限制时间条件下,相较当前先进的算法McSplit、McSplitSBS,McSplitRLR分别多解决了109、33个困难算例,求解率分别提高了5.6%、1.6%。

The traditional branching strategies of Maximum Common induced Subgraph(MCS)problem rely on the static properties of graphs and lack learning information about historical searches.In order to solve these problems,a branching strategy based on vertex conflict learning was proposed.Firstly,the reduction value of the upper bound was used as the reward to the branch node for completing a matching action.Secondly,when the optimal solution was updated,the optimal solution obtained actually was the result of continuous inference of the branch nodes.Therefore,the appropriate rewards were given to the branch nodes on the complete search path to strengthen the positive effect of these vertices on search.Finally,the value function of matching action was designed,and the vertices with the maximum cumulative rewards would be selected as new branch nodes.On the basis of Maximum common induced subgraph Split(McSplit)algorithm,an improved McSplit Reinforcement Learning and Routing(McSplitRLR)algorithm combined with the new branching strategy was completed.Experimental results show that,with the same computer and solution time limit,excluding the simple instances solved by all comparison algorithms within 10 seconds,compared to the state-of-the-art algorithms of McSplit and McSplit Solution-Biased Search(McSplitSBS),McSplitRLR solves 109 and 33 more hard instances respectively,and the solution rate increases by 5.6%and 1.6%respectively.