서론
august14님께서 BOJ에서 이벤트를 개최하셨습니다. (이벤트 공지)
다항시간 안에 해결하지 못하는 문제를 적절히 잘 풀어나가는 이벤트로, 재미있어 보이길래 참가했습니다. 이벤트가 2일만에 끝나서 아쉽긴 하지만, 여러가지 시도를 많이 해봤고 오랜만에 재밌게 문제를 풀 수 있었습니다.
3월 16일에 이벤트가 끝나면 올릴 생각이었지만 일찍 끝났길래 지금 올립니다.
이 글에서는 2일동안 제가 이 문제를 풀기 위해 시도한 것들을 정리합니다.
유전 알고리즘을 이용해 그래프 컬러링 문제를 해결하는 것을 주제로 고등학교 1학년 겨울방학에 동아리 프로젝트를 진행한 적이 있습니다. (링크1, 링크2)
이 문제에서도 유전 알고리즘이 꽤 강력할 것으로 생각해, 유전 알고리즘을 사용했습니다.
방법 1 - 시작
교차를 할 때 원소를 하나씩 옮기는 것보다는 적당한 덩어리를 골라 옮기는 것이 이득인 것은 당연합니다. 처음에는 교차 방법을 다음과 같이 정의했습니다.
8×14 배열을 8조각으로 나눈 뒤, 두 개의 부모 유전자에서 동일한 확률로 하나를 골라 물려줌
돌연변이는 각 유전자에 대해 10%의 확률로 수행하며, 돌연변이는 각 원소에 대해 1%의 확률로 값을 바꿔주는 것으로 정했습니다. 선택은 이벤트 시작부터 끝날 때까지 계속 룰렛 휠 방식을 사용했습니다.
이 방법으로 약 2000점 이상을 뽑아낼 수 있습니다.
방법 2 - 새로운 교차 정책
2000점 이상인 데이터를 여러 개를 만든 뒤, 초기 유전자에 넣은 상태로 유전 알고리즘을 돌리는 것을 시도했습니다. 약 2500점 정도의 결과가 꾸준하게 나오게 되었습니다.
교차 정책을 바꿨습니다.
무작위로 직사각형 영역을 선택한 뒤, 해당 부분만 교차
교차 정책을 바꾸고 다시 한 번 2500점 이상인 데이터를 여러 개 만들고 돌렸더니 3000점 정도가 나왔고, 더 이상 이 방법으로는 효과를 보지 못했습니다.
방법 3 - 지역 최적화 + 새로운 정책 몇 가지
까먹고 있던 것이 있었습니다! 위에서 언급한 동아리 프로젝트에서 좋은 성능을 뽑을 수 있었던 이유는 강력한 지역 최적화가 동반되었기 때문입니다.
지역 최적화 방법을 고민하다가, 꽤 괜찮은 아이디어를 떠올렸습니다.
현재 점수가 T라면 원소 하나를 바꿔 T+1을 만드는 것을 시도
구현하기 쉬우면서 성능도 괜찮았습니다. 랜덤 유전자에서 5분만에 3000점을 뽑을 수 있게 됩니다.
여기에서 돌연변이 정책과 대치 정책을 변경했습니다.
- 대치 정책
- 다음 세대 중 10개는 현재 세대에서 가장 좋은 10개 선택
- 다음 세대 중 10개는 현재 세대에서 룰렛 휠로 선택
- 다음 세대 중 10개는 현재 세대에서 랜덤으로 선택
- 다음 세대 중 70개는 룰렛 휠로 2개 골라서 교차
- 돌연변이 정책
- 가장 큰 3개는 돌연변이를 하지 않음
- 점수 순으로 8등 이후인 경우, 10%의 확률로 완전 랜덤으로 초기화
- 위 2개에 해당하지 않는 경우 기존 정책 유지
4000점까지 나오게 됩니다.
방법 4 - 지역 최적해 탈출
지역 최적해에 빠지면 더 이상 발전을 할 수 없습니다. 지역 최적해에서 탈출하는 방법을 고민했습니다.
30세대 이상 발전이 없으면 각 유전자마다 원소 2개를 swap하는 행위를 10~500회 반복
주기적으로 재실행을 하지 않아도 알아서 탈출을 하기 때문에 꽤 괜찮은 선택이었다고 생각합니다.
방법 5 - 평가 기준 변경
1부터 5000까지의 수 중에서 얼마나 많은 수를 만들 수 있는지 확인해보았고, 약 50개를 제외하면 다 만들 수 있었습니다. 10000까지 확인했을 때도 200개 미만의 수만 비어있었습니다. 중간 중간에 뚫린 몇 개만 채워주면 점수가 많이 올라갈 수 있다는 것을 알게되었습니다.
룰렛 휠의 기준을 아래와 같이 바꿨습니다.
1부터 5000까지 만들 수 없는 수가 나올 때마다 점수의 증가폭을 1/2로 줄임.
방법 6 - 지역 최적화 속도 향상
이유는 모르겠지만, 실행 속도가 매우 느려졌습니다. 지역 최적화 코드의 수행 시간을 대폭 향상시킬 좋은 방법을 찾아야만 했고, 의외로 쉽게 찾았습니다.
지금까지는 모든 칸을 일일히 바꿔보면서 최적화를 했습니다. 탐색 공간을 줄이기 위해서, 점수를 T라고 했을 때 1부터 T까지 만드는데 사용된 칸을 제외한 칸들만 바꿔주면서 최적화를 진행하는 것으로 바꿨습니다.
수행 시간 상으로는 많은 커팅이 되지만, 점수 향상 속도는 높지 않았습니다.
그래서 10%의 확률로 커팅을 동반하지 않은, 기존의 방법을 이용해 지역 최적화를 수행하도록 바꿨습니다.
방법 5와 방법 6을 이용해 답을 구하던 도중, 이벤트가 끝나버렸습니다.
기타
성능적인 측면 말고 로그나 visualization 관련해서도 많이 발전했지만, 저는 해당 부분에 참여하지 않았기 때문에 생략합니다.
코드
- API.md 에는 각 클래스의 설명이 작성되어 있습니다.
- jhnah917-method.md 에는 협업 이전에 제가 사용하던 방식이 기록되어 있습니다.
- 프로그램을 실행하는 경우, 시작할 때 나오는 문구를 잘 읽어주시기 바랍니다.
마지막으로, 짧은 시간이었지만 재미있는 이벤트를 운영해주신 august14님께 감사의 말씀 전합니다.