Genetic Algorithms คืออะไร?
ในช่วงไม่กี่ปีที่ผ่านมามีความโกลาหลเกี่ยวกับปัญญาประดิษฐ์ (AI) บริษัท ขนาดใหญ่เช่น Google, Apple และ Microsoft กำลังดำเนินการแก้ไขปัญหานี้อย่างจริงจัง ในความเป็นจริง AI เป็นเพียงร่มที่ครอบคลุมเป้าหมายแนวทางเครื่องมือและแอปพลิเคชันมากมาย Genetic Algorithms (GA) เป็นเพียงหนึ่งในเครื่องมืออันชาญฉลาดที่มองหาโซลูชันที่เป็นไปได้มากมาย
AG คือการค้นหาแบบ meta-heuristic ตลอดจนเทคนิคการเพิ่มประสิทธิภาพตามหลักการที่มีอยู่ในวิวัฒนาการตามธรรมชาติ มันเป็นของอัลกอริธึมวิวัฒนาการที่ยาวนานกว่า
AG รักษา ประชากรโครโมโซม - ชุดวิธีแก้ไขปัญหาที่เป็นไปได้ แนวคิดก็คือ 'วิวัฒนาการ' พบวิธีแก้ปัญหาที่ดีที่สุดหลังจากหลายชั่วอายุคนต่อเนื่องกัน - คล้ายกับการคัดเลือกโดยธรรมชาติ
AG เลียนแบบกระบวนการวิวัฒนาการสามขั้นตอน ได้แก่ การคัดเลือกการข้ามโครโมโซมและการกลายพันธุ์
สถาปนิกโซลูชันที่ผ่านการรับรอง aws – Associate
เช่นเดียวกับการคัดเลือกโดยธรรมชาติแนวคิดหลักของการคัดเลือก AG คือการปรับตัว โครโมโซมที่ปรับตัวได้ดีขึ้นมีโอกาสรอดมากกว่า การปรับตัวเป็นฟังก์ชันที่ใช้วัดคุณภาพของสารละลายที่แสดงโดยโครโมโซม โดยพื้นฐานแล้วโครโมโซมแต่ละตัวภายในประชากรจะแสดงถึงพารามิเตอร์อินพุตเช่นปริมาตรและอัตราแลกเปลี่ยนโครโมโซมแต่ละตัวในเชิงตรรกะจะประกอบด้วยสององค์ประกอบ การเข้ารหัสองค์ประกอบภายในโครโมโซมเป็นอีกเรื่องหนึ่ง
ในระหว่างการคัดเลือกโครโมโซมจะสร้างคู่ของ พ่อแม่ สำหรับ การสืบพันธุ์ . แต่ละ เด็ก มีลักษณะของพ่อแม่ของเขา โดยพื้นฐานแล้วเด็กแสดงถึงการรวมกันของลักษณะเฉพาะของพ่อแม่ของเขา: ลักษณะบางอย่างถูกนำมาจากพ่อแม่คนหนึ่งและบางส่วนมาจากพ่อแม่อีกคน นอกจากการรวมตัวกันใหม่แล้วลักษณะบางอย่างอาจ กลายพันธุ์ .
เนื่องจากโครโมโซมที่เหมาะสมที่สุดสร้างลูกได้มากขึ้นแต่ละรุ่นที่ตามมาจึงเหมาะสมกว่า ในบางช่วงเวลารุ่นหนึ่งจะมีโครโมโซมซึ่งแสดงถึงวิธีการแก้ปัญหาที่ดีพอสำหรับเรา
AG มีประสิทธิภาพและใช้ได้อย่างกว้างขวางกับปัญหาที่ซับซ้อน มีปัญหาการเพิ่มประสิทธิภาพหลายระดับซึ่งค่อนข้างยากที่จะแก้ไขโดยใช้เทคนิคการเพิ่มประสิทธิภาพแบบเดิม อัลกอริทึมทางพันธุกรรมเป็นอัลกอริทึมที่มีประสิทธิภาพซึ่งมีโซลูชันที่เหมาะสมที่สุดโดยประมาณ แอปพลิเคชั่นที่รู้จักกันดี ได้แก่ การจัดตารางเวลาการขนส่งการวางแผนเส้นทางเทคโนโลยีกลุ่มการออกแบบแผนการฝึกอบรมโครงข่ายประสาทเทียมและอื่น ๆ อีกมากมาย
นำสิ่งต่างๆไปสู่การปฏิบัติ
ตัวอย่างที่เราจะเห็นนี้ถือได้ว่าเป็น“ Hello World” ของ AG ตัวอย่างนี้นำเสนอครั้งแรกโดย J. Freeman in การจำลองโครงข่ายประสาทเทียมด้วย Mathematica . ฉันเอามาจาก อัลกอริทึมทางพันธุกรรมและการออกแบบทางวิศวกรรม โดย Mitsuo Gen และ Runwei Cheng
ปัญหาการจำลองโลกพยายามที่จะพัฒนานิพจน์ด้วยอัลกอริทึมทางพันธุกรรม ในขั้นต้นอัลกอริทึมต้อง 'เดา' วลี 'เป็นหรือไม่เป็น' จากรายการตัวอักษรที่สร้างขึ้นแบบสุ่ม
เนื่องจากมีตัวอักษรที่เป็นไปได้ 26 ตัวสำหรับแต่ละตำแหน่งจาก 13 ตำแหน่ง [ไม่รวมช่องว่าง] ในรายการโอกาสที่เราจะได้วลีที่ถูกต้องโดยการสุ่มคือ (1/26) ^ 13 = 4.03038 × 10-19 ดังนั้นซึ่งก็คือ เกี่ยวกับโอกาสสองครั้งใน [ล้านล้าน] (Gen & Chong, 1997)
เราจะกำหนดปัญหาให้มากขึ้นที่นี่โดยการแก้ปัญหาให้ยากขึ้น สมมติว่าเราไม่ได้ จำกัด เฉพาะภาษาอังกฤษหรือวลีเฉพาะ เราสามารถจัดการกับตัวอักษรใด ๆ หรือแม้แต่ชุดของสัญลักษณ์ใดก็ได้ เราไม่มีความรู้เรื่องภาษา เราไม่รู้ด้วยซ้ำว่ามีภาษาอะไร
สมมติว่าฝ่ายตรงข้ามของเรานึกถึงวลีโดยพลการรวมทั้งช่องว่าง เราทราบความยาวของประโยคและจำนวนสัญลักษณ์ในตัวอักษร นั่นคือความรู้เดียวที่เรามี หลังจากทายแต่ละครั้งฝ่ายตรงข้ามจะบอกเราว่ามีตัวอักษรกี่ตัว
โครโมโซมแต่ละตัวเป็นลำดับของดัชนีสำหรับสัญลักษณ์ในตัวอักษร ถ้าเรากำลังพูดถึงตัวอักษรภาษาอังกฤษ 'a' จะแทนด้วย 0, 'b' ด้วย 1, 'c' ด้วย 2 และอื่น ๆ ตัวอย่างเช่นคำว่า 'be' จะแสดงเป็น [4, 1]
เราจะสาธิตขั้นตอนทั้งหมดผ่านส่วนของโค้ด Java แต่ความรู้ใน Java ไม่ใช่ข้อกำหนดในการทำความเข้าใจในแต่ละขั้นตอน
ศูนย์กลางของอัลกอริทึมทางพันธุกรรม
เราสามารถเริ่มต้นด้วยการใช้อัลกอริทึมทางพันธุกรรมโดยทั่วไป:
public void find() { // Initialization List population = Stream.generate(supplier) .limit(populationSize) .collect(toList()); // Iteration while (!termination.test(population)) { // Selection population = selection(population); // Crossover crossover(population); // Mutation mutation(population); } } นี่คือชุดขั้นตอนง่ายๆที่ AG ทุกคนควรมี ในขั้นตอนแรกเราจะสร้างกลุ่มวลีขึ้นมา ขนาดของประชากรถูกกำหนดโดย populationSize และวิธีสร้างวลีนี้ขึ้นอยู่กับการใช้งาน supplier
ภายในขั้นตอนการทำซ้ำเราจะพัฒนาประชากรจนกว่าจะตรงตามเงื่อนไขภายในการทดสอบโหนด while เงื่อนไขระยะเวลาอาจรวมถึงจำนวนรุ่นและความลงตัวของวลีใดคำหนึ่งในกลุ่มประชากร termination สรุปการใช้งานที่แน่นอน
ในการทำซ้ำแต่ละครั้งเราทำตามขั้นตอน AG ทั่วไป:
- ดำเนินการคัดเลือกประชากรตามความเพียงพอของโครโมโซม
- ผลิต 'เจเนอเรชั่น' ใหม่ผ่านการทำงานแบบครอสโอเวอร์
- มันนำตัวอักษรบางตัวมารวมกันใหม่ในบางประโยค
แกนหลักของอัลกอริทึมนั้นง่ายมากและไม่เชื่อเรื่องพระเจ้า มันจะเหมือนกันสำหรับปัญหาทั้งหมด สิ่งที่คุณต้องปรับคือการนำตัวดำเนินการทางพันธุกรรม จากนั้นเราจะมาดูรายละเอียดเกี่ยวกับผู้ให้บริการ AG แต่ละรายดังกล่าว
วิธีรับข้อมูล Twitter เพื่อการวิเคราะห์
การเลือก
ดังที่เราทราบกันดีอยู่แล้วว่าการคัดเลือกเป็นกระบวนการที่ทำขึ้นเพื่อค้นหาผู้สืบทอดของโครโมโซมในปัจจุบันซึ่งเป็นโครโมโซมที่เหมาะสมที่สุดสำหรับปัญหาของเรา ในระหว่างการคัดเลือกเราจำเป็นต้องตรวจสอบให้แน่ใจว่าโครโมโซมที่เข้ากันดีที่สุดมีโอกาสรอดชีวิตที่ดีกว่า
private List selection(List population) { final double[] fitnesses = population.stream() .mapToDouble(fitness) .toArray(); final double totalFitness = DoubleStream.of(fitnesses).sum(); double sum = 0; final double[] probabilities = new double[fitnesses.length]; for (int i = 0; i { int index = binarySearch(probabilities, random()); if (index <0) { index = -(index + 1); } return population.get(index); }).collect(toList()); } แนวคิดของการใช้งานนี้มีดังต่อไปนี้: ประชากรจะแสดงเป็นลักษณะที่ตามมาบนแกนตัวเลข ประชากรทั้งหมดอยู่ระหว่าง 0 ถึง 1
ส่วนของชุดที่โครโมโซมใช้เป็นสัดส่วนกับความเพียงพอ สิ่งนี้ส่งผลให้โครโมโซมที่เหมาะสมกว่ามากซึ่งมีขนาดใหญ่กว่า จากนั้นเราเลือกตัวเลขโดยสุ่มระหว่าง 0 ถึง 1 และค้นหาซีรีส์ที่มีตัวเลขนี้ เห็นได้ชัดว่าชุดที่มีขนาดใหญ่กว่ามีโอกาสที่จะถูกเลือกได้ดีกว่าดังนั้นโครโมโซมที่เหมาะสมที่สุดจึงมีโอกาสรอดชีวิตที่ดีกว่า
อินเตอร์เน็ตออฟธิงส์สมาร์ทดีไวซ์
เนื่องจากเราไม่ทราบรายละเอียดเกี่ยวกับฟังก์ชันการออกกำลังกายเราจึงต้องปรับค่าฟิตเนสให้เป็นปกติ ฟังก์ชันการออกกำลังกายแสดงโดย fitness ซึ่งจะเปลี่ยนโครโมโซมเป็นคู่โดยพลการซึ่งแสดงถึงความสมบูรณ์ของโครโมโซม
ในรหัสเราพบอัตราการจับคู่สำหรับโครโมโซมทั้งหมดในประชากรและเรายังพบการจับคู่ทั้งหมด ภายในโหนด for เราเรียกใช้ผลรวมสะสมมากกว่าความน่าจะเป็นลดลงด้วยความพอดีทั้งหมด ในทางคณิตศาสตร์สิ่งนี้ควรส่งผลให้ตัวแปรสุดท้ายมีค่าเป็น 1 เนื่องจากความไม่แม่นยำของจุดลอยตัวเราไม่สามารถรับประกันได้ดังนั้นเราจึงตั้งค่าเป็น 1 เพื่อให้ปลอดภัย
ในที่สุดสำหรับระยะเวลาที่เท่ากับจำนวนโครโมโซมที่เข้ามาเราจะสร้างตัวเลขสุ่มค้นหาชุดที่มีจำนวนแล้วเลือกโครโมโซมที่เกี่ยวข้อง ดังที่คุณอาจสังเกตเห็นโครโมโซมเดียวกันสามารถเลือกได้หลายครั้ง
ครอสโอเวอร์
ตอนนี้เราต้องการโครโมโซมเพื่อ 'สืบพันธุ์'
private void crossover(List population) { final int[] indexes = range(0, population.size()) .filter(i-> random() ด้วยความน่าจะเป็นที่กำหนดไว้ล่วงหน้าเป็น crossoverProbability เราจึงเลือกพ่อแม่พันธุ์สำหรับการผสมพันธุ์ พ่อแม่ที่ถูกเลือกมาผสมกันจึงทำให้สามารถผสมกันได้ เราใช้ผู้ปกครองเป็นคู่และใช้ตัวดำเนินการ crossover. เราใช้ตัวดำเนินการสองครั้งสำหรับแต่ละคู่เพราะเราต้องการให้ขนาดประชากรเท่ากัน เด็กแทนที่พ่อแม่ในประชากร
การกลายพันธุ์
สุดท้ายเราดำเนินการรวมกันใหม่ของลักษณะ
private void mutation(List population) { for (int i = 0; i ด้วยความน่าจะเป็น mutationProbability กำหนดไว้ล่วงหน้าเราดำเนินการ 'การกลายพันธุ์' ในโครโมโซม การกลายพันธุ์ดังกล่าวถูกกำหนดให้เป็น mutation
การกำหนดค่าอัลกอริทึมเฉพาะปัญหา
ตอนนี้เรามาดูว่าเราต้องจัดเตรียมพารามิเตอร์ปัญหาเฉพาะประเภทใดสำหรับการใช้งานทั่วไปของเรา
private BiFunction crossover; private double crossoverProbability; private ToDoubleFunction fitness; private Function mutation; private double mutationProbability; private int populationSize = 100; private Supplier supplier; private Predicate termination; พารามิเตอร์ตามลำดับคือ 1. ตัวดำเนินการไขว้ 2. ความน่าจะเป็นแบบไขว้ 3. ฟังก์ชันความเหมาะสม 4. ตัวดำเนินการการกลายพันธุ์ 5. ความน่าจะเป็นของการกลายพันธุ์ 6. ขนาดของประชากร 7. ผู้ให้โครโมโซมสำหรับประชากรเริ่มต้น 8. ระยะของฟังก์ชัน
นี่คือการกำหนดค่าปัญหาของเรา:
new GeneticAlgorithm() .setCrossover(this::crossover) .setCrossoverProbability(0.25) .setFitness(this::fitness) .setMutation(this::mutation) .setMutationProbability(0.05) .setPopulationSize(100) .setSupplier(() -> supplier(expected.length)) .setTermination(this::termination) .find() ตัวดำเนินการครอสโอเวอร์และความน่าจะเป็น
private char[] crossover(char[] value1, char[] value2) { final int i = (int) round(random() * value1.length); final char[] result = new char(value1.length); System.arraycopy(value1, 0, result, 0, i); System.arraycopy(value2, i, result, i, value2.length - i); return result; } ความน่าจะเป็นของการครอสโอเวอร์คือ 0.25 ดังนั้นเราจึงคาดว่าโดยเฉลี่ย 25 เปอร์เซ็นต์ของโครโมโซมจะถูกเลือกสำหรับครอสโอเวอร์ เราดำเนินการตามขั้นตอนง่ายๆสำหรับการครอสโอเวอร์ของโครโมโซมคู่หนึ่ง เราสร้างตัวเลขสุ่ม n สำหรับการเลือก [0..length] โดยที่ length คือความยาวของโครโมโซม ตอนนี้เราเข้าร่วมคู่ที่เลือกโดยใช้สัญลักษณ์แรก n ของโครโมโซมตัวใดตัวหนึ่งและสัญลักษณ์ที่เหลือหลังจากที่สอง
ฟังก์ชั่นที่เพียงพอ
private double fitness(char[] value) { return range(0, value.length) .filter(i -> value[i] == expected[i]) .count(); } ฟังก์ชันที่เหมาะสมจะนับจำนวนชุดค่าผสมระหว่างวลีหลักและโครโมโซมที่กำหนด
ตัวดำเนินการการกลายพันธุ์และความน่าจะเป็น
private char[] mutation(char[] value) { final char[] result = Arrays.copyOf(value, value.length); for (int i = 0; i <2; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); int location = (int) round(random() * (value.length - 1)); result[location] = ALPHABET[letter]; } return result; } การดำเนินการกลายพันธุ์ดำเนินไปอย่างอิสระในโครโมโซมแต่ละตัว ความน่าจะเป็นของการกลายพันธุ์คือ 0.05 ดังนั้นเราจึงคาดว่าโดยเฉลี่ยห้าเปอร์เซ็นต์ของประชากรจะกลายพันธุ์ เรากลายพันธุ์โดยเลือกตำแหน่งตัวอักษรแบบสุ่มและแทนที่ค่าด้วยตัวอักษรแบบสุ่มจากตัวอักษร เราทำสองครั้งสำหรับแต่ละโครโมโซมที่กลายพันธุ์
ผู้ให้บริการ
private char[] supplier(int length) { final char[] result = new char(length); for (int i = 0; i ผู้ให้บริการสร้างวลีแบบสุ่มโดยการสุ่มตัวอักษรเท่า ๆ กัน แต่ละวลีมีความยาวคงที่ที่กำหนดไว้ล่วงหน้า
ฟังก์ชันระยะ
private boolean termination(Collection chars) { count++; final Optional result = chars.stream() .filter(value -> round(fitness(value)) == expected.length) .findAny(); if (result.isPresent()) { System.out.println('Count: ' + count); System.out.println(result.get()); return true; } final boolean terminated = count == 3000; if (terminated) { chars.forEach(System.out::println); } return terminated; } ฟังก์ชันคำนี้จะนับจำนวนการโทรและส่งกลับ true หากมีการจับคู่แบบตรงทั้งหมดอยู่แล้วหรือหากจำนวนรุ่นถึง 3,000
การดำเนินการ
ตอนนี้เราพร้อมที่จะทดสอบอัลกอริทึมของเราแล้ว หากคุณเรียกใช้หลายครั้งคุณจะสังเกตได้ว่าไม่ใช่ทุกการวิ่งที่ประสบความสำเร็จ แต่ละครั้งจำนวนการทำซ้ำจะแตกต่างกัน เนื่องจากลักษณะความน่าจะเป็นของอัลกอริทึม อัลกอริทึมมีหลายจุดที่สามารถปรับปรุงได้ คุณสามารถเล่นกับครอสโอเวอร์และความน่าจะเป็นของการกลายพันธุ์
ลดจำนวนลงเป็นวิธีแก้ปัญหาที่เสถียร แต่ช้า โครโมโซมจำนวนน้อยจะได้รับผลกระทบจากตัวดำเนินการทางพันธุกรรมดังนั้นจึงต้องมีการทำซ้ำมากขึ้นสำหรับการแก้ปัญหา
การเพิ่มตัวเลขจะทำให้อัลกอริทึมเร็วขึ้น แต่ก็จะทำให้โซลูชันไม่เสถียรเช่นกัน โครโมโซมที่เหมาะสมจะไม่เพียง แต่รักษาไว้เท่านั้น แต่ยังได้รับผลกระทบจากตัวดำเนินการทางพันธุกรรมด้วย ด้วยเหตุนี้พวกเขาจะสูญเสียยีนที่ 'ดี' ไป
สิ่งสำคัญคือต้องหาสมดุลที่ดี การเพิ่มจำนวนการทำซ้ำจะทำให้อัลกอริทึมมีโอกาสมากขึ้นในการค้นหาวิธีแก้ปัญหา แต่ในทางกลับกันจะใช้เวลามากขึ้น ใช้วิธีการครอสโอเวอร์และการกลายพันธุ์ที่แตกต่างกัน การเลือกตัวดำเนินการเหล่านี้ที่ดีจะช่วยปรับปรุงคุณภาพของโซลูชันได้อย่างมาก
อะไรต่อไป?
เราได้ปกคลุมเพียงส่วนปลายของภูเขาน้ำแข็ง เรานำตัวอย่างที่มีเพียงรายการเดียวและสามารถนำเสนอเป็นโครโมโซมได้อย่างง่ายดาย ตัวดำเนินการทางพันธุกรรมนั้นเรียบง่าย
ปัญหาด้านความปลอดภัยของอินเทอร์เน็ตของสิ่งต่าง ๆ
เป็นเรื่องที่น่าสนใจมากที่จะนำปัญหาจากชีวิตจริงมาใช้และใช้ขั้นตอนวิธีทางพันธุกรรมกับมัน คุณจะค้นพบวิธีต่างๆในการเข้ารหัสอินพุตข้อมูลจริงตลอดจนการใช้งานครอสโอเวอร์และการกลายพันธุ์ที่แตกต่างกัน
หากสามารถแสดงปัญหาผ่านชุดพารามิเตอร์ที่เราต้องคาดเดาเพื่อเพิ่มประสิทธิภาพเมตริกเราสามารถสร้าง AG ได้อย่างรวดเร็วเพื่อใช้แก้ไข
ปัญหาที่น่าสนใจอย่างหนึ่งคือการสอนโครงข่ายประสาทเทียม เราสามารถตั้งค่าพารามิเตอร์ที่ปรับให้เหมาะสมเป็นแรงไซแนปส์และเพื่อให้เมตริกที่เหมาะสมคือเปอร์เซ็นต์ของอินพุตที่เครือข่ายประสาทเทียมของเราให้คำตอบที่ถูกต้อง หลังจากนั้นเราสามารถผ่อนคลายและปล่อยให้เครือข่ายประสาทของเราพัฒนาไปสู่ทางออกที่ดีที่สุดที่เราต้องการ หรืออย่างน้อยก็จนกว่าเราจะมีสิ่งที่ดีพอเพราะวิวัฒนาการต้องใช้เวลา
