ขั้นตอนวิธีทางพันธุกรรม: การค้นหาและการเพิ่มประสิทธิภาพโดยการคัดเลือกโดยธรรมชาติ

อัลกอริทึมทางพันธุกรรมคืออะไร?

ในช่วงไม่กี่ปีที่ผ่านมา ปัญญาประดิษฐ์ (AI) ได้รับความนิยมอย่างล้นหลาม บริษัทใหญ่ๆ เช่น Google, Apple และ Microsoft กำลังทำงานในหัวข้อนี้อย่างแข็งขัน อันที่จริง AI เป็นร่มที่ครอบคลุมเป้าหมาย แนวทาง เครื่องมือ และแอปพลิเคชันมากมาย Genetic Algorithms (GA) เป็นเพียงหนึ่งในเครื่องมือสำหรับการค้นหาอย่างชาญฉลาดผ่านโซลูชันที่เป็นไปได้มากมาย

GA เป็นเทคนิคการค้นหาเชิงอภิปรัชญาและการปรับให้เหมาะสมตามหลักการที่มีอยู่ในวิวัฒนาการตามธรรมชาติ มันเป็นของอัลกอริธึมวิวัฒนาการระดับใหญ่

GA รักษา จำนวนโครโมโซม ซึ่งเป็นชุดแนวทางแก้ไขปัญหาที่เป็นไปได้ แนวคิดก็คือ "วิวัฒนาการ" จะพบวิธีแก้ปัญหาที่เหมาะสมที่สุดหลังจากรุ่นต่อๆ มาหลายรุ่น ซึ่งคล้ายกับการคัดเลือกโดยธรรมชาติ

GA เลียนแบบกระบวนการวิวัฒนาการสามกระบวนการ: การคัดเลือก ยีนครอสโอเวอร์ และการกลายพันธุ์

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

ระหว่างการคัดเลือก โครโมโซมจะจับคู่ พ่อแม่ พันธุ์เพื่อ ผสมพันธุ์ เด็ก แต่ละคนมีลักษณะเฉพาะจากพ่อแม่ โดยพื้นฐานแล้ว เด็กเป็นตัวแทนของการรวมตัวกันของคุณลักษณะจากพ่อแม่: คุณลักษณะบางอย่างถูกพรากไปจากพ่อแม่คนหนึ่งและบางส่วนจากอีกคนหนึ่ง นอกเหนือจากการรวมตัวใหม่ คุณลักษณะบางอย่างสามารถ กลายพันธุ์ ได้

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

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

นำสิ่งต่าง ๆ ไปสู่การปฏิบัติ

ตัวอย่างที่เราจะพิจารณาถือได้ว่าเป็น "Hello World" ของ GA ตัวอย่างนี้เริ่มต้นโดย J. Freeman ใน การจำลองโครงข่ายประสาทเทียมด้วย Mathematica ฉันนำมาจาก อัลกอริทึมทางพันธุกรรมและการออกแบบทางวิศวกรรม โดย Mitsuo Gen และ Runwei Cheng

ปัญหาการจับคู่คำพยายามที่จะพัฒนานิพจน์ด้วยอัลกอริธึมทางพันธุกรรม ในขั้นต้น อัลกอริทึมควรจะ "เดา" วลี "เป็นหรือไม่เป็น" จากรายการตัวอักษรที่สร้างแบบสุ่ม

เนื่องจากมีตัวอักษรที่เป็นไปได้ 26 ตัวสำหรับแต่ละตำแหน่งจาก 13 ตำแหน่ง [ไม่รวมช่องว่าง] ในรายการ ความน่าจะเป็นที่เราจะได้วลีที่ถูกต้องโดยการสุ่มทั้งหมดคือ (1/26)^13=4.03038×10-19 ซึ่งประมาณ โอกาสสองครั้งจาก [quintillion] (Gen & Chong, 1997)

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

สมมติว่าคู่ต่อสู้ของเรานึกถึงวลีโดยพลการ ซึ่งรวมถึงช่องว่างด้วย เราทราบความยาวของวลีและการนับสัญลักษณ์ในตัวอักษร นั่นคือความรู้เดียวที่เรามี หลังจากการเดาแต่ละครั้ง คู่ต่อสู้จะบอกเราว่ามีจดหมายกี่ฉบับ

โครโมโซมแต่ละตัวเป็นลำดับดัชนีของสัญลักษณ์ในตัวอักษร หากเรากำลังพูดถึงตัวอักษรภาษาอังกฤษ 'a' จะถูกแทนด้วย 0, 'b' คูณ 1, 'c' คูณ 2 เป็นต้น ตัวอย่างเช่น คำว่า "เป็น" จะแสดงเป็น [4, 1]

เราจะสาธิตขั้นตอนทั้งหมดผ่านข้อมูลโค้ด Java แต่ไม่จำเป็นต้องมีความรู้เกี่ยวกับ Java เพื่อทำความเข้าใจแต่ละขั้นตอน

แกนอัลกอริทึมทางพันธุกรรม

