ما هي الأمثلة الجيدة للخوارزميات الجينية/حلول البرمجة الجينية؟[مغلق]

Question

الخوارزميات الجينية (جا) و البرمجة الجينية (GP) هي مجالات بحثية مثيرة للاهتمام.

أود أن أعرف عن المشكلات المحددة التي قمت بحلها باستخدام GA/GP وما هي المكتبات/أطر العمل التي استخدمتها إذا لم تقم بإنشاء مكتبتك الخاصة.

أسئلة:

• ما هي المشاكل التي استخدمت GA/GP لحلها؟
• ما المكتبات/الأطر التي استخدمتها؟

أنا أبحث عن تجارب مباشرة، لذا يرجى عدم الإجابة إلا إذا كان لديك ذلك.

Answer 1

لا العمل في المنزل.

كانت وظيفتي الأولى كمبرمج محترف (1995) هي كتابة نظام تداول آلي قائم على الخوارزمية الجينية لعقود S&P500 الآجلة.تم كتابة التطبيق في Visual Basic 3 [!] وليس لدي أي فكرة عن كيفية القيام بأي شيء في ذلك الوقت، حيث أن VB3 لم يكن لديه حتى فئات.

بدأ التطبيق بمجموعة من السلاسل ذات الطول الثابت التي تم إنشاؤها عشوائيًا (الجزء "الجيني")، والتي يتوافق كل منها مع شكل محدد في بيانات الأسعار الدقيقة لعقود S&P500 الآجلة، بالإضافة إلى أمر محدد. (شراء أو بيع) ومبالغ وقف الخسارة ووقف الربح.تم تقييم أداء أرباح كل سلسلة (أو "جين") من خلال 3 سنوات من البيانات التاريخية؛كلما تطابق "الشكل" المحدد مع البيانات التاريخية، افترضت أمر الشراء أو البيع المقابل وقمت بتقييم نتيجة التجارة.أضفت التحذير بأن كل جين بدأ بمبلغ ثابت من المال وبالتالي من المحتمل أن يفلس ويتم إزالته من مجموعة الجينات بالكامل.

بعد كل تقييم للسكان، تم تهجين الناجين بشكل عشوائي (عن طريق خلط أجزاء من أبوين فقط)، مع تناسب احتمال اختيار الجين كوالد مع الربح الذي ينتجه.أضفت أيضًا إمكانية حدوث طفرات نقطية لإضفاء الإثارة على الأشياء قليلاً.وبعد بضع مئات من الأجيال من هذا، انتهى بي الأمر بمجموعة من الجينات التي يمكن أن تحول 5000 دولار إلى متوسط ​​قدره حوالي 10000 دولار دون أي فرصة للوفاة/الكسر (وفقًا للبيانات التاريخية بالطبع).

لسوء الحظ، لم تتح لي الفرصة أبدًا لاستخدام هذا النظام بشكل مباشر، حيث خسر مديري ما يقرب من 100000 دولار في أقل من 3 أشهر من التداول بالطريقة التقليدية، كما فقد رغبته في الاستمرار في المشروع.إذا نظرت إلى الماضي، أعتقد أن النظام كان سيحقق أرباحًا ضخمة - ليس لأنني بالضرورة كنت أفعل أي شيء صحيح، ولكن لأن مجموعة الجينات التي أنتجتها كانت متحيزة نحو أوامر الشراء (بدلاً من أوامر البيع) بحوالي 5: 1 نسبة.وكما نعلم بعد فوات الأوان 20/20، ارتفع السوق قليلاً بعد عام 1995.

Answer 2

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

بدأ البرنامج بمجموعة عشوائية من المخلوقات ذات أدمغة عشوائية.كانت الخلايا العصبية المدخلة والمخرجة ثابتة ولكن ما كان بينهما لم يكن كذلك.

البيئة تحتوي على الغذاء والمخاطر.يزيد الطعام من الطاقة وعندما يكون لديك ما يكفي من الطاقة يمكنك التزاوج.ستؤدي المخاطر إلى تقليل الطاقة وإذا كانت الطاقة 0 ماتوا.

وفي النهاية تطورت المخلوقات لتتنقل حول العالم وتجد الطعام وتتجنب المخاطر.

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

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

