Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The graph partitioning problem has numerous applications in various scientific fields. It usually involves the effective partitioning of a graph into a number of disjoint sub-graphs/zones, and hence becomes a combinatorial optimization problem whose worst case complexity is NP-complete. The inadequacies of exact methods, like linear and integer programming approaches, to handle large-size instances of the combinatorial problems have motivated heuristic techniques to these problems. In the present work, a multi-objective evolutionary algorithm (MOEA), a kind of heuristic techniques, is developed for partitioning a graph under multiple objectives and constraints. The developed MOEA, which is a modified form of NSGA-II, is applied to four randomly generated graphs for partitioning them by optimizing three common objectives under five general constraints. The applications show that the MOEA is successful, in most of the cases, in achieving the expected results by partitioning a graph into a variable number of zones.

REFERENCES

• 1: R. K. Ahuja, A. Kumar, K. C. Jha, and J. B. Orlin. Exact and heuristic algorithms for the weapon target assignment problem. Operations Research, 55(6):1136--1146, 2007.
• 2: Konstantin Andreev , Harald Racke, Balanced Graph Partitioning, Theory of Computing Systems, v.39 n.6, p.929-939, November 2006 [doi>10.1007/s00224-006-1350-7]
• 3: Z. Baruch, O. Cre¸t, and K. Pusztai. Genetic algorithm for circuit partitioning. In Fifth Int. Conf. on Engineering of Modern Electric Systems: Section Computer Science and Control Systems, pages 19--23, Oradea, 1999.
• 4: Paul K. Bergey , Cliff T. Ragsdale , Mangesh Hoskote, A decision support system for the electrical power districting problem, Decision Support Systems, v.36 n.1, p.1-17, September 2003 [doi>10.1016/S1344-6223(02)00033-0]
• 5: B. Bozkaya, E. Erkut, and G. Laporte. Discrete optimization: A tabu search heuristic and adaptive memory procedure for political districting. European Journal of Operational Research, 144:12--26, 2003.
• 6: 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]
• 7: R. Chandrasekharam, S. Subhramanian, and S. Chaudhury. Genetic algorithm for node partitioning problem and applications in VLSI design. In IEE Proceedings on Computers and Digital Techniques, volume 140, pages 255--260, 1993.
• 8: D. Datta. Multi-Objective Evolutionary Algorithms for Resource Allocation Problems. PhD thesis, Department of Mechanical Engineering, Indian Institute of Technology Kanpur (IIT-Kanpur), India, 2007.
• 9: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 10: K. Deb, S. Agarwal, A. Pratap, and T. Meyarivan. A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182--197, 2002.
• 11: K. Deb, S. Agarwal, A. Pratap, and T. Meyarivan. A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182--197, 2002.
• 12: Robert Entriken , Siegfried Vössner, Genetic algorithms with cluster analysis for production simulation, Proceedings of the 29th conference on Winter simulation, p.1307-1314, December 07-10, 1997, Atlanta, Georgia, United States [doi>10.1145/268437.268776]
• 13: Jacques A. Ferland , Gilles Guénette, Decision support system for the school districting problem, Operations Research, v.38 n.1, p.15-21, Jan–Feb. 1990 [doi>10.1287/opre.38.1.15]
• 14: V. D. Gesú, R. Giancarlo, G. L. Bosco, A. Raimondi, and D. Scaturro. GenClust: A genetic algorithm for clustering gene expression data. BMC Bioinformatics, (6):289, 2005.
• 15: G. Getz, H. Gal, I. Kela, D. A. Notterman, and E. Domany. Coupled two-way clustering analysis of breast cancer and colon cancer gene expression data. Bioinformatics, 19(9):1079--1089, 2003.
• 16: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 17: S. W. Hadley and B. L. Mark. An efficient eigenvector approach for finding netlist partitions. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 11(7):885--892, 1992.
• 18: S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671--680, 1983.
• 19: B. Krishnamurthy, An Improved Min-Cut Algonthm for Partitioning VLSI Networks, IEEE Transactions on Computers, v.33 n.5, p.438-446, May 1984 [doi>10.1109/TC.1984.1676460]
• 20: F. Melício, J. P. Caldeira, and A. Rosa. Two neighbourhood approaches to the timetabling problem. In Proceedings of the Practice and Theory of Automated Timetabling V, Fifth International Conference, PATAT 2004, Pittsburgh, PA, USA, pages 267--282, 2004.
• 21: R. M. Othman, S. Deris, R. M. Illias, Z. Zakaria, and S. M. Mohamad. Automatic clustering of gene ontology by genetic algorithm. Int. J. of Information Technology, 3(1):37--46, 2006.
• 22: Sadiq M. Sait , Habib Youssef, VISI Physical Design Automation: Theory and Practice, McGraw-Hill, Inc., New York, NY, 1994
• 23: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 24: K. Tagawa, T. Fukui, and H. Haneda. Phenotypic genetic algorithm for partitioning problem. In IEEE Int. Conf. on Evolutionary Computation, pages 553--556, Indianapolis, 1997.
• 25: F. Tavares-Pereira, J. R. Figueira, V. Mousseau, and B. Roy. Multiple criteria districting problems: The public transporation network pricing system of the Paris region. Annals of Operations Research, 154(1):69--92, 2007.
• 26: H. H. Yang and D. F. Wong. Efficient network flow based min-cut balanced partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 15(12):1533--1540, 1996.
• 27: A. A. Zoltners and P. Sinha. Sales territory alignment: A review and model. Management Science, 29(11):1237--1256, 1983.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

General Terms:
Algorithms

Keywords:
evolutionary algorithms, multi-objective optimization, partitioning problems