A bivariate probabilistic model-building genetic algorithm for graph bipartitioning

ABSTRACT

We investigate a bi-variate probabilistic model-building GA for the graph bipartitioning problem.The graph bipartitioning problem is a grouping problem that requires some modi.cations to the standard construction of the dependency tree.We also increase the computational efficiency of the Bi-PMBGA by restricting the dependency tree to the edges of the graph to be partitioned.Experimental results indicate that the Bi-PMBGA performs signi .cantly better than the multi-start local search.Compared to a genetic local search algorithm the Bi-PMBGA performs slightly worse on some of the graphs considered here.

REFERENCES

• 1: Shumeet Baluja , Scott Davies, Using Optimal Dependency-Trees for Combinational Optimization, Proceedings of the Fourteenth International Conference on Machine Learning, p.30-38, July 08-12, 1997
• 2: Bosman, P.A.N. & de Jong, E. D. Learning Probabilistic Tree Grammars for Genetic Programming. Proceedings of Parallel Problem Solving from Nature - PPSN VIII, pp. 192--201, 2004. Springer-Verlag.
• 3: Peter A. N. Bosman , Dirk Thierens, Permutation Optimization by Iterated Estimation of Random Keys Marginal Product Factorizations, Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, p.331-340, September 07-11, 2002
• 4: Falkenauer, E. A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, Vol.2, pp. 5--30, 1996. Kluwer Academic Publishers.
• 5: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 6: David S. Johnson , Cecilia R. Aragon , Lyle A. McGeoch , Catherine Schevon, Optimization by simulated annealing: an experimental evaluation. Part I, graph partitioning, Operations Research, v.37 n.6, p.865-892, Nov–Dec. 1989 [doi>10.1287/opre.37.6.865]
• 7: Yong-Hyuk Kim , Byung-Ro Moon, Investigation of the Fitness Landscapes in Graph Bipartitioning: An Empirical Study, Journal of Heuristics, v.10 n.2, p.111-133, March 2004 [doi>10.1023/B:HEUR.0000026263.43711.44]
• 8: Anany V. Levitin, Introduction to the Design and Analysis of Algorithms (2nd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2006
• 9: Peter Merz , Bernd Freisleben, Fitness Landscapes, Memetic Algorithms, and Greedy Operators for Graph Bipartitioning, Evolutionary Computation, v.8 n.1, p.61-91, March 2000 [doi>10.1162/106365600568103]
• 10: Pelikan. M. & Müühlenbein, H. The Bivariate Marginal Distribution Algorithm. Proceedings of Advances in Soft Computing - Engineering Design and Manufacturing, pp. 521--535, 1999. Springer-Verlag.
• 11: Martin Pelikan , David E. Goldberg , Fernando G. Lobo, A Survey of Optimization by Building and Using Probabilistic Models, Computational Optimization and Applications, v.21 n.1, p.5-20, January 2002 [doi>10.1023/A:1013500812258]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Performance

Keywords:
probabilistic model-building EAs