← งานวิจัย COINล้างคิวทั้งหมดEnglish
COIN · ROSE · PERMUTATION OPTIMIZATION

ห้องทดลอง COIN/ROSE
Load Partitioning

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

ตัวประเมินเดียว · งบเท่ากันทุกอัลกอริทึมใช้ instance, evaluator, seed และจำนวน objective evaluations เดียวกัน ผลลัพธ์จึงตรวจสอบและทำซ้ำได้
StatusReady
Runs completed0 / 0
Evaluations—
Best primary—

Benchmark

ผลจะปรากฏหลังการทดลอง

Current: —

บทนำและแนวคิดของปัญหา

โจทย์นี้เริ่มจาก Bin Packing Problem แบบหนึ่งมิติ: สิ่งของทุกชิ้นมีน้ำหนักและกระสอบมีความจุเท่ากัน เป้าหมายมาตรฐานคือลดจำนวนกระสอบ แต่ห้องทดลองเพิ่มคำถามเชิงปฏิบัติว่า เมื่อใช้จำนวนกระสอบเท่ากัน ควรจัดน้ำหนักให้สมดุลหรือควรเติมบางใบให้เต็มที่สุด

COIN เรียนรู้ adjacency และตำแหน่งที่พบใน permutation คุณภาพสูง ส่วน ROSE เรียนรู้ relative order ก่อน–หลัง ตัวแบ่งที่เห็นในผลลัพธ์ไม่ได้เป็น gene แต่เกิดจาก decoder เดียวกันสำหรับทุกอัลกอริทึม

การแทนคำตอบ

π = (3,8,2,5,7,1,6,4,9)
Decode(π) = (3,8,2,5) | (7,1,6) | (4,9)

ตัวถอดรหัสแบบ Next Fit อ่านจากซ้ายไปขวา ใช้เวลา O(n) และเริ่มกระสอบใหม่ก่อนวาง item ที่ทำให้ load เกิน C ทุก permutation จึงเป็นคำตอบที่ feasible โดยไม่ต้อง repair

นิยามปัญหา วัตถุประสงค์ และการคำนวณ fitness

ให้ wᵢ เป็นน้ำหนัก, C เป็นความจุ, B(π) เป็นจำนวนกระสอบ และ Lᵦ เป็น load ของกระสอบ b

min f₁ = B(π)
min f₂ = (1/B) Σ(C−Lᵦ)
min f₃ = maxᵦ(C−Lᵦ)
min f₄ = (1/B) Σ(Lᵦ−L̄)²

average unused capacity เท่ากับ C−Σwᵢ/B จึงให้ข้อมูลเดียวกับจำนวนกระสอบเมื่อ C และน้ำหนักรวมคงที่ หน้า Lab แสดงไว้เพื่อการสอน แต่ maximum unused และ variance ใช้แยกคำตอบที่มี B เท่ากันได้ สำหรับ standard track ควรใช้ lexicographic priority โดยให้ B สำคัญที่สุด; สำหรับ MO track หน้าเว็บรายงาน Pareto set โดยไม่ซ่อน trade-off

ที่มาของ benchmark และวรรณกรรมที่เกี่ยวข้อง

หน้าเว็บโหลดตัวอย่างจาก BPPLIB จริง โดยเลือกตระกูล Falkenauer U และ T ตระกูล U ใช้น้ำหนักแบบ uniform ส่วน T มีโครงสร้าง triplet ที่ออกแบบให้สมาชิกสามชิ้นอยู่ร่วม bin ในคำตอบเหมาะที่สุด เราเรียกวัตถุประสงค์ด้าน balance ว่า balanced extension of BPPLIB เพราะค่าอ้างอิงของ BPPLIB มุ่งจำนวน bin ไม่ใช่ variance

เอกสารอ้างอิง

  1. Delorme, Iori & Martello. BPPLIB. Optimization Letters 12, 235–250 (2018).
  2. Falkenauer, E. A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics 2, 5–30 (1996).
  3. Delorme, Iori & Martello. Bin Packing and Cutting Stock Problems: Mathematical Models and Exact Algorithms. EJOR 255 (2016).