ตั้งค่าการทดลอง
Sudoku
ผลเปรียบเทียบ Algorithm
เริ่มการทดลองเพื่อเปรียบเทียบทั้งสี่วิธี
| Algorithm | Penalty | กลุ่มที่ถูก | เลขซ้ำส่วนเกิน | กลุ่มแย่สุด | Time |
|---|
Prime-product penalty ที่ดีที่สุดตาม evaluations
คำตอบเดียว แต่แยกสัญญาณเพื่อช่วยการค้นหา
Sudoku ไม่ใช่ปัญหาตัดสินใจหลายวัตถุประสงค์โดยธรรมชาติ เพราะคำตอบที่ถูกต้องทุกกระดานเป็น optimal เหมือนกัน Multi-objectivization คือการตั้งใจแยก penalty ความถูกต้องหนึ่งค่าให้เป็นเวกเตอร์ของสัญญาณที่สัมพันธ์กัน เพื่อให้ population search แยก candidate ซึ่งเคยได้คะแนนรวมเท่ากันได้ เป้าหมายคือแบ่ง credit และรักษาความหลากหลายระหว่างค้นหา ไม่ใช่ยอมรับ trade-off ของคำตอบสุดท้ายที่ยังผิด
ideal point = (0, 0) = exact Sudoku
ตัวอย่างเช่น (2,8) และ (5,5) มีผลรวมเท่ากัน แต่บอกทิศทางการซ่อมคนละแบบ Pareto dominance จะเก็บทั้งคู่เมื่อไม่มีตัวใดดีกว่าทุกแกน crowding ช่วยรักษาตัวแทนจากบริเวณต่าง ๆ และ external archive เก็บกระดาน non-dominated ข้าม generation เมื่อทุกองค์ประกอบเป็นศูนย์ certificate จะยืนยันคำตอบ exact และหยุดค้นหาได้
จาก 2 objectives สู่ many-objective
- 2D · Row × Column — baseline ที่ชัดและอ่าน Pareto front ง่ายที่สุด
- 6D · Bands × Stacks — สามแถบแนวนอนกับสามแถบแนวตั้งช่วยระบุตำแหน่ง conflict
- 9D · Block responsibility — แบ่งความรับผิดชอบให้แต่ละ block จาก conflict ที่ cell ของมันก่อในแถว/คอลัมน์
- 9D · Digit conflicts — แสดงว่าเลขตัวใดยังจัดวางยาก
- 2D · Worst × Total — สมดุลการซ่อมกลุ่มที่แย่ที่สุดกับความคืบหน้ารวม
มิติที่มากขึ้นเป็นสมมติฐานการทดลอง ไม่ได้ดีกว่าอัตโนมัติ เพราะเมื่อมิติสูง candidate จำนวนมากจะกลายเป็น non-dominated จน selection pressure อ่อนลง จึงต้องเทียบด้วย population, seeds และ evaluation budget เท่ากัน แล้วรายงาน solution rate, evaluations-to-solution, convergence, spread, archive size และ runtime
Permutation รับประกันอะไร
เลขที่ขาดแต่ละ occurrence กลายเป็น token ที่ไม่ซ้ำกัน แต่ decode กลับเป็น digit ดังนั้น candidate ทุกตัวรักษา clue และจำนวนเลขแต่ละตัวให้ครบเก้าตัวเสมอ token คนละตัวอาจ decode เป็นเลขเดียวกันได้ ซึ่งทำให้เห็น symmetry ของ representation อย่างชัดเจน
ละเอียดกว่าแค่ผ่านหรือไม่ผ่าน
Penalty = 100000·duplicate excess + 1000·invalid groups + 10·squared excess + worst group
ความถูกต้องของแต่ละกลุ่มมาจาก prime product ส่วน exponent ของ prime บอก multiplicity ทำให้ optimizer เห็นระดับความผิด และค่า 0 ยังคงหมายถึงคำตอบ Sudoku ที่ถูกต้องพอดี
ตอนนี้ใช้ Controlled Fixtures และรองรับ Open Puzzle Bank ต่อไป
โจทย์สามชุดในหน้านี้เป็น controlled clue masks ที่สร้างจากคำตอบซึ่งตรวจแล้ว เพื่อศึกษาผลของขนาด permutation โดยไม่อ้างว่าเป็นระดับความยากสำหรับมนุษย์ งานทดลองขนาดใหญ่ขั้นต่อไปสามารถใช้ Sudoku Exchange Puzzle Bank ซึ่งมีโจทย์ unique-solution หลายแสนชุด จัดระดับด้วย Sukaku Explainer และอุทิศเป็น public domain Sudoku Exchange Puzzle Bank ↗