เราสามารถเริ่มต้นด้วยการนำอัลกอริธึมทางพันธุกรรมไปใช้โดยทั่วไป:

 public void find() { // Initialization List<T> population = Stream.generate(supplier) .limit(populationSize) .collect(toList()); // Iteration while (!termination.test(population)) { // Selection population = selection(population); // Crossover crossover(population); // Mutation mutation(population); } }

นี่เป็นชุดขั้นตอนง่ายๆ ที่ GA ทุกแห่งประกอบด้วยไม่มากก็น้อย ในขั้นตอนการเริ่มต้น เราสร้างกลุ่มวลีเริ่มต้น ขนาดของประชากรกำหนดโดย populationSize Size วิธีสร้างวลีนั้นขึ้นอยู่กับการใช้งานของ supplier

ภายในขั้นตอนการวนซ้ำ เราพัฒนาประชากรจนกว่าจะตรงตามเงื่อนไขการสิ้นสุดภายในการทดสอบของ while loop เงื่อนไขการเลิกจ้างอาจรวมทั้งจำนวนรุ่นและการจับคู่แบบตรงทั้งหมดของวลีในกลุ่มประชากร การ termination สรุปการใช้งานที่แน่นอน

ในการทำซ้ำแต่ละครั้ง เราดำเนินการตามขั้นตอน GA ทั่วไป:

1. ทำการเลือกประชากรตามความเหมาะสมของโครโมโซม
2. สร้าง “เจเนอเรชั่นใหม่” ผ่านการทำงานแบบครอสโอเวอร์
3. ทำการรวมตัวอักษรบางตัวในวลีบางวลี

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

การคัดเลือก

ดังที่เราทราบแล้ว การคัดเลือกเป็นกระบวนการในการค้นหาผู้สืบทอดโครโมโซมในปัจจุบัน ซึ่งเป็นโครโมโซมที่เหมาะกับปัญหาของเรามากกว่า ในระหว่างการคัดเลือก เราต้องตรวจสอบให้แน่ใจว่าโครโมโซมที่มีความฟิตดีขึ้นมีโอกาสรอดชีวิตมากขึ้น

 private List<T> selection(List<T> 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 < fitnesses.length; i++) { sum += fitnesses[i] / totalFitness; probabilities[i] = sum; } probabilities[probabilities.length - 1] = 1; return range(0, probabilities.length).mapToObj(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<T> population) { final int[] indexes = range(0, population.size()) .filter(i-> random() < crossoverProbability) .toArray(); shuffle(Arrays.asList(indexes)); for (int i = 0; i < indexes.length / 2; i++) { final int index1 = indexes[2 * i]; final int index2 = indexes[2 * i + 1]; final T value1 = population.get(index1); final T value2 = population.get(index2); population.set(index1, crossover.apply(value1, value2)); population.set(index2, crossover.apply(value2, value1)); } }

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

การกลายพันธุ์

สุดท้าย เราทำการรวมคุณสมบัติใหม่เข้าด้วยกัน

 private void mutation(List<T> population) { for (int i = 0; i < population.size(); i++) { if (random() < mutationProbability) { population.set(i, mutation.apply(population.get(i))); } } }

ด้วยความน่าจะเป็นที่กำหนดไว้ล่วงหน้า ความน่าจะเป็น เราทำการ "กลาย mutationProbability " บนโครโมโซม การกลายพันธุ์นั้นถูกกำหนดโดย mutation

การกำหนดค่าอัลกอริทึมเฉพาะปัญหา

ตอนนี้ มาดูกันว่าพารามิเตอร์เฉพาะปัญหาประเภทใดที่เราต้องมีเพื่อการใช้งานทั่วไปของเรา

 private BiFunction<T, T, T> crossover; private double crossoverProbability; private ToDoubleFunction<T> fitness; private Function<T, T> mutation; private double mutationProbability; private int populationSize = 100; private Supplier<T> supplier; private Predicate<Collection<T>> termination;

พารามิเตอร์ตามลำดับคือ:

1. ตัวดำเนินการครอสโอเวอร์
2. ความน่าจะเป็นแบบครอสโอเวอร์
3. ฟังก์ชั่นฟิตเนส
4. โอเปอเรเตอร์การกลายพันธุ์
5. ความน่าจะเป็นของการกลายพันธุ์
6. ขนาดของประชากร
7. ซัพพลายเออร์โครโมโซมสำหรับประชากรเริ่มต้น
8. ฟังก์ชันการสิ้นสุด

นี่คือการกำหนดค่าสำหรับปัญหาของเรา:

 new GeneticAlgorithm<char[]>() .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 < length; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); result[i] = ALPHABET[letter]; } return result; }

ซัพพลายเออร์สร้างวลีแบบสุ่มโดยใช้ตัวอักษรสุ่มจากตัวอักษร แต่ละวลีมีความยาวที่กำหนดไว้ล่วงหน้าคงที่

ฟังก์ชันการสิ้นสุด

 private boolean termination(Collection<char[]> chars) { count++; final Optional<char[]> 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

การดำเนินการ

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

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

การเพิ่มตัวเลขจะทำให้อัลกอริทึมเร็วขึ้น แต่จะทำให้โซลูชันไม่เสถียรด้วย Fit chromosomes ไม่เพียงแต่ถูกรักษาไว้แต่ยังจะได้รับผลกระทบจากยีนโอเปอเรเตอร์ ดังนั้นพวกเขาจะสูญเสียยีน "ดี" ของพวกเขาไป

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

อะไรต่อไป?

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

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

หากสามารถแสดงปัญหาผ่านชุดพารามิเตอร์ที่เราต้องเดาเพื่อปรับเมตริกให้เหมาะสม เราสามารถตั้งค่า GA ที่เราใช้แก้ปัญหาได้อย่างรวดเร็ว

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