진화 알고리즘:최적의 재채집 분석

Question

실제로 제목에 모든 내용이 나와 있지만 진화 알고리즘에 관심이 있는 사람을 위해 여기에 세부 내용이 나와 있습니다.

EA의 기본 전제는 특정 수의 유기체(실제로는 매개변수 집합일 뿐임)를 무작위로 생성하고 이를 문제에 맞서 실행한 다음 최고의 성능을 발휘하는 유기체가 살아남도록 하는 것입니다.

그런 다음 생존자의 교배종, 생존자의 돌연변이 및 특정 수의 새로운 무작위 유기체의 조합으로 다시 채워집니다.

그런 일을 수천 번 하면 효율적인 유기체가 생겨납니다.

어떤 사람들은 때때로 교배가 허용되는 별도의 개체군인 유기체의 여러 "섬"을 도입하는 등의 작업도 수행합니다.

그래서 내 질문은 다음과 같습니다.최적의 재인구 비율은 얼마입니까?

나는 상위 10% 성과자를 유지하고 30% 교배종과 30% 돌연변이로 다시 채워왔습니다.나머지 30%는 새로운 유기체를 위한 것입니다.

나는 또한 다중섬 이론을 시험해 보았는데, 그에 대한 당신의 결과에도 관심이 있습니다.

이것이 바로 EA가 해결할 수 있는 문제 유형이라는 사실을 저는 잊지 않았습니다.그런 일을 시도하는 사람이 있다는 걸 알고 있나요?

미리 감사드립니다!

Answer 1

나는 처음에 유기 시스템이 생각하는 것을 모델링하려고 노력했다. 궁극적으로 그것은 좋지 않다고 결정했고, 10%를 유지하고, 20% 돌연변이, 60% 교배 및 10% 무작위로 더 공격적으로 결정했습니다.

그런 다음 내 상위 10%가 모두 거의 동일하다는 것을 알았습니다. 그래서 나는 무작위를 30%로 증가시켰다. 그것은 일부 도움이되었지만 그다지 많지는 않았습니다.

나는 다수의 섬과 세대를 자극하고 재현을 시도한 결과, 더 나은 결과를 얻었지만 여전히 불만족스럽고, 10%, 미친 세대의 수많은 차이가 거의 없어서 결과를 얻었습니다. 대부분 코드는 체력 평가를 해킹하는 방법을 배웠습니다.

최고의 공연자를 얻는 것은 정말 쉽기 때문에 너무 많은 것을 유지하는 것에 대해 걱정하지 마십시오. 크로스 브레이즈는 긍정적이고 부정적인 특성을 파괴하는 데 도움이되므로 유용하지만 실제로 원하는 것은 많은 양의 임의의 자란입니다. 돌연변이와 새로운 랜덤에 초점을 맞추고, 기능을 가져오고, 교황과 최고 공연자들을 두십시오. 최고를 추적하고 더 천천히 개선하십시오. IE : 마지막 세대를 기반으로 한 것들이 더 나은 지역 최대 값을 찾는 것입니다.

나는 여전히 당신의 질문에 대한 최적의 답변이 과일 비행 경로의 무작위성에 관한 최근 기사에서와 같이 자연 현상을 관찰함으로써 찾을 수 있다고 생각합니다.

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

Answer 2

GA와 EA에 관해 내가 접한 최고의 리소스는 John Koza의 책이었습니다. 유전 프로그래밍.그는 게놈 인코딩 기술, 무작위 돌연변이, 번식, 적합성 기능 조정 등의 주제를 심도 깊게 다룹니다.

개인적으로 나는 교육적 목적으로 소수의 시뮬레이터만을 작성했습니다.내가 발견한 것은 내가 그 백분율을 조정한 방법이 내가 사용하고 있는 피트니스 기능의 세부 사항, 내가 도입한 무작위 돌연변이의 양, 돌연변이와 번식을 만들기 위해 얼마나 '똑똑하게' 노력했는지와 관련이 있다는 것입니다. '스마트' 나는 돌연변이 유발자와 교차 논리를 만들려고 노력했고 집단의 체력 점수가 더 빨리 향상되었습니다. 또한 나는 돌연변이 확률에 대해 너무 보수적이었다는 것을 발견했습니다. 나의 초기 실행은 로컬 최대값에 도달했고 그들에게서 벗어나는 데 어려움을 겪습니다.

이 중 어느 것도 구체적인 답변을 제공하지는 않지만 구체적인 답변은 없다고 생각합니다. GA는 특성상 예측할 수 없으며 이러한 종류의 매개변수를 조정하는 것은 여전히 ​​약간의 예술일 수 있습니다.물론, 이러한 매개변수를 염색체로 사용하여 실행 중인 기본 GA에서 더 빠른 적합성을 생성하는 설정을 검색하여 언제든지 Meta-GA를 시도할 수 있습니다.

