โครงข่ายประสาทเทียม - อัลกอริทึมทางพันธุกรรม
ธรรมชาติเป็นแหล่งที่มาของแรงบันดาลใจที่ดีสำหรับมวลมนุษยชาติ Genetic Algorithms (GAs) คืออัลกอริธึมที่ใช้การค้นหาตามแนวคิดของการคัดเลือกโดยธรรมชาติและพันธุศาสตร์ GAs เป็นชุดย่อยของสาขาการคำนวณที่ใหญ่กว่าที่เรียกว่าEvolutionary Computation.
GAs ได้รับการพัฒนาโดย John Holland และนักศึกษาและเพื่อนร่วมงานของเขาที่ University of Michigan โดยเฉพาะอย่างยิ่ง David E.Goldberg และได้รับการทดลองในปัญหาการเพิ่มประสิทธิภาพต่างๆพร้อมกับความสำเร็จในระดับสูง
ใน GAs เรามีกลุ่มหรือกลุ่มของวิธีแก้ปัญหาที่เป็นไปได้สำหรับปัญหาที่กำหนด จากนั้นวิธีการแก้ปัญหาเหล่านี้จะผ่านการรวมตัวกันใหม่และการกลายพันธุ์ (เช่นเดียวกับในพันธุศาสตร์ตามธรรมชาติ) ผลิตลูกใหม่และกระบวนการนี้ซ้ำแล้วซ้ำอีกในหลายชั่วอายุคน แต่ละคน (หรือวิธีการแก้ปัญหาของผู้สมัคร) จะได้รับการกำหนดค่าสมรรถภาพ (ตามค่าฟังก์ชันวัตถุประสงค์) และบุคคลที่มีความเหมาะสมจะได้รับโอกาสที่สูงกว่าในการผสมพันธุ์และให้ผลตอบแทนแก่บุคคลที่ "ช่างฟิต" มากขึ้น ซึ่งสอดคล้องกับทฤษฎีดาร์วินเรื่อง“ Survival of the Fittest”
ด้วยวิธีนี้เราจะ“ พัฒนา” บุคคลหรือแนวทางแก้ไขที่ดีขึ้นเรื่อย ๆ มาหลายชั่วอายุคนจนกว่าจะถึงเกณฑ์ที่หยุดชะงัก
อัลกอริทึมทางพันธุกรรมมีการสุ่มอย่างเพียงพอในลักษณะ แต่จะทำงานได้ดีกว่าการค้นหาในพื้นที่แบบสุ่มมาก (ซึ่งเราลองใช้วิธีการสุ่มแบบต่างๆเพื่อติดตามสิ่งที่ดีที่สุดจนถึงตอนนี้) เนื่องจากใช้ประโยชน์จากข้อมูลในอดีตเช่นกัน
ข้อดีของ GAs
GAs มีข้อดีหลายประการซึ่งทำให้พวกเขาได้รับความนิยมอย่างกว้างขวาง สิ่งเหล่านี้ ได้แก่ -
ไม่ต้องการข้อมูลอนุพันธ์ใด ๆ (ซึ่งอาจไม่มีให้สำหรับปัญหาในโลกแห่งความเป็นจริง)
เร็วขึ้นและมีประสิทธิภาพมากขึ้นเมื่อเทียบกับวิธีการแบบเดิม
มีความสามารถแบบขนานที่ดีมาก
ปรับฟังก์ชั่นทั้งแบบต่อเนื่องและไม่ต่อเนื่องตลอดจนปัญหาหลายวัตถุประสงค์
แสดงรายการโซลูชันที่ "ดี" ไม่ใช่แค่โซลูชันเดียว
มักจะได้รับคำตอบสำหรับปัญหาซึ่งจะดีขึ้นเมื่อเวลาผ่านไป
มีประโยชน์เมื่อพื้นที่ค้นหามีขนาดใหญ่มากและมีพารามิเตอร์จำนวนมากที่เกี่ยวข้อง
ข้อ จำกัด ของ GAs
เช่นเดียวกับเทคนิคอื่น ๆ GAs ก็มีข้อ จำกัด บางประการเช่นกัน สิ่งเหล่านี้ ได้แก่ -
GAs ไม่เหมาะกับทุกปัญหาโดยเฉพาะปัญหาที่เรียบง่ายและมีข้อมูลอนุพันธ์
ค่าฟิตเนสจะคำนวณซ้ำ ๆ ซึ่งอาจมีราคาแพงในการคำนวณสำหรับปัญหาบางอย่าง
การสุ่มตัวอย่างจะไม่มีการรับประกันเกี่ยวกับความเหมาะสมหรือคุณภาพของโซลูชัน
หากไม่ได้ติดตั้งอย่างถูกต้อง GA อาจไม่รวมเข้ากับโซลูชันที่เหมาะสมที่สุด
GA - แรงจูงใจ
อัลกอริทึมทางพันธุกรรมมีความสามารถในการนำเสนอโซลูชันที่ "ดีเพียงพอ" "เร็วพอ" สิ่งนี้ทำให้ Gas น่าสนใจสำหรับใช้ในการแก้ปัญหาการเพิ่มประสิทธิภาพ เหตุผลที่ GAs จำเป็นมีดังต่อไปนี้ -
การแก้ปัญหาที่ยาก
ในวิทยาการคอมพิวเตอร์มีปัญหาชุดใหญ่ซึ่ง ได้แก่ NP-Hard. สิ่งนี้หมายความว่าโดยพื้นฐานแล้วแม้แต่ระบบคอมพิวเตอร์ที่ทรงพลังที่สุดก็ใช้เวลานานมาก (เป็นปี!) ในการแก้ปัญหานั้น ในสถานการณ์เช่นนี้ GAs พิสูจน์แล้วว่าเป็นเครื่องมือที่มีประสิทธิภาพในการจัดหาusable near-optimal solutions ในช่วงเวลาสั้น ๆ
ความล้มเหลวของวิธีการไล่ระดับสี
วิธีการที่ใช้แคลคูลัสแบบดั้งเดิมทำงานโดยเริ่มต้นที่จุดสุ่มและโดยการเคลื่อนที่ไปตามทิศทางของการไล่ระดับสีจนกว่าเราจะไปถึงยอดเขา เทคนิคนี้มีประสิทธิภาพและใช้ได้ผลดีกับฟังก์ชันวัตถุประสงค์จุดยอดเดียวเช่นฟังก์ชันต้นทุนในการถดถอยเชิงเส้น อย่างไรก็ตามในสถานการณ์จริงส่วนใหญ่เรามีปัญหาที่ซับซ้อนมากที่เรียกว่าภูมิประเทศซึ่งประกอบด้วยยอดเขาจำนวนมากและหุบเขาจำนวนมากซึ่งทำให้วิธีการดังกล่าวล้มเหลวเนื่องจากพวกเขาต้องทนทุกข์ทรมานจากแนวโน้มที่จะติดอยู่ที่ Optima ในท้องถิ่นดังที่แสดง ในรูปต่อไปนี้
รับทางออกที่ดีอย่างรวดเร็ว
ปัญหาที่ยากบางอย่างเช่นปัญหาพนักงานขายการเดินทาง (TSP) มีแอปพลิเคชันในโลกแห่งความเป็นจริงเช่นการค้นหาเส้นทางและการออกแบบ VLSI ลองนึกภาพว่าคุณกำลังใช้ระบบการนำทางด้วย GPS และใช้เวลาสองสามนาที (หรือสองสามชั่วโมง) ในการคำนวณเส้นทางที่ "เหมาะสมที่สุด" จากต้นทางไปยังปลายทาง ความล่าช้าในแอปพลิเคชันในโลกแห่งความเป็นจริงนั้นไม่สามารถยอมรับได้ดังนั้นโซลูชันที่ "ดีเพียงพอ" ซึ่งส่งมอบให้ "เร็ว" จึงเป็นสิ่งที่จำเป็น
วิธีใช้ GA สำหรับปัญหาการเพิ่มประสิทธิภาพ
เราทราบดีอยู่แล้วว่าการเพิ่มประสิทธิภาพเป็นการกระทำเพื่อให้บางสิ่งบางอย่างเช่นการออกแบบสถานการณ์ทรัพยากรและระบบมีประสิทธิภาพมากที่สุด กระบวนการเพิ่มประสิทธิภาพจะแสดงในแผนภาพต่อไปนี้
ขั้นตอนของกลไก GA สำหรับกระบวนการเพิ่มประสิทธิภาพ
ต่อไปนี้เป็นขั้นตอนของกลไก GA เมื่อใช้เพื่อเพิ่มประสิทธิภาพของปัญหา
สร้างประชากรเริ่มต้นแบบสุ่ม
เลือกโซลูชันเริ่มต้นที่มีค่าสมรรถภาพที่ดีที่สุด
รวมโซลูชันที่เลือกใหม่โดยใช้ตัวดำเนินการการกลายพันธุ์และครอสโอเวอร์
แทรกลูกหลานเข้าไปในประชากร
ตอนนี้หากตรงตามเงื่อนไขการหยุดแล้วให้ส่งคืนโซลูชันที่มีค่าสมรรถภาพที่ดีที่สุด จากนั้นไปที่ขั้นตอนที่ 2