Skip to content
กลับไปยังผลการค้นหา

กลยุทธ์เชิงวิวัฒนาการ (CMA-ES) — การปรับเมทริกซ์ความแปรปรวนร่วม (Evolutionary Strategy: Covariance Matrix Adaptation)

ผู้เสนอ
Nikolaus Hansen & Andreas Ostermeier
ปี
2001
ประเภท
Derivative-free continuous black-box optimizer

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

CMA-ES ซึ่งย่อมาจาก Covariance Matrix Adaptation Evolution Strategy เป็นตัวหาค่าเหมาะที่สุดแบบไม่ใช้อนุพันธ์ (derivative-free optimizer) สำหรับฟังก์ชันกล่องดำแบบต่อเนื่อง (continuous black-box functions) ที่พัฒนาขึ้นโดย Hansen และ Ostermeier ในปี 2001 โดยจะรักษาประชากรของคำตอบที่เป็นไปได้ซึ่งสุ่มมาจาก การแจกแจงแบบปกติหลายตัวแปร (multivariate normal distribution) และปรับปรุงค่าเฉลี่ย ขนาดก้าว (step size) และเมทริกซ์ความแปรปรวนร่วม (covariance matrix) ทั้งหมดอย่างต่อเนื่อง เพื่อนำทางการค้นหาไปยังบริเวณที่ดีขึ้นของปริภูมิพารามิเตอร์ (parameter space) ปัจจุบัน CMA-ES ได้กลายเป็นมาตรฐานโดยพฤตินัย (de-facto standard) สำหรับการหาค่าเหมาะที่สุดของฟังก์ชันกล่องดำแบบต่อเนื่อง และถูกนำไปใช้อย่างแพร่หลายในการค้นหาโครงสร้างสถาปัตยกรรมประสาท (neural architecture search) และการหาค่าเหมาะที่สุดของนโยบายในการเรียนรู้แบบเสริมกำลัง (reinforcement-learning policy optimization)

แนวคิดเบื้องหลังวิธีการ

ลองจินตนาการว่าคุณกำลังค้นหาจุดที่ต่ำที่สุดในภูมิประเทศที่เป็นภูเขา แต่คุณไม่สามารถมองเห็นภูมิประเทศได้ คุณทำได้เพียงสำรวจตำแหน่งต่างๆ และทราบระดับความสูงของแต่ละตำแหน่ง CMA-ES ทำงานเหมือนฝูงที่ถูกนำทาง: มันจะปล่อยกลุ่มของจุดสำรวจรอบๆ การประมาณค่าที่ดีที่สุดในปัจจุบัน วัดว่าแต่ละจุดสำรวจดีเพียงใด จากนั้นจึงปรับรูปร่างของกลุ่มสำหรับการดำเนินการรอบถัดไป กลุ่มนี้ไม่ใช่ทรงกลมธรรมดา แต่จะเรียนรู้รูปร่างที่ยาวและเอียงของหุบเขาที่กำลังลงไป โดยจดจำทิศทางที่นำไปสู่การปรับปรุง เมื่อเวลาผ่านไปหลายรุ่น กลุ่มจะแคบลงและเอียงเพื่อจัดแนวกับความโค้งของพื้นผิวฟังก์ชันสูญเสีย (loss surface) ทำให้ขั้นตอนวิธีสามารถนำทางในหุบเขาที่ยาวและแคบซึ่งจะทำให้วิธีการที่ง่ายกว่าติดขัดได้

ประวัติศาสตร์

