개시하다

저번 기린을 예로 들면 유전 알고리즘을 봤다.
이번에는 원맥스 문제와 같은 간단한 수학 문제를 예로 들어 프로그램에 대한 관점에서 설명한다.

OneMax 질문

먼저 원맥스 문제가 뭔지 설명해 주세요.매우 간단하니 경원하지 마십시오😄
원맥스는 예를 들어 0과 1의 숫자 10개로 구성된 [1,0,1,1,1,1,0,1]과 같은 수열의 합을 어떻게 극대화할 것인가의 문제다.
사람이 보기엔 너무 쉬워.모두 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1이 되면 이 몇 열의 합이 가장 크다.
이 보도의 취지는 억지로 유전 알고리즘으로 이 초간단한 문제를 해결하려는 것이다.

유전 알고리즘으로 vOneMax 문제 해결 프로세스

지난번 보도 "기린을 예로 삼아 유전 알고리즘을 보다"와 같은 절차로 설명하기 때문에 적절하게 비교해보세요.

① 개인 그룹의 제작

먼저 개인 그룹을 만든다.
0과 1의 무작위 그룹을 많이 만듭니다.
사실 더 많이 할 건데 이번엔 설명 편하게 6개만 할게요.

② 개인평가

각 개체를 평가하고 점수를 매기다.
이번 평가점은 수열의 합계이기 때문에 각 수열의 합계를 계산해 점수로 삼는다.예를 들어 [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1]의 점수는 2점이다.

③개체 선택

평가가 높은 것을 다음 세대에 계승하기 위해 남겨두다.

④교차

③ 중에서 선택한 개체 중에서 아이를 만든다.
두 개체를 어딘가에서 두 부분으로 나누어 뒷부분을 교환한다.
분리할 곳을 무작위로 선택하다.
처음 6개 개체를 만들었기 때문에 똑같이 6개 개체를 만들었다.
일부 개체에 대해 교차할 필요가 없고 ③에서 선택한 개체를 보존할 수도 있다.


교차로 된 게 이거예요.

⑤돌연변이

진화의 다양성을 유지하기 위해 일부 체득에 갑자기 변이가 생겼다.
갑작스런 변이가 발생한 곳과 변이가 발생한 후의 값은 모두 무작위이다.

이렇게 해서 차세대 개체 단체가 형성되었다.
처음보다 많이 알고 싶어요.↓

⑥ 반복 ②~⑤

새로 설립된 개인 집단에 대해 ②에서 ⑤까지 반복한다.
②부터 ⑤까지 하면 이렇게 되는 느낌.↓(랜덤 요소가 많기 때문에 항상 인상이다.)

최초의 개인 단체에 비해 1이 갈수록 많아지고 있다.
10대를 반복하면 이렇게 되겠지.↓

이렇게 되면 거의 모든 개체가 10점이나 9점이면 점수가 더 이상 오르지 않는다.
그리고 마지막 세대의 가장 좋은 개체가 가장 좋은 해결 방안으로 도출된다.
이렇게 [1,1,1,1,1,1,1,1]하면 답이 된다.

총결산

인간이 보기에는'아니야, 다 1을 고르면 돼'하면서도 굳이 유전 알고리즘으로 문제를 풀려면 그런 흐름이다.
유전 알고리즘의 강점은 그와 같은 절차만으로는 계산할 수 없는 문제도 답을 얻을 수 있다는 점이다.
간단하게 실현하는 것은 유전 알고리즘의 가장 큰 장점이라고 할 수 있다.
Twitter@ruemura3