一种求解子图同构问题的改进遗传算法

摘要/Abstract

摘要： 子图同构(Subgraph Isomorphism)技术在计算机视觉、人工智能以及生物化学工程等领域具有重要的应用。文章聚焦于子图同构问题的求解算法,提出了一种基于基因遗传算法的改进算法。结合子图同构的特点,针对遗传算法中的杂交过程和进化过程,改进了传统的子代生成算法,提出了一种新的适应度函数来评估子代的适应性。新算法可以指引搜索过程更快地收敛到最优解,并能够以更高的概率求得最优解。通过仿真实验表明,提出的改进算法相较于传统的算法能够更好地处理大规模子图,并取得更好的效果。

关键词: 适应度函数, 遗传算法, 杂交过程, 子图同构

Abstract: Subgraph isomorphism plays an important role in computer vision,artificial intelligence and bio-chemical engineering.This paper focused on the subgraph isomorphism (SI) problem and proposed a novel method based on the genetic algorithm to solve it.The sub-generation producing method is improved during the crossover and evolution process.Moreover,a new fitness function was presented to measure the fitness of the population.The new algorithm is more fast to get convergence and can find the optimal solutions with higher probability.Experiments show that the proposed improved algorithm outperforms other traditional methods by processing large graphs.

Key words: Crossover, Fitness function, Genetic algorithm, Subgraph isomorphism

中图分类号:

TP311

项英倬, 魏强, 游凌, 石浩. 一种求解子图同构问题的改进遗传算法[J]. 计算机科学, 2019, 46(6A): 98-101. https://doi.org/

XIANG Ying-zhuo, WEI Qiang, YOU Ling, SHI Hao. Improved Genetic Algorithm for Subgraph Isomorphism Problem[J]. Computer Science, 2019, 46(6A): 98-101. https://doi.org/

参考文献

