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

Genetic Algorithm — การปรับให้เหมาะสมเชิงวิวัฒนาการ

ผู้เสนอ
John Henry Holland
ปี
1975
ประเภท
Population-based metaheuristic

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

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

ใช้ทำอะไร?

ขั้นตอนวิธีเชิงพันธุกรรม (Genetic Algorithm หรือ GA) เป็นระเบียบวิธีอภิวิธาน (metaheuristic) สำหรับการหาค่าเหมาะสมที่สุดที่อาศัยประชากร (population-based) ซึ่งนำเสนอโดย John Henry Holland (1975) โดยเลียนแบบหลักการของการคัดเลือกโดยธรรมชาติ ขั้นตอนวิธีนี้จะรักษาประชากรของคำตอบที่เป็นไปได้ และปรับปรุงคำตอบเหล่านั้นซ้ำ ๆ ผ่านตัวดำเนินการคัดเลือก (selection), การผสมข้าม (crossover) และการกลายพันธุ์ (mutation) ทำให้มีประสิทธิภาพเป็นพิเศษในปริภูมิการค้นหาที่ไม่ต่อเนื่อง (discontinuous), ไม่เป็นนูน (non-convex) และมีหลายโหมด (multi-modal) ซึ่งระเบียบวิธีที่อาศัยการไล่ระดับแบบดั้งเดิมไม่สามารถทำงานได้

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

ลองจินตนาการว่าคุณมีคำตอบที่เป็นไปได้นับพันสำหรับปัญหาที่ยาก และไม่มีสูตรสำเร็จในการหาคำตอบที่ดีที่สุด ขั้นตอนวิธีเชิงพันธุกรรมจะถือว่าคำตอบที่เป็นไปได้แต่ละคำตอบเป็นสิ่งมีชีวิตหนึ่ง ๆ ในประชากร ในแต่ละรุ่น (generation) ขั้นตอนวิธีจะเก็บสิ่งมีชีวิตที่เหมาะสมที่สุดไว้ ผสมพันธุ์พวกมันเข้าด้วยกันเพื่อรวมลักษณะที่ดี และบางครั้งก็ทำให้ลูกหลานกลายพันธุ์เพื่อเพิ่มความแปลกใหม่ เมื่อผ่านไปหลายรุ่น ประชากรจะค่อย ๆ เคลื่อนเข้าสู่คำตอบที่ดีขึ้นเรื่อย ๆ โดยไม่ได้อาศัยการไล่ระดับ แต่โดยการเลียนแบบวิวัฒนาการที่หล่อหลอมสิ่งมีชีวิตเมื่อเวลาผ่านไป

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

ขั้นตอนวิธีเชิงพันธุกรรมถูกนำเสนอโดย John Henry Holland ในหนังสือของเขา Adaptation in Natural and Artificial Systems ปี 1975 ซึ่งได้กำหนดแนวคิดของ schema (หน่วยโครงสร้าง) และให้การวิเคราะห์ทางทฤษฎีพื้นฐานว่าทำไมการผสมข้ามและการคัดเลือกจึงขับเคลื่อนการค้นหาไปยังภูมิภาคที่เหมาะสมกว่า ลูกศิษย์ของ Holland — โดยเฉพาะ David Goldberg — ทำให้ GA เป็นที่นิยมผ่านการประยุกต์ใช้ทางวิศวกรรมในช่วงทศวรรษ 1980 Kalyanmoy Deb ได้ขยายกรอบแนวคิดนี้ไปยังการตั้งค่าหลายวัตถุประสงค์ในภายหลัง ซึ่งนำไปสู่ขั้นตอนวิธี NSGA-II (2002) ที่ได้รับการยอมรับอย่างกว้างขวาง ปัจจุบัน GA ยังคงเป็นเครื่องมือมาตรฐานในการคำนวณเชิงวิวัฒนาการ โดยมีการวิจัยที่กำลังดำเนินอยู่เกี่ยวกับวิธีการแบบผสมผสานที่รวมการค้นหาเชิงวิวัฒนาการเข้ากับการปรับปรุงเฉพาะที่

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

