Geometric crossover for multiway graph partitioning

ABSTRACT

Geometric crossover is a representation-independent generalization of the traditional crossover defined using the distance of the solution space. Using a distance tailored to the problem at hand, the formal definition of geometric crossover allows to design new problem-specific crossovers that embed problem-knowledge in the search. The standard encoding for multiway graph partitioning is highly redundant: each solution has a number of representations, one for each way of labeling the represented partition. Traditional crossover does not perform well on redundant encodings. We propose a new geometric crossover for graph partitioning based on a labeling-independent distance that filters the redundancy of the encoding. A correlation analysis of the fitness landscape based on this distance shows that it is well suited to graph partitioning. Our new genetic algorithm outperforms existing ones.

REFERENCES

• 1: Roberto Battiti , Alan Albert Bertossi, Greedy, Prohibition, and Reactive Heuristics for Graph Partitioning, IEEE Transactions on Computers, v.48 n.4, p.361-385, April 1999 [doi>10.1109/12.762522 ]
• 2: Boese, K. D., Kahng, A. B., and Muddu, S. A new adaptive multi-start technique for combinatorial global optimizations. Operations Research Letters 15 (1994), 101--113.
• 3: Thang Nguyen Bui , Byung Ro Moon, Genetic Algorithm and Graph Partitioning, IEEE Transactions on Computers, v.45 n.7, p.841-855, July 1996 [doi>10.1109/12.508322 ]
• 4: Choi, S. S., and Moon, B. R. Normalization in genetic algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (2003), pp. 862--873.
• 5: Jason Cong , Sung Kyu Lim, Multiway partitioning with pairwise movement, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.512-516, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289079]
• 6: Jason Cong , Sung Kyu Lim , Chang Wu, Performance driven multi-level and multiway partitioning with retiming, Proceedings of the 37th conference on Design automation, p.274-279, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337418]
• 7: 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
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: Hu, T. C., and Kuh, E. S. VLSI Curcuit Layout Theory and Design. IEEE Press, New York, 1985.
• 10: 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
• 11: Jones, T. Evolutionary Algorithms, Fitness Landscapes and Search. PhD thesis, University of New Mexico, 1995.
• 12: Kang, S. J., and Moon, B. R. A hybrid genetic algorithm for multiway graph partitioning. In Proceedings of the Genetic and Evolutionary Computation Conference (2000), pp. 159--166.
• 13: George Karypis , Vipin Kumar, Multilevel k-way partitioning scheme for irregular graphs, Journal of Parallel and Distributed Computing, v.48 n.1, p.96-129, Jan. 1998 [doi>10.1006/jpdc.1997.1404 ]
• 14: Kernighan, B., and Lin, S. An efficient heuristic procedure for partitioning graphs. Bell Systems Technical Journal 49 (Feb. 1970), 291--307.
• 15: Kim, J. P., and Moon, B. R. A hybrid genetic search for multi-way graph partitioning based on direct partitioning. In Proceedings of the Genetic and Evolutionary Computation Conference (2001), pp. 408--415.
• 16: Yong-Hyuk Kim , Byung-Ro Moon, Lock-Gain Based Graph Partitioning, Journal of Heuristics, v.10 n.1, p.37-57, January 2004 [doi>10.1023/B:HEUR.0000019985.94952.eb]
• 17: Yong-Hyuk Kim , Byung-Ro Moon, New topologies for genetic search space, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068232]
• 18: Kuhn, H. W. The Hungarian method for the assignment problem. Naval Res. Logist. Quart. 2 (1955), 83--97.
• 19: Laszewski, G. Intelligent structural operators for the k-way graph partitioning problem. In Proceedings of the Fourth International Conference on Genetic Algorithms (July 1991), pp. 45--52.
• 20: 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]
• 21: Moraglio, A., and Poli, R. Topological interpretation of crossover. In Proceedings of the Genetic and Evolutionary Computation Conference (2004), pp. 1377--1388.
• 22: Moraglio, A., and Poli, R. Geometric crossover for the permutation representation. Technical Report CSM-429, University of Essex (2005).
• 23: Alberto Moraglio , Riccardo Poli, Topological crossover for the permutation representation, Proceedings of the 2005 workshops on Genetic and evolutionary computation, June 25-26, 2005, Washington, D.C. [doi>10.1145/1102256.1102330]
• 24: Pardalos, P. M., and Resende, M. G. C., Eds. Handbook of Applied Optimization. Oxford University Press, 2002.
• 25: L. A. Sanchis, Multiple-Way Network Partitioning, IEEE Transactions on Computers, v.38 n.1, p.62-81, January 1989 [doi>10.1109/12.8730 ]
• 26: Weinberger, E. D. Correlated and uncorrelated fitness landscapes and how to tell the difference. Biological Cybernetics 63 (1990), 325--336.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Theory

Keywords:
geometric crossover, labeling-independent distance, multiway graph partitioning