فما هو الدرس هنا؟التواصل يعني التعاون.بمجرد تقديم عنصر حيث إيذاء شخص آخر يعني حصولك على شيء ما، يتم تدمير التعاون.

وأتساءل كيف ينعكس هذا على نظام الأسواق الحرة والرأسمالية.أعني، إذا كان بإمكان الشركات الإضرار بمنافستها و تفلت من العقاب, فمن الواضح أنهم سيفعلون كل ما في وسعهم للإضرار بالمنافسة.

يحرر:

لقد كتبته بلغة C++ بدون أي أطر عمل.كتبت الشبكة العصبية الخاصة بي ورمز GA.إريك، شكرًا لك على قولك أن هذا أمر معقول.عادة لا يؤمن الناس بصلاحيات GA (على الرغم من أن القيود واضحة) حتى يلعبوا بها.GA بسيط ولكنه ليس تبسيطيًا.

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

إليك الكود التجريبي لمثال البقاء: http://www.mempko.com/darcs/neural/demos/eaters/تعليمات البناء:

• تثبيت darcs، libboost، liballegro، gcc، cmake، make
• darcs clone --lazy http://www.mempko.com/darcs/neural/
• cd neural
• cmake .
• make
• cd demos/eaters
• ./eaters

Answer 3

في يناير 2004، اتصلت بي شركة Philips New Display Technologies التي كانت تصنع الأجهزة الإلكترونية لأول حبر إلكتروني تجاري على الإطلاق، وهو Sony Librie، الذي تم طرحه في اليابان فقط، قبل سنوات من وصول Amazon Kindle والآخرين إلى السوق في الولايات المتحدة. أوروبا.

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

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

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

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

لم أتقاضى سنتًا واحدًا مقابل ذلك، لكني حصلت على حقوق "التفاخر".قالوا منذ البداية أنهم تجاوزوا الميزانية بالفعل، لذلك كنت أعرف ما هي الصفقة قبل أن أبدأ العمل عليها.وهي قصة رائعة لتطبيقات GAs.:)

Answer 4

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

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

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

تحديث:لأن بعض الناس سألوا كيف...

ابدأ بمجموعة من الضيوف (أو المدن) بترتيب عشوائي ولكن متسق، على سبيل المثال، حسب الترتيب الأبجدي.نسمي هذا الحل المرجعي.فكر في فهرس الضيف كرقم مقعده.

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

وبالتالي يمكن توليد الكروموسومات بشكل عشوائي، وتحورها، وتهجينها مع الآخرين، وسوف تنتج دائمًا حلاً صالحًا.

Answer 5

لقد استخدمت الخوارزميات الجينية (بالإضافة إلى بعض التقنيات ذات الصلة) لتحديد أفضل الإعدادات لنظام إدارة المخاطر الذي حاول منع مزارعي الذهب من استخدام بطاقات الائتمان المسروقة لدفع ثمن ألعاب MMO.سيستقبل النظام عدة آلاف من المعاملات ذات القيم "المعروفة" (احتيال أم لا) ويكتشف أفضل مجموعة من الإعدادات لتحديد المعاملات الاحتيالية بشكل صحيح دون وجود الكثير من النتائج الإيجابية الخاطئة.

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

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

انتهى هذا الأمر إلى تحديد الغالبية العظمى من عمليات الاحتيال التي حدثت، لكنه لم يتمكن من جعلها أقل من 1% على العناصر الأكثر عرضة للاحتيال (بالنظر إلى أن 90% من المعاملات الواردة يمكن أن تكون احتيالًا، كان ذلك جيدًا جدًا).

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

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

Answer 6

البقشيش لكرة القدم.لقد قمت ببناء نظام GA للتنبؤ بنتائج المباريات الأسبوعية في AFL (قواعد كرة القدم الأسترالية).

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

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

ومن الناحية العملية، سيجد النظام حلولاً تنبأت بدقة بأكثر من 90% من نتائج الألعاب السابقة.سيتم بعد ذلك اختيار حوالي 60-80% من الألعاب بنجاح للأسبوع القادم (هذا هو الأسبوع غير الموجود في مجموعة التدريب).

النتائج:فقط فوق منتصف العبوة.لا توجد جائزة نقدية كبيرة ولا نظام يمكنني استخدامه للتغلب على فيغاس.لقد كان ممتعا بالرغم من ذلك.

