Advertisement

Genetic Algorithms as Multi-Coordinators in Large-Scale Optimization

  • Ioannis T. Christou
  • Wayne Martin
  • Robert R. Meyer
Chapter
Part of the The IMA Volumes in Mathematics and its Applications book series (IMA, volume 111)

Abstract

We present high-level, decomposition-based algorithms for large-scale block-angular optimization problems containing integer variables, and demonstrate their effectiveness in the solution of large-scale graph partitioning problems. These algorithms combine the subproblem-coordination paradigm (and lower bounds) of price-directive decomposition methods with knapsack and genetic approaches to the utilization of “building blocks” of partial solutions. Even for graph partitioning problems requiring billions of variables in a standard 0–1 formulation, this approach produces high-quality solutions (as measured by deviations from an easily computed lower bound), and substantially outperforms widely-used graph partitioning techniques based on heuristics and spectral methods.

Keywords

Genetic Algorithm Optimal Shape Knapsack Problem Rectangular Domain Quadratic Assignment Problem 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. [CM96a]
    I.T. Christou and R.R. Meyer. Optimal and asymptotically optimal equi-partition of rectangular domains via stripe decomposition. In H. Fischer, B. Riedmuller, and S. Schaffier, editors, Applied Mathematics and Parallel Computing - Festschrift for Klaus Ritter, pages 77–96. Physica-Verlag, 1996.Google Scholar
  2. [CM96b]
    I.T. Christou and R.R. Meyer. Optimal equi-partition of rectangular domains for parallel computation. Journal of Global Optimization, 8:15–34, January 1996.MathSciNetzbMATHCrossRefGoogle Scholar
  3. [Dav97]
    L.D. Davis. Telecommunication network optimization with genetic algorithms: A decade of progress. In Evolutionary Algorithms. Springer-Verlag, 1997. To appear.Google Scholar
  4. [D. Levine95]
    D. Levine. User’s Guide to the PGAPack Parallel Genetic Algorithm Library Version 0.2. Argonne National Laboratory, June 1995.Google Scholar
  5. [Fal94]
    Emanuel Falkenauer. A new representation and operations for genetic algorithms applied to grouping problems. Evolutionary Computation, 2(2):123–144, 1994.CrossRefGoogle Scholar
  6. [GBD+94]
    A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, and V. Sunderam. PVM 3 User’s Guide and Reference Manual. Oak Ridge National Laboratory, 1994.Google Scholar
  7. [GMT95]
    J.R. Gilbert, G.L. Miller, and S.H. Teng. Geometric mesh partition-ing: Implementation and experiments. In Proceedings of the 9th International Symposium on Parallel Processing,pages 418–427, 1995.Google Scholar
  8. [Gre95]
    J.J. Grefenstette. Virtual genetic algorithms: First results. Technical Report AIC-95–013, Navy Center for Applied Research in Al, 1995.Google Scholar
  9. [Har94]
    W.E. Hart. Adaptive global optimization with local search. PhD the-sis, University of California, San Diego, 1994.Google Scholar
  10. [HL95]
    B. Hendrickson and R. Leland. The Chaco User’s Guide Version 2.0. Sandia National Laboratories, July 1995.Google Scholar
  11. [KK95]
    G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. Technical Report 95–064, Department of Computer Science, University of Minnesota, 1995.Google Scholar
  12. [KL70]
    B.W. Kernighan and S. Lin. An effective heuristic procedure for partitioning graphs. Bell Systems Tech. Journal, pages 291–308, February 1970.Google Scholar
  13. [Mar96]
    W. Martin. Fast equi-partitioning of rectangular domains[ using stripe decomposition. Discrete Applied Mathematics, 82 (1998) 193–207.MathSciNetzbMATHCrossRefGoogle Scholar
  14. [MSB91]
    H. Muhlenbein, M. Schomisch, and J. Born. The parallel genetic algorithm as function optimizer. In R. Belew and L. Booker, editors, Proceedings of the Fourth Intl. Conference on Genetic Algorithms, pages 45–52. Morgan Kaufmann Publishers, Los Altos, CA, 1991.Google Scholar
  15. [PJ94]
    M. A. Potter and K. De Jong. A cooperative coevolu-tionary approach to function optimization. In Proceedings of the Third International Conference on Parallel Problem Solving from Nature. Springer-Verlag, 1994.Google Scholar
  16. [PRW93]
    P.M. Pardalos, F. Rendl, and H. Wolkowicz. The quadratic assign-ment problem: A survey and recent developments. In P.M. Pardalos and H. Wolkowicz, editors, Quadratic Assignment and Related Problems. American Mathematical Society, 1993.Google Scholar
  17. [Sch89]
    R.J. Schalkoff. Digital Image Processing and Computer Vision. John Wiley & Sons, 1989.Google Scholar
  18. [Str89]
    J. Strikwerda. Finite Difference Schemes and Partial Differential Equations. Wadsworth & Brooks, 1989.Google Scholar
  19. [YM92]
    J. Yackel and R.R. Meyer. Optimal tilings for parallel database de-sign. In P.M. Pardalos, editor, Advances in Optimization and Parallel Computing, pages 293–309. North - Holland, 1992.Google Scholar

Copyright information

© Springer Science+Business Media New York 1999

Authors and Affiliations

  • Ioannis T. Christou
    • 1
  • Wayne Martin
    • 1
  • Robert R. Meyer
    • 1
  1. 1.Computer Sciences DepartmentUniversity of WisconsinMadisonUSA

Personalised recommendations