최적화

유전 알고리즘 정의

cBot 최적화 방법에 대해 논의할 때, cBot은 유전 알고리즘 방법을 사용하여 개선될 수 있다고 언급했습니다. 이 가이드에서는 정확히 무엇인지 그리고 어떻게 작동하는지 설명합니다.

유전 알고리즘 방법은 자연 선택 이론을 기반으로 합니다. 이 이론은 가장 적합한 개체만이 후속 생존을 위해 살아남는다고 말합니다.

cBot 최적화에서 각 최적화 패스는 개체로 간주됩니다. 개별 패스를 평가하기 위해 유전 알고리즘은 각 패스에 대한 적합도 점수를 계산하고 이 점수를 다른 모든 패스와 비교합니다.

이것이 작동하려면 유전 알고리즘은 초기 개체군이 필요합니다. 이를 생성하기 위해 최적화 도구는 무작위 매개변수로 여러 다른 패스를 실행합니다. 초기 개체군을 생성한 후, 알고리즘은 가장 적합한 최적화 패스를 찾는 과정을 시작합니다. 이 과정은 자식 패스의 적합도 점수가 정체되고 수렴하기 시작할 때까지 계속됩니다. 이 시점에서 알고리즘은 중지됩니다.

유전 알고리즘 단계

모든 유전 알고리즘은 다음과 같은 단계를 가집니다.

graph TB
  B([선택]) ==> C([교차]);
  C ==> D([돌연변이]);
  D ==> B;

단계는 다음과 같이 설명됩니다.

선택

이 단계에서 알고리즘은 각각의 적합도 점수를 사용하여 가장 적합한 두 개의 최적화 패스를 찾습니다.

교차

가장 적합한 두 개의 최적화 패스를 찾은 후, 알고리즘은 이를 사용하여 부모 패스의 매개변수 값 조합을 사용하여 새로운 자식(또는 후손) 패스를 생성합니다.

예시

cBot이 최적화를 위한 네 가지 다른 매개변수를 가지고 있다면, 알고리즘은 자식 패스의 첫 번째와 두 번째 매개변수 값을 한 부모로부터, 세 번째와 네 번째 매개변수 값을 두 번째 부모로부터 가져옵니다.

변이

이 단계에서 알고리즘은 하나 이상의 매개변수 값을 무작위로 수정하여 자식 패스를 변이시킵니다.

변이 단계 후, 최적화 도구는 새로운 자식 최적화 패스를 실행합니다. 이후, 자식 패스의 적합도 점수가 마지막 가장 적합한 최적화 패스보다 높은 경우에만 모든 단계를 반복합니다. 이러한 결과는 개선의 여지가 있음을 의미하며, 최적화가 계속되어야 함을 나타냅니다.

그렇지 않으면 알고리즘은 정체 카운터를 증가시킵니다. 정체 카운터가 알고리즘 정체 기간 매개변수 값에 도달하면 최적화 과정이 자동으로 중지됩니다.

유전 알고리즘 매개변수

유전 알고리즘은 수명 동안 사용하는 여러 매개변수를 가지고 있습니다. 이 매개변수는 변경할 수 없습니다.

매개변수	정의
개체군 크기	개체군의 최대 크기 또는 각 최적화 반복 중 수행된 패스의 최대 수.
최대 반복 횟수	알고리즘이 수행하는 최적화 반복의 최대 횟수.
정체 기간	정체 카운터의 최대 값. 이 값에 도달하면 알고리즘이 중지됩니다.
엘리트 비율	이 값은 현재 알고리즘 반복에서 가장 높은 적합도 점수를 가진 X%의 개체를 선택하는 데 사용됩니다. 이 패스는 다음 반복까지 생존합니다.
토너먼트 크기 비율	이 값은 부모 패스를 찾기 위해 반복에서 X%의 개체를 선택하는 데 사용됩니다.
이주 비율	이 값은 각 새로운 반복 또는 개체군 생성 중에 무작위로 생성된 패스의 X%를 추가하는 데 사용됩니다.
변이 비율	자식 패스의 매개변수 중 변이될 비율.
변이 확률 비율	변이될 자식 패스의 비율. 이 비율에 포함되지 않은 패스는 변이 단계를 거치지 않습니다.