ค่าเฉลี่ยหลาย reference
ทำนายตำแหน่งเป้าหมายจาก reference หลายตัวที่เพิ่งวาง นำคำทำนายมาเฉลี่ย แล้วผสมคะแนน relative order กับความน่าจะเป็นของตำแหน่ง
Permutation estimation-of-distribution algorithm
ROSE
Algorithm
Relative Order SEquencer ไม่ได้เรียนเพียงว่าสมาชิกอยู่ตำแหน่งใด แต่เรียนว่าใครมาก่อนใครและมักห่างกันเท่าไร จึงเปลี่ยน relative order ให้เป็นภาษาความน่าจะเป็นที่นำกลับไปใช้กับปัญหา permutation ได้หลายชนิด
ที่มา · คำถามก่อนเกิดอัลกอริทึม
ปัญหาไม่ได้อยู่ที่ permutation แต่อยู่ที่สิ่งที่เราเลือกให้โมเดลจดจำ
ROSE เริ่มจากความไม่พอใจเล็ก ๆ ต่อวิธีมองปัญหา permutation ในคำตอบทุกชุด สมาชิกทุกตัวปรากฏเหมือนกันและปรากฏเพียงครั้งเดียว สิ่งที่แยกคำตอบที่ดีออกจากคำตอบทั่วไปจึงไม่ใช่ “มีตัวอะไรอยู่บ้าง” แต่เป็นโครงสร้างความสัมพันธ์ระหว่างสมาชิกเหล่านั้น อัลกอริทึมเรียนรู้จึงต้องตัดสินใจก่อนว่า คำว่าโครงสร้างหมายถึงอะไร
งานคลาสสิกด้าน permutation ทำให้คำถามนี้หลีกเลี่ยงไม่ได้ Goldberg และ Lingle ชี้ว่า allele กับ locus ไม่สามารถตีความอย่างง่ายเหมือนโครโมโซมไบนารี เพราะการขยับสมาชิกหนึ่งตัวเปลี่ยนความหมายของหลายตำแหน่ง ต่อมา order-based representation แสดงว่า “ก่อน–หลัง” สามารถเป็น building block ได้ในตัวเอง ความสนใจจึงเคลื่อนจากค่าของสมาชิกแต่ละตัวไปสู่ความสัมพันธ์ระหว่างสมาชิก
ประสบการณ์จากการพัฒนา COINCIDENCE ทำให้ความแตกต่างนี้ชัดขึ้น แบบจำลอง node/position ถามว่าสมาชิกหนึ่งมักอยู่ตำแหน่งใด ส่วนแบบจำลอง edge ถามว่าใครมักต่อจากใคร ทั้งสองแบบมีประโยชน์ แต่ยังอธิบายรูปแบบหนึ่งได้ไม่ครบ: สมาชิกสองตัวอาจรักษาลำดับก่อน–หลังไว้ แม้ไม่ได้อยู่ติดกัน และระยะห่างระหว่างทั้งคู่อาจมีสาระด้วย
คำถามที่กลายมาเป็น ROSE จึงเกิดขึ้นว่า ถ้า A มักมาก่อน C เราจะให้โมเดลเรียนต่อได้หรือไม่ว่า C มักอยู่ห่างจาก A กี่ตำแหน่ง?
จากลำดับสู่ระยะห่าง
Precedence บอกทิศทาง ส่วน ROSE เก็บระยะทางไว้ด้วย
ADBEC
pos(A)=0 · pos(C)=4 · Δ(A,C)=+4เครื่องหมายของ Δ เก็บว่าใครมาก่อน ส่วนขนาดเก็บระยะห่าง edge จึงเป็นกรณีพิเศษที่ |Δ|=1 ขณะที่ precedence เก็บเพียงเครื่องหมายแล้วทิ้งขนาด relative displacement จึงไม่ได้ลบล้าง representation เดิม แต่เชื่อม representation หลายแบบเข้าด้วยกัน
นี่คือก้าวสำคัญของแนวคิด: ประมาณ distribution ของ signed pair distance แล้วใช้ความสัมพันธ์ที่เรียนได้สร้าง permutation ใหม่ที่ยังถูกต้อง ชื่อ “Relative Order SEquencer” จึงเรียกการจัดลำดับ ส่วน estimator อธิบายกลไกสถิติภายใน
Algorithm family
สามวิธีเรียนรู้ relative order
ช่วงจาก reference เดียว
เลือก reference จริงหนึ่งตัว แล้วสุ่ม signed distance จาก truncated normal ที่กำหนดด้วย mean, min, max และ SD โดยไม่เก็บ histogram
ฮิสโตแกรมจาก reference เดียว
เก็บ empirical distribution ของ signed distance โดยตรง จึงละเอียดกว่า แต่ tensor ระยะทางแบบ dense ใช้หน่วยความจำมากกว่าอย่างชัดเจน
/WT · With Template — ทุกรุ่นมีแบบ /WT ซึ่งเก็บบางตำแหน่งของ parent เจาะตำแหน่งที่เลือก เติมเฉพาะสมาชิกที่ถูกนำออก และรับ offspring เมื่อดีกว่า parent เท่านั้น
Research interpretation
สิ่งที่หลักฐานปัจจุบันรองรับ
ในการทดลอง permutation flow shop ปัจจุบัน ROSE/WT ทำงานได้ดีกับ makespan และ total machine idle time ในบางชุดทดลอง ขณะที่ total flow time อาจทำให้การค้นติดกับดัก ข้อนี้เป็นข้อสังเกต ไม่ใช่อันดับที่จริงเสมอไป จึงควรรายงานแยกตาม objective, instance, evaluation budget และ seed