لقد بنيت كل شيء من الصفر، دون استخدام أي إطار.

Answer 7

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

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

أملك الإطار الخاص بي التي أستخدمها للخوارزميات التطورية.

Answer 8

لقد قمت بتطوير مشروب منزلي GA لنظام تشكيل سطح الليزر ثلاثي الأبعاد الذي طورته شركتي لصناعة الشحن في عام 1992.اعتمد النظام على التثليث ثلاثي الأبعاد واستخدم ماسحًا ضوئيًا مخصصًا لخط الليزر وكاميرا مقاس 512 × 512 (مع أدوات التقاط مخصصة).لن تكون المسافة بين الكاميرا والليزر دقيقة أبدًا ولن يتم العثور على النقطة المحورية للكاميرات في الموضع 256,256 الذي توقعته!

لقد كان كابوسًا محاولة تحديد معلمات المعايرة باستخدام الهندسة القياسية ومحاكاة حل المعادلات بأسلوب التلدين.

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

عملت الحيلة علاجًا.لقد شعرت بالذهول على أقل تقدير!في غضون حوالي 10 أجيال، بدا المكعب "الافتراضي" الخاص بي (الذي تم إنشاؤه من المسح الأولي وإعادة إنشائه من معلمات المعايرة) وكأنه مكعب!وبعد حوالي 50 جيلًا حصلت على المعايرة التي أحتاجها.

Answer 9

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

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

ال رجل اللون اعتاد أن يحمل معه برنامجًا يستخدم GA.كان يبدأ بأربعة ألوان مختلفة - كل منها مشفر على شكل كروموسوم مشفر (قيمته التي تم فك تشفيرها ستكون قيمة RGB).يختار المستهلك لونًا واحدًا من الألوان الأربعة (وهو الأقرب إلى ما يفكر فيه).سيقوم البرنامج بعد ذلك بتعيين الحد الأقصى لياقة بدنية إلى ذلك فردي والانتقال إلى التالي جيل استخدام طفرة / كروس.سيتم تكرار الخطوات المذكورة أعلاه حتى يجد المستهلك اللون الدقيق وبعد ذلك رجل اللون تستخدم لنقول له تركيبة RGB!

من خلال تعيين أقصى قدر من الملاءمة للألوان القريبة بما يدور في ذهن المستهلك، فإن رجل اللونيعمل برنامج 's على زيادة فرص التقارب مع اللون الذي يضعه المستهلك في الاعتبار بالضبط.لقد وجدت أنها ممتعة جداً!

الآن بعد أن حصلت على -1، إذا كنت تخطط لمزيد من -1، من فضلك.توضيح سبب القيام بذلك!

Answer 10

كجزء من دراستي الجامعية في CompSci، تم تكليفنا بمشكلة العثور على علامات jvm المثالية للجهاز الظاهري لأبحاث Jikes.تم تقييم ذلك باستخدام مجموعة Dicappo القياسية التي تُرجع وقتًا إلى وحدة التحكم.لقد كتبت خوارزمية جينية موزعة تقوم بتبديل هذه العلامات لتحسين وقت تشغيل مجموعة المعايير، على الرغم من أن الأمر استغرق أيامًا للتشغيل للتعويض عن عدم استقرار الأجهزة الذي يؤثر على النتائج.المشكلة الوحيدة هي أنني لم أتعلم بشكل صحيح عن نظرية المترجم (والتي كانت الهدف من المهمة).

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

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

Answer 11

أولاً، "البرمجة الجينية" لجوناثان كوزا (على الأمازون) هو إلى حد كبير كتاب عن تقنيات الخوارزمية/البرمجة الجينية والتطورية، مع العديد من الأمثلة.أقترح بشدة التحقق من ذلك.

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

Answer 12

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

وفي مجال التعلم الآلي أيضًا، قمت بتطبيق إطار قواعد التصنيف المستند إلى GA في لغة c/c++ من البداية.
لقد استخدمت أيضًا GA في نموذج مشروع للتدريب الشبكات العصبية الاصطناعية (ANN) مقابل استعمال المشهور خوارزمية الانتشار العكسي.

