진화 알고리즘 : 최적의 다시 채우기 고장 그것은 모든 제목에 정말하지만 여기에 진화 알고리즘에 관심이 누구를위한 고장의

Question

: EA의에서

는 기본 전제는 무작위로 생물의 특정 번호를 생성한다는 것입니다 (실제로는 매개 변수의 집합 임), 문제에 대해 실행 한 다음 최고 실적자가 생존하도록하십시오.

그런 다음 생존자의 교잡종, 생존자의 돌연변이 및 일정한 수의 새로운 무작위 생물을 조합하여 다시 채집하십시오.

몇 천 번 반복하면 효율적인 유기체가 생깁니다.

일부 사람들은 유기체의 여러 "섬"을 소개하는 등의 일을합니다.이 개체는 잠시 동안 교잡이 허용되는 별도의 개체군입니다.

제 질문은 다음과 같습니다. 최적의 재생 백분율은 얼마입니까?

나는 최고 10 %의 연기자를 지켜 왔으며 30 %의 교잡종과 30 %의 돌연변이로 다시 채웠다. 나머지 30 %는 새로운 유기체를위한 것입니다.

나는 다중 섬 이론을 시험해 보았습니다. 나는 그 결과에 대해서도 관심이 있습니다.

이것은 EA가 해결할 수있는 문제 유형과 정확히 같지 않습니다. 그걸 시도하는 사람을 알고 있습니까?

미리 감사드립니다.

Answer 1

처음에는 유기적 인 시스템이 어떤 것인지 생각해 보았습니다. 궁극적으로 그게 좋지 않다고 결정하고, 10 %를 유지하고 20 % 돌연변이, 60 % 크로스 번트 및 10 % 무작위로 더 공격적으로 결정했습니다.

그런 다음 상위 10 %가 모두 대략 동일하다는 사실을 알게되었습니다. 그래서 랜덤을 30 %로 늘 렸습니다. 그건 도움이되었지만별로는 아니 었습니다.

나는 여러개의 섬을 시도해 보았지만 더 나은 결과를 얻었지만, 여전히 만족스럽지 못했지만, 상위 10 %에 약간의 변화가있었습니다. 결과를 얻으려는 세대가 많았습니다. 대부분이 코드는 내 피트니스 평가를 해킹하는 방법을 배웠습니다.

최고의 연주자를 얻는 것은 정말 쉽습니다. 너무 많은 연주자를 유지하는 것에 대해 걱정하지 마십시오. 잡종 교배는 긍정적이고 부정적인 형질을 깎아 내리는 데 도움이되므로 유용하지만 실제로 원하는 것은 무작위로 자란 많은 돌연변이입니다. 돌연변이와 새로운 돌연변이에 초점을 맞추어 기능을 도입하고 교배종과 최고의 수행자들에게 최선을 추적하고 더 천천히 수정하십시오. IE : 마지막 세대를 기반으로하는 항목은 더 나은 로컬 맥시마를 찾는 것입니다. 랜덤 스는 더 나은 글로벌 맥시마를 찾습니다.

나는 과일 - 파리 비행 경로의 무작위성에 관한 최근 기사에서와 같이 자연 현상을 관찰하여 최적의 답변을 찾을 수 있다고 생각합니다.

아마도 가장 좋은 대답은 그것을 실행하고 조정하는 것입니다. 꽤 많이 조정할 것을 두려워하지 마세요. 인구는 강력합니다. 저장하고 계속하는 방법을 구현해야합니다.

Answer 2

당신은 할 수있는 일을 알고 있습니다 ... 최적의 분포를 결정하는 유전 알고리즘을 작성할 수 있습니다.

하지만 일반적으로 상위 12 %와 28 %의 교잡종을 유지합니다. 다른 사람들은 각각 30 %입니다.

Answer 3

내가 GA와 EA를 통해 만났던 최고의 자료는 Genetic Programming에 관한 John Koza의 책이었습니다. 그는 게놈을 인코딩하는 기술, 무작위 돌연변이, 육종, 피트니스 기능 튜닝에 대한 깊이있는 주제를 다룹니다.

개인적으로 나는 교육적인 목적으로 소수의 시뮬레이터 만 작성했습니다. 내가 발견 한 것은 그 비율을 조정 한 방법은 내가 사용했던 피트니스 기능의 세부 사항, 내가 얼마나 많이 도입 한 무작위 돌연변이 및 돌연변이와 번식을 시도했는지 '똑똑한'방법과 관련이 있다는 것입니다. '똑똑한'뮤 테이터와 크로스 오버 논리를 만들려고 노력하면서 인구가 더 빨리 체력 점수를 올릴수록 돌연변이 확률이 너무 보수적 인 것으로 나타났습니다. 초기 실행이 로컬 맥시마를 치고 힘든 시간을 빠져 나가.

아무 것도 구체적인 답변을 제공하지 않지만 구체적인 대답은 없다고 생각합니다. GA는 그 특성상 예측할 수 없으며 그러한 매개 변수를 조정하는 것은 여전히 ​​예술 일 수 있습니다. 물론 meta-GA를 시도해 볼 수도 있습니다. 이러한 매개 변수를 염색체로 사용하여 실행중인 기본 GA에서보다 신속한 피트니스를 생성하는 설정을 검색합니다.

'메타'방법에 따라 다릅니다.

Answer 4