ขั้นตอนวิธีเชิงพันธุกรรมเหมาะสมเมื่อปริภูมิการค้นหามีขนาดใหญ่, ไม่ต่อเนื่อง, ไม่สามารถหาอนุพันธ์ได้ หรือมีหลายโหมดสูง ซึ่งเป็นสภาวะที่ตัวแก้ปัญหาที่อาศัยการไล่ระดับไม่สามารถทำงานได้หรือติดอยู่ในค่าเหมาะสมที่สุดเฉพาะที่ (local optima) ขั้นตอนวิธีนี้ใช้ได้กับตัวแปรประเภทต่อเนื่อง, เชิงหมวดหมู่, ไบนารี และเชิงอันดับ และไม่กำหนดข้อสมมติฐานเกี่ยวกับการแจกแจงหรือความเป็นปกติ ข้อกำหนดเดียวคือฟังก์ชันความเหมาะสมที่คำนวณได้ สำหรับปัญหาที่มีสูตรเชิงวิเคราะห์หรือเป็นนูน วิธีการแบบดั้งเดิม (การเขียนโปรแกรมเชิงเส้น, การไล่ระดับลง) จะเร็วกว่าและควรได้รับการพิจารณา การวนซ้ำที่เพียงพอ (โดยทั่วไปมากกว่า 1,000 รุ่น) เป็นสิ่งจำเป็นสำหรับการลู่เข้าที่มีความหมาย การรันจำนวนรุ่นน้อยเกินไปเป็นโหมดความล้มเหลวที่พบบ่อยที่สุด

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

  • ไม่รับประกันการลู่เข้าสู่ค่าเหมาะสมที่สุดทั่วโลก; ผลลัพธ์อาจแตกต่างกันไปในการรันแต่ละครั้ง
  • มีค่าใช้จ่ายในการคำนวณสูง: แต่ละรุ่นต้องประเมินประชากรทั้งหมด ซึ่งเป็นสิ่งที่ไม่สามารถทำได้เมื่อฟังก์ชันความเหมาะสมทำงานช้า
  • ประสิทธิภาพมีความไวต่อการเลือกไฮเปอร์พารามิเตอร์ — ขนาดประชากร, ความน่าจะเป็นของการผสมข้าม และอัตราการกลายพันธุ์ — ซึ่งมักจะต้องมีการปรับแต่งเฉพาะปัญหา
  • สำหรับปัญหาที่ราบรื่น, เป็นนูน หรือมีโครงสร้างที่ดี วิธีการที่อาศัยการไล่ระดับแบบดั้งเดิมหรือวิธีการเชิงเส้นจะเร็วกว่าและน่าเชื่อถือกว่า

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

จุดแข็ง

  • ทำงานได้ดีกับภูมิทัศน์วัตถุประสงค์ที่ไม่ต่อเนื่อง, ไม่สามารถหาอนุพันธ์ได้ และมีหลายโหมด ซึ่งวิธีการที่อาศัยการไล่ระดับจะล้มเหลว
  • ไม่กำหนดข้อสมมติฐานเกี่ยวกับการแจกแจง — ข้อมูลนำเข้าที่จำเป็นเพียงอย่างเดียวคือฟังก์ชันความเหมาะสมที่คำนวณได้
  • จัดการกับประเภทตัวแปรที่หลากหลายได้อย่างเป็นธรรมชาติ: ต่อเนื่อง, ไบนารี, เชิงหมวดหมู่ และเชิงอันดับ
  • ความหลากหลายของประชากรช่วยให้สามารถสำรวจหลายภูมิภาคของปริภูมิการค้นหาได้พร้อมกัน ลดความเสี่ยงของการติดอยู่ในค่าเหมาะสมที่สุดเฉพาะที่ก่อนกำหนด
  • สามารถขยายได้สูง: ตัวดำเนินการผสมข้ามและการกลายพันธุ์เฉพาะโดเมน, การจัดการข้อจำกัด และรูปแบบหลายวัตถุประสงค์ (เช่น NSGA-II) เป็นที่ยอมรับอย่างดีในวรรณกรรม

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

  • การปรับให้เหมาะสมการออกแบบทางวิศวกรรม: การค้นหาการกำหนดค่าพารามิเตอร์ที่เหมาะสมที่สุดสำหรับโครงสร้าง, วงจร หรือระบบกลไก
  • ปัญหาการจัดตารางเวลาและการกำหนดเส้นทาง: การจัดตารางการผลิต (job-shop scheduling), การกำหนดเส้นทางยานพาหนะ และการจัดตารางเรียน ซึ่งปริภูมิการค้นหาแบบผสมผสานมีขนาดใหญ่เกินไปสำหรับการค้นหาแบบครบถ้วน
  • การเรียนรู้ของเครื่อง: การปรับแต่งไฮเปอร์พารามิเตอร์, การค้นหาสถาปัตยกรรมโครงข่ายประสาทเทียม และการเลือกคุณลักษณะ
  • การวิจัยดำเนินงาน: การปรับให้เหมาะสมของห่วงโซ่อุปทาน, การจัดสรรพอร์ตการลงทุน และการจัดสรรทรัพยากรภายใต้ข้อจำกัดที่ซับซ้อน
  • ชีวสารสนเทศ: การจัดเรียงลำดับ, การทำนายโครงสร้างโปรตีน และการอนุมานเครือข่ายควบคุมยีน

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

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

