ในด้านปัญญาประดิษฐ์ อัลกอริธึมวิวัฒนาการ (EA) คือชุดย่อยของการคำนวณประชากรทั้งหมดโดยอิงจากการเพิ่มประสิทธิภาพเชิงอภิมาน EA ใช้กลไกที่ได้รับแรงบันดาลใจจากการพัฒนาทางชีววิทยา เช่น การสืบพันธุ์ การกลายพันธุ์ การรวมตัวกันใหม่ และการคัดเลือก วิธีแก้ปัญหาของผู้สมัครในปัญหาของอัลกอริธึมการปรับให้เหมาะสมเชิงวิวัฒนาการเล่นบทบาทของปัจเจกในประชากร และฟังก์ชันฟิตเนสจะกำหนดคุณภาพของคำตอบด้วย
อัลกอรึทึมเชิงวิวัฒนาการมักจะประมาณการแก้ปัญหาทุกประเภทได้ดี เพราะในอุดมคติแล้ว พวกเขาไม่ได้ตั้งสมมติฐานใดๆ เกี่ยวกับแนวฟิตเนสที่เป็นพื้นฐาน วิธีการที่ใช้สำหรับการสร้างแบบจำลองวิวัฒนาการและอัลกอริธึมทางพันธุกรรมมักจะจำกัดเฉพาะการศึกษากระบวนการทางจุลภาคและแบบจำลองการวางแผนตามระยะเซลล์ ในแอปพลิเคชัน EA ส่วนใหญ่ ความซับซ้อนในการคำนวณเป็นปัจจัยห้าม
ที่จริงปัญหานี้เกี่ยวข้องกับการประเมินฟังก์ชันฟิตเนส การประมาณค่าฟิตเนสเป็นวิธีหนึ่งในการเอาชนะความยากลำบากนี้ อย่างไรก็ตาม EA ที่ดูเรียบง่ายสามารถแก้ปัญหาที่ซับซ้อนได้บ่อยครั้ง ดังนั้นจึงไม่มีความสัมพันธ์โดยตรงระหว่างความซับซ้อนของลำดับและปัญหา รายละเอียดเพิ่มเติมสามารถพบได้ในหนังสือ "Evolutionary Algorithms"
การนำไปใช้
ขั้นตอนที่หนึ่งคือการสร้างประชากรเริ่มต้นของบุคคลโดยการสุ่ม
ขั้นตอนที่สองคือการประเมินความเหมาะสมของแต่ละคนในกลุ่มนี้ (จำกัดเวลา ความพร้อมเพียงพอ ฯลฯ)
ขั้นตอนที่สาม - ทำซ้ำขั้นตอนการฟื้นฟูต่อไปนี้เพื่อให้เสร็จสิ้น:
- เลือกคนที่เหมาะสมที่สุดในการผสมพันธุ์ (พ่อแม่).
- นำบุคคลใหม่ที่ผ่านอัลกอริธึมวิวัฒนาการโดยใช้ครอสโอเวอร์และการกลายพันธุ์เพื่อให้ได้ลูกหลาน
- ประเมินความฟิตของคนใหม่
- แทนที่ประชากรที่พอดีน้อยที่สุดด้วย
ประเภท
Genetic Algorithm คือลำดับวิวัฒนาการ ซึ่งเป็นประเภท Expert Advisor ที่ได้รับความนิยมมากที่สุด การแก้ปัญหาจะค้นหาในรูปแบบของสตริงของตัวเลข (ตามธรรมเนียมไบนารีแม้ว่าการแสดงที่ดีที่สุดมักจะเป็นสิ่งที่สะท้อนถึงปัญหาที่กำลังแก้ไขมากขึ้น) โดยใช้ตัวดำเนินการเช่นการรวมตัวใหม่และการกลายพันธุ์ (บางครั้งอาจใช้ทั้งสองอย่างในบางกรณีทั้งสองอย่าง). ที่ปรึกษาผู้เชี่ยวชาญประเภทนี้มักใช้ในปัญหาการปรับให้เหมาะสม อีกชื่อหนึ่งสำหรับสิ่งนี้คือ fetura (จากภาษาละตินสำหรับ "birth"):
- โปรแกรมพันธุกรรม. โดยนำเสนอวิธีแก้ปัญหาเป็นรหัสคอมพิวเตอร์ และความเหมาะสมจะพิจารณาจากความสามารถในการทำงานด้านคอมพิวเตอร์
- การเขียนโปรแกรมเชิงวิวัฒนาการ. คล้ายกับอัลกอริธึมทางพันธุกรรมวิวัฒนาการ แต่โครงสร้างได้รับการแก้ไขและพารามิเตอร์ตัวเลขสามารถเปลี่ยนแปลงได้
- การเขียนโปรแกรมการแสดงออกของยีน พัฒนาแอปพลิเคชันคอมพิวเตอร์ แต่สำรวจระบบจีโนไทป์-ฟีโนไทป์ โดยโปรเจ็กต์ที่มีขนาดต่างกันจะถูกเข้ารหัสบนโครโมโซมเชิงเส้นที่มีความยาวคงที่
- กลยุทธ์. ทำงานกับเวกเตอร์ของจำนวนจริงเพื่อแทนคำตอบ มักใช้อัลกอริธึมอัตราการกลายพันธุ์วิวัฒนาการที่ปรับตัวเองได้
- การพัฒนาความแตกต่าง. อิงตามความแตกต่างของเวกเตอร์และดังนั้นจึงเหมาะสำหรับปัญหาการเพิ่มประสิทธิภาพตัวเลขเป็นหลัก
- วิวัฒนาการของระบบประสาท. คล้ายกับการเขียนโปรแกรมเชิงวิวัฒนาการและอัลกอริธึมทางพันธุกรรม แต่ส่วนหลังเป็นโครงข่ายประสาทเทียม ซึ่งอธิบายโครงสร้างและน้ำหนักของการเชื่อมต่อ การเข้ารหัสจีโนมสามารถโดยตรงหรือโดยอ้อม
เปรียบเทียบกับกระบวนการทางชีววิทยา
ข้อจำกัดที่เป็นไปได้ของอัลกอริธึมวิวัฒนาการจำนวนมากคือการขาดความแตกต่างที่ชัดเจนระหว่างจีโนไทป์และฟีโนไทป์ โดยธรรมชาติแล้ว ไข่ที่ปฏิสนธิต้องผ่านกระบวนการที่ซับซ้อนที่เรียกว่าการกำเนิดของตัวอ่อนเพื่อให้เจริญเติบโต คิดว่าการเข้ารหัสทางอ้อมนี้จะทำให้การค้นหาทางพันธุกรรมมีความน่าเชื่อถือมากขึ้น (กล่าวคือ มีโอกาสน้อยที่จะทำให้เกิดการกลายพันธุ์ที่ร้ายแรง) และอาจช่วยปรับปรุงความสามารถในการพัฒนาของสิ่งมีชีวิตด้วย ทางอ้อมดังกล่าว (กล่าวอีกนัยหนึ่งคือการเข้ารหัสแบบกำเนิดหรือแบบพัฒนา) ยังอนุญาตให้วิวัฒนาการใช้ประโยชน์จากความสม่ำเสมอของสภาพแวดล้อม
งานล่าสุดในการสร้างตัวอ่อนเทียมหรือระบบพัฒนาการพยายามแก้ไขปัญหาเหล่านี้ เมื่อเขียนโปรแกรมการแสดงออกของยีน ขอบเขตของยีน-ฟีโนไทป์จะถูกสำรวจอย่างประสบความสำเร็จ โดยที่ช่วงแรกประกอบด้วยโครโมโซมมัลติยีนเชิงเส้นที่มีความยาวคงที่ และส่วนที่สองของแผนผังการแสดงออกหรือโปรแกรมคอมพิวเตอร์ที่มีขนาดและรูปร่างต่างกัน
เทคนิคที่เกี่ยวข้อง
อัลกอริทึมรวมถึง:
- การเพิ่มประสิทธิภาพอาณานิคมมด ตามแนวคิดที่ว่าแมลงค้นหาอาหารโดยเชื่อมต่อกับฟีโรโมนเพื่อสร้างทางเดิน เหมาะอย่างยิ่งสำหรับการเพิ่มประสิทธิภาพการรวมกันและปัญหากราฟ
- อัลกอริธึมตัวเลื่อนรูท ผู้สร้างได้รับแรงบันดาลใจจากการทำงานของรากพืชในธรรมชาติ
- อัลกอริทึมสำหรับรังผึ้งเทียม ตามพฤติกรรมของผึ้ง มีการเสนอเบื้องต้นสำหรับการเพิ่มประสิทธิภาพเชิงตัวเลขและขยายเพื่อแก้ปัญหาเชิงรวม ขอบเขต และหลายวัตถุประสงค์ อัลกอริทึมของผึ้งขึ้นอยู่กับพฤติกรรมการหาอาหารของแมลง มันถูกนำไปใช้ในหลาย ๆ แอปพลิเคชันเช่นการกำหนดเส้นทางและการตั้งเวลา
- การเพิ่มประสิทธิภาพฝูงอนุภาค - ตามแนวคิดพฤติกรรมฝูงสัตว์ และยังเหมาะสำหรับงานกระบวนการเชิงตัวเลขเป็นหลัก
วิธี metaheuristic ยอดนิยมอื่น ๆ
- ล่าสัตว์หา. วิธีการตามการจับกลุ่มของสัตว์บางชนิด เช่น หมาป่า เป็นต้น ซึ่งกระจายหน้าที่การล้อมเหยื่อ สมาชิกของอัลกอริธึมวิวัฒนาการแต่ละคนมีความเกี่ยวข้องกับผู้อื่นในทางใดทางหนึ่ง โดยเฉพาะอย่างยิ่งสำหรับผู้นำ นี่คือวิธีการปรับให้เหมาะสมอย่างต่อเนื่องซึ่งถูกปรับให้เป็นวิธีการประมวลผลแบบผสมผสาน
- ค้นหาตามขนาด อัลกอริธึมของกระบวนการปรับตัวนั้นไม่เหมือนกับวิธีการ metaheuristic ที่อิงกับธรรมชาติซึ่งแตกต่างจากวิธี metaheuristic ตามธรรมชาติ แต่จะใช้วิธีที่เน้นประสิทธิภาพอย่างง่ายโดยยึดตามการอัปเดตพารามิเตอร์อัตราส่วนมิติการค้นหาในการวนซ้ำแต่ละครั้ง อัลกอริธึมหิ่งห้อยได้รับแรงบันดาลใจจากวิธีที่หิ่งห้อยดึงดูดเข้าหากันด้วยแสงแวบวับ สิ่งนี้มีประโยชน์อย่างยิ่งสำหรับการเพิ่มประสิทธิภาพหลายรูปแบบ
- ค้นหาความสามัคคี ตามความคิดพฤติกรรมของนักดนตรี ในกรณีนี้ อัลกอริธึมวิวัฒนาการเป็นหนทางไปสู่การเพิ่มประสิทธิภาพแบบผสมผสาน
- ดัดแปลงแบบเกาส์เซียน. ตามทฤษฎีสารสนเทศ ใช้เพื่อเพิ่มประสิทธิภาพและความพร้อมใช้งานโดยเฉลี่ยสูงสุด ตัวอย่างของอัลกอริธึมวิวัฒนาการในสถานการณ์นี้: เอนโทรปีในอุณหพลศาสตร์และทฤษฎีข้อมูล
มีม
วิธีไฮบริดตามแนวคิดของ Richard Dawkins ที่มีม โดยปกติแล้วจะอยู่ในรูปแบบของอัลกอริธึมตามประชากรรวมกับขั้นตอนการเรียนรู้ส่วนบุคคลที่สามารถทำการปรับแต่งในท้องถิ่นได้ เน้นการใช้ความรู้เฉพาะปัญหาและความพยายามที่จะจัดระเบียบการค้นหาแบบละเอียดและทั่วโลกในลักษณะการทำงานร่วมกัน
วิวัฒนาการอัลกอริธึมเป็นแนวทางฮิวริสติกสำหรับปัญหาที่ไม่สามารถแก้ไขได้ง่ายในเวลาพหุนาม เช่น ปัญหา NP-hard แบบคลาสสิกและสิ่งอื่นใดที่อาจใช้เวลานานเกินไปในการประมวลผลอย่างละเอียดถี่ถ้วน เมื่อใช้อย่างอิสระ มักใช้สำหรับปัญหาเชิงผสมผสาน อย่างไรก็ตาม อัลกอริธึมทางพันธุกรรมมักใช้ควบคู่กับวิธีอื่นๆ ซึ่งเป็นวิธีที่รวดเร็วในการค้นหาจุดเริ่มต้นที่เหมาะสมที่สุดหลายแห่ง
สมมติฐานของอัลกอริธึมวิวัฒนาการ (เรียกว่าที่ปรึกษา) นั้นค่อนข้างง่าย เนื่องจากคุณคุ้นเคยกับกระบวนการคัดเลือกโดยธรรมชาติ ประกอบด้วยสี่ขั้นตอนหลัก:
- การเริ่มต้น;
- choice;
- ตัวดำเนินการทางพันธุกรรม
- จบ
แต่ละขั้นตอนเหล่านี้สัมพันธ์กันคร่าวๆ กับการคัดเลือกโดยธรรมชาติบางส่วน และให้วิธีง่ายๆ ในการทำให้หมวดหมู่ของอัลกอริทึมนั้นเป็นโมดูล พูดง่ายๆ ใน EA สมาชิกที่เหมาะสมที่สุดจะอยู่รอดและขยายพันธุ์ ในขณะที่สมาชิกที่ไม่ฟิตจะตายและไม่มีส่วนทำให้เกิดกลุ่มยีนรุ่นต่อไป
การเริ่มต้น
ในการเริ่มอัลกอริทึม คุณต้องสร้างชุดโซลูชันก่อน ประชากรจะมีข้อความแจ้งปัญหาที่เป็นไปได้จำนวนหนึ่ง ซึ่งมักเรียกว่าสมาชิก สิ่งเหล่านี้มักถูกสร้างขึ้นแบบสุ่ม (ภายในข้อจำกัดของงาน) หรือหากทราบความรู้ก่อนหน้านี้ ให้เน้นไปที่สิ่งที่ถือว่าเป็นอุดมคติอย่างไม่แน่นอน เป็นสิ่งสำคัญที่ประชากรจะครอบคลุมโซลูชั่นที่หลากหลายเพราะโดยพื้นฐานแล้วมันคือแหล่งรวมยีน ดังนั้น หากใครต้องการสำรวจความเป็นไปได้ที่แตกต่างกันมากมายภายในอัลกอริธึม เราควรพยายามให้มียีนที่แตกต่างกันมากมาย
ตัวเลือก
เมื่อสร้างจำนวนประชากรแล้ว สมาชิกจะต้องได้รับการประเมินตามฟังก์ชันฟิตเนส ฟังก์ชันฟิตเนสใช้คุณลักษณะของสมาชิกและแสดงตัวเลขว่าสมาชิกมีความพอดีเพียงใด การสร้างสิ่งเหล่านี้มักจะเป็นเรื่องยากมาก สิ่งสำคัญคือต้องหาระบบที่ดีที่แสดงถึงข้อมูลได้อย่างถูกต้อง นี่เป็นปัญหาเฉพาะเจาะจงมาก ตอนนี้ จำเป็นต้องคำนวณความเหมาะสมของผู้เข้าร่วมทั้งหมดและเลือกสมาชิกที่ดีที่สุดบางส่วน
ฟังก์ชั่นหลายวัตถุประสงค์
EA สามารถขยายเพื่อใช้ระบบเหล่านี้ได้ สิ่งนี้ทำให้กระบวนการค่อนข้างซับซ้อน เนื่องจากแทนที่จะระบุจุดที่เหมาะสมที่สุดจุดหนึ่ง จะได้รับชุดเมื่อใช้จุดเหล่านี้ ชุดของการแก้ปัญหานี้เรียกว่า Pareto frontier และมีองค์ประกอบที่เหมาะสมเท่าเทียมกันในแง่ที่ว่าไม่มีวิธีแก้ปัญหาอื่นใดครอบงำ
ตัวดำเนินการทางพันธุกรรม
ขั้นตอนนี้ประกอบด้วยสองขั้นตอนย่อย: ครอสโอเวอร์และการกลายพันธุ์ หลังจากเลือกคำศัพท์ที่ดีที่สุด (โดยปกติคือ 2 อันดับแรก แต่ตัวเลขนี้สามารถเปลี่ยนแปลงได้) ตอนนี้ใช้เพื่อสร้างอัลกอริทึมรุ่นต่อไป โดยการนำคุณลักษณะของผู้ปกครองที่เลือกมาประยุกต์ใช้ ทำให้มีการสร้างลูกใหม่ที่ผสมผสานคุณสมบัติต่างๆ เข้าด้วยกัน ซึ่งมักจะเป็นเรื่องยากขึ้นอยู่กับประเภทของข้อมูล แต่มักจะเป็นปัญหาแบบผสมผสานมันค่อนข้างเป็นไปได้ที่จะผสมและส่งออกชุดค่าผสมที่ถูกต้อง
ตอนนี้จำเป็นต้องแนะนำสารพันธุกรรมใหม่สู่รุ่น หากไม่ดำเนินการตามขั้นตอนที่สำคัญนี้ นักวิทยาศาสตร์จะติดอยู่ในพื้นที่สุดขั้วอย่างรวดเร็วและไม่ได้ผลลัพธ์ที่ดีที่สุด ขั้นตอนนี้เป็นการกลายพันธุ์ และทำได้ค่อนข้างง่าย โดยเปลี่ยนส่วนเล็ก ๆ ของเด็กในลักษณะที่ส่วนใหญ่ไม่สะท้อนชุดย่อยของยีนของพ่อแม่ การกลายพันธุ์มักจะเกิดขึ้นอย่างน่าจะเป็นไปได้ เนื่องจากความน่าจะเป็นที่เด็กจะได้รับ เช่นเดียวกับความรุนแรง ถูกกำหนดโดยการแจกแจง
สิ้นสุด
สุดท้ายอัลกอริทึมก็ต้องจบ ซึ่งมักเกิดขึ้นในสองกรณี: ถึงเวลาดำเนินการสูงสุดแล้วหรือถึงเกณฑ์ประสิทธิภาพแล้ว ณ จุดนี้ โซลูชันสุดท้ายจะถูกเลือกและส่งคืน
ตัวอย่างอัลกอริธึมวิวัฒนาการ
ตอนนี้ เพื่อแสดงผลลัพธ์ของกระบวนการนี้ คุณต้องพบที่ปรึกษาในการดำเนินการ ในการทำเช่นนี้ เราจำได้ว่าไดโนเสาร์หลายชั่วอายุคนเรียนรู้ที่จะเดิน (ค่อยๆ ควบคุมแผ่นดิน) ปรับโครงสร้างร่างกายให้เหมาะสมและใช้ความแข็งแรงของกล้ามเนื้อ แม้ว่าสัตว์เลื้อยคลานยุคแรกจะเดินไม่ได้ แต่ที่ปรึกษาก็สามารถพัฒนาพวกมันเมื่อเวลาผ่านไปผ่านการกลายพันธุ์และครอสโอเวอร์ให้อยู่ในรูปแบบที่เดินได้
อัลกอริธึมเหล่านี้มีความเกี่ยวข้องมากขึ้นในโลกสมัยใหม่ เนื่องจากมีการใช้โซลูชันที่อิงตามอัลกอริทึมเหล่านี้มากขึ้นในอุตสาหกรรมต่างๆ เช่น การตลาดดิจิทัล การเงิน และสุขภาพ
EA ใช้งานที่ไหน
กว้างกว่านั้น อัลกอริธึมวิวัฒนาการถูกใช้ในแอปพลิเคชันที่หลากหลาย เช่น การประมวลผลภาพ การกำหนดเส้นทางของยานพาหนะ การเพิ่มประสิทธิภาพการสื่อสารผ่านมือถือ การพัฒนาซอฟต์แวร์ และแม้แต่การฝึกอบรมโครงข่ายประสาทเทียม เครื่องมือเหล่านี้เป็นหัวใจสำคัญของแอพและเว็บไซต์จำนวนมากที่ผู้คนใช้เป็นประจำทุกวัน รวมถึง Google Maps และแม้แต่เกมอย่าง The Sims นอกจากนี้ วงการแพทย์ใช้ EA เพื่อช่วยในการตัดสินใจทางคลินิกเกี่ยวกับการรักษามะเร็ง อันที่จริง อัลกอริธึมวิวัฒนาการนั้นแข็งแกร่งมากจนสามารถใช้แก้ปัญหาการปรับให้เหมาะสมได้แทบทุกอย่าง
กฎของมัวร์
ความชุกของ EO ที่เพิ่มขึ้นนั้นเกิดจากสองปัจจัยหลัก: พลังการประมวลผลที่มีอยู่และการสะสมของชุดข้อมูลขนาดใหญ่ ข้อแรกสามารถอธิบายได้ด้วยกฎของมัวร์ ซึ่งระบุโดยพื้นฐานว่าปริมาณพลังประมวลผลในคอมพิวเตอร์จะเพิ่มขึ้นเป็นสองเท่าทุกๆ สองปีโดยประมาณ คำทำนายนี้มีมานานหลายทศวรรษ ปัจจัยที่สองเกี่ยวข้องกับการพึ่งพาเทคโนโลยีที่เพิ่มขึ้น ซึ่งช่วยให้สถาบันสามารถรวบรวมข้อมูลจำนวนมากอย่างไม่น่าเชื่อ ซึ่งช่วยให้พวกเขาสามารถวิเคราะห์แนวโน้มและเพิ่มประสิทธิภาพผลิตภัณฑ์ได้
อัลกอรึทึมวิวัฒนาการช่วยนักการตลาดได้อย่างไร
สภาวะตลาดเปลี่ยนแปลงอย่างรวดเร็วและมีการแข่งขันสูง สิ่งนี้ทำให้ผู้จัดการฝ่ายการตลาดต้องแข่งขันกันเพื่อการตัดสินใจที่ดีขึ้น เพิ่มขึ้นในที่มีอยู่พลังประมวลผลทำให้พนักงานใช้ EA ในการแก้ปัญหา
การเพิ่มประสิทธิภาพการแปลง
เป้าหมายหลักประการหนึ่งคือการเพิ่มอัตราผู้เข้าชมเว็บไซต์ ปัญหานี้เกิดขึ้นจากการเพิ่มประสิทธิภาพจำนวนผู้ใช้ที่ทำในสิ่งที่นักการตลาดต้องการ ตัวอย่างเช่น หากบริษัทขายแล็ปท็อป อุดมคติคือการเพิ่มจำนวนผู้เยี่ยมชมไซต์ที่ลงเอยด้วยการซื้อผลิตภัณฑ์ นี่คือสาระสำคัญของการเพิ่มประสิทธิภาพอัตราการแปลง
สิ่งหนึ่งที่สำคัญอย่างน่าประหลาดใจคือตัวเลือกอินเทอร์เฟซผู้ใช้ หากการออกแบบเว็บไม่เป็นมิตรกับผู้ใช้มากนัก อาจมีผู้ที่ไม่ได้ซื้อผลิตภัณฑ์ด้วยเหตุผลใดก็ตาม เป้าหมายคือการลดจำนวนผู้ใช้ที่ไม่ทำ Conversion ซึ่งจะเป็นการเพิ่มผลกำไรโดยรวม
