ขั้นตอนวิธีการของหวังและลันเดา

การทดสอบระบบ

เราต้องการหาค่าพลังงานศักย์ของการแกว่งแบบฮาร์โมนิคซึ่งมีสูตรดังนี้ E (x) = x2 จากการพิจารณาค่าความหนาแน่นของสาร ได้ว่า
g (E) =\int\delta (E (x) -E_0) dx=\int\delta (x^2-E_0) dx
เมื่อทำการแก้ปริพันธ์แล้วจะได้
g (E) \propto E^{-1/2}
โดยทั่วไปนั้นการหาค่าความหนาแน่นของสภาวะของสารสำหรับการแกว่งแบบฮาร์โมนิคหลายมิติ จะถูกกำหนดโดยพลังงานE ซึ่งเลขชี้กำลังจะถูกกำหนดตามมิติของระบบ

รหัสเทียม

รหัสเทียมนี้เป็นรหัสแสดงขั้นตอนวิธีการของหวังและลันเดาในภาษาการเขียนโปรแกรม D
real[real] log_g; // อาเรย์นี้เก็บค่าล็อกการิททึ่มของค่าความหนาแน่นของสภาวะของสารuint[real] H; // อาเรย์เก็บค่ากราฟแสดงความถี่ทางสถิติ
 
real E_old = the_system.energy (); // เก็บค่าพลังงานเก่าreal F = 1; //เก็บค่าคงที่
 
while (F > epsilon) {
the_system.evolve (); // สร้างการพัฒนาการของระบบreal E_new = the_system.energy (); // คำนวณค่าพลังงานของระบบปัจจุบัน
 
if (log_g[E_new] < log_g[E_old]) // ตรวจสอบว่าข้อเสนอสามารถถูกยอมรับได้หรือไม่
E_old = E_new;else if (random () < exp (log_g[E_old] - log_g[E_new]) )
E_old = E_new;else
the_system.reject_and_undo ();
 
H[E_old]++; // เปลี่ยนแปลงค่ากราฟแสดงความถี่ทางสถิติและค่าความหนาแน่นของสภาวะของสาร
log_g[E_old] += F;
 
if (is_flat (H) ) { // ถ้ากราฟแสดงความถี่มีลักษณะแบนราบ
H[] = 0; // ให้ตั้งค่ากราฟแสดงความถี่เป็น0และลดค่าคงที่
F *= 0.5;}}
 
return log_g;
รหัสเทียมเป็นตัวอักษร
เริ่มต้นจาก ตั้งค่า f=e
do{ do{
Metropolis แก้ไขค่าซึ่งขึ้นกับความน่าจะเป็น W[i->j] = min[1, r (Ei) / r (Ej)]
ปรับตัว r (E) ในแต่ละขั้น : r (E) <- r (E) x f
เพิ่มค่ากราฟแสดงความถี่เชิงสถิติ H (E) ++ }
จนกว่า H (E) มีลักษณะแบนราบ (ประมาณ ร้อยละ20) }
ลด f } จนกว่า f-1 มีค่าประมาณ 10^ (-8)

ปัญหาที่เกี่ยวข้อง

ความหนาแน่นในสภาวะของสาร Density of states (DOS) ของระบบนั้นสามารถเขียนแทนด้วย จำนวนขั้น ต่อ ช่วงระดับพลังงานแต่ละค่าที่สร้างสามารถมีอยู่ได้ ซึ่งแตกต่างกับ isolated systems (เช่น อะตอม หรือ โมเลกุลแก๊ส) การกระจายตัวของ ความหนาแน่น นั้นมีความต่อเนื่อง DOS ที่สูงนั้นหมายถึง มีหลาย state ที่เป็นไปได้ โดยทั่วไปนั้น DOS จะเป็นค่าเฉลี่ยบนที่ว่างและเวลาของระบบ การคำนวณ DOS
ปกติระบบที่เราสนใจนั้นจะมีความซับซ้อน เช่น สารประกอบ, biomolecules, โพลิเมอร์ ฯลฯ ซึ่งส่วนใหญ่ระบบที่มีความซับซ้อน การคำนวณ DOS เทียบจะเป็นไปได้ยากหรือเป็นไปไม่ได้เลย จึงมีการใช้คอมพิวเตอร์ simulate algorithms เพื่อประเมิน DOS ให้ได้ถูกต้องใกล้เคียง หนึ่งใน algorithms ที่มีการใช้ คือ Wang and Landau algorithm
ใน Wang and Landau algorithm นั้น ข้อมูล DOS ก่อนหน้าจำเป็นต้องรู้ cost function ซึ่งเทียบได้กับ พลังงานของระบบนั้นถูก discretized ซึ่งแต่ละรอบ bin i จะ update DOS ของ state g (i) ใน histogram ด้วย g (i) -> g (i) +f โดย f เรียกว่า modification factor
เมื่อแต่ละ bin ใน histogram ถูก update เป็นจำนวน 10-15 รอบ ค่า f จะถูกลดทอนลงด้วย f (n+1) =1/2f (n) โดยที่ n คือรอบที่ n ของการ update
การ simulate นั้นจะทำไปเรื่อย ๆ จนกว่า modification factor จะน้อยกว่าค่า threshold ที่ได้กำหนดไว้ เช่น fn < 10 − 8.
ข้อดีของ ขั้นตอนวิธีการของหวังและลันเดา ที่เหนือกว่าขั้นตอนวิธีอื่น ๆ (เช่น multicanonical simulations and Parallel tempering เป็นต้น) นั่นคือ การจำลองนั้นให้ผลลัพธ์หลักคือ DOS นอกจากนี้ การจำลองเป็นอิสระต่ออุณหภูมิ การคำนวณ DOS ของระบบโดยใช้ขั้นตอนวิธีนี้มักใช้ในการคำนวณ DOS ของโปรตีน

