A Reordering Binary Decision Diagram based on Decision Tree Learning and Tabu Search

Main Article Content

พิเชษฐ์ กันทะวัง
ชลยืน หงส์ไพศาลวิวัฒน์
สุกรี สินธุภิญโญ
บุญเสริม กิจศิริกุล

Abstract

เนื่องจากแผนภาพตัดสินใจทวิภาคเป็นโครงสร้างข้อมูลแบบกราฟที่มีประสิทธิภาพในการแทนฟังก์ชันบูลีน แผนภาพตัดสินใจทวิภาคจึงถูกนำไปประยุกต์ใช้กับงานต่างๆของการใช้คอมพิวเตอร์ช่วยในการออกแบบ แต่ปัญหาหนึ่งที่พบเกี่ยวกับแผนภาพตัดสินใจทวิภาคคือ ขนาดของแผนภาพตัดสินใจทวิภาคจะขึ้นอยู่กับลำดับของตัวแปร ดังนั้น วิธีการหาลำดับตัวแปรที่ดีจึงเป็นสิ่งสำคัญในการสร้างแผนภาพตัดสินใจทวิภาคที่มีขนาดเล็ก งานวิจัยฉบับนี้ได้นำเสนอวิธีการปรับลำดับแผนภาพตัดสินใจทวิภาค โดยวิธีการที่นำเสนอจะใช้การเรียนรู้ต้นไม้ตัดสินใจ ร่วมกับเทคนิคการค้นหาต้องห้าม ซึ่งเป็นเทคนิคของปัญญาประดิษฐ์ โดยการหาลำดับตัวแปรเริ่มต้นของแผนภาพตัดสินใจทวิภาคจากนั้นจะลดขนาดของแผนภาพตัดสินใจทวิภาคด้วยเทคนิคการค้นหาต้องห้าม โดยเปรียบเทียบกับวิธีการปรับปรุงแบบก้าวหน้าที่มีอยู่เดิมซึ่งได้รับการปรับปรุงการเลือกตัวแปรแล้ว เช่น AD2 AD3 AD4 AR ARSA และ SIFTING ผลการทดลองกับวงจรวัดเปรียบเทียบสมรรถนะของ MCNC แสดงให้เห็นว่าวิธีการปรับลำดับแผนภาพตัดสินใจทวิภาคที่นำเสนอ สามารถให้แผนภาพที่มีขนาดเล็กกว่าเมื่อเทียบกับขนาดแผนภาพตัดสินใจทวิภาคที่ได้จากวิธีการการปรับปรุงแบบก้าวหน้าทุกแบบที่กล่าวมาข้างต้น

Article Details

How to Cite
กันทะวัง พ. ., หงส์ไพศาลวิวัฒน์ ช. ., สินธุภิญโญ ส. ., & กิจศิริกุล บ. . (2003). A Reordering Binary Decision Diagram based on Decision Tree Learning and Tabu Search. Frontiers in Engineering Innovation Research, 4, 7–19. Retrieved from https://ph01.tci-thaijo.org/index.php/jermutt/article/view/242333
Section
Research Articles

References

Aker, S. B. Binary decision diagrams.IEEE Transactions on Computer Vol.C27 No.6 (June 1978): 509-516.

Bryant, R. E. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computer Vol.C-35 No.8 (August 1986): 677-691.

Bryant, R. E. Symbolic Boolean manipulation with ordered binary decision diagrams. ACM Computing Surveys Vol.24 No.3 (September1992): 293-318.

Micheli, G .D. Synthesis and optimization of digital circuits. New York: McGrawHill, 1994.

Fujita, M.; Fujisawa, H. and Kawato,N. Evaluations and improvementa of Boolean comparison method based on binary decision diagrams. Proceedings of the IEEE Conference on Computer Aided Design (November 1988):2-5

Malik, S.; Wang, A. R.; Brayton, R. K. and Sangiovanni-Vincentelli, A. Logic verification using binary decision diagrams in a logic synthesis environment.Proceedings of the IEEE Conference

on Computer-Aided Design (November1988):6-9

Masunaga , Y, and Fujita , M. Mulis level logic optimization using binary decision diagrams. Proceeding of the IEEE Conference on Computer – Aided Design ( November 1989 ).

Calazans , N; Jasobi , R;; Zhang , Q. and Trullemans , C. Improveing BDDs manipulation through incremental reduction and enhanced heuristics Proceeding of the IEEE Custom

Integrated Circuit Conference (1991): 472-475.

Jacobi, R. ; Calazans , N. and Trullemans, C. Incremental reduction of binary decision diagrams. Proceedings of the IEEE Conference on Computer-Aided Design (November 1991):3174-3177

Ishiura , N.; Sawada , H and Yajima , S Minimization of biary decision diagrams based on exhanges of variables. Proceedings of the IEEE Conference on Computer-Aided Design (November1991): 472 - 475.

Rudell , R. Dynamic variable ordering for ordered binary diagrams. Proceedings of the IEEE Conference on Computer Aided Design (November 1993): 42-47.

Friedman, S.J, and Supowit , K.J. Finding the optimal variable ordering for binary decision diagrams. IEEE Transaction on Computer Vol.39 No.5 (May 1990 ).

Fred Glover,Manuel Laguna TABU SEARCH

Rick, E. and Knight , K. Artificial Intelligence 2"d.ed. Singapore: McGrawHill,1991

Mitchell,T.M. Machine Learning.Massachussetts: McGraw-Hill,1994

Quinlan , J.R.C4.5 : Programs for machine learning. California : Morgan Kaufmann,1993.

MCNC Benchmark Circuit ,[path:pub/benchmark_dirs/LGSyth91/twolexample], Marc 1994.

MCNC Benchmark Circuit [19] Vinyoonutakul, S.; Kijsirikul ,B.and Thongtak, A. Binary decision diagrams minimization based on decision tree learning. Proceedings of the IEEE International Symposium on Intelligent Signal Processing and Communication Systems. (1999)

ศิริพรรณ วิญญนันทกุล,บุญเสริมกิจศิริกุล และอาทิตย์ ทองทักษ์. การปรับปรุงวิธี การสร้างแผนภาพตัดสินใจทวิภาคโดย การเรียนรู้ต้นไม้ตัดสินใจ. การประชุมวิชาการทางวิศวกรรมไฟฟ้า ครั้งที่ 22(2542).

บุญเสริม กิจศิริกุล, ปัญญาประดิษฐ์ (Artificial Intelligence), เอกสารคำสอน 2004

Christop Meinel,Thorsten Theobald Algorithms and Data Structures in VLSI Design, Springer-Verlag Berlin Heidelberg 1998.