กลยุทธ์วิวัฒนาการ (Evolution strategies) ถูกนำเสนอในช่วงทศวรรษ 1960 และ 1970 ในฐานะกลุ่มของตัวหาค่าเหมาะที่สุดแบบอิงประชากรที่ได้รับแรงบันดาลใจจากวิวัฒนาการทางชีววิทยา กลไกการปรับเมทริกซ์ความแปรปรวนร่วมได้รับการพัฒนาโดย Hansen และ Ostermeier และอธิบายไว้อย่างสมบูรณ์ในบทความ Evolutionary Computation ปี 2001 ซึ่งแสดงให้เห็นว่าการปรับตัวเองแบบสมบูรณ์โดยไม่มีการสุ่ม (completely derandomized self-adaptation) — การเรียนรู้เรขาคณิตอันดับสองเต็มรูปแบบของภูมิประเทศการค้นหาจากประวัติของขั้นตอนที่ประสบความสำเร็จ — มีประสิทธิภาพเหนือกว่ากลยุทธ์วิวัฒนาการก่อนหน้านี้อย่างมากในปัญหาที่มีเงื่อนไขไม่ดีและไม่สามารถแยกได้ (non-separable problems) บทแนะนำในปี 2016 ของ Hansen ได้รวบรวมขั้นตอนวิธีและคุณสมบัติทางทฤษฎี ทำให้ CMA-ES เป็นวิธีการอ้างอิงมาตรฐานสำหรับการวัดประสิทธิภาพการหาค่าเหมาะที่สุดของฟังก์ชันกล่องดำแบบต่อเนื่อง

ควรใช้เมื่อใด

CMA-ES เหมาะสมเมื่อฟังก์ชันวัตถุประสงค์เป็นแบบต่อเนื่อง (continuous) อาจไม่เป็นนูน (non-convex) มีหลายค่าเหมาะสม (multimodal) หรือมีสัญญาณรบกวน (noisy) และเมื่อข้อมูลอนุพันธ์ไม่พร้อมใช้งานหรือมีค่าใช้จ่ายสูงเกินไปในการคำนวณ ช่วงมิติที่เหมาะสมคือประมาณ 10 ถึง 1000 พารามิเตอร์ ต่ำกว่า 10 มิติ วิธีการที่ง่ายกว่ามักจะเพียงพอ และสูงกว่า 1000 มิติ ค่าใช้จ่ายหน่วยความจำแบบกำลังสองของเมทริกซ์ความแปรปรวนร่วมอาจกลายเป็นข้อจำกัด ไม่มีความต้องการขนาดตัวอย่างขั้นต่ำในเชิงสถิติ ขั้นตอนวิธีจะสร้างจุดประเมินของตนเอง CMA-ES เหมาะสมโดยธรรมชาติสำหรับการปรับแต่งไฮเปอร์พารามิเตอร์ (hyperparameter tuning) การค้นหาโครงสร้างสถาปัตยกรรมประสาท การหาค่าเหมาะที่สุดของนโยบายในการเรียนรู้แบบเสริมกำลัง และปัญหาการออกแบบทางวิศวกรรมที่ตัวจำลองให้ผลลัพธ์แบบกล่องดำเท่านั้น

ข้อจำกัดและข้อควรพิจารณา

  • ต้นทุนหน่วยความจำแบบกำลังสองและต้นทุนการคำนวณต่อรุ่นตามจำนวนมิติ จำกัดการใช้งานเกินกว่าประมาณ 1000 พารามิเตอร์โดยไม่มีรูปแบบการลดมิติ (dimensionality-reduction variants)
  • ลู่เข้าสู่ค่าเหมาะสมเฉพาะที่ (local optimum) หากไม่มีการเริ่มต้นใหม่ สำหรับภูมิประเทศที่มีหลายค่าเหมาะสม (highly multimodal landscapes) จำเป็นต้องมีการเริ่มต้นใหม่หลายครั้ง (IPOP-CMA-ES หรือ BIPOP-CMA-ES)
  • ไม่เหมาะสำหรับปริภูมิการค้นหาแบบไม่ต่อเนื่อง (discrete) หรือแบบผสม (combinatorial) — วิธีการนี้ถูกกำหนดโดยธรรมชาติบนเวกเตอร์ค่าจริงแบบต่อเนื่อง

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • ไม่ต้องการข้อมูลอนุพันธ์ — ทำงานได้กับฟังก์ชันวัตถุประสงค์ที่เรียกใช้ได้ทุกประเภท รวมถึงฟังก์ชันที่มีสัญญาณรบกวนหรืออิงจากการจำลอง
  • เรียนรู้ความโค้งเฉพาะที่ของภูมิประเทศการค้นหาผ่านการปรับเมทริกซ์ความแปรปรวนร่วม ทำให้สามารถนำทางในปริภูมิการค้นหาที่ยาวและมีเงื่อนไขไม่ดี (ill-conditioned) ซึ่งวิธีการแบบไม่มีอนุพันธ์ที่มีการแจกแจงการค้นหาคงที่ (fixed search distributions) ไม่สามารถทำได้
  • ไม่เปลี่ยนแปลงตามการแปลงฟังก์ชันวัตถุประสงค์ที่รักษาลำดับ (order-preserving transformations) และการหมุนของปริภูมิการค้นหา ทำให้มีความทนทานต่อรูปทรงปัญหาที่หลากหลาย
  • เหมาะสมสำหรับปัญหาแบบต่อเนื่องที่มีมิติปานกลางถึงสูง (10–1000 พารามิเตอร์) โดยมีไฮเปอร์พารามิเตอร์ที่ปรับได้เพียงตัวเดียว คือ ขนาดก้าวเริ่มต้น