การติดตามการเคลื่อนไหวอย่างทันทีทันใด

ขั้นตอนวิธีการของหวังและลันเดาสามารถนำไปใช้กับการติดตามการเคลื่อนไหวอย่างทันทีทันใด
เราสามารถตั้งสมมติฐานขั้นตอนวิธีที่ใช้ติดตามการเคลื่อนไหวในทันทีทันใดโดยใช้พื้นฐานจากขั้นตอนวิธีของหวังและลันเดาเป็นตัวอย่าง ซึ่งมีประสิทธิภาพในการรองรับภาพที่เคลื่อนไหวในทันทีทันใด การเคลื่อนไหวในทันทีทันใดมักจะทำให้การติดตามการเคลื่อนไหวธรรมดาล้มเหลว เพราะว่าความราบรื่นของกิริยาท่าทางมีน้อยเกินไป เราจึงสามารถนำขั้นตอนวิธีการของหวังและลันเดามาใช้เพราะมีความสามารถในการตรวจสอบสถานะทางกายภาพ และนำขั้นตอนวิธีนี้มาใช้ร่วมกับขั้นตอนวิธีแบบ Markov Chain Monte Carlo ซึ่งเป็นพื้นฐานในการติดตามการเคลื่อนไหวปกติ
วิธีการนี้ทำให้ความไม่ราบรื่นของการเคลื่อนไหวลดลง โดยใช้ความคล้ายคลึงกับลักษณะความหนาแน่นของสภาวะของสาร ซึ่งสามารถหาค่าโดยประมาณได้จากขั้นตอนวิธีการของหวังและลันเดา ซึ่งการใช้ขั้นตอนวิธีนี้ได้ผล ทำให้ความแม่นยำในการติดตามการเคลื่อนไหวราบรื่นขึ้น เพราะว่าลักษณะความหนาแน่นของสภาวะของสารสามารถจับการเคลื่อนไหวอย่างทันทีทันใดได้อย่างแน่นหนา
ผลการทดลองพบว่าการใช้ขั้นตอนวิธีนี้ได้ผลเป็นอย่างดี ตัวอย่างที่ใช้ทดสอบพบว่าลักษณะความหนาแน่นของสภาวะของสารสามารถควบคุมการติดตามการเคลื่อนไหวโดยที่ไม่เสียเวลาเลย สรุปได้ว่า การใช้ขั้นตอนวิธีของหวังและลันเดาในการติดตามภาพที่เคลื่อนไหวในทันทีทันใดสามารถติดตามได้อย่างแม่นยำและถูกต้องเป็นอย่างมาก

การใช้งานกับHeisenberg Chain

ไฟล์:Heisen.png L=10 ให้ค่า Heisenberg chain L = 250
พลังงานเสรีกับค่าความยุ่งเหยิงสามารถนำมาใช้ได้
การจำลองหนึ่งครั้งต่อทุกอุณหภูมิ
T>0.05จูล
ได้ผลดังนี้ ไฟล์:Heisen2.png
ไฟล์:Heisen3.png

การเพิ่มสมรรถภาพของขั้นตอนวิธีของหวังและลันเดาโดยใช้ขอบเขตที่สามารถเปลี่ยนแปลงได้

ขั้นตอนวิธีของหวังและลันเดาในการจำลองระบบขนาดใหญ่ จำเป็นต้องทำการหารช่วงของพลังงานลงเป็น ขอบเขต หลาย ๆ ขอบเขต แล้วนำมารวมกันเพื่อหาคำตอบ ผลของความหนาแน่นของสถานะของสารที่มีระบบขนาดใหญ่มากเกินไป ทำให้เกิดปัญหาการจำลองพลังงานแลททิซของโพลีเมอร์และแบบจำลอง 5ขั้นตอนของ Potts เพราะการจำลองของทั้งสองอย่างนั้นต้องใช้การจำลองที่มีขนาดใหญ่มาก
วิธีการแก้ปัญหาที่เกิดจากระบบมีขนาดใหญ่มากเกินไปทำได้โดยใช้ ขอบเขตที่สามารถเปลี่ยนแปลงได้แทนที่จะใช้ขอบเขตที่มีขนาดคงที่ ค่าของขอบเขตนั้นขึ้นกับค่าของพลังงานในกลุ่มในกราฟแสดงความถี่เชิงสถิติ (Discrete Histogram) มีลักษณะแบนราบหรือไม่เป็นลำดับขั้นของการจำลอง
การเปลี่ยนแปลงขนาดของขอบเขตในแต่ละครั้งของการเปลี่ยนค่าf เราจะทำการตัดขอบของค่า ที่มีผลต่อการจำลองซึ่งใช้ในการจำลองโครงสร้างของขอบเขตปกติ ขอบเขตแบบเปลี่ยนแปลงได้สามารถเพิ่มช่วงของระบบที่จะนำมาจำลองสภานะสภาวะของสารได้อย่างมีประสิทธิภาพ

ความคิดเห็นของผู้เขียน

ขั้นตอนวิธีนี้เป็นขั้นตอนวิธีที่สามารถใช้ประโยชน์ได้มาก นอกจากที่จะใช้ในเชิงฟิสิกส์แล้ว ยังสามารถใช้ในเชิงพาณิชย์ได้ เช่นการทำซอฟต์แวร์ การติดตามการเคลื่อนที่แบบทันทีทันใด สามารถใช้ในการตรวจสอบการเคลื่อนไหวของนักเทนนิส อาจดัดแปลงไปเป็นการทำงานอื่น ๆ ที่มีประโยชน์ต่อมวลมนุษยชาติก็เป็นได้