이것은 매우 도메인 특정적인 것으로 보이는 뜨거운 논쟁 (참고 자료 및 Melanie, et al books) 주제입니다. n 매개 변수가있는 한 유형의 한 문제에 대해 작동하는 것은 다른 문제, 다른 도메인 또는 다른 매개 변수 집합에 대해서는 거의 작동하지 않습니다.

그래서 TraumaPony가 제안했듯이 해결하려는 각 문제에 대해 직접 조정하거나 문제를 최적화하기 위해 무언가를 작성하십시오. 할 수있는 최선의 방법은 "노브 부끄러움"과 미세 조정 실험을 모두 추적하여 솔루션 영역을 매핑하고 해당 공간에서 신속하게 최적화하는 방법에 대한 느낌을 얻을 수 있도록하는 것입니다. 힐 클라이밍과 같은 대체 기술을 시도해보십시오.

@Kyle Burton : 크로스 오버 대 돌연변이 비율은 또한 GA 및 GP에 전달되는 각 클래스의 문제에서 constantly debated입니다.

Answer 5

상위 X % 퍼센테이지를 정량화하는 방법이 있다고 가정하면 하드 코딩 된 임계 값을 사용하는 대신 성능 분포를 분석하고 성능에서 첫 번째 주요 저하 범위 내에서 어딘가에 자르기를 제안합니다 , 그 다음 틈새를 채우기 위해 crossbreads, 돌연변이와 새로운 유기체를 조정해라. 이 방법을 사용하면 매우 "생산적"으로 실행되어 다양한 변형이 성공적으로 이루어지면 상당한 수의 우수한 실적을 올리지 못합니다. 또한 "비생산적인"실행을하는 경우 더 많은 새로운 유기체를 선호하여 더 많은 기존 유기체를 폐기 할 수 있습니다.

Answer 6

2 차 GA의 최적 매개 변수를 결정하기 위해 2 차 GA를 사용하여 1 차 GA의 최적 매개 변수를 결정할 것을 제안하는 답변이 몇 개 있습니다. 이 접근법을 제안하는 사람들의 종교적 신념에 대해 의아하게 생각합니다.

Answer 7

부모 염색체의 유전자 중 두 개에서 돌연변이와 교차를 설정하여 인구의 다양성을 향상시키는 데 성공했습니다.

이것은 돌연변이 비율이 0이 될 때까지 작동합니다. 이것을하기위한주기적인 진화론 적 압력이있을 가능성이 높으므로, 이들 유전자가 최소 속도를 가지도록 노력해야합니다.

실제로, 나는 다중 염색체 유전자형을 선택했다. 하나의 염색체는 다른 사람의 생식 기능을 나타냅니다.더 작은 '복제 염색체'는 돌연변이와 교차에 대해 현명한 고정 속도를 보였다.

이것은 고전적인 고원과 인구의 수렴을 막을 것이라는 것을 알았습니다.

제쳐두고, 저는 각 어린이마다 교차와 돌연변이를하는 경향이 있습니다.

세대 간 GA의 경우, 나는 엘리트주의를 모두 배척하려고 노력하지만, 여러 섬에서 거주하는 경우 각 섬에서 최고 엘리트를 유지합니다. 섬이 모이면 엘리트들은 모두 번식 할 수 있습니다.

Answer 8

다른 언급했듯이 최적의 조합은 특정 문제 및 솔루션 공간 크기와 같은 기타 문제 별 요인에 따라 달라집니다.

한 세대에서 다음 세대로 진화의 붕괴를 논의하기 전에 각 세대의 크기를 고려하는 것이 중요합니다. 일반적으로 나의 접근 방식은 Koza가 그의 작품 중 일부에서 제안하는 것으로 상당히 다양한 개인 (~ 100k ~ 500k 개인)으로 시작하는 것입니다. 이러한 다양성을 처음부터 파악하려면 솔루션 공간을 버킷으로 나눈 다음 적어도 특정 수의 개인이 각 버킷에 포함되도록 할 수 있습니다. (각 개인에 대한 트리 표현이있는 경우 EG로 2, 3, ..., max_depth의 깊이로 동일한 양이 생성되도록하십시오)

실제 질문과 관련하여 명확한 접근 방법은 없지만 문제에 따라 임의성을 강조하거나 강조하지 않을 수도 있습니다. 당신이 그것을 강조하고 싶을 때, 당신은 더 적은 인원 수를 유지하고 더 많은 새로운 임의의 개인을 소개해야합니다. 일반적으로 솔루션 공간에 로컬 최대 값이 많고 더 넓은 검색을 원할 경우이 작업을 수행하는 것이 좋습니다.

휴식을 취할 때 고려해야 할 몇 가지 사항이 있습니다. 하나, 중복 (맨 위의 근친 교배에서 동일하거나 많이 동일한 개인)입니다. 이를 줄이려면 세대 간 인구를 스윕하고 새로운 무작위 적 개체 또는 교잡 된 개체로 중복을 대체 할 수 있습니다.

내 말은 현재 상위 1 %를 유지하고 상위 20 %를 새로운 20 %로 교잡하고 상위 20 %를 다음 20 %로 교배하며 상위 90 %를 교배하여 다음 20 개를 생성하는 것입니다 나머지는 무작위로 생성한다 (39 %). 중복이있는 경우이를 제거하고 새로운 임의의 개인으로 교체합니다.

나는 다음의 교배 기간 동안 높은 숫자의 무작위 개인이 "돌연변이"를 추가해야하므로 돌연변이를 사용하지 않습니다.