الخوارزميات الجينية: البحث والتحسين عن طريق الانتقاء الطبيعي

ما هي الخوارزميات الجينية؟

على مدى السنوات القليلة الماضية ، كان هناك ضجة كبيرة حول الذكاء الاصطناعي (AI). تعمل الشركات الكبرى مثل Google و Apple و Microsoft بنشاط على هذا الموضوع. في الواقع ، يعد الذكاء الاصطناعي بمثابة مظلة تغطي الكثير من الأهداف والأساليب والأدوات والتطبيقات. الخوارزميات الجينية (GA) هي مجرد واحدة من أدوات البحث الذكي من خلال العديد من الحلول الممكنة.

GA هي تقنية بحث وتحسين metaheuristic تعتمد على المبادئ الموجودة في التطور الطبيعي. إنه ينتمي إلى فئة أكبر من الخوارزميات التطورية.

يحافظ GA على مجموعة من الكروموسومات - مجموعة من الحلول المحتملة للمشكلة. الفكرة هي أن "التطور" سيجد الحل الأمثل للمشكلة بعد عدد من الأجيال المتعاقبة - على غرار الانتقاء الطبيعي.

يحاكي GA ثلاث عمليات تطورية: الاختيار ، وتقاطع الجينات ، والطفرة.

على غرار الانتقاء الطبيعي ، فإن المفهوم المركزي لاختيار GA هو اللياقة. تتمتع الكروموسومات الأكثر ملاءمة بفرصة أفضل للبقاء. اللياقة هي وظيفة تقيس جودة المحلول الذي يمثله الكروموسوم. في جوهرها ، يمثل كل كروموسوم داخل السكان معلمات الإدخال. على سبيل المثال ، إذا كانت مشكلتك تحتوي على معلمتين للإدخال ، مثل السعر والحجم في التداول ، فسيتكون كل كروموسوم منطقيًا من عنصرين. كيفية ترميز العناصر داخل الكروموسوم موضوع مختلف.

أثناء الانتقاء ، تشكل الكروموسومات أزواجًا من الآباء للتكاثر . كل طفل يأخذ خصائص من والديه. في الأساس ، يمثل الطفل إعادة تركيب الخصائص من والديه: بعض الخصائص مأخوذة من أحد الوالدين وبعضها من الآخر. بالإضافة إلى إعادة التركيب ، يمكن أن تتغير بعض الخصائص.

لأن الكروموسومات المناسبة تنتج المزيد من الأطفال ، فإن كل جيل لاحق سيكون له لياقة أفضل. في مرحلة ما ، سيحتوي جيل على كروموسوم يمثل حلاً جيدًا كافياً لمشكلتنا.

GA قوية وقابلة للتطبيق على نطاق واسع للمشاكل المعقدة. هناك فئة كبيرة من مشكلات التحسين التي يصعب حلها باستخدام تقنيات التحسين التقليدية. الخوارزميات الجينية هي خوارزميات فعالة يكون حلها هو الأمثل تقريبًا. تشمل التطبيقات المعروفة الجدولة ، والنقل ، والتوجيه ، وتقنيات المجموعة ، وتصميم التخطيط ، وتدريب الشبكة العصبية ، وغيرها الكثير.

وضع الأشياء موضع التنفيذ

يمكن اعتبار المثال الذي سنلقي نظرة عليه "Hello World" في GA. تم تقديم هذا المثال في البداية بواسطة J. Freeman في محاكاة الشبكات العصبية باستخدام Mathematica . لقد أخذته من الخوارزميات الجينية والتصميم الهندسي بواسطة ميتسو جين ورونوي تشينج.

تحاول مشكلة مطابقة الكلمات تطوير تعبير باستخدام خوارزمية جينية. في البداية ، من المفترض أن تقوم الخوارزمية "بتخمين" عبارة "أكون أو لا أكون" من قوائم الحروف التي تم إنشاؤها عشوائيًا.

نظرًا لوجود 26 حرفًا محتملاً لكل موقع من 13 موقعًا [باستثناء المسافة البيضاء] في القائمة ، فإن احتمال حصولنا على العبارة الصحيحة بطريقة عشوائية خالصة هو (1/26) ^ 13 = 4.03038 × 10-19 ، أي تقريبًا فرصتان من أصل [كوينتيليون] (جين وتشونغ ، 1997).

سنقوم بتعريف المشكلة بشكل أوسع قليلاً هنا ، مما يجعل الحل أكثر صعوبة. لنفترض أننا لسنا مقيدين باللغة الإنجليزية أو بعبارة محددة. يمكن أن ينتهي بنا الأمر بالتعامل مع أي أبجدية ، أو حتى أي مجموعة من الرموز. ليس لدينا معرفة باللغة. لا نعرف حتى ما إذا كانت هناك أي لغة على الإطلاق.