بالإضافة إلى ذلك، وكجزء من بحث التخرج، استخدمت GA في التدريب نماذج ماركوف المخفية كنهج إضافي للقائمة على EM باوم ويلش الخوارزمية (في c/c++ مرة أخرى).

Answer 13

أنا جزء من فريق يبحث في استخدام الحوسبة التطورية (EC) لإصلاح الأخطاء في البرامج الموجودة تلقائيًا.لقد نجحنا في إصلاح عدد من الأخطاء الحقيقية في مشاريع برمجيات العالم الحقيقي (انظر الصفحة الرئيسية لهذا المشروع).

لدينا تطبيقان لتقنية إصلاح EC هذه.

• الأول (معلومات الكود والاستنساخ متاحة من خلال صفحة المشروع) يطور أشجار بناء الجملة المجردة التي تم تحليلها من برامج C الحالية ويتم تنفيذها في Ocaml باستخدام محرك EC المخصص الخاص بنا.

• الثاني (معلومات الكود والاستنساخ متاحة من خلال صفحة المشروع)، مساهمتي الشخصية في المشروع، تعمل على تطوير تجميع x86 أو كود Java بايت المجمع من برامج مكتوبة بعدد من لغات البرمجة.يتم تنفيذ هذا التطبيق في Clojure ويستخدم أيضًا محرك EC المصمم خصيصًا له.

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

Answer 14

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

Answer 15

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

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

Answer 16

لقد قمت بإنشاء إطار عمل GA كامل باسم "GALAB" لحل العديد من المشكلات:

• تحديد موقع GSM ANTs (BTS) لتقليل التداخل والمواقع الفارغة.
• جدولة مشروع قيود الموارد.
• خلق الصورة التطورية.(مثير للإعجاب)
• مشكلة البائع المتجول.
• مشاكل N-Queen وN-Color.
• جولة الفارس ومشاكل الحقيبة.
• المربع السحري وألغاز سودوكو.
• ضغط السلسلة، بناءً على مشكلة السلسلة الفائقة.
• مشكلة التغليف ثنائية الأبعاد.
• تطبيق الحياة الاصطناعية الصغير.
• لغز روبيك.

Answer 17

لقد استخدمت GA ذات مرة لتحسين وظيفة التجزئة لعناوين الذاكرة.كانت العناوين بأحجام صفحات 4K أو 8K، لذلك أظهرت بعض القدرة على التنبؤ في نمط البت الخاص بالعنوان (البتات الأقل أهمية كلها صفر؛تتزايد البتات الوسطى بانتظام، وما إلى ذلك.) كانت وظيفة التجزئة الأصلية "مكتنزة" - وكانت تميل إلى تجميع النتائج في كل مجموعة تجزئة ثالثة.كان للخوارزمية المحسنة توزيع مثالي تقريبًا.

Answer 18

لا أعرف إذا كانت الواجبات المنزلية مهمة...

أثناء دراستي قمنا بإعداد برنامجنا الخاص لحل مشكلة البائع المتجول.

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

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

لقد كانت دورة مثيرة للاهتمام لأننا انخرطنا أيضًا في الشبكات العصبية وما شابه.

أود أن أعرف ما إذا كان أي شخص يستخدم هذا النوع من البرمجة في كود "الإنتاج".

Answer 19

لقد قمت ببناء GA بسيط لاستخراج الأنماط المفيدة من نطاق تردد الموسيقى أثناء تشغيلها.تم استخدام الإخراج لقيادة التأثيرات الرسومية في البرنامج المساعد لبرنامج Winamp.

• مدخل:عدد قليل من إطارات FFT (تخيل مجموعة ثنائية الأبعاد من العوامات)
• انتاج:قيمة تعويم مفردة (المجموع المرجح للمدخلات)، تصل إلى 0.0 أو 1.0
• الجينات:أوزان المدخلات
• وظيفة اللياقة البدنية:مزيج من دورة العمل وعرض النبض وBPM ضمن نطاق معقول.

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

كان أحد الآثار الجانبية المثيرة للاهتمام هو أن متوسط ​​اللياقة البدنية بين السكان كان مؤشرًا جيدًا للتغيرات في الموسيقى، على الرغم من أن الأمر استغرق عمومًا من 4 إلى 5 ثوانٍ لمعرفة ذلك.

Answer 20

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

يمكنك العثور على الرمز هنا.