การประยุกต์ใช้

  • การปรับแต่งไฮเปอร์พารามิเตอร์สำหรับแบบจำลองการเรียนรู้ของเครื่อง (machine-learning models) รวมถึงสถาปัตยกรรมโครงข่ายประสาทเทียม (neural network architectures) และตัวแทนการเรียนรู้แบบเสริมกำลัง (reinforcement-learning agents)
  • การค้นหาโครงสร้างสถาปัตยกรรมประสาท — การหาค่าเหมาะที่สุดของพารามิเตอร์สถาปัตยกรรมที่เข้ารหัสแบบไม่ต่อเนื่อง (discrete-encoded architecture parameters) ผ่านการคลายเงื่อนไขให้เป็นแบบต่อเนื่อง (continuous relaxation)
  • การหาค่าเหมาะที่สุดของนโยบายในการเรียนรู้แบบเสริมกำลัง เมื่อนโยบายถูกกำหนดโดยเวกเตอร์แบบต่อเนื่อง
  • การหาค่าเหมาะที่สุดในการออกแบบทางวิศวกรรม เช่น การหาค่าเหมาะที่สุดของรูปทรงอากาศพลศาสตร์ (aerodynamic shape optimization) และการปรับพารามิเตอร์โครงสร้าง (structural parameter fitting) ซึ่งมีเพียงผลลัพธ์จากตัวจำลองเท่านั้นที่พร้อมใช้งาน
  • การปรับเทียบแบบจำลองทางวิทยาศาสตร์ — การปรับแบบจำลองการจำลองให้เข้ากับข้อมูลจากการทดลอง เมื่อฟังก์ชันความควรจะเป็น (likelihood) ไม่สามารถหาอนุพันธ์ได้ หรือมีค่าใช้จ่ายในการคำนวณสูง

วิธีการทำงาน

วิธีการทำงาน

1

ขั้นตอนวิธีเริ่มต้นด้วยเวกเตอร์คำตอบเริ่มต้น (initial solution vector) และขนาดก้าวเริ่มต้น (initial step size) (sigma) เมทริกซ์ความแปรปรวนร่วมเริ่มต้นด้วยเมทริกซ์เอกลักษณ์ (identity matrix) ซึ่งเปรียบเสมือนกลุ่มการค้นหาที่เป็นทรงกลมสมบูรณ์ ขนาดประชากร (population size) ถูกกำหนด โดยทั่วไปจะอยู่ที่ประมาณ 4 + floor(3 * ln(dimension))

2

ในแต่ละรุ่น จะมีการสุ่มตัวอย่างประชากรของคำตอบที่เป็นไปได้จากการแจกแจงแบบปกติหลายตัวแปรในปัจจุบัน ซึ่งกำหนดโดยเวกเตอร์ค่าเฉลี่ย ขนาดก้าว และเมทริกซ์ความแปรปรวนร่วม เนื่องจากเป็นการแจกแจงแบบปกติหลายตัวแปร ตัวอย่างที่สุ่มได้จะสะท้อนทั้งค่าประมาณที่ดีที่สุดในปัจจุบันและรูปร่างที่เรียนรู้ของปริภูมิการค้นหา