얻고 싶은 '메타' 방법에 따라 다릅니다.

Answer 3

이것은 뜨겁고 (문헌에서 Melanie 등) 매우 도메인별로 보이는 주제. N 매개 변수가있는 한 유형의 한 가지 문제에 대해 작동하는 것은 다른 문제, 다른 도메인 또는 다른 매개 변수 세트에서 거의 작동하지 않습니다.

따라서 외상이 제안한 것처럼, 당신이 해결하는 각 문제에 대해 스스로 조정하거나 당신을 위해 그것을 최적화하기 위해 무언가를 작성하십시오. 당신이 할 수있는 최선의 방법은 모든 "노브-트림 링"및 미세 조정 실험을 추적하여 솔루션 지형을 매핑하고 해당 공간 내에서 빠르게 최적화하는 방법에 대한 느낌을 얻을 수 있습니다. 또한 Hill-Climbing과 같은 대체 기술을 시도하여 이길 기준을 가질 수 있습니다.

@kyle Burton : 크로스 오버 대 돌연변이 속도도 있습니다 끊임없이 토론했습니다 각 종류의 문제에서 가스 및 GPS에 전달되었습니다.

Answer 4

상위 X% 퍼센트 수행자를 정량화하는 방법이 있다고 가정하면 하드 코드 임계 값을 사용하는 대신 성능 분포를 분석하고 첫 번째 주요 성능 하락 범위에서 컷오프를 한 다음 조정하는 것이 좋습니다. 당신의 십자형, 돌연변이 및 새로운 유기체가 틈을 메우는 유기체. 이런 식으로 많은 변형이 성공한 매우 "생산적인"실행이 있다면 상당수의 고성능자를 던지지 않습니다. 또한 "비생산적인"달리기가 있다면 더 새로운 유기체를 선호하여 기존 유기체를 더 많이 긁어 모아야합니다.

Answer 5

나는 부모 염색체의 두 유전자로부터 돌연변이와 교차를 설정함으로써 인구의 다양성을 증가시켰다.

이것은 돌연변이 속도가 0으로 떨어질 때까지 작동합니다. 이를 수행하기위한 주기적 진화 압력이있을 가능성이 높기 때문에 이러한 유전자에 최소 속도가 있는지 확인해야합니다.

실제로, 나는 다중 chromosome 유전자형을 선택했습니다. 하나의 염색체는 다른 염색체의 생식 기능을 위해 코딩되었습니다. 더 작은 '생식 염색체'는 돌연변이 및 교차에 대한 합리적인 고정 속도를 가졌다.

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

제쳐두고, 나는 각 어린이에 대해 크로스 오버와 돌연변이를 모두 수행하는 경향이 있습니다.

세대 가스의 경우, 나는 엘리트주의를 완전히 피하려고 노력하지만 여러 섬에서 채워지는 곳에서는 각 섬에서 최고 엘리트를 유지합니다. 섬이 모이면 엘리트들은 모두 함께 번식 할 수 있습니다.

Answer 6

2nd GA에 대한 최적 파라미터를 결정하기 위해 2nd GA를 사용하여 2nd의 최적 매개 변수를 결정하는 방법에 대한 언급이없는 몇 가지 답변이있는 것으로 보입니다. 나는이 접근법을 제안하는 사람들의 종교적 신념에 대해 궁금해 할 수 없지만 ...

Answer 7

다른 사람들이 언급했듯이, 최적의 믹스는 특정 문제 및 솔루션 공간의 크기와 같은 다른 문제 별 요소에 따라 다릅니다.

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

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

분류를 얻을 때 고려해야 할 몇 가지 사항이 있습니다 ... 한 번의 복제 (최상위 근친 교배의 동일하거나 새로 동일한 개인). 이를 줄이려면 세대 사이에 인구를 휩쓸고 복제를 새로운 임의의 개인 또는 교통 개체로 대체 할 수 있습니다.

즉, 현재의 접근 방식은 상위 1%를 유지하고, 상위 20%를 새로운 20%로 크로스 베어링하고, 상위 40%를 다음 20%로 크로스 베어링하고, 다음 20%를 생성하기 위해 상위 90%를 크로스 베어링했습니다. 나머지를 생성하십시오 (39%). 복제물이 있으면 복제를 제거하고 새로운 임의의 개인으로 교체합니다.

많은 수의 임의의 개인이 다음과 교배 기간 동안 "돌연변이"를 첨가해야하기 때문에 돌연변이를 사용하지 않습니다.

Answer 8

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

그러나 보통 나는 상위 12%와 28%의 교배를 유지합니다. 다른 사람들은 각각 30%로.