1

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

2

สิ่งมีชีวิตทุกตัวในประชากรจะถูกให้คะแนนด้วยฟังก์ชันความเหมาะสม (fitness function) ซึ่งวัดว่าคำตอบนั้นดีเพียงใดเมื่อเทียบกับวัตถุประสงค์ของปัญหา ฟังก์ชันความเหมาะสมเป็นองค์ประกอบเฉพาะโดเมนเพียงอย่างเดียวที่ผู้ใช้ต้องจัดหาให้ ซึ่งอาจเป็นมาตรวัดที่คำนวณได้ใด ๆ เช่น ผลลัพธ์จากการจำลอง, สูตรต้นทุน หรือเมตริกข้อผิดพลาดของแบบจำลอง

3

สิ่งมีชีวิตที่มีความเหมาะสมสูงกว่าจะถูกเลือกเป็นพิเศษเพื่อเป็นพ่อแม่สำหรับรุ่นถัดไป กลไกการคัดเลือกที่พบบ่อย ได้แก่ การคัดเลือกแบบทัวร์นาเมนต์ (tournament selection), การคัดเลือกแบบวงล้อรูเล็ต (roulette-wheel หรือ fitness-proportionate selection) และการคัดเลือกตามอันดับ (rank-based selection) แรงกดดันในการคัดเลือก (selection pressure) ควบคุมความสมดุลระหว่างการใช้ประโยชน์จากคำตอบคุณภาพสูงและการรักษาความหลากหลายของประชากร

4

พ่อแม่ที่ถูกเลือกจะสร้างลูกหลานผ่านการผสมข้าม (crossover หรือ recombination) ซึ่งส่วนของรหัสพันธุกรรมของพ่อแม่สองตัวจะถูกรวมกันเพื่อสร้างสิ่งมีชีวิตใหม่ และผ่านการกลายพันธุ์ (mutation) ซึ่งมีการเปลี่ยนแปลงแบบสุ่มเล็กน้อยกับยีนแต่ละตัว ความน่าจะเป็นของการผสมข้ามและอัตราการกลายพันธุ์เป็นพารามิเตอร์การปรับแต่งที่สำคัญ: การกลายพันธุ์ที่น้อยเกินไปทำให้เกิดการลู่เข้าก่อนกำหนด (premature convergence) การกลายพันธุ์ที่มากเกินไปจะเปลี่ยนการค้นหาเป็นการเดินสุ่ม (random walk)

5

วงจรของการประเมิน → การคัดเลือก → การสืบพันธุ์ จะดำเนินต่อไปตามจำนวนรุ่นที่กำหนด หรือจนกว่าจะถึงเกณฑ์การลู่เข้า (เช่น ไม่มีการปรับปรุงในช่วงหลายรุ่น) สิ่งมีชีวิตที่ดีที่สุดที่พบตลอดทุกรุ่นจะถูกส่งคืนเป็นคำตอบ เนื่องจากการลู่เข้าสู่ค่าเหมาะสมที่สุดทั่วโลก (global optimum) ไม่ได้รับการรับประกัน จึงแนะนำให้ทำการรันอิสระหลายครั้งสำหรับปัญหาที่มีความเสี่ยงสูง

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

  • การรันจำนวนรุ่นน้อยเกินไปเป็นข้อผิดพลาดที่พบบ่อยที่สุด: ด้วยจำนวนรุ่นที่ไม่เพียงพอ ขั้นตอนวิธีจะไม่ลู่เข้า ดังนั้นวิธีการเชิงวิเคราะห์หรือวิธีการที่อาศัยการไล่ระดับควรได้รับการพิจารณาเมื่อมีงบประมาณการวนซ้ำน้อย
  • การลู่เข้าก่อนกำหนด — การที่ประชากรสูญเสียความหลากหลายเร็วเกินไป — ทำให้เกิดผลลัพธ์ที่เหมาะสมที่สุดเฉพาะที่แต่ไม่เหมาะสมที่สุดทั่วโลก; ควรรักษาระดับขนาดประชากรและอัตราการกลายพันธุ์ให้เพียงพอเพื่อแก้ไขปัญหานี้
  • การใช้ฟังก์ชันความเหมาะสมที่กำหนดไม่ดีหรือไม่ถูกต้องจะทำให้เกิดผลลัพธ์ที่ทำให้เข้าใจผิดไม่ว่าขั้นตอนวิธีจะถูกต้องเพียงใด; ควรตรวจสอบความถูกต้องของฟังก์ชันความเหมาะสมอย่างอิสระก่อนที่จะรัน GA
  • การใช้ GA กับปัญหาที่ราบรื่นและเป็นนูนซึ่งการไล่ระดับลงหรือการเขียนโปรแกรมเชิงเส้นก็เพียงพอแล้ว จะเป็นการสิ้นเปลืองทรัพยากรการคำนวณและนำความสุ่มที่ไม่จำเป็นเข้ามา
  • การรายงานผลลัพธ์จากการรันเพียงครั้งเดียวโดยไม่ตรวจสอบความสามารถในการทำซ้ำ; สำหรับแอปพลิเคชันที่มีความเสี่ยงสูง ควรรันขั้นตอนวิธีหลายครั้งและรายงานการกระจายของผลลัพธ์

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

