(الإصدار 2 ، مع الأخطاء المطبعية تصحيح - آمل أن الجميع ...)
مرحبا يا هبر!
الآن كان جالسًا ، يصنع نموذجًا أوليًا للخوارزمية الوراثية لأحد الأصدقاء. من وحي لمشاركته ، وبعض الأفكار الأخرى ...
المعطى (طلب العميل): في
مملكة معينة
، يحتوي المستودع على 100 خلية. البضائع في ذلك. كيف تأخذ الكمية X لتفريغ جميع الخلايا المعنية حتى النهاية؟ حسنًا ، لديك نوع من الخلايا [34 ، 10 ، 32 ، 32 ، 33 ، 41 ، 44 ، 4 ، 28 ، 23 ، 22 ، 28 ، 29 ، 14 ، 28 ، 15 ، 38 ، 49 ، 30 ، 24 ، 18 ، 9 ، 15 ، 8 ، 17 ، 9 ، 2 ، 7 ، 30 ، 29 ، 29 ، 2 ، 28 ، 23 ، 19 ، 4 ، 15 ، 30 ، 38 ، 3 ، 14 ، 21 ، 43 ، 50 ، 29 ، 14 ، 17 ، 12 ، 25 ، 15 ، 23 ، 28 ، 47 ، 38 ، 29 ، 7 ، 36 ، 45 ، 25 ، 6 ، 25 ، 11 ، 10 ، 1 ، 19 ، 37 ، 24 ، 27 ، 50 ، 12 ، 1 ، 1 ، 44 ، 22 ، 48 ، 13 ، 46 ، 49 ، 11 ، 33 ، 29 ، 4 ، 19 ، 33 ، 12 ، 3 ، 47 ، 27 ، 26 ، 45 ، 40 ، 37 ، 21 ، 2 ، 8 ، 41 ، 5 ، 1 ، 9 ، 5] - كيفية الاتصال ، مثلا ، 40
حسنًا ، يمكنك التمثال ، بالتأكيد هناك شيء ذكي ، ولكن يمكنك حلها باستخدام خوارزمية وراثية ...
السؤال الأول: لماذا تجف أدمغتك ، لأنه إذا ذهبت للتو من خلال القائمة ، فعليك أن تأخذ من أول خليتين لهذا - والثاني ، مع ذلك ، سيكون الباقي. ولن تضطر إلى الذهاب بعيدًا. ولكن لنرى ، العميل هو الكمال ، فهو يريد أن يكون مثل صيدلية. ربما في مستودع خلية يستحق وزنه بالذهب. هذا يحدث.
السؤال الثاني: إذا قمت بفرزها بترتيب تصاعدي ، فيمكنك بالتأكيد سحب الكثير من الخلايا ... في مثالنا ، هناك الكثير من الخلايا التي تحتوي على أقل من عشر خلايا. ربما ، لا يريد العميل أيضًا ؛) صادفت هؤلاء الأشخاص أيضًا: أنا الرئيس هنا. قالوا لك - افعلها ولا تسأل أسئلة.
(حسنًا ، لا موكلي ، وإلا فقد فقدت الثقة في العقل البشري ...)
حسنًا ، الله معه ، لكل شخص أولوياته الخاصة ... ثم سنتحدث عن الخوارزميات الجينية - يجب علينا حل هذه المشكلة بطريقة ما ... سنكتب بلغة جافا.
بالنسبة لأولئك الذين لم يسمعوا عنها من قبل: تقليد الطبيعة الأم.
- تشفير السلوكيات
- نحن نتحقق من مدى عمل كل خيار بمساعدة معيار مناسب
- أفضل تمرير على سماتها إلى الجيل القادم
في الخطوة الأخيرة في الطبيعة ، هناك مكونان: العبور (تبادل الأحرف بين الأجزاء نفسها من الكروموسوم) والطفرة (التغيرات التلقائية في الشفرة الوراثية). مرحبا ، المدرسة الثانوية ؛)
ربما هذا كل شيء. سنقوم بتدوين الخلايا التي ستأخذ منها ، والتي لن نتخذها. لدينا 100 خلية ، مما يعني أن كروموسومنا سيكون من 100 عنصر حقيقي / خاطئ ، ولهذا أخذت سلسلة ، حيث سيتم كتابة الأصفار والأخرى. هم ، بالطبع ، سيكون 100.
المعيار هو أهم شيء في هذه العملية. تبحث الطبيعة عن مكانة ملائمة ، وستبحث طبيعة الكمبيوتر عن وجود ثقب في معيارك لخداعها والبقاء على قيد الحياة. رائع ، بصراحة ...
مع كل ما قيل ، شيء مثل هذا:
private static int benchmark(String chromosome, boolean verbose) { int sum = 0; char[] cArr = chromosome.toCharArray(); for (int i = 0; i < cnt_bins; i++) { if (cArr[i] == '1') { sum += stock[i]; if (verbose) System.out.println("storage bin " + i + ":\t+" + stock[i] + "\t= " + sum); } if (sum == target_qty) { return 0; } } return Math.abs(target_qty - sum); }
والفكرة هي أنه كلما ابتعدنا عن العدد المرغوب 40 ، كان الأسوأ. إذا سجلنا 40 ، فلنذهب إلى أبعد من ذلك في الصبغي ، فزنا. سنقوم ، بالطبع ، بترتيب زيادة الطلب - كلما قلت نقاط الجزاء ، كلما كان ذلك أفضل.
يتم إنشاء الجيل الأول بشكل عشوائي:
نظرًا لأن الخوارزمية الجينية ، في الواقع ، تقترب من الهدف ، ولكنها لا تحققه دائمًا ، فمن المهم الحد من عدد الأجيال.
for (int generationNo = 0; generationNo < maxGenerationCnt; generationNo++) {
التصنيف ، اترك الأفضل:
...
نحن نتكاثر ونتضاعف ونستعيد حجم السكان. أي أننا نختار الآباء بشكل عشوائي ، ونجمع بين نفس العلامات (إذا كنت محظوظًا - انظر علامة التبادل) ، وتغير (علامة تحول) ، انتظر المعجزة ...
حسنًا ، إليك معجزة:القيمة المستهدفة: 40
الأسهم: [34 ، 10 ، 32 ، 32 ، 33 ، 41 ، 44 ، 4 ، 28 ، 23 ، 22 ، 28 ، 29 ، 14 ، 28 ، 15 ، 38 ، 49 ، 30 ، 24 ، 18 ، 9 ، 15 ، 8 ، 17 ، 9 ، 2 ، 7 ، 30 ، 29 ، 29 ، 2 ، 28 ، 23 ، 19 ، 4 ، 15 ، 30 ، 38 ، 3 ، 14 ، 21 ، 43 ، 50 ، 29 ، 14 ، 17 ، 12 ، 25 و 15 و 23 و 28 و 47 و 38 و 29 و 7 و 36 و 45 و 25 و 6 و 25 و 11 و 10 و 1 و 19 و 37 و 24 و 27 و 50 و 12 و 1 و 1 و 44 و 22 ، 48 ، 13 ، 46 ، 49 ، 11 ، 33 ، 29 ، 4 ، 19 ، 33 ، 12 ، 3 ، 47 ، 27 ، 26 ، 45 ، 40 ، 37 ، 21 ، 2 ، 8 ، 41 ، 5 ، 1 ، 9 ، 5]
الجيل 0 ؛ أفضل / آخر الوالدين / الأسوأ: 705/991/1580
الجيل 1 ؛ أفضل / آخر الوالدين / أسوأ: 576/846/1175
الجيل 2 ؛ أفضل / آخر الوالدين / أسوأ: 451/722/1108
الجيل 3 ؛ أفضل / آخر الوالدين / أسوأ: 0/613/904
وجدت الحل
صندوق تخزين 7: +4 = 4
صندوق تخزين 10: +22 = 26
صندوق تخزين 13: +14 = 40
وهنا هو الكود كله package ypk; import java.io.IOException; import java.io.StringWriter; import java.util.AbstractMap.SimpleEntry; import java.util.stream.Collectors; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Random; public class YPK { private static int generation_size = 1000; private static int best_size = 200; private static int cnt_bins = 100; private static int max_stock = 50; private static double exchange_rate = .2; private static double mutation_rate = .01; private static Random rnd = new Random(); private static int target_qty = rnd.nextInt(cnt_bins * max_stock / 5);
وأخيراً: إذا اختلطت بالمعلمات - الكثير من الطفرات ، وصغر حجم السكان ، إلخ. - سوف الركود أو حتى إعطاء كل أسوأ النتائج.
هذه المشكلة ، بالمناسبة ، غالباً ما يتم حلها بشكل عشوائي بالفعل وليس هناك حاجة للأجيال القادمة :) إذا كنت ترغب في تعقيد حياة الكمبيوتر ، فقم بإزالة هذا العائد من المعيار:
if (sum == target_qty) { return 0; }
هذا سوف يعقد المهمة ويجعل الكمبيوتر يعاني قليلا ...
حظا سعيدا
m_OO_m