تطبيق التقاطع والطفرة على رسم بياني (خوارزمية وراثية)

Question

ألعب مع خوارزمية وراثية أريد أن أتطور فيها الرسوم البيانية. هل تعرف طريقة لتطبيق التقاطع والطفرة عندما تكون الكروموسومات عبارة عن رسومات بيانية؟

أو هل أفتقد ترميزًا للرسوم البيانية التي تسمح لي بتطبيق التقاطع "العادي" والطفرة على سلاسل البت؟

شكر كثيرا! أي مساعدة ، حتى لو لم تكن مرتبطة بشكل مباشر بمشكلتي ، يتم تقديرها!

مانويل

Answer 1

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

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

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

_{(مصدر: Natekohl.net)}

(في هذا المثال ، كل جين هو صندوق ويمثل اتصالًا بين العقدتين. الرقم الموجود في الجزء العلوي من كل جين هو العلامة التاريخية لهذا الجين.)

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

Answer 2

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

_{(مصدر: GeneticProgramming.com)}

إليكم كيف يعمل كروس للأشجار (والرسوم البيانية):

1. يمكنك تحديد 2 عينات للتزاوج.
2. يمكنك اختيار عقدة عشوائية من أحد الوالدين وتبديلها بعقدة عشوائية في الوالد الآخر.
3. الأشجار الناتجة هي ذرية.

Answer 3

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

بدلاً من ذلك ، إذا كنت تمثل رسمًا بيانيًا كمصفوفة مجاورة ، فيمكنك تبديل/تحور العناصر في المصفوفات (نوع من استخدام سلسلة بت ثنائية الأبعاد).

Answer 4

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

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

Crossover: خذ بعض الأوزان من أحد الوالدين ، الباقي من الآخر ، يمكن القيام به بسهولة بالغة إذا كنت تمثل الأوزان كصفيف أو قائمة. لمزيد من التفاصيل أو البدائل انظر http://en.wikipedia.org/wiki/Crossover_٪28GENECT_ALGORITHM٪29.

طفرة: ببساطة حدد بعض الأوزان وضبطها قليلاً.

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

إذا كنت ترغب أيضًا في تطوير الطوبولوجيا ، فإن الأمور تصبح أكثر إثارة للاهتمام. هناك بعض إمكانيات الطفرة الإضافية ، مثل إضافة عقدة (على الأرجح متصلة بعقدتين موجودتين بالفعل) ، تقسيم الاتصال (بدلاً من a-> b لها a-> c-> b) ، إضافة اتصال ، أو الأضداد من هؤلاء.

لكن التبادل لن يكون سهلاً للغاية (على الأقل إذا لم يتم إصلاح عدد العقد) ، لأنك ربما ترغب في العثور على العقد "المطابقة" (حيث يمكن أن يكون المطابقة أي شيء ، ولكن من المحتمل أن يكون مرتبطًا بـ "دور" مماثل أو مكان مماثل في الشبكة). إذا كنت تريد أيضًا القيام بذلك ، فإنني أوصي بشدة بدراسة التقنيات الموجودة بالفعل. واحد الذي أعرفه وما شابه يسمى أنيق. يمكنك العثور على بعض المعلومات حول هذا الموضوع في
http://en.wikipedia.org/wiki/neuroevolution_of_augmenting_topologies
http://nn.cs.utexas.edu/؟neat
و http://www.cs.ucf.edu/~kstanley/neat.html

Answer 5

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