التنفيذ الفعال للاختيار "الروليت" متناسق

Question

أنا حاليا كتابة خوارزمية تحسين تخطيط لوحة المفاتيح في ج (مثل واحد صمم من قبل بيتر كلاوزلر) وأريد تنفيذ اختيار متناسك للياقة البدنية كما هو موضح هنا (رابط PDF):

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

المشكلة هي أنه لا أرى كيفية تنفيذها بكفاءة. لقد فكرت بطريقتين: واحد غير موثوق به، والآخر بطيء.

أولا، واحد بطيء:

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

array[0][0] = 0; // minimum
array[0][1] = 9; // maximum
array[1][0] = 10;
array[1][1] = 30;
array[2][0] = 31;
array[2][1] = 55;

(في هذه الحالة، يكون انخفاض اللياقة البدنية أفضل، لأنه يعني جهد أقل مطلوبا.)

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

المشكلة مع هذا هو أنه بطيء جدا. يستغرق عمليات O (N ^ 2) لإنهاءها.

التالي واحد سريع:

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

إذن السؤال هو، ما هو التنفيذ الفعال؟

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

Answer 1

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

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

/* These will need to be populated at the outset */
int scores[100];
int totalScore;

for (gen = 0; gen < nGenerations; ++gen) {
    /* Perform a selection and update */
    int r = rand() % totalScore;        /* HACK: using % introduces bias */
    int t = 0;
    for (i = 0; i < 100; ++i) {
        t += scores[i];
        if (r < t) {
            /* Bingo! */
            totalScore -= scores[i];
            keyboards[i] = generate_new_keyboard_somehow();
            scores[i] = score_keyboard(keyboards[i]);
            totalScore += scores[i];    /* Now totalScore is correct again */
        }
    }
}

يأخذ كل اختيار / تحديث س (ن) وقت لوحات المفاتيح N.