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), การกำหนดเส้นทางยานพาหนะ และการจัดตารางเรียน ซึ่งปริภูมิการค้นหาแบบผสมผสานมีขนาดใหญ่เกินไปสำหรับการค้นหาแบบครบถ้วน
- การเรียนรู้ของเครื่อง: การปรับแต่งไฮเปอร์พารามิเตอร์, การค้นหาสถาปัตยกรรมโครงข่ายประสาทเทียม และการเลือกคุณลักษณะ
- การวิจัยดำเนินงาน: การปรับให้เหมาะสมของห่วงโซ่อุปทาน, การจัดสรรพอร์ตการลงทุน และการจัดสรรทรัพยากรภายใต้ข้อจำกัดที่ซับซ้อน
- ชีวสารสนเทศ: การจัดเรียงลำดับ, การทำนายโครงสร้างโปรตีน และการอนุมานเครือข่ายควบคุมยีน
วิธีการทำงาน
วิธีการทำงาน
มีการสร้างประชากรของคำตอบที่เป็นไปได้ (สิ่งมีชีวิต) โดยทั่วไปจะสุ่มภายในปริภูมิการค้นหา สิ่งมีชีวิตแต่ละตัวจะเข้ารหัสคำตอบที่เป็นไปได้ เช่น เป็นสายอักขระไบนารี, เวกเตอร์ค่าจริง หรือการเรียงสับเปลี่ยน และขนาดประชากรเป็นพารามิเตอร์สำคัญที่กำหนดว่าปริภูมิการค้นหาจะถูกสุ่มตัวอย่างอย่างกว้างขวางเพียงใดตั้งแต่เริ่มต้น
สิ่งมีชีวิตทุกตัวในประชากรจะถูกให้คะแนนด้วยฟังก์ชันความเหมาะสม (fitness function) ซึ่งวัดว่าคำตอบนั้นดีเพียงใดเมื่อเทียบกับวัตถุประสงค์ของปัญหา ฟังก์ชันความเหมาะสมเป็นองค์ประกอบเฉพาะโดเมนเพียงอย่างเดียวที่ผู้ใช้ต้องจัดหาให้ ซึ่งอาจเป็นมาตรวัดที่คำนวณได้ใด ๆ เช่น ผลลัพธ์จากการจำลอง, สูตรต้นทุน หรือเมตริกข้อผิดพลาดของแบบจำลอง
สิ่งมีชีวิตที่มีความเหมาะสมสูงกว่าจะถูกเลือกเป็นพิเศษเพื่อเป็นพ่อแม่สำหรับรุ่นถัดไป กลไกการคัดเลือกที่พบบ่อย ได้แก่ การคัดเลือกแบบทัวร์นาเมนต์ (tournament selection), การคัดเลือกแบบวงล้อรูเล็ต (roulette-wheel หรือ fitness-proportionate selection) และการคัดเลือกตามอันดับ (rank-based selection) แรงกดดันในการคัดเลือก (selection pressure) ควบคุมความสมดุลระหว่างการใช้ประโยชน์จากคำตอบคุณภาพสูงและการรักษาความหลากหลายของประชากร
พ่อแม่ที่ถูกเลือกจะสร้างลูกหลานผ่านการผสมข้าม (crossover หรือ recombination) ซึ่งส่วนของรหัสพันธุกรรมของพ่อแม่สองตัวจะถูกรวมกันเพื่อสร้างสิ่งมีชีวิตใหม่ และผ่านการกลายพันธุ์ (mutation) ซึ่งมีการเปลี่ยนแปลงแบบสุ่มเล็กน้อยกับยีนแต่ละตัว ความน่าจะเป็นของการผสมข้ามและอัตราการกลายพันธุ์เป็นพารามิเตอร์การปรับแต่งที่สำคัญ: การกลายพันธุ์ที่น้อยเกินไปทำให้เกิดการลู่เข้าก่อนกำหนด (premature convergence) การกลายพันธุ์ที่มากเกินไปจะเปลี่ยนการค้นหาเป็นการเดินสุ่ม (random walk)
วงจรของการประเมิน → การคัดเลือก → การสืบพันธุ์ จะดำเนินต่อไปตามจำนวนรุ่นที่กำหนด หรือจนกว่าจะถึงเกณฑ์การลู่เข้า (เช่น ไม่มีการปรับปรุงในช่วงหลายรุ่น) สิ่งมีชีวิตที่ดีที่สุดที่พบตลอดทุกรุ่นจะถูกส่งคืนเป็นคำตอบ เนื่องจากการลู่เข้าสู่ค่าเหมาะสมที่สุดทั่วโลก (global optimum) ไม่ได้รับการรับประกัน จึงแนะนำให้ทำการรันอิสระหลายครั้งสำหรับปัญหาที่มีความเสี่ยงสูง
ข้อผิดพลาดที่พบบ่อย
- การรันจำนวนรุ่นน้อยเกินไปเป็นข้อผิดพลาดที่พบบ่อยที่สุด: ด้วยจำนวนรุ่นที่ไม่เพียงพอ ขั้นตอนวิธีจะไม่ลู่เข้า ดังนั้นวิธีการเชิงวิเคราะห์หรือวิธีการที่อาศัยการไล่ระดับควรได้รับการพิจารณาเมื่อมีงบประมาณการวนซ้ำน้อย
- การลู่เข้าก่อนกำหนด — การที่ประชากรสูญเสียความหลากหลายเร็วเกินไป — ทำให้เกิดผลลัพธ์ที่เหมาะสมที่สุดเฉพาะที่แต่ไม่เหมาะสมที่สุดทั่วโลก; ควรรักษาระดับขนาดประชากรและอัตราการกลายพันธุ์ให้เพียงพอเพื่อแก้ไขปัญหานี้
- การใช้ฟังก์ชันความเหมาะสมที่กำหนดไม่ดีหรือไม่ถูกต้องจะทำให้เกิดผลลัพธ์ที่ทำให้เข้าใจผิดไม่ว่าขั้นตอนวิธีจะถูกต้องเพียงใด; ควรตรวจสอบความถูกต้องของฟังก์ชันความเหมาะสมอย่างอิสระก่อนที่จะรัน GA
- การใช้ GA กับปัญหาที่ราบรื่นและเป็นนูนซึ่งการไล่ระดับลงหรือการเขียนโปรแกรมเชิงเส้นก็เพียงพอแล้ว จะเป็นการสิ้นเปลืองทรัพยากรการคำนวณและนำความสุ่มที่ไม่จำเป็นเข้ามา
- การรายงานผลลัพธ์จากการรันเพียงครั้งเดียวโดยไม่ตรวจสอบความสามารถในการทำซ้ำ; สำหรับแอปพลิเคชันที่มีความเสี่ยงสูง ควรรันขั้นตอนวิธีหลายครั้งและรายงานการกระจายของผลลัพธ์
คำถามที่พบบ่อย
ขั้นตอนวิธีเชิงพันธุกรรมแตกต่างจากการไล่ระดับลงอย่างไร?
การไล่ระดับลงต้องมีวัตถุประสงค์ที่สามารถหาอนุพันธ์ได้และจะตามการไล่ระดับเฉพาะที่ลงไป ขั้นตอนวิธีเชิงพันธุกรรมต้องการเพียงแค่ว่าความเหมาะสมสามารถคำนวณได้สำหรับคำตอบที่เป็นไปได้ใด ๆ; มันค้นหาโดยการวิวัฒนาการประชากรแทนที่จะตามการไล่ระดับ ดังนั้นจึงสามารถจัดการกับภูมิทัศน์ที่ไม่ต่อเนื่อง, ไม่สามารถหาอนุพันธ์ได้ และมีหลายโหมด ซึ่งการไล่ระดับลงล้มเหลวหรือติดขัด
ฉันต้องใช้จำนวนรุ่นเท่าใดและขนาดประชากรเท่าใด?
ไม่มีกฎสากล; ทั้งสองขึ้นอยู่กับความซับซ้อนของปริภูมิการค้นหา ประชากรที่เล็กเกินไปหรือการรันที่สั้นเกินไปมีความเสี่ยงที่จะเกิดการลู่เข้าก่อนกำหนด ในทางปฏิบัติ จุดเริ่มต้นทั่วไปคือขนาดประชากร 50–200 และจำนวนรุ่น 100–1,000 เป็นที่นิยมในวรรณกรรม แต่ปัญหาที่ท้าทายมักจะต้องใช้มากกว่านั้น ควรตรวจสอบเส้นโค้งการลู่เข้าเสมอแทนที่จะกำหนดเกณฑ์การหยุดแบบสุ่ม
ขั้นตอนวิธีเชิงพันธุกรรมรับประกันว่าจะพบค่าเหมาะสมที่สุดทั่วโลกหรือไม่?
ไม่ GA เป็นระเบียบวิธีฮิวริสติกและไม่รับประกันการลู่เข้าสู่ค่าเหมาะสมที่สุดทั่วโลกในเวลาจำกัด สำหรับการรับประกันแบบกำหนด คุณต้องใช้วิธีการที่แม่นยำ เช่น ตัวแก้ปัญหาการเขียนโปรแกรมจำนวนเต็ม สำหรับการตัดสินใจที่มีความเสี่ยงสูง ควรรัน GA หลายครั้ง รายงานการกระจายของผลลัพธ์ และเปรียบเทียบคำตอบที่ดีที่สุดกับขอบเขตที่ทราบ
ฉันควรเลือก GA เมื่อใดเมื่อเทียบกับการอบอ่อนจำลอง (simulated annealing) หรือการปรับให้เหมาะสมด้วยฝูงอนุภาค (particle swarm optimisation)?
GA มักจะได้รับความนิยมเมื่อคำตอบถูกเข้ารหัสตามธรรมชาติเป็นโครงสร้างแบบผสมผสาน (การเรียงสับเปลี่ยน, สายอักขระไบนารี) หรือเมื่อต้องการส่วนขยายแบบหลายวัตถุประสงค์ การปรับให้เหมาะสมด้วยฝูงอนุภาค มักจะเร็วกว่าในปัญหาแบบต่อเนื่องแบบโหมดเดียว การอบอ่อนจำลองนั้นง่ายต่อการนำไปใช้สำหรับปัญหาแบบผสมผสานที่มีพื้นที่ใกล้เคียงที่กำหนดไว้อย่างดี ในทางปฏิบัติ การเปรียบเทียบวิธีการสองหรือสามวิธีกับตัวอย่างปัญหาขนาดเล็กก่อนที่จะตัดสินใจเลือกวิธีใดวิธีหนึ่งเป็นสิ่งแนะนำ
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้วDeb, K. (2001). Multi-Objective Optimization using Evolutionary Algorithms. Wiley.
ISBN: 9780471873396คัดลอกแล้ว