باستخدام GA في واجهة المستخدم الرسومية

Question

آسف إذا لم يكن هذا واضحًا لأنني أكتب هذا على جهاز محمول وأحاول أن أجعله سريعًا.

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

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

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

حسب الطلب ، تم تصميم الفرد باستخدام فئة منفصلة (Indiv) ، مع كل الأعمال الرئيسية التي يتم في فئة البوب. عندما يتم تثبيت شخص جديد ، تمثل مجموعة من int جينات الفرد المذكور ، حيث يتم اختيار الجينات عشوائيًا من رقم بين 0 و 1. وتضيف وظيفة اللياقة فقط قيمة هذه الجينات وفي اختيار فئة POP. ، طفرة والتقاطع بين شخصين مختارين. لا يوجد الكثير من الأشياء الأخرى ، ويظهر برنامج سطر الأوامر التطور على مدى أجيال ن مع تحسن اللياقة الكلية على كل تكرار.

تحرير: لقد بدأ الأمر أكثر منطقية الآن ، على الرغم من وجود بعض الأشياء التي تزعجني ...

كما اقترح Adamski أنني أريد إنشاء "وكيل" مع الخيارات الموضحة أدناه. المشكلة التي أمتلكها هي المكان الذي تدخل فيه سلسلة البتات العشوائية هنا. يعرف الوكيل مكان وجود الجدران وهل وضعه في سلسلة 4 بت (أي 0111) ، ولكن كيف يؤثر هذا على سلسلة عشوائية 32 بت؟ (أي 1000101101100100110011101101011) إذا كان لدي المتاهة التالية (x هي مكان البدء ، 2 هو الهدف ، 1 هو الجدار):

x 1 1 1 1
0 0 1 0 0
1 0 0 0 2

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

لذلك ، للحصول على هذا مستقيم ...

اللياقة هي نتيجة عندما يكون الوكيل قادرًا على التحرك وهو بجدار.

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

هل هذا صحيح؟

Answer 1

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

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

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

FBLR Action
0000 Move Forward
0001 Move Forward
0010 Turn Right
etc

يمنحك هذا سلسلة صغيرة تتكون من 16 إجراءً ، كل إجراء مشفر على أنه 2 بت (00 = تحرك للأمام ، 01 = انعطف يمينًا ، 10 = انعطف يسارًا ، 11 = تحرك للخلف). عند تقييم وكيلك ، فإنه يحدد ببساطة حالته الحالية ويستخدم سلسلة البت كجدول بحث لتحديد كيفية الاستجابة له. ثم يكرر هذا عددًا معينًا من المرات التي تُقوم فيها إلى تقييم لياقتها.

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

امل ان يساعد.

تعديل

ردا على آخر تحرير:

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

لذلك يجب عليك كتابة رمز للبحث عن الجزء ذي الصلة من سلسلة البت المعطى مجموعة معينة من قراءات المستشعرات ؛ على سبيل المثال

/**
 * Enumeration describing the four available actions to the agent
 * and methods for decoding a given action from the "bit" string
 * (actually represented using booleans).
 */
public enum Action {
  MOVE_FORWARD, REVERSE, TURN_LEFT, TURN_RIGHT

  Action decodeAction(boolean b1, boolean b2) {
    Action ret;

    if (b1) {
      ret = b2 ? Action.MOVE_FORWARD : Action.TURN_LEFT;
    } else {
      ret = b2 ? Action.TURN_RIGHT : Action.REVERSE;
    }

    return ret;
  }
}

/**
 * Class encapsulating the 32-bit "bit string" represented using booleans.
 * Given the state of the four agent inputs the gene will provide a specific
 * action for the agent to perform.
 */
public class Gene {
  private final boolean[] values = new boolean[32];

  public Action getActionForSensorInputs(boolean wallInFront,
    boolean wallBehind, boolean wallToLeft, boolean wallToRight) {

    int i=0;

    // Encode the four sensor inputs as a single integer value by
    // bitwise-ORing each sensor value with a power of 2.
    // The encoded value will be in the range [0, 15].
    if (wallToRight) {
      i |= 0x01;
    }

    if (wallToLeft) {
      i |= 0x02;
    }

    if (wallBehind) {
      i |= 0x04;
    }

    if (wallInFront) {
      i |= 0x08;
    }

    // The look-up index is i * 2 because each action is encoded as 2
    // booleans.
    int index = i * 2;

    // Retrieve the two action bits from the bit string.
    boolean b1 = this.values[index];
    boolean b2 = this.values[index + 1];

    // Finally decode the action to perform.
    return Action.decodeAction(b1, b2);
  }

  // TODO: Add method to support crossover and mutation with other Genes.
}

بالنظر إلى هذا التعريف البسيط لـ Gene يمكنك تضمين هذه الفئة داخل Agent تنفيذ وتسجيل كيفية أداء الوكيل مع الجين الحالي "مثبت" ؛ على سبيل المثال

private enum Direction { NORTH, SOUTH, EAST, WEST };

public class Agent {
  private final Geneva gene;
  private final int x; // x position in maze;
  private final int y; // y position in maze;
  private Direction currentDirection;

  public double evaluate() {
    double fitness;

    // Perform up to 20 actions and then evaluate fitness.
    for (int i=0; i<20; ++i) {
      // TODO Determine sensor inputs.

      Action action = gene.getActionForSensorInputs(...);

      // TODO: Now apply action to update agent's state.
      // If agent has reached goal exit loop and return fitness 1.0 (max fitness).
      // If agent has exited the maze then exit loop and return 0.0 (min fitness).
    }

    // Calculate fitness after 100 steps taken.  For example could be
    // calculated as sqrt((goal.x - x) ^ 2 + (goal.y - y) ^ 2).

    return fitness;
  }
}

Answer 2

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

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

يتمثل تمثيل بسيط للغاية للحركة في السماح للجينات بربح طريق معين. يمكنك استخدام كتل من أربعة جينات لتمثيل الاتجاهات المختلفة ، ثم تمثل 0 "لا تتحرك في هذا الاتجاه" ويمثل 1 الحركة.

ثم التمثيل 01001101 يمكن ترجمتها كنمط الحركة التالي:

stand still
go one step east
stand still
stand still
go one step north
go one step east
stand still
go one step west