ขั้นตอนวิธีเชิงพันธุกรรมแบบสุ่ม — การค้นหาแบบวิวัฒนาการเชิงสุ่มเพื่อการปรับให้เหมาะสมที่สุด
- ผู้เสนอ
- Holland, J. H.
- ปี
- 1975
- ประเภท
- Stochastic evolutionary metaheuristic
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
ขั้นตอนวิธีเชิงพันธุกรรมแบบสุ่ม (Stochastic Genetic Algorithm หรือ SGA) เป็นเมตาฮิวริสติกส์แบบประชากรที่เลียนแบบวิวัฒนาการทางชีววิทยา ได้แก่ การคัดเลือก การผสมข้าม และการกลายพันธุ์ เพื่อค้นหาคำตอบที่ใกล้เคียงค่าเหมาะสมที่สุดในปริภูมิที่ซับซ้อน ไม่เป็นเชิงเส้น หรือเชิงการจัดเรียง ตัวดำเนินการเชิงสุ่มของ SGA ทำให้มีความทนทานต่อค่าเหมาะสมที่สุดเฉพาะที่ และสามารถนำไปประยุกต์ใช้ได้อย่างกว้างขวางในด้านวิศวกรรม การจัดตารางเวลา การเรียนรู้ของเครื่อง และการวิจัยดำเนินงาน
แนวคิดเบื้องหลังวิธีการ
ลองจินตนาการถึงประชากรของชุดคำตอบที่เป็นไปได้ที่แข่งขันกันเพื่อความอยู่รอด ชุดคำตอบที่ดีกว่ามีแนวโน้มที่จะถูกเลือกเป็นพ่อแม่มากขึ้น ลูกหลานจะได้รับและผสมผสานลักษณะที่ดีเข้าด้วยกัน ในขณะที่การกลายพันธุ์แบบสุ่มที่เกิดขึ้นเป็นครั้งคราวจะนำความแปลกใหม่เข้ามา กระบวนการนี้จะลู่เข้าสู่บริเวณที่มีคุณภาพสูงของปริภูมิการค้นหาเมื่อผ่านไปหลายชั่วรุ่นโดยไม่จำเป็นต้องใช้ข้อมูลการไล่ระดับ คำว่า “สุ่ม” เน้นย้ำว่าการคัดเลือก การผสมข้าม และการกลายพันธุ์ ล้วนเกี่ยวข้องกับการสุ่มแบบความน่าจะเป็น ซึ่งเป็นสิ่งที่ทำให้ GA แบบดั้งเดิมแตกต่างจากตัวแปรเชิงกำหนดที่หายาก และทำให้มีความสามารถในการค้นหาแบบทั่วโลก
ประวัติศาสตร์
John Holland ได้นำเสนอรากฐานทางทฤษฎีของขั้นตอนวิธีเชิงพันธุกรรมที่มหาวิทยาลัยมิชิแกนในปี 1975 โดยอ้างอิงจากงานก่อนหน้าของ Fraser (1957) เกี่ยวกับระบบพันธุกรรมจำลอง หนังสือเรียนของ David Goldberg ในปี 1989 ทำให้ GA เป็นที่นิยมสำหรับการปรับให้เหมาะสมทางวิศวกรรม ลักษณะเชิงสุ่มของการคัดเลือกได้รับการกำหนดอย่างเป็นทางการผ่านทฤษฎีสกีมา และวิธีการนี้ได้กลายเป็นรากฐานสำคัญของการคำนวณเชิงวิวัฒนาการและปัญญาประดิษฐ์เชิงคำนวณ
ควรใช้เมื่อใด
ใช้ขั้นตอนวิธีเชิงพันธุกรรมแบบสุ่มเมื่อ: (1) ปริภูมิการค้นหามีขนาดใหญ่ มีหลายโหมด หรือไม่ต่อเนื่อง และวิธีการที่อิงการไล่ระดับล้มเหลวหรือไม่สามารถนำมาใช้ได้; (2) ฟังก์ชันวัตถุประสงค์เป็นแบบกล่องดำ มีสัญญาณรบกวน หรือมีค่าใช้จ่ายสูงในการประเมิน แต่สามารถจัดการได้สำหรับการสุ่มตัวอย่างระดับประชากร; (3) ปัญหาเชิงการจัดเรียงหรือจำนวนเต็มผสมขาดตัวแก้ที่แม่นยำและมีประสิทธิภาพ; (4) ชุดคำตอบที่ใกล้เคียงค่าเหมาะสมที่สุดที่พบภายในจำนวนการประเมินที่เหมาะสมเป็นที่ยอมรับ ไม่ควรใช้ SGA เมื่อ: ปัญหาเป็นแบบนูนหรือมีการไล่ระดับและมีค่าใช้จ่ายต่ำ — การปรับให้เหมาะสมแบบคลาสสิกจะลู่เข้าได้เร็วกว่า; เมื่อการประเมินฟังก์ชันมีค่าใช้จ่ายสูงมาก (หลายสิบหรือหลายร้อย) วิธีการที่อิงประชากรอาจใช้ทรัพยากรเกินงบประมาณ; หรือเมื่อต้องการชุดคำตอบที่รับประกันว่าเหมาะสมที่สุด เนื่องจาก GA ไม่มีการรับประกันค่าเหมาะสมที่สุด
ข้อจำกัดและข้อควรพิจารณา
- ไม่มีการรับประกันว่าจะพบค่าเหมาะสมที่สุดทั่วโลก; คุณภาพของชุดคำตอบขึ้นอยู่กับขนาดประชากร การเลือกตัวดำเนินการ และจำนวนรุ่น
- มีค่าใช้จ่ายในการคำนวณสูงเมื่อเทียบกับวิธีการที่อิงการไล่ระดับในปัญหาที่ราบรื่นและมีมิติต่ำ — ต้องมีการประเมินฟังก์ชันจำนวนมาก
- การปรับจูนไฮเปอร์พารามิเตอร์ (ขนาดประชากร อัตราการผสมข้าม อัตราการกลายพันธุ์) ขึ้นอยู่กับปัญหาและมักต้องอาศัยการทดลอง
- การลู่เข้าก่อนกำหนดอาจเกิดขึ้นได้หากแรงกดดันในการคัดเลือกสูงเกินไป หรืออัตราการกลายพันธุ์ต่ำเกินไป ทำให้การค้นหาติดอยู่ในบริเวณที่ด้อยกว่าค่าเหมาะสมที่สุด
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ไม่ต้องการข้อมูลการไล่ระดับ — สามารถใช้ได้กับวัตถุประสงค์แบบกล่องดำ ไม่ต่อเนื่อง หรือไม่สามารถหาอนุพันธ์ได้
- จัดการกับปริภูมิการค้นหาเชิงการจัดเรียง จำนวนเต็มผสม และการเรียงสับเปลี่ยนได้อย่างเป็นธรรมชาติด้วยการเข้ารหัสที่เหมาะสม
- สามารถประมวลผลแบบขนานได้โดยการออกแบบ: ประชากรสามารถประเมินผลแบบขนานได้ ซึ่งช่วยลดเวลาที่ใช้จริง
- ทนทานต่อค่าเหมาะสมที่สุดเฉพาะที่เนื่องจากความหลากหลายของประชากรและการสำรวจแบบสุ่ม
- สามารถขยายได้สูง: ตัวดำเนินการ การเข้ารหัส และรูปแบบการคัดเลือกสามารถปรับแต่งได้สำหรับข้อจำกัดเฉพาะโดเมน
การประยุกต์ใช้
- การจัดตารางงานในโรงงานและการจัดตารางการไหลในการผลิตและโลจิสติกส์
- การเลือกคุณลักษณะและการปรับจูนไฮเปอร์พารามิเตอร์ในกระบวนการเรียนรู้ของเครื่อง
- การปรับให้เหมาะสมโครงสร้างและโทโพโลยีในวิศวกรรมเครื่องกลและโยธา
- ปัญหาพนักงานขายเดินทางและปัญหาการจัดเส้นทางยานพาหนะในการวิจัยดำเนินงาน
- การทำนายโครงสร้างโปรตีนและการค้นพบยาในชีวสารสนเทศ
- การค้นหาสถาปัตยกรรมโครงข่ายประสาทเทียมและการปรับให้เหมาะสมน้ำหนัก
วิธีการทำงาน
วิธีการทำงาน
สร้างประชากรเริ่มต้น N ชุดคำตอบที่เป็นไปได้ (โครโมโซม) แบบสุ่ม หรือโดยการใช้ฮิวริสติกส์ โครโมโซมแต่ละตัวเข้ารหัสจุดที่เป็นไปได้ในปริภูมิการตัดสินใจ ไม่ว่าจะเป็นสายอักขระไบนารี เวกเตอร์จำนวนจริง การเรียงสับเปลี่ยน หรือต้นไม้ ขึ้นอยู่กับการนำเสนอของปัญหาที่เลือก
คำนวณค่าความเหมาะสม f(x_i) สำหรับแต่ละบุคคลในประชากรโดยใช้ฟังก์ชันวัตถุประสงค์ (หรือตัวแทน) ค่าความเหมาะสมจะวัดคุณภาพของชุดคำตอบ ค่าความเหมาะสมที่สูงขึ้นหมายถึงชุดคำตอบที่ดีขึ้น สำหรับปัญหาการหาค่าน้อยที่สุด ค่าความเหมาะสมมักถูกกำหนดให้เป็นส่วนกลับหรือการแปลงของฟังก์ชันต้นทุน
สูตร
f(x_i), \quad i = 1, \ldots, N
ใช้ตัวดำเนินการคัดเลือกแบบสุ่มเพื่อเลือกพ่อแม่ การคัดเลือกแบบวงล้อรูเล็ต (ตามสัดส่วนความเหมาะสม) จะกำหนดความน่าจะเป็นให้กับแต่ละบุคคลตามสัดส่วนของค่าความเหมาะสม การคัดเลือกแบบทัวร์นาเมนต์ การคัดเลือกตามอันดับ และการคัดเลือกแบบชนชั้นนำ เป็นรูปแบบทั่วไปที่ควบคุมแรงกดดันในการคัดเลือก
สูตร
P(\text{select } x_i) = \frac{f(x_i)}{\sum_{j=1}^{N} f(x_j)}ด้วยความน่าจะเป็น p_c (โดยทั่วไปคือ 0.6–0.9) ให้รวมคู่ของพ่อแม่ที่ถูกเลือกเพื่อสร้างลูกหลาน การผสมข้ามแบบจุดเดียว แบบสองจุด หรือแบบสม่ำเสมอ จะแลกเปลี่ยนสารพันธุกรรมระหว่างโครโมโซมของพ่อแม่ สร้างลูกหลานที่ได้รับลักษณะจากทั้งสอง ตัวดำเนินการนี้ขับเคลื่อนการใช้ประโยชน์จากส่วนประกอบที่ดี
ด้วยความน่าจะเป็นที่ต่ำ p_m (โดยทั่วไปคือ 0.001–0.05 ต่อหนึ่งยีน) ให้เปลี่ยนแปลงยีนแต่ละตัวในโครโมโซมลูกหลานแต่ละตัวแบบสุ่ม การกลายพันธุ์รักษาความหลากหลายทางพันธุกรรม ป้องกันการลู่เข้าก่อนกำหนด และทำให้มั่นใจว่าขั้นตอนวิธีสามารถหลีกหนีจากค่าเหมาะสมที่สุดเฉพาะที่ได้ อัตราการกลายพันธุ์เป็นพารามิเตอร์ที่สำคัญซึ่งปรับให้เข้ากับปัญหา
แทนที่ประชากรปัจจุบันด้วยลูกหลาน (การแทนที่แบบรุ่นต่อรุ่น) หรือใช้การปรับปรุงแบบคงที่ ประเมินค่าความเหมาะสมอีกครั้งและทำซ้ำตั้งแต่ขั้นตอนการคัดเลือกจนกว่าจะถึงเกณฑ์การหยุด เช่น จำนวนรุ่นสูงสุด เกณฑ์ค่าความเหมาะสม หรือไม่มีการปรับปรุงในช่วงจำนวนรุ่นที่กำหนด
ข้อผิดพลาดที่พบบ่อย
- การใช้อัตราการกลายพันธุ์ที่สูงเกินไปจะลดประสิทธิภาพของขั้นตอนวิธีลงเป็นการค้นหาแบบสุ่มและทำลายผลกำไรด้านความเหมาะสมที่สะสมมา
- การละเลยการคัดเลือกแบบชนชั้นนำในกลยุทธ์การแทนที่อาจทำให้ชุดคำตอบที่ดีที่สุดที่พบสูญหายไประหว่างรุ่น
- การใช้ตัวดำเนินการผสมข้ามค่าจริงกับปัญหาที่เข้ารหัสแบบไบนารี (หรือในทางกลับกัน) จะทำให้การเข้ารหัสเสียหายและสร้างลูกหลานที่ไม่สามารถใช้งานได้
- การหยุดเร็วเกินไป — จำนวนรุ่นไม่เพียงพอ — เป็นสาเหตุที่พบบ่อยที่สุดของคุณภาพชุดคำตอบที่ไม่ดีในการปฏิบัติจริง
- การละเลยการจัดการข้อจำกัด: การผสมข้ามและการกลายพันธุ์ที่ไม่มีข้อจำกัดมักละเมิดข้อจำกัดของปัญหา; ฟังก์ชันปรับโทษหรือตัวดำเนินการซ่อมแซมต้องถูกสร้างขึ้นอย่างชัดเจน
คำถามที่พบบ่อย
ขั้นตอนวิธีเชิงพันธุกรรมแบบสุ่มแตกต่างจากขั้นตอนวิธีเชิงพันธุกรรมมาตรฐานอย่างไร?
คำว่า 'สุ่ม' เน้นย้ำว่าตัวดำเนินการหลักทั้งหมด — การคัดเลือก การผสมข้าม และการกลายพันธุ์ — เกี่ยวข้องกับการสุ่มแบบความน่าจะเป็น GA แบบดั้งเดิมที่ Holland นำเสนอมีลักษณะเป็นสุ่มโดยธรรมชาติ คำนี้ใช้ในวรรณกรรมจำลอง/การปรับให้เหมาะสมเพื่อแยกความแตกต่างจากตัวแปรเชิงกำหนดที่หายาก (เช่น การรวมกลุ่มแบบกำหนด) และเพื่อชี้แจงว่าพฤติกรรมของขั้นตอนวิธีแตกต่างกันไปในแต่ละรอบเนื่องจากความสุ่ม
ขนาดประชากรควรเป็นเท่าใด?
จุดเริ่มต้นทั่วไปคือ 50–200 บุคคลสำหรับปัญหาที่มีมิติปานกลาง ประชากรที่ใหญ่ขึ้นช่วยเพิ่มความหลากหลายและลดการลู่เข้าก่อนกำหนด แต่เพิ่มต้นทุนการคำนวณต่อรุ่น มีกฎทั่วไปที่อิงตามความยาวโครโมโซม (เช่น 10 เท่าของจำนวนยีน) แต่การปรับจูนเชิงประจักษ์หรือการปรับให้เหมาะสมแบบเมตา มักมีความจำเป็น
ฉันควรเลือกใช้ Particle Swarm Optimization หรือ Simulated Annealing แทน Genetic Algorithm เมื่อใด?
Particle Swarm Optimization (PSO) มักจะเร็วกว่าในปัญหาค่าจริงต่อเนื่องเนื่องจากใช้ประโยชน์จากข้อมูลความเร็ว Simulated Annealing (SA) นั้นง่ายต่อการนำไปใช้และมีประสิทธิภาพสำหรับการค้นหาเส้นทางชุดคำตอบเดียว GA เป็นที่นิยมเมื่อปริภูมิการค้นหาเป็นแบบเชิงการจัดเรียง เมื่อการผสมข้ามรวมโครงสร้างชุดคำตอบได้อย่างมีความหมาย หรือเมื่อความหลากหลายของประชากรมีคุณค่าสำหรับภูมิทัศน์แบบหลายโหมด
ขั้นตอนวิธีเชิงพันธุกรรมแบบสุ่มสามารถปรับขนาดสำหรับปัญหาที่มีมิติสูงได้หรือไม่?
ประสิทธิภาพจะลดลงในมิติที่สูงมาก (หลายร้อยถึงหลายพันตัวแปร) เนื่องจากประชากรต้องมีขนาดใหญ่พอที่จะสุ่มตัวอย่างปริภูมิได้อย่างเพียงพอ ตัวแปรเฉพาะทาง — เช่น GA ที่เรียนรู้การเชื่อมโยง ขั้นตอนวิธีประมาณการกระจาย หรือโมเดลเกาะที่มีการย้ายถิ่น — จัดการกับความสามารถในการปรับขนาดแต่เพิ่มความซับซ้อน
ฉันจะจัดการกับข้อจำกัดใน Genetic Algorithm ได้อย่างไร?
มีสามกลยุทธ์หลักที่ใช้: (1) ฟังก์ชันปรับโทษที่ลดค่าความเหมาะสมสำหรับการละเมิดข้อจำกัด; (2) ตัวดำเนินการซ่อมแซมที่ฉายลูกหลานที่ไม่สามารถใช้งานได้กลับเข้าสู่บริเวณที่สามารถใช้งานได้; (3) การเข้ารหัสและตัวดำเนินการเฉพาะทางที่สร้างเฉพาะชุดคำตอบที่สามารถใช้งานได้โดยการสร้าง วิธีการที่อิงการปรับโทษนั้นง่ายที่สุดในการนำไปใช้ แต่ต้องมีการปรับเทียบสัมประสิทธิ์การปรับโทษอย่างระมัดระวัง
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor.
ISBN: 978-0262581110คัดลอกแล้วGoldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA.
ISBN: 978-0201157673คัดลอกแล้ว