3

คำตอบที่เป็นไปได้แต่ละรายการจะถูกส่งไปยังฟังก์ชันวัตถุประสงค์ (objective function) และได้รับคะแนนความเหมาะสม (fitness score) ไม่จำเป็นต้องใช้ข้อมูลอนุพันธ์ (gradient information) เพียงแค่ค่าของฟังก์ชันตามสเกล ณ จุดที่สุ่มแต่ละจุดเท่านั้น ทำให้ CMA-ES เหมาะสำหรับวัตถุประสงค์ที่มีสัญญาณรบกวน (noisy) ไม่สามารถหาอนุพันธ์ได้ (non-differentiable) และอิงจากการจำลอง (simulation-based)

4

ค่าเฉลี่ยจะถูกเลื่อนไปยังคำตอบที่มีอันดับดีกว่า เมทริกซ์ความแปรปรวนร่วมและขนาดก้าวจะถูกปรับปรุงโดยใช้สองเส้นทางการปรับปรุงที่เสริมกัน ได้แก่ การปรับปรุงแบบอันดับหนึ่ง (rank-one) และอันดับมิว (rank-mu) เพื่อให้ทิศทางที่ให้ผลลัพธ์ที่ดีมีแนวโน้มที่จะเกิดขึ้นมากขึ้นในรุ่นถัดไป นี่คือกลไกหลักที่ CMA-ES เรียนรู้เรขาคณิตเฉพาะที่ของภูมิประเทศการค้นหา

5

ขั้นตอนวิธีจะทำซ้ำวงจรการสุ่ม-ประเมิน-ปรับปรุง จนกว่าจะถึงเกณฑ์การหยุด: จำนวนการประเมินฟังก์ชันสูงสุด (maximum number of function evaluations) ค่าความคลาดเคลื่อนของการเปลี่ยนแปลงค่าเฉลี่ยหรือขนาดก้าว หรือการตรวจพบการเสื่อมสภาพของเมทริกซ์ความแปรปรวนร่วม คำตอบที่ดีที่สุดที่พบตลอดทุกรุ่นจะถูกส่งคืน

ข้อผิดพลาดที่พบบ่อย

  • การตั้งค่าขนาดก้าวเริ่มต้น (sigma) ให้เล็กเกินไปจะทำให้การค้นหาติดอยู่ในบริเวณใกล้เคียงที่แคบและขัดขวางการสำรวจ หากใหญ่เกินไป รุ่นแรกๆ จะสิ้นเปลืองการประเมินผลที่ห่างไกลจากค่าที่เหมาะสม กฎทั่วไปที่ใช้กันคือการตั้งค่า sigma เพื่อให้ค่าที่เหมาะสมที่คาดหวังอยู่ภายในระยะประมาณสาม sigma ของจุดเริ่มต้น
  • การใช้ CMA-ES กับปัญหาที่มีมิติต่ำมาก (น้อยกว่าห้าพารามิเตอร์) มักเป็นการสิ้นเปลือง — การค้นหาแบบตาราง (grid search) หรือ Nelder-Mead ที่ง่ายกว่าก็เพียงพอแล้ว และค่าใช้จ่ายในการจัดการประชากรของ CMA-ES ก็ไม่ก่อให้เกิดประโยชน์
  • การรัน CMA-ES เพียงครั้งเดียวบนภูมิประเทศที่มีหลายค่าเหมาะสม มีความเสี่ยงที่จะพลาดค่าเหมาะสมที่สุดโดยรวม (global optimum) ควรใช้กลยุทธ์การเริ่มต้นใหม่หลายครั้ง (multi-start) หรือกลยุทธ์การเริ่มต้นใหม่แบบอิงประชากร (population-based restart strategies) (IPOP/BIPOP) เมื่อทราบว่าภูมิประเทศมีหลายค่าเหมาะสมสูง
  • การถือว่าคำตอบที่ดีที่สุดที่ได้เป็นค่าเหมาะสมที่สุดโดยรวมที่แท้จริงโดยไม่มีการตรวจสอบการเริ่มต้นใหม่เป็นข้อผิดพลาดทั่วไป — ควรยืนยันเสมอด้วยการรันอิสระหลายครั้งเมื่อฟังก์ชันวัตถุประสงค์ไม่เป็นนูนสูง (highly non-convex)