تمت مقارنة الحلول التي يمكنك العثور عليها مع هذه الخوارزمية في عمل علمي مع الخوارزميات الحديثة SPEA-2 و NSGA ، وقد ثبت أن الخوارزمية تؤدي أداءً قابلاً للمقارنة أو حتى أفضل ، اعتمادًا على المقاييس لك خذ لقياس الأداء ، وخاصة اعتمادًا على مشكلة التحسين التي تبحث عنها.

يمكن ان تجدها هنا.

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

أطروحتي التي تطبق هذا الإطار على مشكلة اختيار المشروع:http://www.ub.tuwien.ac.at/dipl/2008/AC05038968.pdf

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

مزيد من الموارد:

توثيق الإطار:http://thomaskremmel.com/mpoems/mpoems_in_java_documentation.pdf

ورقة العرض التقديمي لـ mPOEMS:http://portal.acm.org/citizen.cfm?id=1792634.1792653

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

Answer 21

في العمل واجهتني المشكلة التالية:في ضوء المهام M وN DSPs، ما هي أفضل طريقة لتعيين المهام إلى DSPs؟تم تعريف "الأفضل" على أنه "تقليل حمل DSP الأكثر تحميلًا".كانت هناك أنواع مختلفة من المهام، وكان لأنواع المهام المختلفة تداعيات مختلفة على الأداء اعتمادًا على المكان الذي تم تعيينها فيه، لذلك قمت بتشفير مجموعة تعيينات المهمة إلى DSP باعتبارها "سلسلة DNA" ثم استخدمت خوارزمية جينية "للتكاثر" أفضل سلسلة مهمة يمكنني القيام بها.

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

Answer 22

كانت هناك منافسة على موقع codechef.com (موقع رائع بالمناسبة، مسابقات برمجة شهرية) حيث كان من المفترض أن يقوم الشخص بحل لعبة سودوكو غير قابلة للحل (يجب على المرء أن يقترب قدر الإمكان مع أقل عدد ممكن من الأعمدة/الصفوف/الخائفة قدر الإمكان).

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

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

Answer 23

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

Answer 24

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

Answer 25

في المرحلة الجامعية، استخدمنا NERO (مزيج من الشبكة العصبية والخوارزمية الجينية) لتعليم الروبوتات داخل اللعبة كيفية اتخاذ قرارات ذكية.لقد كان رائعًا.

Answer 26

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

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

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

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

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

Answer 27

لقد حاولت ذات مرة أن أصنع مشغل كمبيوتر للعبة Go، معتمدًا حصريًا على البرمجة الجينية.سيتم التعامل مع كل برنامج كوظيفة تقييم لسلسلة من التحركات.ومع ذلك، لم تكن البرامج التي تم إنتاجها جيدة جدًا، حتى على لوحة صغيرة الحجم مقاس 3x4.

لقد استخدمت لغة Perl، وقمت بتشفير كل شيء بنفسي.سأفعل الأشياء بشكل مختلف اليوم.

Answer 28

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

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

Answer 29

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

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

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

المكتبات المستخدمة:إذا كنت أتذكر بشكل صحيح، IRAF وcfitsio لمعالجة بيانات الصور الفلكية والإدخال/الإخراج.

Answer 30

لقد قمت بتجربة GA في شبابي.لقد كتبت محاكاة في بايثون تعمل على النحو التالي.

قامت الجينات بتشفير أوزان الشبكة العصبية.

كانت مدخلات الشبكة العصبية عبارة عن "هوائيات" تكتشف اللمسات.القيم الأعلى تعني القرب الشديد والصفر يعني عدم اللمس.

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

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

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

ثم قمت بإقرانهم و"تربيتهم" لإنشاء الجيل القادم.كانت احتمالية اختياره للتكاثر متناسبة مع لياقته.في بعض الأحيان كان هذا يعني أن الفرد قد تم تربيته مع نفسه بشكل متكرر إذا كان يتمتع بلياقة نسبية عالية جدًا.

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

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

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

لقد جربت أشياء مختلفة مثل وجود مجموعات جينية منفصلة لا تتجمع إلا بعد 100 جيل.لكن لا شيء يمكن أن يدفعهم إلى استراتيجية أفضل.ربما كان الأمر مستحيلا.

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