ขั้นตอนวิธีเชิงพันธุกรรมแตกต่างจากการไล่ระดับลงอย่างไร?

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

ฉันต้องใช้จำนวนรุ่นเท่าใดและขนาดประชากรเท่าใด?

ไม่มีกฎสากล; ทั้งสองขึ้นอยู่กับความซับซ้อนของปริภูมิการค้นหา ประชากรที่เล็กเกินไปหรือการรันที่สั้นเกินไปมีความเสี่ยงที่จะเกิดการลู่เข้าก่อนกำหนด ในทางปฏิบัติ จุดเริ่มต้นทั่วไปคือขนาดประชากร 50–200 และจำนวนรุ่น 100–1,000 เป็นที่นิยมในวรรณกรรม แต่ปัญหาที่ท้าทายมักจะต้องใช้มากกว่านั้น ควรตรวจสอบเส้นโค้งการลู่เข้าเสมอแทนที่จะกำหนดเกณฑ์การหยุดแบบสุ่ม

ขั้นตอนวิธีเชิงพันธุกรรมรับประกันว่าจะพบค่าเหมาะสมที่สุดทั่วโลกหรือไม่?

ไม่ GA เป็นระเบียบวิธีฮิวริสติกและไม่รับประกันการลู่เข้าสู่ค่าเหมาะสมที่สุดทั่วโลกในเวลาจำกัด สำหรับการรับประกันแบบกำหนด คุณต้องใช้วิธีการที่แม่นยำ เช่น ตัวแก้ปัญหาการเขียนโปรแกรมจำนวนเต็ม สำหรับการตัดสินใจที่มีความเสี่ยงสูง ควรรัน GA หลายครั้ง รายงานการกระจายของผลลัพธ์ และเปรียบเทียบคำตอบที่ดีที่สุดกับขอบเขตที่ทราบ

ฉันควรเลือก GA เมื่อใดเมื่อเทียบกับการอบอ่อนจำลอง (simulated annealing) หรือการปรับให้เหมาะสมด้วยฝูงอนุภาค (particle swarm optimisation)?

GA มักจะได้รับความนิยมเมื่อคำตอบถูกเข้ารหัสตามธรรมชาติเป็นโครงสร้างแบบผสมผสาน (การเรียงสับเปลี่ยน, สายอักขระไบนารี) หรือเมื่อต้องการส่วนขยายแบบหลายวัตถุประสงค์ การปรับให้เหมาะสมด้วยฝูงอนุภาค มักจะเร็วกว่าในปัญหาแบบต่อเนื่องแบบโหมดเดียว การอบอ่อนจำลองนั้นง่ายต่อการนำไปใช้สำหรับปัญหาแบบผสมผสานที่มีพื้นที่ใกล้เคียงที่กำหนดไว้อย่างดี ในทางปฏิบัติ การเปรียบเทียบวิธีการสองหรือสามวิธีกับตัวอย่างปัญหาขนาดเล็กก่อนที่จะตัดสินใจเลือกวิธีใดวิธีหนึ่งเป็นสิ่งแนะนำ

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

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

  1. Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว
  2. Deb, K. (2001). Multi-Objective Optimization using Evolutionary Algorithms. Wiley.

    ISBN: 9780471873396
    คัดลอกแล้ว