คำถามที่พบบ่อย

CMA-ES แตกต่างจากอัลกอริทึมพันธุกรรม (genetic algorithm) แบบง่ายอย่างไร?

อัลกอริทึมพันธุกรรมแบบคลาสสิกจะรักษาประชากรและใช้การผสมข้าม (crossover) และการกลายพันธุ์ (mutation) ด้วยตัวดำเนินการคงที่ ในทางกลับกัน CMA-ES จะจำลองประชากรเป็นตัวอย่างจากการแจกแจงแบบปกติหลายตัวแปร และปรับการแจกแจงนั้นอย่างต่อเนื่อง — ค่าเฉลี่ย ขนาดก้าว และเมทริกซ์ความแปรปรวนร่วมทั้งหมด — โดยอิงตามคำตอบที่ประสบความสำเร็จ สิ่งนี้ช่วยให้ CMA-ES เรียนรู้รูปร่างของพื้นผิวฟังก์ชันวัตถุประสงค์ และนำทางในปริภูมิที่มีความสัมพันธ์กันและมีเงื่อนไขไม่ดีได้อย่างมีประสิทธิภาพมากกว่าอัลกอริทึมพันธุกรรมที่มีตัวดำเนินการคงที่

CMA-ES รับประกันว่าจะพบค่าเหมาะสมที่สุดโดยรวมหรือไม่?

ไม่ CMA-ES เป็นวิธีการค้นหาเฉพาะที่ (local search method) ในแง่ที่ว่าการรันเพียงครั้งเดียวสามารถลู่เข้าสู่ค่าเหมาะสมเฉพาะที่ได้ สำหรับภูมิประเทศที่มีหลายค่าเหมาะสม ขอแนะนำให้ทำการเริ่มต้นใหม่หลายครั้งอย่างอิสระ — อาจมีการเพิ่มขนาดประชากร (IPOP-CMA-ES) — เพื่อปรับปรุงการครอบคลุมปริภูมิการค้นหา

ไฮเปอร์พารามิเตอร์ใดที่สำคัญที่สุดในการตั้งค่า?

ขนาดก้าวเริ่มต้น sigma เป็นไฮเปอร์พารามิเตอร์ที่มีอิทธิพลมากที่สุดเพียงตัวเดียว หลักการทั่วไปที่ดีคือการตั้งค่า sigma เพื่อให้ค่าที่เหมาะสมที่คาดหวังอยู่ภายในระยะประมาณสาม sigma ของจุดเริ่มต้น ขนาดประชากรและจำนวนการประเมินสูงสุดเป็นการควบคุมรอง สูตรขนาดประชากรเริ่มต้น (4 + floor(3 * ln(dimension))) ทำงานได้ดีในทางปฏิบัติ

CMA-ES สามารถจัดการกับฟังก์ชันวัตถุประสงค์ที่มีสัญญาณรบกวนได้หรือไม่?

ได้ เนื่องจาก CMA-ES ใช้เฉพาะข้อมูลอันดับ (rank-order information) จากประชากร — ไม่ใช่ค่าฟังก์ชันสัมบูรณ์ — จึงมีความทนทานต่อสัญญาณรบกวนค่อนข้างดี สำหรับการประเมินที่มีสัญญาณรบกวนสูง การเพิ่มขนาดประชากรหรือการหาค่าเฉลี่ยของการประเมินหลายครั้งต่อคำตอบหนึ่งรายการสามารถเพิ่มความทนทานได้อีก

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Hansen, N. & Ostermeier, A. (2001). Completely Derandomized Self-Adaptation in Evolutionary Strategies. Evolutionary Computation, 9(2), 159-195.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Hansen, N. (2016). The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว