Computer Science ›› 2019, Vol. 46 ›› Issue (6A): 98-101.

• Intelligent Computing • Previous Articles     Next Articles

Improved Genetic Algorithm for Subgraph Isomorphism Problem

XIANG Ying-zhuo1, WEI Qiang1, YOU Ling1, SHI Hao2   

  1. National Key Laboratory of Science and Technology on Blind Signal Processing,Chengdu 610041,China1;
    Department of Automation,University of Science and Technology of China,Hefei 230031,China2
  • Online:2019-06-14 Published:2019-07-02

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

CLC Number: 

  • TP311
[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.
[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.
[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.
[1] YANG Hao-xiong, GAO Jing, SHAO En-lu. Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery [J]. Computer Science, 2022, 49(6A): 191-198.
[2] LI Dan-dan, WU Yu-xiang, ZHU Cong-cong, LI Zhong-kang. Improved Sparrow Search Algorithm Based on A Variety of Improved Strategies [J]. Computer Science, 2022, 49(6A): 217-222.
[3] SHEN Biao, SHEN Li-wei, LI Yi. Dynamic Task Scheduling Method for Space Crowdsourcing [J]. Computer Science, 2022, 49(2): 231-240.
[4] WU Shan-jie, WANG Xin. Prediction of Tectonic Coal Thickness Based on AGA-DBSCAN Optimized RBF Neural Networks [J]. Computer Science, 2021, 48(7): 308-315.
[5] ZHENG Zeng-qian, WANG Kun, ZHAO Tao, JIANG Wei, MENG Li-min. Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster [J]. Computer Science, 2021, 48(6): 261-267.
[6] WANG Jin-heng, SHAN Zhi-long, TAN Han-song, WANG Yu-lin. Network Security Situation Assessment Based on Genetic Optimized PNN Neural Network [J]. Computer Science, 2021, 48(6): 338-342.
[7] ZUO Jian-kai, WU Jie-hong, CHEN Jia-tong, LIU Ze-yuan, LI Zhong-zhi. Study on Heterogeneous UAV Formation Defense and Evaluation Strategy [J]. Computer Science, 2021, 48(2): 55-63.
[8] YAO Ze-wei, LIU Jia-wen, HU Jun-qin, CHEN Xing. PSO-GA Based Approach to Multi-edge Load Balancing [J]. Computer Science, 2021, 48(11A): 456-463.
[9] GAO Shuai, XIA Liang-bin, SHENG Liang, DU Hong-liang, YUAN Yuan, HAN He-tong. Spatial Cylinder Fitting Based on Projection Roundness and Genetic Algorithm [J]. Computer Science, 2021, 48(11A): 166-169.
[10] GAO Ji-xu, WANG Jun. Multi-edge Collaborative Computing Unloading Scheme Based on Genetic Algorithm [J]. Computer Science, 2021, 48(1): 72-80.
[11] JI Shun-hui, ZHANG Peng-cheng. Test Case Generation Approach for Data Flow Based on Dominance Relations [J]. Computer Science, 2020, 47(9): 40-46.
[12] DONG Ming-gang, HUANG Yu-yang, JING Chao. K-Nearest Neighbor Classification Training Set Optimization Method Based on Genetic Instance and Feature Selection [J]. Computer Science, 2020, 47(8): 178-184.
[13] LIANG Zheng-you, HE Jing-lin, SUN Yu. Three-dimensional Convolutional Neural Network Evolution Method for Facial Micro-expression Auto-recognition [J]. Computer Science, 2020, 47(8): 227-232.
[14] YANG De-cheng, LI Feng-qi, WANG Yi, WANG Sheng-fa, YIN Hui-shu. Intelligent 3D Printing Path Planning Algorithm [J]. Computer Science, 2020, 47(8): 267-271.
[15] FENG Bing-chao and WU Jing-li. Partheno-genetic Algorithm for Solving Static Rebalance Problem of Bicycle Sharing System [J]. Computer Science, 2020, 47(6A): 114-118.
Full text



No Suggested Reading articles found!