A Multi-Objective Evolutionary Algorithm for Channel Routing Problems | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Multi-Objective Evolutionary Algorithm for Channel Routing Problems

  • Chapter
Evolutionary Scheduling

Part of the book series: Studies in Computational Intelligence ((SCI,volume 49))

  • 1145 Accesses

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 17159
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 21449
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
JPY 21449
Price includes VAT (Japan)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Burstein, M. (1986). “Channel routing,” in Layout Design and Verification, Ohtsuki, T. (ed), New York: Elsevier Science.

    Google Scholar 

  2. Burstein, M. and Pelavin, R. (1983). “Hierarchical wire routing,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 2, no. 4, pp. 223-234.

    Article  Google Scholar 

  3. Blickle, T. and Thiele, L. (1995). “A mathematical analysis of tournament selection,” in Proceedings of the 6th International Conference on Genetic Algorithms, pp. 9-16.

    Google Scholar 

  4. Davidenko, V. N., Kureichik, V. M. and Miagkikh, V. V. (1997). “Genetic algorithm for restrictive channel routing problem,” in Proceedings of the 7th International Conference on Genetic Algorithms, pp. 636-642.

    Google Scholar 

  5. Fonseca, C. M. and Fleming, P. J. (1993). “Genetic algorithm for multiobjective optimization: formulation, discussion and generalization,” in Proceedings of the 5th International Conference on Genetic Algorithms, pp. 416-423.

    Google Scholar 

  6. Geraci, M., Orlando, P., Sorbello, F. and Vasallo, G. (1991). “A genetic algorithm for the routing of VLSI circuits,” in Proceedings of Euro ASIC91, pp. 218-223.

    Google Scholar 

  7. Gerez, S. H. and Herrmann, O. E. (1989). “Switchbox routing by stepwise reshaping,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 8, no. 12, pp. 1350-1361.

    Article  Google Scholar 

  8. Groeneveld, P. (1933). “Necessary and sufficient conditions for the routability of classical channels,” The Integration, the VLSI Journal, vol. 16, no. 1, pp. 59-74.

    Article  Google Scholar 

  9. Göckel, N., Pudelko, G., Drechsler, R. and Becker, B. (1996). “A hybrid genetic algorithm for the channel routing problem,” in Proceedings of the 1996 IEEE International Symposium on Circuits and Systems, pp. 675-678.

    Google Scholar 

  10. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning, Boston: Addison Wesley.

    MATH  Google Scholar 

  11. Goldberg, D. E. and Deb, K. (1991). “A comparative analysis of selection schemes used in genetic algorithms,” in Foundations of Genetic Algorithms, Gregory, J. (ed), pp. 69-93.

    Google Scholar 

  12. Goldberg, D. E. and Richardson, J. (1987). “Genetic algorithms with sharing for multimodal function optimization,” in Proceedings of the 2nd International Conference on Genetic Algorithms on Genetic algorithms and their Application, pp. 41-49.

    Google Scholar 

  13. Hashimoto, A. and Stevens, S. (1971). “Wire routing by optimizing channel assignment within large apertures,” in Proceedings of the Eight Design Automation Conference, pages 155-169, ACM/IEEE.

    Google Scholar 

  14. Joobbani, R. (1986). An Artificial Intelligence Approach to VLSI Routing, Boston: Kluwer Academic Publishers.

    Google Scholar 

  15. Lengauer, T. (1990). Combinatorial Algorithms for Integrated Circuit Layout, New York: John Wiley & Sons.

    MATH  Google Scholar 

  16. Leong, H. W., Wong D. F. and Liu, C. L. (1985). “A simulated annealing channel router,” in Proceeding of IEEE International Conference on CAD, pp. 226-228.

    Google Scholar 

  17. Lienig, J. (1997). “A parallel genetic algorithm for performance-driven VLSI routing,” IEEE Transactions on Evolutionary Computation, vol. 1, No. 1, pp. 29-39.

    Article  Google Scholar 

  18. Lienig, J. (1997). “Channel and switchbox routing with minimized crosstalk - a parallel genetic approach,” in Proceedings of the 10th International Conference on VLSI Design, pp. 27-31.

    Google Scholar 

  19. Lienig, J. and Thulasiraman, K. (1994). “A new genetic algorithm for the channel routing problem,” in Proceedings of the 7th International Conference on VLSI Design, pp. 133-136.

    Google Scholar 

  20. Lienig, J. and Thulasiraman, K. (1994). “A genetic algorithm for channel routing in VLSI circuits,” Evolutionary Computation, vol. 1, no. 4, pp. 293-311.

    Article  Google Scholar 

  21. Lin, Y. L., Hsu Y. C. and Tsai F. S. (1989). “SILK: A simulated evolution router,” IEEE Transactions Computer Aided Design of Integrated Circuits and Systems, vol. 8, no. 10, pp. 1108-1114.

    Article  Google Scholar 

  22. Mahfoud, S. W. (1995). Niching Methods for Genetic Algorithms, University of Illinois, Urbana-Champaign, PhD thesis.

    Google Scholar 

  23. Masuda, T., Hayashi, Y., Shigchiro, Y. and Inoue, J. (2000). “A VLSI channel routing method using genetic algorithm based on the coexistence of heterogeneous populations,” IEE Japan Extended Summary, vol. 120-C, no. 11.

    Google Scholar 

  24. Prahlada Rao, B. B. and Hansdah, R. C. (1993). “Extended distributed genetic algorithm for channel routing,” in Proceedings of the IEEE Symposium on Parallel and Distributed Processing, pp. 726-733.

    Google Scholar 

  25. Prahlada Rao, B. B., Patnik, L. M. and Hansdah, R. C. (1995) “An extended evolutionary programming algorithm for VLSI channel routing”, in Proceedings of the Fourth Annual Conference on Evolutionary Programming, pp. 521-544.

    Google Scholar 

  26. Prahlada Rao, B. B., Patnaik, L. M. and Hansdah, R. C. (1994). “A genetic algorithm for channel routing using inter-cluster mutation,” in Proceedings of the first IEEE International Conference on Evolutionary Computation, pp. 97-103.

    Google Scholar 

  27. Prahlada Rao, B.B., Patnaik, L. M. and Hansdah, R.C.(1993). “A parallel genetic algorithm for channel routing problem,” in Proceedings of the IEEE 3rd Great Lake Symposium on Design Automation of High Performance VLSI Systems, pp. 69-70.

    Google Scholar 

  28. Rivest, R. L. and Fidducia, C. M. (1982). “A greedy channel router,” in Proceedings 13th Design Automation Conference, pp. 418-424.

    Google Scholar 

  29. Saymanski, T. G (1985). “Dogleg channel routing is NP-complete, ” IEEE Transactions on Computer-Aided Design, vol. 4, no. 1, pp. 31-41.

    Article  Google Scholar 

  30. Shin, H. and Sangiovanni-Vincentelli, A. (1987). “A detailed router based on incremental routing modifications mighty,” IEEE Transactions on Computer-Aided-Design, vol. 6, no. 6, pp. 942-955.

    Article  Google Scholar 

  31. Tan, K. C., Khor, E. F., Lee, T. H. and Sathikannan, R. (2003). “An evolutionary algorithm with advanced goal and priority specification for multi-objective optimization,” Journal of Artificial Intelligence Research, vol. 18, pp. 183-215.

    MATH  MathSciNet  Google Scholar 

  32. Yoshimura T. and Kuh, E. S. (1982). “Efficient algorithms for channel routing,” IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, vol. 1, no.1, pp. 25-35.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. National University of Singapore, 4, Engineering Drive 3, 117576, Singapore

    Chi Keong Goh

  2. National University of Singapore, 4, Engineering Drive 3, 117576, Singapore

    Wei Ling Lim

  3. National University of Singapore, 4, Engineering Drive 3, 117576, Singapore

    Yong Han Chew

  4. National University of Singapore, 4, Engineering Drive 3, 117576, Singapore

    Prof. Kay Chen Tan

Authors
  1. Chi Keong Goh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wei Ling Lim
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yong Han Chew
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Prof. Kay Chen Tan
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Modeling Optimisation Scheduling and Intelligent Control (MOSAIC), Research Centre, Department of Computing, University of Bradford, West Yorkshire, BD7 1DP, Bradford, UK

    Keshav P. Dahal

  2. Department of Electrical and Computer Engineering, National University of Singapore, 4 Engineering Drive 3, Singapore, Singapore

    Kay Chen Tan

  3. Modeling Optimisation Scheduling and Intelligent Control (MOSAIC), Research Centre, Department of Computing, University of Bradford, West Yorkshire, BD7 1DP, Bradford, UK

    Peter I. Cowling

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Goh, C.K., Lim, W.L., Chew, Y.H., Tan, K.C. (2007). A Multi-Objective Evolutionary Algorithm for Channel Routing Problems. In: Dahal, K.P., Tan, K.C., Cowling, P.I. (eds) Evolutionary Scheduling. Studies in Computational Intelligence, vol 49. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-48584-1_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-48584-1_15

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-48582-7

  • Online ISBN: 978-3-540-48584-1

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation