【作者】 林凌雪； 钟庆；

【Author】 Lingxue Lin;Qing Zhong;Scholl of Electric Power,South China University of Technology;

【机构】 华南理工大学电力学院；

【摘要】 子图同构问题是非线性复杂性完备问题之一,可用于模式匹配的判定和实现。通过定义增广关联矩阵,将增广关联矩阵中元素1的个数为目标函数,当目标函数达到最大时,子图同构得到验证。基于遗传算法的子图同构方法,能够有效通过图形节点编码的方式对子图同构问题进行求解。设定图形的顶点排列编码向量为种群的样本。通过选择、交叉和变异算法,对种群进行操作,生成下一代种群。遗传算法搜索出问题的解,即可得到子图同构的验证和实现方案。该算法在电力系统的实时数字仿真中得到应用,并验证得出的方案可行。更多还原

【Abstract】 Subgraph isomorphism is one of NP-complete problems. The method can be used in the pattern reconginiton and realization. The expended incidence matrix are defined and the number of ones in the matrix is considered as the object function in the solution. If the object function reach the maximum, the subgraph isomorphism has been testified. The method base on genetic algorithm is a effective algorithm to solve the problem with the nth-binary coding. The individals in the population are given as the permutation of the vertices in the graph. By selection, crossover and mutation in the genetic algorithm, the next population can be generated. The iteration of genetic algorithm will search the optimal solution for the problem. The solution can testify the subgraph isomorphism and give the proposal. The computational resource assignment in the real time digital simulation of power system are solved by the subgraph isomorphism. The proposal by the method are feasible during the simulation.更多还原