📂Optimization

What is a Tournament in Genetic Algorithms?

Definition ¹

genetic algorithm에서 tournament란 일부 개체 간의 적합도를 직접 비교하여 적합도가 낮은 개체를 누락시키고 다음 세대로 넘겨 natural selection하는 방법이다.

Explanation

tournament는 예를 들어 전체 solution set에서 무작위로 2개씩 짝을 짓도록 하고, 각 쌍마다 적합도가 낮은 개체를 삭제하는 식으로 구현할 수 있다. 이렇게 가해지는 선택압은 어떠한 복잡한 수단이나 hyperparameter 조정 없이도 자연스럽게 적합도가 높은 개체가 살아남도록 한다. 물론 적합도의 비교에서 일정 확률로 열세인 개체가 살아남도록 한다거나, 여러 개체를 한꺼번에 뽑아서 여러 생존자를 선정하는 등 다양한 변형이 가능하다.

elitism는 일정 수준 이상의 적합도를 가진 개체에게 반드시 살아남는다는 특권을 주고, 이들은 자신들을 뛰어넘는 변화가 있지 않은 이상 계속해서 버틸 수 있다. 그에 비해 토너먼트는 실제로 스포츠 등에서 그러하듯 이변이 일어날 수 있는 방식으로, 어지간한 적자라 할지라도 본인보다 뛰어난 적합도를 가진 개체와 맞붙게 될 경우 얼마든지 도태될 수 있다.