[1]BROWN A D,THOMAS P R.Goal-oriented subgraph isomorphism technique for IC device recognition[J].IEE Proceedings I(Solid-State and Electron Devices),1988,135(6):141-150.
[2]GUHA A.Optimizing codes for concurrent fault detection in microprogrammed controllers[C]∥Proc.Int.Conf.Computer Design:VLSI in Computers and Processors(ICCD’87).1987:486-489.
[3]LANG S Y T,WONG A K C.A sensor model registration technique for mobile robot localization[C]∥Proceedings of the 1991 IEEE International Symposium on Intelligent Control.IEEE,1991:298-305.
[4]EPPSTEIN D.Subgraph isomorphism in planar graphs and related problems[M]∥Graph Algorithms And Applications I.2002:283-309.
[5]ULLMANN J R.An algorithm for subgraph isomorphism[J].Journal of the ACM(JACM),1976,23(1):31-42.
[6]BOMZE I M,BUDINICH M,PARDALOS P M,et al.The maximum clique problem[M]∥Handbook of Combinatorial Optimization.Springer,Boston,MA,1999:1-74.
[7]SAHNI S,GONZALEZ T.P-complete approximation problems[J].Journal of the ACM(JACM),1976,23(3):555-565.
[8]COOK S A.The complexity of theorem-proving procedures[C]∥ Proceedings of the Third Annual ACM Symposium on Theory of Computing.ACM,1971:151-158.
[9]SCHMIDT,DOUGLAS C,DRUFFEL L E.A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices[J].Journal of the ACM(JACM),1976,23(3):433-445.
[10]CORDELLA L P,FOGGIA P,SANSONE C,et al.A(sub) graph isomorphism algorithm for matching large graphs[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(10):1367-1372.
[11]MCKAY B D.Practical graph isomorphism[J].Congressus Numerantium,1981,30:45-87.
[12]MCKAY B D,PIPERNO A.Practical graph isomorphism,II[J].Journal of Symbolic Computation,2014,60:94-112.
[13]KIRKPATRICK S,GELATT C D,VECCHI M P.Optimization by simulated annealing[J].Science,1983,220(4598):671-680.
[14]FOGEL D B.An introduction to simulated evolutionary optimization[J].IEEE Transactions on Neural Networks,1994,5(1):3-14.
[15]ZHONG Q,WU Z,LIN L,et al.Computing resources assign-ment in rtds simulators with subgraph isomorphism based on genetic algorithm[C]∥2011 4th International Conference on Electric Utility Deregulation and Restructuring and Power Technologies(DRPT).IEEE,2011:1144-1149.
[16]CVETKOVIC＇ D M,DOOB M,SACHS H.Spectra of graphs:theory and application[M].Deutsher Verlag der Wissen-schaften,1980.
[17]GOLDBERG D E,LINGLE R.Alleles,loci,and the traveling salesman problem[C]∥Proceedings of an International Conference on Genetic Algorithms and Their Applications.Lawrence Erlbaum,Hillsdale,NJ,1985,154:154-159.
[18]GOLDBERG D E.Genetic algorithms in search,optimization,and machine learning ∥Genetic Algorithms in Search,Optimization,and Machine Learning.1989.
[19]CICIRELLO V A,SMITH S F.Modeling GA performance for control parameter optimization∥Proceedings of the 2nd Annual Conference on Genetic and Evolutionary Computation.Morgan Kaufmann Publishers Inc.,2000:235-242.
[20]刘荷花,崔超,陈晶.一种改进的遗传算法求解旅行商问题[J].北京理工大学学报,2013,33(4):390-393.
[21]朱学军,陈彤,薛量,等.多个体参与交叉的 Pareto 多目标遗传算法[J].电子学报,2001,29(1):106-109.
[22]MUHLENBEIN H.How genetic algorithms really work:I.mutation and hillclimbing[C]∥Proc.2nd Int.Conf.on Parallel Problem Solving from Nature,1992.Elsevier,1992.
[23]WHITLEY D.A genetic algorithm tutorial[J].Statistics and Computing,1994,4(2):65-85.
[24]梁宇宏,张欣.对遗传算法的轮盘赌选择方式的改进[J].信息技术,2009(12):127-129.
[25]GOLDBERG D E.A note on Boltzmann tournament selection for genetic algorithms and population-oriented simulated annealing[J].Complex Systems,1990,4(4):445-460.
[26]GOLDBERG D E,DEB K.A comparative analysis of selection schemes used in genetic algorithms[M]∥Foundations of Gene-tic Algorithms.Elsevier,1991:69-93.
[27]DEB K.An efficient constraint handling method for genetic algorithms[J].Computer methods in Applied Mechanics and Engineering,2000,186(2-4):311-338.
[28]FARAHANI M M,CHAHARSOUGHI S K.A genetic and iter-ative local search algorithm for solving subgraph isomorphism problem[C]∥2015 International Conference on Industrial Engineering and Operations Management(IEOM).IEEE,2015:1-6.

相关文章 15

[1]	杨浩雄, 高晶, 邵恩露. 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题 Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery 计算机科学, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005
[2]	沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[3]	吴善杰, 王新. 基于AGA-DBSCAN优化的RBF神经网络构造煤厚度预测方法 Prediction of Tectonic Coal Thickness Based on AGA-DBSCAN Optimized RBF Neural Networks 计算机科学, 2021, 48(7): 308-315. https://doi.org/10.11896/jsjkx.200800110
[4]	郑增乾, 王锟, 赵涛, 蒋维, 孟利民. 带宽和时延受限的流媒体服务器集群负载均衡机制 Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster 计算机科学, 2021, 48(6): 261-267. https://doi.org/10.11896/jsjkx.200400131
[5]	王金恒, 单志龙, 谭汉松, 王煜林. 基于遗传优化PNN神经网络的网络安全态势评估 Network Security Situation Assessment Based on Genetic Optimized PNN Neural Network 计算机科学, 2021, 48(6): 338-342. https://doi.org/10.11896/jsjkx.201200239
[6]	左剑凯, 吴杰宏, 陈嘉彤, 刘泽源, 李忠智. 异构无人机编队防御及评估策略研究 Study on Heterogeneous UAV Formation Defense and Evaluation Strategy 计算机科学, 2021, 48(2): 55-63. https://doi.org/10.11896/jsjkx.191100053
[7]	高帅, 夏良斌, 盛亮, 杜宏亮, 袁媛, 韩和同. 基于投影圆度和遗传算法的空间圆柱面拟合方法 Spatial Cylinder Fitting Based on Projection Roundness and Genetic Algorithm 计算机科学, 2021, 48(11A): 166-169. https://doi.org/10.11896/jsjkx.201100057
[8]	姚泽玮, 林嘉雯, 胡俊钦, 陈星. 基于PSO-GA的多边缘负载均衡方法 PSO-GA Based Approach to Multi-edge Load Balancing 计算机科学, 2021, 48(11A): 456-463. https://doi.org/10.11896/jsjkx.210100191
[9]	高基旭, 王珺. 一种基于遗传算法的多边缘协同计算卸载方案 Multi-edge Collaborative Computing Unloading Scheme Based on Genetic Algorithm 计算机科学, 2021, 48(1): 72-80. https://doi.org/10.11896/jsjkx.200800088
[10]	吉顺慧, 张鹏程. 基于支配关系的数据流测试用例生成方法 Test Case Generation Approach for Data Flow Based on Dominance Relations 计算机科学, 2020, 47(9): 40-46. https://doi.org/10.11896/jsjkx.200700021
[11]	董明刚, 黄宇扬, 敬超. 基于遗传实例和特征选择的K近邻训练集优化方法 K-Nearest Neighbor Classification Training Set Optimization Method Based on Genetic Instance and Feature Selection 计算机科学, 2020, 47(8): 178-184. https://doi.org/10.11896/jsjkx.190700089
[12]	梁正友, 何景琳, 孙宇. 一种用于微表情自动识别的三维卷积神经网络进化方法 Three-dimensional Convolutional Neural Network Evolution Method for Facial Micro-expression Auto-recognition 计算机科学, 2020, 47(8): 227-232. https://doi.org/10.11896/jsjkx.190700009
[13]	杨德成, 李凤岐, 王祎, 王胜法, 殷慧殊. 智能3D打印路径规划算法 Intelligent 3D Printing Path Planning Algorithm 计算机科学, 2020, 47(8): 267-271. https://doi.org/10.11896/jsjkx.190700184
[14]	冯炳超, 吴璟莉. 求解自行车共享系统静态再平衡问题的单亲遗传算法 Partheno-genetic Algorithm for Solving Static Rebalance Problem of Bicycle Sharing System 计算机科学, 2020, 47(6A): 114-118. https://doi.org/10.11896/JsJkx.190700120
[15]	姚敏. 求解柔性资源受限项目调度问题的多种群遗传算法 Multi-population Genetic Algorithm for Multi-skill Resource-constrained ProJect Scheduling Problem 计算机科学, 2020, 47(6A): 124-129. https://doi.org/10.11896/JsJkx.190900123

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed