피트니스 룰렛 선택을 효율적으로 구현

Question

저는 C에서 키보드 레이아웃 최적화 알고리즘 (Peter Klausler가 디자인 한 알고리즘)을 작성하고 있으며 여기에 설명 된 피트니스 비례 선택을 구현하려고합니다 (PDF Link) : 룰렛 선택과

당신은 roullete 휠 모델을 기반으로 인구의 멤버를 선택합니다. 원형 차트를 만듭니다. 여기서 멤버의 슬라이스 영역 전체가 이고 전체 구성원 수는 입니다. 당신이 볼 수 있듯이 원의 외연에 점이 무작위로 선택된 인 경우 더 높은 적합도를 가진 구성원 은 더 높은 확률로 을 가질 것입니다. 자연 선택은 자리를 차지하도록합니다.

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

우선, 느린 하나를 길이 N의 키보드 풀의

이 길이의 배열을 만들 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; 

을 (이 경우 A의 낮은 체력은 더 적은 노력이 필요하다는 것을 의미하므로 더 낫습니다.)

그런 다음 난수를 생성하십시오. 숫자가 어느 범위에 속하는지에 따라 해당 키보드는 "kill"되어 다른 키보드의 자손으로 대체됩니다. 원하는만큼 반복하십시오.

이 문제는 매우 느립니다. 완료하려면 O (N^2) 작업이 필요합니다.

다음으로 빠른 방법 1 : 키보드의 최저 및 최고 fitnesses이 무엇인지

첫 번째 그림 밖으로. 그런 다음 (가장 낮은 적합도)와 (가장 높은 적합도) 사이의 임의의 숫자를 생성하고 생성 된 숫자보다 높은 적합성을 갖는 모든 키보드를 제거합니다. 이것은 효율적이지만 키보드 절반 만 제거 할 수있는 것은 아닙니다. 그것은 또한 "룰렛 휠"선택과는 다소 다른 메커니즘을 가지고 있기 때문에 적용되지 않을 수도 있습니다.

그럼 효과적인 구현이란 무엇입니까?

이 책의 36 페이지 (Link)에는 다소 효율적인 알고리즘이 있지만 문제는 룰렛 선택을 한 번 또는 몇 번만하면 효율적이라는 것입니다. 병렬로 많은 룰렛 선택을하는 효율적인 방법이 있습니까? 당신이 (높은 점수 키보드 될 가능성이 높습니다) 선택을 "죽일"하려는 경우에 대한 부적합 점수를 이야기처럼 한 가지를 들어

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)의 시간이 소요 : 나는 가장 간단한 방법은 당신이 다음 선택을 통해 반복 점수의 단일 배열을 유지하는 것입니다 생각합니다.