유전자 알고리즘 최적화?

Question

성능 향상을 위해 유전자 알고리즘 병렬 처리를 해왔지만 유전 알고리즘을 최적화하는 데 일반적으로 사용되는 기술이 무엇인지 궁금합니다.

Answer 1

적합도 값을 자주 다시 계산하므로 (알고리즘 실행에 따라 인구의 다양성이 감소 함) GA 성능을 향상시키는 좋은 전략은 적합성을 계산하는 데 필요한 시간을 줄이는 것입니다.

세부 정보는 구현에 따라 다르지만 이전에 계산 된 적합도 값은 종종 해시 테이블과 함께 효율적으로 저장 될 수 있습니다. 이러한 종류의 최적화로 계산 시간이 크게 단축 될 수 있습니다 (예 : "IMPROVING GENETIC ALGORITHMS PERFORMANCE BY HASHING FITNESS VALUES" - RICHARD J. POVINELLI, XIN FENG은 GA에 대한 해시 적용이 복잡한 실제 문제에 대해 50 % 이상 성능을 향상시킬 수 있음을보고합니다).

핵심 포인트는 충돌 관리입니다. 해시 테이블의 기존 요소를 덮어 쓰거나 스키마 (예 : 선형 프로브)를 채택 할 수 있습니다.

후자의 경우 충돌이 탑재됨에 따라 해시 테이블의 효율성이 선형 검색의 효율성으로 저하됩니다. 누적 충돌 수가 해시 테이블 크기를 초과하면 더 큰 해시 테이블을 만들고 더 작은 해시 테이블의 요소를 더 큰 해시 테이블로 복사해야합니다.

복사 단계을 생략 할 수 있습니다. GA가 실행될 때 다양성이 감소하므로 제거 된 요소가 많이 사용되지 않고 가장 자주 사용되는 염색체 값이 신속하게 다시 계산됩니다 (해시 테이블이 다시 채워집니다). 가장 많이 사용되는 키 요소 값).

Answer 2

내가 한 일은 적합성 계산의 수를 제한하는 것입니다. 예를 들어, 풍경이 시끄럽지 않은 경우, 즉 피트니스의 재 계산으로 매번 동일한 답변이 나오는 경우 재 계산하지 않고 단순히 답을 캐시하십시오.

또 다른 접근법은 메모리 연산자를 사용하는 것입니다. 운영자는 솔루션의 '메모리'를 유지 관리하고 해당 메모리에서 최상의 솔루션이 GA 인구에 포함되어 있는지 확인합니다. GA 실행 중에 좋은 해결책으로 메모리가 최신 상태로 유지됩니다. 이 접근법은 필요한 적합성 계산 횟수를 줄이고 성능을 향상시킬 수 있습니다.

http://johnnewcombe.net/blog/gaf-part-8/ http://johnnewcombe.net/blog/gaf-part-3/

:

나는 여기에이 물건의 몇 가지의 예를