Genetic Algorithms - บทนำ

Genetic Algorithm (GA) เป็นเทคนิคการเพิ่มประสิทธิภาพตามการค้นหาตามหลักการของ Genetics and Natural Selection. มักใช้เพื่อค้นหาวิธีแก้ปัญหาที่ดีที่สุดหรือใกล้เคียงที่สุดสำหรับปัญหาที่ยากซึ่งอาจต้องใช้เวลาตลอดชีวิตในการแก้ไข มักใช้เพื่อแก้ปัญหาการเพิ่มประสิทธิภาพในการวิจัยและการเรียนรู้ของเครื่อง

ข้อมูลเบื้องต้นเกี่ยวกับการเพิ่มประสิทธิภาพ

การเพิ่มประสิทธิภาพเป็นกระบวนการของ making something better. ในกระบวนการใด ๆ เรามีชุดอินพุตและชุดเอาต์พุตดังแสดงในรูปต่อไปนี้

การเพิ่มประสิทธิภาพหมายถึงการค้นหาค่าของอินพุตในลักษณะที่เราได้รับค่าเอาต์พุตที่ "ดีที่สุด" คำจำกัดความของคำว่า“ ดีที่สุด” จะแตกต่างกันไปในแต่ละปัญหา แต่ในแง่คณิตศาสตร์หมายถึงการเพิ่มหรือลดฟังก์ชันวัตถุประสงค์อย่างน้อยหนึ่งฟังก์ชันโดยการเปลี่ยนพารามิเตอร์อินพุต

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

Genetic Algorithms คืออะไร?

ธรรมชาติเป็นแหล่งที่มาของแรงบันดาลใจที่ดีสำหรับมวลมนุษยชาติ Genetic Algorithms (GAs) เป็นอัลกอริธึมที่ใช้การค้นหาตามแนวคิดของการคัดเลือกโดยธรรมชาติและพันธุศาสตร์ GAs เป็นชุดย่อยของสาขาการคำนวณที่ใหญ่กว่าที่เรียกว่าEvolutionary Computation.

GAs ได้รับการพัฒนาโดย John Holland และนักศึกษาและเพื่อนร่วมงานของเขาที่ University of Michigan โดยเฉพาะอย่างยิ่ง David E.

ใน GAs เรามีไฟล์ pool or a population of possible solutionsกับปัญหาที่กำหนด จากนั้นวิธีการแก้ปัญหาเหล่านี้จะผ่านการรวมตัวกันใหม่และการกลายพันธุ์ (เช่นเดียวกับในพันธุศาสตร์ตามธรรมชาติ) ผลิตลูกใหม่และกระบวนการนี้ซ้ำแล้วซ้ำอีกในชั่วอายุต่างๆ แต่ละคน (หรือวิธีการแก้ปัญหาของผู้สมัคร) จะได้รับการกำหนดค่าสมรรถภาพ (ตามค่าฟังก์ชันวัตถุประสงค์) และบุคคลที่มีความเหมาะสมจะได้รับโอกาสในการผสมพันธุ์และให้ผลตอบแทนที่สูงขึ้น ซึ่งสอดคล้องกับทฤษฎีดาร์วินเรื่อง“ Survival of the Fittest”

ด้วยวิธีนี้เราจะ“ พัฒนา” บุคคลหรือแนวทางแก้ไขที่ดีขึ้นเรื่อย ๆ มาหลายชั่วอายุคนจนกว่าจะถึงเกณฑ์ที่หยุดชะงัก

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

ข้อดีของ GAs

GAs มีข้อดีหลายประการซึ่งทำให้พวกเขาได้รับความนิยมอย่างกว้างขวาง ซึ่ง ได้แก่ -

• ไม่ต้องการข้อมูลอนุพันธ์ใด ๆ (ซึ่งอาจไม่มีให้สำหรับปัญหาในโลกแห่งความเป็นจริง)

• เร็วขึ้นและมีประสิทธิภาพมากขึ้นเมื่อเทียบกับวิธีการแบบเดิม

• มีความสามารถแบบขนานที่ดีมาก

• ปรับฟังก์ชั่นทั้งแบบต่อเนื่องและไม่ต่อเนื่องและปัญหาหลายวัตถุประสงค์

• แสดงรายการโซลูชันที่ "ดี" ไม่ใช่แค่โซลูชันเดียว

• มักจะได้รับคำตอบสำหรับปัญหาซึ่งจะดีขึ้นเมื่อเวลาผ่านไป

• มีประโยชน์เมื่อพื้นที่ค้นหามีขนาดใหญ่มากและมีพารามิเตอร์จำนวนมากที่เกี่ยวข้อง

ข้อ จำกัด ของ GAs

เช่นเดียวกับเทคนิคอื่น ๆ GAs ยังต้องทนทุกข์ทรมานจากข้อ จำกัด บางประการ ซึ่ง ได้แก่ -

• GAs ไม่เหมาะกับทุกปัญหาโดยเฉพาะปัญหาที่เรียบง่ายและมีข้อมูลอนุพันธ์

• ค่าฟิตเนสจะคำนวณซ้ำ ๆ ซึ่งอาจมีราคาแพงในการคำนวณสำหรับปัญหาบางอย่าง

• การสุ่มตัวอย่างจะไม่มีการรับประกันเกี่ยวกับความเหมาะสมหรือคุณภาพของโซลูชัน

• หากไม่ได้ติดตั้งอย่างถูกต้อง GA อาจไม่บรรจบกันเป็นโซลูชันที่เหมาะสมที่สุด

GA - แรงจูงใจ

อัลกอริทึมทางพันธุกรรมมีความสามารถในการนำเสนอโซลูชันที่ "ดีเพียงพอ" "เร็วพอ" สิ่งนี้ทำให้อัลกอริทึมทางพันธุกรรมน่าสนใจสำหรับใช้ในการแก้ปัญหาการเพิ่มประสิทธิภาพ เหตุผลที่ GAs จำเป็นมีดังต่อไปนี้ -

การแก้ปัญหาที่ยาก

ในวิทยาการคอมพิวเตอร์มีปัญหาชุดใหญ่ซึ่ง ได้แก่ NP-Hard. สิ่งนี้หมายความว่าโดยพื้นฐานแล้วแม้แต่ระบบคอมพิวเตอร์ที่ทรงพลังที่สุดก็ใช้เวลานานมาก (เป็นปี!) ในการแก้ปัญหานั้น ในสถานการณ์เช่นนี้ GAs พิสูจน์แล้วว่าเป็นเครื่องมือที่มีประสิทธิภาพในการจัดหาusable near-optimal solutions ในช่วงเวลาสั้น ๆ

ความล้มเหลวของวิธีการไล่ระดับสี

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

รับทางออกที่ดีอย่างรวดเร็ว

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