การประมาณค่าความน่าเชื่อถือของโครงข่ายโดยใช้ขั้นตอนวิธีหวังลันเดาว์แบปรับปรุง
Estimating Network Reliability Using an Improved WangLandau Algorithm
โดย ผู้ช่วยศาสตราจารย์ ดร.วันหยก อติเศรษฐพงศ์ สาขาวิชาคณิตศาสตร์และสถิติ
บทคัดย่อ (ภาษาไทย)
โครงข่ายทางกายภาพในปัจจุบัน เช่น โครงข่ายการสื่อสารและการขนส่งสินค้า สามารถพิจารณาให้อยู่ในรูปของกราฟได้ เราใช้แบบจำลองโครงข่ายเพื่อระบุค่าความน่าจะเป็นที่โหนดในกราฟจะเชื่อมโยงกัน โดยพิจารณาผลกระทบจากการที่มีเส้นเชื่อมบางเส้นไม่สามารถใช้งานได้ ซึ่งเป็นค่าที่สำคัญสำหรับการออกแบบการหาค่าเหมาะที่สุด และความน่าเชื่อถือของโครงข่าย ในงานวิจัยนี้ เราจะนำเสนอวิธีการสามวิธี สำหรับการประมาณค่าความน่าเชื่อถือของโครงข่าย โดยใช้ขั้นตอนวิธีของหวัง-ลันเดาว์ วิธีแรกการเดินสุ่มจะทำบนฟังก์ชันโครงสร้าง ซึ่งมีเพียงสองสถานะคือ โครงข่ายเชื่อมโยงและโครงข่ายไม่เชื่อมโยง วิธีที่สองการเดินสุ่มจะทำบนพหุนามความน่าจะเป็น ส่วนวิธีที่สามจะรวมการเดินสุ่มร่วมกับการหาค่าเฉลี่ยของความน่าจะเป็นที่กราฟจะเป็นกราฟเชื่อมโยง โดยในงานวิจัยได้ทำการเปรียบเทียบความแม่นยำของค่าประมาณและเสนอข้อจำกัดของทั้งสามวิธี โดยใช้การทดสอบกับโครงข่ายสองแบบ ได้แก่ โครงข่ายแบบสะพาน และโครงข่ายแบบบันได ผลการทำงานแสดงให้เห็นว่า วิธีการเดินสุ่มบนฟังก์ชันโครงสร้างไม่สามารถใช้ในการประมาณค่าโครงข่ายที่มีความน่าเชื่อถือสูงได้ ในขณะที่อีกสองวิธีสามารถประมาณค่าความน่าเชื่อถือของโครงข่ายได้อย่างมีประสิทธิภาพ โดยการใช้การเดินสุ่มบนพหุนามความน่าเชื่อถือ และการใช้การเดินสุ่มร่วมกับค่าเฉลี่ยของความน่าจะเป็นที่กราฟจะเป็นกราฟเชื่อมโยงนั้นจะให้ค่าประมาณที่มีความแม่นยำ อย่างไรก็ตามการใช้การเดินสุ่มร่วมกับค่าเฉลี่ยของความน่าจะเป็นที่กราฟจะเป็นกราฟเชื่อมโยงใช้เวลาในการคำนวณน้อยกว่า เมื่อพิจารณาโครงข่ายที่มีขนาดใหญ่
Abstract
Modern physical networks, for example in communication and transportation, can be interpreted as directed graphs. Network models are used to identify the probability that given nodes are connected, and therefore the effect of a failure at a given link. This is essential for network design, optimization, and reliability. In this study, we investigated three alternative ensembles for estimating network reliability using the Wang-Landau algorithm. The first performed random walks on a structure function having two possible states: connected and disconnected. The second used random walks on a reliability polynomial. The third combined random walks with the average of connecting probabilities. The accuracy and limitations of the three ensembles were compared by estimating the reliability of two network models: a bridge network and a ladder-type network. The simulation results showed that the use of a random walk on a structure function failed to estimate the reliability of a highly reliable network, whereas the other two approaches performed efficiently. The use of a random walk on a reliability polynomial, and combining this with the average of connecting probabilities yielded highly accurate estimates. However, the use of the average of connecting probabilities required less computation time when applied to a large network.