لنفترض أن خصمنا فكر في عبارة عشوائية ، بما في ذلك المسافة البيضاء. نعرف طول العبارة وعدد الرموز في الأبجدية. هذه هي المعرفة الوحيدة التي لدينا. بعد كل تخمين ، يخبرنا خصمنا بعدد الأحرف الموجودة في المكان.

كل كروموسوم هو سلسلة من مؤشرات الرموز في الأبجدية. إذا كنا نتحدث عن الأبجدية الإنجليزية ، فسيتم تمثيل "أ" بـ 0 ، و "ب" في 1 ، و "ج" في 2 ، وهكذا. لذلك ، على سبيل المثال ، سيتم تمثيل كلمة "يكون" كـ [4, 1] .

سنشرح جميع الخطوات من خلال مقتطفات تعليمات 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 . تعتمد كيفية إنشاء العبارة على تنفيذ supplier .

ضمن خطوة التكرار ، نقوم بتطوير المجتمع حتى يتم استيفاء شروط الإنهاء داخل اختبار الحلقة while . قد تتضمن شروط الإنهاء كلاً من عدد الأجيال والمطابقة التامة لإحدى العبارات في المجتمع. يتضمن 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 إذا كان هناك تطابق تام ، أو إذا وصل عدد التوليد إلى 3000.

تنفيذ

نحن الآن جاهزون لاختبار الخوارزمية الخاصة بنا. إذا قمت بتشغيله عدة مرات ، ستلاحظ أنه ليس كل عمليات التشغيل ناجحة. في كل مرة ، سيكون عدد التكرارات مختلفًا. هذا يرجع إلى الطبيعة الاحتمالية للخوارزمية. تحتوي الخوارزمية على عدة نقاط حيث يمكن تحسينها. يمكنك اللعب مع احتمالية التقاطع والطفرة.

سيؤدي خفض الرقم إلى حل مستقر ولكنه بطيء. سيتأثر عدد أقل من الكروموسومات بالعوامل الجينية ، وبالتالي ، ستكون هناك حاجة إلى مزيد من التكرارات للحل.

ستؤدي زيادة الأرقام إلى تسريع الخوارزمية ، ولكنها ستجعل الحل أيضًا غير مستقر. لن يتم الحفاظ على الكروموسومات الملائمة فحسب ، بل ستتأثر أيضًا بالعوامل الجينية. لذلك ، سوف يفقدون جيناتهم "الجيدة".

من المهم إيجاد توازن جيد. ستؤدي زيادة عدد التكرارات إلى منح الخوارزمية المزيد من الفرص لإيجاد حل ، ولكن من ناحية أخرى ، سيستغرق الأمر مزيدًا من الوقت. يمكنك أيضًا تطبيق طرق مختلفة للتقاطع والطفرة. سيؤدي الاختيار الجيد لهؤلاء المشغلين إلى تحسين جودة الحل بشكل كبير.

ماذا بعد؟

لقد غطينا فقط غيض من فيض هنا. أخذنا مثالًا يحتوي على مُدخل واحد فقط ، ويمكن تقديم المُدخلات بسهولة ككروموسوم. العوامل الجينية واضحة وبسيطة.

من المثير للاهتمام تناول مشكلة حقيقية وتطبيق الخوارزمية الجينية عليها. سوف تكتشف طرقًا مختلفة في ترميز بيانات الإدخال الحقيقية بالإضافة إلى تطبيقات التبادل والتحول المختلفة.

إذا كان من الممكن التعبير عن مشكلة من خلال مجموعة من المعلمات التي يتعين علينا تخمينها لتحسين أحد المقاييس ، فيمكننا إعداد GA بسرعة يمكننا استخدامها لحلها.

واحدة من أكثر المشاكل إثارة للاهتمام هي تدريس الشبكات العصبية الاصطناعية. يمكننا تعيين المعلمات القابلة للتحسين لتكون نقاط قوة المشبك ، ومقياس اللياقة ليكون النسبة المئوية للمدخلات التي أعطت شبكتنا العصبية الإجابة الصحيحة لها. بعد ذلك ، يمكننا الجلوس والسماح لشبكتنا العصبية بالتطور إلى الحل المثالي الذي نرغب فيه. أو على الأقل حتى نحصل على شيء جيد بما فيه الكفاية ، لأن التطور يستغرق وقتًا.