demonstration

A bivariate probabilistic model-building genetic algorithm for graph bipartitioning

Author:

Dirk ThierensAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference companion on Genetic and evolutionary computation

Pages 2089 - 2092

https://doi.org/10.1145/1388969.1389027

Published: 12 July 2008 Publication History

Get Access

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]

Baluja, S. & Davies, S. Using optimal dependency-trees for combinatorial optimization: Learning the structure of the search space. Proceedings of the 14th International Conference on Machine Learning, pp. 30--38, 1997. Morgan Kaufmann.

Digital Library

Google Scholar

[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.

Google Scholar

[3]

Bosman, P.A.N. & and Thierens, D. Permutation Optimization by Iterated Estimation of Random Keys Marginal Product Factorizations. Proceedings of Parallel Problem Solving From Nature - PPSN VII, pp. 331--340, 2002. Springer-Verlag.

Digital Library

Google Scholar

[4]

Falkenauer, E. A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, Vol.2, pp. 5--30, 1996. Kluwer Academic Publishers.

Crossref

Google Scholar

[5]

Fiduccia, C.M. & Mattheyses, R.M. A Linear-Time Heuristic for Improving Network Partitions. Proceedings of the 19th Conference on Design Automation, pp. 175--181, 1982. IEEE Press.

Digital Library

Google Scholar

[6]

Johnson, D.S. & Aragon, C.R. & McGeoch, L.A. & Schevon, C. Optimization by simulated annealing: an experimental evaluation, part I (graph partitioning). Operations Research 37, pp. 865--892, 1989.

Digital Library

Google Scholar

[7]

Kim, Y.K. & Moon, B.R. Investigation of the Fitness Landscapes in Graph Bipartitioning: An Empirical Study. Journal of Heuristics, Vol. 10, Nr. 2, pp. 111--133, 2004. Kluwer Academic Publishers.

Digital Library

Google Scholar

[8]

Levitin, A. The Design and Analysis of Algorithms. 2nd edition, 2007, Pearson.

Digital Library

Google Scholar

[9]

Merz, P. & Freisleben, B. Fitness Landscapes, Memetic Algorithms, and Greedy Operators for Graph Bipartitioning. Journal of Evolutionary Computation, Vol. 8, Nr. 1, pp. 61--91, 2000. MIT Press.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[11]

Pelikan, M. & Goldberg, D.E. & Lobo, F. A survey of optimization by building and using probabilistic models. Computational Optimization and Applications, Vol. 21, Nr. 1, pp.5--20, 2002. Kluwer.

Digital Library

Google Scholar

Cited By

View all

Lobo FLima CPelikan MBranke J(2010)Towards automated selection of estimation of distribution algorithmsProceedings of the 12th annual conference companion on Genetic and evolutionary computation10.1145/1830761.1830831(1945-1952)Online publication date: 7-Jul-2010
https://dl.acm.org/doi/10.1145/1830761.1830831

Index Terms

A bivariate probabilistic model-building genetic algorithm for graph bipartitioning
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
      1. Heuristic function construction
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

Probabilistic model-building genetic algorithms
GECCO '08: Proceedings of the 10th annual conference companion on Genetic and evolutionary computation

Probabilistic model-building algorithms (PMBGAs) replace traditional variation of genetic and evolutionary algorithms by (1) building a probabilistic model of promising solutions and (2) sampling the built model to generate new candidate solutions. ...
Probabilistic model-building genetic algorithms
GECCO '10: Proceedings of the 12th annual conference companion on Genetic and evolutionary computation

Probabilistic model-building algorithms (PMBGAs) replace traditional variation of genetic and evolutionary algorithms by (1) building a probabilistic model of promising solutions and (2) sampling the built model to generate new candidate solutions. ...
Probabilistic model-building genetic algorithms
GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation

Probabilistic model-building genetic algorithms (PMBGAs), also known as estimation of distribution algorithms (EDAs) and iterated density-estimation algorithms (IDEAs), guide the search for the optimum by building and sampling explicit probabilistic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '08: Proceedings of the 10th annual conference companion on Genetic and evolutionary computation

July 2008

1182 pages

ISBN:9781605581316

DOI:10.1145/1388969

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

probabilistic model-building EAs

Qualifiers

Demonstration

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
164
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lobo FLima CPelikan MBranke J(2010)Towards automated selection of estimation of distribution algorithmsProceedings of the 12th annual conference companion on Genetic and evolutionary computation10.1145/1830761.1830831(1945-1952)Online publication date: 7-Jul-2010
https://dl.acm.org/doi/10.1145/1830761.1830831

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Probabilistic model-building genetic algorithms

Probabilistic model-building genetic algorithms

Probabilistic model-building genetic algorithms