Comparative Study of Ant Colony and Genetic Algorithms for VLSI Circuit Partitioning

<!DOCTYPE html> <html lang="en" dir="ltr"> <head>  <script async src="https://www.googletagmanager.com/gtag/js?id=G-P63WKM1TM1"></script> <script> window.dataLayer = window.dataLayer || []; function gtag(){dataLayer.push(arguments);} gtag('js', new Date()); gtag('config', 'G-P63WKM1TM1'); </script>  <script type="text/javascript" > (function(m,e,t,r,i,k,a){m[i]=m[i]||function(){(m[i].a=m[i].a||[]).push(arguments)}; m[i].l=1*new Date(); for (var j = 0; j < document.scripts.length; j++) {if (document.scripts[j].src === r) { return; }} k=e.createElement(t),a=e.getElementsByTagName(t)[0],k.async=1,k.src=r,a.parentNode.insertBefore(k,a)}) (window, document, "script", "https://mc.yandex.ru/metrika/tag.js", "ym"); ym(55165297, "init", { clickmap:false, trackLinks:true, accurateTrackBounce:true, webvisor:false }); </script> <noscript><div><img src="https://mc.yandex.ru/watch/55165297" style="position:absolute; left:-9999px;" alt="" /></div></noscript>    <title>Comparative Study of Ant Colony and Genetic Algorithms for VLSI Circuit Partitioning</title> <meta name="description" content="Comparative Study of Ant Colony and Genetic Algorithms for VLSI Circuit Partitioning"> <meta name="keywords" content="Partitioning, genetic algorithm, ant colony optimization, non-polynomial hard, netlist, mutation."> <meta name="viewport" content="width=device-width, initial-scale=1, minimum-scale=1, maximum-scale=1, user-scalable=no"> <meta charset="utf-8"> <meta name="citation_title" content="Comparative Study of Ant Colony and Genetic Algorithms for VLSI Circuit Partitioning"> <meta name="citation_author" content="Sandeep Singh Gill"> <meta name="citation_author" content="Rajeevan Chandel"> <meta name="citation_author" content="Ashwani Chandel"> <meta name="citation_publication_date" content="2009/04/28"> <meta name="citation_journal_title" content="International Journal of Electrical and Computer Engineering"> <meta name="citation_volume" content="3"> <meta name="citation_issue" content="4"> <meta name="citation_firstpage" content="1149"> <meta name="citation_lastpage" content="1153"> <meta name="citation_pdf_url" content="https://publications.waset.org/14013/pdf"> <link href="https://cdn.waset.org/favicon.ico" type="image/x-icon" rel="shortcut icon"> <link href="https://cdn.waset.org/static/plugins/bootstrap-4.2.1/css/bootstrap.min.css" rel="stylesheet"> <link href="https://cdn.waset.org/static/plugins/fontawesome/css/all.min.css" rel="stylesheet"> <link href="https://cdn.waset.org/static/css/site.css?v=150220211555" rel="stylesheet"> </head> <body> <header> <div class="container"> <nav class="navbar navbar-expand-lg navbar-light"> <a class="navbar-brand" href="https://waset.org"> <img src="https://cdn.waset.org/static/images/wasetc.png" alt="Open Science Research Excellence" title="Open Science Research Excellence" /> </a> <button class="d-block d-lg-none navbar-toggler ml-auto" type="button" data-toggle="collapse" data-target="#navbarMenu" aria-controls="navbarMenu" aria-expanded="false" aria-label="Toggle navigation"> <span class="navbar-toggler-icon"></span> </button> <div class="w-100"> <div class="d-none d-lg-flex flex-row-reverse"> <form method="get" action="https://waset.org/search" class="form-inline my-2 my-lg-0"> <input class="form-control mr-sm-2" type="search" placeholder="Search Conferences" value="" name="q" aria-label="Search"> <button class="btn btn-light my-2 my-sm-0" type="submit"><i class="fas fa-search"></i></button> </form> </div> <div class="collapse navbar-collapse mt-1" id="navbarMenu"> <ul class="navbar-nav ml-auto align-items-center" id="mainNavMenu"> <li class="nav-item"> <a class="nav-link" href="https://waset.org/conferences" title="Conferences in 2024/2025/2026">Conferences</a> </li> <li class="nav-item"> <a class="nav-link" href="https://waset.org/disciplines" title="Disciplines">Disciplines</a> </li> <li class="nav-item"> <a class="nav-link" href="https://waset.org/committees" rel="nofollow">Committees</a> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownPublications" role="button" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false"> Publications </a> <div class="dropdown-menu" aria-labelledby="navbarDropdownPublications"> <a class="dropdown-item" href="https://publications.waset.org/abstracts">Abstracts</a> <a class="dropdown-item" href="https://publications.waset.org">Periodicals</a> <a class="dropdown-item" href="https://publications.waset.org/archive">Archive</a> </div> </li> <li class="nav-item"> <a class="nav-link" href="https://waset.org/page/support" title="Support">Support</a> </li> </ul> </div> </div> </nav> </div> </header> <main> <div class="container mt-4"> <div class="row"> <div class="col-md-9 mx-auto"> <form method="get" action="https://publications.waset.org/search"> <div id="custom-search-input"> <div class="input-group"> <i class="fas fa-search"></i> <input type="text" class="search-query" name="q" placeholder="Author, Title, Abstract, Keywords" value=""> <input type="submit" class="btn_search" value="Search"> </div> </div> </form> </div> </div> <div class="row mt-3"> <div class="col-sm-3"> <div class="card"> <div class="card-body"><strong>Commenced</strong> in January 2007</div> </div> </div> <div class="col-sm-3"> <div class="card"> <div class="card-body"><strong>Frequency:</strong> Monthly</div> </div> </div> <div class="col-sm-3"> <div class="card"> <div class="card-body"><strong>Edition:</strong> International</div> </div> </div> <div class="col-sm-3"> <div class="card"> <div class="card-body"><strong>Paper Count:</strong> 33093</div> </div> </div> </div> <div class="card publication-listing mt-3 mb-3"> <h5 class="card-header" style="font-size:.9rem">Comparative Study of Ant Colony and Genetic Algorithms for VLSI Circuit Partitioning</h5> <div class="card-body"> <p class="card-text"><strong>Authors:</strong> <a href="https://publications.waset.org/search?q=Sandeep%20Singh%20Gill">Sandeep Singh Gill</a>, <a href="https://publications.waset.org/search?q=Rajeevan%20Chandel"> Rajeevan Chandel</a>, <a href="https://publications.waset.org/search?q=Ashwani%20Chandel"> Ashwani Chandel</a> </p> <p class="card-text"><strong>Abstract:</strong></p> <p>This paper presents a comparative study of Ant Colony and Genetic Algorithms for VLSI circuit bi-partitioning. Ant colony optimization is an optimization method based on behaviour of social insects [27] whereas Genetic algorithm is an evolutionary optimization technique based on Darwinian Theory of natural evolution and its concept of survival of the fittest [19]. Both the methods are stochastic in nature and have been successfully applied to solve many Non Polynomial hard problems. Results obtained show that Genetic algorithms out perform Ant Colony optimization technique when tested on the VLSI circuit bi-partitioning problem.</p> <iframe src="https://publications.waset.org/14013.pdf" style="width:100%; height:400px;" frameborder="0"></iframe> <p class="card-text"><strong>Keywords:</strong> <a href="https://publications.waset.org/search?q=Partitioning" title="Partitioning">Partitioning</a>, <a href="https://publications.waset.org/search?q=genetic%20algorithm" title=" genetic algorithm"> genetic algorithm</a>, <a href="https://publications.waset.org/search?q=ant%20colony%20optimization" title=" ant colony optimization"> ant colony optimization</a>, <a href="https://publications.waset.org/search?q=non-polynomial%20hard" title=" non-polynomial hard"> non-polynomial hard</a>, <a href="https://publications.waset.org/search?q=netlist" title=" netlist"> netlist</a>, <a href="https://publications.waset.org/search?q=mutation." title=" mutation."> mutation.</a> </p> <p class="card-text"><strong>Digital Object Identifier (DOI):</strong> <a href="https://doi.org/10.5281/zenodo.1082181" target="_blank">doi.org/10.5281/zenodo.1082181</a> </p> <a href="https://publications.waset.org/14013/comparative-study-of-ant-colony-and-genetic-algorithms-for-vlsi-circuit-partitioning" class="btn btn-primary btn-sm">Procedia</a> <a href="https://publications.waset.org/14013/apa" target="_blank" rel="nofollow" class="btn btn-primary btn-sm">APA</a> <a href="https://publications.waset.org/14013/bibtex" target="_blank" rel="nofollow" class="btn btn-primary btn-sm">BibTeX</a> <a href="https://publications.waset.org/14013/chicago" target="_blank" rel="nofollow" class="btn btn-primary btn-sm">Chicago</a> <a href="https://publications.waset.org/14013/endnote" target="_blank" rel="nofollow" class="btn btn-primary btn-sm">EndNote</a> <a href="https://publications.waset.org/14013/harvard" target="_blank" rel="nofollow" class="btn btn-primary btn-sm">Harvard</a> <a href="https://publications.waset.org/14013/json" target="_blank" rel="nofollow" class="btn btn-primary btn-sm">JSON</a> <a href="https://publications.waset.org/14013/mla" target="_blank" rel="nofollow" class="btn btn-primary btn-sm">MLA</a> <a href="https://publications.waset.org/14013/ris" target="_blank" rel="nofollow" class="btn btn-primary btn-sm">RIS</a> <a href="https://publications.waset.org/14013/xml" target="_blank" rel="nofollow" class="btn btn-primary btn-sm">XML</a> <a href="https://publications.waset.org/14013/iso690" target="_blank" rel="nofollow" class="btn btn-primary btn-sm">ISO 690</a> <a href="https://publications.waset.org/14013.pdf" target="_blank" class="btn btn-primary btn-sm">PDF</a> <span class="bg-info text-light px-1 py-1 float-right rounded"> Downloads <span class="badge badge-light">2248</span> </span> <p class="card-text"><strong>References:</strong></p> <br>[1] Eugene L. Lawler, Karl N. Levitt, and James Turner, "Module Clustering to minimize delay in Digital Networks", IEEE Transactions on Computers, Vol. C-18 , No.1, pp. 47-57,Jan, 1969. <br>[2] B.W. Kerhinghan, S. Lin, "An efficient heuristic procedure for partitioning graphs", Bell System Tech. Journal, Vol. 49, pp. 291 - 307, Feb,1970. <br>[3] D.G. Schweikert and B.W. Kernighan, "A proper model for the partitioning of electrical circuits," Proc. ACM/IEEE Design Automation Workshop, pp. 57-62, 1972. <br>[4] C.M. Fiduccia and Mattheyses, "A Linear time heuristic for improving network partitions", Proc. 19th IEEE Design and Automation Conference, IEEE Press, Piscataway, NJ, USA , pp. 175-182, 1982.. <br>[5] B. Krishnamurthy, "An improved min-cut algorithm for partitioning VLSI circuits", IEEE Trans. on Computers, Vol. C-33, May, 1989. <br>[6] L.A. Sanchis, "Multiple way network partitioning", IEEE Trans. on Computers, Vol. 38, No. 1, pp. 62-81 ,1989. <br>[7] Wei and Cheng, "Ratio-cut partitioning for hierarchical design", IEEE transc. on Computer Aided Design, pp. 911-921, July 1991. <br>[8] Jason Cong,L.Hagen, Andrew Kahng, "Net partitions yield better module partitions" , 29th ACM/IEEE Design Automation Conference , Anaheim, CA, USA , pp. 47-52 ,1992. <br>[9] Shawki Areibi and Anthony Vannelli, "Circuit partitioning using a tabu search approach", IEEE International Symposium on Circuits and Systems , Chicago, Illinois, pp. 1643-1646, March,1993. <br>[10] K.Shahookar and Mazumder "Genetic Multiway partitioning", IEEE 8th International Conference on VLSI Design, New Delhi, India, pp. 365- 369, 4-7 Jan 1995. <br>[11] James Cane, Theodre Manikas, "Genetic Algorithms vs Simulated Annealing: A comparison of approaches for solving circuit partitioning problem", Technical report, University of Pittsburgh. <br>[12] S. M. Sait, and H. Youseff, "VLSI Physical Design Automation", McGraw Hill Publishers, New Jersey, 1995. <br>[13] George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar, "Multilevel Hypergraph Partitioning: Applications in VLSI Domain", IEEE 34th Design Automation Conference., Anaheim, California, United States, ACM Press New York, NY, USA., pp 526-529,1997. <br>[14] S. Areibi, "Memetic Algorithms for VLSI Physical Design: Implementation Issues", Genetic and Evolutionary computation Conference, San Fransisco, California, pp140-145, July, 2001. <br>[15] S. Areibi, "Recursive and flat partitioning for VLSI circuit design", The 13th International Conference on Microelectronics, Rabat, Morocco, pp.237-240, 2001. <br>[16] C. Ababei, S.Navaratnasothie, K. Bazargan and G. Karypis, "Multiobjective Circuit partitioning for Cutsize and path-base delay minimization", IEEE International Conference on Computer aided Design,2002. <br>[17] Maurizio Palesi,Tony Givargis, "Multi-Objective Design Space Exploration Using Genetic Algorithms", Proceedings of the 10th International symposium on Hardware/software codesign, ACM Press, Estes Park, Colorado , pp. 67-72 ,2002. <br>[18] Greg Stitt, Roman Lysecky, Frank Vahid, "Dynamic Hardware/Software Partitioning: A First Approach" ACM/IEEE Design Automation Conference 2003, Anaheim, California, USA,pp 250-255, June 2-6, 2003. <br>[19] P. Mazumder, E.M. Rudnik, "Genetic Algorithms for VLSI Design, Layout and Test Automation", Pearson Education, 2003. <br>[20] R. Banos, C. Gil, M.G. Montoya, and J. Ortega, "A Parallel evolutionary algorithm for circuit partitioning", Proceedings of the Eleventh Euromicro conference on Parallel, Distributed, and network based Processing, 2003. <br>[21] Sadiq M. Sait, Aiman H.El-Maleh, and Raslan H. Al-Abaji, "Enhancing performance of iterative heuristics for VLSI net list partitioning", ICECS-2003, pp. 507-510, 2003. <br>[22] D. Kolar, J. Divokovic Puksec and Ivan Branica, "VLSI Circuit partitioning using Simulated annealing Algorithm", IEEE Melecon, Dubrovnik, Croatia, May 12-15, 2004. <br>[23] D.E. Goldberg, "Genetic Algorithms in Search, Optimization and Machine learning", Pearson Education, 2004. <br>[24] P. Ghafari , E. Mirhard, M.Anis, S. Areibi and M. Elmary, " A low power partitioning methodology by maximizing sleep time and minimizing cut nets", IWSOC, Bauf, Alberta, Canada, pp. 368-371, July, 2005. <br>[25] Naveed Sherwani, "Algorithms for VLSI Physical Design and Automation", Third edition, Springer (India) Private Limited, New Delhi, 2005 <br>[26] G. Wang, W. Gang and R.Kastner, "Application Partitioning on programmable platforms using Ant Colony Optimization", Journal of Embedded Computing, Vol.2, Issue 1, 2006. <br>[27] Marco Dorigo and Thomas Stutzle, "Ant Colony Optimization", Prentice Hall of India Private Limited, 2006. <br>[28] Shawki Areibi and Fujian Ali, "A Hardware/Software co-design approach for VLSI circuit partitioning", IEEE International Workshop on SoC, Cairo, Egypt, pp.179-184, December, 2006. <br>[29] K.A. Sumitra Devi, N.P. Banashree and Annamma Abraham, "Comparative Study of Evolutionary Model and Clustering Methods in Circuit Partitioning Pertaining to VLSI Design", Proceeding of World Academy of Science, Engineering and Technology, April, 2007. <br>[30] http://www.gigascale.org/bookshelf </div> </div> </div> </main> <footer> <div id="infolinks" class="pt-3 pb-2"> <div class="container"> <div style="background-color:#f5f5f5;" class="p-3"> <div class="row"> <div class="col-md-2"> <ul class="list-unstyled"> About <li><a href="https://waset.org/page/support">About Us</a></li> <li><a href="https://waset.org/page/support#legal-information">Legal</a></li> <li><a target="_blank" rel="nofollow" href="https://publications.waset.org/static/files/WASET-16th-foundational-anniversary.pdf">WASET celebrates its 16th foundational anniversary</a></li> </ul> </div> <div class="col-md-2"> <ul class="list-unstyled"> Account <li><a href="https://waset.org/profile">My Account</a></li> </ul> </div> <div class="col-md-2"> <ul class="list-unstyled"> Explore <li><a href="https://waset.org/disciplines">Disciplines</a></li> <li><a href="https://waset.org/conferences">Conferences</a></li> <li><a href="https://waset.org/conference-programs">Conference Program</a></li> <li><a href="https://waset.org/committees">Committees</a></li> <li><a href="https://publications.waset.org">Publications</a></li> </ul> </div> <div class="col-md-2"> <ul class="list-unstyled"> Research <li><a href="https://publications.waset.org/abstracts">Abstracts</a></li> <li><a href="https://publications.waset.org">Periodicals</a></li> <li><a href="https://publications.waset.org/archive">Archive</a></li> </ul> </div> <div class="col-md-2"> <ul class="list-unstyled"> Open Science <li><a target="_blank" rel="nofollow" href="https://publications.waset.org/static/files/Open-Science-Philosophy.pdf">Open Science Philosophy</a></li> <li><a target="_blank" rel="nofollow" href="https://publications.waset.org/static/files/Open-Science-Award.pdf">Open Science Award</a></li> <li><a target="_blank" rel="nofollow" href="https://publications.waset.org/static/files/Open-Society-Open-Science-and-Open-Innovation.pdf">Open Innovation</a></li> <li><a target="_blank" rel="nofollow" href="https://publications.waset.org/static/files/Postdoctoral-Fellowship-Award.pdf">Postdoctoral Fellowship Award</a></li> <li><a target="_blank" rel="nofollow" href="https://publications.waset.org/static/files/Scholarly-Research-Review.pdf">Scholarly Research Review</a></li> </ul> </div> <div class="col-md-2"> <ul class="list-unstyled"> Support <li><a href="https://waset.org/page/support">Support</a></li> <li><a href="https://waset.org/profile/messages/create">Contact Us</a></li> <li><a href="https://waset.org/profile/messages/create">Report Abuse</a></li> </ul> </div> </div> </div> </div> </div> <div class="container text-center"> <hr style="margin-top:0;margin-bottom:.3rem;"> <a href="https://creativecommons.org/licenses/by/4.0/" target="_blank" class="text-muted small">Creative Commons Attribution 4.0 International License</a> <div id="copy" class="mt-2">© 2024 World Academy of Science, Engineering and Technology</div> </div> </footer> <a href="javascript:" id="return-to-top"><i class="fas fa-arrow-up"></i></a> <div class="modal" id="modal-template"> <div class="modal-dialog"> <div class="modal-content"> <div class="row m-0 mt-1"> <div class="col-md-12"> <button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">×</span></button> </div> </div> <div class="modal-body"></div> </div> </div> </div> <script src="https://cdn.waset.org/static/plugins/jquery-3.3.1.min.js"></script> <script src="https://cdn.waset.org/static/plugins/bootstrap-4.2.1/js/bootstrap.bundle.min.js"></script> <script src="https://cdn.waset.org/static/js/site.js?v=150220211556"></script> <script> jQuery(document).ready(function() { /*jQuery.get("https://publications.waset.org/xhr/user-menu", function (response) { jQuery('#mainNavMenu').append(response); });*/ jQuery.get({ url: "https://publications.waset.org/xhr/user-menu", cache: false }).then(function(response){ jQuery('#mainNavMenu').append(response); }); }); </script> </body> </html>

CINXE.COM

Comparative Study of Ant Colony and Genetic Algorithms for VLSI Circuit Partitioning