Genetic approaches for graph partitioning: a survey

ABSTRACT

The graph partitioning problem occurs in numerous applications such as circuit placement, matrix factorization, load balancing, and community detection. For this problem, genetic algorithm is a representative approach with competitive performance with many related papers being published. Although there are a number of surveys on graph partitioning, none of them deals with genetic algorithms in much detail. In this survey, a number of problem-specific issues in applying genetic algorithms to the graph partitioning problem are discussed; the issues include encoding, crossover, normalization, and balancing.

References

1. C. J. Alpert and A. B. Kahng. Recent directions in netlist partitioning: A survey. Integration, the VLSI Journal, 19(1--2):1--81, 1995.
2. M. Armbruster, M. Fugenschuh, C. Helmberg, N. Jetchev, and A. Martin. LP-based genetic algorithm for the minimum graph bisection problem. In Operations Research Proceedings, pages 315--320, 2005.
3. M. Armbruster, M. Fugenschuh, C. Helmberg, N. Jetchev, and A. Martin. Hybrid genetic algorithm within branch-and-cut for the minimum graph bisection problem. In Evolutionary Computation in Combinatorial Optimization, pages 1--12, 2006.
4. M. Barake, P. Chardaire, and G. P. McKeown. The PROBE metaheuristic and its application to the multiconstraint knapsack problem. In Metaheuristics: computer decision-making, pages 19--36. Kluwer Academic Publishers, 2004.
5. R. Battiti and A. Bertossi. Greedy, prohibition, and reactive heuristics for graph partitioning. IEEE Transactions on Computers, 48(4):361--385, 1999.
6. M. J. Berger and S. H. Bokhari. A partitioning strategy for nonuniform problems on multiprocessors. IEEE Transactions on Computers, 36(5):570--580, 1987.
7. K. D. Boese, A. B. Kahng, and S. Muddu. A new adaptive multi-start technique for combinatorial global optimizations. Operations Research Letters, 15:101--113, 1994.
8. M. Boulif. Genetic algorithm encoding representations for graph partitioning problems. In International Conference on Machine and Web Intelligence, pages 288 --291, 2010.
9. M. Boulif and K. Atif. A new branch-&-bound-enhanced genetic algorithm for the manufacturing cell formation problem. Computers & Operations Research, 33(8):2219 -- 2245, 2006.
10. T. N. Bui and C. Jones. Finding good approximate vertex and edge partitions is NP-hard. Information Processing Letters, 42:153--159, 1992.
11. T. N. Bui and C. Jones. A heuristic for reducing fill-in in sparse matrix factorization. In Sixth SIAM Conference on Parallel Processing for Scientific Computing, pages 445--452, 1993.
12. T. N. Bui and B.-R. Moon. Hyperplane synthesis for genetic algorithms. In Fifth International Conference on Genetic Algorithms, pages 102--109, 1993.
13. T. N. Bui and B.-R. Moon. A genetic algorithm for a special class of the quadratic assignment problem. The Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 16:99--116, 1994.
14. T. N. Bui and B.-R. Moon. On multi-dimensional encoding/crossover. In Sixth International Conference on Genetic Algorithms, pages 49--56, 1995.
15. T. N. Bui and B.-R. Moon. Genetic algorithm and graph partitioning. IEEE Transactions on Computers, 45(7):841--855, 1996.
16. T. N. Bui and L. C. Strite. An ant system algorithm for graph bisection. In Genetic and Evolutionary Computation Conference, pages 43--51, 2002.
17. P. Chardaire, M. Barake, and G. P. McKeown. A PROBE-based heuristic for graph partitioning. IEEE Transactions on Computers, 56(12):1707--1720, 2007.
18. S.-S. Choi, Y.-K. Kwon, and B.-R. Moon. Properties of symmetric fitness functions. IEEE Transactions on Evolutionary Computation, 11(6):743--757, 2007.
19. S.-S. Choi and B.-R. Moon. Normalization in genetic algorithms. In Genetic and Evolutionary Computation Conference, pages 862--873, 2003.
20. S.-S. Choi and B.-R. Moon. Normalization for genetic algorithms with nonsynonymously redundant encodings. IEEE Transactions on Evolutionary Computation, 12(5):604--616, 2008.
21. A. Cincotti, V. Cutello, and M. Pavone. Graph partitioning using genetic algorithms with ODPX. In IEEE Congress on Evolutionary Computation, pages 402--406, 2002.
22. J. P. Cohoon and W. Paris. Genetic placement. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 6(6):956--964, 1987.
23. R. Collins and D. Jefferson. Selection in massively parallel genetic algorithms. In Fourth International Conference on Genetic Algorithms, pages 249--256, 1991.
24. W. Donath and A. Hoffman. Lower bounds for the partitioning of graphs. IBM Journal of Research and Development, 17:420--425, 1973.
25. A. Dunlop and B. Kernighan. A procedure for placement of standard-cell VLSI circuits. IEEE Transactions on Computer-Aided Design, CAD-4(1):92--98, 1985.
26. S. Dutt and W. Deng. A probability-based approach to VLSI circuit partitioning. In Design Automation Conference, pages 100--105, 1996.
27. J. Elsner. Graph partitioning - a survey. Technische Universität Chemnitz, 1997.
28. M. Farshbaf and M.-R. Feizi-Derakhshi. Multi-objective optimization of graph partitioning using genetic algorithms. In Proceedings of the Third International Conference on Advanced Engineering Computing and Applications in Sciences, pages 1--6, 2009.
29. C. Fiduccia and R. Mattheyses. A linear time heuristics for improving network partitions. In 19th ACM/IEEE Design Automation Conference, pages 175--181, 1982.
30. P. O. Fjallström. Algorithms for graph partitioning: A survey. Linköping Electronic Atricles in Computer and Information Science, 3(10), 1998.
31. L. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.
32. M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete problems. In Sixth Annual ACM Symposium on Theory of Computing, pages 47--63, 1974.
33. B. Hendrickson and R. W. Leland. The Chaco user's guide, version 2.0. Technical Report SAND95--2344, Sandia National Laboratories, Albuquerque, 1995. Open-source software distributed at http://www.cs.sandia.gov/bahendr/chaco.html.
34. C. Höhn and C. Reeves. Graph partitioning using genetic algorithms. In Second International Conference on Massively Parallel Computing Systems, pages 27--43, 1996.
35. I. Hwang, Y.-H. Kim, and B.-R. Moon. Multi-attractor gene reordering for graph bisection. In Genetic and Evolutionary Computation Conference, pages 1209--1216, 2006.
36. H. Inayoshi and B. Manderick. The weighted graph bi-partitioning problem: A look at GA performance. In The Third Conference on Parallel Problem Solving from Nature, pages 617--625, 1994.
37. D. S. Johnson, C. Aragon, L. McGeoch, and C. Schevon. Optimization by simulated annealing: An experimental evaluation; Part 1, graph partitioning. Operations Research, 37:865--892, 1989.
38. D. R. Jones and M. A. Beltramo. Solving partitioning problems with genetic algorithms. In Fourth International Conference on Genetic Algorithms, pages 442--449, 1991.
39. A. B. Kahng and B.-R. Moon. Toward more powerful recombinations. In Sixth International Conference on Genetic Algorithms, pages 96--103, 1995.
40. S.-J. Kang and B.-R. Moon. A hybrid genetic algorithm for multiway graph partitioning. In Genetic and Evolutionary Computation Conference, pages 159--166, 2000.
41. G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20(1):359--392, 1998.
42. G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 48(1):96--129, 1998.
43. B. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell Systems Technical Journal, 49:291--307, 1970.
44. J.-P. Kim and B.-R. Moon. A hybrid genetic search for multi-way graph partitioning based on direct partitioning. In Genetic and Evolutionary Computation Conference, pages 408--415, 2001.
45. Y.-H. Kim and B.-R. Moon. Investigation of the fitness landscapes in graph bipartitioning: An empirical study. Journal of Heuristics, 10(2):111--133, 2004.
46. Y.-H. Kim and B.-R. Moon. Lock gain based graph partitioning. Journal of Heuristics, 10(1):37--57, 2004.
47. B. Krishnamurthy. An improved min-cut algorithm for partitioning VLSI networks. IEEE Transactions on Computers, C-33:438--446, 1984.
48. S. Küçükpetek, F. Polat, and O Ouguztüzün. Multilevel graph partitioning: an evolutionary approach. Journal of the Operational Research Society, 56(5):549--562, 2005.
49. H. W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2:83--97, 1955.
50. V. Kumar, A. Grama, A. Gupta, and G. Karypis. Introduction to Parallel Computing. The Benjamin/Cummings Publishing Company, Inc., 1994.
51. G. Laszewski. Intelligent structural operators for the k-way graph partitioning problem. In Fourth International Conference on Genetic Algorithms, pages 45--52, 1991.
52. G. Laszewski and H. Mühlenbein. Partitioning a graph with a parallel genetic algorithm. In First Workshop on Parallel Problem Solving from Nature, pages 165--169, 1991.
53. F. T. Leighton and S. Rao. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In 29th Symposium on Foundations of Computer Science, pages 422--431, 1988.
54. S. Lin and X. Cheng. BC-GA: A graph partitioning algorithm for parallel simulation of internet applications. In 16th Euromicro Conference on Parallel, Distributed and Network-Based Processing, pages 358--365, 2008.
55. H. S. Maini, K. G. Mehrotra, C. K. Mohan, and S. Ranka. Genetic algorithms for graph partitioning and incremental graph partitioning. In International Conference on Supercomputing, pages 449--457, 1994.
56. J. G. Martin. Subproblem optimization by gene correlation with singular value decomposition. In Genetic and Evolutionary Computation Conference, pages 1507--1514, 2005.
57. J. G. Martin. Spectral techniques for graph bisection in genetic algorithms. In Genetic and Evolutionary Computation Conference, pages 1249--1256, 2006.
58. P. Merz and B. Freisleben. Fitness landscapes, memetic algorithms, and greedy operators for graph bipartitioning. Evolutionary Computation, 8(1):61--91, 2000.
59. A. Moraglio, Y.-H. Kim, Y. Yoon, and B.-R. Moon. Geometric crossovers for multiway graph partitioning. Evolutionary Computation, 15(4):445--474, 2007.
60. A. Moraglio, Y.-H. Kim, Y. Yoon, and B.-R. Moon. Geometric crossovers for multiway graph partitioning. Theory and Principled Methods for the Design of Metaheuristics, 2011. (to appear).
61. H. Mühlenbein. Parallel genetic algorithm in combinatorial optimization. In O. Balci, R. Sharda, and S. Zenios, editors, Computer Science and Operations Research, pages 441--456. Pergamon Press, 1992.
62. H. Mühlenbein and T. Mahnig. Evolutionary optimization and the estimation of search distributions with applications to graph bipartitioning. International Journal of Approximate Reasoning, 31(3):157--192, 2002.
63. M. Pelikan, D. E. Goldberg, and K. Sastry. Bayesian optimization algorithm, decision graphs, and Occam's razor. IlliGAL Report No. 2000020, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, 2000.
64. H. Pirkul and E. Rolland. New heuristic solution procedures for the uniform graph partitioning problem: extensions and evaluation. Computers and Operations Research, 21(8):895--907, 1994.
65. A. Pothen. Graph partitioning algorithms with applications to scientific computing. In D. E. Keyes, A. H. Sameh, and V. Venkatakrishnan, editors, Parallel Numerical Algorithms, pages 323--368. Kluwer Academic Press, 1997.
66. J. M. Pujol, V. Erramilli, and P. Rodriguez. Divide and conquer: Partitioning online social networks. CoRR, abs/0905.4918, 2009.
67. N. J. Radcliffe. Forma analysis and random respectful recombination. In International Conference on Genetic Algorithms, pages 222--229, 1991.
68. E. Rolland, H. Pirkul, and F. Glover. Tabu search for graph partitioning. Annals of Operations Research, 63(2):209--232, 1996.
69. F. Rothlauf and D. E. Goldberg. Redundant representations in evolutionary computation. Evolutionary Computation, 11(4):381--415, 2003.
70. Y. G. Saab. An effective multilevel algorithm for bisecting graphs and hypergraphs. IEEE Transactions on Computers, 53(6):641--652, 2004.
71. Y. G. Saab and V. Rao. Stochastic evolution: a fast effective heuristic for some genetic layout problems. In 27th ACM/IEEE Design Automation Conference, pages 26--31, 1990.
72. L. A. Sanchis. Multiple-way network partitioing. IEEE Transactions on Computers, 38(1):62--81, 1989.
73. J. Schwarz and J. Oucenáusek. Experimental study: hypergraph partitioning based on the simple and advanced genetic algorithm BMDA and BOA. In 5th International Conference of Soft Computing, pages 124--130, 1999.
74. A. J. Soper, C. Walshaw, and M. Cross. A combined evolutionary search and multilevel optimisation approach to graph-partitioning. Journal of Global Optimization, 29(2):225--241, 2004.
75. A. G. Steenbeek, E. Marchiori, and A. E. Eiben. Finding balanced graph bi-partitions using a hybrid genetic algorithm. In IEEE International Conference on Evolutionary Computation, pages 90--95, 1998.
76. S. H. Strogatz. Exploring complex networks. Nature, 410:268--276, 2001.
77. E.-G. Talbi and P. Bessière. A parallel genetic algorithm for the graph partitioning problem. In Fifth International Conference on Supercomputing, pages 312--320, 1991.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

  • Mathematical analysis

    • Mathematical optimization

• Theory of computation

  • Design and analysis of algorithms

    • Mathematical optimization