skip to main content
10.1145/1389095.1389222acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
research-article

Graph partitioning through a multi-objective evolutionary algorithm: a preliminary study

Published: 12 July 2008 Publication History

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]
K. Andreev and H. Räcke. Balanced graph partitioning. Theory of Computing Systems, 39:929--939, 2006.
[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]
P. K. Bergeya, C. T. Ragsdaleb, and M. Hoskotec. A decision support system for the electrical power districting problem. Decision Support Systems, 36:1--17, 2003.
[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]
T. N. Bui and B. R. Moon. Genetic algorithm and graph partitioning. IEEE Transcations on Computers, 45(7):841--855, 1996.
[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]
K. Deb. Multi-Objective Optimization using Evolutionary Algorithms. John Wiley & Sons Ltd, Chichester, England, 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]
R. Entriken and S. Vössner. Genetic algorithms with cluster analysis for production simulation. In Proceedings of the 29th Conf. on Winter Simulation, pages 1307--1314, Atlanta, 1997.
[13]
J. A. Ferland and G. Guénette. Decision support system for the school districting problem. Operations Research, 38(1):15--21, 1990.
[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]
D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, 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 algorithm for partitioning VLSI networks. IEEE Transcations on Computers, 33(5):438--446, 1984.
[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]
S. M. Sait and H. Youssef. VLSI Physical Design Automation. McGraw-Hill, 1995.
[23]
J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Trans. Pattern Analysis & Machine Intelligence, 22(8):888--905, 2000.
[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.

Cited By

View all
  • (2023)Multilayer Network Community Detection: A Novel Multi-Objective Evolutionary Algorithm Based on Consensus Prior Information [Feature]IEEE Computational Intelligence Magazine10.1109/MCI.2023.324572918:2(46-59)Online publication date: May-2023
  • (2023)A novel methodology for pipe grouping and rehabilitation interventions scheduling in water distribution networksUrban Water Journal10.1080/1573062X.2023.220956020:7(769-781)Online publication date: 5-May-2023
  • (2021)An iterative local search based hybrid algorithm for the service area problemComputational Urban Science10.1007/s43762-021-00018-71:1Online publication date: 17-Aug-2021
  • Show More Cited By

Index Terms

  1. Graph partitioning through a multi-objective evolutionary algorithm: a preliminary study

        Recommendations

        Comments

        Information & Contributors

        Information

        Published In

        cover image ACM Conferences
        GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation
        July 2008
        1814 pages
        ISBN:9781605581309
        DOI:10.1145/1389095
        • Conference Chair:
        • Conor Ryan,
        • Editor:
        • Maarten Keijzer
        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]

        Sponsors

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        Published: 12 July 2008

        Permissions

        Request permissions for this article.

        Check for updates

        Author Tags

        1. evolutionary algorithms
        2. multi-objective optimization
        3. partitioning problems

        Qualifiers

        • Research-article

        Conference

        GECCO08
        Sponsor:

        Acceptance Rates

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

        Contributors

        Other Metrics

        Bibliometrics & Citations

        Bibliometrics

        Article Metrics

        • Downloads (Last 12 months)3
        • Downloads (Last 6 weeks)0
        Reflects downloads up to 22 Feb 2025

        Other Metrics

        Citations

        Cited By

        View all
        • (2023)Multilayer Network Community Detection: A Novel Multi-Objective Evolutionary Algorithm Based on Consensus Prior Information [Feature]IEEE Computational Intelligence Magazine10.1109/MCI.2023.324572918:2(46-59)Online publication date: May-2023
        • (2023)A novel methodology for pipe grouping and rehabilitation interventions scheduling in water distribution networksUrban Water Journal10.1080/1573062X.2023.220956020:7(769-781)Online publication date: 5-May-2023
        • (2021)An iterative local search based hybrid algorithm for the service area problemComputational Urban Science10.1007/s43762-021-00018-71:1Online publication date: 17-Aug-2021
        • (2017)Optimizing the Structure of Distribution Smart Grids with Renewable Generation against Abnormal Conditions: A Complex Networks Approach with Evolutionary AlgorithmsEnergies10.3390/en1008109710:8(1097)Online publication date: 26-Jul-2017
        • (2017)An improved multiobjective evolutionary approach for community detection in multilayer networks2017 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2017.7969345(443-449)Online publication date: Jun-2017
        • (2017)A multi-objective genetic algorithm based approach for location of grain silos in Paran State of BrazilComputers and Industrial Engineering10.1016/j.cie.2017.07.019111:C(381-390)Online publication date: 1-Sep-2017
        • (2015)Multi-objective optimization in partitioning the healthcare system of Parana State in BrazilOmega10.1016/j.omega.2014.10.00552(53-64)Online publication date: Apr-2015
        • (2014)Reporting and analyzing alternative clustering solutions by employing multi-objective genetic algorithm and conducting experiments on cancer dataKnowledge-Based Systems10.5555/2842045.284237056:C(108-122)Online publication date: 1-Jan-2014
        • (2014)An Evolutionary Multiobjective Approach for Community Discovery in Dynamic NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2013.13126:8(1838-1852)Online publication date: Aug-2014
        • (2014)Reporting and analyzing alternative clustering solutions by employing multi-objective genetic algorithm and conducting experiments on cancer dataKnowledge-Based Systems10.1016/j.knosys.2013.11.00356(108-122)Online publication date: Jan-2014
        • Show More Cited By

        View Options

        Login options

        View options

        PDF

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader

        Figures

        Tables

        Media

        Share

        Share

        Share this Publication link

        Share on social media