วิวัฒนาการเชิงผลต่าง — ตัวหาค่าเหมาะที่สุดเชิงสุ่มระดับส่วนกลาง (Differential Evolution: Global Stochastic Optimiser)
- ผู้เสนอ
- Rainer Storn & Kenneth Price
- ปี
- 1997
- ประเภท
- Population-based stochastic metaheuristic
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
Differential Evolution (DE) ซึ่งถูกนำเสนอโดย Rainer Storn และ Kenneth Price ในปี 1997 เป็นอัลกอริทึมการหาค่าเหมาะที่สุดแบบสุ่มที่ใช้ประชากร (population-based stochastic optimisation algorithm) ซึ่งออกแบบมาสำหรับปริภูมิพารามิเตอร์แบบต่อเนื่อง (continuous parameter spaces) อัลกอริทึมนี้สร้างคำตอบที่เป็นไปได้ (candidate solutions) โดยการรวมผลต่างของเวกเตอร์ระหว่างสมาชิกในประชากรที่มีอยู่ ทำให้เป็นทางเลือกที่มีประสิทธิภาพและใช้พารามิเตอร์น้อยเมื่อเทียบกับ Genetic Algorithms และ Particle Swarm Optimisation ในกรณีที่พื้นที่การค้นหา (search landscape) ไม่ใช่แบบนูน (non-convex) มีหลายจุดเหมาะสมที่สุดเฉพาะที่ (multimodal) หรือไม่เหมาะสมกับวิธีที่ใช้เกรเดียนต์ (gradient-based methods)
แนวคิดเบื้องหลังวิธีการ
ลองจินตนาการถึงกลุ่มนักสำรวจที่กระจายตัวอยู่ทั่วภูมิประเทศที่ไม่คุ้นเคยเพื่อค้นหาหุบเขาที่ต่ำที่สุด ในแต่ละขั้นตอน นักสำรวจแต่ละคนจะสังเกตเพื่อนร่วมทางสามคนที่ถูกเลือกแบบสุ่ม เคลื่อนที่ไปในทิศทางที่แนะนำโดยผลต่างระหว่างสองคนในนั้น ซึ่งถูกปรับขนาดด้วยตัวคูณขนาดของก้าว (step-size factor) จากนั้นจึงตัดสินใจว่าตำแหน่งใหม่หรือตำแหน่งเดิมเป็นสภาพภูมิประเทศที่ดีกว่า ในหลายๆ รอบ กลุ่มทั้งหมดจะค่อยๆ เกาะกลุ่มกันรอบหุบเขาที่ลึกที่สุดที่ค้นพบร่วมกัน Differential Evolution ทำงานในลักษณะนี้: 'ผลต่าง' ระหว่างเวกเตอร์ประชากรสองตัวทำหน้าที่เป็นทิศทางการค้นหา และตัวคูณขนาด F จะควบคุมความกล้าของแต่ละก้าว
ประวัติศาสตร์
Differential Evolution ถูกนำเสนอโดย Rainer Storn และ Kenneth Price ในบทความสำคัญของพวกเขาในปี 1997 ในวารสาร Journal of Global Optimization อัลกอริทึมนี้พัฒนามาจากการทำงานก่อนหน้านี้ของ Price เกี่ยวกับ genetic annealing และการทดลองของ Storn เกี่ยวกับการครอสโอเวอร์แบบจุดลอยตัว (floating-point crossover) รูปแบบดั้งเดิมที่ปัจจุบันเรียกว่า DE/best/1/bin พิสูจน์แล้วว่ามีประสิทธิภาพเทียบเคียงได้ และมักจะเหนือกว่ากลยุทธ์เชิงวิวัฒนาการ (evolutionary strategies) และอัลกอริทึมเชิงพันธุกรรม (genetic algorithms) ที่มีอยู่ในขณะนั้นในเกณฑ์มาตรฐานมาตรฐาน การทบทวนอย่างครอบคลุมโดย Das, Mullick และ Suganthan (2016) ได้รวบรวมรูปแบบต่างๆ (variants) แผนการปรับอัตโนมัติ (adaptive schemes) และการประยุกต์ใช้ตลอดระยะเวลากว่าสองทศวรรษ ซึ่งจัดให้ DE เป็นหนึ่งในวิธีการพื้นฐานในวรรณกรรมเกี่ยวกับอภิวิธี (metaheuristics)
ควรใช้เมื่อใด
Differential Evolution เหมาะสมเมื่อฟังก์ชันวัตถุประสงค์เป็นแบบต่อเนื่อง อาจไม่สามารถหาอนุพันธ์ได้ (non-differentiable) หรือมีหลายจุดเหมาะสมที่สุดเฉพาะที่ (multimodal) และทราบขอบเขตการค้นหาสำหรับพารามิเตอร์ทั้งหมดล่วงหน้า อัลกอริทึมนี้ไม่ต้องการข้อมูลเกรเดียนต์และไม่มีข้อสมมติฐานเกี่ยวกับการแจกแจงปกติ (normality assumption) ดังนั้นจึงเหมาะสำหรับงานออกแบบทางวิศวกรรม การปรับไฮเปอร์พารามิเตอร์ (hyperparameter tuning) การปรับเทียบแบบจำลองซิมูเลชัน (simulation models) และงานหาค่าเหมาะที่สุดแบบกล่องดำ (black-box optimisation) ใดๆ ขนาดประชากรประมาณ 10 เท่าของจำนวนพารามิเตอร์เป็นจุดเริ่มต้นทั่วไป DE ไม่ควรนำไปใช้กับปัญหาที่เกี่ยวกับจำนวนเต็ม (discrete) หรือปัญหาการจัดหมู่ (combinatorial) โดยเฉพาะ ควรใช้วิธีอื่นแทน นอกจากนี้ยังต้องการจำนวนรอบอย่างน้อย 1,000 รอบเพื่อให้ลู่เข้าได้อย่างน่าเชื่อถือ หากงบประมาณการประเมินฟังก์ชันมีจำกัด การหาค่าเหมาะที่สุดแบบเบย์เซียน (Bayesian optimisation) จะเป็นทางเลือกที่ใช้ตัวอย่างน้อยกว่า
ข้อจำกัดและข้อควรพิจารณา
- การลู่เข้าอาจช้าหากจำนวนรอบไม่เพียงพอ จำนวนรุ่นน้อยกว่า 1,000 รอบมักให้ผลลัพธ์ที่ยังไม่ใช่ค่าเหมาะที่สุด
- ประสิทธิภาพขึ้นอยู่กับการเลือกค่า F และ CR — การตั้งค่าพารามิเตอร์ที่ไม่เหมาะสมอาจนำไปสู่การลู่เข้าก่อนเวลาอันควร (premature convergence) หรือความคืบหน้าที่ช้าเกินไป
- ไม่ได้ออกแบบมาสำหรับปริภูมิการค้นหาที่เป็นจำนวนเต็ม (discrete) หรือการจัดหมู่ (combinatorial) โดยเฉพาะ มีส่วนขยายสำหรับปัญหาจำนวนเต็มอยู่แต่ไม่เป็นมาตรฐาน
- แต่ละรอบการทำงานต้องการการประเมินฟังก์ชันวัตถุประสงค์ NP ครั้ง ซึ่งอาจมีค่าใช้จ่ายสูงเมื่อการประเมินแต่ละครั้งต้องใช้การคำนวณมาก
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ไม่ต้องการข้อมูลเกรเดียนต์ — ทำงานได้กับฟังก์ชันวัตถุประสงค์แบบกล่องดำทุกประเภท รวมถึงฟังก์ชันที่ไม่สามารถหาอนุพันธ์ได้และฟังก์ชันที่มีสัญญาณรบกวน
- มีพารามิเตอร์ควบคุมน้อยมาก (F, CR, NP) เมื่อเทียบกับพลังการค้นหา ทำให้กำหนดค่าได้ง่ายกว่าเมื่อเทียบกัน
- จัดการกับพื้นที่การค้นหาที่มีหลายจุดเหมาะสมที่สุดเฉพาะที่ (multimodal landscapes) ได้ตามธรรมชาติ ซึ่งอัลกอริทึมที่ใช้เกรเดียนต์มักจะลู่เข้าสู่จุดเหมาะสมที่สุดเฉพาะที่ (local optima)
- การประเมินผลในแต่ละรุ่นของประชากรเป็นอิสระต่อกันและสามารถประมวลผลแบบขนานได้ง่าย ช่วยลดเวลาในการประมวลผลบนระบบแบบหลายคอร์ (multi-core systems)
- มีประสิทธิภาพเทียบเคียงได้กับ Genetic Algorithms และ Particle Swarm Optimisation ในหลายๆ เกณฑ์มาตรฐาน (benchmarks) ในขณะที่ใช้กฎการอัปเดตที่ง่ายกว่า
การประยุกต์ใช้
- การปรับเทียบแบบจำลองซิมูเลชัน (simulation models) และแบบจำลองตัวแทน (agent-based models) ที่มีฟังก์ชันวัตถุประสงค์ไม่เป็นไปตามฟังก์ชันวิเคราะห์ (non-analytic)
- การปรับไฮเปอร์พารามิเตอร์สำหรับไปป์ไลน์การเรียนรู้ของเครื่อง (machine-learning pipelines) เมื่อปริภูมิการค้นหาเป็นแบบต่อเนื่องและมีขอบเขต
- ปัญหาการออกแบบทางวิศวกรรม เช่น การออกแบบเสาอากาศ การหาค่าเหมาะที่สุดเชิงโครงสร้าง และการปรับแต่งตัวควบคุม (controller tuning)
- การฝึกโครงข่ายประสาทเทียม (neural networks) และการปรับแบบจำลองที่ไม่เป็นเชิงเส้น (non-linear models) ในสาขาวิศวกรรมและวิทยาศาสตร์ธรรมชาติ
- การหาค่าเหมาะที่สุดของน้ำหนักพอร์ตโฟลิโอ (portfolio weight optimisation) และการประมาณค่าพารามิเตอร์ในแบบจำลองอนุกรมเวลาทางการเงิน (financial time-series models)
วิธีการทำงาน
วิธีการทำงาน
ประชากรของเวกเตอร์คำตอบที่เป็นไปได้ NP ตัว ถูกสุ่มเลือกอย่างสม่ำเสมอภายในขอบเขตการค้นหา (search bounds) ที่กำหนดไว้ล่วงหน้าสำหรับแต่ละพารามิเตอร์ ผู้ใช้ต้องระบุขอบเขตการค้นหาก่อนที่อัลกอริทึมจะเริ่มทำงาน DE ไม่สามารถอนุมานขอบเขตเหล่านั้นจากปัญหาได้ ประชากรเริ่มต้นที่ดีควรครอบคลุมพื้นที่ที่สามารถเป็นไปได้ทั้งหมด เพื่อที่อัลกอริทึมจะได้ไม่พลาดบริเวณที่มีแนวโน้มตั้งแต่เริ่มต้น
สำหรับเวกเตอร์เป้าหมายแต่ละตัวในประชากร จะมีการเลือกเวกเตอร์ที่แตกต่างกันสามตัวแบบสุ่ม เวกเตอร์กลายพันธุ์ (mutant vector) จะถูกสร้างขึ้นโดยการบวกผลต่างที่ปรับขนาดของสองเวกเตอร์นั้นเข้ากับเวกเตอร์ที่สาม: v = x_r1 + F*(x_r2 - x_r3) โดยที่ F คือตัวคูณขนาด (scale factor) (โดยทั่วไปคือ 0.4–1.0) ขั้นตอนที่อิงตามผลต่างนี้คือสิ่งที่ทำให้ DE แตกต่างจากอัลกอริทึมเชิงวิวัฒนาการอื่นๆ และให้ข้อมูลทิศทางที่ปรับเปลี่ยนได้เองโดยไม่ต้องคำนวณเกรเดียนต์
เวกเตอร์ทดลอง (trial vector) จะถูกสร้างขึ้นโดยการผสมผสานเวกเตอร์กลายพันธุ์และเวกเตอร์เป้าหมายเดิมทีละองค์ประกอบ องค์ประกอบแต่ละส่วนจะถูกนำมาจากเวกเตอร์กลายพันธุ์ด้วยความน่าจะเป็น CR (อัตราการครอสโอเวอร์, crossover rate) (โดยทั่วไปคือ 0.5–1.0) และจากเวกเตอร์เป้าหมายในกรณีอื่น อย่างน้อยหนึ่งองค์ประกอบจะถูกนำมาจากเวกเตอร์กลายพันธุ์เสมอ ขั้นตอนนี้จะควบคุมความสมดุลระหว่างการสำรวจ (exploration) และการใช้ประโยชน์ (exploitation): CR สูงจะส่งเสริมเวกเตอร์กลายพันธุ์ ในขณะที่ CR ต่ำจะรักษาโซลูชันปัจจุบันไว้มากขึ้น
เวกเตอร์ทดลองจะถูกประเมินโดยฟังก์ชันวัตถุประสงค์ (objective function) และเปรียบเทียบกับเวกเตอร์เป้าหมาย หากเวกเตอร์ทดลองได้ค่าวัตถุประสงค์เท่ากันหรือดีกว่า มันจะเข้ามาแทนที่เวกเตอร์เป้าหมายในรุ่นถัดไป มิฉะนั้นเวกเตอร์เป้าหมายจะยังคงอยู่เหมือนเดิม การเลือกแบบโลภ (greedy) แบบตัวต่อตัวนี้ช่วยป้องกันไม่ให้ประชากรเสื่อมโทรมและรับประกันการปรับปรุงค่าที่ดีที่สุดที่พบได้อย่างต่อเนื่อง
การกลายพันธุ์ (mutation) การครอสโอเวอร์ (crossover) และการคัดเลือก (selection) จะทำซ้ำไปเรื่อยๆ เป็นจำนวนรุ่น (generations) ที่เพียงพอ (โดยทั่วไปคือ 1,000 รุ่นขึ้นไป) จนกว่าจะบรรลุเกณฑ์การลู่เข้า (convergence criterion) เช่น การเปลี่ยนแปลงของค่าวัตถุประสงค์ที่ดีที่สุดลดลงต่ำกว่าเกณฑ์ความคลาดเคลื่อน (tolerance threshold) หรือถึงจำนวนรอบสูงสุดที่กำหนด เวกเตอร์ที่ดีที่สุดในประชากรสุดท้ายคือคำตอบของอัลกอริทึม
ข้อผิดพลาดที่พบบ่อย
- การรัน Differential Evolution โดยใช้จำนวนรอบน้อยเกินไป (น้อยกว่า ~1,000 รอบ) เป็นข้อผิดพลาดที่พบบ่อยที่สุด — อัลกอริทึมยังไม่มีจำนวนรุ่นเพียงพอที่จะลู่เข้า และควรพิจารณาผลลัพธ์ว่าเป็นเพียงข้อมูลเบื้องต้น หากงบประมาณการประเมินมีจำกัด ควรเปลี่ยนไปใช้ Bayesian optimisation
- การตั้งค่าตัวคูณขนาด F ต่ำเกินไปจะทำให้ความหลากหลายลดลงก่อนเวลาอันควร การตั้งค่าสูงเกินไปจะขัดขวางการลู่เข้า ควรเริ่มต้นด้วย F ในช่วง [0.4, 1.0] และปรับแต่งตามประสบการณ์
- การละเลยหรือระบุขอบเขตการค้นหาผิดพลาดเป็นข้อผิดพลาดร้ายแรง — DE ใช้ขอบเขตในการเริ่มต้นประชากรและจะให้ผลลัพธ์ที่ไม่มีความหมายหากขอบเขตแคบเกินไปหรือไม่มีอยู่
- การถือว่ารัน DE เพียงครั้งเดียวก็เพียงพอมีความเสี่ยงในพื้นที่ที่มีหลายจุดเหมาะสมที่สุดเฉพาะที่ — ควรทำการทดลองอิสระหลายครั้งโดยเริ่มจากค่าเริ่มต้นแบบสุ่มที่แตกต่างกัน และรายงานค่าที่ดีที่สุดที่พบจากการรันทั้งหมด
คำถามที่พบบ่อย
ฉันจะเลือกตัวคูณขนาด F และอัตราการครอสโอเวอร์ CR ได้อย่างไร?
ค่าเริ่มต้นที่อ้างอิงกันมากที่สุดคือ F = 0.8 และ CR = 0.9 สำหรับกลยุทธ์ DE/best/1/bin ในทางปฏิบัติ F ควบคุมขนาดของก้าว — ค่าประมาณ 0.4–1.0 เป็นค่าทั่วไป — และ CR ควบคุมว่าเวกเตอร์กลายพันธุ์จะเข้ามาแทนที่เวกเตอร์เป้าหมายมากน้อยเพียงใด หากประชากรลู่เข้าเร็วเกินไป ให้เพิ่ม F หรือลด CR รูปแบบ DE ที่ปรับอัตโนมัติ (adaptive DE variants) เช่น jDE, JADE จะปรับพารามิเตอร์เหล่านี้โดยอัตโนมัติระหว่างการรัน ซึ่งเป็นทางเลือกที่สมเหตุสมผลเมื่อการปรับแต่งด้วยตนเองไม่สามารถทำได้จริง
ต้องใช้จำนวนรุ่นกี่รุ่น?
ตามกฎทั่วไป แนะนำให้ใช้จำนวนรุ่นอย่างน้อย 1,000 รุ่น สำหรับปัญหาที่มีมิติสูง (พารามิเตอร์จำนวนมาก) หรือพื้นที่การค้นหาที่ซับซ้อน อาจจำเป็นต้องใช้จำนวนรอบที่มากขึ้น ให้สังเกตค่าวัตถุประสงค์ของโซลูชันที่ดีที่สุดตลอดหลายรุ่น: หากไม่มีการเปลี่ยนแปลงเป็นเวลาหลายร้อยรอบ แสดงว่า DE น่าจะลู่เข้าแล้ว — หรือติดขัด (stagnated) ในกรณีนี้ การรันใหม่ด้วยค่าเริ่มต้นแบบสุ่มใหม่จะเหมาะสม
DE เปรียบเทียบกับ Genetic Algorithms และ Particle Swarm Optimisation อย่างไร?
ทั้งสามวิธีเป็นอภิวิธีที่ใช้ประชากรสำหรับการหาค่าเหมาะที่สุดแบบต่อเนื่อง โดยทั่วไป DE ใช้พารามิเตอร์ควบคุมน้อยกว่า GA และมีกฎการอัปเดตที่ง่ายกว่าและแน่นอนกว่าเมื่อเทียบกับ PSO ในชุดทดสอบเปรียบเทียบ (benchmark) มาตรฐานหลายชุด DE มีประสิทธิภาพเทียบเคียงได้หรือดีกว่าทั้งสองวิธี แต่ประสิทธิภาพขึ้นอยู่กับปัญหา การเลือกระหว่างวิธีเหล่านี้มักขึ้นอยู่กับความคุ้นเคยและการใช้งานที่มีอยู่ มากกว่าการจัดอันดับที่ครอบคลุมทุกกรณี
DE สามารถจัดการกับพารามิเตอร์ที่เป็นจำนวนเต็มหรือประเภทได้หรือไม่?
DE ถูกออกแบบมาสำหรับปริภูมิแบบต่อเนื่อง สามารถรองรับพารามิเตอร์จำนวนเต็มได้โดยการปัดเศษคำตอบแบบต่อเนื่องเป็นจำนวนเต็มที่ใกล้ที่สุดหลังจากการอัปเดตแต่ละครั้ง แต่นี่เป็นการประมาณค่า ปัญหาที่เกี่ยวกับประเภท (categorical) หรือการจัดหมู่ (combinatorial) โดยเฉพาะ เช่น การจัดตารางเวลา (scheduling) หรือการกำหนดเส้นทาง (routing) จะเหมาะสมกว่าหากใช้วิธีการที่ออกแบบมาสำหรับปริภูมิแบบไม่ต่อเนื่อง (discrete spaces) เช่น Ant Colony Optimisation หรือ Tabu Search
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Storn, R. & Price, K. (1997). Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization, 11(4), 341–359.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วDas, S., Mullick, S. S., & Suganthan, P. N. (2016). Recent advances in differential evolution – An updated survey. Swarm and Evolutionary Computation, 27, 1–30.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว