유전자 알고리즘을 사용한 드문 매개 변수 선택

Question

유전자 알고리즘 (GA)을 사용하여 해결하고 싶은 매개 변수 선택 문제에 직면 해 있습니다. 가능한 3000 개 중 4 개 이하의 매개 변수를 선택하지 않아야합니다. 이진 염색체 표현을 사용하는 것은 자연스러운 선택처럼 보입니다. 평가 함수는 너무 많은 "선택된"속성을 처벌하고 속성 수를 허용하는 경우 선택을 평가합니다.

문제는 이러한 희소 조건에서 GA가 인구를 거의 개선 할 수 없다는 것입니다. 평균 체력 비용이나 "최악의"개인의 체력은 세대에 걸쳐 향상되지 않습니다. 내가 보는 것은 최고의 개인의 점수가 약간 (작은) 개선 된 것입니다. 이는 무작위 샘플링의 결과입니다.

매개 변수의 지수를 사용하여 문제를 인코딩하는 것도 작동하지 않습니다. 이것은 아마도 염색체가 방향성이라는 사실 때문에 아마도 선택 문제는 그렇지 않기 때문에 (즉, 염색체 [1, 2, 3, 4]; [4, 3, 2, 1]; [3, 2,, 4, 1] 등이 동일합니다)

어떤 문제 표현을 제안 하시겠습니까?

추신 : 이것이 중요하다면, 나는 사용합니다 Pyevolve.

Answer 1

나는 Pyevolve에 익숙하지 않지만 유전자 알고리즘에 대해 기억할 수있는 것에서 4 단계에 관심이 있습니다.

1. chormosome 평가 (아마도 이미 이것을 알아 냈을 것입니다)
2. 염색체 초기화
3. 염색체 크로스 오버
4. 염색체 돌연변이

나는 당신이 목록으로 이것을 잘 할 수 있다고 생각합니다. 일부 연산자를 과부하해야하지만 Pyevolve처럼 보입니다. 이것을 할 수 있습니다 간단한 것은 목록 표현을 유지하는 것입니다. 염색체를 반환하기 전에 수치 적으로 분류하는 것입니다.

귀하의 문제에 대해 더 알아야하지만 여기에 제 제안이 있습니다. 가변 수의 매개 변수가 있으므로 염색체의 매개 변수 수에 대한 일종의 확률 분포를 제시해야합니다. 나는 여기서 1,2,3,4에 균일 한 무작위를 가정하지만, 더 좋아한다면 다른 것을 시도 할 수 있습니다. 이 배포판을 P_N이라고 부를 것입니다.

2. 초기화. (적어도) 3000 염색체로 인구를 뿌리십시오. 이 c_1, ..., c_3000으로 전화하십시오. p_n에서 n_j를 그립니다. C_J에 j를 넣으십시오. 나머지 매개 변수에서 균일 한 무작위 분포가있는 나머지 N_J -1 매개 변수를 선택하십시오.
3. 크로스 오버. 두 개의 염색체가 있다고 가정 해 봅시다. C_1 및 C_2. 우리는 염색체 C_3을 생성 (및 반환) 할 것입니다. 확률 1/2로 각각 {n_1, n_2}에서 n_3을 선택하십시오. 이제 C_1 및 C_2의 매개 변수를 하나의 목록에 넣습니다 (그리고 고유 한 경우 둘 다 C_1 및 C_2에는 매개 변수 1이 포함되어 있으며 한 번만 목록에 있습니다). 조인트 목록에서 n_3 매개 변수를 그려 염색체 C_3에 넣습니다.
4. 돌연변이. 염색체 C_1이 주어지면 p_n에서 n_1*를 그립니다. n_1*이 <n_1 인 경우 n_1* 요소가있을 때까지 C_1에서 요소를 무작위로 삭제하십시오. n_1* = n_1 인 경우 C_1에서 1 개의 요소 1을 무작위로 선택하고 C_1에없는 것 중에서 무작위로 선택한 매개 변수로 바꾸십시오. N_1*> N_1이면 무작위로 C_1에 요소를 추가 할 때까지 크기 N_1*을 가질 때까지 요소를 추가하십시오.

이제이 문제를 해결하는 방법에는 여러 가지가 있으므로 문제에 가장 적합한 것은 무엇입니까?

Answer 2

나는 단일 가치 분해라고 생각합니다 (http://en.wikipedia.org/wiki/singular_value_decomposition) 매개 변수 수의 한계로 인해 여기에서 더 적합 할 수 있습니다.