피트니스 프로모션 "룰렛"선택의 효율적인 구현

Question

현재 C (Peter Klausler가 디자인 한 것과 같은)에서 키보드 레이아웃 최적화 알고리즘을 작성하고 있으며 여기에 설명 된대로 피트니스 프로모션 선택을 구현하고 싶습니다 (PDF 링크):

룰렛 선택을 사용하면 Roullete 휠 모델을 기반으로 인구 구성원을 선택합니다. 회원의 슬라이스 영역이 전체 원의 전체 인구와의 비율 인 원형 차트를 만드십시오. 당신이 원의 경계에 대한 지점이 무작위로 선택되는지 알 수 있듯이, 더 높은 인구가 높은 인구 구성원은 더 높은 선택 가능성을 가질 것입니다. 이것은 자연 선택이 이루어 지도록합니다.

문제는 효율적으로 구현하는 방법이 없다는 것입니다. 나는 두 가지 방법을 생각했습니다. 하나는 신뢰할 수없고 다른 방법은 느립니다.

첫째, 느린 것 :

길이 n의 키보드 풀의 경우, 배열의 각 요소에 실제로 최소 및 최대 값의 두 가지 요소가 포함 된 길이 n 배열을 만듭니다. 각 키보드에는 해당 최소 및 최대 값이 있으며 범위는 키보드의 체력을 기반으로합니다. 예를 들어, 키보드 제로가 피트니스가 10 인 경우 키보드 1은 피트니스가 20이고 키보드 2는 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

우선, 당신이 말하는 것처럼 들립니다. 부적합 선택한 선택 (키보드가 될 가능성이 높습니다. 높은 점수).

두 배열을 유지할 필요가 없습니다. 가장 간단한 방법은 단일 점수를 유지하는 것입니다. 그런 다음 선택하기 위해 반복합니다.

/* 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 키보드에 대한 O (N) 시간이 걸립니다.